Logo

Login | Create Account

On Three-Dimensional Layout of Interconnection Networks (Extended Abstract)

Calamoneri, Tiziana and Massini, Annalisa (1998) On Three-Dimensional Layout of Interconnection Networks (Extended Abstract). [Conference Paper]

Full text not available from this repository.

Abstract

In this paper we deal with the layout of interconnection networks on three-dimensional grids. In particular, in the first part we prove a general formula for calculating an exact value for the lower bound on the volume. The we introduce the new notion of k-3D double channel routing and we use it to exhibit an optimal three-dimensional layout for butterfly networks. Finally, we show a method to lay out multigrid and X-tree networks in optimal volume.

Item Type:Conference Paper
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
ID Code:70
Deposited By:Martinez Leon, Victoria
Deposited On:26 Oct 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

1. AVIOR, A. - CALAMONERI, T. - EVEN, S. - LITMAN, A. - ROSENBERG, A.L.: A Tight Layout of the Butterfly Network. Proc. ACM SPAA '96, ACM Press Ed., 1996, pp 170-175.

2. BIEDL, T.: New Lower Bounds for Orthogonal Graph Drawings. Proc. GD '95, LNCS 1027, Springer-Verlag, 1995, pp 28-29.

3. CALAMONERI, T. - STERBINI, A.L.: Drawing 2-,3- and 4-colorable Graphs in O(n²) volume. Proc. GD '96, LNCS 1190, Springer Verlag, 1996, pp 53-62.

4. COHEN, R.F. - EADES, P. - LIN, T. - RUSKEY, F.: Three-dimensional graph drawing. Proc. GD '94, LNCS 894, Springer-Verlag, 1994, 1-11. Also in Algorithmica 17 (2), pp 199-208, 1997.

5. EADES, P. - FENG, Q.W.: Multilevel Visualization of Clustered Graphs. Proc. GD '96, LNCS 1190, Springer-Verlag, 1996, pp 101-112.

6. EADES, P. - SYMVONIS, A. - WHITESIDES, S.:Two Algorithms for Three Dimensional Orthogonal Graph Drawing. Proc. GD '96, LNCS 1190, Springer-Verlag, 1996, pp 139-154.

7. EVEN, S. - LITMAN, A.: Layered Cross Product - Technique to Construct Interconnection Networks. ACM SPAA '92, ACM Press Ed., 60-69, 1992.

8. LEIGHTON, F.T.: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-Exchange Graph an Other Networks. MIT Press, Cambridge, Mass, 1983.

9. MEHLORN, K. - PREPARATA, F.P. - SARRAFZADEH, M.: Channel routing in knock-knee mode: simplified algorithms and proofs. Algorithmica 1, 213-221, 1986.

10. PACH, J. - TÓTH, G.: Three-dimensional grid drawings of graphs, These Proceedings, 1997.

11. PINTER, R.Y.: O routing two-point nets across a channel. 19th ACM-IEEE Design Automation Conf., 894-902, 1982.

12. ROSENBERG, A.L.: Three-Dimensional VLSI: A case Study. Journal of the ACM, 30 (3), 1983, pp 397-416.

13. THOMPSON, C.D.: A complexity theory for VLSI. Ph.D. thesis, Carnegie-Mellon Univ. Pittsburgh, 1980.

14. WISE, D.S.: Compact layouts of banyan/FFT networks. VLSI Systems and Computations (H.T. Kung, B. Sproull, G. Steele, eds.) Computer Science Press, Rockville, Md., 1981, pp 186-195.

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.