Hierarchically interconnected multiprocessors

The design of interconnection networks is a central problem in parallel computing, especially for shared-memory systems, where network latency, or delay, is one factor that limits system size. This paper discusses aspects of one particular approach to network structure, a design comprising a multiplicity of subnetworks that form a hierarchy of paths. The hierarchy includes fast paths that are used in the absence of contention, and alternate paths with contention resolution. That is, just as in the case of a memory hierarchy, the fastest component of the hierarchy that can provide the desired function is utilized at a given time. The viability and robustness of hierarchical networks is studied first by examining circuit and implementation issues, and then by considering performance modeling and analysis. The overall performance of the hierarchy is shown to be close to that of a contention-free network of fast paths.