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

ВВЕДЕНИЕ

ГЛАВА I. ОСНОВНЫЕ ЗАДАЧИ ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ

ВЫЧИСЛЕНИЙ НА КОМПЛЕКСАХ.

1.1. Вычислительные структуры, ориентированные на эффективную реализацию параллельных вычислений.

1.2. Многомашинные и многопроцессорные комплексы из серийных ЭВМ.

1.3. Языки и системы параллельного программирования

1.4. Основные механизмы управления выполнением параллельных программ на комплексах

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

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

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

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

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

В 1.4 рассматриваются основные механизмы управления выполнением ПП на ВК без учета отказов и сбоев аппаратуры на цримере АБС-системы параллельного программирования, как отражающей наиболее общие черты управления выполнением ПП на комплексах, организуемых из серийных ЭВМ.

ВЫВОДЫ

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

1. Разработана общая модель управления выполнением параллельных программ (ПП) на многомашинных и многопроцессорных вычислительных комплексах (ВК) в условиях отказов, сбоев и восстановлений аппаратуры,

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

3. Разработаны эффективные алгоритмы обеспечения высокой надежности процесса выполнения ПП на ВК в условиях отказов, сбоев и восстановлений его компонентов, включая отказы и восстановления ЭВМ, каналов связи и процессоров.

4. Применительно к АБС-системе параллельного программирования создана система программных средств обеспечения надежности процесса выполнения Ш на ВК ЕС ЭВМ, которая включает: а) язык описания структуры ВК и средства трансляции с этого языка; б) управляющие программы обеспечения надежности процесса выполнения ПП на ВК.

Подготовлена и тиражируется соответствующая документация.

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

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

7. Разработанные программные средства обеспечения надежности выполнения ПП на ВК ЕС ЭВМ внедрены на ряде предприятий отечественной промышленности.

4.3. Заключение.

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

2. Предложена структура программного обеспечения управления выполнением ПП в условиях отказов, сбоев и восстановлений аппаратуры ВК организуемого из машин ЕС ЭШ.

3. Разработана общая схема организации взаимодействия ПСВ с программами управления выполнением ПП АБС-системы параллельного программирования, аппаратно-программными средствами восстановления и операционной системой ЕС ЭШ.

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

1. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. "Наука", Новосибирск, 1966.

2. Евреинов Э.В., Хорошевский В.Г. Однородные вычислительные системы. "Наука", Новосибирск, 1978.

3. Каляев А.В. Теория цифровых интегрирующих, машин и структур. "Сов.радио", М., 1970.

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

5. Глушков В.М. и др. Теория языковых процессоров и параллельные вычисления. "Кибернетика", № I, 1979.

6. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. "Радио и связь", М., 1981.

7. Евреинов Э.В. Однородные вычислительные системы, структуры и среды. "Радио и связь", М., 1981.

8. Фостер К. Ассоциативные параллельные процессоры. "Энерго-издат", М., 1981. (Перевод с английского под редакцией Еутепова В.П.)

9. Марчук Г.И., Котов В.Е. Модульная асинхронная развиваемая система (концепция). Части I и 2. Препринт ВЦ СО АН СССР, 86, 87. Новосибирск, 1978.

10. Котов В.Е. Введение в теорию схем црограмм. Новосибирск, "Наука", 1979.

11. Кутепов В.П., Фальк В.Н. Функциональные граф-схемы и их эквивалентные преобразования. Труды Первой Всесоюзной конференции по программированию. Киев, Институт кибернетики АН УССР, 1968.

12. Кутепов В.П. Исчисление функциональных схем и параллельные алгоритмы. "Программирование", № 6, 1976.

13. Кутепов В.П. Функциональные системы и параллельные вычисления. Диссертация на соискание ученой степени доктора техн.наук.1. М., МЭИ, 1981.

14. Ющенко Е.Л. Структурное программирование и параллельные вычисления, В сб.: Параллельное программирование и высокопроизводительные системы. Часть I. СО АН СССР, Вычислительный центр, Новосибирск, 1980.

15. Евреинов Э.В., Хорошевский В.Г. Вычислительные системы с программируемой структурой. В сб.: Параллельное программированиеи высокопроизводительные системы. Часть I. СО АН СССР, Вычислительный центр, Новосибирск, 1980.

16. Поспелов Д.А. Введение в теорию вычислительных систем. "Сов.радио", М., 1972.

17. Димитриев Ю.К., Хорошевский В.Г. Вычислительные системы из мини-ЭВМ. Под ред. Евреинова Э.В. М., "Радио и связь", 1982.

18. Д.Феррари. Оценка производительности вычислительных систем. М., "Мир", 198I.

19. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Теория структур данных и синхронные параллельные вычисления. "Кибернетика", J& 6, 1976.

20. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Теория языковых процессоров и параллельные вычисления. "Кибернетика", iß I, Киев, 1979.

21. Барский А.Б. Планирование параллельных вычислительных процессов. М., "Машиностроение", 1980.

22. Трахтенгерц Э.А. Структура многопроцессорных систем РВМ и распараллеливание вычислительных процессов. В кн.: Разработки и исследования рациональных структур вычислительных систем реального времени. Материалы семинара. М., МДНТП, 1979, с. 14-18.

23. Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. "Наука", М., 1978.

24. Головкин Б.А. Параллельные вычислительные системы. "Наука", М., 1980.

25. Кутепов В.П. Языки и планирование выполнения параллельных алгоритмов на системах. В кн.: Разработки и исследования рациональных структур вычислительных систем реального времени. Материалы семинара. - ВДНТП, М., 1979, с. I09-II4.

26. Деннис Дж.Б., Фоссин Дж.Б., Линдерман Дж.П., Схемы потока данных. Теория программирования. Часть 2, Труды симпоз., ВЦ СО

27. АН СССР, Новосибирск, 1972.

28. Евреинов Э.В., Косарев Ю.Г. Матричный Р-язык для описания параллельных алгоритмов. Вычислительные системы, вып. 17, Новосибирск, 1965.

29. Керн P.M., Миллер P.E. Параллельные схемы программ. В кн.: "Кибернетический сборник" (нов.серия), вып. 13, "Мир", М., 1976.

30. Кутепов В.П., Кораблин Ю.П. Язык граф-схем параллельных алгоритмов. "Программирование", № I, М., 1978.

31. Кутепов В.П., Фальк В.Н. функциональные системы: теоретический и практический аспекты. "Кибернетика", № I, Киев, 1979.

32. Baer , /(survey о| some theoretical aspects multiprocessing, Computing Surveys, v.5, n1, 1973

33. Кутепов В.П., Кораблин Ю.П. Реализация языка граф-схем параллельных алгоритмов на вычислительных системах. В сб.: Автоматизированные системы управления. М., МЭИ, 1980.

34. Kuck D.I, ILLiAC-4 software and apptlcatl-on programming, • IEEE Trans. on comp., V.17 18,1967.

35. Lind se Y C.H., Van Meu£eta S. G\ f Informad Introduction, to A£go£-68, North HotEand pubtLsfiLng Company , 1971 .

36. MltEer R.E., A comparison o| some tfieoretlcai models q£ paracet computation T IEEE Traías.on comput., '1973, с-22 , ns& , Special Section on ParaCCet computation.

37. Строева T.M., Фальк В.Н. Асинхронные вычислительные сети: ABC-модель и ABC-система параллельного программирования. "Кибернетика", № 3, Киев, 1981.

38. Вычислительная система СУММА. В кн.: "Вычислительные системы". Вып.60, Новосибирск, 1974.

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

40. Кербель В.Г. и др. Программное обеспечение системы МИНИМАКС. Препринт ИМ СО АН СССР, 0ВС-09, Новосибирск, 1979.

41. Кутепов В.П. и др. Вопросы реализации параллельных алгоритмов на вычислительных системах. "Программирование", № 2, М., 1975.

42. Миренков H.H. Системное параллельное программирование. 4.1, Ч.П, Препринты ИМ СО АН СССР, ОВС-5, ОВС-6, Новосибирск, 1978.

43. Hoare C.A.R., Monitors: an operating svstem. structuring Concept, comms. ACM, V.1?, nHO, 1974.

44. Organic ЕЛ., Computer svstem organization r Tfie B-5?0Q / B~6?00 series , Academic Press ; Mew York ? 19P3.

45. Диспетчер параллельных алгоритмов для систем М-6000/М-7000. Программное обеспечение М-6000 свт, 3.008.ООО.С, Северодонецк,1. НИИ ЭВМ, 1976.

46. Миренков H.H. Организация высоконадежного счета в однородных вычислительных системах. УС и М. - Киев, 1976, № 4, с.46-54.

47. Саркисян Т.Е. Средства обеспечения высокой надежности и ремонтопригодности ЭВМ EC-I045. "Вопросы радиоэлектроники", сер. ЭВТ, 1979, вып.14.

48. Сидоров A.M. Методы контроля электронных цифровых машин. "Советское радио", М., 1966.

49. Черкесов Г.Н. Надежность технических систем с временной избыточностью. "Советское радио", М., 1974.

50. Метц С., Вильсон Д. Диагностическая подсистема, обеспечивающая непрерывность работы отказоустойчивого многомашинного комплекса. "Электроника", т.55, № 24 (654), "Мир", М., 1982.

51. Жабин В.И., Лесюк В.Г. и др. Программное обеспечение многомашинных вычислительных комплексов ЕС ЭВМ. В сб.: Рациональное проектирование, создание и обслуживание вычислительных комплексовв АСУ для народного хозяйства. М., ЩЩТП, 1976, с.108-113.

52. Единая система электронных вычислительных машин. Операционная система. Контрольная точка повторный пуск. Руководство программиста. Ц51.804.006 Д6.

53. Надежность автоматизированных систем управления. Учебное пособие для вузов. Атовмян И.О. и др.; Под ред. Хетагурова Я.А. -М., "Высшая школа", 1979.

54. Единая система электронных вычислительных машин. Операционная система. Управление средствами комплексирования. Руководство системного программиста. Ц51.804.006.Д90.

55. ABC-система параллельного программирования для комплексов ЕС ЭВМ. Описание. МЭИ НИИ ЭВМ, Минск, 1981.

56. Щубинский Н.Б., Пивень E.H. Расчет надежности ЭВМ. Киев, "Техника", 1979.

57. Бутрименко A.B. Разработка и эксплуатация сетей ЭВМ "Финансы и статистика", М., 1981.

58. Хьгоз Дж., Мичтом Дж. Структурный подход к программированию. Пер. с англ. М., "Мир", 1980.

59. Уолкер Б.Дж., Блейк Я.Ф. Безопасность ЭВМ и организация их защиты. Пер. с англ. М., "Связь", 1980.

60. ГОСТ 13377-75. Надежность в технике. Термины и определения. М., Стандарты, 1975.

61. Майерс Г. Надежность программного обеспечения. Пер. с англ. под ред. Кауфмана В.Ш. М., "Мир", 1980.

62. Маслов А.Я., Татарский В.Ю. Повышение надежности РЭА. М., "Сов.радио", 1972.

63. Ладыгин И.И. Аппаратные средства обеспечения надежности ЭВМ. Учебное пособие по курсу "Надежность ЭВМ". М., 1979.

64. Липаев В.В. Надежность программного обеспечения АСУ. М., "Энергоиздат", 1981.

65. WeitzMcm С. Distributed Micro/Minicomputer Svstems . Prentice Halt , 1980.

66. Малые ЭВМ и их применение. По ред. Наумова Б.Н., М., "Статистика", 1980.

67. Строева Т.М. Асинхронные вычислительные сети и их применение в системах параллельного программирования. Диссертация на соискание уч.степени к.т.н. М., МЭИ, 1981.

68. Арефьев A.A., Кутепов В.П., Кораблин В.П. Язык граф-схем параллельных алгоритмов и его расширения. "Программирование", 1981, № 4.

69. Борздова Т.В., Вахрушева М.Б., Степов В.П., Петцояьд В. Полиязычная система параллельного программирования, основанная на одном семействе функциональных систем. "Программирование", 1984, & I.

70. Единая система электронных вычислительных машин. Операционная система. Макрокоманда супервизора. Руководство программиста. Ц51.804.006 Д5.

71. АВС-система параллельного программирования для комплексов ЕС ЭВМ. Программные средства восстановления. Общее описание. М.( МЭИ, 1983.

72. Единая система электронных вычислительных машин. Операционная система. Управление данными. Руководство программиста. Ц51.804.005 Д4.

73. Черноусов Е.А. Программирование задач обработки экономической информации. М., ^Финансы и статистика", 1982.

74. Ope 0. Теории графов. M., "Наука", главная редакции физико-математической литературы, 1980.

75. Дроздов Е.А., Комарницкий В.А., Пятибратов А.П. Электронные вычислительные машины Единой системы. М., "Машиностроение", 1981

76. Элементы параллельного программирования. Вальковский В.А., Котов В.Е., Марчук А.Г., Миренков H.H.; Под ред. Котова В.Е. М., "Радио и связь", 1983.

77. Гуляев В.А., Додонов А.Г., Пелехов С.П. Организация живучих вычислительных структур. Киев., "Наукова думка", 1982.