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

Calamoneri, Tiziana and Massini, Annalisa (1998) On Three-Dimensional Layout of Interconnection Networks (Extended Abstract). In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 64-75 (Official URL: http://dx.doi.org/10.1007/3-540-63938-1_51).

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
Additional Information:10.1007/3-540-63938-1_51
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
ID Code:70

Repository Staff Only: item control page

References

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.

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

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.

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.

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

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.

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

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

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

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

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

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

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

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.