Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Centralized scheduling > Centralized scheduling - Pg. 48

48 CHAPTER 4 Interconnects and switching fabrics none, while there may be additional requests in RM that can be served. In order to improve performance, we need to identify such additional requests. The 2DRR achieves this in the following fashion: after examining ("applying") the selected diagonal as described earlier, if there are idle inputs and outputs, it "applies" the remaining diagonals, one at a time and within the same cycle, in order to identify additional requests to be served. The application sequence of the remaining diagonals is critical for fairness: if they are applied in a fixed sequence, for example, D 0 , . . ., D N À 1 , requests that lie in the cells of D 0 are preferred over ones that belong to the other diagonals D 1 . . . D N À 1 , the requests that lie in the cells of D 1 are preferred over the ones in D 2 . . . D N À 1 , and so on. This unfairness is alleviated by changing the order in which the diagonals are applied in every cycle. In 2DRR, this order is defined through a Pattern Sequence Matrix (PSM), which dictates the sequence in which the N diagonals must be applied in a sequence of N cycles. The PSM for a 4 Â 4 switch is shown in Figure 4-8(b). As the figure indicates, during the first cycle of operation the diagonals will be applied with the sequence specified in the first column of PSM; in the second cycle, they will be applied as specified in the second column; and so on. After four cycles, PSM is reused starting from the first column, etc. The PSM of Fig- ure 4-8(b) has two important properties that provide fairness among diagonals. These