Geodesic
Multiprocesor Interconnection Networks
Zbornik radova, Tome 13 (2009) no. 21, p. 33 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 $\Delta$, the largest eigen value $\lambda_1$ and $m$ distinct eigenvalues. The products $m\Delta$ and $(D+1)\lambda_1$ are called the tightness of $G$ of the first and second type, respectively. In the recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. We study these and some other types of tightness and some related graph invariants and demonstrate their usefulness in the analysis of multiprocessor interconnection networks. A survey of frequently used interconnection networks is given. Load balancing problem is presented. We prove that the number of connected graphs with a bounded tightness is finite and 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$.
Classification : 05C50 68M07 68M10 68M14
Keywords: Multiprocessor Systems, Interconnection Topologies, Load Balancing, Spectra of Graphs, Graph Invariants. 
@article{ZR_2009_13_21_a2,
     author = {Drago\v{s} Cvetkovi\'c and Tatjana Davidovi\'c},
     title = {Multiprocesor {Interconnection} {Networks}},
     journal = {Zbornik radova},
     pages = {33 },
     publisher = {mathdoc},
     volume = {13},
     number = {21},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZR_2009_13_21_a2/}
}
TY  - JOUR
AU  - Dragoš Cvetković
AU  - Tatjana Davidović
TI  - Multiprocesor Interconnection Networks
JO  - Zbornik radova
PY  - 2009
SP  - 33 
VL  - 13
IS  - 21
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZR_2009_13_21_a2/
LA  - en
ID  - ZR_2009_13_21_a2
ER  - 
%0 Journal Article
%A Dragoš Cvetković
%A Tatjana Davidović
%T Multiprocesor Interconnection Networks
%J Zbornik radova
%D 2009
%P 33 
%V 13
%N 21
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZR_2009_13_21_a2/
%G en
%F ZR_2009_13_21_a2
Dragoš Cvetković; Tatjana Davidović. Multiprocesor Interconnection Networks. Zbornik radova, Tome 13 (2009) no. 21, p. 33 . http://geodesic.mathdoc.fr/item/ZR_2009_13_21_a2/