TAILIEUCHUNG - Parallel Programming: for Multicore and Cluster Systems- P7
Parallel Programming: for Multicore and Cluster Systems- P7: 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 | 50 2 Parallel Computer Architecture 2D mesh with 3 x 3 nodes Fig. 3 x 3 mesh and corresponding channel dependence graph for XY routing This is a contradiction and thus no deadlock can occur. Each routing path selected by XY routing consists of a sequence of links with increasing numbers. Each edge in the channel dependence graph points to a link with a larger number than the source link. Thus there can be no cycles in the channel dependence graph. A similar approach can be used to show deadlock freedom for E-cube routing see 38 . Source-Based Routing Source-based routing is a deterministic routing algorithm for which the source node determines the entire path for message transmission. For each node ni on the path the output link number ai is determined and the sequence of output link numbers a0 . an-1 to be used is added as header to the message. When the message passes a node the first link number is stripped from the front of the header and the message is forwarded through the specified link to the next node. Table-Driven Routing For table-driven routing each node contains a routing table which contains for each destination node the output link to be used for the transmission. When a message arrives at a node a lookup in the routing table is used to determine how the message is forwarded to the next node. Turn Model Routing The turn model 68 125 tries to avoid deadlocks by a suitable selection of turns that are allowed for the routing. Deadlocks occur if the paths for message transmission contain turns that may lead to cyclic waiting in some situations. Deadlocks can Routing and Switching 51 Fig. Illustration of turns for a two-dimensional mesh with all possible turns top allowed turns for XY routing middle and allowed turns for west-first routing bottom turns not allowed be avoided by prohibiting some of the turns. An example is the XY routing on a two-dimensional mesh. From the eight possible turns see Fig. top only .
đang nạp các trang xem trước