CS-534: Packet Switch Architecture Spring 2011 Department of Computer Science © copyright: University of Crete, Greece

## Exercise Set 5: Linked-List Queue Management

Assigned: Wed. 15 Mar. 2011 (week 5) - Due: Wed. 23 Mar. 2011 (week 6)

 [Lecture: 3.3 Multiple Queue in a Buf.Mem.] [Print version, in PDF]

### 5.1   Pointer-Access Cost of Enqueue and Dequeue Operations

In section 3.3 slide 6, we saw the implementation of multiple queues using linked lists, so that they can share a given buffer memory space. The pointers are kept in separate memories, so that parallel accesses can be performed to the data and to the pointers. Oftentimes, the desired throughput corresponds to one operation per clock cycle --either one data segment (block) enqueue or one data segment dequeue per clock cycle. For each such operation, the required data memory throughput is one access (one address) per clock cycle --see exercises 3.1, 3.2. The throughput of the control (pointer) memories will often be adjusted to match the data memory throughput. When the required throughput exceeds one access (one address) per cycle, multi-ported memories will be needed for the corresponding pointers. The objective of this exercise is to determine the above throughput, i.e. count the number of required accesses per operation (enqueue or dequeue) to each pointer (control) memory. When counting, one has to be careful about what needs to be done in the "exceptional" cases, as outline below.

(a) Count the above numbers, for each of the pointer (control) memories (Empty, Head, Tail, NextPointer), in each of the following cases; the number of ports for each memory --in order to sustain the one-operation-per-cycle rate, is the worst of these numbers for that memory:

• 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.