ABSTRACT
Recent work in reconfigurable computing research has shown that a substantial performance speedup can be achieved through architectures that map the most relevant application inner-loops to a reconfigurable datapath. Any solution to this problem must be able to synthesize a datapath for each loop and to merge them together into a single reconfigurable datapath. The main contribution of this paper is a novel graph-based technique for the datapath merge problem. This approach is based on the solution of a maximum clique problem that merges datapaths one at a time. A set of experiments, using the MediaBench benchmark, shows that the proposed technique produces 24% fewer datapath interconnections than a previous solution to this problem.
- R. Battiti and M. Protasi. Reactive local search for the maximum clique problem. Algorithmica, 29(4), 2000.Google Scholar
- T. J. Callahan, J. R. Hauser, and J. Wawrzynek. The Garp architecture and C compiler. IEEE Computer, April 2000. Google ScholarDigital Library
- P. P. Chang, S. A. Mahlke, W. Y. Chen, N. J. Warter, and W. W. Hwu. IMPACT: An architectural framework for multiple-instruction-issue processors. In 18th International Symposium on Computer Architecture, 1991. Google ScholarDigital Library
- K. Compton and S. Hauck. Reconfigurable computing: A survey of systems and software. ACM Computing Surveys, 34(2), 2002. Google ScholarDigital Library
- C. Ebeling, D. C. Cronquist, and D. Franklin. RaPid -- Reconfigurable pipelined datapath. Lecture Notes in Computer Science 1142 --- Field Programmable Logic: Smart Applications, New Paradigms and Compilers, 1996. Google ScholarDigital Library
- S. C. Goldstein et al. PipeRench: A reconfigurable architecture and compiler. IEEE Computer, 33, 2000. Google ScholarDigital Library
- J. R. Hauser and J. Wawrzynek. Garp: A MIPS processor with a reconfigurable coprocessor. In IEEE Symposium on Field-Programmable Custom Computing Machines, 1997. Google ScholarDigital Library
- Z. Huang and S. Malik. Managing dynamic reconfiguration overhead in systems-on-a-chip design using reconfigurable datapaths and optimized interconnection networks. In Design, Automation and Test in Europe Conference, 2001. Google ScholarDigital Library
- Z. Huang and S. Malik. Exploiting operation level parallelism through dynamically reconfigurable datapaths. In 39th Design Automation Conference, 2002. Google ScholarDigital Library
- C. Lee, M. Potkonjak, and W. H. Mangione-Smith. MediaBench: A tool for evaluating and synthesizing multimedia and communication systems. In 30th Annual International Symposium on Microarchitecture, 1997. Google ScholarDigital Library
- A. Marshall et al. A reconfigurable arithmetic array for multimedia applications. In ACM/SIGDA International Symposium on FPGAs, 1999. Google ScholarDigital Library
- T. Miyamori and K. Olukotun. A quantitative analysis of reconfigurable coprocessors for multimedia applications. In IEEE Symposium on Field-Programmable Custom Computing Machines, 1998. Google ScholarDigital Library
- R. Razdan and M. D. Smith. A high-performance microarchitecture with hardware-programmable functional units. In 27th Annual International Symposium on Microarchitecture, 1994. Google ScholarDigital Library
- C. R. Rupp et al. The NAPA adaptive processing architecture. In IEEE Symposium on Field-Programmable Custom Computing Machines, 1998. Google ScholarDigital Library
- N. Shirazi, W. Luk, and P. Cheung. Automating production of run-time reconfigurable designs. In IEEE Symposium on Field-Programmable Custom Computing Machines, 1998. Google ScholarDigital Library
- C. C. Souza and A. M. Morais. Private communication. Applied Combinatorics Laboratory, IC-UNICAMP, March 2002.Google Scholar
- M. Weinhardt and W. Luk. Pipeline vectorization for reconfigurable systems. In IEEE Symposium on Field-Programmable Custom Computing Machines, 1999. Google ScholarDigital Library
- A. Ye et al. Chimaera: A high-performance architecture with a tightly-coupled reconfigurable functional unit. In 27th Annual International Symposium on Computer Architecture, 2000. Google ScholarDigital Library
Index Terms
- Datapath merging and interconnection sharing for reconfigurable architectures
Recommendations
Efficient datapath merging for partially reconfigurable architectures
Reconfigurable systems have been shown to achieve significant performance speedup through architectures that map the most time-consuming application kernel modules or inner loops to a reconfigurable datapath. As each portion of the application starts to ...
A New Datapath Merging Method for Reconfigurable System
ARC '09: Proceedings of the 5th International Workshop on Reconfigurable Computing: Architectures, Tools and ApplicationsReconfigurable systems have been proved to achieve significant performance speed-up by mapping the most time-consuming loops to a reconfigurable units. Datapath merging (DPM) synthesis has identified the similarities among the Data Flow Graphs (DFGs) ...
Efficient datapath merging for the overhead reduction of run-time reconfigurable systems
High latencies in FPGA reconfiguration are known as a major overhead in run-time reconfigurable systems. This overhead can be reduced by merging multiple data flow graphs representing different kernels of the original program into a single (merged) ...
Comments