Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности
Диссертация
Планирование оптимального размещения задач по множеству обрабатывающих процессоров — важный этап в процедурах подготовки комплекса взаимодействующих программ к параллельной обработке в мультикомпьютерах и кластерных системах. Оно выполняется с целью минимизации величин коммуникационных задержек, обусловленных способом обмена данными между задачами в ходе их обработки путем передачи сообщений… Читать ещё >
Содержание
- 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. Выводы
Список литературы
- Цилькер, Б.Я. Организация ЭВМ и систем Текст.: учебник для вузов / Б .Я. Циль-кер, С. А. Орлов. СПб.: Питер, 2004.668 с.
- Воеводин В.В., Воеводин Вл.В. Параллельные вычисления— СПб.: БХВ- Петербург, 2002.- 608 с.
- 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.
- Barker, M. (Ed.) (2000). Cluster Computing Whitepaper
- Андреев A.H., Воеводин В. В. Методика измерения основных характеристик программно-аппаратной среды.
- Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.
- R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.
- Борзов Д.Б. Модели и методы размещения задач в параллельных системах и устройства для их реализации / Д. Б. Борзов. канд. дис., Курск, 2002
- Ю.Зотов И. В. и др. Организация и синтез микропрограммных мультимикрокон-троллеров. Курск.: Изд-во «Курск», 1999. — 368 с.
- А.В. Гергель, Р. В. Виноградов. Оценка сложности коммуникационных операций в кластерных вычислительных системах / Нижегор. гос. тех. ун-т им. Н. И. Лобачевского С. 73−77
- R. Buyya. High Performance Cluster Computing: Systems and Architectures. Volume 1, Prentice Hall PTR, NJ, 1999.
- Pfister, G. Sizing Up Parallel Architectures Text. / G Pfister // DataBase Programming & Design OnLine. May 1998
- 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
- Коршунов Ю.М. Математические основы кибернетики. М.: Энергоатомиз-дат, 1987.-496 с.
- Воеводин В.В. Математические модели и методы в параллельных процессах. -М.: Наука., 1986.-296 с.
- Arden B.W., Lee H. Analysis of chordial ring network // IEEETC. 1981. -Vol. C-30,№ 4.-PP. 291−295.
- Reames C.C., Liu M. T. A loop network simultaneous transmission of variable length message // In: 2nd ASCA, Houston, Tex. 1975. — PP. 7−12.
- 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.
- 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.
- Ope О. Теория графов. — M.: Наука, 1968. — 352 с.
- Feng T-Y. A survey of interconnection network // IEEE Computer. 1981. — Vol. 14, № 12. — PP.12−27.
- Wittie L.D. Communication structures for large networks of microcomputers // ШЕЕ Transactions on Computers. 1981. — Vol. C-30, № 4. — PP. 264−273.
- 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.
- 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.
- Chu W.W., Holloway L.J., Lan M.-T., Efe K. Task allocation in distributed data processing // IEEE Computer. — 1980. — № 11. — PP. 57−69.
- 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.
- 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.
- Jo B.-L. et al. Task assignment in homogeneous linear array networks // IEICE Trans. 1991. — Vol. 74, № 9. — PP. 2642−2648.
- H.S. Stone, S.H. Bokhair. Control of distributed processes // Computer. 1978. -№ 6.-PP. 97−106.
- L.M. Ni, K. Hwang. Optimal load balancing strategies for a multiply processor system // Proc. Inernat. Conf. Parallel. Proc. 1981. — PP. 352 — 357.
- Gottlieb A., Schawarts J.T. Networks and algorithms for very-large-scale parallel computation // Computer. 1982. — Vol. 15, № 1. — PP. 27−36.
- Шоу А. Логическое проектирование операционных систем. М.: Мир, 1981.
- Wu S.S., Sweeting D. Heuristic algorithms for task assignment and scheduling in a processor network // Parallel Computing. 1994. — № 20. — PP. 1−14.
- Bokhari Sh. H. On the mapping problem // IEEE Transactions on Computers. — 1981. — Vol. C-30, № 3. — PP. 207−214.
- 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.
- K. Efe. Heuristic models for task assignment scheduling in distributed systems // IEEE Comput. 1982. — 15(6). — PP. 50−56.
- B.W. Kerninghan, S. Lin. An efficient heuristic procedure for partitioning graph // Bell Syst. Tech J. 1970. — № 2, PP. 291−307.
- 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.
- H.S. Stone. Multiprocessor scheduling with the aid of network flow algorithms // IEEE Trans. Software Eng. 1977. — Vol. SE-3. — PP. 85−93.
- 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.
- Y. Zhu. Efficient processor allocation strategies for mesh-connected parallel computers // Parallel and distributed computers. 1992. — Vol. 16. — PP. 328−337.
- Борзов Д.Б., Зотов И. В., Титов B.C. О субоптимальном размещении процессов и данных в кольцевых сетях. Известия вузов. Приборостроение. — Санкт-Петербург, — 2003, — Т46, № 11, С. 48−54.
- Борзов, Д.Б. Процедура размещения комплексов алгоритмов управления в микроконтроллерных сетях с кольцевой структурой / Д. Б. Борзов, И. В. Зотов // Сборник материалов 4-ой международной конференции «Распознавание-99». -Курск, 1999.- С. 137−139.
- Борзов Д.Б. Устройство поиска нижней оценки размещения в матричных системах / Патент РФ № 2 275 681, БИ № 12- от 27.04.2006.
- Борзов Д.Б., Зотов И. В., Титов B.C. Устройство для формирования субоптимального размещения и его оценки / Патент РФ № 2 193 796, БИ № 33, 2002.
- 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.
- Борзов ДБ., Мараят Б. И., Масолов С. А. Метод снижения коммуникационной задержки путем субоптимального размещения задач в матричных базовых блоках кластера, Телекоммуникации 2008№ 4, С 21−25.
- Tanenbaum A.S. Distributed Operation Systems // Prentice-Hall Engeneer-ing/Science/Mathematics- 1st edition- 1994.-PP. 1−648.
- Борзов Д.Б., Мараят Б. И., Типикин А. П. Алгоритмы и принцип организации аппаратных средств ускорения составления плана размещения задач в кластерных мультикомпьютерах / Деп. в ВИНИТИ 25.10.07 г., № 998-В 2007.
- Борзов Д.Б., Мараят Б. И. Методика планирования размещения задач в матрич-но-торроидальных базовых блоках кластерных мультикомпьютеров / Деп. в ВИНИТИ 18.07.06 г., №>961-В 2006.
- Борзов Д.Б., Мараят Б. И., Типикин А. П. Акселератор планирования размещения задач в кластерных вычислительных системах высокой готовности. Известия вузов. Приборостроение, 2008, № 2, С. 29−33.
- Мараят Б.И. Устройство оценки качества размещения в системах с матричной организацией Текст. / Б. И. Мараят, Д. Б. Борзов, Т. А. Заикина, М.Х. Наджад-жра // Положительное решение на выдачу патента РФ по заявке № 2 007 100 634/09(664)).