МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

«Гомельский государственный университет имени Франциска Скорины»

Математический факультет

Кафедра МПУ

Курсовая работа

"Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса"

 

 

Гомель 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] полумарковского процесса.

Для эргодических полумарковских процессов, как и для эргодических марковских цепей, характерно наличие стационарного режима.



Информация о работе «Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса»
Раздел: Информатика, программирование
Количество знаков с пробелами: 49855
Количество таблиц: 1
Количество изображений: 5

Похожие работы

Скачать
116226
28
14

... 115537,893 Итого - - 1050310,49 Годовой эффект совокупных затрат определяется по формуле, р.: Срок окупаемости срок определяется по формуле (2.9) Коэффициент эффективности определяется по формуле (2.10) Применение цифровой защиты фидеров контактной сети постоянного тока ЦЗАФ-3,3 выгодно, так как эффективность от внедрения данной защиты составляет 2,334 и окупится менее чем за ...

Скачать
148576
34
0

... элементов, глобальное пространство имен, а также лавинообразную первоначальную загрузку сети. Таким образом ОСРВ SPOX имеет необходимые механизмы для создания отказоустойчивой распределенной операционной системы реального времени, концепция построения которой описана в главе 2. 4.3 Аппаратно-зависимые компоненты ОСРВ Модули маршрутизации, реконфигурации, голосования реализованы как аппаратно- ...

Скачать
170408
6
43

... ; фС- красный; 0-шина: изолированный контроль– белый; заземлённая нейтраль–чёрный. 2. ~; фаза–красный; 0–жёлтый. 3. –; (+)–красный; (–)–синий; нейтраль–белый.  Лекция 20. "Основы конструирования" Основы патентоведения 1.0 Введение –Изобретательство – важный фактор ТП.– Изобретательское право (ИП).– Открытия, Изобретения, Промышленные образцы – объекты изобретательского права (Субъекты ...

Скачать
131261
1
0

... в должности, либо увольняется и на его место приходит тот, кто способен вывести ситуацию из тупика. Определяющую роль в стабильности фирмы играет управление персоналом, в том числе отбор и адаптация кадров.. В фирме "ИСТА" процесс управления трудовым персоналом проходит следующие стадии: • Планирование персонала. • Набор персонала. • Отбор. • Определение заработной платы и льгот: ...

0 комментариев


Наверх