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

ВВЕДЕНИЕ.

Глава I. СИНХРОНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ.

§ I. Основные задачи синхронизации параллельных процессов в вычислительных системах . ^

§ 2. Основные средства синхронизации параллельных процессов.

§ 3. Влияние конфликтов на производительность многопроцессорной системы

§ 4. Способы уменьшения потерь, связанных с синхронизацией параллельных процессов

Выводы к первой главе. 3*t

Глава 2. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОНФЛИКТОВ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ПРИ РАВНОЦЕННЫХ

РЕСУРСАХ.ЗЬ~

§ I. Математическая модель конфликтов в вычислительной системе.39

§ 2. Общие замечания относительно модели конфликтов в вычислительной системе

§ 3. Оптимальное правило разрешения конфликтов в многопроцессорной системе: случай одного неделимого ресурса. W

§ 4. Экспериментальная проверка эффективности оптимального правила для модели с одним неделимым ресурсом

§ 5. Оптимальное взаимодействие между двумя параллельными процессами с несколькими критическими участками.

§ б. Аналитическая оценка эффективности оптимального правила разрешения конфликтов для двух процессов с несколькими критическими участками . ^SO

§ 7. Оптимальное правило разрешения конфликтов между слабо связанными параллельными процессами . SZ

§ 8. Экспериментальная проверка эффективности оптимального правила для модели слабосвязанных процессов.

§ 9. Возможные обобщения рассмотренных ситуаций

Выводы ко второй главе . .6Z

Глава 3. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОНФЛИКТОВ С

УЧЕТОМ НЕРАВНОЦЕННОСТИ РЕСУРСОВ.€

§ I. Модель конфликтов в многопроцессорной системе с учетом неравноценности ресурсов

§ 2. Понятие оптимальности в и его свойства

§ 3. Управляемые марковские цепи с векторными штрафами

§ 4. Свойства управляемых марковских цепей с векторными штрафами.

§ 5. Человеко-машинная процедура отыскивания оптимальной стратегии при существовании функции полезности

§ б. Применение разработанного аппарата к задаче разрешения конфликтов.8$

Выводы к третьей главе

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

Наиболее эффективно эти требования могут быть удовлетворены на пути максимального распространения многомашинных и мультипроцессорных вычислительных систем.

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

Производство и применение параллельных вычислительных систем и практическое параллельное программирование постепенно становятся массовыми, увеличивается область применения параллельных вычислительных методов, растет число работ по теории параллельной обработки информации. По данным о Западной Европе и Северной Америке, там в начале 70-х годов работало около пяти тысяч параллельных систем, выпускаемых такими фирмами как 3L/AROUQMS , IBM, СДС, ДЕС, HOtfZYWElL и другими [i J .

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

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

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

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

Примерами конфликтов служат одновременный запрос со сторо

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

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

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

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

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

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

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

Диссертация состоит из введения, четырех глав, заключения и приложения.

Выводы к четвертой главе

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

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

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

4. Показано, что применение алгоритма разрешения конфликтов в качестве алгоритма распределения процессора в режиме мультипрограммирования приводит:

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

2) к сохранению производительности системы при отсутствии простоя процессора, причем по отношению к стандартному алгоритму ДОС АСПО индивидуальная производительность некоторых задач резко повышается за счет незначительного снижения производительности в отношении остальных;

3) к увеличению при наличии простоев процессора общей производительности системы (в среднем на 10-15%).

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

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

ЗАКЛЮЧЕНИЕ

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

В диссертации получены следующие основные теоретические и практические результаты.

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

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

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

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

5. Разработанные алгоритмы реализованы в качестве алгоритма диспетчеризации в операционной системе ДОС АСПО для вычислительного комплекса М-7000 (СМ-2) и для управления доступом к последовательно используемым ресурсам в операционной системе вычислительного комплекса IIC-3000.

1. Головкин Б.А, Методы и средства параллельной обработки информации» - В кн.: Итоги науки и техники. Теория вероятностей. .Математическая статистика. Теоретическая кибернетика, т. 17. М.: ВИНИТИ, 1979, с. 85-193.

2. Карцев М.А. Некоторые вопросы построения многопроцессорных вычислительных систем. Вопр. радиоэлектроники, сер. ЭВТ, 1970, вып. 5-6, с. 3-19.

3. Мэдник С,, Донован Дж. Операционные системы. М.: Мир,1978.

4. М. Hynn, J. Gray, A. Jones, К. Legally, Н. Opderbeck, G. Popek, В. Raudell, J. Seltzer, H. Wickle. Operating Systems. Berlin, Heidelberg, New York: Springer-Verlag,1979.

5. Трапезников В. А., Прангишвили И .В., Новохатний А, А., Резанов В,В. Многопроцессорный УВК с перестраиваемой структурой типа ПС-3000, Приборы и системы управления, 1984, Ге- I, с. 3-5.

6. Прангишвили И.В., Игнатущенко В,В., Горинович Л.Н., Трах-тенгерц Э.А. Перестраиваемая управляющая вычислительная система на основе однородных структур. В кн.: 17 Всесоюзное совещание по проблемам управления. М.: Наука, 1974.

7. Прангишвили И.В., Резанов В.В. Многопроцессорные управляющие вычислительные комплексы с перестраиваемой структурой. Препринт, № 10. М.: ИТМиВТ АН СССР, 1977.

8. Мультипроцессорные системы и параллельные вычисления. /Под ред. Ф.Энслоу. М.: Мир, 1976.

9. Котов В.Е. Языки параллельного программирования. В кн.: Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. М.: Наука, 1982, с. 139-169.

10. Дийкстра Э. Взаимодействие последовательных процессов. -В кн.: Языки программирования. М.: Мир, 1972, с. 9-86.

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

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

13. Принципы работы системы 1Ш-370. М.: Мир, 1975.

14. Прангишвили И.В., Стещра Г.Г. Микропроцессорные системы. М.: Наука, 1980.

15. Бабаян Б.А., Сахин Ю.Х. Система Эльбрус. Программирование, 1980, № 6, с. 72-86.

16. Presser L. Multiprogramming coordination.- Comput. Surv., 1975, v.7, Ho.1, p.21-44.

17. Patil S.S. Limitations and capabilites of Dijkstra's semaphore primitives for coordination among processe. Cambridge: MIT, 1971.

18. Lanescu S. A large operating system based semaphore.-Commun. ACM, 1975, v.18, No.7, p.377-389.

19. Andrews G., Schneider P. Concepts and notations for Concurrent Programming.- Comput. Surv., 1983, v.15, JTo.1, p.3-43.

20. Hoare C.A.R. Monitors: an operating system structuring concept.- Commun. ACM, 1974, v.17, No.10, p.549-557.2I.Wirth K. Design and implementation of modula Software -Pract. and Exper., 1978, v.7, No.1, p.67-89.

21. Лшаев В.В. Распределение ресурсов в вычислительных системах. М.: Статистика, 1979.

22. Штрик А,А. Оценка затрат производительности на обмен данными в управляющих многомашинных комплексах систем реального времени. Управляющие системы и машины, 1978, №2,

23. Синюкова Л.Ф., Штрик А.А. Оценка потерь производительности многопроцессорных комплексов при конфликтах в секционированной общей памяти. Автоматика и телемеханика, 1978, гё 10, с. 192-199.

24. Башарин Г.П., Богуславский Л.Б., Штейнберг В.И. Анализ конфликтов в общей памяти мультипроцессорных систем. -Автоматика и вычислительная техника, 1980, № 6, с. 27-32.

25. A.Smith. Multiprocessor Memory Organization and Memory Interference.- Commun. ACM, 1977, v.20, No.10, p.754-761.

26. J. Kurtzberg. On the Conflict Problem in Multiprocessor Systems.- IEEE Trans, on Сотр., 1974, v.C-23, No.3,p.286-293.

27. Бронштейн И.И., Меликян А.Л., Трахтенгррц Э.А. Факторы, влияющие на эффективность работы вычислительных систем. М.: Институт проблем управления, 1981.

28. Авен О .И., Коган ЯД. Управление вычислительным процессом в ЭШ. М.: Энергия, 1978.

29. Майн X., Осаки С. Марковские процессы принятия решений. М.: Наука, 1977.

30. Беллман Р. Динамическое программирование. М.: ИЛ, I960.

31. Ховард Р. Динамическое программирование и марковские процессы. М.: Советское радио, 1964.

32. Бронштейн И.И., Генинсон Б.А,, Трахтенгерц Э.А. Правило минимизации числа конфликтов в многопроцессорных вычислительных системах. Автоматика и телемеханика, 1979, № 3, с. 143-149.

33. Соболь И.М., Численные методы Монте-Карло. М.: Наука, 1973.

34. Генинсон Б.А. Оптимальное взаимодействие между двумя параллельными процессами с несколькими критическими участками. -Программирование, 1980, №3, с. 64-67.

35. Кемени Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука, 1970.

36. Авен О.И., Гурин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982.

37. Генинсон Б.А., Рубчинский А.А, Оптимальное управление слабосвязанными параллельными процессами в вычислительных системах. Автоматика и телемеханика, 1980, № 10, с. 180-187.

38. Боровков А.А. Теория вероятностей. М.: Наука, 1981.

39. Генинсон Б.А, Оптимальное управление общим семафором Дийкстры. В кн.: Моделирование и оптимизация сложных систем управления. М.: Наука, 1981, с. 56-57.

40. Виноградская ТЛ., Генинсон Б.А., Рубчинский А.А. Оптимальные правила разрешения конфликтов в многопроцессорных системах при неоднородных ресурсах. X. Формализация задачи. Техническая кибернетика, Х984, №2, с. 135-142.

41. Виноградская Т.М., Рубчинский А.А. Отделимые отношения в задачах векторной оптимизации» В кн.: Математические методы оптимизации и их применения. М.: ЦЭМИ АН СССР, 1980, с. 74-77.

42. Виноградская Т.М., Рубчинский А.А. Бинарные координатные отношения в критериальном пространстве. Автоматика и телемеханика, 1981, J6 3, с. 95-ЛЮЗ.

43. Винограцская Т.М., Генинсон Б.А., Рубчинский А.А. Полумарковские процессы принятия решений с векторными доходами. Теория.вероятностей и ее применения, 1983, т. 28, вып. I, с. 182-184.

44. Рыков В.В. Управляемые системы массового обслуживания. -В кн.: Итоги науки. Теория вероятностей. Математическая статистика. Теоретическая кибернетика, т. 12. М.: ВИНИТИ, 1975, с. 135-241.

45. Дынкин Е.Б., Юшкевич А.А. Управляемые марковские процессы и их приложения. М.: Наука, 1975.

46. Юшкевич А.А. Об одном классе стратегий в общих управляемых марковских моделях. Теория вероятностей и ее применения, 1973, т. 18, & 4, с. 815-817.

47. Джоффрион А., Дайер Дж., Файнберг А. Решение задачи оптимизации при многих критериях на основе человеко-машинных процедур. В кн.: Вопросы анализа и процедуры принятия решений. М.: Мир, 1976, с. 126-145.

48. Карданов В.Г. Математическое программирование. М.: Наука, 1980.

49. Виноградская Т.М. Иерархические отношения и алгоритм выделения недоминируемых множеств. ДАН СССР, 1979, т. 247, №5, с. 1073-1077.

50. Эфрос Л,Б. 0 приоритетном обслуживании параллельных процессов на критических интервалах. Программирование, 1976, № 5, с. 10-20.

51. Frelbeger W., Grenander U., Sampson P. Patterns in Program References.- IBM Journal of research and development, 1975, v.19, No.3, p.230-243.

52. Генинсон Б.А., Рубчинский A.A., Трахтенгерц Э.А. Целесообразные алгоритмы синхронизации параллельных процессов. Автоматика и вычислительная техника, 1984, № I, с. 4041.

53. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. М.: Наука, 1969.

54. АСП0. Операционные системы. Общее описание и руководство системного программиста. 3.100.0I0T, 1979.

55. Чжун-Кай-лаи. Однородные цепи Маркова. М.: Мир, 1964.

56. Харди Дж., Литявуд Дж., Полиа Д. Неравенства. М.: ИЛ, 1948.