J.H. Park and M.S. Or (USA)
parallel prefix, reconfigurable computing, FPGAs, PRAM
This paper presents a design of a reconfigurable parallel prefix computation hardware on FPGAs. The design is based on a pipelined dataflow algorithm, and control logics are added to reconfigure the system for the arbitrary parallelism degree. The design receives multiple input streams of elements in parallel, and produces output streams in parallel. The design has the great advantage of controlling the degree of parallelism explicitly at run time. Time complexity of the design is O(d + (N-d) / d), where d and N are parallelism degree and stream size, respectively. When the stream size is very big, the initial trigger time d in the time complexity can be ignored and we get O(N/d). Unlike the software parallel prefix algorithms, the design works for both known and unknown sized data. The design is implemented and tested for target devices Xilinx Spartan2S XC2S300EFT256-6Q and XC2S600EFG676-6.
Important Links:
Go Back
