Compiling custom instructions onto expression-grained reconfigurable architectures

ABSTRACT

While customizable processors aim at combining the flexibility of general purpose processors with the speed and power advantages of custom circuits, commercially available processors are often limited by the inability to reconfigure the application-specific features after manufacturing. Even though reconfigurable array-based accelerators are available, their performance is often unacceptable, and comes with other disadvantages such as the size of the configuration bitstream. Additionally, compilation support is limited for existing Coarse Grain Reconfigurable Arrays (CGRAs).

We propose to target a different reconfigurable fabric, the EGRA (Expression-Grained Reconfigurable Array), to realize custom instructions in a customizable processor. The EGRA is based on arithmetic processing elements that can compute entire subexpressions in a single cycle and can be connected in both combinational or sequential manners. We present here a compilation flow for this architecture, including novel algorithms for subgraph enumeration and scheduling. The compilation flow proposed is used here to efficiently explore the design space of the EGRA processing element; furthermore, its modularity and flexibility suggest suitability to generic CGRA retargetable compilation.

REFERENCES

• 1: G. Ansaloni, P. Bonzini, and L. Pozzi, "Design and architectural exploration of expression--grained reconfigurable arrays," in Proceedings of the 6th Symposium on Application Specific Processors, Anaheim, CA, June 2008.
• 2: Nathan Clark , Manjunath Kudlur , Hyunchul Park , Scott Mahlke , Krisztian Flautner, Application-Specific Processing on a General-Purpose Core via Transparent Instruction Set Customization, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.30-40, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.5]
• 3: Ajay K. Verma , Philip Brisk , Paolo Ienne, Rethinking custom ISE identification: a new processor-agnostic method, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289905]
• 4: C. Morra, J. a. M. P. Cardoso, and J. Becker, "Using rewriting logic to match patterns of instructions from a compiler intermediate form to coarse-grained processing elements," in Proceedings of the 2007 IEEE International Parallel and Distributed Processing Symposium, 2007, Mar. 2007, pp. 1--8.
• 5: R. Geiβ, G. V. Batz, D. Grund, S. Hack, and A. Szalkowski, "GrGen: A fast SPO-based graph rewriting tool," in Proceedings of the 3rd Internatial Conference on Graph Transformations, Natal, Brazil, Sept. 2006.
• 6: Kubilay Atasu , Laura Pozzi , Paolo Ienne, Automatic application-specific instruction-set extensions under microarchitectural constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775897]
• 7: Nathan Clark , Amir Hormati , Scott Mahlke , Sami Yehia, Scalable subgraph mapping for acyclic computation accelerators, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176779]
• 8: P. Y. Calland, A. Mignotte, O. Peyran, Y. Robert, and F. Vivien, "Retiming DAG's," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 17, no. 12, pp. 1319--25, Dec. 1998.
• 9: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 10: M. Galanis, G. Theodoridis, S. Tragoudas, and C. Goutis, "A high-performance data path for synthesizing DSP kernels," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 6, pp. 1154--1162, June 2006.
• 11: B. Mei, S. Vernalde, D. Verkest, H. De Man, and R. Lauwereins, "DRESC: A retargetable compiler for coarse-grained reconfigurable architectures," in Proceedings of the IEEE International Conference on Field-Programmable Technology, Dec. 2002, pp. 166--173.
• 12: Minwook Ahn , Jonghee W. Yoon , Yunheung Paek , Yoonjin Kim , Mary Kiemb , Kiyoung Choi, A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 13: Jonghee W. Yoon , Aviral Shrivastava , Sanghyun Park , Minwook Ahn , Reiley Jeyapaul , Yunheung Paek, SPKM: a novel graph drawing based algorithm for application mapping onto coarse-grained reconfigurable architectures, Proceedings of the 2008 conference on Asia and South Pacific design automation, January 21-24, 2008, Seoul, Korea
• 14: Yuanqing Guo , Gerard J.M. Smit , Hajo Broersma , Paul M. Heysters, A graph covering algorithm for a coarse grain reconfigurable system, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 15: 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]
• 16: F. Bouwens, M. Berekovic, A. Kanstein, and G. Gaydadjiev, "Architectural exploration of the ADRES coarse-grained reconfigurable array," in Reconfigurable Computing: Architectures, Tools and Applications, ser. Lecture Notes in Computer Science. Berlin: Springer, June 2007, vol. 4419, pp. 1--13.
• 17: 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]
• 18: PACT XPP Technologies, Inc., "XPP-III processor overview," 2006. {Online}. Available: http://www.pactxpp.com/main/ download/XPP-III overview WP.pdf

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Data-flow architectures
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
coarse-grained reconfigurable architectures, compilers, data-flow architectures, horizontal microprogramming, instruction set extensions