Avoiding Tree Saturation in the Face of ManyHotspots with Few BuffersBradley C. KuszmaulMIT CSAIL32 Vassar StreetCambridge, MA 02139email: bradley@mit.eduWilliam H. KuszmaulMIT PRIMES and Stanford Universityemail: william.kuszmaul@gmail.comAbstract—In a multistage network, hotspots induce tree sat-uration. The known solutions employ a variety of techniques,including combining (which works only for certain kinds ofmessages), feedback damping (which appears to provide lowutilization in the absence of hot spots), and large numbers ofbuffers. In practice, the approach used today is to provide largenumbers of buffers: in a P-processor system, the rule of thumbappears to be to provide 10P buffers, but 10P buffers may betoo expensive for systems containing 10 5 or more processors.Even employing ?(P) buffers does not appear to provide anyguarantees, however. We show that by organizing the switchesso that the messages addressed to a particular processor canuse only certain of the buffers, many hotspots can be toleratedwith few buffers. For example, a switch with O(logP) bufferscan tolerate a single hotspot with probability 1, and allows thefirst few hotspots to have a large number of buffers before beingdeclared a hotspot. A switch with B buffers can be organized sothat it blocks a particular non-hotspot message with probabilityless than O(1/s) if there are O(B/logs) hotspots, and canhandle a factor of O(B(loglogs)/logs) more hotspots beforethe probability becomes a constant. A similar approach can alsobe used to improve caching behavior in a multithreaded systemin which one of the threads tries to consume all of the cache.I. I NTRODUCTIONLarge-scale computing systems typically employ multistageinterconnection networks to interconnect their processors.These systems can suffer from hotspot contention, how-ever [1]. Hotspots arise when source processors collectivelysend too many messages to a particular destination processor—the destination processor falls behind trying to receive mes-sages, and the messages back up into the network filling upbuffers in the switches leading to the destination. Then theswitches leading to those switches fill up, and eventually thecongestion propagates backward through the network, forminga tree rooted at the hot destination of routing nodes withfull buffers. This saturation pattern is sometimes called treesaturation [1]. Hotspots require very little nonuniform trafficand onset can be very fast and can take a long time toalleviate [2]. Data center and supercomputer switches urgentlyneed effective congestion management to avoid performanceproblems [3].Tree saturation becomes a bigger problem as a systemgrows to encompass more and more processors. Tree saturationoriginally was understood as a problem even on networksThis work was supported in part by NSF grants CCF-0937860, CCF-1162148, CNS-1017058, CCF-1314547.containing as few as 100 processors [1], but a series oftechniques has mitigated tree saturation, at least on networkswith as many as thousands of processors.Several techniques have been proposed to solve hotspot con-tention. These techniques can be divided into four categories:combining, feedback, buffering, and counting.The combining solution involves organizing the system sothat switches find two messages that are destined for the sameprocessor, and combine them into one message. Although therules for combining messages have been worked out for certaincases (e.g., to implement shared memory [4]), many kindsof messages cannot combine. Even for combinable messages,one problem that shows up is that messages going to thesame address might not ever meet each other, even if thereis a hotspot. Ranade showed a theoretically effective way toimplement shared-memory on a butterfly [5], but combininghas yet to be implemented in any large-scale or commerciallyimportant systems.The feedback approach aims to stop messages destined toa hotspot at their sources (e.g., [6], [7]). Feedback schemesnotice that there is a hotspot, and provide information backto the sources to slow them down. This kind of negative-feedback control system seems to require difficult tuningto avoid oscillation, and even when successful, appears tounderutilize the network [8].The buffering approach involves adding more bufferingto the internal nodes of the routing network. It has beenlong known that organizing the switches as a collection ofFIFO’s on input ports gives poor performance, due to head-of-line blocking. By using buffers, which allow an unblockedmessage to pass a blocked message, good performance can beachieved, however (e.g., see [9]). Systems that avoid head-of-line blocking require only a few buffers per input port to getgood performance on random routing patterns.Today’s network architects appear to be doubling down onthe buffering approach. For example, Bechtolsheim [3], [10]indicates that for a network containing P processors, a switchshould contain enough buffering to hold 10P messages, butthat the implied memory requirements seem too large to bepractical.One reason the use of many buffers does not necessarilysolve the hotspot problem is that networks perform flow
