A Mathematical Framework for Structural Connectivity and Complexity Analysis of Processor Interconnection Networks
TL;DR
The framework provides a unified structural baseline that can be extended to larger processor configurations and failure-oriented studies and is demonstrated using five representative processor interconnection topologies: Hypercube, Torus, Fat-Tree, Dragonfly, and Perfect Difference Network.
Abstract
Processor interconnection networks provide the communication infrastructure for parallel computing, multiprocessor systems, many-core architectures, distributed computing, and high-performance computing. Their topology directly influences processor connectivity, communication distance, structural redundancy, fault tolerance, scalability, and implementation requirements. A systematic structural analysis is therefore essential for understanding interconnection-network characteristics before topology optimization or intelligent routing is applied. This paper presents a mathematical framework for the structural connectivity and complexity analysis of processor interconnection networks using graph-theoretic models. An interconnection network is represented as an undirected graph $G=(V,E)$, where vertices represent processors and edges represent communication links. The framework integrates multiple structural measures, including node degree, degree variance, link density, network diameter, average shortest-path length, clustering coefficient, betweenness and closeness centrality, path diversity, connectivity ratio, structural redundancy, and fault-tolerance retention. A normalized Structural Complexity Index (SCI) is formulated to jointly characterize communication distance and link requirements within a common comparative framework. The framework is demonstrated using five representative processor interconnection topologies: Hypercube, Torus, Fat-Tree, Dragonfly, and Perfect Difference Network (PDN). A 64-node configuration is used as the representative structural demonstration to examine differences in connectivity, communication distance, redundancy, and structural requirements across the selected topologies. The framework provides a unified structural baseline that can be extended to larger processor configurations and failure-oriented studies. Detailed stochastic failure experiments and probabilistic reliability estimation are beyond the scope of the present study.