МЕТОД ОТОБРАЖЕНИЯ ЗАДАЧ НА КРУПНОГРАНУЛЯРНЫЕ РЕКОНФИГУРИРУЕМЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

Румянцев Александр Сергеевич

2014 , ТОМ 14, НОМЕР 1 ( ЯНВАРЬ-ФЕВРАЛЬ )

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

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

УДК 004.274

МЕТОД ОТОБРАЖЕНИЯ ЗАДАЧ НА КРУПНОГРАНУЛЯРНЫЕ РЕКОНФИГУРИРУЕМЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

Румянцев А.С.

Читать статью полностью

Аннотация

Произведен анализ существующих подходов к отображению задач на реконфигурируемые вычислительные системы, особое внимание уделялось методам отображения на крупногранулярные реконфигурируемые вычислительные системы. На основе произведенного анализа сформированы цель и задачи создания нового эвристического метода отображения задач на крупногранулярные реконфигурируемые вычислительные системы, который базируется на методе разделения графа с выталкиванием вершин, алгоритме покрытия графов, эвристическом подходе к оптимизации и упаковке графа для конкретного варианта крупногранулярной реконфигурируемой вычислительной системы и разработанном методе отображения графа потока данных задачи на ресурсы крупногранулярной реконфигурируемой вычислительной системы. В ходе работы было осуществлено имитационное моделирование разработанного метода и существующих подходов к отображению задач на крупногранулярные реконфигурируемые вычислительные системы на модели системы с крупногранулярной реконфигурируемым аппаратным ускорителем MATRIX. Приведены экспериментальные результаты, доказывающие эффективность предлагаемого подхода по сравнению с широко используемыми методами отображения задач на крупногранулярные реконфигурируемые вычислительные системы и возможность использования динамических параметров функционирования крупногранулярной реконфигурируемой вычислительной системы для дальнейшего улучшения получаемого отображения задачи.

Ключевые слова: крупногранулярные реконфигурируемые вычислительные системы, отображение задач на вычислительные системы, покрытие графов

Список литературы

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