Reconfigurable hardware solution to parallel prefix computation |
| |
Authors: | Jin Hwan Park H K Dai |
| |
Affiliation: | (1) Department of Computer Science, State University of New York at New Paltz, New Paltz, NY 12561, USA;(2) Computer Science Department, Oklahoma State University, Stillwater, OK 74078, USA |
| |
Abstract: | This paper presents the design and implementation of an efficient reconfigurable parallel prefix computation hardware on field-programmable
gate arrays (FPGAs). The design is based on a pipelined dataflow algorithm, and control logic is added to reconfigure the
system for arbitrary parallelism degree. The system receives multiple input streams of elements in parallel and produces output
streams in parallel. It has an advantage of controlling the degree of parallelism explicitly at run time. The 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 sufficiently larger than the initial trigger
time of the pipeline (d), the time complexity becomes O(N/d). Unlike the prefix computation circuits found in the literature, the design is scalable for different problem sizes including
unknown sized data. The design is modular based on a finite state machine, and implemented and tested for target FPGA devices
Xilinx Spartan2S XC2S300EFT256-6Q and XC2S600EFG676-6.
|
| |
Keywords: | Parallel prefix computation Reconfigurable hardware Field-programmable gate arrays Dataflow Pipeline |
本文献已被 SpringerLink 等数据库收录! |
|