Parallel Supercomputing Using PCs/Workstations and a Synchronization Box

Hank Dietz
Assoc. Prof. of Electrical and Computer Engineering
Purdue University
West Lafayette, IN 47907-1285

Abstract

Parallel processing offers the potential to achieve faster program execution by having multiple processors work together. Traditionally, these processors were contained within a dedicated parallel supercomputer; now, it may be more cost-effective to use the processors of a group, or cluster, of PCs or workstations. The problem with clusters as parallel machines is that conventional networks were not designed to coordinate processors working on a single program, but to transfer large blocks of data between essentially independent systems.

Instead of using conventional network hardware and software, we suggest that it may be more appropriate to use a simple custom synchronization unit to coordinate the actions of a cluster of machines. In particular, we discuss how PAPERS, Purdue's Adapter for Parallel Execution and Rapid Synchronization, can make a cluster behave as a single tightly-coupled parallel supercomputer.

Parallel Supercomputing?

Multiple processors cooperate to speed-up a computation
Execution mode
- MIMD (most often SPMD)
- SIMD
- VLIW
Communication/synchronization model
- Shared memory/locks or semaphores
- Message passing/signals or active messages
- Aggregate functions/barriers

Using PCs (Workstations)

Multiple PCs cooperate to speed-up a computation
PCs are
- High performance per unit cost
- Mature systems, clear upgrade paths
- Politically correct
High-bandwidth PC networks are cheap
- $200/PC for 10 Mbits/s Ethernet
- $2,000/PC for 100 Mbits/s Ethernet
- $3,000/PC for 155 Mbits/s ATM

Why Not?

Execution mode
- Only MIMD (most often SPMD)
Communication/synchronization model
- Only message passing/signals or active messages
Networks have bandwidth, but latency...?
- Latency determines minimum grain size
- Coarser grain means fewer applications
- 1,000 us latency ~= 100,000 FLOP granularity

Sources of Latency

Actual network transmission time
Network interface and routing overhead
Message formatting and tag handling
Unreliable transport mechanisms
Interrupt and context switch overhead
Memory-based buffering
OS-level protocols (e.g., BSD sockets)
Constructed collective operations
User-level messaging libraries (e.g., PVM)

What is PAPERS?

Purdue's Adapter for Parallel Execution and Rapid Synchronization
Hardware support for parallel processing on a cluster
- Cost less than $100/PC
- Latency as low as < 3 us
- Efficiently supports all modes and communication models
Works with almost any workstations and/or PCs
Public domain hardware design and software

What's in TTL_PAPERS

TTL_PAPERS	TTL_PAPERS 951201

What's in PAPERS

Each PC connects via standard parallel port...
Will improve bandwidth, add aggregates
PAPERS unit contains 4 subsystems:
- Fast barrier synchronization hardware
- LED status display
- Aggregate function data communication
- Parallel signal support

Barrier Synchronization

An arbitrary group of PCs can participate
No PC executes past a barrier until all have arrived
Two-cycle barriers using two barrier units:
1. Output: present at barrier, reset barrier'
2. Input: poll for all PCs present
Synchronization time:
- < 0.1 us logic, < 0.2 us cable, 1 us port register
- Total < 3 us for 4 PCs; < 7 us for 2,000+ PCs

LED Status Display

Blue power on
Bi-color LED/PE
- Green: running
- Red: at barrier
- Orange: in OS
- Black: no program

A Simple Demonstration

Cluster of 4 sub-notebooks
Multi-voice music
Each note is randomly assigned to a PC;
PCs without notes have red LEDs
Without precise coordination, it isn't music

Aggregate Functions

Not shared memory nor message passing
As a barrier side-effect, each PC can:
1. Output: a datum
2. Input: selected function of data from all PCs
Can examine global state in a single operation

Can simulate shared memory & message passing

Aggregate Functions

Broadcast: bcastPutType(d), bcastGetType()
Multi-broadcast: putgetType(d, s)
Associative reductions: reduceOpType(d)
Scans (parallel prefix): scanOpType(d)
SIMD conditionals: any(f), all(f)
VLIW multi-way branch: waitvec(f)
Voting & scheduling: vote(s), matchType(d)

Performance (us latency)

Machine Barrier Sync. 32-bit Putget (permutation) 64-bit Broadcast

MasPar MP-1 0.1 44.0 31.0

486 Linux
(PAPERS1) 3.1 27.0 81.0

Cray T3D (PVM) 21.0 82.0

486 Linux
(TTL_PAPERS) 2.5 216.0 137.0

Intel Paragon XP/S 530.0 700.0 210.0

486 Linux
(Ethernet PVM3) 49,000.0 100,000.0 40,000.0

Machine	Barrier Sync.	32-bit Putget (permutation)	64-bit Broadcast
MasPar MP-1	0.1	44.0	31.0
486 Linux (PAPERS1)	3.1	27.0	81.0
Cray T3D (PVM)	21.0		82.0
486 Linux (TTL_PAPERS)	2.5	216.0	137.0
Intel Paragon XP/S	530.0	700.0	210.0
486 Linux (Ethernet PVM3)	49,000.0	100,000.0	40,000.0

Parallel Signals

Any PC can asynchronously signal all PCs
Separate barrier used for signal acknowledge
Used for:
- Parallel job control, gang scheduling
- Asynchronous shared memory
- Asynchronous message passing

Shared Memory

Asynchronous atomic access to shared objects
Each PC has a copy, always up-to-date
C++ templates intercept operations on shared objects
- Lvalue store causes s_write(a, s);
  Signal and update, ~60 us typical
- Rvalue fetch causes s_poll();
  Poll and local fetch, ~1 us
Load balancing shared-memory Mandelbrot achieves > 250 MFLOPS using 4 Pentium 90 TTL_PAPERS

TTL_PAPERS 951201, 386	TTL_PAPERS, 486	TTL_PAPERS, Pentium

So Many PAPERS...

What's been done?
- Built & tested 8 types at Purdue
- Tested with Linux (386, 486, Pentium), AIX (PowerPC), and OSF/1 (Alpha)
- Full library, compiler support
- TTL_PAPERS at 5+ other universities
Support from
ONR, Intel, IBM, DEC, TI, NSF, & AMD
Looking for commercial partners...

Conclusion

Barrier synchronization can provide
- Aggregate function communication
- Support for MIMD, SIMD, and VLIW modes
- Emulated shared memory & message passing
- Simpler, faster, hardware structures
PAPERS proves it works;
See http://garage.ecn.purdue.edu/~papers
Lots more compiler, OS, and architecture to come