Exercise Set 6:
Linked-List Queue Management

6.1 Pointer-Access Cost of Enqueue and Dequeue Operations

Consider the case where all pointers are stored in a single, 1-port, off-chip memory (first line of the table). More precisely, the width of this memory is either the width of one pointer (one segment address), or that width plus 1 bit; in the latter case, we can store one head or tail pointer plus one Empty Flag in one word of this available memory. (Note: an alternative scheme to storing both an empty flag and a pointer in a word is to only store the pointer while reserving one specific pointer value (e.g. "NULL") to denote an empty queue; for the purposes of this exercise, the two schemes are identical). This single memory contains all next-pointers (NxtPtr), all head pointers (Hd) of all queues, all tail pointers (Tl) of all queues, and all empty flags (in case such flags are used) of all queues. Each access to this single memory is performed to a single address (it is not possible to access in parallel the pointer in word A and the empty flag in another word B), and the access either reads the whole addressed word, or writes the whole addressed word (pointer plus flag, if a flag exists).

Count the number of accesses to this memory that are necessary in order to perform each of the following operations in the cases listed:

• enqN (Enqueue Normal): append a given new segment at the tail of a given queue qID. You don't know a priori whether the queue was empty or not, so you have to check for that, but assume that in this case the queue was not empty.
• enqE (Enqueue Exceptional): append a given new segment at the tail of a given queue qID. You don't know a priori whether the queue was empty or not, so you have to check for that, and assume that in this case the queue was empty.
• deqN (Dequeue Normal): remove the segment at the head of a given queue qID, and return the address of that segment. We know that the queue was not empty (the scheduler does not issue illegal or dummy operations), so you do not have to check for that. However, we do not know a priori whether the queue will become empty after we remove the head segment, so you have to check for that, but assume that in this case the queue does not become empty.
• deqE (Dequeue Exceptional): remove the segment at the head of a given queue qID, and return the address of that segment. We know that the queue was not empty so you do not have to check for that. However, we do not know a priori whether the queue will become empty after we remove the head segment, so you have to check for that, and assume that in this case the queue does become empty.

• Empty with Head: the queue-empty flag is stored in the same word where the queue head pointer is stored.
• Empty with Tail: the queue-empty flag is stored in the same word where the queue tail pointer is stored.
• Empty with Both: there are two identical copies of the empty flag for each queue; one of them is stored in the same word with the queue head pointer, and the other is stored in the same word with the queue tail pointer.

• Which of the 3 queue implementation schemes (empty with head, empty with tail, empty with both) yield(s) the highest worst-case operation rate? The worst case is the case where all operations on the queues are of the worst of the 4 possible combinations: enqN-deqN, enqN-deqE, enqE-deqN, enqE-deqE.
• Which of the 3 queue implementation schemes (empty with head, empty with tail, empty with both) yield(s) the highest average operation rate? Assume that 75% of the enqueues are normal and 25% are exceptional, and similarly 75% of the dequeues are normal and 25% are exceptional. (Note that exceptional cases are not that rare: higher-priority queues will usually be empty, and, when per-flow queueing is used, flows that are bottlenecked upstream of this link will have usually-empty queues).

6.2 Descriptor Memory Space needed for Multicast QoS Support

Consider a shared-buffer switch with 16 output ports. The buffer memory is made of 16 synchronous DRAM chips of size 2 M x 32 bits, each, like the MT46V2M32 DDR SDRAM chip example that we saw in section 3.2. The segment size is 128 bytes. What is the size of the buffer memory, in MBytes, and what is the number of segments in it? How wide (how many bits) is a segment pointer? How many reference counts and how wide each do we need?

(a) According to the first scheme --dedicated per-output and per-segment next-pointers-- how many nxtPtr's will the system need to store? What is the size, in Mbits, of the memory required to store these pointers plus the required reference counts? Assume that this memory is built out of 9 Mbit DDR static RAM chips like the MT57V256H36 chip example seen in section 3.2, of size 256 K x 36 bits each, that support burst-of-4 accesses only. Further assume that the width of this memory should be such that each access touches all nxtPtr's and the reference count associated with one segment (remember that each access yields a burst of 4 words from each chip). How wide (how many chips) does this memory need to be? Note that the memory width must be an integer number of chips, but this number does not need to be a power of two. How deep does the memory need to be? How many SRAM chips do we need in total?

(b) Now consider the second scheme --queue-member descriptors that are decoupled from segment addresses. We choose to have a number of descriptors that is twice the number of buffer memory segments. How many descriptors will we have? What is the width (number of bits) of a descriptor pointer? How large (number of bits) is a descriptor? What is the size, in Mbits, of the memory required to store these descriptors plus the required reference counts? Assuming that this memory is also built out of 9 Mbit SRAM chips, and that a "nice" packing of descriptors and reference counts into memory words can be found, what is the (minimum) required number of chips for this memory?

(c) Assuming that the average fan-out of multicast segments is 4, what is the maximum percentage of multicast segments in the buffer memory, so that we do not run out of descriptors before we run out of buffer space?

(Hint for optional thought on question (b), for those interested: a "nice" packing of descriptors and reference counts into memory words could be a placement such that the number of descriptors per burst is not a power of 2. In that case, to avoid the need for a divider in the addressing circuit, we could make descriptor pointers to be true burst-number and burst-offset pointers, and agree that not all integer numbers are valid descriptor pointers; as long as the free list of descriptors is correctly initialized to only contain the valid descriptors, no one else should ever care...)