# Presentation: 659463

## CS 267 Applications of Parallel ComputersLecture 8:Distributed Memory Computers 

**Horst D. Simon**
**Sept. 19, 2002**
**http://www.cs.berkeley.edu/~strive/cs267**

## Recap of Last Lectures

**Shared memory processors ****(Lect. 5, 9/10/2002)**
**Caches in individual processors must be kept ****coherent**** -- multiple cached copies of same location must be kept equal.**
**Requires clever hardware (see CS258).**
**Distant memory much more expensive to access.**
**Shared memory programming ****(Lect. 6, next discussion section)**
**Starting, stopping threads.**
**Synchronization with barriers, locks.**
**OpenMP is the emerging standard for the shared memory parallel programming model.**

## Recap of Last Lectures (cont.)

**Distributed memory programming ****(Lect. 7, 9/17/2002 by J. Carter)**
**MPI (message passing interface)**
**MPI syntax and concepts**
**Synchronization with messages**
**Blocking and non-blocking send/receive calls**
**Collective communication calls**

## Outline

**Distributed Memory Architectures**
**Topologies**
**Cost models**
**Sharks and Fish Example**
**Gravity**

## Historical Perspective

**Early machines were:**
**Collection of microprocessors.**
**Communication was performed using bi-directional queues between nearest neighbors.**
**Messages were forwarded by processors on path.**
**There was a strong emphasis on topology in algorithms, in order to minimize the number of hops.**

## Network Analogy

**To have a large number of transfers occurring at once, you need a large number of distinct wires.**
**Networks are like streets:**
**Link = street.**
**Switch = intersection.**
**Distances (hops) = number of blocks traveled.**
**Routing algorithm = travel plan.**
**Properties:**
**Latency: how long to get between nodes in the network.**
**Bandwidth: how much data can be moved per unit time:**
**Bandwidth is limited by the number of wires and the rate at which each wire can accept data.**

## Characteristics of a Network

**Topology (how things are connected)**
**Crossbar, ring, 2-D and 2-D torus, hypercube, omega network.**
**Routing algorithm:**
**Example: all east-west then all north-south (avoids deadlock).**
**Switching strategy:**
**Circuit switching: full path reserved for entire message, like the telephone.**
**Packet switching: message broken into separately-routed packets, like the post office.**
**Flow control (what if there is congestion):**
**Stall, store data temporarily in buffers, re-route data to other nodes, tell source node to temporarily halt, discard, etc.**

## Properties of a Network

**Diameter****:  the maximum (over all pairs of nodes) of the shortest path between a given pair of nodes.**
**A network is ****partitioned ****into two or more disjoint sub-graphs if some nodes cannot reach others.**
**The ****bandwidth ****of a link =   w * 1/t**
**w is the number of wires**
**t is the time per bit**
**Effective bandwidth**** is usually lower due to packet overhead.**
**Bisection bandwidth:  ****sum of the bandwidths of the minimum number of channels which, if removed, would partition the network into two sub-graphs.**

## Network Topology

**In the early years of parallel computing, there was considerable research in network topology and in mapping algorithms to topology.**
**Key cost to be minimized in early years:  number of “hops” (communication steps) between nodes (e.g. “store and forward”)**
**Modern networks hide hop cost (I.e., “wormhole routing”), so the underlying topology is no longer a major factor in algorithm performance.**
**Example:  On IBM SP system, hardware latency varies from 0.5 usec to 1.5 usec, but user-level message passing latency is roughly 36 usec.**
**However, since some algorithms have a natural topology, it is worthwhile to have some background in this arena.**

## Linear and Ring Topologies

**Linear array**
**Diameter = n-1; average distance ~ n/3.**
**Bisection bandwidth = 1.**
**Torus or Ring**
**Diameter = n/2; average distance ~ n/4.**
**Bisection bandwidth = 2.**
**Natural for algorithms that work with 1D arrays.**

## Meshes and Tori 

**2D**
**Diameter =   2 * ********n**
**Bisection bandwidth =   n**
**             ****2D mesh                                           2D torus**

-  **Often used as network in machines.**
** ****Generalizes to higher dimensions (Cray T3D used 3D Torus).**
** ****Natural for algorithms that work with 2D and/or 3D arrays.**

## Hypercubes

**Hypercubes**

**Number of nodes n = 2****d   ****for dimension d.**
**Diameter = d. **
**Bisection bandwidth = n/2.**
**    ****0d       1d       2d           3d                  4d**
**Popular in early machines (Intel iPSC, NCUBE).**
**Lots of clever algorithms. **
**See 1996 notes.**
**Greycode addressing:**
**Each node connected to                                                                            d others with 1 bit different. **

- 001

- 000

- 100

- 010

- 011

- 111

- 101

- 110

## Trees

**Diameter = log n.**
**Bisection bandwidth = 1.**
**Easy layout as planar graph.**
**Many tree algorithms (e.g., summation).**
**Fat trees avoid bisection bandwidth problem:**
**More (or wider) links near top.**
**Example: Thinking Machines CM-5.**

## Butterflies

**Diameter = log n.**
**Bisection bandwidth = n.**
**Cost: lots of wires.**
**Used in BBN Butterfly.**
**Natural for FFT.**

## Evolution of Distributed Memory Multiprocessors

**Special queue connections are being replaced by direct memory access (DMA):**
**Processor packs or copies messages.**
**Initiates transfer, goes on computing.**
**Message passing libraries provide store-and-forward abstraction:**
**Can send/receive between any pair of nodes, not just along one wire.**
**Time proportional to distance since each processor along path must participate.**
**Wormhole routing in hardware:**
**Special message processors do not interrupt main processors along path.**
**Message sends are pipelined.**
**Processors don’t wait for complete message before forwarding. **

## Performance Models

## PRAM

**Parallel Random Access Memory.**
**All memory access operations complete in one clock period -- no concept of memory hierarchy (“too good to be true”).**
**OK for understanding whether an algorithm has enough parallelism at all.**
**Slightly more realistic:  Concurrent Read Exclusive Write (CREW) PRAM.**

## Latency and Bandwidth Model

**Time to send message of length n is roughly.**
**Topology is assumed irrelevant.**
**Often called “******** model” and written**
**Usually ******** >> ******** >> time per flop.**
**One long message is cheaper than many short ones.**
**Can do hundreds or thousands of flops for cost of one message.**
**Lesson:  Need large computation-to-communication ratio to be efficient.**

**Time = latency + n*cost_per_word**
**         ****= latency + n/bandwidth**

**Time = ******** + n*******

****** ****n********n******

## Example communication costs

****** ****and ******** measured in units of flops, ******** measured per 8-byte word**

- Machine                          Year                                 Mflop rate per proc

-     CM-5                             1992     1900       20                            20
-     IBM SP-1                      1993     5000        32                          100
-     Intel Paragon                1994     1500          2.3                         50
-     IBM SP-2                      1994     7000        40                          200
-     Cray T3D (PVM)           1994     1974        28                            94
-     UCB NOW                    1996     2880        38                          180
-     SGI Power Challenge   1995     3080        39                          308
-     SUN E6000                   1996    1980           9                         180

- Exercise: Determine andfor IBM SP and Millenium.
- Hint: Look for data in these lecture notes

## A more detailed performance model: LogP

**L: latency across the network. **
**o: overhead (sending and receiving busy time).**
**g: gap between messages (1/bandwidth).**
**P: number of processors.**
**People often group overheads into latency                 (******** model).**
**Real costs more complicated -- see Culler/Singh, Chapter 7.**

## End to End Latency Over Time

**Latency has not improved significantly**
**T3E (shmem) was lowest point**
**Federation in 2003 will not reach that level – 7 years later!**

**Data from Kathy Yelick, UCB and NERSC**

## Send Overhead Over Time

**Overhead has not improved significantly; T3D was best**
**Lack of integration; lack of attention in software**

**Data from Kathy Yelick, UCB and NERSC**

## Results: EEL and Overhead

**Data from Mike Welcome, NERSC**

**Notes:**
The height of bars = end-to-end one-way latency.  
Red is send overhead alone
Blue is recv overhead alone
Purple shows overlap of send and receive overhead
White is wire latency, or the part of the end-to-end latency that is not explained by send and receive overhead in the CPU.  This will include latency incurred on the network as well as by the NICs on both nodes.
Note that many of the high performance systems have no measurable receive overhead.  On the T3E, the data is placed directly in the remote processors E-registers so there is noting to that processor to do.  For quadrics, myrinet and Giganet, the NIC performs DMA to the application host memory so receive overhead is low.  Note that all MPI implementation have receive overhead because, at a minimum, send/recv matching operations must be performed.
Note also the latency hiding effects of communication networks in which send and receive overhead overlap in time.

## Bandwidth Chart

**Data from Mike Welcome, NERSC**

**Notes:**
Although we emphasize latency in this talk, there are occasions in GAS languages where large-message bandwidth is important.  This graph
Displays the characteristics of the various networks.
Note that the IBM finally shines, but only if you use LAPI.  The difference between MPI and LAPI is probably an additional data copy.
The T3E shmem performance nearly peaks out the torus bandwidth even for 4k messages.
The quadrics and Dolphin bandwidth are probably limited by the PCI bus 
As well as Giganet (for older, 32 bit, 33Mhz PCI bus).
Why is Myrinet so slow?

## Message Passing Libraries

**Many “message passing libraries” available**
**Chameleon, from ANL.**
**CMMD, from Thinking Machines.**
**Express, commercial.**
**MPL, native library on IBM SP-2.**
**NX, native library on Intel Paragon.**
**Zipcode, from LLL.**
**PVM, Parallel Virtual Machine, public, from ORNL/UTK.**
**Others...**
**MPI, Message Passing Interface, now the industry standard.**
**Need standards to write portable code.**
**Rest of this discussion independent of which library.**
**Lecture 7 was detailed MPI lecture**

## Workstation/PC Clusters

**Reaction to commercial MPPs:**** **
**build parallel machines out of commodity components**
**Inexpensive workstations or PCs as computing nodes**
**Fast (gigabit) switched network between nodes**
**Benefits:**
**10x - 100x cheaper for comparable performance**
**Standard OS on each node**
**Follow commodity tech trends**
**Incrementally upgradable and scalable**
**Fault tolerance**
**Trends:**
**Berkeley NOW (1994): 100 UltraSPARCs, Myrinet**
**ASCI RED (1997): 4510 dual Pentium II nodes, custom network**
**Millennium (1999): 100+ dual/quad Pentium IIIs, Myrinet**
**Google (2001): 8000+ node Linux cluster, ??? network**

## Contributions of Beowulf

- An experiment in parallel computing systems
- Established _vision of_ low cost, high end computing
- Demonstrated effectiveness of PC clusters for some (not all) classes of applications
- Provided networking software
- Conveyed findings to broad community (great PR)
- Tutorials and book
- Design standard to rally
-    community!
- Standards beget:
-    books, trained people,
-    software ... virtuous cycle

## Limits to Cluster Based Systems for HPC

**Memory Bandwidth**
**Commodity memory interfaces [SDRAM, RDRAM, DDRAM]**
**Separation of memory and CPU implementations limits performance**
**Communications fabric/CPU/Memory Integration**
**Current networks are attached via I/O devices**
**Limits bandwidth and latency and communication semantics**
**Node and system packaging density**
**Commodity components and cooling technologies limit densities**
**Blade based servers moving in right direction but are not High Performance**
**Ad Hoc Large-scale Systems Architecture**
**Little functionality for RAS**
**Lack of systems software for production environment**
**... ****but departmental and single applications clusters will be highly successful**

**After Rick Stevens, Argonne**

## Commercially Integrated Tflop/s Clusters

- Shell: largest engineering/scientific cluster
- NCSA: 1024 processor cluster (IA64)
- PNNL: announced 9.1 Tflops (peak) IA64 cluster from HP with Quadrics interconnect
- DTF in US: announced 4 clusters for a total of 13 Teraflops (peak)

**Notes:**

Collaborators/clients at this time:
 . SLAC
 . FETC
 . LBNL HENP
 . MSRI
 . ExtremeLinux society (national labs, universities, etc)
 . Millennium Project

The following slides all address performance aspects. However, our work will be just as much in ease-of-setup/admin, working with users, etc. 

## Comparison Between Architectures (2001)

**Source: Tammy Welcome, NERSC**

## Performance Comparison(2)Class C NPBs

**Source: Tammy Welcome, NERSC**

**Notes:**
Class C numbers – Mops/s/processor
Except for LU, Alvarez is about 1⁄2 speed of seaborg
Comparable to mcurie
We need to examine
	ability of memory subsystem to handle memory traffic on SMP
	effects of Linux SMP scheduling

## Effectiveness of Commodity PC Clusters

**Dollars/performance based on peak**
**SP and Alvarez are comparable $/TF**
**Get lower % of peak on Alvarez than SP**
**Based on SSP, 4.5% versus 7.2% for FP intensive applications**
**Based on sequential NPBs, 5-13.8% versus 6.3-21.6% for FP intensive applications**
**x86 known not to perform well on FP intensive applications**
**$/Performance and cost of ownership need to be examined much more closely**
**Above numbers do not take into account differences in system balance or configuration**
**SP was aggressively priced**
**Alvarez was vendor-integrated, not self-integrated**

**Source: Tammy Welcome, NERSC**

**Notes:**
Alvarez – early system
	not discounted
Seaborg
	discounted
	includes maintenance/people costs/etc

## Summary – Wrap-up

**Network structure and concepts**
** ****Switching, routing, flow control**
** ****Topology, bandwidth, latency, bisection bandwidth, diameter**
**Performance models**
** ****PRAM, ********, and LogP**
**Workstation/PC clusters**
** ****Programming environment, hardware**
** ****Challenges**
**Message passing implementation**

## Extra Slides

## Implementing Synchronous Message Passing

**Send operations complete after matching receive and source data has been sent.**
**Receive operations complete after data transfer is complete from matching send.**

**                                                                     ****source                                           destination**
**1) Initiate send                                     send (P****dest****, addr, length,tag) rcv(P****source****, addr,length,tag)**
**2) Address translation on P****dest**** **
**3) Send-Ready Request                                                              send-rdy-request**
**                                                                                                                           **
**4) Remote check for posted receive                                                                  tag match                                                     **
**5) Reply transaction**
**                                                                                                            ****receive-rdy-reply**
**6) Bulk data transfer**
**                                                      **
**                                                                                                ****data-xfer**

## Example: Permuting Data

** ****Exchanging data between Procs 0 and 1, V.1: What goes wrong?**

- Processor 0                                                    Processor 1
-      send(1, item0, 1, tag1)                                     send(0, item1, 1, tag2)
-      recv( 1, item1, 1, tag2)                                     recv( 0, item0, 1, tag1)

** ****Deadlock**
** ****Exchanging data between Proc 0 and 1, V.2:**

-  Processor 0                                                   Processor 1
-       send(1, item0, 1, tag1)                                  recv(0, item0, 1, tag1)
-       recv( 1, item1, 1, tag2)                                  send(0,item1, 1, tag2)

** ****What about a general permutation, where Proc j wants to send to**
**   ****Proc s(j), where s(1),s(2),...,s(P) is a  permutation of 1,2,...,P?**

## Implementing Asynchronous Message Passing

**Optimistic single-phase protocol assumes the destination can buffer data on demand.**

**                                                                     ****source                                           destination**
**1) Initiate send                                        send (P****dest****, addr, length,tag) **
**2) Address translation on P****dest**** **
**3) Send Data  Request                                                              data-xfer-request**
**                                                                                                                               ****tag match**
**                                                                                                                               ****allocate                                                      **
**4) Remote check for posted receive **
**5) Allocate buffer (if check failed)**
**6) Bulk data transfer                                                                              **
**                                                                                                                ****rcv(P****source****, addr, length,tag)**
**                                                                                                                                                      **

## Safe Asynchronous Message Passing

**Use 3-phase protocol**
**Buffer on sending side **
**Variations on send completion**
**wait until data copied from user to system buffer**
**don’t wait -- let the user beware of modifying data**

**                                                                     ****source                                           destination**
**Initiate send                                **
**Address translation on P****dest **
**Send-Ready Request                                                              send-rdy-request**
**                                                                                                                           **
**4) Remote check for posted receive         return and continue                         tag match                                                     **
**             ****record send-rdy                                     computing**
**5) Reply transaction**
**                                                                                                            ****receive-rdy-reply**
**6) Bulk data transfer**

## Example Revisited: Permuting Data

** ****Processor j sends item to Processor s(j), where**
**    ****s(1),...,s(P) is a permutation of 1,...,P**

- Processor j
-      send_asynch(s(j), item, 1, tag)
-      recv_block( ANY,  item, 1, tag)

** ****What could go wrong?**
** ****Need to understand semantics of send and receive.**
** ****Many flavors available.**

## Other operations besides send/receive

**“****Collective Communication” (more than 2 procs)**
**Broadcast data from one processor to all others.**
**Barrier.**
**Reductions (sum, product, max, min, boolean and, #, ...), where # is any “associative” operation.**
**Scatter/Gather.**
**Parallel prefix -- Proc j owns x(j) and computes y(j) = x(1) # x(2) # ... # x(j).**
**Can apply to all other processors, or a user-define subset.**
**Cost = O(log P) using a tree.**
**Status operations**
**Enquire about/Wait for asynchronous send/receives to complete.**
**How many processors are there?**
**What is my processor number?**

## Example: Sharks and Fish

**N fish on P procs, N/P fish per processor**
**At each time step, compute forces on fish and move them**
**Need to compute gravitational interaction**
**In usual n^2 algorithm, every fish depends on every other fish.**
**Every fish needs to “visit” every processor, even if it “lives” on just one.**
**What is the cost?**

## Two Algorithms for Gravity: What are their costs?

- Algorithm 1
-         Copy local Fish array of length N/P to Tmp array
-         for j = 1 to N
-               for k = 1 to N/P,   Compute force of Tmp(k) on Fish(k)
-               “Rotate” Tmp by 1
-                      for k=2 to N/P, Tmp(k) <= Tmp(k-1)
-                      recv(my_proc - 1,Tmp(1))
-                      send(my_proc+1,Tmp(N/P)
- Algorithm 2
-         Copy local Fish array of length N/P to Tmp array
-         for j = 1 to P
-               for k=1 to N/P, for m=1 to N/P, Compute force of Tmp(k) on Fish(m)
-               “Rotate” Tmp by N/P
-                     recv(my_proc - 1,Tmp(1:N/P))
-                     send(my_proc+1,Tmp(1:N/P))
- What could go wrong?  (be careful of overwriting Tmp)

## More Algorithms for Gravity

**Algorithm 3 (in sharks and fish code):**
**All processors send their Fish to Proc 0.**
**Proc 0 broadcasts all Fish to all processors.**
**Tree-algorithms:**
**Barnes-Hut, Greengard-Rokhlin, Anderson.**
**O(N log N) instead of O(N^2).**
**Parallelizable with cleverness.**
**“****Just” an approximation, but as accurate as you like (often only a few digits are needed, so why pay for more).**
**Same idea works for other problems where effects of distant objects becomes “smooth” or “compressible”: **
**electrostatics, vorticity, ...**
**radiosity in graphics.**
**anything satisfying Poisson equation or something like it.**