Home |
Menu
Click here for result summary
Click here for the source code
ABSTRACT:
This paper studies the problems of permutation routing on different mesh models of parallel computation and simulates algorithms for different mesh models using C. Simple algorithms for permutation routing mesh models with and without bus have been considered, analyzed and simulated. In mesh models with bus, models with fixed bus and reconfigurable buses are dealt. For problems in permutation routing on meshes with bus, a technique has been considered that can be used to develop deterministic algorithms that are better than the simpler algorithms. This paper also analyzes one deterministic algorithm derived using the technique for permutation routing on two dimensional networks and implements this algorithm using C. For permutation routing with reconfigurable bus the computational aspects of reconfigurable mesh model has been analyzed and simulating the problem in a simulator called RMSIM. A hardware for the reconfiguration switch is also suggested and implemented in VHDL. The design of the switch is based on restricted configuration model that involves ten different possible configurations. VHDL test pattern analysis for the switch, simulation results for the above-mentioned models are also provided.
RESULTS :
The Permutation routing algorithms are successfully simulated using C in Mesh without buses and Mesh with row, column buses. The simulator RMSIM is used successfully to do Permutation routing in a reconfigurable mesh environment. The hardware switch implemented in VHDL obeys the test patterns. The results of the simulations and trial run samples are enclosed in appendix.
CONCLUSIONS AND FUTURE DIRECTIONS:
This paper ignored the problem of queue size in Reconfigurable meshes simulation. This simulation can be improved by considering queue size. Another possible improvement could be with respect to VHDL implementation. The implementation is done using bit vectors instead of buses. This can be improved by using actual buses. Another improvement is to optimize the instruction set for configurations. Since only ten configurations are implemented this can be done with 4 bits instead of 5 bits. The whole simulation could also be done for actual packet routing instead of limiting to Permutation routing. Only RMSIM simulation code needs to be changed because other simulations are already done keeping queue size and general packet routing in mind.