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

РГ6 од

1 о ЧАГ1 ^юо смиская академия наук

институт проблем кибернетики

На правах рукописи УДК 681.324.001.51

ДИЛЬМАН Марк Израилевич

РАЗРАБОТКА И ИССЛЕДОВАНИЕ КОНСЕРВАТИВНЫХ АЛГОРИТМОВ СИНХРОНИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ПРОЦЕССОВ ПРИ РАСПРЕДЕЛЕННОМ МОДЕЛИРОВАНИИ ДИСКРЕТНЫХ СИСТЕМ НА ТРАНСПЬЮТЕРНЫХ СЕТЯХ

Специальность 05.13.16 - применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

МОСКВА 1993

Работа выполнена в Научном совете по комплексной проблеме "Кибернетика" Российской Академии наук.

Научный руководитель: доктор технических наук, профессор Ю.Г. ААМВВ

Официальные оппоненты: доктор физико-математических наук А.Н. ТОМИАМН кандидат физико-математических наук Н.В. МАКАРОВ-ЗЕМЛЯНСКИИ

Ведущая организация: Вычислительный центр Российской Академии наук

Защита состоится "_"_ 1993 г. в___часов на

заседании специализированного совета Д.003.78.01 ИПК РАН по адресу: 117312 Москва, ул. Вавилова, 37.

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разослан

Ученый секретарь специализированного совета

к.ф.-м.н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

- з -

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

Апробация работы. Основные результаты работы докладывались на семинаре отдела базового программного обеспечения Института проблем кибернетики РАН (1989-93гг.), на семинаре отдела вычислительной механики Научно-исследовательского института системных исследований РАН (1992г.), 1-ой конференции "Транспьютерные системы и их применение" (г. Звенигород, 1991г.). Тезисы докладов по результатам работы приняты для публикации в материалах международных конференций PACTA*92 (Испания) и ТАРА-92 (Австралия).

Публикации. Представляемые на защиту результаты опубликованы в работах [1-3].

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и трех приложений. Ее общий объем 125 страниц, в том числе, 53 рисунка, 2 таблицы, список литературы из 74 наименований и 2 справки о внедрении.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы, определяются основные направления исследования и формулируется цель работы. Приводится краткое содержание диссертационной работы.

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

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

В имитационных моделях можно выделить три типа параллелизма.

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

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

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

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

Использование параллелизма на модельном уровне предполагает формализованное представление исследуемой системы как совокупности активных объектов, взаимодействующих между собой путем обмена сообщениями по связывающим их каналам. Будем называть указанные объекты физическими процессами (ФП), а их программную реализацию в модели - логическими процессами (ЛП).

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

которых изменяется состояние системы, т.е. совершается событие.

Итак, после декомпозиции имеем представление системы в виде множества физических процессов: Б = { Р4, Р2, ... Рп }. Каждый элемент этого множества обозначает выполнение последовательности активностей: Р. = (а. „ ,а.„,... ,а ), где 1<1<п. Завершение актив-

V 11 12 ът.

V

ности а^. (1<^<т.) приводит к совершению события е... Каждое событие происходит в некоторый момент времени и относится к определенному физическому процессу, т.е. имеет две координаты - временную и пространственную: е..= (1;. , Р1). Таким образом, результатом выполнения физического процесса р.является упорядоченная последовательность событий (е.,,е.„, ... , е. ), где 1;. <1;. < ... <1;. .

VI 12 1ТП. VI к ¿ тп.

V I

Если событие е.. может вызвать возникновение некоторой активности в физическом процессе Рк то между соответствующими ЛП в

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

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

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

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

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

Таким образом, продвижение модельного времени не характеризуется абсолютностью, присущей реальному (ньютоновскому) времени, а является относте'лъныл. Иными словами, ЛП могут забегать вперед или отставать относительно друг друга в модельном времени.

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

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

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

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

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

распределенных моделей.

В разделе 2.1 анализируются возможности для распараллеливания процесса моделирования при использовании консервативных алгоритмов синхронизации.

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

Если обозначить модельное время события е через t(e), а тот факт, что данное событие запланировано для выполнения в i-м ЛП -выражением е б то событие е( е ЬР^ находится в причинно-

следственной зависимости от события е2 £ (I^d и t(et)>t(e2)) тогда и только тогда, когда в результате моделирования е2 может быть запланировано событие в'г 6 такое что t(e£)<t(e ).

Для определения безопасных событий в процессе распределенного моделирования каждым ЛП должна периодически вычисляться верхняя граница безопасного врелени o£(i). На каждом шаге моделирования ЛП может имитировать выполнение только тех событий, для которых t(e)«i(i).

Если допустить, что t(ep-t(e2)>0, т.е. событие, запланированное в i-м ЛП, может в результате своего выполнения мгновенно воздействовать на состояние j-ro ЛП, то безопасными в распределенной модели могут считаться только события с наименьшей временной координатой. В этом случае параллельное выполнение модели может выродиться в последовательное.

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

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

вания (СМО) для каждого обслуживающего прибора можно определить минимальное время обслуживания, не равное нулю. Длина указанного интервала времени называется просмотрел вперед, поскольку для любого дискретного значения локального времени ЛП можно гарантировать отсутствие в будущем сообщений на выходах соответствующего ФП в течении времени просмотра вперед. Обозначим просмотр вперед 1-го ЛП через 1(1).

Кроме просмотра вперед, ненулевым может быть минимальное время распространения сообщения между выходом и входом ЕР. , которое обозначим через p(i,j). Сумму d(i,J)=l(i)+p(l,J) назовем расстояние* между ы^ и LP.. Вследствие наличия ненулевых расстояний между Ж каждый из них как бы обладает определенной зоной нечувствительности по входам, что и создает возможность параллельной имитации событий с различными временными координатами. Расстояни». между ЛП, как правило, не изменяются в процессе моделирования.

И наконец, третьим фактором инерционности является временная задержка q. между поступлением сообщения на вход ФП и началом его обработки. Например, в СМО - это время нахождения заявки в очереди к обслуживающему прибору. Эта величина изменяется в процессе моделирования. Обозначим минимальное значение модельного времени, когда 1-й ФП в состоянии начать обработку очередного сообщения, через lst(I) и назовем его локальным, лодёлъныл временем 1S., поскольку состояние моделируемого ФП известно вплоть до этого момента времени.

По способу вычисления ci(l) консервативные алгоритмы можно разделить на синхронные и асинхронные. В синхронных алгоритмах на каждом. шаге моделирования вначале все ЛП одновременно вычисляют для себя значения ot(i) посредством так называемого предварительного моделирования, а затем моделируют выявленные безопасные события, после чего этот процесс повторяется. В течение предварительного моделирования вместо сообщений о событиях между ЛП распространяются оценки времени возможных возникновений событий. Для того чтобы эти оценки были корректными, необходимо обеспечить, чтобы переход каждого ЛП от предварительного моделирования к непосредственно моделированию и наоборот осуществлялся только после того, как все остальные ЛП вычислят значения с£(1), т.е. синхронно с другими ЛП. В асинхронных консервативных алгоритмах безопасное время ct(l) определяется каждым ЛП непосредственно в

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

В разделе 2.2 рассматриваются вопросы отображения синхронных алгоритмов, предложенных Б.Д.Любачевским, на архитектуру транспьютерных сетей.

Основное отличие синхронных алгоритмов друг от друга заключается в методах определения величины безопасного времени.

Если значения q^o для всех i, или ими можно пренебречь, то ct(i) может быть вычислено по следующей формуле :

ct(i) = mjn {min [т., [т. + d(i,J)]] + d(J,i)| . (1)

Здесь - временная метка самого раннего события, запланированного в списке событий ev.list(i) 1-го ЛП:

m _ Г min t(e), если ev.list(i) * 0 i X + аз , если ev.list(i) = 0 ,

a d(i,J) - длина кратчайшего пути из nv в ЬР., т.е. такого пути,

при следовании по которому сумма расстояний между соседними ЛП

будет минимальна. Если пути из ър. в ьр. не существует, то

d(i,d) = + со .

Формула (1) учитывает две возможности поступления сообщения о событии на вход ър.: i) поступление сообщения непосредственно от iiP. с временной координатой т. + d(j,i) и 2) поступление от LP. сообщения-отклика на сообщение, поступившее от ьр., с временной координатой + d(i,3) + d(j,i).

Заметим, что для каждого ЛП существует кратчайший элементарный контур с фиксированной длиной dm-n(i)= m^n jd (i, J) + d(j,i)|,

которая может быть вычислена до начала моделирования. Поэтому (1) можно переписать следующим образом:

d(l) = min {(га^п |V + dU.i)]], (т. + dmn(i)]} . (2)

Формула (2) требует по сравнению с формулой (1) вдвое меньше операций сложения и в п раз меньше операций сравнения, где п -количество ЛП.

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

|t(e.) - t(0j)| < в, vi.J (3)

в этом случае каждому ьр. необходимо получить значения т. только от тех LP., расстояние до которых не превосходит, в, т.е. оценка ct(i) производится каждым ЛП для сферы s(i,B) с центром в LP. и радиусом в. Чтобы не нарушалось соотношение (Э), ЛП на каждом шаге моделирования должен имитировать только те безопасные события, временная координата которых t(e) < tmin + в, где tmin = min(ov).

Для физических систем, в которых q^o и пренебрежение ими приводит к неэффективному моделированию, постановка задачи предварительного моделирования изменяется. В данном случае время прохождения сообщения от ы^ до LP. зависит не только от величины d(i,j), но и от значений q всех ЛП, находящихся на пути следования сообщения. Значения qt изменяются в процессе моделирования, поэтому заранее выделить фиксированный путь между двумя Ж, при следовании по которому сообщение получит минимальное приращение временной метки, уже нельзя. Такие пути для каждой пары ЛП должны каждый раз переопределяться на этапе предварительного моделирования с учетом текущих значений q.. Сформулируем задачу следующим образом.

Пусть имеется направленный граф, вершины которого соответствуют ЛП, а дуги - каналам связи между ними. Припишем вершине ер вес LST(i), а дуге (i,J) - вес d(i,j). Поместим в каждую вершину LP. маркер с атрибутом и зададим следующие правила перемещения маркеров по графу:

„, I) при выходе из вершины ЬР1 атрибуту маркера тк присваивается зачение, равное шах |шк, LST(i)j ;

2) при перемещении по дуге (i,j) к атрибуту маркера прибавляется вес этой дуги d(i,j).

Необходимо для каждой вершины графа определить минимальное значение атрибута, с которым произвольный маркер может попасть в данную вершину. Это и будут искомые значения c£(i).

На рис. I приведен алгоритм нахождения сС(i), ориентированный на распределенные вычислительные системы типа транспьютерных с двухточечными связями между процессорами.

Этот алгоритм одновременно выполняется на этапе предварительного моделирования всеми ЛП. Обмены информацией между ЛП осуществляются на уровне ближайших соседей. На первом шаге производится оценка ct(i) для окрестности N(1,1) единичного радиуса, на втором - для N(1,2) и т.д. до тех пор, пока радиус окрестности R

не станет равным м - максимальной длине элементарного пути в графе. Здесь и и м измеряются количеством дуг, р(1) и 7(1) -вспомогательные переменные.

J * » * '

1Р 7(1) < оЦ1) ТНЕГ1 о£(±) 7(1)

|3(1) <- 7(1)

й «- И + 1

При больших значениях м, когда представленный на рис. I алгоритм требует значительного времени для своего выполнения, целесообразно так же, как и в предыдущем случае, ограничить вычисления для каждого ЛП сферой Б(1,в). При зтом число итераций алгоритма, необходимых для получения оценки о£(1),будет равно т - максимальной

для данного графа длине элементарного пути ЬР ЬР. ->...-*

о 1

■» ЬР. -» ЬР , для которого <1(1Л,1. ) + ... + (1(1 ) < в.

V , I А О 1 т-1 т

тп-1 т

Впервые подобный алгоритм предварительного моделирования был предложен в предположении, что переменные (3(1) и 1£Ш(1) доступны для чтения всеми ЛП системы. В таком случае для корректной интерпретации общих переменных необходима синхронизация ЛП до и после обновления значений р(1) на каждой итерации приведенного алгоритма. При транспьютерной реализации данного алгоритма, когда все переменные являются локальными, а их значения передаются по каналам с синхронной организацией ввода/вывода, корректность принимаемых данных обеспечивается автоматически, однако при этом существует возможность возникновения тупиковой ситуации.

Для исключения тупиковых ситуаций в процессе моделирования под управлением синхронных алгоритмов достаточно соблюдения следующих условий при обмене данными между Ж:

I) каждой операции ввода данных должен предшествовать вывод

Рис. I

аналогичных данных;

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

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

proc syncr.lp (ПСНАК OF MESSAGE input,output) par seq

... инициализация

— основной ищи.

while not признак.завершения

seq

— этап предварительного моделирования ... вычисление t .

min

... оценка et(±)

— этап моделирования ... цикл моделирования ... цикл вывода

... цикл ввода ... завершение работы ЛП

... буферы входных каналов Рис." 2

Этап моделирования состоит из трех циклов. На первом из них ЛП имитирует выполнение безопасных событий, т.е. тех событий из списка ev.list(i), временная координата которых t(e) удовлетворяет условиям: t(е) < ci(i) и t(е) < t . + в. В результате имитации

mm *

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

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

этапов, составляющих основной цикл. Причем в предшествующих работах делается вывод, что в процессе моделирования необходима так называемая барьерная синхронизация, которая предполагает, что "перешагнуть" через операцию синхронизации можно лишь после завершения всеми ЛП всех операций, предшествующих синхронизации. Такой тип синхронизации требует при наличии общей памяти O(log п) времени, где п - количество ЛП в модели.

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

Выполненный в работе детальный анализ основных фрагментов синхронного алгоритма позволил сделать вывод, что при их транспьютерной реализации существует ряд возможностей для значительного сокращения количества и уменьшения временной сложности операций по синхронизации. При рациональном использовании этих возможностей синхронизация ЛП может быть осуществлена при помощи механизма, который в литературе называется d-синхронизатором и заключается в том, что по завершении выполнения фрагмента алгоритма, требующего после себя синхронизацию, Ж посылает сообщение об этом ближайшим соседям по своим выходным каналам, затем ждет поступления аналогичных сообщений по всем своим входным каналам, после чего переходит к выполнению следующего фрагмента алгоритма. Такая локальная синхронизация в случае разреженного графа модели (когда число дуг, инцидентных каждой вершине, не зависит от п) характеризуется временной сложностью 0(1) при коммуникационной сложности 0(п). Причем, как показано в данном разделе диссертации, для корректного выполнения алгоритма достаточно однократной синхронизации всех Ж на каждой итерации алгоритма.

Таким образом, в отличие от алгоритма, рассматриваемого в работе Любачевского, каждая итерация основного цикла которого требует выполнения как минимум 2ш + 3 операций барьерной синхронизации с временной сложностью о(log п), описанные в диссертационной

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

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

В разделе 2.3. приведены асимптотические оценки эффективности синхронных консервативных алгоритмов. На основании сделанных предположений о характеристиках моделируемой системы показано, что коэффициент ускорения при переходе к распределенному моделированию на транспьютерных сетях будет порядка о(n/D), где п - количество ЛП в модели, a D - диаметр графа, задающего топологию связей между ними.

В разделе 2.4. предлагаются две модификации базовой версии синхронного алгоритма.

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

В первую очередь рассмотрим упрощенный вариант синхронного алгоритма, полученный в результате исключения из его базовой версии операции вычисления et (i), связанной с обменом данными между ЛП. Такая модификация алгоритма допустима при условии, что выявление безопасных событий в процессе моделирования производится на основании следующего утверждения, не требующего доказательства: все события, временные координаты которых попадают в интервал Tt . ; t . + d . Г , где d . = min d(i,J) - минимальное расстоя-

L mm min mm[_ min i»J

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

перелещзщееся временное окно (moving time window). В связи с этим алгоритмы, реализующие данный подход, называются в работе алгоритмами типа MTW.

В процессе моделирования под управлением алгоритмов типа MTW на каждой итерации осуществляется имитация событий из "временного окна" фиксированной ширины dmin, границы которого всегда совпадают для всех ЛП модели. Нижней границей "временного окна" является текущее значение tmi , которое при переходе к каждой последующей итерации алгоритма увеличивается как минимум на величину d t . Вероятность того, что приращение t будет незначительно отличаться от dmin определяется плотностью событий в модельном времени, законами распределения и параметрами случайных величин, задающих приращения временных координат при имитации событий и будет расти с увеличением количества Ж в модели. Если указанная вероятность достаточно велика, то имеет смысл сдвигать "временное окно" при переходе к следующей итерации с фиксированным шагом dmin, исключив необходимость глобальной операции по определению t t . При этом этап предварительного моделирования сводится к независимому выполнению каждым Ж всего лишь одной операции: cC(i) «- ct(i) + dmin. (При инициализации модели всем c((i) присваиваются значения 0.) Такое упрощение приводит к новому классу алгоритмов, которые будем называть алгоритмами типа TS.

Исключение из алгоритма MTW "барьерной" операции определения t t оставляет Ж возможности только для локальной синхронизации с ближайшими соседями при вводе сообщений о планируемых событиях. Локальная синхронизация не гарантирует одновременное выполнение всеми Ж модели одной и той же итерации алгоритма. Легко доказать, что, если кратчайший путь между некоторыми ы^ и ЕР^ содержит к дуг, то при выполнении алгоритма типа TS ы\ может опережать ер. максимум на к итераций. Казалось бы это должно привести к нарушению корректного порядка моделирования событий, поскольку EPi может получить от ЕР. сообщение о событии, относящемся к его модельному прошлому. На самом деле возможность возникновения такой ситуации полностью исключается. Действительно, вследствие того, что на каждой итерации моделируются события из "временного окна" шириной dmin, отрыв EPv от ЕР. в модельном времени не может быть больше величины kd . равной, с другой стороны, минимальному приращению временной метки сообщения о событии при следовании по пути от ер. до ЕРГ

В отличие от алгоритмов типа эта и МТУ/, алгоритмы типа тэ не являются синхронными в полном смысле этого слова, они занимают промежуточное положение между синхронными и асинхронными алгоритмами, которые рассматриваются в разделе 2.5.

Все асинхронные консервативные алгоритмы основаны на соблюдении в процессе моделирования следующих правил:

1. Продвижение вперед модельного времени ЛП осуществляется только после считывания временных меток сообщений из всех входных каналов. Если какие-либо входные каналы пусты, то ЛП ждет поступления сообщений по этим каналам. Показания локальных часов Ж устанавливаются равными значению минимальной из считанных временных меток.

2. На каждом шаге моделирования ЬР. имитирует выполнение только тех запланированных событий, временные координаты которых не превосходят текущих показаний локальных часов ЛП - с1оск(1).

3. Выходное сообщение т^эД,,]) с временной меткой ts, порожденное в результате имитации некоторого события в ьр1 и предназначенное ЬР., направляется в соответствующий канал только тогда, когда

< с1оск(1) + ¿(1,3) • (4)

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

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

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

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

Нуль-сообщение (НС) не содержит информации о каком-либо

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

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

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

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

В разделе 2.6 описана программная реализация консервативных алгоритмов, выполненная на языке Occam 2, и изложены принципы построения библиотеки универсальных программных модулей, позволяющей при минимальных затратах времени конструировать и исследовать распределенные модели дискретных систем. Полный текст основных модулей библиотеки приведен в Приложении I.

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

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

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

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

В разделе 3.4 выделены управляемые параметры ИРН, влияние которых на производительность представляет интерес для исследования. К их числу относятся:

1) закон распределения величины Дt - приращения модельного времени при имитации события;

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

3) вероятности, определящие последствия имитации события;

4) дисциплина маршрутизации выходных сообщений;

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

6) параметры, определяющие режимы функционирования моделируемой системы (замкнутый/разомкнутый, с очередями или без очередей);

7) топология моделируемой системы

8) радиус сферы, в пределах которой производится оценка верхней границы безопасного времени в алгоритмах типа буы и

9) плотность событий в модельном времени.

В разделе 3.5. перечисляются выходные данные экспериментов.

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

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

- среднее количество нуль-сообщений, приходящихся на каждое обрабатываемое сообщение о событии;

- среднее количество событий, имитируемых ЛП на одном цикле моделирования;

- среднее время, затрачиваемое ЛП на ожидание завершения цикла моделирования соседними ЛП, и некоторые другие величины.

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

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

В разделе 4.1. рассматриваются основные фактоге, определяющие время выполнения распределенных моделей.

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

- время, расходуемое на выполнение операций по синхронизации

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

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

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

Учет перечисленных факторов позволяет позволяет объяснить большинство закономерностей, выявленных в ходе экспериментальных исследований.

В разделах 4.2-4.8 приводятся экспериментальные данные о влиянии параметров ИРН на производительность исследуемых алгоритмов распределенного моделирования и сравнительный анализ их эффективности.

В качестве примера на рисунках 3-6 приведены графики зависимости коэффициента ускорения (К) для четырех исследуемых алгоритмов от коэффициента просмотра вперед (lar), количества априорно планируемых событий (IMP), средней длительности процесса имитации события (d) и топологии моделируемой системы соответственно.

Эксперименты выполнялись на сети из шести транспьютеров, на каждом из которых моделировался один ФП. Были исследованы следующие три топологии связей между ФП в моделируемой системе: ring-1 - кольцо с возможностью передачи сообщений только в одном направлении; ring-2 - кольцо с двунаправленными связями между ФП; ring-3 - кольцо с двунаправленными связями между соседними ФП, дополненное диаметральными двунаправленными связями.

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

ВО

d = 5 ms, IMP = 5

¡ ¡ 1 ¡ ¡ 1

-в-ASYNSYN -w-MTW -«-TS

Á И

p ^ 1

во

70

.60

SO-

40-

30"

0.1

0.2

0.3

0.4

0.5 LAR

0.в

0.7

0.8

0.9

Pua 3

LAR = 0.5, d = 1 ms

^asyn^syn шьтг ¡mis Pua 4

100 90 80 N 70 ¡< 60 50 40 30

LAR = 0.5, IMP = 10

0 0.5 1

1.5

2 2.5 3 d, ms

3.5

c:—

/ i

-e-ASYNSYN -*-lfnr -"-TS

/

i ¡ i i ! ! 1 ! ! !

4.5

Puc. 5

LAR = 0.5, d = 1 ms, IMP = 5

RING—1

RING-2

RING-3

ES8 ASYN SYN

1ÍTW f"H~l TS

Puc. 6

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

6. В ходе экспериментальных исследований получены сравнительные оценки эффективности четырех алгоритмов распределенного моделирования и установлены основные причины различий в характере зависимости производительности исследуемых алгоритмов от значений параметров ИРН. Знание указанных причин позволяет распространить полученные результаты на те области значений параметров ИРН, которые остались за рамками экспериментальных исследований.

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

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

8. С использованием разработанного алгоритмического и программного обеспечения реализована сетевая распределенная модель транспортных потоков, исследование которой подтвердило достоверность результатов, полученных в экспериментах с применением ИРН.

По теые диссертации опубликованы следующие работы:

1. Дильман М.И. Вопросы распределенного моделирования систем на транспьютерных сетях. - М., 1991, - 40с. (Препринт/НСК АН СССР).

2. Дильман М.И. Имитационное моделирование дискретных систем на транспьютерных сетях. - Первая конференция "Транспьютерные системы и их применение", Звенигород, 1991. - с.60.

3. Дильман М.И. Имитационное моделирование дискретных систем на транспьютерных сетях под управлением консервативных алгоритмов синхронизации. "Вопросы кибернетики.", М.:1993, стр. 5-24.

М.И. Дильман

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

Подписано в печать 19.04.93г. Формат бумаги 60 х 84 1/16 Тираж 100 экз. Заказ 33. Бесплатно.

Отпечатано на ротапринтах ВЦ РАН. 117967, Москва, ул Вавилова 40.