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

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

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

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

Кафедра МПУ

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

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

Гомель 2002

Реферат

Курсовая работа 25 страниц, 10 источников, 5 рисунков, 1 таблица

Ключевые слова: ИМИТАЦИОННАЯ МОДЕЛЬ, МЕТОД ВЕТВЕЙ И ГРАНИЦ, ПОЛУМАРКОВСКИЕ ПРОЦЕССЫ, ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА, ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС, ПРОГРАММНЫЙ МОДУЛЬ, ГРАФ, МАТРИЦА ВЕРОЯТНОСТЕЙ, МЕТОД МОНТЕ-КАРЛО

Объект исследования: имитационная модель процесса обработки данных.

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

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

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

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

Содержание

Введение

1. Марковские процессы

2. Метод Монте-Карло

2.1 Общая характеристика метода Монте-Карло

2.2 Точность метода

3. Метод ветвей и границ

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

4.1 Формализация вычислительного процесса и рабочей нагрузки

4.2 Особенности организации имитационного эксперимента

4.3 Модификация последовательности решения задач в пакете по методу ветвей и границ

Заключение

Список источников

Введение

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

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

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

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

1. Марковские процессы

Пусть имеется система, которая в произвольный момент времени t_k может находиться в одном из состояний s_i , , с вероятностью . Через некоторые промежутки времени система переходит из одного состояния в другое. Каждый такой переход называется шагом процесса. Случайный процесс, протекающий в системе S, называется марковским, если для произвольного момента времени вероятность любого состояния системы в будущем (при ) зависит только от её состояния в настоящем (при ) и не зависит от того, когда и каким образом система пришла в это состояние. Различают марковские процессы с дискретными состояниями и дискретным временем (стохастическая последовательность, или дискретная цепь Маркова) и марковские процессы с дискретным состоянием и непрерывным временем (непрерывная цепь Маркова). Оба типа цепей могут быть однородными и неоднородными.

Для дискретной цепи Маркова смены состояний процесса происходят в дискретные моменты времени t_i с шагом . Состояние системы s_i в момент t_k необходимо характеризовать условными вероятностями (1) того, что система за один шаг перейдёт в какое-либо состояние s_j при условии, что в момент t_{k -1} она находилась в состоянии s_i . Вероятности (1) = являются основными характеристиками марковской цепи. Они называются вероятностями перехода или переходными вероятностями. Поскольку система может находиться в одном из состояний, то для каждого момента времени t_r необходимо задать n² вероятностей перехода

.

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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать