A Performance Bound of Multistage Combining Networks

Concurrent requests by many processors to a shared variable on a shared memory machine can create contention that will be serious enough to stall large machines. “Combining,” in which several requests for the same variable can be combined into a single request, has been suggested as an effective method of alleviating this contention. “Multistage combining network” is a multistage interconnection network in which each switching node can perform combining. In this paper, a bound on the delays in multistage combining networks is developed by considering an idealized combining under “hot spot” traffic. Our result states that multistage combining networks are “stable” at least in theory under hot spot traffic. We also discuss some problems in achieving such stability in practice.