Комплекс инструментальных средств разработки программ для вычислительных систем с параллельной архитектурой тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Стефанов, Константин Сергеевич

• Стефанов, Константин Сергеевич
• кандидат физико-математических наук
• 2007

Оглавление диссертации кандидат физико-математических наук Стефанов, Константин Сергеевич

Введение 4 Общая характеристика работы.

ГЛАВА 1. Существующие методы и системы анализа последовательных программ для распараллеливания

1.1 Задача анализа структуры программных комплексов.

1.2 Причины создания автономных систем анализа программ

1.3 Инструментарий для анализа структуры программ.

1.4 Постановка задачи.

ГЛАВА 2. Эволюционные компоненты комплекса инструментальных средств

2.1 Подходы к добавлению анализируемых языков программирования

2.2 Исследование общей структуры программных комплексов

2.3 Исследование управляющей структуры отдельных подпрограмм

2.4 Исследование информационной структуры подпрограмм

2.5 Модули целевых преобразований (эксперты).

2.6 Подсистема визуализации и интерфейс с пользователем.

ГЛАВА 3. Архитектура и принципы построения технологического инструментария

3.1 Принципы построения технологического инструментария

3.2 Общая структура инструментария.

3.3 Уровень внутреннего представления.

3.4 Блоки анализа и преобразований.

3.5 Зависимые от языка блоки.

3.6 Не зависимые от языка блоки

3.7 Уровень модулей целевых преобразований (экспертов)

3.8 Уровень интерфейсов.

ГЛАВА 4. Реализация базовых модулей технологического инструментария

4.1 Разбор программы и перевод во внутреннее представление

4.2 Блоки, реализуемые вычислениями на деревьях.

4.3 Модули определения свойств и их связь с внутренним представлением

4.4 Подключение внешних модулей.

Введение диссертации (часть автореферата) на тему «Комплекс инструментальных средств разработки программ для вычислительных систем с параллельной архитектурой»

Общая характеристика работы

В последнее время все более широкое распространение получают компьютерные методы решения задач. Из-за высокой вычислительной сложности многих методов значительная часть задач не может быть решена без привлечения параллельных вычислительных систем и суперкомпьютеров. Ставшие неотъемлемой частью архитектуры суперкомпьютерных систем элементы параллелизма активно используются в структуре процессоров вплоть до персональных ЭВМ. Вместе с этим, уже более чем тридцатилетняя практика работы с параллелизмом показывает, насколько трудным является этот процесс. Создание программного обеспечения, помогающего эффективно осваивать вычислительные системы с параллельной архитектурой, а также стоящая в этом же ряду задача адаптации большого числа существующих программ под новые компьютеры является важной и актуальной проблемой.

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

Для помощи пользователям создаются специальные технологии параллельного программирования и разрабатываются автономные системы анализа структуры программ. Данное направление исследований активно развивается и у нас в стране, и за рубежом, в создание подобных систем внесли свой вклад многие ученые, такие как С.М. Абрамов, В.В. Воеводин, Вл.В. Воеводин, А.П. Ершов, И.Б. Задыхайло, В.А. Крюков, A.JI. Ласто-вецкий, P. Feautrier, К. Kennedy, D. Kuck, М. Lam, W. Pugh, M. Wolfe и ряд других.

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

Более общий подход к выбору методов анализа программ реализован в системе V-Ray, разработанной в лаборатории Параллельных информационных технологий НИВЦ МГУ и использующей в качестве основы для анализа программ граф алгоритма (параметрическое описание информационной истории реализации программ). В работах В.В. Воеводина и Вл.В. Воеводина сформулированы и доказаны условия существования информационной зависимости в программах, являющиеся не только достаточными, но и необходимыми. Эти критерии применимы к широкому классу программ, называемому линейным классом. Система предназначена для анализа программ на языке Фортран-77.

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

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

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

Разработаны принципы организации и архитектура технологического инструментария, ориентированного на создание как многофункциональных, так и специализированных автономных систем исследования и оптимизации программ, а также на взаимодействие с внешними системами через интерфейсы различного уровня.

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

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

Зависимость от языка анализируемой программы локализована на уровнях внутреннего представления и зависимых от языка модулей, что упрощает добавление других языков для анализа. То же относится и к зависимости от платформы, на которой выполняется полученная система анализа: эта зависимость проявляется в относительно небольшом числе блоков уровня интерфейсов, что облегчает перенос системы.

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

Диссертация состоит из введения, четырех глав, заключения и списка литературы.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Стефанов, Константин Сергеевич

Основные результаты работы:

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

• Разработаны принципы организации и архитектура технологического инструментария, ориентированного на создание как многофункциональных, так и специализированных автономных систем исследования и оптимизации программ, а также на взаимодействие с внешними системами через интерфейсы различного уровня.

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

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

ЗАКЛЮЧЕНИЕ

Список литературы диссертационного исследования кандидат физико-математических наук Стефанов, Константин Сергеевич, 2007 год

1. Shen Z., Li Z., Yew P.-C. An Empirical Study of Fortran Programs for Parallelizing Compilers // IEEE Transactions on Parallel and Distributed Systems. 1990. - Vol. 1, no. 3. - Pp. 356-364.

2. Voevodin V. V., Voevodin VI. V. The V-Ray Technology of Optimizing Programs to Parallel Computers. // WNAA. 1996. - Pp. 546-556.

3. SUIF: An Infrastructure for Research on Parallelizing and Optimizing Compilers / R. P. Wilson, R. S. French, C. S. Wilson et al. // SIGPLAN Notices. 1994. - Vol. 29, no. 12. - Pp. 31-37.

4. The SUIF 1.x Compiler Software Distribution.- 13.09.2007. http:// www-suif.stanford.edu/suif/suifl/index.html.

5. The SUIF Compiler SUIF 2.- 13.09.2007. http ://www-suif. Stanford.edu/suif/suif2/index.html.

6. The KAP/S-1: An Advanced Source-to-Source Vectorizer for the S-1 Mark IIa Supercomputer. / C. Huson, T. Macke, J. Davies et al. // ICPP. 1986. - Pp. 833-835.

7. The KAP/205: An Advanced Source-to-Source Vectorizer for the Cyber 205 Supercomputer. / C. Huson, T. Macke, J. Davies et al. // ICPP. — 1986.-Pp. 827-832.

8. The KAP/ST-100: A Fortran Translator for the ST-100 Attached Processor. / T. Macke, C. Huson, J. Davies et al. // ICPP. 1986. - Pp. 171-175.

9. The FORGE Product Set. — Placerville: Applied Parallel Research Inc., 1995.

10. Polaris: Improving the Effectiveness of Parallelizing Compilers / W. Blume, R. Eigenmann, K. Faigin et al. // Languages and Compilers for Parallel Computing. 1994.- Pp. 141-154.

11. Polaris Project Home Page.— 13.09.2007. http://polaris.cs.uiuc. edu/polaris/polaris-old.html.

12. CAPO Computer-Aided Parallelizer and Optimizer. — 13.09.2007. http: //people.nas.nasa.gov/~hj in/CAPO/index.html.

13. Computer aided parallelisation tools (CAPTools) conceptual overview and performance on the parallelisation of structured mesh codes / C. S. Ierotheou, S. P. Johnson, M. Cross, P. F. Leggett // Parallel Corn-put. 1996. - Vol. 22, no. 2. - Pp. 163-195.

14. Открытая распараллеливающая система.— 13.09.2007. http://ops. rsu. ru/about. shtml.

15. Intel Threading Analysis Tools.— 13.09.2007. http://www.intel.com/ cd/software/products/asmo-na/eng/threading/index.htm

16. Para Wise. — 13.09.2007. http: //www. parallelsp. com/parawise. htm.

17. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. — СПб.: БХВ-Петербург, 2002. 608 с.

18. Св-во Роспатента о регистрации программы для ЭВМ № 2006613632. Система V-Ray исследования и преобразования структуры программ / В. В. Воеводин, Вл. В. Воеводин, К. С. Стефанов и др. № 2006613343; Заяв. 5.10.2006.

19. Система V-Ray. 13.09.2007. http: //v-ray. Parallel. ru.

20. Стефанов К. С. Система анализа информационной структуры программ // Вычислительные методы и программирование. — 2005. — Т. 6, № 1. С. 124-135.

21. Воеводин В. В. Информационная структура алгоритмов. — М.: Изд. Моск. ун-та, 1997. 137 с.

22. OpenMP: Simple, Portable, Scalable SMP Programming. 13.09.2007. http ://www.openmp.org.

23. Fortran DVM язык разработки мобильных параллельных программ / H. А. Коновалов, В. А. Крюков, С. Н. Михайлов, А. А. Погребцов // Программирование. — 1995. — № 1.

24. DVM-система. 13.09.2007. http : //www. keldysh. ru/dvm/.

25. Воеводин Вл. В., Жуматий С. А. Инструментальные средства разработки портабельных программ со сложным графическим интерфейсом // Труды конф. МГУ (по материалам Ломоносовских чте-ний'96).- Изд-во Моск. унив-та, 1996.- С. 37-42.

26. Хмелев Д. В. Восстановление линейных индексных выражений для сведения программ к линейному классу // ЖВМ и МФ.— 1998.— Т. 38, №3.-С. 532-544.

27. Воеводин Вл. В. Теория и практика исследования параллелизма последовательных программ // Программирование. — 1992. — № 3. — С. 3853.

28. Common Text Transformation Library.- 13.09.2007. http://cttl. sourcef orge. net/.

29. CoCoLab Cocktail Toolbox. - 13.09.2007. http://www.cocolab.com/ en/cocktail. html.

30. The mpC Parallel Programming Language and its Programming Environment for Computing on Heterogeneous Computer Networks. — 13.09.2007. http://www.ispras.ru/~mpc/.

31. ELI: A Complete, Flexible Compiler Construction System. / R. W. Gray, S. P. Levi, V. P. Heuring et al. // Commun. ACM. 1992.- Vol. 35, no. 2.-Pp. 121-130.

32. Kastens U., Pfahler P., Jung M. The Eli System // Proceedings 7th International Conference on Compiler Construction CC'98 / Ed. by K. Koskimies. — Lecture Notes in Computer Science no. 1383. — Springer Verlag, 1998. Pp. 294-297.

33. Eli: An Integrated Toolset for Compiler Construction. 13.09.2007. http : //eli-proj ect.sourceforge.net.

34. The PERFECT Club Benchmarks: Effective Performance Evaluation of Supercomputers / M. Berry, D. Chen, P. Koss et al. // The International Journal of Supercomputer Applications. — 1989. — Vol. 3, no. 3. — Pp. 540.

35. Cygwin Information and Installation. — 13.09.2007. http : //www. cygwin. com.

36. Clemm G. M. The Odin system // Selected papers from the ICSE SCM-4 and SCM-5 workshops on software configuration management / Ed. by

37. J. Estublier. — Vol. 1005 of Lecture Notes in Computer Science. — London: Springer-Verlag, 1995. Pp. 241-262.

38. Odin: make replacement.— 13.09.2007. ftp://ftp.cs.colorado.edu/ pub/distribs/odin.

39. Feldman S. I. Make — A Program for Maintaining Computer Programs // Software — Practice and Experience. — 1979. — Vol. 9, no. 4. — Pp. 255— 265.

40. Gansner E. R., North S. C. An open graph visualization system and its applications to software engineering. // Software — Practice and Experience. 2000. - Vol. 30, no. 11. - Pp. 1203-1233.

41. Graphviz — Graph Visualization Software.— 13.09.2007. http://www. graphviz. org/.

42. Стефанов К. С. Архитектура инструментального комплекса для анализа и преобразования структуры программ // Системы управления и информационные технологии. ~ 2007. — № 1.3(27). — С. 395-398.