Interconnection Networks and Mapping and Scheduling Parallel Computations: DIMACS Workshop, February 7-9, 1994Derbiau Frank Hsu, Arnold L. Rosenberg, Dominique Sotteau American Mathematical Soc., 1995. gada 1. janv. - 342 lappuses This book contains the refereed proceedings of a DIMACS Workshop on Massively Parallel Computation. |
No grāmatas satura
6. lappuse
... assume that B ( n ) has a Hamiltonian path P2 that begins at ( 0 ; 00 ... 0 ) and ends at ( n - 1 ; 10 ... 0 ) ; in fact , finishing with the cross - edge forms a Hamiltonian cycle . Now consider B ( n + 1 ) , which we can view as a ...
... assume that B ( n ) has a Hamiltonian path P2 that begins at ( 0 ; 00 ... 0 ) and ends at ( n - 1 ; 10 ... 0 ) ; in fact , finishing with the cross - edge forms a Hamiltonian cycle . Now consider B ( n + 1 ) , which we can view as a ...
7. lappuse
... Assuming multiplication of an n - bit number by a log n - bit number can be computed in O ( n ) time , it follows that the time complexity for the ranking algorithm for Pn on the Butterfly is O ( n ) . The time complexity for the ...
... Assuming multiplication of an n - bit number by a log n - bit number can be computed in O ( n ) time , it follows that the time complexity for the ranking algorithm for Pn on the Butterfly is O ( n ) . The time complexity for the ...
20. lappuse
... assume that we have n processors , each with one optical tunable transmitter and one optical tunable receiver , the tuning time being p . Furthermore , let k be the life - span of an optical message ( number of receivers that can access ...
... assume that we have n processors , each with one optical tunable transmitter and one optical tunable receiver , the tuning time being p . Furthermore , let k be the life - span of an optical message ( number of receivers that can access ...
21. lappuse
... assume that transmitters and receivers are always tuned to the same wavelength . This strong assumption may be obtained by using one acousto- optic device per processor , used by both transmitter and receiver . Furthermore , we assume ...
... assume that transmitters and receivers are always tuned to the same wavelength . This strong assumption may be obtained by using one acousto- optic device per processor , used by both transmitter and receiver . Furthermore , we assume ...
24. lappuse
... Assume that k > 1. The processors are logically organized in one wide tree where the root , the initiator of the multiple broadcasting , has k ( k + 1 ) children , and each such child is the root of a balanced 24 24 P. BERTHOMÉ AND A ...
... Assume that k > 1. The processors are logically organized in one wide tree where the root , the initiator of the multiple broadcasting , has k ( k + 1 ) children , and each such child is the root of a balanced 24 24 P. BERTHOMÉ AND A ...
Saturs
9 | |
19 | |
Restricted routing and wide diameter of the cycle prefix network | 31 |
Permutation routing via Cayley graphs with an example for bus intercon | 47 |
Using helpful sets to improve graph bisections | 57 |
Modification of consecutived digraphs | 75 |
Highly adaptive wormhole routing algorithms for Ndimensional torus | 87 |
Conflictfree access to constantperimeter rectangular subarrays | 105 |
Communications in optically interconnected parallel computer systems | 181 |
Faulttolerant Kautz networks | 201 |
Asynchronous packet routers | 211 |
Cayley digraphs of finite cyclic groups with minimal average distance | 229 |
Shuffled tree based faulttolerant hierarchical interconnection networks | 251 |
Restricted connectivity and restricted fault diameter of some interconnec | 267 |
Sorting and selection on interconnection networks | 275 |
Towards a simple construction method for Hamiltonian decomposition | 297 |
Makespan minimization of task graphs with random task running times | 125 |
Scheduling of structured and unstructured computation | 139 |
The problem of contention | 173 |
Generalized reduced hypercube interconnection networks for massively par | 307 |
List of Participants | 327 |
Citi izdevumi - Skatīt visu
Interconnection Networks and Mapping and Scheduling Parallel Computations ... Derbiau Frank Hsu,Arnold L. Rosenberg,Dominique Sotteau Ierobežota priekšskatīšana - 1995 |
Bieži izmantoti vārdi un frāzes
2-D APW adaptive routing architecture binary bisection bits Bruijn graphs bus cycle Cayley graphs cluster communication conflict-free connected construction deadlock-free defined denoted Department of Computer destination deterministic diameter diff-value digraph distance Distributed Computing E-mail edges elements emulation fault-tolerant Figure follows Hamiltonian cycles Hamiltonian path heuristic hypercube hypergraph IEEE Trans implementation input integer interconnection networks Kautz Kautz graphs labeled labelled multigraph latin square Lemma loop lower bound mapping Mathematics Mathematics Subject Classification maximum memory modules Mesh node number of nodes number of processors optimal out-forest Parallel Algorithms parallel computers partitioning PE's performance permutation route PRAM problem Proc Proof PYRROS R₁ randomized randomized algorithm rectangular subarrays RH's routing algorithm routing function scheduling sequence skewing schemes sorting sparse matrix speedup steps subset task graph templates Theorem total number upper bound upper subfield vertex vertices virtual channels wavelength
Populāri fragmenti
290. lappuse - GE Blelloch, CE Leiserson, BM Maggs, CG Plaxton, SJ Smith, and M. Zagha. A comparison of sorting algorithms for the Connection Machine CM2.
324. lappuse - A survey of wormhole routing techniques in direct networks,
87. lappuse - The flit at the head of a message governs the route. As the header flit advances along the specified route, the remaining flits follow it in a pipeline fashion. If the header encounters a channel already in use, it is blocked until the channel is freed; the flow control within the network blocks...
88. lappuse - However, deadlocks may appear if the routing algorithms are not carefully designed. A deadlock in the interconnection network of a multicomputer occurs when no message can advance toward its destination because the queues of the message system are full. The size of the queues strongly influences the probability to reach a deadlocked configuration.
325. lappuse - Department of Electrical and Computer Engineering New Jersey Institute of Technology Newark. NJ 07102. USA GRAHAM C GOODWIN Department of Electrical and Computer Engineering University of Newcastle New South Wales.
200. lappuse - Department of Computer Science Hong Kong University of Science and Technology Clear Water Bay, Kowloon, Hong Kong Email: {zhangfan, chanson} @cs.ust.hk Abstract Multimedia applications over the Internet are becoming increasingly popular.
88. lappuse - These algorithms are based on a structured buffer pool. However, with wormhole routing, buffer allocation cannot be restricted, because flits have no routing information. Once the header of a message has been accepted by a channel, the remaining flits must be accepted before the flits of any other message can be accepted. So, routing must be restricted to avoid deadlock.
277. lappuse - Therefore, there are exactly n edges going out of (and coming into) any vertex. If a hypercube processor can handle only one edge at any time step, this version of the hypercube will be called the sequential model. Handling (or processing) an edge here means either sending or receiving a key along that edge. A hypercube model where each processor can process all its incoming and outgoing edges in a unit step is called the parallel model [9].
88. lappuse - Dally [9] has proposed a methodology to design static routing algorithms under general assumptions. He defines a channel dependency graph and establishes a total order among channels. Routing is restricted to visit channels in decreasing or increasing order to eliminate cycles in the channel dependency graph. This methodology has been applied to the design of routing chips for multicomputers [8] and multicomputer nodes with integrated communication support [2].
10. lappuse - The distance between two vertices u and v is the length of a shortest path between them. The diameter of H is the maximum of the distances over all pairs of vertices, and is denoted by D{H).