УДК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).


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2019 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика