Содержание к диссертации
Стр.
ВВЕДЕНИЕ *"
Глава I. СИНХРОНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ В ВЫ
ЧИСЛИТЕЛЬНЫХ СИСТЕМАХ '/
I. Основные задачи синхронизации параллельных
процессов в вычислительных системах .... ^
2. Основные средства синхронизации параллель
ных процессов /*
3. Влияние конфликтов на производительность
многопроцессорной системы 2 Г
4. Способы уменьшения потерь, связанных с синх
ронизацией параллельных процессов 30
Выводы к первой главе 3*t
Глава 2. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОНФЛИКТОВ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ ПРИ РАВНОЦЕННЫХ
РЕСУРСАХ ЗЬ~
I. Математическая модель конфликтов в вычисли
тельной системе 31
2. Общие замечания относительно модели конфлик
тов в вычислительной системе ЪО
3. Оптимальное правило разрешения конфликтов в
многопроцессорной системе: случай одного не
делимого ресурса . W
4. Экспериментальная проверка эффективности оп
тимального правила для модели с одним недели
мым ресурсом . .96
— з —
5. Оптимальное взаимодействие между двумя парал
лельными процессами с несколькими критически
ми участками /t8
б. Аналитическая оценка эффективности оптимального правила разрешения конфликтов для двух процессов с несколькими критическими участками . ^SO
7. Оптимальное правило разрешения конфликтов между слабо связанными параллельными процессами . SZ
8. Экспериментальная проверка эффективности опти
мального правила для модели слабосвязанных
процессов .64
9. Возможные обобщения рассмотренных ситуаций , . _64
Выводы ко второй главе 6
Глава 3. ОПТИМАЛЬНЫЕ ПРАВИЛА РАЗРЕШЕНИЯ КОШЛИКТОВ С
УЧЕТОМ НЕРАВНОЦЕННОСТИ РЕСУРСОВ 2
I. Модель конфликтов в многопроцессорной системе
с учетом неравноценности ресурсов 0
Z. Понятие оптимальности в ^ и его свойства . ?з
3. Управляемые марковские цепи с векторными штра
фами ^
4. Свойства управляемых марковских цепей с век
торными штрафами &
5. Человеко-машинная процедура отыскивания опти
мальной стратегии при существовании функции по
лезности _83
б. Применение разработанного аппарата к задаче
разрешения конфликтов <5о
-* -
Выводы к третьей главе 91
Приложение к третьей главе 93
Глава 4. РЕАЛИЗАЦИЯ АЛГОРИТМОВ РАЗРЕШЕНИЯ КОНФЛИКТОВ
В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ 5/
I. Алгоритмы разрешения конфликтов в вычисли
тельных системах 33
2. Целесообразный табличный алгоритм разрешения
конфликтов и его модификации 40Z
3. Обоснование выбора алгоритма *%> для разре
шения конфликтов между параллельными процес
сами 10^
4. Оценка эффективности табличных алгоритмов на
имитационной модели 40?
5. Использование алгоритма разрешения конфликтов
в системах мультипрограммирования 444
б. Синхронизация параллельных процессов на
уровне передачи сообщений. Реализация
алгоритма разрешения конфликтов в вычисли
тельном комплексе ПС-3000 424
Выводы к четвертой главе 4ZZ
Приложение к четвертой главе 423
ЗАКЛЮЧЕНИЕ 43І
ЛИТЕРАТУРА 440
ПРИЛОЖЕНИЕ (Акты о внедрении) 4И
Введение к работе
Разработка и внедрение в народное хозяйство автоматизированных систем управления и систем обработки данных, широкое использование вычислительной техники для научных и инженерно-технических расчетов, создание вычислительных центров коллективного пользования и организация вычислительных сетей, появление и повсеместное распространение концепции банков данных, задачи ускорения научно-технического прогресса выдвинули повышенные требования к характеристикам, необходимых для эксплуатации вычислительных систем, таким как производительность, надежность и живучесть, адаптируемость к изменениям внешней среды системы и ее внутренней структуры.
Наиболее эффективно эти требования могут быть удовлетворены на пути максимального распространения многомашинных и мультипроцессорных вычислительных систем.
Тем самым одним из путей дальнейшего повышения быстродействия вычислительных средств является создание особых структур таких средств, позволяющих совмещать во времени выполнение нескольких вычислительных операций, что приводит к распараллеливанию вычислительного процесса и рациональной организации вычислений. Уже в настоящее время применение методов и средств параллельной обработки обеспечивает исключительно разнообразные возможности по обработке информации и управлению, включая достижение рекордных показателей производительности, надежности и живучести при относительно невысоких затратах.
Производство и применение параллельных вычислительных систем и практическое параллельное программирование постепенно становятся массовыми, увеличивается область применения параллельных вычислительных методов, растет число работ по теории параллельной
- 6 -обработки информации. По данным о Западной Европе и Северной Америке, там в начале 70-х годов работало около пяти тысяч параллельных систем, выпускаемых такими фирмами как BL/AROUQMS , IBM, СДС, ДЕС, HOtfYWlL и другими [i J .
Особенно перспективно применение параллельных методов обработки информации в таких областях как геология и геофизика, метеорология, расчет сложных, в первую очередь, энергетических систем, глобальное экономическое планирование и прогнозирование, а также управление технологическими процессами, обработка статистических данных, решение задач математической физики, применение методов Монте-Карло и т.д.
В настоящее время интенсивные исследования по разработке параллельных вычислительных средств и параллельному программированию ведутся и зарубежными фирмами и организациями в нашей стране в связи с созданием и развитием систем типа ЕС ЭВМ, ПС, "Эльбрус".
Появление систем параллельной обработки информации, допускающих распараллеливание вычислительного процесса, поставило перед разработчиками математического обеспечения этих систем ряд специфических проблем организации вычислительного процесса, в значительной степени обусловленных конкуренцией параллельно выполняющихся процессов и, как следствие, требованиями координации их действий.
Конкуренция процессов приводит к возникновению конфликтов между процессами. Под конфликтом в дальнейшем понимается ситуация, в которой более чем один из процессов претендует на неделимый ресурс системы, т.е. ресурс, доступный в каждый момент времени только одному из выполняющихся процессов. Здесь под ресурсом системы можно понимать физический, информационный или программный ресурс.
Примерами конфликтов служат одновременный запрос со сторо-
-*-
ны нескольких процессов на общую таблицу, устройство печати или нереентабельную программу. В каждом из этих случаев ресурс является неделимым, т.к. его одновременное использование более чем одним процессом может привести к непредсказуемым и более того, к нежелательным результатам в работе системы.
Отметим, что конфликты органически присущи логической природе параллельной обработки информации и не могут, следовательно, быть устранены на физическом уровне, например, при помощи дублирования ресурса.
Для устранения.конфликтов следует специальным образом организовать взаимодействие процессов - синхронизировать их действия по отношению к общим неделимым ресурсам.
В настоящее время известны различные аппаратно или программно реализуемые средства синхронизации параллельных процессов. Общим для них является то, что так или иначе они приостанавливают выполнение всех конфликтующих из-за некоторого ресурса процессов, кроме одного, который и получает ресурс. Таким образом, конфликты сопряжены с задержками выполняющихся процессов, что значительно снижает производительность системы 2?_і7 .
Выбор процесса из числа конфликтующих, который получает необходимый ресурс, как показано в диссертационной работе, существенно влияет на число конфликтов. Поэтому естественно поставить вопрос об оптимальном правиле разрешения конфликтов, минимизирующем их число на конечном интервале времени работы системы или их частоту в случае, когда время функционирования системы можно считать бесконечным. Нахождение оптимальных правил разрешения конфликтов и разработка реализующих их алгоритмов с тем, чтобы увеличить эффективную производительность вычислительных систем, являются основными целями диссертационной работы.
Выбор данной темы диссертационной работы инициирован разра-
боткой в Институте проблем управления параллельной вычислительной системы ПС-3000 . Полученные результаты ориентированы на применение в многопроцессорных вычислительных системах с перестраиваемой структурой со многими потоками команд и данных типа ПС.
Хотя в литературе отмечалась целесообразность принятия специальных мер для снижения частоты конфликтов и их продолжительности L$J , формализация этих вопросов, использованная в диссертационной работе, является оригинальной и полученные результаты не имеют аналогов.
Диссертация состоит из введения, четырех глав, заключения и приложения.
В первой главе содержится обзор, где обсуждаются основные задачи синхронизации параллельных процессов и существующие средства синхронизации, реализация которых служит решению этих задач. Эти средства не учитывают характеристик выполняющихся процессов, что является их существенным недостатком, и характера потребляемых ресурсов. Рассмотрен ряд работ, где исследовано влияние конфликтов на производительность многопроцессорных систем. Согласно приведенным в этих работах оценкам потери могут достигать в среднем 30% - 40%, в связи с чем задача об оптимальных правилах разрешения конфликтов, минимизирующих их число, приобретает практическую значимость.
Во второй главе приводится и обсуждается общая математическая постановка задачи о минимизации числа конфликтов в рамках формальной модели, соответствующей управляемой марковской цепи. Различаются два случая: случай равноценных ресурсов системы и случай, когда ресурсы системы неравноценны. В первом случае при некоторых предположениях с использованием аппарата динамического программирования получены явные формулировки оптимальных правил
- 9-разрешения конфликтов, основанные на учете характеристик поведения процессов в системе: частоты обращения процессов к неделимым ресурсам. Рассматриваются возможные обобщения полученных результатов с тем, чтобы учесть, в частности, время использования ресурсов процессами. Второй случай - неравноценности ресурсов -исследуется в третьей главе.
В третьей главе показано, что задача разрешения конфликтов при неравноценных ресурсах формально сводится к управляемой марковской цепи с векторными штрафами, т.е. требует аппарата многокритериальной оптимизации. В главе разработан соответствующий аппарат, позволяющий учесть относительную важность ресурсов системы, описываемую бинарным отношением /\ в многомерном пространстве штрафов за конфликт по каждому из ресурсов. Доказаны утверждения, гарантирующие существование R -оптимальных правил разрешения конфликтов; показано, как можно использовать известные методы для численного отыскания /\ -оптимальных правил и приведена человеко-машинная процедура оптимизации при существовании функции полезности разработчика системы. Ряд результатов второй главы перенесен на случай неравноценных ресурсов. В конце главы приводится пример, иллюстрирующий ш-существу методику учета относительной важности ресурсов при конкретном выборе R -оптимального правила разрешения конфликтов.
Реализация правил разрешения конфликтов является предметом четвертой главы. Основной характеристикой процессов, требующейся при реализации оптимальных правил разрешения конфликтов, является частота обращения процессов к неделимым ресурсам. Сбор нужной статистики в некоторых случаях может быть затруднителен. Поэтому в первой части главы ставится и решается задача разработки субоптимальных алгоритмов адаптивного типа - целесообразных алгоритмов разрешения конфликтов. С этой целью вводится класс табличных
—-/0-іалгоритмов разрешения конфликтов и предлагаются конкретные конст'
рукции алгоритмов из этого класса, обладающие, как показано в главе, свойством целесообразности. При этом, результаты, полученные в предыдущих главах, являются теоретической основой предложенных алгоритмов - они показывают какой параметр следует оценивать в процессе адаптации и как следует использовать эти оценки.
Во второй части четвертой главы приводится описание реализации одного из алгоритмов разрешения конфликтов в качестве алгоритма диспетчеризации задач в режиме мультипрограммирования для вычислительного комплекса М-7000, СМ-2, что повысило производительность комплекса в этом режиме на 10$ - 15%. На основе используемых в вычислительном комплексе ДС-3000 средств синхронизации параллельных процессов (ветвей) дано описание реализации алгоритма разрешения конфликтов в этом комплексе.
В приложении приводятся акты о внедрении алгоритмов разрешения конфликтов.
-a-
