Logic-Based Distributed Routing (LBDR)

Specifications

• LBDR is a sub-set of the control part of the router.

• Used for calculating the candidate output port(s) to forward the packet (flits).

• Packet (flits) might be chosen to be forwarded to one of the output ports that are connected to the neighbor routers or to the local port (connected to NI and the PE).

• LBDR does not pass the data through it, it only generates the request!

• Request(s) from LBDR goes (go) to allocator unit, which are then handled.

• LBDR only goes active on the header flit of a packet. For body flit, it keeps the previous values of the output signals (requests). For tail flit, it deactivates all the requests, in order to show that the packet has ended.

• LBDR uses 2 sets of configuration bits, (1) connectivity bits (4 bits per router) and (2) routing bits (8 bits per router). Connectivity bits describe the topology, while routing bits describe the set of allowed and prohibited turns (describing the routing algorithm).

• Connectivity bits are sent to LBDR in its generic part, when instantiated in the router module (Cx_rst). Routing bits are fed into the logic via Rxy_reconf input, which is controlled by the Reconfig input (Reconfiguration command).

• LBDR only needs the destination address of the packet, which is extracted from the header flit. It also uses the current address of the router. Based on these two addresses, it figures out on which quadrant or direction the destination is located. In the second phase, based on the values of Cx and Rxy bits, it generates the final Request outputs (ONLY for the header flit) (Req_N, Req_E, Req_W, Req_S, Req_L).

• LBDR is instantiated per each input port (similar to FIFO).

• U-turns are not allowed, therefore, for example, North LBDR cannot generated Req_N set as ‘1’.

• If a Dimension-Ordered Routing (DOR) algorithm such as XY is chosen (Rxy is set to 00111100), The output Requests of LBDR must always follow the one-hot fashion.

• Since LBDR uses minimal routing, more than two output Requests cannot go active at the same time.

• If the packet (flit) has reached its destination, then only Req_L can go high and all other requests must be zero. Similarly, if the packet has not reached its destination, Req_L cannot go high.

On reset (which is asynchronous to clock):

• Rxy_reconf from input of the module goes to the Rxy signal (routing bits get initialized)
• All Request outputs of LBDR (Req_FF) get initialized to zero.
• ReConf_FF_out gets initialized to zero.

Rxy can be fed via one of the following conditions:

• if ReConf_FF_out is set to one and the flit type is tail and the input FIFO is not empty and a grant has been given from the allocator unit from one of the output directions (basically if the last flit of the packet has left the router) : Rxy gets the value from Rx_reconf (input port of LBDR) and ReConf_FF_in becomes zero.
• if the case above does not hold, the Rxy gets its previous value and if the Reconfiguration command (Reconfig) from input is set to high, ReConf_FF_in becomes one. If Reconfig command is zero, Then ReConf_FF keeps its previous value.

At the rising edge of clock (The sequential part):

• Rxy_in goes to Rxy
• The values of output requests for LBDR get their corresponding values.
• ReConf_FF also gets its value updated.

The condition for checking whether all the requests should become zero, is checked by checking that the flit type is tail and FIFO is not empty and one grant is given from one of the outputs (via allocator unit) => This means the last flit of the packet has left the router => so all the LBDR outputs should go to zero.

Routing and Connectivity Bit Mapping

Connectivity Bits

The connectivity bits specify if there is a connection on the specific cardinal direction to the router (connectivity bit is '1') or not (connectivity bit is '0').

The mapping of the connectivity bits to the directions can be seen in the figure above. In case of the turn model shown in the figure.

Routing Bits

Routing bits are used to define the turn model (the routing algorithm). Normally all routers use the same routing configuration (although there exceptions, e.g. odd-even routing). A turn model consists of 8 turns, out of which some will be enabled and some will be disabled to form a turn model. A turn is defined as a case when a flit would change its cardinal direction while passing through the router (e.g. it enters the router from north and exits in west). Different turn models differ on the number and location of enabled and disabled turns. However, not all turn models are useful - if the turn model is not constrained enough, if will cause a deadlock. On the other hand, if the turn model is too much constrainted, it does not provide full connectivity. Also it should be noted that U-turns are always not allowed.

The list and comparison of all usable turn models can be seen here: http://turnmodel.pld.ttu.ee/index.php/2d-turn-models/

The mapping of the turns to the routing bits can be seen in the figure above. In case of the turn model shown in the figure, the resulting routing bit vector would look like the following:

Rxy = 00111100