47250 (Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса)
Описание файла
Документ из архива "Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47250"
Текст из документа "47250"
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
«Гомельский государственный университет имени Франциска Скорины»
Математический факультет
Кафедра МПУ
Курсовая работа
"Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса"
Гомель 2002
Реферат
Курсовая работа 25 страниц, 10 источников, 5 рисунков, 1 таблица
Ключевые слова: ИМИТАЦИОННАЯ МОДЕЛЬ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ, ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА, ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС, ПРОГРАММНЫЙ МОДУЛЬ, ГРАФ, МАТРИЦА ВЕРОЯТНОСТЕЙ, МЕТОД МОНТЕ-КАРЛО
Объект исследования: имитационная модель процесса обработки данных.
Предмет исследования: применение метода ветвей и границ в процессе обработки данных.
Цель курсовой работы: найти рациональный порядок следования запросов, который обеспечит максимальный критерий эффективности использования компонентов вычислительного процесса в вычислительной системе.
Задачами курсовой работы являются: изучить метод ветвей и границ и применить его к модели машинного моделирования, позволяющей найти такой порядок следования запросов, который обеспечит максимально быстрое выполнение вычислительного процесса.
Выводы: с помощью метода ветвей и границ удаётся построить такой порядок выполнения запросов, при котором время их обслуживания будет минимальным.
Содержание
Введение
1. Марковские процессы
2. Метод Монте-Карло
2.1 Общая характеристика метода Монте-Карло
2.2 Точность метода
3. Метод ветвей и границ
4. Построение оптимальной последовательности заданий на обработку в узле вычислительной системы
4.1 Формализация вычислительного процесса и рабочей нагрузки
4.2 Особенности организации имитационного эксперимента
4.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. Метод Монте-Карло