TAILIEUCHUNG - Parallel Programming: for Multicore and Cluster Systems- P5
Parallel Programming: for Multicore and Cluster Systems- P5: Innovations in hardware architecture, like hyper-threading or multicore processors, mean that parallel computing resources are available for inexpensive desktop computers. In only a few years, many standard software products will be based on concepts of parallel programming implemented on such hardware, and the range of applications will be much broader than that of scientific computing, up to now the main application area for parallel computing | 30 2 Parallel Computer Architecture is transferred. A sequence of nodes v0 . vk is called path of length k between v0 and vk if v v 1 e E for 0 i k. For parallel systems all interconnection networks fulfill the property that there is at least one path between any pair of nodes u v e V. Static networks can be characterized by specific properties of the connection graph including the following properties number of nodes diameter of the network degree of the nodes bisection bandwidth node and edge connectivity of the network and flexibility of embeddings into other networks as well as the embedding of other networks. In the following a precise definition of these properties is given. The diameter 8 G of a network G is defined as the maximum distance between any pair of nodes 8 G max min k k is the length of the path p from u to v . u veV p path from u to v The diameter of a network determines the length of the paths to be used for message transmission between any pair of nodes. The degree g G of a network G is the maximum degree of a node of the network where the degree of a node n is the number of direct neighbor nodes of n g G max g v g v degree of v e V . In the following we assume that A denotes the number of elements in a set A. The bisection bandwidth B G of a network G is defined as the minimum number of edges that must be removed to partition the network into two parts of equal size without any connection between the two parts. For an uneven total number of nodes the size of the parts may differ by 1. This leads to the following definition for B G B G min u v e E u e U1 v e U2 . U1 U2 partition of V U1 - U21 1 B G 1 messages can saturate a network G if these messages must be transferred at the same time over the corresponding edges. Thus bisection bandwidth is a measure for the capacity of a network when transmitting messages simultaneously. The node and edge connectivity of a network measure the number of nodes or edges that must fail to disconnect the .
đang nạp các trang xem trước