FPGA Based Parallel Transitive Closure Algorithm
In this paper, the authors propose a FPGA-based parallel algorithm to compute the transitive closure of the relation matrix on a fixed-size PE array. Experimental results showed that speedup increases with the problem size. The speedup against a single PE is between 11.3 and 195.9. Compared to a general CPU solution, this algorithm achieves acceleration rate of 3.7 and 376 under the worst and best situations, respectively. The FPGA is supposed to fill the gap between Application Specific Integrated Circuit (ASIC) hardware and general software problem solution. Scientists have been aiming at much higher performance gained through FPGAs in computational intensive applications.