PREVENTING TREE SATURATION IN MULTISTAGE NETWORKS

In a large-scale multiprocessing system, contention for a particular m emory location (called hotspot), may create congestion in the intercon nection network. Usually a tree of saturated buffers rooted at the hot memory module and extending to the processors is formed which causes excessive delay for both hotspot and regular nonhotspot requests. To p revent tree saturation, a simple combining technique is proposed. The technique attempts to increase the chances of request combining. The n ew scheme called input queue combining uses simpler queueing structure compared to those proposed for conventional pairwise combining. The c omponent count in each queue reduces to one-third of that in pairwise combining and the number for the waitbuffer reduces to half. While con ventional pairwise combining is effective only for smaller networks, t he proposed technique eliminates tree saturation even in very large ne tworks, with reasonable delay. Networks delays reported here are among the lowest reported to date.