Well-Suited Multiprocessor Topologies with Small Number of Processors

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 λ1 and m distinct eigenvalues. The products m∆ and (D+1)λ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.