Deadlock Avoidance and Flow Control



next up previous
Next: Prototype Design Details Up: Architectural Overview Previous: Cache Coherence

Deadlock Avoidance and Flow Control

 

NUMAchine ensures that deadlock will not occur by dealing with messages that elicit responses from the target stations differently from those that do not elicit a response; we refer to the former as nonsinkable and the latter as sinkable. Sinkable messages include read responses, write-backs, multicasts, and invalidation commands, while nonsinkable messages include all types of read requests (including interventions). To avoid deadlock, certain functional modules in NUMAchine use separate queues to hold sinkable and nonsinkable messages.gif

The following rules govern the handling of sinkable and nonsinkable messages once they have entered the network:

For implementation purposes, an additional requirement is that the number of nonsinkable messages in the system is bounded. This is guaranteed because the number of nonsinkable messages that are issued from a station is limited by the local ring interface (up to 16 in our prototype). This bound implies that the size of some of the nonsinkable queues in NUMAchine grows as a linear function of the number of stations. Although this is not a scalable approach, it does not impose any practical limitations for the target system sizes. (An alternative scalable strategy is to negatively acknowledge nonsinkable messages when a queue becomes full, turning a nonsinkable message into a sinkable one.) For example, a queue size of 32KBytes per ring interface would be sufficient to handle the nonsinkable messages in a system with one thousand processors.

In addition to the deadlock avoidance scheme described above, NUMAchine has a simple flow control mechanism optimized for expected bandwidth requirements. Each ring interface has an input queue large enough to handle short term traffic bursts. Whenever the input queue is close to capacity, the operation of the ring that is feeding the buffer is temporarily halted; other rings are unaffected and continue to operate. Meanwhile, packets at the head of the full queue are processed until it is empty enough to start up the ring again. The flow control ensures that the order of sinkable requests is maintained, and it can be shown that this allows for important common case optimizations to the coherence protocol. However, it can result in poor performance under extreme conditions, such as when many processors simultaneously flush modified data from their caches to remote memory.



next up previous
Next: Prototype Design Details Up: Architectural Overview Previous: Cache Coherence



Stephen D. Brown
Wed Jun 28 18:34:27 EDT 1995