Hierarchical communication in cube-connected multiprocessors

Interconnection structures that can provide access to multiple levels of a shared memory hierarchy in a multiprocessor are investigated. The results are also applicable to distributed memory architectures in which localities of communication can be statically defined. All the structures presented conform in some fashion to the binary cube topology with per-processor logic cost ranging from O (log N) to O(log²N). The results illustrate that without resorting to separate networks for access at each level, several architectures can provide fast access at lower levels in the hierarchy and progressively slower access at higher levels. Even at the highest communication level (corresponding to system wide communication), messages encounter less delay than in a nonhierarchical access situation