Automatic compilation to a coarse-grained reconfigurable system-opn-chip

ABSTRACT

The rapid growth of device densities on silicon has made it feasible to deploy reconfigurable hardware as a highly parallel computing platform. However, one of the obstacles to the wider acceptance of this technology is its programmability. The application needs to be programmed in hardware description languages or an assembly equivalent, whereas most application programmers are used to the algorithmic programming paradigm. SA-C has been proposed as an expression-oriented language designed to implicitly express data parallel operations. The Morphosys project proposes an SoC architecture consisting of reconfigurable hardware that supports a data-parallel, SIMD computational model. This paper describes a compiler framework to analyze SA-C programs, perform optimizations, and automatically map the application onto the Morphosys architecture. The mapping process is static and it involves operation scheduling, processor allocation and binding, and register allocation in the context of the Morphosys architecture. The compiler also handles issues concerning data streaming and caching in order to minimize data transfer overhead. We have compiled some important image-processing kernels, and the generated schedules reflect an average speedup in execution times of up to 6× compared to the execution on 800 MHz Pentium III machines.

REFERENCES

• 1: Kiran Bondalapati , Viktor K. Prasanna, Loop Pipelining and Optimization for Run Time Reconfiguration, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.906-915, May 01-05, 2000
• 2: Jack W. Crenshaw, Math toolkit for real-time programming, CMP Publications, Inc., Manhasset, NY, 2000
• 3: Carl Ebeling , Darren C. Cronquist , Paul Franklin, RaPiD - Reconfigurable Pipelined Datapath, Proceedings of the 6th International Workshop on Field-Programmable Logic, Smart Applications, New Paradigms and Compilers, p.126-135, September 23-25, 1996
• 4: Filho, E. M. C. 1998. The TinyRISC instruction set architecture. www.eng.uci.edu/morphosys/ docs/isa.pdf.
• 5: Jan Frigo , Maya Gokhale , Dominique Lavenier, Evaluation of the streams-C C-to-FPGA compiler: an applications perspective, Proceedings of the 2001 ACM/SIGDA ninth international symposium on Field programmable gate arrays, p.134-140, February 2001, Monterey, California, United States [doi>10.1145/360276.360326]
• 6: Seth Copen Goldstein , Herman Schmit , Mihai Budiu , Srihari Cadambi , Matt Moe , R. Reed Taylor, PipeRench: A Reconfigurable Architecture and Compiler, Computer, v.33 n.4, p.70-77, April 2000 [doi>10.1109/2.839324 ]
• 7: Hall, M., Diniz, P., Bondalapati, K., Ziegler, H., Duncan, P., Jain, R., and Granacki, J. 1999. DEFACTO: A design environment for adaptive computing technology. In 6th Reconfigurable Architectures Workshop (RAW'99).
• 8: Hammes, J. P. and Böhm, A. P. W. 2001. The SA-C language. www.cs.colostate.edu/cameron Colorado State University.
• 9: Hammes, J. P., Rinker, R. E., McClure, D. M., Böhm, A. P. W., and Najjar, W. A. 2001. The SA-C compiler dataflow description. www.cs.colostate.edu/cameron Colorado State University.
• 10: Jeff Hammes , Bob Rinker , Wim Bohm , Walid Najjar , Bruce Draper , Ross Beveridge, Cameron: High Level Language Compilation for Reconfigurable Systems, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.236, October 12-16, 1999
• 11: Hsieh, C. and Lin, T. 1992. VLSI architecture for block-matching motion estimation algorithm. IEEE Transactions on Circuits, Systems for Video Technology 2, 169--175.
• 12: Meenakshi Kaul , Ranga Vemuri , Sriram Govindarajan , Iyad Ouaiss, An automated temporal partitioning and loop fission approach for FPGA based reconfigurable synthesis of DSP applications, Proceedings of the 36th ACM/IEEE conference on Design automation, p.616-622, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310010]
• 13: Randy Allen , Ken Kennedy, Automatic translation of FORTRAN programs to vector form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.4, p.491-542, Oct. 1987 [doi>10.1145/29873.29875]
• 14: Ming-Hau Lee , Hartej Singh , Guangming Lu , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. C. Filho , Vladimir Castro Alves, Design and Implementation of the MorphoSys Reconfigurable ComputingProcessor, Journal of VLSI Signal Processing Systems, v.24 n.2-3, p.147-164, Mar. 2000
• 15: Yanbing Li , Tim Callahan , Ervan Darnell , Randolph Harr , Uday Kurkure , Jon Stockwood, Hardware-software co-design of embedded reconfigurable architectures, Proceedings of the 37th conference on Design automation, p.507-512, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337559]
• 16: R. Maestre , F. J. Kurdahi , N. Bagherzadeh , H. Singh , R. Hermida , M. Fernandez, Kernel scheduling in reconfigurable computing, Proceedings of the conference on Design, automation and test in Europe, p.21-es, January 1999, Munich, Germany [doi>10.1145/307418.307460]
• 17: Peterson, J. B., O'Connor, R. B., and Athanas, P. M. 1996. Scheduling and partitioning ANSI-C programs onto multiple FPGA CCM architectures. In IEE Symposium on FPGAs for Custom Computing Machines. Napa, CA,
• 18: Hartej Singh , Ming-Hau Lee , Guangming Lu , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. Chaves Filho, MorphoSys: An Integrated Reconfigurable System for Data-Parallel and Computation-Intensive Applications, IEEE Transactions on Computers, v.49 n.5, p.465-481, May 2000 [doi>10.1109/12.859540 ]
• 19: Venkataramani, G. 2001. A compiler framework for mapping applications to a coarse-grained reconfigurable architecture. M.S. Thesis, University of California Riverside.
• 20: Elliot Waingold , Michael Taylor , Devabhaktuni Srikrishna , Vivek Sarkar , Walter Lee , Victor Lee , Jang Kim , Matthew Frank , Peter Finch , Rajeev Barua , Jonathan Babb , Saman Amarasinghe , Anant Agarwal, Baring It All to Software: Raw Machines, Computer, v.30 n.9, p.86-93, September 1997 [doi>10.1109/2.612254 ]
• 21: Timothy J. Callahan , John Wawrzynek, Instruction-Level Parallelism for Reconfigurable Computing, Proceedings of the 8th International Workshop on Field-Programmable Logic and Applications, From FPGAs to Computing Paradigm, p.248-257, August 31-September 03, 1998
• 22: Zhi Alex Ye , Andreas Moshovos , Scott Hauck , Prithviraj Banerjee, CHIMAERA: a high-performance architecture with a tightly-coupled reconfigurable functional unit, Proceedings of the 27th annual international symposium on Computer architecture, p.225-235, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Data-flow languages
      D.3.4 Processors
          Subjects: Optimization; Code generation; Compilers

General Terms:
Algorithms, Design, Experimentation

Keywords:
Reconfigurable computing, SIMD, compilers