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

Введение.

1. Задачи, модели и методы оптимального размещения.

1.1 Архитектура современных параллельных систем.

1.1.1 Архитектура массивно-параллельных компьютеров на примере CRAYT3D.

1.1.2 Системы с неоднородным доступом к памяти (NUMA) на примере ORIGIN

1.1.3 Массивно-параллельная система Intel Paragon.

1.2 Размещение задач в параллельных системах.

1.2.1 Топологии параллельных систем и их роль в решении задачи размещения.

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

1.3 Классификация моделей и методов оптимального размещения.

1.4 Анализ моделей и методов размещения в коммутационномонтажном проектировании.

Выводы.

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

2.1 Формализованная постановка задачи.

2.2 Общие принципы решения

2.3 Процесс s-оптимального размещения.

2.4 Получение нижней оценки длины маршрутов между задачами.

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

2.6 Описание процедуры оптимального размещения.

2.6.1 Процедура оптимального размещения.

2.6.2 Пример работы процедуры.

2.7 Анализ эффективности процедуры.

Выводы.

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

3.1 Модель параллельной системы и размещения алгоритмов.

3.2 Формализованная постановка задачи.

3.3 Общие принципы решения.

3.4 Алгоритм поиска нижней оценки.

3.5 Описание процедуры.

3.6 Пример работы процедуры.

3.7 Анализ эффективности процедуры.

3.7.1 Постановка эксперимента.

3.7.2 Результаты эксперимента.

3.8 Выводы.

4 Аппартные модели и устройства оптимального размещения.

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

4.2 Организация взаимодействия с акселератором.

4.3 Аппаратное представление задачи.

4.4 Оценка предельных параметров размещения.

4.4.1 Модель для получения нижней оценки интенсивности взаимодействия подзадач в ПС.

4.4.2 Модель получения нижней оценки длины маршрутов взаимодействующих подзадач в ПС.

4.5 Аппаратная модель оптимального размещения задач в ПС с кольцевой структурой.

4.6 Оценка временных свойств и аппаратных затрат моделей.

4.7 Аппаратная реализация.

4.7.1 Устройство для оценки степени оптимальности размещения.

4.7.2 Устройство для формирования субоптимального размещения и его оценки.

Выводы.

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

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

В данной работе решение задачи размещения предлагается перенести на аппаратный уровень и реализовать его на базе специализированных акселераторов. Это позволяет, с одной стороны, резко уменьшить время поиска размещения, а с другой - искать размещение с большей степенью оптимальности на ограниченном временном интервале, что весьма актуально для режима динамического размещения. На вход акселератора поступают исходные данные задачи размещения от главной машины (хост-компьютера). Акселератор выполняет поиск варианта размещения и выдает его в виде «рекомендаций» для главной машины, которая на их основе управляет ПС. Такой подход пока не нашел широкого применения при синтезе ПС, однако, известны примеры его использования при решении сходных по характеру задач. В частности, аппаратные модели широко используются при размещении монтажных схем в рамках коммутационно-монтажного проектирования ЭВМ, что говорит об их потенциальной применимости к рассматриваемому классу задач.

Работа выполнена в соответствии с программой П.Т.614 "Многопроцессорные ЭВМ с параллельной структурой и системы виртуальной реальности", приказ Министерства общего и профессионального образования Российской Федерации №572 от 2.03.98 г. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2002 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

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

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

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

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

4. Аналитическая и экспериментальная оценка асимптотической сложности предложенных процедур и устройств, а также степени оптимальности получаемых решений.

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

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

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

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

4. Выведены распределения степени оптимальности размещения для представительной выборки графов комплексов задач.

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

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

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

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

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

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

5. Создана программная подсистема, реализующая разработанные алгоритмы размещения задач в параллельных системах. Подсистема зарегистрирована в Отраслевом Фонде алгоритмов и программ с присвоением номера государственной регистрации 50200100267.

Реализация и внедрение. Результаты диссертационной работы были использованы в учебном процессе и внедрены на различных предприятиях, в частности, в ОАО «Счетмаш» («Устройство для оценки качества размещения» по патенту №2171493) и ООО ГШ «Микрокод» программная подсистема (№ 50200100267), что подтверждается соответствующими актами.

Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на второй Международной научно-практической конференции «Информационные технологии в моделировании и управлении» (г. Санкт-Петербург, 2000 г.), на пятой Международной электронной научной конференции «Современные проблемы информатизации в технике и технологиях» (г. Воронеж, 2000 г.), на Пятой Международной конференции «Распознавание - 2001» (г. Курск, 2001 г.), на второй Всероссийской научно-технической конференции «Компьютерные технологии в науке, проектировании и производстве» (г. Нижний-Новгород, 2000 г.), на Межвузовской научно-технической конференции «Управляющие и вычислительные системы. Новые технологии» (г. Вологда, 2000 г.), на третьей Всероссийской научно-технической конференции «Информационные технологии в электротехнике и электроэнергетике» (г. Чебоксары, 2000 г.), на региональной научно-технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2000 г.).

Публикации. Результаты диссертационной работы отражены в 19 работах, в том числе в 1 статье, 3 патентах на изобретение и 1 свидетельстве на программную подсистему, а также 14 тезисах и материалах докладов. Наиболее важные результаты работы вошли как раздел в монографию, подготовленную в соавторстве с И.В. Зотовым и B.C. Титовым.

На защиту выносятся:

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

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

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

4. Устройства-акселераторы для формирования субоптимального размещения.

Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 110 страниц текста и поясняется 35 рисунками; список литературы включает 80 наименований; 3 приложения содержат 40 страниц. Общий объем составляет 180 страниц.

Выводы

1. Предложены аппаратно-ориентированные модели формирования нижних оценок интенсивности взаимодействия задач, позволяющие находить значение за время порядка 0(N |Е|) и длины связей задач, которая находит соответствующее значение за время 0(2|Е!|).

2. Разработана аппаратно-ориентированная модель формирования оптимального размещения задач в ПС с кольцевой топологической организацией, обладающая временной сложностью 0(N4|e|).

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

Заключение

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

При решении поставленной задачи в диссертационной работе получены следующие результаты:

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

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

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

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

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

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

1. Высокоскоростные вычисления. Архитектура, производительность, прикладные алгоритмы и программы Супер ЭВМ / Под ред. Ковалика. -М.: Радио и связь, 1988.-432 С.

2. Балабанов А.С. Многопроцессорные системы. Основные принципы организации. Управляющие системы и машины. - 1983. - №3. - С. 3-10.

3. Валях Е. Последовательно-параллельные вычисления. М.: Мир, 1985. -456 с.4. www.parallel.ru

4. Flynn M.J. Some computer organization and their effectivness // IEEETC. -1972.-vol. C-21, №9. PP. 296-304.

5. Тербер К.Дж. Архитектура высокопроизводительных вычислительных систем. М.: Наука, 1985. - 272 с.

6. Hockney R. Classification and Evaluation of ParallelComputer Systems // Lecture Notes in Computer Science. 1987, №295. - PP. 13-25.

7. Головкин Б.А. Параллельные вычислительные системы. — М.: Наука, 1980.- 520 с.

8. P. Sadayappan, F. Ercal, J. Ramanujam. Cluster partitioning approaches to mapping parallel problems onto a hypercube // Parallel Comput. 1987. - №13(1). -PP. 1-6.

9. Wu S.B., Liu M.T. A cluster structure as an interconnection network for large multimicrocomputer systems // IEEE Transactions on Computers. 1981. - Vol. C-30, №4. - PP. 254-264.

10. Kozdrowski E.W., Theis D.I. Second generation of vector supercomputer // Computer. 1984.-Vol. 13, №11.-PP. 71-83.

11. 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.13. http://ed-thelen.0rg/c0mp-hist/intel-parag0n.html#Placard

12. Anderson G.A., Jensen L.D. Computer interconnection structures, taxonomy, characteristics and examples // Computing Surveys of AC. 1975. - Vol. 7, №4. -PP. 197-213.

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

14. Jafari H., Lewis T.G., Spragins J.D. Simulation of a class of ring structured networks // IEEE Transactions on Computers. 1980. - Vol. C-29, №5. - PP. 385392.

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

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

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

18. Колосков В.А. Метод восстановления логической структуры мультимик-роконтроллерной сети // Известия КГТУ. 1997. - №1. - С. 82-90.

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. Horowits E., Zorat A. The binary tree as an interconnection network: application of multiprocessor systems and VLSI // IEEETC. 1981. - Vol. C-30, №4. -PP. 247-253.

21. Nath D., Maheshwari S.N., Bhatt P.C.P. Efficient VLSI networks for parallel processing based on orthogonal trees // IEEETC. 1983. - Vol. C-32, №6. - PP. 569-581.

22. Despain A.M., Patterson D.A. X-tree: a tree structured multiprocessor computer architecture / Proceedings of 5th Symp. on Computer Architecture, Palo Alto, Calif. 1978.-PP. 144-151.

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

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

25. Perparata F.P., Vuillemin J. The cube-connected connected cycles: a versatile network for parallel computation // Commun. Of ACM. 1981. - Vol. 24, №5. -PP. 300-309.

26. Bhuyan L.N., Agrawal D.P. Generalized hypercube and hyperbus structures for a computer network // IEEETC. 1984. - Vol. C-33, №4. - PP. 323-333.

27. Труды института инженеров по электротехнике и радиоэлектронике // 1989.-Т. 77, №12.

28. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ // Автоматика и вычислительная техника. 1987. - №3. - С. 31-43.

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

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

31. Зотов И.В.и др. Функционально-топологическая организация микропрограммных мультимикроконтроллеров группового логического управления. -Тула.: Тул. гос. ун-т, 1997. 226 с.

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

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

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

35. 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.

36. 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.

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

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

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

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

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

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

43. 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.

44. V.M. Lo. Heuristic algorithms for task assignment in distributed systems // IEEE Transactions on Computers 1988. - Vol. C-37 (11). - PP. 1384-1397.

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

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

47. 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.

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

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

50. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учебное пособие для вузов. М.: «Радио и связь», 1983. - 280 с.

51. Курейчик В.М., Глушань В.М. Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: «Радио и связь», 1990. - 216 с.

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

53. Борзов Д.Б., Зотов И.В. Методика оптимального размещения управляющих алгоритмов в микроконтроллерных сетях с кольцевой структурой // Сборник научных статей «Методы и средства обработки информации», Выпуск №2. Курск, 2000. - С. 44-52.

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

55. O.I. El-Dessouki, W.H. Huan. Distributed enumeration on network computer // Transactions Comput. 1980. - C-29(9). - PP. 818 - 825.

56. Баас Р., Фервай М., Гюнтер X. Delphi 4: полное руководство. К.: Издательская группа BHV, 1998. - 800 с.

57. Борзов Д.Б., Зотов И.В. О формировании предельного размещения алгоритмов в микроконтроллерных сетях с матричной структурой / «Информа-циооные технологии в науке, проектировании и производстве». Н-Н, 2000. -С. 20.

58. Харари Ф. Теория графов. M.: Мир, 1973.

59. Новиков Ю.В., Калашников О.А., Гуляев С.Э. Разработка устройств сопряжения. М.: «ЭКОМ», 1997. - 224 с.

60. Мячев А.А., Степанов В.Н., Щербо В.К. Интерфейсы систем обработки данных: Справочник. М.: Радио и связь, 1989 - 416 с.

61. Борзов Д.Б., Зотов И.В. Устройство для вычисления интенсивности взаимодействия алгоритмов в параллельных управляющих системах / Материалы межвузовской НТК «Управляющие и вычислительные системы. Новые технологии». Вологда, 2000. - С. 111-112.

62. Борзов Д.Б., Зотов И.В., Сусин П.В. Аппаратная модель задачи размещения в параллельных системах с кольцевой структурой // Известия вузов. Приборостроение. Санкт-Петербург, 2002. - №7. - С. 21-29.

63. Шило B.JI. Популярные цифровые микросхемы: Справочник. Металлургия, Челябинск, 1988. - 352 с.

64. Микросхемы и их применение / Батушев В.А., Вениаминов В.Н., Ковалев В. -М.: Энергия, 1978. 248 с.

65. Интегральные микросхемы: Справочник / Тарабрин Б.В., Лунин Л.Ф., Смирнов Ю.Н. -М.: Радио и связь, 1984. -528 с.

66. Петровский И.И. и др. Логические ИС КР1533, КР1554: Справочник в 2-х ч. М.: ТОО «Бином», 1993.

67. Борзов Д.Б., Зотов И.В., Титов B.C. Устройство для оценки степени оптимальности размещения / Патент №2177172 Россия, кл. G 06F 17/00, G 06G 7/122; от. 25.05.2000.

68. Бернштейн Л.С., Калычев Д.П., Дедюлин К.К. Устройство для оценки размещения элементов / А.с. №1430949 СССР. G 06 F 7/00, 15/20; 25.03.87, БИ 38.

69. Борзов Д.Б., Зотов И.В., Титов B.C. Устройство для оценки степени оптимальности размещения / Тезисы докладов региональной научно-технической конференции «Интеллектуальные и информационные системы». Тула, 2000. -С. 83-84.

70. МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

71. На правах рукописи УДК 681.511. Борзов Дмитрий Борисович

72. МОДЕЛИ РАЗМЕЩЕНИЯ ЗАДАЧ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ И УСТРОЙСТВАХ ДЛЯ ИХ РЕАЛИЗАЦИИ