On the effectiveness of combining in resolving ′Hot-Spot′ contention

Sharing the memory in a parallel computer suggests that there is a possibility of many processors requesting a shared variable at virtually the same time. This idea has been formalized in the “hot spot” traffic model, where a fixed fraction of memory requests is for a single shared variable. Under the model, it has been shown that such concurrent requests to shared variable can create contention serious enough to stall large machines. As an effective method of alleviating this type of contention, “combining,” in which several requests for the same variable can be combined into a single request, has been suggested. The NYU Ultracomputer and the IBM RP3 machine use “pairwise” combining, in which only two requests for the same variable can be combined at a switch of the processor-memory intereconnection. We study the effectiveness of combining. In particular, it turns out that pairwise combining is slightly too restrictive to handle hot spots if the machine size becomes very large. We suggest ways to overcome this weakness.