As the level of chip-integration continues to advance at a fast pace, the desire for efficient interconnects - whether on-chip or off-chip - is rapidly increasing. Traditional interconnects like buses, point-to-point wires, and regular topologies may suffer from poor resource sharing in the time and space domains, leading to high contention or low resource utilization. In this paper, we propose a design methodology for constructing networks for special-purpose computer systems with well-behaved (known) communication characteristics. A temporal and spatial model is proposed to define the sufficient condition for contention-free communication. Based upon this model, a design methodology using a recursive bisection technique is applied to systematically partition a parallel system such that the required number of links and switches is minimized while achieving low contention. Results show that the design methodology can generate more optimized on-chip networks with up to 60 percent fewer resources than meshes or tori while providing blocking performance closer to that of a fully connected crossbar.

As the level of chip integration continues to advance at a fast pace, the desire for efficient interconnects - whether on-chip or off-chip - is rapidly increasing. Traditional interconnects like buses, point-to-point wires and regular topologies may suffer from poor resource sharing in the time and space domains, leading to high contention or low resource utilization. In this paper, we propose a design methodology for constructing networks for special-purpose computer systems with well-behaved (known) communication characteristics. A temporal and spatial model is proposed to define the sufficient condition for contention-free communication. Based upon this model, a design methodology using a recursive bisection technique is applied to systematically partition a parallel system such that the required number of links and switches is minimized while achieving low contention. Results show that the design methodology can generate more optimized on-chip networks with up to 60% fewer resources than meshes or tori while providing blocking performance closer to that of a fully connected crossbar.

Support for arbitrary topologies has become more popular for system-area networks but very little has been done in trying to characterize their behavior and performance. Traditional parameters like diameter and bisection width are not sufficient for characterizing the irregularities that abound in such networks and fail to give much insight into throughput performance. A clustering approach for partitioning a network into clusters of richly-connected regions is proposed as a means of defining two performance-correlated characterization metrics: intercluster bandwidth index and intercluster link-cost index. The two characterization metrics are shown to have a strong correlation to saturation throughput when link and load distribution of a network is imbalanced. Simulation results also show that the clustering algorithm can be applied to a variety of network configurations and traffic scenarios, particularly irregular ones. With the proposed characterization metrics that correlate more strongly with performance, it is possible to classify networks into categories having similar performance.

Networks of workstations (NOW) have gained importance in recent years. The interconnection network of NOW systems often consist of generic switches connected in an irregular topology. Traditionally, interconnection networks are characterized by their topological properties, such as number of nodes, diameter, and bisection width. These parameters are not sufficient in characterizing irregular networks. This research puts forth a new approach that characterizes both regular and irregular networks. A partitioning algorithm is proposed to break down a network topology into groups or clusters of nodes such that there is higher bandwidth within clusters than between clusters. By doing so, the potential bottlenecks of a network are identified. Furthermore, a characterization scheme based on measurement of these clusters is defined. The new scheme uses two parameters, the intercluster bandwidth index and intercluster link cost index to describe a network topology. Simulation results show that these two indices have stronger correlation to performance than traditional topological properties.