A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures

ABSTRACT

In this work, we investigate the problem of automatically mapping applications onto a coarse-grained reconfigurable architecture and propose an efficient algorithm to solve the problem. We formalize the mapping problem and show that it is NP-complete. To solve the problem within a reasonable amount of time, we divide it into three subproblems: covering, partitioning and layout. Our empirical results demonstrate that our technique produces nearly as good performance as hand-optimized outputs for many kernels.

REFERENCES

• 1: Alfred V. Aho , Mahadevan Ganapathi , Steven W. K. Tjiang, Code generation using tree matching and dynamic programming, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.4, p.491-516, Oct. 1989 [doi>10.1145/69558.75700]
• 2: Yoonjin Kim , Mary Kiemb , Chulsoo Park , Jinyong Jung , Kiyoung Choi, Resource Sharing and Pipelining in Coarse-Grained Reconfigurable Architecture for Domain-Specific Optimization, Proceedings of the conference on Design, Automation and Test in Europe, p.12-17, March 07-11, 2005 [doi>10.1109/DATE.2005.260]
• 3: Girish Venkataramani , Walid Najjar , Fadi Kurdahi , Nader Bagherzadeh , Wim Bohm, A compiler framework for mapping applications to a coarse-grained reconfigurable computer architecture, Proceedings of the 2001 international conference on Compilers, architecture, and synthesis for embedded systems, November 16-17, 2001, Atlanta, Georgia, USA [doi>10.1145/502217.502235]
• 4: B. Mei, et. Al., DRESC: A retargetable compiler for coarse-grained reconfigurable architectures. In International Conference on Field Programmable Technology, 2002
• 5: 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]
• 6: Charles Oliver Shields, Jr. , Ivan Hal Sudborough, Area efficient layouts of binary trees in grids, 2001
• 7: 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
• 8: M. Weinhardt and W. Luk. Pipeline vectorization. IEEE Trans. CAD, 20:234--248, Feb, 2001
• 9: Reiner Hartenstein , Michael Herz , Thomas Hoffmann , Ulrich Nageldinger, KressArray Xplorer: a new CAD environment to optimize reconfigurable datapath array, Proceedings of the 2000 conference on Asia South Pacific design automation, p.163-168, January 2000, Yokohama, Japan [doi>10.1145/368434.368597]
• 10: 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]
• 11: K. Sugiyama, et. al.,. On planarization algorithms of 2-level graphs. IEEE Trans. on Systems, Man and Cybernetics, SMC-11:109-125, 1981
• 12: Corinna G. Lee , Mark G. Stoodley, Simple vector microprocessors for multimedia applications, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.25-36, November 1998, Dallas, Texas, United States