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

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

Количество процессоров в многопроцессорных системах постоянно увеличивается, поэтому для их полного и эффективного использования, требуется загрузка каждого процессора информационно-независимыми задачами. В связи с этим возникает задача отображения последовательных программ на множестве процессоров. Для этого применяются методы и алгоритмы выявления линейных, условных и циклических независимых участков (Вл.В. Воеводин, В. В. Воеводин, A.B. Каляев, Б. Я. Штейнберг, Э. А. Трахтенгерц, А. П. Типикин, И.В. Зотов), которые в основном ориентированы на программную реализацию. В многопроцессорных системах задача распараллеливания выполняется, как правило, централизованно хост—процессором. Известно, что в число его задач кроме компиляции входит также маршрутизация, назначение и перераспределение заданий, реконфигурация системы в случае сбоев и другие функции, обеспечивающие управление системой. Процедура компиляции состоит из нескольких этапов, отличающихся вычислительной сложностью, поэтому для решения задачи обеспечения распараллеливания сложных последовательных программ требуется привлечение дополнительных технических средств.

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

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

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

Объектом исследования являются процессы обработки данных в вычислительных системах.

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

Для достижения поставленной цели решены следующие задачи.

1. Анализ известных методов выявления параллельно исполняемых участков программ в вычислительных системах и подходов к построению средств аппаратной поддержки распараллеливания задач.

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

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

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

Научная новизна результатов работы состоит в следующем:

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

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

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

Практическая ценность работы заключается в следующем.

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

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

3. Разработан пакет программ для имитационного моделирования, позволяющий получить оценку временного выигрыша в скорости решения задач с использованием разработанного вычислительного устройства. Моделирование показало, что применение устройства ускоряет решение задачи компиляции для 10−500 операторов в 5−8 раз, а для 520 и более — примерно в 10 раз.

На защиту выносится следующие результаты.

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

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

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

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

1. Цилькер, Б .Я. Организация ЭВМ и систем Текст.: учебник для вузов / Б .Я. Цилькер, С. А. Орлов. СПб.: Питер, 2004. 668 с.

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

3. Ахо, А. Компиляторы: принципы, технологии и инструменты Текст. / Р. Сети, Дж.Ульман. М.: Издательский дом «Вильяме», 2001.

4. Ахо, А. Теория синтаксического анализа, перевода и компиляции Текст.: в 2 т. / Дж.Ульман. М.:Мир, 1978.

5. Грис, Д. Конструирование компиляторов для цифровых вычислительных машин Текст.. М.: Мир, 1975.

6. Емельянов, П. Г. Абстрактная интерпретация императивных программ. Текст.: В сб. Системная Информатика, Вып.6. Новосибирск: Наука, 1998. — с.7—47.

7. Flynn, М. Very high-speed computing system Text. / M. Flynn // Proc. IEEE. 1966. N54. P. 1901;1909.

8. Flynn, M. Some Computer Organisations and Their Effectiveness Text. / M. Flynn // IEEE Trans. Computers. 1972. V.21. N 9. P. 948−960.

9. Higbie, L. C. Supercomputer architecture Text. / L. Higbie // Computer. 1973. V.6. N 12. P.48−56.

10. Handler, W. On classification schemes for computer systems in the post Von Neumann era Text. / W. Handler // Lecture Notes in Computer Science, 1975. № 89. P 34¹⁶.

11. Thurber, K. J. Large Scale Computer Architecture Text. / K.L. Thurber // Hayden Book Company, Rochelle Park, New Jersey, 1976.

12. Hwang, K. Computer Architecture and Parallel Processing. Text. / K. Hwang, F.A. Briggs // Lecture Notes in Computer Science. 1984. P.32−40.

13. Feng, Т. Some Characteristics of Assotiative Parallel Processing Text. / T. Feng // Proc. 1972 Sagamore Computing Conf. New Jersey, 1972. P. 5−16.

14. Hockney, R. Parallel Computers: Architecture and Performance Text. / R. Hockney // Proc. of Int. Conf. Parallel Computing'85. Computer Architecture News. 1986. P. 33−69.

15. Hockney, R. Classification and Evaluation of ParallelComputer Systems Text. / R. Hockney // Lecture Notes in Computer Science. 1987. N 295. P. 13−25.

16. Johnson, E. E. Completing an MIMD Multiprocessor Taxonomy Text. // E.E. Johnson // Computer Architecture News. 1988. V. 16. N 2. P. 44−48.

17. Duncan, R. A survey of parallel computer architectures Text. // R. Duncan // Computer. V.23. N 2. 1990. P. 5−16.

18. Killicorn, D. A. Taxonomy for Computer Architectures Text. / D.A. Skillicorn // Computer. 1988. V.21. N 11. P. 46−57.

19. Ортега, Дж.

Введение

в параллельные и векторные методы решения линейных систем Текст.. М. Мир, 1991. — 365с.

20. Чинин, Т. Д. Векторизация программ: теория, методы, реализация Текст.: сб. -М.: Мир, 1991.-272с.

21. Денисенко, В. А. Проблемы схемотехнического моделирования КМОП СБИС Текст. // Компоненты и технологии, 2002. № 4.

22. Пяткин, А. К. Реализация на ПЛИС быстрого преобразования Фурье для алгоритмов ЦОС в многофункциональных PJIC Текст. / М. В. Никитин //- «Цифровая обработка сигналов» № 3, 2003.

23. Пат. 2 039 375 РФ, МКИ6 G 06 F 17/00, 17/20. Устройство для реализации продукций. В. М. Довгаль.

24. Пат. 2 067 315 РФ, МКИ5 G 06 F 15/20. Устройство для реализации подстановок. В. М. Довгаль.

25. S. Gochman et al. The Intel Pentium M Processor: Microarchitecture and Performance. Intel Technology Journal, V.7, Issue 2, 2003.

26. Дюбрюкс, C.A. Устройство для формирования размещения и оценки его качества / Д. Б. Борзов // Международный сборник научных трудов «Информационные технологии моделирования и управления. Выпуск 17». Воронеж: Из-во «Научная книга», 2004. — С. 3−8.

27. Картунов, В. Prescott: Последний из могикан? (Pentium 4: от Willamette до Prescott). Ф-Центр, 2005.

28. Бессонов, О. Новое вино в старые мехи. Сопгое: внук процессора Pentium III, племянник архитектуры NetBurst? iXBT.com, 2005.

29. Бессонов, О. Двухъядерный процессор Yonah: уже не Pentium III, ещё не Сопгое. iXBT.com, 2006.

30. Sean Lee, Н.Н. Р6 & NetBurst Microarchitecture. School of ЕСЕ, Georgia Institute of Technology, 2003.

31. IA—32 Intel Architecture Optimization Reference Manual. Intel, 2006.

32. IA-32 Intel Architecture Software Developer’s Manual. Intel, 2006.

33. Картунов, В. Детальное исследование архитектуры AMD64. iXBT.com, 2003.

34. De Vries, Н. Understanding the detailed Architecture of AMD’s 64 bit Core. Chip-Architect, 2003.

35. Kanter, D. AMD’s K8L and 4×4 Preview. Real World Technologies, 2006.i.

36. Tendler et al, J. POWER4 system microarchitecture. IBM Journal of Research and Development, V.46, No. l, 2002.

37. Толл, P. P. Множества. Логика. Аксиоматические теории Текст. М.: Просвещение, 1968. — 232 с.

38. Кантор, Г. Труды по теории множеств Текст. -М.: Наука, 1985. с. 173.

39. Куратовский, К. А. Теория множеств Текст. — М.: Мир, 1970. 416 с.

40. Верещагин, Н. К. Лекции по математической логике и теории алгоритмов Текст.: Часть 1. Начала теории множеств / А.Шень.

41. Френкель, А. Основания теории множеств Текст. / И. Бар—ХиллелПеревод с английского Ю. А. Гастева под редакцией А. С. Есенина-Вольпина. — М.: Мир, 1966.-366 с.

42. Гетманова, А. Д. Учебник по логике. — М.: Владос, 1995. — 303 с.

43. Кондаков Н. И.: Логический словарь-справочник. — М.: Наука, 1975. — 720 с.

44. Дюбрюкс С. А. Метод выявления параллелизма внутри линейных участков последовательных программ и его аппаратная реализация / Д. Б. Борзов, В. С. Титов // Известия вузов. Приборостроение. Т.2 Санкт-Петербург, 2008 — с. 34−38.

45. Трахтенгерц, Э.А.

Введение

в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции Текст. — М.:Наука, 1981.-254с.

46. Воеводин, В. В. Математические модели и методы в параллельных процессах Текст. М.: Наука., 1986. — 296 с.

47. Патент № 2 285 289 РФ, БИ № 28. Устройство планирования размещения задач в системах с кольцевой организацией при направленной передаче информации / Д. Б. Борзов Д.С. Горощенков- № 2 005 101 060/09- заявл. 18.01.2005; опубл. 10.10.2006, Бюл. № 28. 13 с.

48. Ивлев, Ю. В. Учебник логики Текст.: Семестровый курс: Учебник. — М.: Дело, 2003. —208 с.

49. Бочаров, В. А. Основы логики Текст.: Учебник. / В. И. Маркин. — М.: ИН-ФРА-М, 2001. —296 с.

50. Ивин, А. А. ЛогикаТекст.: Учебное пособие. Изд. 2-е. —М.: Знание, 1998.

51. Ивин, А. А. Словарь по логике Текст. / Никифоров A. JI. — М.: Туманит, ВЛАДОС, 1997. —384 с.

52. Корнеев, В. В. Параллельные вычислительные системы Текст. -М:" Нолидж", 1999. 320 с.

53. Дюбрюкс, С. А. Методика поиска и устранения избыточных вычислений в последовательных участках программ / Д. Б. Борзов // Студенческий научно-технический журнал «Инженер», № 9. Донецк. 2008. — С.62−64.

54. Дюбрюкс, С.А., Устройство для формирования размещения и оценки его качества / Д. Б. Борзов // Международный сборник научных трудов «Информационные технологии моделирования и управления. Выпуск 17». — Воронеж: Из-во «Научная книга», 2004. — с. 3−8.

55. Костенко, В.А. К вопросу об оценке оптимальной степени параллелизма. -Программирование. 1995, с. 24—28.

56. Антонов, A.C. Параллельное программирование с использованием технологии MPI Текст.: Учебное пособие. -М.: Изд-во МГУ, 2004. 71 с.

57. Бочаров, Н. В. Технологии и техника параллельного программирования. Обзор. // «Программирование», № 1, 2003. с.5−23.

58. Соколинский, Л. Б. Параллельные машины баз данных. // Сборник научно-популярных статей «Российская наука на заре нового века». Под редакцией академика В. П. Скулачева. М.: научный мир, 2001. — с. 484−494.

59. Таненбаум, Э. Распределенные системы. Принципы и парадигмы Текст. -СПб.: Питер, 2003. 877 с.

60. Дюбрюкс, С. А. Метод объединения и разделения циклических участков последовательных наследуемых программ / Д. Б. Борзов, В. С. Титов // Известия вузов. Приборостроение. № 2. — Санкт-Петербург, 2009 с.34−38.

61. Дюбрюкс, С. А. Программная модель распараллеливания линейных участков последовательных программ со связями по управлению. / Д. Б. Борзов, В. С. Титов // Свидетельство о государственной регистрации программы для ЭВМ № 2 010 610 467. Москва: РосПатент.

62. Кобзарь, А. И. Прикладная математическая статистика Текст. — М.: Физ-матлит, 2006. — 816 с.

63. Бибило, П. Н. Основы языка VHDL Текст. М.: «Солон-Р», 2000.

64. Зотов, В. Ю. Проектирование цифровых устройств на основе ПЛИС фирмы Xilinx в САПР WebPACK ISE Текст. / В. Ю. Зотов. М.: Горячая линия-Телеком, 2003. — 624 с.

65. Зотов, В. Ю. Проектирование цифровых устройств на основе ПЛИС фирмы Xilinx в САПР WebPACK ISE Текст. / В. Ю. Зотов. М.: Горячая линия-Телеком, 2006. — 550 с.

66. Поляков, А. К. Языки VHDL и VERILOG в проектировании цифровой аппаратуры Текст. М.: Солон-пресс, 2009. — 320 с.

67. Максфилд, К. Проектирование на ПЛИС. Курс молодого бойца Текст., 2007. — 440 с.

68. Армстронг Д. Моделирование цифровых систем на языке VHDL Текст. — М.: Мир, 1992.

69. Суворова, Е. Проектирование цифровых систем на VHDL Текст. / Шейнин Ю. Cn6.:BHV, 2003. — 576 с.

70. Тарасов, И. Е. Разработка цифровых устройств на основе ПЛИС Xilinx с применением языка VHDL Текст. / И. Е. Тарасов. М.: Горячая линия-Телеком, 2005.-252 с.

71. Суворова, Е. А. Проектирование цифровых систем на VHDL Текст. / Е. А. Суворова, Ю. Е. Шейнин. СПб.: БХВ-Петербург, 2003. — 576 с.

72. Сергиенко, А.М. VHDL для проектирования вычислительных устройств Текст. / А. М. Сергиенко К.: ЧП «Корнейчук», ООО «ТИД ДС», 2003. — 208 с.

73. Патент № 2 319 204 РФ, МПК G06 °F 17/50. Устройство для формирования размещения в системах с линейной организацией / С. А. Дюбрюкс, Д. Б. Борзов, В.С.Титов- № 2 006 127 974/09- заявл. 01.08.2006; опубл. 10.03.2008, Бюл. № 7. 11 с.