Poboljšanje performansi mreža na čipu zasnovanih na deflekcionom rutiranju

Abstract

This doctoral dissertation comprises performance enhacement solutions for deflection-routed networks-on-chip. Presented solutions include the techniques for deflection minimization and techniques for misrouting supression. Two solutions presented: distributed and global port allocation (SMD and DMD). Both solutions reduce deflection rate by replacing existing algorithm of deflection router commutation stage with the novel algorithm that leads to better output ports allocation. While SMD minimizes deflection rate by choosing configuration that is beneficial for the flits at the single arbiter level, DMD introduces global port allocation in order to minimize the number of deflected flits at the output ports. Solutions for misrouting suppression presented in this doctoral dissertation are classified into solutions implemented on the inter-router link and solutions implemented in the router. There are presented two solutions that are implemented on the link: reflective link (LB) and reflective link with buffers (ILB). The essence of the LB solution is to include the option for returning the deflected flit back to the input of the router where it was deflected, which gives the flit a new opportunity for contending for productive port in the next network cycle. ILB solution additionally incorporates FIFO baffers on the links, that gives an additional flexibility compared to LB, and allows deflected flits to be kept in a buffer before returning back to the router where it was deflected. Also, ILB allows one of multiple link configurations in order to reduce misrouting. Both solutions are suitable for hardware implementation, and can be applied in any deflection network without modifying the internal router architecture. This doctoral dissertation also presents a solution for misrouting suppression in minimally-buffered deflection routers (SB_O). This solution includes modification of both the router architecture and the algorithm for SB buffer allocation. Router architecture is modified by moving the Buffer Inject stage to the front of PAS stage, in order to give higher injection priority to the flits originating from IP core, thus improving traffic distribution within the network. The SB_O also involves a novel algorithm for SB buffer allocation that selects for buffering a flit deflected on a port that is productive for flit already buffered in SB. Beside solutions for improving performance of deflection networks, doctoral dissertation presents a livelock detection and resolution mechanism. In difference to the existing livelock prevention schemes, the proposed mechanism can be easily adapted to different router architectures, and provides smaller latention of livelock detection compared to existing solutions. For the purpose of evaluating the proposed solutions, a dedicated cycleaccurate simulator of deflection networks has been developed and presented in doctoral dissertation. The simulator is implemented using language for digital systems modeling and verification – SystemC. The simulator allows functional modeling of deflection router, communication link, network topology, and network traffic. Beside simulations for performance comparing of presented solutions and reference routers, a separate set of simulations is performed in order to analyse influence of implemented performance enhancement mechanisms on distribution of network traffic.