Logo

Login | Create Account

Nearly Optimal Three Dimensional Layout of Hypercube Networks

Calamoneri, Tiziana and Massini, Annalisa (2004) Nearly Optimal Three Dimensional Layout of Hypercube Networks. [Conference Paper]

Full text not available from this repository.

Abstract

In this paper we consider the three-dimensional layout of hypercube networks. Namely, we study the problem of laying hypercube networks out on the three-dimensional grid with the properties that all nodes are represented as rectangular slices and lie on two opposite sides of the bounding box of the layout volume. We present both a lower bound and a layout method providing an upper bound on the layout volume of the hypercube network.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
P Styles > P.999 Others
ID Code:532
Deposited By:Maciejak, Agnes
Deposited On:09 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=247

Repository Staff Only: item control page

References

1. T. Biedl, T. Thiele, D. R. Wood: Three-Dimensional Orthogonal Graph Drawing with Optimal Volume. Proc. Graph Drawing (GD'00), pp. 284-295, 2001.

2. T. Calamoneri, A. Massini: An Optimal Layout of Multigrid Networks. Information Processing Letters, 72, pp. 137-141, 1999.

3. T. Calamoneri, A. Massini: Optimal three-dimensional layout of interconnection networks. Theoretical Computer Science, 255, pp. 263-279, 2001.

4. A. DeHon: Compact, Multilayer Layout for Butterfly Fat-Tree. ACM Symp. on Parallel Algorithms and Architectures (SPPA), 2000.

5. P. Eades, A. Symvonis, S. Whitesides: Two Algorithms for Three Dimensional Orthogonal Graph Drawing. Proc. Graph Drawing '96 (GD'96), Lecture Notes in Computer Science 1190, Springer-Verlag, 1996, pp. 139-154.

6. R. I. Greenberg and L. Guan: On the area of hypercube layouts. Information Processing Letters, 84, pp. 41-46, 2002.

7. F. T. Leighton: Introduction to Parallel Algorithms and Architecture: Arrays, Trees and Hypercubes, Morgan Kaufmann Publ., San Mateo, CA, 1992.

8. K. Melhorn, F. P. Preparata and M. Sarrafzadeh: Channel routing in knock-knee mode: simplified algorithms and proofs. Algorithmica 1, 213-221, 1986.

9. S. Muthukrishnan, M. Paterson, S. C. Sahinalp and T. Suel: Compact Grid Layouts of Multi-Level Networks. 31st ACM Symp. on Theory of Computing, 1999.

10. R. Y. Pinter, On routing two-point nets across a channel, 19th ACM-IEEE Design Automation Conf. (1982) 894-902.

11. A. L. Rosenberg: Three-Dimensional VLSI: A Case-Study. Journal of the ACM, 30(3), 1983, pp. 397-416.

12. D. R. Wood: A New Algorithm and Open Problems in Three-Dimensional Orthogonal Graph Drawing. Proc. 10th Australasian Work. Combinatorial Algorithms (AWOCA), pp. 157-167, 1999.

13. T. Yamada and S. Ueno: On Three-Dimensional Layout of De Bruijn Networks. 2002 IEEE International Symposium on Circuits and Systems (ISCAS '02), Vol. III, pp. 779-782, 2002.

14. T. Yamada and S. Ueno: On Three-Dimensional Layout of Pyramid Networks. 2002 IEEE Asia Pacific Conference on Circuits and Systems (APCCAS '02), 2002.

15. C.-H. Yeh, B. Parhami, E. A. Varvarigos and H. Lee: VLSI Layout and Packaging of Butterfly Networks. ACM Symp. on Parallel Algorithms and Architectures (SPPA), pp. 196-205, 2000.

16. C.-H. Yeh, E. A. Varvarigos and B. Parhami: Multilayer VLSI Layout for Interconnection Networks. 2000 Int.l Conference on Parallel Processing (ICPP), pp. 33-40, 2002.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.