МИНИСТЕРСТВО ОБРАЗОВАНИЯРЕСПУБЛИКИ БЕЛАРУСЬ
«Гомельскийгосударственный университет имени Франциска Скорины»
Математический факультет
Кафедра МПУ
Курсовая работа
«Использованиеметода ветвей и границ при адаптации рабочей нагрузки к параметрамвычислительного процесса»
Гомель 2002
Реферат
Курсоваяработа 25 страниц, 10 источников, 5 рисунков, 1 таблица
Ключевые слова:ИМИТАЦИОННАЯ МОДЕЛЬ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ,ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА, ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС, ПРОГРАММНЫЙ МОДУЛЬ, ГРАФ,МАТРИЦА ВЕРОЯТНОСТЕЙ, МЕТОД МОНТЕ-КАРЛО
Объектисследования: имитационная модель процесса обработки данных.
Предметисследования: применение метода ветвей и границ в процессе обработки данных.
Цель курсовойработы: найти рациональный порядок следования запросов, который обеспечитмаксимальный критерий эффективности использования компонентов вычислительногопроцесса в вычислительной системе.
Задачамикурсовой работы являются: изучить метод ветвей и границ и применить его кмодели машинного моделирования, позволяющей найти такой порядок следованиязапросов, который обеспечит максимально быстрое выполнение вычислительногопроцесса.
Выводы: спомощью метода ветвей и границ удаётся построить такой порядок выполнениязапросов, при котором время их обслуживания будет минимальным.
Содержание
Введение
1. Марковские процессы
2. Метод Монте-Карло
2.1 Общая характеристикаметода Монте-Карло
2.2 Точность метода
3. Метод ветвей и границ
4. Построение оптимальнойпоследовательности заданий на обработку в узле вычислительной системы
4.1 Формализациявычислительного процесса и рабочей нагрузки
4.2 Особенностиорганизации имитационного эксперимента
4.3 Модификацияпоследовательности решения задач в пакете по методу ветвей и границ
Заключение
Список источников
Введение
Выборомрабочей нагрузки под вычислительный процесс в вычислительных системахзанимались многие исследователи. Однако все они оперировали интегральнымихарактеристиками решения задач, не рассматривая при этом динамику использованияресурсов вычислительных систем во времени выполнения задач и пространствепараметров. Такой подход иногда приводил к существенной ошибке в оценкепроизводительности системы в условиях, когда задания сильно конкурируют заресурсы вычислительной системы. Это обстоятельство определило актуальностьзадачи адаптации рабочей нагрузки под возможности вычислительных систем вусловиях, когда технология их обработки рассматривается на высоком уровнедетализации. В данной работе будем исходить из следующих допущений:
1. Каждоезадание вероятностным образом использует различные ресурсы вычислительногопроцесса, а сам вероятностный процесс является полумарковским.
2. Исследователюизвестны заранее характеристики полумарковского процесса, реализуемого каждымиз заданий, или же имеются инструментальные средства для измерения этиххарактеристик.
3. Потокзаданий постоянно используется на данной вычислительной системе и имеетпрактически неизменную структуру запросов ресурсов вычислительной системы, чтопозволяет говорить о принципиальной возможности нахождения такого порядказаданий, который является оптимальным при заданном составе ресурсов вычислительнойсистемы.
1.Марковские процессы
Пусть имеетсясистема, которая в произвольный момент времени tk может находиться в одномиз состояний si, />, с вероятностью />. Через некоторыепромежутки времени система переходит из одного состояния в другое. Каждый такойпереход называется шагом процесса. Случайный процесс, протекающий в системе S, называется марковским,если для произвольного момента времени /> вероятностьлюбого состояния системы в будущем (при />) зависит только от еёсостояния в настоящем (при />) и не зависит от того,когда и каким образом система пришла в это состояние. Различают марковскиепроцессы с дискретными состояниями и дискретным временем (стохастическаяпоследовательность, или дискретная цепь Маркова) и марковские процессы сдискретным состоянием и непрерывным временем (непрерывная цепь Маркова). Обатипа цепей могут быть однородными и неоднородными.
Длядискретной цепи Маркова смены состояний процесса происходят в дискретныемоменты времени ti с шагом />.Состояние системы si в момент tk необходимо характеризовать условнымивероятностями /> (1) того, чтосистема за один шаг перейдёт в какое-либо состояние sj при условии, что вмомент tk-1 она находилась в состоянии si. Вероятности /> (1) =/> являются основнымихарактеристиками марковской цепи. Они называются вероятностями перехода или переходнымивероятностями. Поскольку система может находиться в одном из состояний, то длякаждого момента времени tr необходимо задать n2 вероятностей перехода />
/>.
Эта матрицаназывается матрицей переходных вероятностей или матрицей переходов. Для неёсправедливо выражение />, />. Матрица переходныхвероятностей обязательно является квадратной матрицей с неотрицательнымиэлементами, образующими по строкам единичную сумму; матрица такого роданазывается стохастической. В случае, когда вероятности перехода не зависят отвремени, а зависят только от величины τ и не изменяются при сдвиге вдольвременной оси, цепь Маркова называется однородной. Для такой цепи задаётсяматрица
/>.
Вероятностиперехода представляют собой важнейшие характеристики любой марковской цепи.Однако они по определению являются условными, и поэтому знание матрицыпереходных вероятностей не полностью определяет цепь Маркова. Если отнестиматрицу переходов к первому шагу, определяющему начало работы системы, то дляисключения условностей необходимо задать ещё вероятности начальных состояний.
Вероятностиначальных состояний />, />,…, /> являются безусловнымивероятностями и образуют матрицу-строку />,сумма элементов которой по условию нормировки должна быть равна 1.
Матрицапереходов даёт исчерпывающее представление о вероятностях возможных переходовза один шаг. Естественно возникает вопрос: как рассчитать вероятности того, чтосистема, находящаяся в данный момент в состоянии si, переходит в состояние sj за r шагов. Матрица переходовза r шагов P(r) вычисляется как r-я степень матрицыперехода за один шаг P(r)=pr. Безусловные вероятности системы на r-м шаге определяются извыражений: /> />.
Различаютцепи эргодические и поглощающие. Это различие основано на классификациисостояний. Состояние si называется невозвратным, если существуют такиесостояния sj (/>) и число шагов r, что pij(r)>0, но pij(q)=0 для всех q. Все остальные состоянияназываются возвратными. Таким образом, из невозвратного состояния всегда можнос положительной вероятностью и за какое-либо число шагов перейти в некотороедругое состояние. В то же время вернуться из этого состояния в первоначальноеневозможно.
Если выбратьтакие состояния si и sj, что для них при некоторых r и q выполняется неравенство pij(r)>0, pji(r)>0, то они называютсясообщающимися. Если sj сообщается с si, а si с sk, то sj сообщается с sk. Это обстоятельствопозволяет разделить множество возвратных состояний на классы (подмножества)сообщающихся состояний. Состояния, принадлежащие к различным классам, несообщаются между собой. Если множество возвратных состояний состоит из одногокласса, то оно называется эргодическим. Существуют так называемые поглощающиесостояния, например если si – поглощающее состояние, то pii=1, pij=0. Цепи Маркова, несодержащие возвратные множества и образующие эргодическое множество, называютсяэргодическими. Свойства и методы расчетов параметров поглощающих и эргодическихцепей различны.
Длянепрерывной цепи Маркова вводится понятие плотности вероятности перехода(интенсивность потока событий) как предела отношения вероятности переходасистемы за время Δt из состояния i в состояние j к длине промежутка:
/> (/>).
Если λij не зависит от t, то есть от того, вкакой момент начинается Δt, то непрерывная цепь Маркова называется однородной, впротивном случае она называется неоднородной.
Однороднаяцепь Маркова характеризуется тем, что все потоки, переводящие систему из одногосостояния в другое, являются простейшими, то есть стационарными пуассоновскимипотоками. При этом время непрерывного пребывания цепи в каждом состояниираспределено по экспоненциальному закону.
Длянеоднородной цепи промежутки времени между соседними событиями распределены непо показательному закону.
Еслинепрерывная цепь Маркова является однородной и между любыми её двумясостояниями существует маршрут, то она эргодичная. Кроме того, если вероятностисостояний системы pj не зависят от времени наблюдения системы и совпадают с еёначальными вероятностями состояний /> истационарными вероятностями, т.е. />, торежим цепи является стационарным.
Отметим, чтопонятия «стационарность управляющих потоков» и «стационарный режим» совершенноразные и из первого не следует второе. Таким образом, однородная непрерывнаяцепь Маркова определяется начальным распределением вероятностей />, матрицей интенсивностей [λij] простейших потоков, гдеλij=pijλi, вектором экспоненциально распределённыхвремён пребывания в состояниях с параметрами {1/μ1, 1/μ2,…, 1/μn}.
Главноеотличие полумарковского процесса от цепи Маркова состоит в отказе оттребования, чтобы распределения времени пребывания в каждом состоянииподчинялись показательному закону. Обычно полумарковский процесс задаётсяначальным распределением вероятностей />,матрицей переходных вероятностей [pij] и совокупностьюпроизвольных функций распределения времени пребывания в состояниях />.
В моментыпереходов из одного состояния в другое полумарковский процесс обладаетмарковским свойством. Если рассматривать полумарковский процесс только вмоменты переходов, то получающаяся при этом марковская цепь с дискретнымвременем называется вложенной марковской цепью (так как она содержится вполумарковском процессе). Вложенная цепь имеет то же пространство состояний S и тот же вектор P(0) начального распределениявероятностей состояний, что и полумарковский процесс, а матрицей переходоввложенной цепи является матрица P=[pij] полумарковского процесса.
Дляэргодических полумарковских процессов, как и для эргодических марковских цепей,характерно наличие стационарного режима.
2. МетодМонте-Карло
Различныеметоды и приборы для определения параметров и характеристик случайных процессовможно объединить в две группы. Первую группу составляют приборы для определениякорреляционных функций (корреляторы), спектральных плотностей (спектрометры), математическихожиданий, дисперсий, законов распределения и прочих случайных процессов ивеличин.
Все приборыпервой группы можно разделить на две подгруппы. Одни определяют характеристикизаписанных случайных сигналов за достаточно большое время, намного превышающеевремя реализации самого случайного процесса. Другие (они в последнее времявызывают наибольший интерес) позволяют получать характеристики случайногопроцесса оперативно, в такт с поступлением информации при натурных испытанияхновых систем управления, так как, пользуясь их показаниями, можнонепосредственно изменять процесс управления и в ходе эксперимента наблюдать зарезультатами этих изменений.
Вторая группасодержит методы и приборы, предназначенные для исследования случайных процессови главным образом систем управления, в которых присутствуют случайные сигналы,на универсальных цифровых и аналоговых вычислительных машинах. Иногда для такихисследований приходится создавать специализированные вычислительные машиныцифрового, аналогового или чаще всего аналого-цифрового (гибридного) типа, таккак существующие типовые машины не приспособлены для решения некоторых задач.
Широкоприменяется на практике метод Монте-Карло (метод статических испытаний). Егоосновная идея чрезвычайно проста и заключается по существу в математическоммоделировании на вычислительной машине тех случайных процессов и преобразованийс ними, которые имеют место в реальной системе управления. Этот метод восновном реализуется на цифровых и, реже, на аналоговых вычислительных машинах.
Можноутверждать, что метод Монте-Карло остаётся чистым методом моделированияслучайных процессов, чистым математическим экспериментом, в известном смыслелишённым ограничений, свойственным другим методам. Рассмотрим данный методприменительно к решению различных задач управления.
2.1 Общаяхарактеристика метода Монте-Карло
Как ужеуказывалось, идея метода Монте-Карло (или метода статистического моделирования)очень проста и заключается в том, что в вычислительной машине создаётся процесспреобразования цифровых данных, аналогичный реальному процессу. Вероятностныехарактеристики обоих процессов (реального и смоделированного) совпадают скакой-то точностью.
Допустим,необходимо вычислить математическое ожидание случайной величины X, подчиняющейся некоторомузакону распределения F(x). Для этого в машине реализуют датчик случайных чисел, имеющийданное распределение F(x), и по формуле, которую легко запрограммировать, определяютоценку математического ожидания:
/>.
Каждоезначение случайной величины xi представляется в машине двоичным числом, котороепоступает с выхода датчика случайных чисел на сумматор. Для статистическогомоделирования рассматриваемой задачи требуется N-кратное повторениерешения.
Рассмотримещё один пример. Производится десять независимых выстрелов по мишени.Вероятность попадания при одном выстреле задана и равна p. Требуется определитьвероятность того, что число попаданий будет чётным, т.е. 0, 2, 4, 6, 8, 10.Вероятность того, что число попаданий будет 2k, равна:
/>,
откудаискомая вероятность
/> (1)
Если этаформула известна, то можно осуществить физический эксперимент, произведянесколько партий выстрелов (по десять в каждой) по реальной мишени. Но прощевыполнить математический эксперимент на вычислительной машине следующимобразом. Датчик случайных чисел выдаст в цифровом виде значение случайнойвеличины ξ, подчиняющейся равномерному закону распределения в интервале[0,1]. Вероятность неравенства ξ
P {ξ
/>
Для поясненияцелесообразно обратиться к рис. 1, на котором весь набор случайных чиселпредставляется в виде точек отрезка [0,1]. Вероятность попадания случайнойвеличины ξ, имеющей равномерное распределение в интервале [0,1], винтервал [0, p](где />) равна длине этогоотрезка, т.е. p.Поэтому на каждом такте моделирования полученное число ξ сравнивают сзаданной вероятностью p. Если ξ
Различают двеобласти применения метода Монте-Карло. Во-первых, для исследования навычислительных машинах таких случайных явлений и процессов, как прохождениеэлементарных ядерных частиц (нейтронов, протонов и пр.) через вещество, системымассового обслуживания (телефонная сеть, система парикмахерских, система ПВО ипр.), надёжность сложных систем, в которых выход из строя элементов иустранения неисправностей являются случайными процессами, статистическоераспознавание образов. Это – применение статистического моделирования кизучению так называемых вероятностных систем управления.
Этот методшироко применяется и для исследования дискретных систем управления, когдаиспользуются кибернетические модели в виде вероятностного графа (например,сетевое планирование с β-распределением времени выполнением работ) иливероятностного автомата.
Если динамикасистемы управления описывается дифференциальными или разностными уравнениями(случай детерминированных систем управления) и на систему, например угловуюследящую систему радиолокационной станции воздействуют случайные сигналы, тостатическое моделирование также позволяет получить необходимые точностныехарактеристики. В данном случае с успехом применяются как аналоговые, так ицифровые вычислительные машины. Однако, учитывая более широкое применение пристатистическом моделировании цифровых машин, рассмотрим в данном разделевопросы, связанные только с этим типом машин.
Втораяобласть применения метода Монте-Карло охватывает чисто детерминированные,закономерные задачи, например нахождение значений определённых одномерных имногомерных интегралов. Особенно проявляется преимущество этого метода посравнению с другими численными методами в случае кратных интегралов.
При решенииалгебраических уравнений методом Монте-Карло число операций пропорциональночислу уравнений, а при их решении детерминированными численными методами эточисло пропорционально кубу числа уравнений. Такое же приблизительнопреимущество сохраняется вообще при выполнении различных вычислений с матрицамии особенно в операции обращения матрицы. Надо заметить, что универсальныевычислительные машины не приспособлены для матричных вычислений и методМонте-Карло, применённый на этих машинах, лишь несколько улучшает процессрешения, но особенно преимущества вероятностного счёта проявляются прииспользовании специализированных вероятностных машин. Основной идеей, котораяиспользуется при решении детерминированных задач методом Монте-Карло, являетсязамена детерминированной задачи эквивалентной статистической задачей, к которойможно применять этот метод. Естественно, что при такой замене вместо точногорешения задачи получается приближённое решение, погрешность которого уменьшаетсяс увеличением числа испытаний.
Эта идея используетсяв задачах дискретной оптимизации, которые возникают при управлении. Часто этизадачи сводятся к перебору большого числа вариантов, исчисляемогокомбинаторными числами вида N=/>. Так, задачараспределения nвидов ресурсов между отраслями для n>3 не может быть точно решена на существующих цифровыхвычислительных машинах (ЦВМ) и ЦВМ ближайшего будущего из-за большого объёмаперебора вариантов. Однако таких задач возникает очень много в кибернетике,например синтез конечных автоматов. Если искусственно ввести вероятностнуюмодель-аналог, то задача существенно упростится, правда, решение будетприближённым, но его можно получить с помощью современных вычислительных машинза приемлемое время счёта.
При обработкебольших массивов информации и управлении сверхбольшими системами, которыенасчитывают свыше 100 тыс. компонентов (например, видов работ, промышленныхизделий и пр.), встаёт задача укрупнения или эталонизации, т.е. сведениясверхбольшого массива к 100–1000 раз меньшему массиву эталонов. Это можновыполнить с помощью вероятностной модели. Считается, что каждый эталон можетреализоваться или материализоваться в виде конкретного представителя случайнымобразом с законом вероятности, определяемым относительной частотой появленияэтого представителя. Вместо исходной детерминированной системы вводитсяэквивалентная вероятностная модель, которая легче поддаётся расчёту. Можнопостроить несколько уровней, строя эталоны эталонов. Во всех этих вероятностныхмоделях с успехом применяется метод Монте-Карло. Очевидно, что успех и точностьстатистического моделирования зависит в основном от качества последовательностислучайных чисел и выбора оптимального алгоритма моделирования.
Задачаполучения случайных чисел обычно разбивается на две. Вначале получаютпоследовательность случайных чисел, имеющих равномерное распределение винтервале [0,1]. Затем из неё получают последовательность случайных чисел,имеющих произвольный закон распределения. Один из способов такогопреобразования состоит в использовании нелинейных преобразований. Пусть имеетсяслучайная величина X, функция распределения вероятности для которой
/>.
Если y является функцией x, т.е. y=F(x), то /> и поэтому />. Таким образом, дляполучения последовательности случайных чисел, имеющих заданную функциюраспределения F(x), необходимо каждоечисло yс выхода датчика случайных чисел, который формирует числа с равномерным закономраспределения в интервале [0,1], подать на нелинейное устройство (аналоговоеили цифровое), в котором реализуется функция, обратная F(x), т.е.
/>. (2)
/>
Полученнаятаким способом случайная величина X будет иметь функцию распределения F(x). Рассмотренная вышепроцедура может быть использована для графического способа получения случайныхчисел, имеющих заданный закон распределения. Для этого на миллиметровой бумагестроится функция F(x)и вводится в рассмотрение другая случайная величина Y, которая связана сослучайной величиной X соотношением (2) (рис. 2).
Так как любаяфункция распределения монотонно неубывающая, то
/>.
Отсюдаследует, что величина Y имеет равномерный закон распределения в интервале [0,1], т. к.её функция распределения равна самой величине
/>.
Плотностьраспределения вероятности для Y
/>.
Для получениязначения Xберётся число из таблиц случайных чисел, имеющих равномерное распределение,которое откладывается на оси ординат (рис. 2), и на оси абсцисссчитывается соответствующее число X. Повторив неоднократно эту процедуру, получимнабор случайных чисел, имеющих закон распределения F(x). Таким образом,основная проблема заключается в получении равномерно распределённых в интервале[0,1] случайных чисел. Один из методов, который используется при физическомспособе получения случайных чисел для ЭВМ, состоит в формировании дискретнойслучайной величины, которая может принимать только два значения: 0 или 1 свероятностями
/>
Далее будемрассматривать бесконечную последовательность z1, z2, z3,… как значения разрядовдвоичного числа ξ* вида
/>
Можнодоказать, что случайная величина ξ*, заключённая в интервале[0,1], имеет равномерный закон распределения
/>.
В цифровойвычислительной машине имеется конечное число разрядов k. Поэтому максимальноеколичество несовпадающих между собой чисел равно 2k. В связи с этим в машинеможно реализовать дискретную совокупность случайных чисел, т.е. конечное множествочисел, имеющих равномерный закон распределения. Такое распределение называетсяквазиравномерным. Возможные значения реализации дискретного псевдослучайногочисла /> в вычислительной машине с k разрядами будут иметьвид:
/>. (3)
Вероятностькаждого значения (3) равна 2-k. Эти значения можнополучить следующим образом
/>.
Случайнаявеличина /> имеет математическоеожидание
/>.
Учитывая, что
/>
и выражениедля конечной суммы геометрической прогрессии
/> />, (4)
получаем:
/>. (5)
Аналогичноможно определить дисперсию величины />:
/>,
где
/> />
/>,
откуда
/>,
или,используя формулу (4), получаем:
/>. (6)
Согласноформуле (5) оценка /> величины ξ*получается смещённой при конечном k. Это смещение особенно сказывается при малом k. Поэтому вместо /> вводят оценку
/>, (7)
где
/>.
Очевидно, чтослучайная величина ξ в соответствии с соотношением (3) может приниматьзначения
/>, i=0,1,2,…, 2k-1
свероятностью p=1/2k.
Математическоеожидание и дисперсию величины ξ можно получить из соотношений (5) и (6),если учесть (7). Действительно,
/>;
/>.
Отсюдаполучаем выражение для среднеквадратичного значения в виде
/>. (8)
Напомним, чтодля равномерно распределённой в интервале [0,1] величины x имеем
/>
Из формулы(8) следует, что при /> среднеквадратичноеотклонение σ квазиравномерной совокупности стремится к />. Ниже приведены значенияотношения среднеквадратичных значений двух величин ξ и η взависимости от числа разрядов, причём величина η имеет равномерноераспределение в интервале [0,1] (табл. 1).
Таблица 1k 2 3 5 10 15
σξ/ση 1,29 1,14 1,030 1,001 1,00
Из табл. 1видно, что при k>10 различие в дисперсиях несущественно.
На основаниивышеизложенного задача получения совокупности квазиравномерных чисел сводится кполучению последовательности независимых случайных величин zi (i=1,2,…, k), каждая из которыхпринимает значение 0 или 1 с вероятностью 1/2. Различают два способа получениясовокупности этих величин: физический способ генерирования и алгоритмическоеполучение так называемых псевдослучайных чисел. В первом случае требуетсяспециальная электронная приставка к цифровой вычислительной машине, во второмслучае загружаются блоки машины.
Прифизическом генерировании чаще всего используются радиоактивные источники илишумящие электронные устройства. В первом случае радиоактивные частицы,излучаемые источником, поступают на счётчик частиц. Если показание счётчикачётное, то zi=1, если нечётное, то zi=0. Определим вероятностьтого, что zi=1. Число частиц k, которое испускается за время Δt, подчиняются законуПуассона:
/>.
Вероятностьчётного числа частиц
/>.
Такимобразом, при больших λΔt вероятность P{Zi=1} близка к 1/2.
Второй способполучения случайных чисел zi более удобен и связан с собственными шумамиэлектронных ламп. При усилении этих шумов получается напряжение u(t), которое являетсяслучайным процессом. Если брать его значения, достаточно отстоящие друг отдруга, так чтобы они были некоррелированы, то величины u(ti) образуютпоследовательность независимых случайных величин. Обычно выбирают уровеньотсечки aи полагают
/>
причёмуровень aследует выбрать так, чтобы
/>.
Такжеприменяется более сложная логика образования чисел zi. В первом вариантеиспользуют два соседних значения u(ti) и u(ti+1), и величина Zi строится по такомуправилу:
/>
Если пара u(ti) – a и u(ti+1) – a одного знака, то берётсяследующая пара. Требуется определить вероятность при заданной логике. Будемсчитать, что P{u(ti)>a}=W и постоянная для всех ti. Тогда вероятностьсобытия /> равна по формуле событий A1Hv. Здесь Hv – это вероятность того,что vраз появилась пара одинакового знака
u(ti) – a; u(ti+1) – a. (9)
Поэтомувероятность события A1Hv
P{A1Hv}=W (1-W) [W2+(1-W)2]v.
Это –вероятность того, что после v пар вида (9) появилось событие A1. Оно может появитьсясразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) свероятностью
W (1-W) [W2+(1+W)2]
и т.д. Врезультате
/>
или
/>.
Отсюдаследует, что если W=const, то логика обеспечивает хорошую последовательность случайныхчисел. Второй способ формирования чисел zi состоит в следующем:
/>
Пусть
W=P {u(ti)>a}=1/2+ξ.
Тогда
P{Zi=1}=2W (1-W)=1/2–2ξ2.
Чем меньше ξ,тем ближе вероятность P{Zi=1} к величине 1/2.
Для полученияслучайных чисел алгоритмическим путём с помощью специальных программ навычислительной машине разработано большое количество методов. Так как на ЦВМневозможно получить идеальную последовательность случайных чисел хотя быпотому, что на ней можно набрать конечное множество чисел, такие последовательностиназываются псевдослучайными. На самом деле повторяемость или периодичность впоследовательности псевдослучайных чисел наступает значительно раньше иобусловливается спецификой алгоритма получения случайных чисел. Точныеаналитические методы определения периодичности, как правило, отсутствуют, ивеличина периода последовательности псевдослучайных чисел определяетсяэкспериментально на ЦВМ. Большинство алгоритмов получается эвристически иуточняется в процессе экспериментальной проверки. Рассмотрение начнём с такназываемого метода усечений. Пусть задана произвольная случайная величина u, изменяющаяся винтервале [0,1], т.е. />. Образуем из неёдругую случайную величину
un=u[mod 2-n], (10)
где u [mod 2-n] используется дляопределения операции получения остатка от деления числа u на 2-n. Можно доказать, чтовеличины un в пределе при /> имеютравномерное распределение в интервале [0,1].
По существу спомощью формулы (10) осуществляется усечение исходного числа со стороны старшихразрядов. При оставлении далёких младших разрядов естественно исключаетсязакономерность в числах и они более приближаются к случайным. Рассмотрим это напримере.
Пример 1. Пусть u = 0,10011101… = 1·1/2 + 0·1/22 + 0·1/23 + 1·1/24 + 1·1/25 + 1·1/26 + 0·1/27 + 1·1/28 + …
Выберем дляпростоты n=4.Тогда {u mod 2-4} = 0,1101…
Израссмотренного свойства ясно, что существует большое количество алгоритмовполучения псевдослучайных чисел. При этом после операции усечения со сторонымладших разрядов применяется стандартная процедура нормализации числа вцифровой вычислительной машине. Так, если усечённое слева число не умещается подлине в машине, то производится усечение числа справа.
При проверке качествапсевдослучайных чисел прежде всего интересуются длиной отрезка апериодичности идлиной периода (рис. 3). Под длиной отрезка апериодичности L понимается совокупностьпоследовательно полученных случайных чисел α1, …, αL таких, что αi/>αj при />, />, />, но αL+1 равно одному из αk (/>).
Под длиной периодапоследовательности псевдослучайных чисел понимается T=L-i+1. Начиная с некоторогономера iчисла будут периодически повторяться с этим периодом (рис. 3).
/>
Как правило,эти два параметра (длины апериодичности и периода) определяютсяэкспериментально. Качество совпадения закона распределения случайных чисел сравномерным законом проверяется с помощью критериев согласия.
2.2 Точностьметода Монте-Карло
МетодМонте-Карло применяется там, где не требуется высокой точности. Например, еслиопределяют вероятность поражения мишени при стрельбе, то разница между p1=0,8 и p2=0,805 несущественна.Обычно считается, что метод Монте-Карло позволяет получить точность примерно0,01–0,05 максимального значения определяемой величины.
Получимнекоторые рабочие формулы. Определим по методу Монте-Карло вероятностьпребывания системы в некотором состоянии. Эта вероятность оценивается отношением
/>,
где M – число пребыванийсистемы в этом состоянии в результате N моделирований. Учитывая выражение для дисперсиивеличины M/N
/>
и неравенствоЧебышёва
/>, (11)
напишем
/>. (12)
Величина
/>
есть ни чтоиное, как ошибка моделирования по методу Монте-Карло. С помощью формулы (11)можно написать следующую формулу для величины (12):
/>,
или
/>,
где p0– вероятностьневыполнения этой оценки. С помощью частоты M/N может быть полученаоценка математического ожидания mx некоторой случайной величины X. Ошибка этой оценки
/>
находится спомощью соотношения
/>.
Отсюда видно,что ошибка моделирования находится в квадратичной зависимости от числареализаций, т.е.
/>. (13)
Пример 2. Допустим, чтоопределяется математическое ожидание ошибки x поражения мишени.Процесс стрельбы и поражения моделируется на ЦВМ по методу Монте-Карло.Требуется точность моделирования δ = 0,1 м с вероятностью p = 1-p0 = 0,9 при заданнойдисперсии σx = 1 м. Необходимо определить количествомоделирований N.По формуле (13) получаем:
/> />.
При такомколичестве реализаций обеспечивается δ=0,1 м с вероятностью p=0,9.
3. Методветвей и границ
Всекомбинаторные методы решения задач целочисленного программирования основаны натой или иной идее направленного перебора вариантов, в результате которого путёмперебора сокращенного числа допустимых решений отыскивается оптимальноерешение. Перебор осуществляется с помощью определённого комплекса правил,которые позволяют исключать подмножества вариантов, не содержащие оптимальнойточки.
В целом этиметоды легче справляются с проблемой округлений, чем методы отсечения, какправило, не используют симплекс-процедуру линейного программирования и имеютболее «простую арифметику» и более «сложную логику».
Основноесодержание этих методов составляют динамическое программирование и совокупностьспособов решения, объединённых общим термином – метод «ветвей и границ».
Комплексныйподход по схеме ветвлений объединяет целый ряд близких комбинаторных методов,как-то: метод ветвей и границ, метод последовательного конструирования, анализаи отсева вариантов и др. Общая идея метода крайне проста. Множество допустимыхпланов некоторым способом разбивается на подмножество. В свою очередь каждое изподмножеств по этому же или другому способу снова разбиваются на подмножествадо тех пор, пока каждое подмножество не будет представлять собой точку вмногомерном пространстве. В силу конечности наборов значений переменных деревоподмножеств (схема ветвления) конечно.
Построениесхемы ветвления есть ни что иное, как формирование процедуры перебора. Переборможет осуществляться различными способами. Сечение исходной допустимой области G0гиперплоскостью на частиG11 и G12 с последующимразделением G11 на G21 и G22 представляет собой построение дерева ветвлений с соответствующимиподмно-жествами, как это показано на рис. 4.
/>
Возможностьоценки образуемых подмножеств по наибольшему (наименьшему) значению для задачминимизации (максимизации) позволяет сократить перебор в силу того, что одно изподмножеств при выполнении определённых соотношений исключается и не нуждаетсяв последующем анализе.
Понятно, чтовыбор оценок и схемы ветвления взаимосвязаны и трудно указать общиерекомендации по использованию на практике этого метода.
Схемаветвления иллюстрируется решением обобщённой задачи одномерного раскроя (пример3) с конкретными числовыми данными.
Пример 3.
Имеютсязаготовки длиной a1=18, a2=16, a3=13. Разрезая их на части, но не склеивая, можно получать деталидлинной b1=12, b2=10, b3=8, b4=6, b5=5, b6=4. Стоимость каждой детали известна и в условных единицахчисленно равна их длине. Перечисленные детали представляют собой «портфельзаказов», который желательно обеспечить в первую очередь. В том случае, еслиэто невозможно, максимизируется стоимость получаемых деталей из заданнойноменклатуры. Если же портфель заказов обеспечивается, необходимомаксимизировать стоимость дополнительной продукции.
Величину /> будем называть дефицитом.Отрицательность дефицита ещё не означает существование варианта раскроя, приположительном дефиците раскрой невозможен. Это свойство может быть использованодля указания перспективности варианта. Так, если заготовка a2 раскраивается на b2 и b5, то независимо откомбинаций остальных отрезков раскрой невыполним, поскольку для оставшихсяотрезков дефицит положителен.
Первые этапыприводимой ниже схемы ветвления, использующей комбинаторные отношенияподмножеств вариантов, показаны на рис. 5. На первом этапе формируютсяразбиения первой группы отрезков (заготовок) на вторую группу (деталей)независимо от того, какой именно отрезок первой группы разрезается. Количествоветвей первого этапа можно вычислить лишь по рекуррентным соотношениям. Смыслподмножества {1, 2, 3} заключается в том, что один из отрезков первой группы врезультате раскроя даёт один отрезок второй группы, один из оставшихся отрезковпервой группы раскраивается на два отрезка второй группы из числа оставшихся и,наконец, последний отрезок первой группы делится на три части, образуя триотрезка второй группы. На втором этапе формируются все перестановки (с учётомпорядка) элементов первого этапа. Скажем, вариант {2, 1, 3} означает, чтоименно первый элемент первой группы a1 разрезается на две части и т.д.
/>
Очереднойэтап ветвления образуется фиксацией отрезков второй группы при указанном напредыдущем этапе числе частей, на которое разрезается первый элемент. Другими словами,формируем сочетания по числу разделений первого элемента первого множества начисло элементов второго множества. В дальнейшем фиксируем отрезки второй группыпри втором элементе первой группы и, наконец, при оставшемся элементе первойгруппы получаем варианты раскроя, всего 447 вариантов. В подробно описаннойсхеме ветвления в отличие от часто применяемых ни на одном этапе неиспользуется конкретный числовой материал. Рекомендуется построить для этого жепримера иную схему ветвления, начиная с третьего этапа, по следующему признаку:отрезки второй группы фиксируются при элементе первой группы, разрезаемом наменьшее число частей. Затем надо сравнить схемы. Нетрудно убедиться, что накаждом этапе ветвления осуществляется по регулярной процедуре, что позволяетзапоминать лишь один вариант. Сравнение дефицитов предыдущего и последующеговариантов позволяет выделить перспективную ветвь. Окончательный результат имеетвид:
{(b2, b3), (b4, b5, b6), (b1)};
{(b1, b4), (b2, b5), (b3, b6)};
{(b1, b4), (b2, b6), (b3, b5)};
{(b1, b5), (b2, b4), (b3, b6)};
{(b2, b3), (b1, b6), (b4, b5)};
{(b1, b6), (b2, b4), (b3, b5)};
{(b2, b4), (b1, b6), (b3, b5)}.
Формальнозадачу можно было бы свести к общему виду линейной задачи целочисленногопрограммирования, но такое сведение приведёт к значительному увеличениюколичества переменных и другим трудностям. Матрица коэффициентов при этомприобретает квазиблочный вид с неплотным заполнением её отличными от нуляэлементами. Как правило, задачи многоиндексные с большим числом условий исложной упорядоченностью рекомендуется решать по схеме ветвлений, используяспецифику условий и ограничений.
Для задачдискретного типа этот метод получил наибольшее распространение в силу простотыи доступности самого метода и, кроме того, наиболее естественной формы описаниясистем условий и ограничений, являющихся, как правило, отправным пунктомпостроения дерева ветвления. По существу большинство оригинальных алгоритмов(Балаша-Фора-Мальгранжа, Черенина, Джефферсона, Хиллиера и др.) являются модификациямиметода ветвей и границ с учётом специфики условий задачи.
4. Построениеоптимальной последовательности заданий на обработку в узле вычислительнойсистемы
4.1 Формализациявычислительного процесса и рабочей нагрузки
Узелвычислительной системы представляется в виде совокупности оборудования ипрограммных компонент. Оборудование включает в себя: центральный процессор (CPU), внешнюю память (HDD), устройстваввода-вывода информации (IOI). Программными компонентами в вычислительнойсистеме являются операционная система (OS) и множество задач,реализуемых по запросам рабочей нагрузки. Для моделирования рабочей нагрузки наузлах вычислительной системы необходимо провести декомпозицию каждого заданияпакета рабочей нагрузки на отдельные программные модули (ПМj). Количество и типы программныхмодулей зависят от имеющегося состава оборудования и программных средств узлавычислительной системы. При этом можно выделить следующие типы программныхмодулей: ввода информации; обработки информации; реализация вычислений нацентральном процессоре; вывода информации. Модуль обработки информацииобращается к базе данных вычислительной системы.
В своюочередь реализация обращения к базе данных также имеет определённую структуру,характеризующуюся графом GBD связей модулей в базе данных (MDBk). Предполагается, чтохарактер следования друг за другом модулей базы данных при выполнении запросовв модуле обработки информации также является полумарковским.
Посколькуреализация задания i из рабочей нагрузки характеризуется полумарковским процессом, тодля определения характера этого процесса необходимо задать следующиехарактеристики:
· матрицувероятности переходов i-го задания от одного (j-го) программного модуляк другому (l-му)программному модулю МРi=||Рijl||;
· матрицу,элементами которой являются функции распределения времени обработки задачи i в i-ом программном модулепри условии получения им управления от j-го программного модуля (MFi=||Fi(tjl)||);
· тип j-гопрограммного модуля, с которого начинается полумарковский процесс задания i (jOi) и количество j-х программных модулей,реализуемых цепочкой j-х программных модулей(nOi).
Аналогичнымспособом определяются характеристики полумарковского процесса реализацииобмена. В качестве исходной информации задаются:
· матрицавероятностей следования друг за другом MDBjk (Mqj=||qjks||);
· матрица,элементами которой являются функции распределения объёмов информации привыполнении MDBjs при условии того, что перед этим использовался модуль MDBjk (МФj=||Fj(Vobjs)||);
· тип MDBjk, с которого начинаетсяобращение к базе данных (kO), и количество MDBjk, реализуемое при данномобращении j-гопрограммного модуля к базе данных (mOj).
4.2 Особенностиорганизации имитационного эксперимента
Динамикавыполнения задач пользователей на оборудовании узла вычислительной системы отражаетсяпоследовательностью j-х программных модулей и имеет вероятностный характер. Каждый j-й программный модульузла захватывает ресурс центрального процессора, часть ресурса оперативнойпамяти (Voni) и обращается к внешней памяти (HDD). Ресурс центральногопроцессора всегда выделяется j-м программным модулем полностью. Распределение ресурсацентрального процессора организует операционная система. Ресурс центральногопроцессора распределяется по всем j-м программным модулям и для его выделения наопределённый квант времени (Δt) используется система управляющих сигналов,формируемых по заявкам, поступающим от j-х программных модулей.Внешняя память моделируется как место размещения базы данных, и поэтомувыделение ресурса внешней памяти для j-х программных модулей осуществляется дозавершения выполнения задания. Функционирование устройств информации вводавывода и модуля вывода информации моделируются как обычные устройства массовогообслуживания с дисциплиной FIFO.
Время,затраченное на выполнение задания i, обозначим через Тжi. Причём, в Тжi включается сумма времениобслуживания задачи i на всех устройствах вычислительной системы, а также сумма времёниздержек выполнения запросов заданий из-за занятости требуемых ресурсов другимизадачами.
Цельюмоделирования вычислительного процесса в вычислительных системах являетсяминимизация />за счёт оптимизации порядкавхода заданий рабочей нагрузки в вычислительной системе при неизменном составересурсов системы. Для получения оптимальной последовательности задач рабочейнагрузки необходимо знать: перечисленные ранее характеристики полумарковскогопредставления процесса решения задач; ресурсные характеристики вычислительнойсистемы; возможные реакции вычислительной системы на задания рабочей нагрузки сцелью подсчёта времени обработки i-го задания в вычислительной системе.
Предполагается,что первые два условия задаются до постановки имитационного эксперимента.Поэтому ниже рассматриваются особенности моделирования вариантов обработкизаданий в вычислительной системе.
Посколькукаждое задание использует ресурс вычислительной системы вероятностным образом,то для расчёта наиболее вероятного времени обработки узлом вычислительнойсистемы i-гозадания Tжi, а также коэффициентов загрузки центральногопроцессора (ηCPU) и внешней памяти (ηHDD) используется методМонте-Карло. Количество реализаций (N) i-го задания i=1,…, n в вычислительной системе определяется из точностимоделирования (/>) для полученияоценок вектора (Тжi, ηCPUi, ηHDDi). По окончании N реализаций имитационногоэксперимента всех n заданий рабочей нагрузки получается матрица для каждого отклика (Тжi, ηCPUi, ηHDDi). Методика расчётакомпонент этого вектора реализуется следующей последовательностью шагов.
Шаг 1. Нахождение временирешения задач (Тжi) и определение коэффициентов загрузки (ηCPU, ηHDDi) для различных уровнеймультипрограммирования. Заметим, что обычно число уровнеймультипрограммирования редко превышает величину 5, поэтому в нашем исследованиибудем ориентироваться на максимальный уровень мультипрограммирования равный 5.Алгоритм реализации шага 1 основан на методе Монте-Карло для каждого уровнямультипрограммирования.
После N реализаций имитационногоэксперимента с моделью вычислительного процесса для h-го уровнямультипрограммирования (h-й вариант вычислительного процесса, h=0,…, 5) по методуМонте-Карло будет сформировано три матрицы, компонентами которой будут парызначений:
M1ih=||(MTжih, DTжih)||; M2ih=||(MηCPUih, DCPUih)||; M3ih=||(MηHDDih, DηHDDih)||.
Шаг 2. По матрицам M1ih, M2ih, M3ih для h-го уровня мультипрограммированияопределяют математические ожидания и дисперсии вычислений каждого из откликов:времени решения всего пакета (МТПАКh, МТПАКh); общей загрузкицентрального процессора (MηHDDh, DηHDDh); общей загрузки внешней памяти (MηHDDh, DηHDDh) по формулам:
MYПАКh=/>, DYПАКh=/>,
где 0/>δi/>/>/>1 – весовой коэффициентзадач i-готипа в пакете;
m0– общее число задач впакете;
mi – количество задач i-го типа в пакете;
YПАКh – отклик, содержаниекоторого соответствует одной из характеристик вычислительного процесса ввычислительной системе (Тж, ηCPU, ηHDD).
4.3 Модификацияпоследовательности решения задач в пакете по методу ветвей и границ
Описанная выше структурапакета рабочей нагрузки позволяет выделить следующие возможные случаиколичества типов заданий.
1. Всезадания пакета рабочей нагрузки имеют один и тот же тип (i=1).
2. Впакете имеются различные типы заданий и количество типов (1
3. Всезадания пакета имеют различные типы (i=m0).
Наибольшийинтерес для исследования поиска оптимального расположения задач в пакетерабочей нагрузки представляет третий случай. Поэтому рассмотрим применениеметода ветвей и границ для этого случая.
Шаг 0. Вычисляется общее времяобработки всего ещё не упорядоченного пакета Tξ(STR).
Шаг 1. Размерность множества STR равна n (|STR| = n). На первом уровневетвления вычисляются оценки Tξ(STRi1), i=1,…, n. Они вычисляются приусловии, что i-езадание начинает обрабатываться первым, а оставшиеся n-1 заданий входят врасписание по мере возрастания Тжi. Среди этих оценоквыбирается оценка с наименьшим Tξ(STRi1) и соответствующее i-е задание (i1) вставляется врасписание первым. При этом остальные оценки отбрасываются и соответствующие импорядки следования задач заданий считаются заведомо неоптимальными.
Шаг 2. Размерность массива STR равна n-1 (|STR| = n-1). Этот уровеньветвления осуществляется при условии, что одно из заданий i (i1) уже вставлено врасписание для обработки первым. Для остальных n-1 заданий, ещё невставленных в расписание, вычисляются оценки Tξ(STRi2), i=1,…, n-1, при условии, чтозадание iзагружается для обработки вторым, а оставшиеся n-2 заданий входят врасписание по мере возрастания Тжi. Среди этих оценоквыбирается оценка с наименьшим Tξ(STRi2) и соответствующее i-е задание (i2) вставляется врасписание вторым. При этом остальные оценки отбрасываются и соответствующие импорядки следования задач заданий считаются заведомо неоптимальными. Врезультате второго шага в оптимальное расписание будут вставлены уже двазадания.
Шаг k(k>2). Размерность массива STR равна n-k+1 (|STR| = n-k+1). Этот уровеньветвления осуществляется при условии, что k-1 задание уже вставленов расписание. Для остальных n-k+1 заданий, ещё не вставленных в расписание, вычисляются оценки Tξ(STRik), i=1,…, n-k+1. Среди этих оценоквыбирается оценка с наименьшим Tξ(STRik) и соответствующее i-е задание (ik) вставляется врасписание k-ым.При этом остальные оценки отбрасываются и соответствующие им порядки следованиязадач заданий считаются заведомо неоптимальными. В результате k-го шага в оптимальноерасписание будут вставлены уже k заданий.
Шаг n. Размерность множества STR равна 1 (|STR| = 1). На этом шагеосталось только одно задание, не вставленное в расписание. Оно вставляется врасписание последним, и вычисляется оценка Tξ(STRin), i=1, которая и будетитоговой оценкой (временем) обработки заданий пакета рабочей нагрузки присоответствующем ей расписании.
Послеполучения оптимальной последовательности порядка задач с помощью метода ветвейи границ необходимо сравнить это время обработки пакета со временем, полученнымпри начальном расположении заданий в пакете рабочей нагрузки.
Заключение
Проблемаадаптации рабочей нагрузки к параметрам вычислительного процесса представляетсяактуальной из-за необходимости повышения эффективности использования ресурсоввычислительной системы и качества обслуживания запросов пользователя. Крометого, на практике зачастую непрерывно меняются и состав, и структура рабочейнагрузки, что усложняет ситуацию выбора оптимального варианта вычислительногопроцесса.
Изучив ипроанализировав ряд научных статей, посвящённых данной проблеме, следуетотметить, что наиболее простым и распространённым способом её решения являетсяметод ветвей и границ. Было установлено, что большинство существующих оригинальныхалгоритмов являются модификациями данного метода. Впервые метод ветвей и границбыл предложен Лендом и Дойгом в 1960 году для решения общей задачицелочисленного линейного программирования. Интерес к этому методу и фактическиего «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела,посвященной задаче комивояжера. Начиная с этого момента, появилось большоечисло работ, посвященных методу ветвей и границ и различным его модификациям.
Можноутверждать, что проблема адаптации рабочей нагрузки будет оставаться актуальнойи в ближайшем будущем в связи с тем, что её можно решать и в условиях локальныхвычислительных сетей.
Такимобразом, рассмотренное применение метода ветвей и границ к построениюоптимальной последовательности заданий на обработку в вычислительной системепозволяет говорить о возможной эффективности привлечения этого метода к такомутипу задач.
Списокисточников
1. Галиев Р.С. Экспериментальныеметоды исследования вычислительного процесса ЕС ЭВМ. – Дис., Гомель, 1987.
2. Демиденко О.М.,Максимей И.В., Имитационное моделирование взаимодействия процессов ввычислительных системах. – Мн.: Белорусская наука, 2000.
3. Корбут А.А.,Финкельштейн Ю.Ю., Дискретное программирование. – М.: Наука, 1969.
4. Максимей И.В.,Серегина В.С. Задачи и модели исследования операций. Часть 2. –Гомель, 1999.
5. Максимей И.В. Имитационноемоделирование на ЭВМ. – М.: Радио и связь, 1988.
6. Грек В.В.,Максимей И.В. Стандартизация и метрология систем обработки данных. –Мн.: Высшая школа, 1994.
7. Бышик Т.П.,Маслович С.Ф., Мережа В.Л. О построении оптимальнойпоследовательности заданий на обработку в узле ЛВС // Известия Гомельскогогосударственного университета имени Ф. Скорины. – 2002. – №6 (15) –С. 7–9.
8. Кузин Л.Т. Основыкибернетики. Том 1. – М.: Энергия, 1973.
9. Land A.H., and Doig A.G. An automatic method of solvingdiscrete programming problems. Econometrica. v28 (1960), pp.497–520.
10. Little J.D.C.,Murty K.G., Sweeney D.W., and Karel C. An algorithm for the travelingsalesman problem. Operations Research. v11 (1963), pp. 972–989.