A cost-effective combining structure for large-scale shared-memory multiprocessors

A cost-effective combining structure to alleviate hot-spot contention is proposed. The key idea is that the combining function is separated from the routing function, so that a binary tree-based combining configuration becomes feasible. The combining element for realizing the new structure has only one wait buffer and one combining logic, involving less hardware than the element used in earlier combining networks. More importantly, the number of constituent combining elements in such a structure with size N is reduced to O(1/log₂ N) of that required in the previous design. The proposed combining structure in conjunction with a regular multistage interconnection network can remove hot-spot contention effectively in any sized system at a considerably lower cost, and appears readily suitable for use in some applications