Regular PapersNo Access

MULTIPROCESSOR INTERCONNECTION NETWORKS WITH SMALL TIGHTNESS

DRAGOŠ CVETKOVIĆ

Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Belgrade, Serbia

Search for more papers by this author

and

TATJANA DAVIDOVIĆ

Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Belgrade, Serbia

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S0129054109006978Cited by:7 (Source: Crossref)

Abstract

Homogeneous multiprocessor systems are usually modelled by undirected graphs. Vertices of these graphs represent the processors, while edges denote the connection links between adjacent processors. Let G be a graph with diameter D, maximum vertex degree Δ, the largest eigenvalue λ₁ and m distinct eigenvalues. The products mΔ and (D+1)λ₁ are called the tightness of G of the first and second type, respectively. In recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. In a previous paper we studied these and some other types of tightness and some related graph invariants and demonstrated their usefulness in the analysis of multiprocessor interconnection networks. We proved that the number of connected graphs with a bounded tightness is finite. In this paper we determine explicitly graphs with tightness values not exceeding 9. There are 69 such graphs and they contain up to 10 vertices. In addition we identify graphs with minimal tightness values when the number of vertices is n = 2,…, 10.

This work has been supported by Serbian Ministry of Science and Technological Development, grant No. 144015.

Keywords:

AMSC: 68M07, 68M10, 68M14, 05C75

References

U. Borštnik, M. Hodošček and D. Janežič, Croatica Chemica Acta 78(2), 211 (2005). Web of Science, Google Scholar
V. Brankovet al., Univ. Beograd, Publ. Elektrotehn. Fak. Ser. Mat. 17, 112 (2006). Google Scholar
G. T. Byrd and B. A. Delagi. Considerations for multiprocessor topologies. Technical report, STAN-CS-87-1144, Department of Computer Science, Stanford University, 1987 . Google Scholar
D. Cvetković and T. Davidović, YUJOR 18(2), 173 (2008). Crossref, Google Scholar
D. Cvetković and T. Davidović, Proc. SYM-OP-IS 2008, ed. D. Teodorović (Soko Banja, 2008) pp. 329–332. Google Scholar
D. M. Cvetković et al. , Recent results in the Theory of Graph Spectra ( North Holland , Amsterdam , 1988 ) . Google Scholar
D. M. Cvetković , M. Doob and H. Sachs , Spectra of Graphs: Theory and Applications , 3rd edn. ( Johann Ambrosius Barth Verlag , Heidelberg-Leipzig , 1995 ) . Google Scholar
D. M. Cvetković and M. Petrić, Discrete Math. 50, 37 (1984), DOI: 10.1016/0012-365X(84)90033-5. Crossref, Web of Science, Google Scholar
R. Elsässer, R. Královič and B. Monien, Theor. Comput. Sci. 307, 549 (2003), DOI: 10.1016/S0304-3975(03)00237-8. Crossref, Web of Science, Google Scholar
A. Ferreira and M. Morvan, Parallel Computing in Optimization (Kluwer Academic Publishers, Dordrecht/Boston/London, 1997) pp. 1–26. Google Scholar
A. Gupta and P. A. Dinda, Lecture Notes in Computer Science 3277, 125 (2005). Crossref, Google Scholar
F. T. Leighton , Introduction to Parallel Algorithms and Architectures, Arrays, trees, hypercubes ( Morgan Kaufmann , San Mateo , 1992 ) . Google Scholar
B. D. McKay. Nauty user's guide (version 2.2). Technical report, http://cs.anu.edu.au/ bdm/nauty, 2006 . Google Scholar
M. Miller and J. Širáň, Electron. J. Combin. DS14 (2005). Google Scholar
K. Qiu and S. K. Das, Int. J. Found. Comput. Sci. 14(3), 371 (2003), DOI: 10.1142/S0129054103001790. Link, Web of Science, Google Scholar
V. Sarkar , Partitioning and Scheduling Parallel Programs for Multiprocessors ( The M.I.T. Press , Cambridge, MA , 1989 ) . Google Scholar
M. Sevkli and M. E. Aydin, IMA Journal of Management Mathematics 18(2), 117 (2007), DOI: 10.1093/imaman/dpm009. Crossref, Web of Science, Google Scholar
G. C. Sih and E. A. Lee, IEEE Trans. Parallel and Distributed Systems 4(2), 175 (1993), DOI: 10.1109/71.207593. Crossref, Web of Science, Google Scholar
T. Sørevik, Parallel Computing in Optimization, eds. A. Migdalas, P. Pardalos and S. Storøy (Kluwer Academic Publishers, Dordrecht/Boston/London, 1997) pp. 57–72. Crossref, Google Scholar
E. van Dam. Graphs with few eigenvalues, An interplay between combinatorics and algebra. PhD thesis, Center for Economic Research, Tilburg University, 1996 . Google Scholar
E. R. van Dam and R. E. Kooij, Linear Alg. Appl. 423, 408 (2007). Crossref, Web of Science, Google Scholar
L. Wang, Z. P. Chen and X. H. Jiang, Ringed Petersen spheres connected hypercube interconnection networks, Proc. 10th IEEE Int. Conf. Eng. Complex Comput. Sys. (ICECCS'05) (IEEE Computer Society, 2005) pp. 127–131. Google Scholar