Baseline Virtual-Channel Based Switching Modules and Routers - Microarchitecture of Network-on-Chip Routers - page 127

Wavefront Allocation

0123

0123

0
1
2
3

0
1
2
3

Final
Grants

Input
Requests
0123

0123

0
1
2
3

0
1
2
3

Step 1 Step 2

0123 0123

0
1
2
3

0
1
2
3

Step 3 Step 4

Fig. 7.17 An example of the operation of a centralized allocator. All requests are examined
starting from the main diagonal of the request matrix. The active requests of a diagonal do not
cause any conflicts and they can be granted at once. A grant given to a certain request-resource
pair directly erases all the remaining requests of the same row and column

without any further checking are the requests that belong to the diagonals of the
matrix. Every element that belongs to a matrix diagonal corresponds to a different
request-resource pair and can be granted without causing any conflict. Once a
request of the i th row and j th column is granted then all the requests of the i th
row and the j th column should be nullified before moving to the next diagonal of
the matrix. An example, of this diagonal-based scheduling mechanism is shown
in Fig. 7.17 . The allocation process evolves in 4 steps (equal to the number of
diagonals) and at each step the non-conflicting requests are granted. The most
efficient centralized allocator is the wavefront arbiter (Tamir and Chi 1993 ;Hurt
et al. 1999 ; Becker 2012b ).
Using a centralized allocator, such as the wavefront arbiter, we can design VC
and switch allocators. A VC allocator is built around a NV NV centralized
allocator that receives the requests of all input VCs in parallel. Figure 7.18 illustrates
this organization. The rows of the centralized allocator correspond to input VCs
and the columns to output VCs, respectively. Each input VC may request many
output VCs of the same output, i.e., it asserts a request to multiple columns of the
centralized allocator. When allocation finishes the N V grant signals coming from
all output VCs are gathered per-input VC, while the OR function at each input VC
just detects if at least one output VC granted the corresponding input VC.
Equivalently, a switch allocator can be built using a N N centralized allocator,
as illustrated in Fig. 7.19 . The rows of the centralized allocator correspond to the
inputs of the routers and the columns to the outputs. Since each input hosts many
VCs, a row of the request matrix can have many active requests that correspond to
the output requests of the input VCs. When the centralized allocator finishes, each