chapter19 Allocation

Chapter19 Allocation of
Principles and Practices of Interconnection Networks by William James Dally, Brian Patrick Towles

When the arbiter allocates a single resource to one of a group of requestors , The allocator performs a match between a set of resources and a set of requestors , And for each requester , It may request one or more resources at the same time . for example , Consider a set of router Input unit for , Each input unit has some flit, these flit The destinations are switch Different output ports of . We're already in the third quarter 17.2.2 The distributor is described in section , There we discussed their use for distribution crossbar switch. In each clock cycle , The allocator must match between the input unit and the output port , To select at most one... From each input port flit, At most one output port can be selected flit.
19.1 Representations
For one n × m distributor , Its acceptance n individual m-bit Vector as input , And generate n individual m-bit Vector as output unit , Pictured 19.1 It shows a 4x3 (n = 4 , m = 3) distributor . If you request input rij Be placed 1 ( It is often called By asserted), Indicates that the requestor i Want to access resources j . Each requester can simultaneously request any subset of the resource . about router Distributor used in the design , The requestor usually corresponds to switch Input , Resources correspond to switch Output . therefore , We usually refer to requesters and resources as inputs and outputs, respectively .
The allocator responds to the request , Generate authorization vectors according to three rules ：

1. There has to be request request
2. For each of these input (requester), There can only be one at most per shot request By grant
3. For each of these output (resource), There can only be one at most per shot request By grant
   
   chart 19.1 n × m distributor , Accept n individual m-bit Request vector , And generate n individual m-bit Grant vector .(a) The symbol of the allocator , It shows the individual requests and grant The signal .(b) A simplified representation of the signal of the distributor .

The allocator can be thought of as accepting a n × m Request matrix R, Then an authorization matrix is generated G, among ,R Contains all single requests rij, Is an arbitrary binary valued matrix .G Include all authorizations gij, It is also a binary matrix [ notes 1]; also G Contains only and R Non zero entries in the are consistent 1（ The rules 1）, At most one per line 1（ The rules 2）, also At most one per column （ The rules 3）.
For the following request matrix R, There are two possibilities grant matrix G1 and G2.

G1 and G2 All are request matrices R Effective authorization matrix for , Because they all conform to the three rules listed above . However ,G2 It is usually a more ideal authorization matrix , Because it assigns all three resources to the input ( You can see G2 Three of them 1) [ notes 2]. image G2 This contains the allocation method for the maximum number of matches , be called maximum matching, This is called the maximum match . and G1, Additional requests cannot be processed without removing one of the existing authorizations , be called maximal matching.
From matrix G1 You can see the difficulty of a good match ： Once... Is set in the first row of the matrix grant g00, It is no longer possible to make a maximum match . Because of the input 2 Just request resources 0, So this resource (output 0) Assigning to any other input will result in input 2 Free . Put resources 1 Assign to input 0 It will also prevent maximum matching , Because of resources 0 Cannot be assigned to input at the same time 1 and 2. For things like R Such a difficult request matrix , An incorrect allocation may result in a suboptimal match .
The assignment problem can also be expressed as a bipartite graph (bipartite graph) [ notes 3]. for example , chart 19.2(a) The request matrix is given R The bipartite graph of . In this form , The assignment problem can be transformed into a bipartite matching problem ： Find the edges (graph edges) The largest subset of , Associate each vertex to at most one edge in the subset . chart 19.2(b) Shows the authorization matrix G2 Bipartite graph matching .

chart 19.2 Bipartite graph representation of assignment problem .(a) Request matrix r Corresponding bipartite graph (b) Authorization matrix G2 The corresponding bipartite graph matches .

For one there is P Ports of switch, The time complexity of calculating the maximum matching is O(P2.5) [83]. Generally speaking , Calculating the maximum match requires backtracking —— Because authorization may be added temporarily , But it will be deleted later . Unfortunately ,switch The allocator or virtual channel allocator cannot afford the complexity of this precise solution , And the backtracking action that must be done makes it difficult for the algorithm to obtain the maximum match to be pipelined . Because in the actual hardware , Usually only one or a few cycles are available to perform the allocation , therefore maximal-size matches Become a more realistic goal . However , As we will see ,maximal matches It can also be very expensive , So in practice , Hardware allocators often introduce simpler heuristics (heuristics) To provide a fast but approximate solution .

notes ：

1. In some applications ,R It can be an integer value , That is, multiple requests can be made for the same output . However , We do not consider these applications here .
2. actually , For non-uniform flow (non-uniform traffic ) For the test scenario ,maximum-size Not always the best [124].
3. In bipartite graphs , Vertices can be divided into two sets A and B, All the edges are connected A A vertex in and B A culmination in .