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

Введение

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

Глава 1. Обзор литературы

Глава 2. Распределенная обработка конкурирующих процессов

2.1 Основные понятия и определения.

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

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

2.4 Однородные конкурирующие процессы.

2.5 Одинаково-распределенные конкурирующие процессы

Глава 3. Базовые синхронные режимы организации конкурирующих процессов при распределенной обработке

3.1 Синхронный режим с непрерывным выполнением блоков программного ресурса каждым из процессов.

3.1.1 Неоднородные конкурирующие процессы.

3.1.2 Однородные конкурирующие процессы.

3.1.3 Одинаково-распределенные конкурирующие процессы

3.2 Синхронный режим с непрерывным выполнением каждого из блоков всеми процессами.

3.2.1 Неоднородные конкурирующие процессы.

3.2.2 Однородные и одинаково-распределенные конкурирующие процессы.

3.3 Сравнительный анализ базовых режимов организации конкурирующих процессов.

Глава 4. Задачи оптимизации распределенных конкурирующих процессов

4.1 Критерий эффективности структурирования программного ресурса при распределенной обработке

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

4.3 Оптимизация числа процессоров при распределенной обработке конкурирующих процессов.

4.4 Коэффициенты ускорения вычислений и эффективности использования процессоров

Глава 5. Организация распределенных вычислений при векторно-конвейерной обработке

5.1 Особенности векторно-конвейерной обработки.

5.2 Векторизация операций алгебры логики булевых функций одной и двух переменных.

5.2.1 Двоичные переменные и базовые двоичные функции

5.2.2 Поразрядное логическое произведение двух двоичных переменных (конъюнкция).

5.2.3 Поразрядное отрицание двоичной переменной

5.2.4 Поразрядная логическая сумма двух двоичных переменных (дизъюнкция).

5.2.5 Поразрядная логическая эквивалентность двух двоичных переменных.

5.2.6 Поразрядная импликация двух двоичных переменных

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

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

5.2.9 Функция Шеффера.

5.2.10 Функция Пирса.

5.2.11 Преобразование двоичного кода числа в код Грея

5.2.12 Преобразование кода Грея числа в обычный позиционный код.

5.3 Векторизация алгоритмов операций теории множеств

5.3.1 Базовые операции теории множеств.

5.3.2 Нахождение произведения двух множеств натуральных чисел.

5.3.3 Нахождение суммы двух множеств натуральных чисел.

5.3.4 Нахождение симметрической разности двух множеств натуральных чисел

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

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

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

Выводы. Таким образом, в пятой главе диссертации предложены векторизованные алгоритмы базовых операций алгебры логики и теории множеств для реализации на ВК ЭВМ. Для всех разработанных алгоритмов получены математические оценки их программных реализаций в тактах ВК ЭВМ в зависимости от размерности решаемых задач. По показателю векторизуемости (конвейеризуемости) предложенные алгоритмы относятся к классу векторных и супервекторных.

ЗАКЛЮЧЕНИЕ

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

В этом плане получены следующие результаты:

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

2. Доказаны критерий существования эффективного и критерии оптимальности структурирования программных ресурсов на параллельно выполняемые блоки.

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

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

Для всех разработанных программных реализаций векторно-кон-вейерных алгоритмов получены математические оценки времен их выполнения в тактах ВК ЭВМ.

1. Андон Ф. П., Лаврищева Е. М. Методы инженерии разработки распределенных компьютерных приложений. — Киев: Наук, думка, 1997. — 228 с.

2. Барский А. Б. Параллельные процессы в вычислительных системах. Планирование и организация.— М.: Радио и связь, 1990.— 256 с.

3. Вальковский В. А. Распараллеливание алгоритмов и программ: Структурный подход.— М.: Радио и связь, 1989.— 175 с.

4. Воеводин А. В. Структура пакета программ для решения задач линейной алгебры на векторно-конвейерной ЭВМ и проблемы развития программного обеспечения // Вопросы кибернетики. Эффективное использование высокопроизводительных ЭВМ.— М.,1985.— С. 44—65.

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

6. Воеводин В. В. Математическая модель конвейерных вычислений // Вопросы кибернетики. Конвейеризация вычислений.— М.,1986.— С. 36—62.

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

8. Вопросы кибернетики. Эффективные вычисления на супер-ЭВМ: Сб. ст. / Под ред. В. А. Мельникова и Ю. Г. Дадаева.— М., 1988.— 180 с.

9. Вопросы кибернетики. Прикладное программное обеспечение и моделирование суперсистем: Сб. ст. / Под ред. В. А. Мельникова и Ю. Г. Дадаева.— М., 1991 — 164 с.

10. Вопросы кибернетики. Средства моделирования и разработка прикладных программ для суперЭВМ: Сб. ст. / Под ред. В. А. Мельникова и Ю. Г. Дадаева.— М., 1992.— 164 с.

11. Гантмахер Ф. Р. Теория матриц.— М.: Наука, 1988.— 552 с.

12. Глушков В. М., Капитонова Ю. В., Летичевский А. А. Эффективность параллельных вычислений при ограниченных ресурсах // Докл. АН СССР.— 1980.— Т. 254, № 3.— С. 527—530.

13. Головкин Б. А. Расчет характеристик и планирование параллельных вычислительных процессов.— М.: Радио и связь, 1983.— 272 с.

14. Дадаев Ю. Г. Стандартное прикладное обеспечение для векторно-конвейерной ЭВМ // Вопросы кибернетики. Программное обеспечение высокопроизводительной системы.— М., 1986.— С. 100—105.

15. Дорошенко А. Е. Динамические модели параллельных вычислений для макроконвейерных программ // Кибернетика и системный анализ.— 1995.— № 6 — С. 45—65.

16. Задыхайло И. Б., Зеленецкий С. Д. Механизмы синхронизации в языках параллельного программирования // Изв. АН СССР. Техническая кибернетика.— 1985.— № 5.— С. 129—174.

17. Иванников В. П., Гайсарян С. С. Особенности систем программирования для векторно-конвейерной ЭВМ // Кибернетика и вычислительная техника. Вып. 2.— М.: Наука, 1986.— С. 3—17.

18. Игнатущенко В. В., Подшивалова И. Ю. Динамическое управление параллельными вычислительными процессами на основе статического прогнозирования их выполнения // Автоматика и телемеханика.— 1997.— № 5.— С. 160—173.

19. Канцедал С. А. Последовательные и параллельные вычисления в общей задаче теории расписаний // Автоматика и телемеханика.— 1989 — № 12.— С. 153—160.

20. Капитонова Ю. В., Кляус П. С., Коваленко Н. С. Об оптимальном структурировании программных ресурсов при организации параллельных вычислений // Докл. Акад. наук БССР.— 1983.— Т. 27, № 3.— С. 228—231.

21. Капитонова Ю. В., Клаус П. С., Коваленко Н. С. Об оптимальной организации одного класса параллельных процессов // Программирование.— 1984.— № 4.— С. 48—56.

22. Капитонова Ю.В., Кляус П.С., Коваленко Н.С. Математическая модель конвейерной организации конкурирующих процессов // ДАН СССР.— 1987.— Т. 293, № 6.— С. 1320—1324.

23. Капитонова Ю. В., Коваленко Н. С. К задаче распределения ресурсов между конкурирующими процессами // Кибернетика.— 1981.— № 3.— С. 17—20.

24. Капитонова Ю. В., Коваленко Н. С. Метод структурирования программных ресурсов при организации параллельных вычислений // Системное и теоретическое программирование: Матер. IV Всес. симпозиума.—■ Кишинев: Штиинца, 1983.— С. 183—185.

25. Капитонова Ю. В., Коваленко Н. С., Овсеец М. И. Об эффективности и оптимальности одного метода распределения программных ресурсов в мультипроцессорных вычислительных системах // Кибернетика.— 1983.— № 6.— С. 23—27.

26. Капитонова Ю. В., Коваленко Н. С., Овсеец М. И. Эффективность конвейерной реализации конкурирующих процессов при ограниченном числе копий программного ресурса // Кибернетика.— 1989.— № 3.— С. 60—65.

27. Капитонова Ю. В., Летичевский А. А. Математическая теория проектирования вычислительных систем.— М.: Наука, 1988.— 296 с.

28. Капитонова Ю. В., Овсеец М. И. Алгоритм построения оптимальной компоновки линейно структурированных программных ресурсов // Кибернетика — 1986.— № 1 — С. 5—8.

29. Катков В. Л., Любимский Э. 3. Программирование.— Мн.: Выш. шк., 1992.— 295 с.

30. Катков В. Л., Любимский Э. 3. Программное обеспечение ЭВМ.— Мн.: Выш. шк., 1992.— 220 с.

31. Коваленко Н. С. О некоторых задачах анализа параллельных вычислений // Кибернетика.— 1980.— № 3 — С. 142—144.

32. Коваленко Н. С., Овсеец М. И., Язневич М. И. Особенности конвейерной организации распределенных конкурирующих процессов // Вопросы кибернетики. Разработка и использование супер-ЭВМ.— М., 1987.— С. 104—111.

33. Коваленко Н. С., Овсеец М. И., Язневич М. И. Векторные алгоритмы нахождения расстояний в графах и их реализация на век-торно-конвейерной ЭВМ // Программирование.— 1992.-— № 1.— С. 65—71.

34. Конвей Р. В., Максвелл В. Л., Миллер Л. В. Теория расписаний.— М.: Наука, 1975.— 360 с.

35. Краснов С. А. Транспьютеры, транспьютерные вычислительные системы и ОККАМ // Вычислительные процессы и системы. Вып. 7.— М.: Наука, 1990 — С. 3—93.

36. Кузюрин Н. Н. О построении многопроцессорных и конвейерных расписаний, близких к оптимальным // Вопросы кибернетики. Разработка и использование супер-ЭВМ.— М., 1987.— С. 84—96.

37. Кузюрин Н. Н., Шокуров А. В. Особенности алгоритмической и программной реализации математических функций на векторно-конвейерных ЭВМ // Вопросы кибернетики. Проблемы организации высокопроизводительных ЭВМ.— М., 1984.— С. 6—23.

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

39. Мельников В. А., Дадаев Ю. Г. Супер-ЭВМ: проблемы создания, использования и развития // Вестн. АН СССР.— 1985.— № 11.— С. 56—59.

40. Михалевич В. С., Капитонова Ю. В., Летичевский А. А. О методах организации макроконвейерных вычислений // Кибернетика.— 1986.— № 3.— С. 3—10.

41. Многопроцессорные ЭВМ и методы их проектирования / Б. А. Бабаян, А. В. Бочаров, В. С. Волин и др.— М.: Высшая школа, 1990.— 143 с.

42. Моисеев H. В. Эффективность планирования последовательности выдачи команд для конвейерной ЭВМ // Вопросы кибернетики. Эффективное использование высокопроизводительных ЭВМ.— М., 1985.— С. 89—110.

43. Овсеец М. И. Минимизация числа процессоров при реализации однородных конкурирующих процессов // Доклады АН БССР.— 1985.— Т. 29, № 12.— С. 1082—1085.

44. Ондаш Й. Алгоритмы распределения ресурсов однородной многопроцессорной системы // Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем.— М.: Наука, 1982.— С. 292—319.

45. Организация вычислений в многопроцессорных вычислительных системах / В. С. Михалевич, Ю. В. Капитонова, А. А. Летичев-ский и др. // Кибернетика.— 1984.— № 3.— С. 1—10.

46. Пособие по программированию на языке Ассемблера Основной машины / Под ред. Ю. Г. Дадаева — М.: Ин-т проблем кибернетики АН СССР, 1986. — 200 с.

47. Проблемы построения системы программирования для векторно-конвейерной ЭВМ / В. П. йванников, Е. С. Кусиков, Е. Е. Мартынов и др. // Вопросы кибернетики. Проблемы создания высокопроизводительных ЭВМ.— М., 1984.— С. 111—117.

48. Саак А. Э., Сапрыкин В. А., Чефранов А. Г. О времени решения пакетов задач в конвейерных системах // Вопросы кибернетики. Средства моделирования и разработка прикладных программ для суперЭВМ.— М., 1992.— С. 125—132.

49. Саак А. Э., Чефранов А. Г. Оценки эффективности параллельно-конвейерных систем при обработке пакетов независимых задач //

50. Известия РАН. Теория и системы управления.— 1996.— № 2.— С. 179—186.

51. Семантика обменов данными в простых мультимодульных программах / А. А. Летичевский, А. Б .Годлевский., А. Е. Дорошенко., С. Л. Кривой // Программирование.— 1983.— № 5.— С. 3—12.

52. Сергеев Н. П., Вашкевич Н. II. Основы вычислительной техники.— М.: Высшая школа, 1988.— 308 с.

53. Столяров Л. Н. Структурный анализ алгоритмов вычислительной математики для их эффективного отображения на архитектуру векторно-конвейерной ЭВМ // Вопросы кибернетики. Конвейеризация вычислений.— М., 1986.— С. 76—103.

54. Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы.— М.: Наука, 1989.— 328 с.

55. Танаев В. С., Шкурба В. В. Введение в теорию расписаний.— М.: Наука, 1975 — 256 с.

56. Транспьютеры: архитектура и программное обеспечение / Г. Харп, Д. Мэй, Р. Уэйман и др.— М.: Радио и связь, 1993.— 303 с.

57. Феррари Д. Оценка производительности вычислительных систем.-М.: Мир, 1981.— 576 с.

58. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей.— М.: Мир, 1984.— 496 с.

59. Фрумкин М. А. Реализация быстрых алгоритмов на векторно-конвейерной ЭВМ // Вопросы кибернетики. Эффективное использование высокопроизводительных ЭВМ.— М., 1985.— С. 65—79.

60. Хокни Р., Джессхоуп К. Параллельные ЭВМ: архитектура, программирование и алгоритмы.— М.: Радио и связь, 1986.— 392 с.

61. Цикритзис Д., Бернстайн Ф. Операционные системы.— М.: Мир. 1977.— 336 с.

62. Черняев А. П. Системы программирования для высокопроизводительных ЭВМ // Итоги науки и техники. Вычислительные науки.— М.: ВИНИТИ, 1990.— Т. 3.— 141 с.

63. Шпаковский Г. И. Организация параллельных ЭВМ и суперскалярных процессоров: Учеб. пособие.— Минск: Белгосуниверситет, 1996.— 284 с.

64. Элементы параллельного программирования / В. А. Вальковский, В. Е. Котов, А. Г. Марчук., Н. Н. Миренков.— М.: Радио и связь. 1983.— 240 с.

65. Data forwarding in scalable sharedmemory multiprocessors / D. A. Koufaty, X. Chen, D. K. Poulsen, J. Torrelas // IEEE Trans. Par all. and Distrib. Syst.— 1996.— Vol. 7, № 12.— P. 1250—1264.

66. Eisenbeis C., Windheiser D. Optimal software pipelining in presence of resource constraints // Parallel Computing Technologies. PaCT-93: Proceedings of the International Conference.— Obninsk. Russia, 1993.— P. 697—712.

67. Frederickson P. 0., Jones R. 0., Smith В. T. Synchronization and control of parallel algorithms // Parallel Comput.— 1985.— Vol. 2, № 3.— P. 255—264.

68. Lee S.-Y., Aggarwal J. K. A mapping strategy for parallel processing // IEEE Trans. Comput.— 1987.— Vol. 36, № 4.— P. 433—442.

69. Lennerstad H., Lundberg L. An optimal execution time estimate of static versus dynamic allocation in multiprocessor systems // SIAM J. Comput.— 1995.— Vol. 24, № 4.— P. 751—764.

70. Kruskal C.P. Allocating independent subtasks on parallel processors // IEEE Trans. Software Engng.— 1985.— Vol. SE-11, № 10.— P. 1001—1016.

71. Kuck D. J. A survey of parallel machine organization and programming // ASM Computing Surveys.— 1977.— Vol. 9, № 1.— P. 29—59.

72. Kuck D. J. Parallel processing of ordinary programs: Advances in computers // N. Y.: Acad. Press — 1977.— № 15 — P. 119—179.

73. Nevison C. Teaching parallel computing using transputers // Parallel Computing Technologies. PaCT-93: Proceedings of the International Conference.— Obninsk. Russia, 1993 — P. 619—629.1.l

74. Rathke M. Parallelisieren ordnungserhaltender Programmsysterne fur hierchische Multiprozessorsysteme // Arbeitsber. Inst. math. Masch, und Datenverars.— 1985.— Bd. 18, № 2.— S. 1—241.

75. Rosberg Z. Process Scheduling in a Computer System // IEEE Trans, on computers.— 1985.— Vol. C-34, № 7.— P. 633—645.

76. Woeginger G. J. A polinomial-time approximation scheme for maximizing the minimum machine completion time // Oper. Res. Lett.— 1997.— Vol. 20, № 4.— P. 149—154.

77. СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

78. Коваленко Н. С., Метельский В. М. О времени реализации конкурирующих процессов при распределенной обработке // Кибернетика и системный анализ.— 1996.— № 1.— С. 54—64.

79. Коваленко Н. С., Метельский В. М. Режимы взаимодействия неоднородных распределенных конкурирующих процессов // Кибернетика и системный анализ.— 1997.— № 3.— С. 31—43.

80. Коваленко Н. С., Метельский В. М. Синхронный режим взаимодействия конкурирзтощих процессов при распределенной обработке // Известия HAH Беларуси. Сер. физ.-мат. наук.— 1998.— № 1.— С. 117—122.

81. Коваленко Н. С., Метельский В. М. Векторизация базовых операций алгебры логики и теории множеств и их реализация.— Минск, 1993.— 24 с.— (Препринт / Акад. наук Беларуси. Ин-т математики; № 10(501)).

82. Метельский В. М. Алгоритмы минимизации числа процессоров при распределенной обработке конкурирующих процессов.— Минск, 1996.— 12 с.— (Препринт / Акад. наук Беларуси. Ин-т математики; № 11(523)).

83. Соболевский П. И., Коваленко Н. С., Метельский В. М. Синхронные режимы выполнения конкурирующих процессов при сосредоточенной и распределенной обработке. — Минск, 1998.— 12 с.— (Препринт / Акад. наук Беларуси. Ин-т математики; № ( )).

84. Соболевский П. И., Коваленко Н. С., Метельский В. М. Оптимизация распределенных конкурирующих процессов // Автоматизация проектирования дискретных систем: Тез. докл. конф.— Минск, 1995.— С. 27.

85. Kovalenko N. S., Metelski V. М. The speed-up of computation in distributed processing of competing processes // 1st International Conference on Parallel Processing and Applied Mathematics.— Czes-tochova, Poland, 1994.— P. 92—99.

86. Kovalenko N. S., Metelski V. M. On a Distributed Processing of Competing Processes // International Conference on Advanced Mathematics, Computations and Applications.— Novosibirsk, 1995.— P. 187—188.