Well-suited multiprocessor topologies with small number of processors


Dragoš Cvetković, Tatjana Davidović




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 eigenvalue $\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 extended analysis to four types of tightness and found all graphs with tightness values at most eight.