VLSI layouts of complete graphs and star graphs. (English) Zbl 1339.68216
Summary: In this paper, we present efficient layouts for complete graphs and star graphs. We show that an \(N\)-node complete graph can be optimally laid out using \(\lfloor N^2/4\rfloor\) tracks for a colinear layout, and can be laid out in \(N^4/16 +o(N^4)\) area for a 2D layout. We also show that an \(N\)-node star graph can be laid out in \(N^2/16 + o(N^2)\) area, which is smaller than any possible layout of a similar-size hypercube. This solves an open question posed by S. B. Akers and B. Krishnamurthy in [“A group theoretic model for symmetric interconnection networks”, in: Proceedings of the international conference on parallel processing, ICPP 86. St. Charles, IL. 216–223 (1986)]. Both the layouts of complete graphs and star graphs are optimal within a factor \(1 + o(1)\).
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Akers, S. B.; Krishnamurthy, B., A group theoretic model for symmetric interconnection networks, (Proc. Internat. Conf. Parallel Processing (1986)), 216-223 |
| [2] | Akers, S. B.; Harel, D.; Krishnamurthy, B., The star graph: an attractive alternative to the \(n\)-cube, (Proc. Internat. Conf. Parallel Processing (1987)), 393-400 |
| [3] | Akl, S. G.; Lyons, K. A., Parallel Computational Geometry (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ |
| [4] | Bagherzadeh, N.; Dowd, M.; Latifi, S., A well-behaved enumeration of star graphs, IEEE Trans. Parallel Distrib. Systems, 6, 5, 531-535 (1995) |
| [5] | Brebner, G., Relating routing graphs and two-dimensional grids, (VLSI: Algorithms and Architectures (1985)), 221-231 · Zbl 0564.94019 |
| [6] | Breznay, P. T.; Lopez, M. A., Tightly connected hierarchical interconnection networks for parallel processors, (Proc. Internat. Conf. Parallel Processing, Vol. I (1993)), 307-310 |
| [7] | Chen, C.; Agrawal, D. P., dBCube: a new class of hierarchical multiprocessor interconnection networks with area efficient layout, IEEE Trans. Parallel Distrib. Systems, 4, 12, 1332-1344 (1993) |
| [8] | Day, K.; Tripathi, A., A comparative study of topological properties of hypercubes and star graphs, IEEE Trans. Parallel Distrib. Systems, 5, 1, 31-38 (1994) |
| [9] | Vecchia, G. Della; Sanges, C., A recursively scalable network VLSI implementation, (Future Generations Comput. Systems (1988)), 235-243 |
| [10] | Duh, D.; Chen, G.; Fang, J., Algorithms and properties of a new two-level network with folded hypercubes as basic modules, IEEE Trans. Parallel Distrib. Systems, 6, 7, 714-723 (1995) |
| [11] | Fernández, A.; Efe, K., Efficient VLSI layouts for homogeneous product networks, IEEE Trans. Comput., 46, 10, 1070-1082 (1997) |
| [12] | Ghose, K.; Desai, R., Hierarchical cubic networks, IEEE Trans. Parallel Distrib. Systems, 6, 4, 427-435 (1995) |
| [13] | Harndi, M., A class of recursive interconnection networks: architectural characteristics and hardware cost, IEEE Trans. Circuits and Sys., I: Fundamental Theory and Applications, 41, 12, 805-816 (1994) · Zbl 0943.68500 |
| [14] | Hoelzeman, D. A.; Bettayeb, S., On the genus of star graphs, IEEE Trans. Comput., 43, 6, 755-759 (1994) · Zbl 1042.68636 |
| [15] | Hwang, K.; Ghosh, J., Hypernet: a communication efficient architecture for constructing massively parallel computers, IEEE Trans. Comput., 36, 12, 1450-1466 (1987) |
| [16] | Latifi, S.; Srimani, P. K., Transposition networks as a class of fault-tolerant robust networks, IEEE Trans. Parallel Distrib. Systems, 45, 2, 230-238 (1996) · Zbl 1048.68522 |
| [17] | Leighton, F. T., Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks (1983), MIT Press: MIT Press Cambridge, MA |
| [18] | Leighton, F. T., Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (1992), Morgan-Kaufman: Morgan-Kaufman San Mateo, CA · Zbl 0743.68007 |
| [19] | Leiserson, C. E., Fat-trees: universal networks for hardware-efficient supercomputing, IEEE Trans. Comput., C-34, 10, 892-901 (1985) |
| [20] | Mendia, V. E.; Sarkar, D., Optimal broadcasting on the star graph, IEEE Trans. Parallel Distrib. Systems, 3, 4, 389-396 (1992) |
| [21] | Saikia, D. K.; Sen, R. K., Two ranking schemes for efficient computation on the star interconnection networks, IEEE Trans. Parallel Distrib. Systems, 4, 321-327 (1996) |
| [22] | Vrt’o, Sýkora I., On VLSI layouts of the star graph and related networks, Integration, VLSI J., 83-93 (1994) · Zbl 0813.94026 |
| [23] | Thompson, C. D., Area-time complexity for VLSI, (Proc. ACM Symp. Theory of Computing (1979)), 81-88 |
| [24] | Tseng, Y.-C.; Sheu, J.-P., Toward optimal broadcast in a star graph using multiple spanning trees, IEEE Trans. Comput., 46, 5, 593-599 (1997) |
| [25] | Yeh, C.-H.; Parhami, B., Recursive hierarchical fully-connected networks: a class of low-degree small-diameter interconnection networks, (Proc. IEEE Internat. Conf. Algorithms and Architectures for Parallel Processing (June 1996)), 163-170 |
| [26] | Yeh, C.-H.; Parhami, B., Recursive hierarchical swapped networks: versatile interconnection architectures for highly parallel systems, (Proc. IEEE Symp. Parallel and Distributed Processing (October 1996)), 453-460 |
| [27] | Yeh, C.-H.; Parhami, B., Cyclic networks—a family of versatile fixed-degree interconnection architectures, (Proc. Internat. Parallel Processing Symp. (April 1997)), 739-743 |
| [28] | C.-H. Yeh, B. Parhami, Tight bounds on the VLSI areas and bisection width of star graphs and HCNs, submitted.; C.-H. Yeh, B. Parhami, Tight bounds on the VLSI areas and bisection width of star graphs and HCNs, submitted. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
