Моделирование параллельных процессов

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

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

Виды параллельных процессов

Асинхронный параллельный процесс такой процесс, состояние которого не зависит от состояния другого параллельного процесса (ПП).

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

Синхронный ПП такой процесс, состояние которого зависит от состояния взаимодействующих с ним ПП.

Пример синхронного ПП: работа торговой организации и доставка товара со склада (нет товара нет торговли).

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

Методы описания параллельных процессов

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

Рассмотрим механизм реализации ПП на основе тран-зактов.

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

Событие, связанное с данным транзактом, может храниться в одном из следующих списков:

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

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

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

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

В списке текущих событий транзакты расположены в порядке убывания приоритета соответствующих событий; при равных приоритетах в порядке поступления в список.

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

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

Стратегическое планирование имитационного эксперимента

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

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

Идентификация факторов.

Выбор уровней факторов.

Под идентификацией факторов понимается их ранжирование по степени влияния на значение наблюдаемой переменной (показателя эффективности).

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

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

Выбор уровней факторов производится с учетом двух противоречивых требований:

уровни фактора должны перекрывать (заполнять) весь возможный диапазон его изменения;

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

Способы построения стратегического плана

Эксперимент, в котором реализуются всевозможные сочетания уровней факторов, называется полным факторным экспериментом (ПФЭ).

Общее число различных комбинаций уровней в ПФЭ для k-факторов можно вычислить следующим образом:

N = If Ї2h... lk,

где lk число уровней k-го фактора.

Если число уровней для всех факторов одинаково, то N = Lk (L число уровней).

Недостаток ПФЭ большие временные затраты на подготовку и проведение.

Например, если в модели отражены 3 фактора, влияющие на значение выбранного показателя эффективности, каждый из которых имеет 4 возможых уровня (значения), то план проведения ПФЭ будет включать 64 эксперимента (N = 43). Если при этом каждый из них длится хотя бы одну минуту (с учетом времени на изменение значений факторов), то на однократную реализацию ПФЭ потребуется более часа.

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

Если такие взаимодействия считают отсутствующими или их эффектом пренебрегают, проводят частичный факторный эксперимент (ЧФЭ).

Известны и применяются на практике различные варианты построения планов ЧФЭ. Мы рассмотрим только некоторые из них.

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

Латинский план (или «латинский квадрат») используется в том случае, когда проводится эксперимент с одним первичным фактором и несколькими вторичными. Суть такого планирования состоит в следующем. Если первичный фактор А имеет l уровней, то для каждого вторичного фактора также выбирается l уровней. Выбор комбинации уровней факторов выполняется на основе специальной процедуры, которую мы рассмотрим на примере.

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

В результате имеем план, требующий 4 х 4 = 16 прогонов, в отличие от ПФЭ, для которого нужно 43 = 64 прогона.

Эксперимент с изменением факторов по одному. Суть его состоит в том, что один из факторов «пробегает» все l уровней, а остальные n-1 факторов поддерживаются постоянными. Такой план обеспечивает исследование эффектов каждого фактора в отдельности. Он требует всего N = li+ І2+ + Із+... lkпрогонов.

Для рассмотренного выше примера (3 фактора, имеющие по 4 уровня) N = 4 + 4 + 4 = 12.

Еще раз подчеркнем, что такой план применим (как и любой ЧФЭ) только при отсутствии взаимодействия между факторами.

4. Дробный факторный эксперимент. Каждый фактор имеет два уровня нижний и верхний, поэтому общее число вариантов эксперимента N = 2k, где k число факторов. Матрицы планов для k = 2 и k = 3 приведены ниже.

Тактическое планирование имитационного эксперимента

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

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

Формирование простой случайной выборки

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

Различие понятий «достоверный результат» и «точный результат» можно пояснить с помощью приведенного ниже рисунка. На рисунке использованы следующие обозначения:

у, уо, истинное и ошибочное значения наблюдаемой переменной у;

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

•вида распределения наблюдаемой переменной у (напомним, при статистическом эксперименте она является случайной величиной);

коррелированности между собой элементов выборки;

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

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

уровней факторов, выбранного на этапе стратегического планирования эксперимента. Такой подход получил название «формирование простой случайной выборки» (ПСВ). Другими словами, при использовании ПСВ каждый «пункт» стратегического плана просто выполняется повторно определенное число раз. При таком подходе общее число прогонов модели, необходимое для

достижения цели моделирования, равно произведению Nc х №

(Nc число сочетаний уровней факторов по стратегическому

j г т г — г J

плану; NT число прогонов модели для каждого сочетания, вычисленное при тактическом планировании).

Например, если для полного факторного эксперимента Nc = 64, а для обеспечения требуемой точности оценок NT должно быть равно 20, то общее число прогонов модели -1280. Требуемое время для проведения всех испытаний (по минуте на каждое) более 20 часов. То есть «модельер» должен трудиться почти сутки без сна и отдыха. Поэтому даже при использовании ПСВ до начала испытаний необходимо определить тот минимальный объем выборки, который обеспечит требуемую точность результатов.

Если случайные значения наблюдаемой переменной не коррелированы и их распределение не изменяется от прогона к прогону, то выборочное среднее можно считать нормально распределенным. В этом случае число прогонов NT, необходимое для того чтобы истинное среднее наблюдаемой переменной лежало в интервале у ± b с вероятностью (1 а), определяется следующим образом:

Z2 • Dy

N =

где Z значение нормированного нормального распределения, которое определяется по справочной таблице при заданном уровне значимости а /2;

Dy дисперсия;

b доверительный интервал.

Если требуемое значение дисперсии Dy до начала эксперимента неизвестно, целесообразно выполнить пробную серию из L прогонов и вычислить на ее основе выборочную дисперсию, значение которой подставляют в вышеприведенную формулу и получают предварительную оценку числа прогонов модели Nt, затем выполняют оставшиеся Nt L прогонов, периодически уточняя оценку и число прогонов NT.