Name
Abstract | ||
|---|---|---|
In VLSI layout of interconnection networks, routing two-point nets in some restricted area is one of the central operations. It aims usually to minimize the layout area, while reducing the number of wire bends is also very desirable. Here, we consider connecting sets of N inputs on a line and N outputs on a perpendicular line, inside a right triangle, where the output order is a given permutation of the order of corresponding inputs. Such triangles were used, for example, by Dinitz, Even and Artishchev-Zapolotsky for an optimal layout of the Butterfly network. However, that was some particular permutation, while here we solve an arbitrary permutation case. We show two layouts in the optimal area of 1/2N(2) + o(N-2), with O(N) bends each. The first one yields the minimal irreducible number of bends, while containing knock-knees. The second eliminates knock-knees, still keeping a constant number of bends per connection. |
Year | Venue | Keywords |
|---|---|---|
2005 | PDPTA '05: Proceedings of the 2005 International Conference on Parallel and Distributed Processing Techniques and Applications, Vols 1-3 | VLSI layout, butterfly, minimal area, triangle |
Field | DocType | Citations |
Permutation graph,Discrete mathematics,Right triangle,Computer science,Permutation,Parallel computing | Conference | 0 |
PageRank | References | Authors |
0.34 | 2 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Artishchev-Zapolotsky | 1 | 0 | 1.35 |
| shimon even | 2 | 2873 | 981.78 |
| vladimir yanovsky | 3 | 122 | 9.72 |