Transcript NUMAの構成 - Keio University

NORA/Clusters
AMANO, Hideharu
Textbook pp.１４０－１４７
NORA (No Remote Access
Memory Model)





No hardware shared memory
Data exchange is done by messages (or
packets)
Dedicated synchronization mechanism is
provided.
High peak performance
Message passing library （MPI,PVM) is
provided.
Message passing
（Blocking）
Send
Receive
Send
Receive
Message passing
（Non-blocking）
Send
Receive
Send
Receive
PVM (Parallel Virtual Machine)



A buffer is provided for a sender.
Both blocking/non-blocking receive is
provided.
Barrier synchronization
MPI
(Message Passing Interface)





Superset of the PVM for 1 to 1
communication.
Group communication
Various communication is supported.
Error check with communication tag.
Next week, a homework based on MPI with
cluster will be presented.
Shared memory model vs．
Message passing model

Benefits





Distributed OS is easy to implement.
Automatic parallelize compiler.
Message passing like Smalltalk requires
shared memory.
GHC → KL/I
Message passing



Formal verification is easy (Blocking)
No-side effect (Shared variable is side effect
itself)
Small cost
Multicomputers vs. Clusters



Multicomputers
 Dedicated hardware (CPU, network)
 High performance but expensive
 Hitachi’s SR8000, Cray T3E, etc.
WS/PC Clusters
 Using standard CPU boards
 High Performance/Cost
 Standard bus often forms a bottleneck
Beowluf Clusters
 Standard CPU boards, Standard components
 LAN+TCP/IP
 Free-software
 A cluster with Standard System Area Network(SAN) like
Myrinet is often called Beowulf Cluster
Beowluf Clusters
(RWCP, using Myrinet)
Networks for NORA machines/Clusters

Direct or Non-symmetric indirect networks



Nodes are connected with links.
Locality of communication can be used.
Extension to large size is easy.
Basic direct networks
Linear
Ring
Tree
つ
り
ｘ
Complete connection
Central concentration
Mesh
Metrics of Direct interconnection network
（D and ｄ）

Diameter：D


degree: d


Number of hops between most distant two nodes
through the minimal path
The largest number of links per a node.
D represents performance and ｄ represents
cost
Recent trends:
Performance: Throughput
Cost: The number of long links
Diameter
２（ｎ－１）
Other requirements





Uniformity：Every node/link has the same
configuration.
Extendability: The size can be easily
extended.
Fault Torelance: A single fault on link or
node does not cause a fatal damage on
the total network.
Embeddability: Emulating other networks
Bisection Bandwidth
bi-section bandwidth
The total amount of data
traffic between two halves of
the network.
Hypercube
0000
0100
1000
1100
0001
0101
1001
1101
0010
0110
1010
1110
0011
0111
1011
1111
Routing on hypercube
0101→1100
Different bits
0000
0100
1000
1100
0001
0101
1001
1101
0010
0110
1010
1110
0011
0111
1011
1111
The diameter of hypercube
0101→1010
All bits are different
→ the largest distance
0000
0100
1000
1100
0001
0101
1001
1101
0010
0110
1010
1110
0011
0111
1011
1111
Characteristics of hypercube





D=d=ｌｏｇＮ
High throughput, Bisection Bandwidth
Enbeddability for various networks
Satisfies all fundamental characteristics of
direct networks（Extendability is quistionable）
Most of the first generation of NORA
machines are hypercubes（iPSC，NCUBE，
FPS-T）
Problems of hypercube

Large number of links




Large number of distant links
High bandwidth links are difficult for a high
performance processors.
Small D does not contribute performance
because of innovation of packet transfer.
Programming is difficult: → Hypercube’s
dilemma
Is hypercube extendable?

Yes（Theoretical viewpoint）


The throughput increases relational to the system
size.
No（Practical viewpoint）

The system size is limited by the link of node.
Hypercube’s dilemma


Programming considering the topology is difficult
unlike 2-D,3-D mesh/torus
Programming for random communication network
cannot make the use of locality of communication.
•2-D/3-D mesh/torus
•Killer applications fit to the topology
•Partial differential equation, Image processing,…
•Simple mapping stratedies
•Frequent communicating processes should be
Assigned to neighboring nodes
ｋ-ａｒｙ ｎ-ｃｕｂｅ




Generalized mesh/torus
K-ary n digits number is assigned into each
node
For each dimension (digit), links are provided
to nodes whose number are the same except
the dimension in order.
Rap-around links (ｎ-1→０) form a torus,
otherwise mesh.
k-ary n-cube
００
０１
０２
3-ary 1-cube
１０
１１
１２
２０
２１
２２
3-ary 2-cube
k-ary n-cube
２ ００
０ ００
０１０
０ ２０
１ ００
１０１
００１
００ ２
１０
１１ ０
１ １１
０ １１
０１２
１２０
１２０
１２１
０ ２１
０ ２２
２０１
２０ ２
１０ ２
１１
２１２
3-ary 1-cube
１１２
２２１
２ ２２
3-ary 2-cube
１２２
3-ａｒｙ 3-ｃｕｂｅ
３-ary 4-cube
0***
1***
2***
k-ary n-cube
400
300
200
100
000
001
002
003
004
010
014
020
024
030
034
040
044
444
5-ary 4-cube
0***
1***
2***
4***
3***
Properties of k-ary n-cube




A class of networks which has Linear, Ring 2D/3-D mesh/torus and Hypercube（binary ncube） as its member.
1/n
Small d=2n but large D（O(k ))
Large number of neighboring links
k-ary n-cube has been a main stream of
NORA networks. Recently, small-n large-k
networks are trendy.
Exercise

Calculate Diameter (D) and degree (d) of the
６-ａｒｙ 4-cube (mesh-type).