Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Parallel computation (3)
- Area-universal networks (2)
- Fat-trees (2)
- Interconnection networks (2)
- Randomized routing (2)
-
- Area-universality (1)
- Channel routing (1)
- Finite-state machines. (1)
- Hypercube (1)
- Layout algorithms (1)
- Message routing (1)
- Message routing algorithms (1)
- Mincut linear arrangement (1)
- Multilayer channel routing (1)
- Optimal linear arrangement (1)
- Routing algorithms (1)
- Routing networks (1)
- Single-layer routing (1)
- Supercomputers (1)
- Universality (1)
- VLSI (1)
- VLSI layout area (1)
- Wire density (1)
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Ronald Greenberg
Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Ronald Greenberg
Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …
On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan
On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan
Ronald Greenberg
This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a …
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Ronald Greenberg
This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …