TASKS MAPPING METHOD FOR COARSE GRAIN RECONFIGURABLE SYSTEMS

Alexander Rumyantsev

2014 , VOLUME 14, NUMBER 1 ( JANUARY-FEBRUARY )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

TASKS MAPPING METHOD FOR COARSE GRAIN RECONFIGURABLE SYSTEMS

A. Rumyantsev

Read the full article

Abstract

This paper deals with analysis of existing approaches to tasks mapping on reconfigurable computing systems with special attention paid to mapping methods for coarse grained reconfigurable computing systems. The purpose and objectives of a new heuristic method for tasks mapping on coarse grained reconfigurable computing systems are produced on the base of the carried out analysis. This novel method for tasks mapping on coarse grained reconfigurable computing systems is based on the method of graph partitioning with pushing vertices, graph covering algorithm, a heuristic approach to optimizing and packaging for a particular graph on coarse grained reconfigurable computing system and displaying methods of data flow graph on resources of coarse grained reconfigurable computing system. The simulation was conducted on system model with coarse grained reconfigurable hardware accelerator MATRIX. Experimental results are given. They prove the effectiveness of the proposed approach as compared with the widely used methods for tasks mapping on coarse grained reconfigurable computing systems and the ability to use dynamic functional parameters of coarse grained reconfigurable computing system to further improvement of the mapping results.

Keywords: coarse grain reconfigurable computing systems, tasks mapping on computing systems, graph covering

References

1. Румянцев А.С. Организация и инструментальные средства реконфигурируемых вычислительных сис- тем // Научно-технический вестник информационных технологий, механики и оптики. 2012. № 4 (80). С. 80–86.

2. Hannig F., Dutta H., Teich J. Mapping of Regular Nested Loop Programs to Coarse-Grained Reconfigurable Arrays - Constraints and Methodology // Proc. 18th International Parallel and Distributed Processing Symposium (IPDPSꞌ04). IEEE Computer Society, 2004. Santa Fe, USA (2004). Workshop 3. 8 р.

3. El-Rewini H., Lewis T., Ali H. Task Scheduling in Parallel and Distributed Systems. Englewood Cliffs, NJ: Prentice Hall, 1994. 290 p.

4. Mei B., Vernalde S., Verkest D., De Man H., Lauwereins R. DRESC: a retargetable compiler for coarsegrained reconfigurable architectures // Proc. of the IEEE International Conference on Field-Programmable Technology. Hong Kong, 2002. P. 166–173.

5. Rau B. R. Iterative Modulo Scheduling // Proc. of the 27th Annual International Symposium on Microarchitecture. San Jose, California, 1994. P. 63–74.

6. Park H., Fan K., Mahlke S.A., Oh T., Kim H. Edge-Centric Modulo Scheduling for Coarse-Grained Reconfigurable Architectures // Proc. of the 17th International Conference on Parallel Architecture and Compilation Techniques (PACT-2008). Toronto, Ontario, Canada, 2008. P. 166–176.

7. Lee G., Lee S., Choi K., Dutt N. Routing-Aware Application Mapping Considering Steiner Point for CoarseGrained Reconfigurable Architectures // Proc. of the 6th International Conference on Reconfigurable Computing: Architectures, Tools and Applications (ARC-2010). Berlin-Heidelberg: Springer-Verlag, 2010. P. 231–243.

8. Han K.-H., Kim J.-H. Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization // IEEE Trans. Evolutionary Computation. 2002. V. 6. N 6. P. 580–593.

9. Guo Y., Smit G.J.M., Broersma H., Heysters P.M. A Graph Covering Algorithm for a Coarse Grain Reconfigurable System // ACM Sigplan Conference on Languages, Compilers, and Tools for Embedded Systems (LCTESꞌ03). California, USA, 2003. P. 199–208.

10. Guo Y., Hoede C., Smit G.J.M. A Pattern Selection Algorithm for Multi-pattern Scheduling //Proc. of the 20th International Conference on Parallel and distributed processing (IPDPSꞌ 06). IEEE Computer Society, 2006. P. 198–205.

11. Ahn M., Yoon J.W., Paek Y., Kim Y., Kiemb M., Choi K. A Spatial Mapping Algorithm for Heterogeneous Coarse-grained Reconfigurable Architectures // Proc. of the Conference on Design, Automation and Test in Europe (DATEꞌ06). Leuven, Belgium, 2006. P. 363–368.

12. Yoon J.W., Shrivastava A., Park S., Ahn M., Paek Y. A Graph Drawing Based Spatial Mapping Algorithm for Coarse-Grained Reconfigurable Architectures // IEEE Transactions on Very Large Scale Integration Systems. 2009. V. 17. N 11. P. 1565–1578.

13. Battista G.D., Patrignani M., Vargiu F. A Split-and-Push Approach to 3D Orthogonal Drawing // 6th International Symposium on Graph Drawing. Lecture Notes in Computer Science. 1998. V.1547. Springer-Verlag, 1998. P. 87–101.

14. Петров С.В., Юрков К.В., Овсянников Е.П. Сравнительный анализ сложности реализации быстрых циф- ровых преобразований на RISC-процессорах // Изв. вузов. Приборостроение. 2011. Т. 54. № 9.С. 34–38.

15. Sarkar V. Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. Cambridge, MA: MIT Press, 1989. 213 p.

16. Liou J.-C., Palis M.A., Wei D.S.L. Performance analysis of task clustering heuristics for scheduling static DAGs on multiprocessor system // Parallel Algorithms and Applications. 1997. V. 12. N 1–3. P. 185–203.

17. Callahan T.J., Hauser J.R., Wawryzynek J. The Garp Architecture and C compiler // IEEE Computer. 2000. V. 33. N 4. P. 62–69.

18. Liou J.-C., Palis M.A. A New Heuristic for Scheduling Parallel Programs on Multiprocessor // Proc. of the International Conference on Parallel Architectures and Compilation Techniques (PACT'98). Paris, 1998. P. 358–365.

19. Patrignani M., Pizzonia M. The Complexity of the Matching-Cut Problem // Proc. of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science (WGꞌ01). Lecture Notes in Computer Science. 2001. V. 2204. P. 284–295.

20. Cohoon J.P., Richards D.S., Salowe J.S. A Linear-Time Steiner Tree Routing Algorithm for Terminals on the Boundary of a Rectangle // IEEE International Conference on Computer-Aided Design (ICCAD-88). Digest of Technical Papers. 1988. P. 402–405.

21. Mirsky E., DeHon A. MATRIX: A Reconfigurable Computing Architecture with Configurable Instruction Distribution and Deployable Resources // IEEE Symposium on FPGAs for Custom Computing Machines (FCCMꞌ96). Napa Valley, California, 1996. P. 157–166.

22. DSP Compiler and Processor Evaluation – DSPstone [Электронный ресурс]. Режим доступа: http://www.ice.rwth-aachen.de/research/tools-projects/entry/detail/dspstone/, свободный. Яз. англ. (дата обращения 10.05.2013).

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License