Recurrence cycle aware modulo scheduling for coarse-grained reconfigurable architectures

ABSTRACT

In high-end embedded systems, coarse-grained reconfigurable architectures (CGRA) continue to replace traditional ASIC designs. CGRAs offer high performance at a low power consumption, yet provide flexibility through programmability. In this paper we introduce a recurrence cycle-aware scheduling technique for CGRAs. Our modulo scheduler groups operations belonging to a recurrence cycle into a clustered node and then computes a scheduling order for those clustered nodes. Deadlocks that arise when two or more recurrence cycles depend on each other are resolved by using heuristics that favor recurrence cycles with long recurrence delays. While with previous work one had to sacrifice either a fast compilation speed in order to get good quality results, or vice versa, this is not necessary anymore with the proposed recurrence cycle-aware scheduling technique. We have implemented the proposed method into our in-house CGRA chip and compiler solution and show that the technique achieves better quality schedules than schedulers based on simulated annealing at a 170-fold speed increase.

REFERENCES

• 1: 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
• 2: N. Bansal, S. Gupta, N. Dutt, A. Nicolau, and R. Gupta. Interconnectaware mapping of applications to coarse-grain reconfigurable architectures. Lecture Notes in Computer Science, 3203:891--899, 2004.
• 3: James C. Dehnert , Ross A. Towle, Compiling for the Cydra 5, The Journal of Supercomputing, v.7 n.1-2, p.181-227, May 1993 [doi>10.1007/BF01205184]
• 4: 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
• 5: Seth Copen Goldstein , Herman Schmit , Matthew Moe , Mihai Budiu , Srihari Cadambi , R. Reed Taylor , Ronald Laufer, PipeRench: a co/processor for streaming multimedia acceleration, Proceedings of the 26th annual international symposium on Computer architecture, p.28-39, May 01-04, 1999, Atlanta, Georgia, United States
• 6: R. Hartenstein, A decade of reconfigurable computing: a visionary retrospective, Proceedings of the conference on Design, automation and test in Europe, p.642-649, March 2001, Munich, Germany
• 7: A. Hatanaka and N. Bagherzadeh. A modulo scheduling algorithm for a coarse-grain reconfigurable array template. In Parallel and Distributed Processing Symposium, pages 1--8, Washington, DC, USA, 2007. IEEE Computer Society.
• 9: Jong-eun Lee , Kiyoung Choi , Nikil D. Dutt, Compilation Approach for Coarse-Grained Reconfigurable Architectures, IEEE Design & Test, v.20 n.1, p.26-33, January 2003 [doi>10.1109/MDT.2003.1173050]
• 10: Josep Llosa, Swing Modulo Scheduling: A Lifetime-Sensitive Approach, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.80, October 20-23, 1996
• 11: Guangming Lu , Hartej Singh , Ming-Hau Lee , Nader Bagherzadeh , Fadi J. Kurdahi , Eliseu M. Chaves Filho, The MorphoSys Parallel Reconfigurable System, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.727-734, August 31-September 03, 1999
• 12: Bingfeng Mei , Serge Vernalde , Diederik Verkest , Hugo De Man , Rudy Lauwereins, Exploiting Loop-Level Parallelism on Coarse-Grained Reconfigurable Architectures Using Modulo Scheduling, Proceedings of the conference on Design, Automation and Test in Europe, p.10296, March 03-07, 2003
• 13: Bingfeng Mei , Serge Vernalde , Diederik Verkest , Rudy Lauwereins, Design Methodology for a Tightly Coupled VLIW/Reconfigurable Matrix Architecture: A Case Study, Proceedings of the conference on Design, automation and test in Europe, p.21224, February 16-20, 2004
• 14: Hyunchul Park , Kevin Fan , Manjunath Kudlur , Scott Mahlke, Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176778]
• 15: Hyunchul Park , Kevin Fan , Scott A. Mahlke , Taewook Oh , Heeseok Kim , Hong-seok Kim, Edge-centric modulo scheduling for coarse-grained reconfigurable architectures, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454140]
• 16: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 17: 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 Asia and South Pacific Design Automation Conference, January 21-24, 2008, Seoul, Korea

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Retargetable compilers

General Terms:
Algorithms, Design, Performance

Keywords:
coarse-grained reconfigurable architectures, placement and routing, software pipelining