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

• Аль-Мараят Бакер Ибрахим
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Аль-Мараят Бакер Ибрахим

Введение.

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

1.1. Коммуникационные задержки в кластерных системах.

1.2. Понятие о размещении задач по процессорам параллельной системы.

1.3. Связь между топологиями вычислительных систем и методами размещения задач.

1.4. Классификация методов размещения.

1.5. Анализ алгоритмов размещения задач и целесообразность их аппаратной реализации.

1.6. Выводы.

2. Метод планирования размещения задач в кластерных вычислительных системах.

2.1. Постановка задачи минимизации коммуникационной задержки в кластерных вычислительных системах.

2.2. Формализованная постановка задачи размещения в кластерных вычислительных системах.

2.3. Метод минимизации коммуникационных задержек в матричных базовых кластерных блоках.

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

2.3.2. Поиск гипотетической нижней оценки величины коммуникационной задержки.

2.4. Алгоритм планирования размещения задач в кластерных вычислительных системах.

2.4.1. Этапы поиска решения.

2.4.2. Операция парной перестановки столбцов и строк матрицы обмена инф ормации.

2.5. Перестановочный алгоритм планирования размещения задач.

2.6. Метод ускорения сходимости алгоритма.

2.7. Ускоренный алгоритм планирования размещения задач.

2.8. Методика ускоренного выполнения процедуры планирования размещения задач.

2.9. Выводы.

3. Моделирование процедур планирования размещения задач в кластерных системах.

3.1. Описание программной модели процедур планирования.

3.2. Методы моделирования.

3.3. Результаты исследования на модели эффективности алгоритма планирования размещения.

3.4. Выводы.

4. Организация двухуровневого микропроцессорного акселератора планирования размещения задач.

4.1. Принципы аппаратной реализации процедур планирования размещения.

4.2. Двухуровневая структурная организация микропроцессорного акселератора планирования размещения задач.

4.3. Алгоритмы функционирования акселератора.

4.4. Производительность акселератора и функциональные схемы узлов его нижнего уровня.

4.5. Методика и быстродействующее устройство проверки качества размещения задач.

4.6. Выводы.

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

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

В связи с началом освоения отказоустойчивых мультикомпьютеров и кластеров высокой готовности повышаются требования к скорости выполнения процедур планирования размещения задач. Быстрое восстановление правильности функционирования' системы путем реконфигурации ее структуры с отключением неисправного процессора и заменой его резервным, расположенным обычно вне поля обрабатывающих процессоров, приводит к существенному изменению конфигурации связей между ними и образованию длинных и перекрывающихся маршрутов передачи данных. Они могут быть уменьшены и разнесены путем оперативного переразмещения задач. В то же время процедуры планирования размещения являются комбинаторными, имеют большую вычислительную сложность и поэтому могут привести к существенному увеличению времени восстановления и снижению коэффициента готовности системы. Отказываться из-за этого от переразмещения задач перед рестартом восстанавливаемой системы нецелесообразно, так как возросшие коммуникационные задержки могут привести к такой потере системной производительности, которая превысит ожидаемый выигрыш от применения параллельной многопроцессорной обработки комплекса взаимодействующих программ. Поэтому для уменьшения времени восстановления многопроцессорных кластерных систем необходимо многократно снизить затраты времени на планирование размещения задач по сравнению с его программной реализацией в управляющей машине кластера: Этого можно достичь путем создания специализированного ускоряющего вычислительного устройства (акселератора), а при разработке алгоритмов его функционирования целесообразно найти новый метод снижения вычислительной сложности процедур планирования размещения задач по процессорам матричных базовых блоков кластерных систем высокой готовности.

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

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

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

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

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

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Аль-Мараят Бакер Ибрахим

4.6. Выводы

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

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

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

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

Заключение

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

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

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

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

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

5. В результате программного моделирования и статистических исследований на модели алгоритма функционирования разработанного акселератора показано, что скорость составления плана субоптимального размещения задач по процессорам матричного базового блока кластерной системы может быть повышена в 10 раз по сравнению с программной реализацией этого же алгоритма в управляющей машине кластера и в 100 раз по сравнению с известными алгоритмами, основанными на поиске субоптимального размещения методом ветвей и границ. Коммуникационные задержки в базовых блоках кластерных систем снижаются в 1.5.4 раза. Снижение выигрыша по сравнению с лучшими результатами, достигаемыми за счет больших затрат времени на поиск, не превышает 16. .19%.

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

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

Список литературы диссертационного исследования кандидат технических наук Аль-Мараят Бакер Ибрахим, 2008 год

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

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

3. Keller A., Reinfeld A. Anatomy of a Resource Management System for HPC Clusters. Preprint. To appear in: Annual Review of Scalable Computing, Vol. 3, 2001.

4. Barker, M. (Ed.) (2000). Cluster Computing Whitepaper

5. Андреев A.H., Воеводин В.В. Методика измерения основных характеристик программно-аппаратной среды.

6. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.

7. R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.

8. Борзов Д.Б. Модели и методы размещения задач в параллельных системах и устройства для их реализации / Д.Б. Борзов. канд. дис., Курск, 2002

9. Ю.Зотов И.В. и др. Организация и синтез микропрограммных мультимикрокон-троллеров. Курск.: Изд-во «Курск», 1999. - 368 с.

10. А.В. Гергель, Р.В. Виноградов. Оценка сложности коммуникационных операций в кластерных вычислительных системах / Нижегор. гос. тех. ун-т им. Н.И. Лобачевского С. 73-77

11. R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.

12. Pfister, G. Sizing Up Parallel Architectures Text. / G Pfister // DataBase Programming & Design OnLine. May 1998

13. A. Barak and O. La'adan. Performance of the MOSIX Parallel System for a Cluster of PC's. In Proceedings of HPCN Europe conference, 1997

14. Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиз-дат, 1987.-496 с.

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

16. Arden B.W., Lee H. Analysis of chordial ring network // IEEETC. 1981. -Vol. C-30,№4.-PP. 291-295.

17. Reames C.C., Liu M. T. A loop network simultaneous transmission of variable length message // In: 2nd ASCA, Houston, Tex. 1975. - PP. 7-12.

18. Virginia Lo, Wanqian Liu. Noncontiguous processor allocation algorithms for mesh-connected multicomputers // IEEE Transactions on parallel and dist. Systems. -1997. Vol. 8, №7. - PP. 712-725.

19. Siegel H.J., McMillen R.J., Mueller Р.Т. A survey of interconnection methods for reconfigurable parallel processing systems // In: AFIPS Conf. Proc., Washington, D.C. 1979. - Vol. C-29, №2. - PP. 108-115.

20. Ope О. Теория графов. — M.: Наука, 1968. — 352 с.

21. Feng T-Y. A survey of interconnection network // IEEE Computer. 1981. - Vol. 14, №12. - PP.12-27.

22. Wittie L.D. Communication structures for large networks of microcomputers // ШЕЕ Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 264-273.

23. K. Windisc, V.M. Lo, B. Bose. Contiguous and noncontiguous processor allocation algorithms for k-ary n-cubes // Proc. Int'l Conf. Parallel processing. 1995.

24. Ma P.R., Lee E.Y.S., Tsuchiya M. A task allocation model for distributed computing systems // IEEE Transactions on Computers. — 1982. — Vol. G-31, №1. — PP. 41-47.

25. Chu W.W., Holloway L.J., Lan M.-T., Efe K. Task allocation in distributed data processing // IEEE Computer. — 1980. — № 11. — PP. 57-69.

26. Lee Ch.-H., Lee D., Kim M. Optimal task assignment in linear array networks // IEEE Transactions on Computers. — 1992. — Vol. 41, №7. — PP. 877-880.

27. G.S. Rao, H.S. Stone, T.C. Hu. Assignment of tasks in a distributed processor system with limited memory // IEEE Trans. Comput. C-28 (4), - 1979, - PP. 291 -299.

28. Jo B.-L. et al. Task assignment in homogeneous linear array networks // IEICE Trans. 1991. - Vol. 74, №9. - PP. 2642-2648.

29. H.S. Stone, S.H. Bokhair. Control of distributed processes // Computer. 1978. -№6.-PP. 97-106.

30. L.M. Ni, K. Hwang. Optimal load balancing strategies for a multiply processor system // Proc. Inernat. Conf. Parallel. Proc. 1981. - PP. 352 - 357.

31. Gottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. 1982. - Vol. 15, №1. - PP. 27-36.

32. Шоу А. Логическое проектирование операционных систем. М.: Мир, 1981.

33. Wu S.S., Sweeting D. Heuristic algorithms for task assignment and scheduling in a processor network // Parallel Computing. 1994. — №20. — PP. 1-14.

34. Bokhari Sh. H. On the mapping problem // IEEE Transactions on Computers. — 1981. — Vol. C-30, №3. — PP. 207-214.

35. Sadayappan P., Ercal F. Nearest-neighbor mapping of finite element graphs onto processor meshes // IEEE Transactions on Computers. — 1987. — Vol. C-36, №12. — PP. 1408-1424.

36. K. Efe. Heuristic models for task assignment scheduling in distributed systems // IEEE Comput. 1982. - 15(6). - PP. 50-56.

37. B.W. Kerninghan, S. Lin. An efficient heuristic procedure for partitioning graph // Bell Syst. Tech J. 1970. - №2, PP. 291-307.

38. Shen Ch.-Ch., Tsai W.-H. A graph matching approach to optimal task assignment in distributed computing systems using a minimax criterion // IEEE Transactions on Computers. — 1985. — Vol. C-34, №3. — PP. 197-203.

39. H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms // IEEE Trans. Software Eng. 1977. - Vol. SE-3. - PP. 85-93.

40. P. Chuang, N. Tseng. An efficient submesh allocation strategy for mesh computer systems // Proc. 1991 Int'l Conf. Distributed Computer Systems. 1991. - PP. 256263.

41. Y. Zhu. Efficient processor allocation strategies for mesh-connected parallel computers // Parallel and distributed computers. 1992. - Vol. 16. - PP. 328-337.

42. Борзов Д.Б., Зотов И.В., Титов B.C. О субоптимальном размещении процессов и данных в кольцевых сетях. Известия вузов. Приборостроение. - Санкт-Петербург, - 2003, - Т46, №11, С. 48-54.

43. Борзов, Д.Б. Процедура размещения комплексов алгоритмов управления в микроконтроллерных сетях с кольцевой структурой / Д.Б. Борзов, И.В. Зотов // Сборник материалов 4-ой международной конференции «Распознавание-99». -Курск, 1999.- С. 137-139.

44. Борзов Д.Б. Устройство поиска нижней оценки размещения в матричных системах / Патент РФ №2275681, БИ №12; от 27.04.2006.

45. Борзов Д.Б., Зотов И.В., Титов B.C. Устройство для формирования субоптимального размещения и его оценки / Патент РФ №2193796, БИ №33, 2002.

46. L.M. Silva, R. Buyya. Parallel programming and paradigms Text. // Silva L.M., Buyya R. A cluster computer and its architecture. Chapter 1, PP. 1-27.

47. Борзов ДБ., Мараят Б.И., Масолов С.А. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера, Телекоммуникации 2008№4, С 21-25.

48. Tanenbaum A.S. Distributed Operation Systems // Prentice-Hall Engeneer-ing/Science/Mathematics; 1st edition- 1994.-PP. 1-648.

49. Борзов Д.Б., Мараят Б.И., Типикин А.П. Алгоритмы и принцип организации аппаратных средств ускорения составления плана размещения задач в кластерных мультикомпьютерах / Деп. в ВИНИТИ 25.10.07 г., №998-В 2007.

50. Борзов Д.Б., Мараят Б.И. Методика планирования размещения задач в матрич-но-торроидальных базовых блоках кластерных мультикомпьютеров / Деп. в ВИНИТИ 18.07.06 г., №>961-В 2006.

51. Борзов Д.Б., Мараят Б.И., Типикин А.П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности. Известия вузов. Приборостроение, 2008, №2, С. 29-33.

52. Мараят Б.И. Устройство оценки качества размещения в системах с матричной организацией Текст. / Б.И. Мараят, Д.Б. Борзов, Т.А. Заикина, М.Х. Наджад-жра // Положительное решение на выдачу патента РФ по заявке №2007100634/09(000664)).