Parallel Routing Algorithm for Extra Level Omega Networks on Reconfigurable Systems

Several parallel routing algorithms have been proposed during the last three decades. However, most algorithms have been not implemented. Therefore, the execution time and memory resources have been neither measured nor reported. This work presents two parallel routing algorithms for Omega multistage networks by using hardware assistant approach. Both algorithms have been mapped on a FPGA. The first algorithm minimizes the execution time and it is based on a priority encoder. The second one optimizes the hardware resources by using embedded FPGA memories. Omega networks are blocking and some permutations are not completely routed. Extra levels increase the routing capability by doubling the number of paths. This work evaluates the route capacity as a function of network workload, parallel networks and extra levels. Network switches with 2 and 4 inputs/outputs have been taken into account. For each connection, the first algorithm spends only two clock cycles by using the priority encoder. For the second algorithm based on memories, the number of cycles per connection ranges from 2 to 10 and the average number of cycles is around 5.