A compiler framework for mapping applications to a coarse-grained reconfigurable computer architecture

ABSTRACT

The rapid growth of silicon densities has made it feasible to deploy reconfigurable hardware as a highly parallel computing platform. However, in most cases, the application needs to be programmed in hardware description or assembly languages, whereas most application programmers are familiar with the algorithmic programming paradigm. SA-C has been proposed as an expression-oriented language designed to implicitly express data parallel operations. Morphosys is a reconfigurable system-on-chip architecture that supports a data-parallel, SIMD computational model. This paper describes a compiler framework to analyze SA-C programs, perform optimizations, and map the application onto the Morphosys architecture. The mapping process involves operation scheduling, resource allocation and binding and register allocation in the context of the Morphosys architecture. The execution times of some compiled image-processing kernels can achieve up to 42x speed-up over an 800 MHz Pentium III machine.

REFERENCES

• 1: André DeHon, The Density Advantage of Configurable Computing, Computer, v.33 n.4, p.41-49, April 2000 [doi>10.1109/2.839320]
• 2: H. Singh, et. al., "Morphosys: An Integrated Reconfigurable Architecture,". NATO Symposium on Systems Concepts and Integration, Monterey, CA, 1998.
• 3: Hartej Singh , Guangming Lu , Eliseu Filho , Rafael Maestre , Ming-Hau Lee , Fadi Kurdahi , Nader Bagherzadeh, MorphoSys: case study of a reconfigurable computing system targeting multimedia applications, Proceedings of the 37th conference on Design automation, p.573-578, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337583]
• 4: H. Singh, et. al., "Morphosys: A Parallel Reconfigurable System,". Euro-Par, Toulouse, France, 1999.
• 5: H. Singh, et. al., "Morphosys: A Reconfigurable Architecture for Multimedia Applications,". Workshop on Reconfigurable Computing at PACT, Paris, France, 1998.
• 6: E. M. C. Filho, "The TinyRISC Instruction Set Architecture, Version 2," University of California, Irvine, Irvine, CA November 1998. http://www.eng.uci.edu/morphosys/docs/isa.pdf.
• 7: 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 [doi>10.1023/A:1008189221436]
• 8: 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]
• 9: Robert Rinker , Margaret Carter , Amitkumar Patel , Monica Chawathe , Charlie Ross , Jeffrey Hammes , Walid A. Najjar , Wim Böhm, An automated process for compiling dataflow graphs into reconfigurable hardware, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.1, p.130-139, Feb. 2001 [doi>10.1109/92.920828]
• 10: J. Hammes, et. al., "Compiling a High-level Language to Reconfigurable Systems," Compiler and Architecture Support for Embedded Systems (CASES), Washington, DC, 1999.
• 11: W. Bohm, "The SA-C Language - Version 1.0," Colorado State University, Fort Collins, CO, Technical Report June 2001. http://www.cs.colostate.edu/cameron/Documents/sassy.pdf.
• 12: W. Bohm, "The SA-C Compiler Data-Dependence-Control- Flow (DDCF)," Colorado State University, Fort Collins, CO, Technical June 2001. http://www.cs.colostate.edu/cameron/Documents/ddcf.pdf.
• 13: C. Ebeling , D. C. Cronquist , P. Franklin , J. Secosky , S. G. Berg, Mapping applications to the RaPiD configurable architecture, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.106, April 16-18, 1997
• 14: 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]
• 15: 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
• 16: 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]
• 17: 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
• 18: V. K. Prasanna et. al., "Mapping Applications onto Reconfigurable Architectures using Dynamic Programming," Military and Aerospace Applications of Programmable Devices and Technologies, Laurel, Maryland, 1999.
• 19: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture

General Terms:
Design, Measurement, Performance