Lecture 4 & 5: Parallel Processing and Network
September 14, 2004 Scribe: T.J.
Idea: Speed up processing using multiple processors.
Divide problem into tasks (sub-problems)
Each task is solved by one CPU.
(Terminology: PE = Processing Element = 1 CPU)
Our model: Each processor has its own memory.
Message passed between PEs through links.
Message: Contains data, destination ID, routing info, etc
(Sender must make) Request to send & Receiver must accept.
Interconnection Networks
To the nods, network can be a black box.
Ex) Bus Network
Write property: At any point in time, at most one message can be on the bus.
Read property: Everybody can read data from bus.
Need arbitration mechanism to decide who gets to transmit.
Notion:
duv: distance between nodes u and v (in terms of hops)
For bus network, duv = 1.
D: Diameter of network = Max duv (Max. distance between any two nodes)
For bus, D=1.
Saturating traffic: Everyone always has data to send.
Ideal traffic: Input-output pairs are arranged so as to maximize simultaneous messages.
Throughput: Data per unit time per PE (sender)
Throughput for bus net:
N = 64 PEs
W = bus width = 8 bytes
tx = time to send 8 bytes
ta = time between messages
M = message size = 256 bytes.
Crossbar Net
N x N structure 2N PEs
D = 2(N-1)
Properties:
Any node can reach any other node
Can route N messages at the same time
Throughput:
N = 64
W = 8 bytes
M = 256 bytes
tx=ta=1cycle
One message = N messages in parallel (best case)
Messages are divided into packets.
Packet movement is synchronized.
Packets will be blocked when multiple packets at a link.
Control of Packets
Store and forward;
Whole message must arrive at a (intermediate) node before a packet for that message is sent.
Wormhole;
All packets follow the same path.
A packet can leave a node when outgoing link is available.
First packet of a message has lower priority than non-first packets of other messages.
Purpose of above rule:
Provides contiguity within packets of a message.
Direct Networks
Each link is between two PEs
Represented as a graph.
G = (V,E) , |V|= n , |E| = m
Bisection width:
The smallest number of links one needs to cut to divide the network into two equal parts (N/2 nodes on iach side).
Examples of direct Networks:
Line graph
D = N 1, in general for N nodes.
Ring Network
Bisection width = 2
Multiple messages can travel at the same time.
Mesh
Nodes are labeled (i,j)
(i,j) connected to : (i-1, j) (i,j-1)
(i+1,j) (i,j+1)
N x N mesh has N2 edges
Bisection width = N for N2 PEs
K-dimensional Mesh:
N x N x x N = Nk nodes
Each node v = (x1, x2, , xk) has neighbors (x1-1, x2,..., xk), (x1+1, x2, ...,xk),(x1, x2-1,..., xk), (x1, x2+1,..., xk), (x1, x2 ,..., xk-1),(x1, x2 ,..., xk+1)
Max degree = 2K
Number of links = (NK x K)
D = (N-1)K : distance between (0,0,,0) and (N1,N2,,Nk)
K-ary cube
K-mesh with wrap around
Same as K-mesh with mod n.
e.g. in 2 dimensions, (x,y) is connected to (x-1 mod 2, y), (x+1 mod y), etc.