Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки

Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки

Автор: Кобак, Валерий Григорьевич

Шифр специальности: 05.13.01

Научная степень: Докторская

Год защиты: 2008

Место защиты: Ростов-на-Дону

Количество страниц: 319 с. ил.

Артикул: 4301407

Автор: Кобак, Валерий Григорьевич

Стоимость: 250 руб.

Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки  Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки 

ВВЕДЕНИЕ
1. СИСТЕМНОЕ ИССЛЕДОВАНИЕ СОСТОЯНИЯ ТЕОРИИ И
ПРАКТИКИ РЕШНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ
1.1 Сферы человеческой деятельности, попадающие в сферу решения
распределительных задач
1.1.1 Параллельные вычислительные процессы
1.1.2 Классификация расписаний
1.1.3 Условия проведения вычислительных экспериментов
1.2 Математическая постановка классической задачи распределения
1.2.1 Основная модель распределения независимых заданий
1.2.2 Оценка связности моделей совокупности простых распределительных задач
1.2.3 Критериальная стратегия решения распределительных задач
1.3. Обзор точных методов решения классической задачи Распределения
1.3.1.онятие сложности алгоритмов построения расписаний
1.3.2. Понятие внутренней сложности алгоритмов
1.3.3. Алгоритм полного перебора
1.3.4. Алгоритм, основанный на идее ветвей и границ
1.4. Обзор приближенных алгоритмов решения задачи распределения
1.4.1 Списочные расписания
1.4.2 Вероятностные расписания
1.4.2.1 Методы отжига
1.4.2.2 Метод роящихся частиц
1.4.2.3 Табуированный поиск
1.4.2.4 Эволюционный подход
1.4.3 Эвристические расписания
1.5. Постановка задачи исследования выводы по первой главе.
2. РАЗРАБОТКА МЕТОДОЛОГИИ СОПОСТАВИТЕЛЬНОКРИТЕРИАЛЬНОЙ АНАЛИТИЧЕСКОЙ ОЦЕНКИ РЕШЕНИЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
2.1. Критериальноя инвариантность распределительных задач в однородных двухприборных системах.
2.2. Исследование соотношения квадратичного и минимаксного вариантов
оптимальных распределений однородных трехприборных систем при наличии выделенного монолита
2.3. Анализ условий критериальной инвариантности в однородных трехприборных системах
2.4. Методика аналитической оценки несовпадения оптимумов по различным критериям в однородных трехприборных системах
2.5. Аналитическое исследование пприборной распределительной задачи с выделенными монолитами
2.6. Выводы по главе.
3. ПОВЫШЕНИЕ ЭФФЕКТИВ1 ГОСТИ АЛГОРИТМОВ ОПТИМАЛЬНОГО РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ
3.1. Решение распределительных задач методом полного перебора
3.2. Алгоритмы точного решения РЗ. Алгоритм Романовского АР
3.2.1. Краткое описание алгоритма
3.2.2. Пример работы алгоритма Романовского
3.2.3. Анализ АР и возможных путей его усовершенствования
3.3. Модификация алгоритма Алексеева
3.3.1 Алгоритм точного решения однородной минимаксной задачи. Алгоритм Алексеева АА.
3.3.2 Модифицированный алгоритм Алексеева для идентичных приборов
3.3.3 Пример работы модифицированного алгоритма Алексеева
3.3.4. Сравнительное исследование алгоритмов Романовского и Алексеева
3.4. Модификация алгоритма Алексеева с учетом времени выполнения каждого задания
3.5. Повышение ресурсной эффективности точных алгоритмов.
3.6. Выводы по главе
4. ИССЛЕДОВАНИЕ И СОВЕРШЕНСТВОВАНИЕ ВОЗМОЖНОСТЕЙ ЭВОЛЮЦИОННОГЕНЕТИЧЕСКИХ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ КАК СРЕДСТВ ПОДДЕРЖКИ СОПОСТАВИТЕЛЬНОКРИТЕРИАЛЬНОЙ ОЦЕНКОК
4.1. Эвристические и вероятностные методы решения распределительных
4.1.1. Предпосылки появления приближенных вероятностных и эвристических методов
4.1.2. Методы отжига
4.1.3 Метод роящихся частиц i
4.1.4 Табуированный поиск
4.1.5. Эволюционногенетический подход
4.2. Эволюционногенетические методы решения распределительных задач
4.2.1. Общая характеристика эволюционно генетического подхода.
4.2.2. Представление данных в генах.
4.2.3. Стратегия отбора.
4.2.4. Стратегии формирования нового поколения.
4.2.5. Генетические операторы.
4.2.6. Модели ЭГД.
4.2.7. Некоторые обобщения.
4.3. Побитовая генетическая модель распределительной задачи.
4.3.1. Влияние сущностных свойств распределительных задач теории расписаний на генетические модели.
4.3.2. Модель гена распределительной задачи .
4.3.3. Примеры построения и использования побитового гена распределительной задачи.
4.3.4. Оператор кроссовера распределительной задачи
4.3.5. Оператор мутации распределительной задачи.
4.3.6. Оператор инверсии распределительной задачи.
4.3.7. Оператор выбора в распределительной задаче.
4.4. Эволюционная модель распределительной задачи.
4.4.1. Итерационный процесс поиска ЭГА.
4.4.2. Пример организации итерационного поиска в ЭГА.
4.4.3. Особенности системы поиска эволюционного алгоритма
4.5. Сравнительный анализ примеров решений распределительной задачи эвристическими алгоритмами.
4.5.1. Задачи и алгоритмы для сравнения.
4.5.2. Решение задачи эволюционногенетическим алгоритмом.
4.5.3. Сравнительная оценка результатов применения к РЗ различных
методов и алгоритмов решения. .
4.6 Имитационностатистический подход к оценке оптимальности решения ЭГА.
4.6.1 Исследование распределительной задачи РЗЭГЛ на наличие закономерностей формирования вероятностной точности.
4.6.2 Теоретические основы оценки заданных вероятностно точностных условий решения РЗ.
4.6.3 Предельная ресурсная оценка решения РЗ параллельными ЭГА.
4.7. Выводы по главе
5. ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ТОЧНЫХ И ГЕЕТИЧЕСКИХ
АЛГОРИТМОВ НА ОСНОВЕ МОДИФИЦИРОВАННЫХ ПРИБЛИЖЕННЫХ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ
5.1 Приближенные алгоритмы решения, основанные на списочных
расписаниях.
5.1.1. Списочный подход к решению распределительных задач.
5.1.2. Составление расписаний методом критического пути.
5.1.3. Составление расписаний методом БРТ.
5.1.4. Составление расписаний методом ЯРТ.
5.2. Алгоритм по направлению.
5.3. Критериальная инвариантность алгоритма обслуживания по
критическому пути в однородных системах.
5.4. Перспективы повышения эффективности решения РЗ в
неоднородных системах на основе унификации списочного подхода.
5.4.1. Основания для исследования.
5.4.2. Формирование универсальной критериальной стратегии оценки ресурсов заданий распределительной задачи.
5.5. Анализ алгоритма обслуживания по критическому пути при качественной неоднородности системы.
5.5.1. Последовательная модификация алгоритма МКП при качественной неоднородности.
5.5.2. Примеры использования модифицированных алгоритмов.
5.6. Приближенные алгоритмы решения, для решения неоднородной минимаксной задачи.
5.6.1. Решение задачи алгоритмом ПлотниковаЗверева
5.6.2. Получение, приближенного решения с помощью алгоритма Алексеева
5.6.3. Экспериментальное сравнение алгоритмов
5.7. Повышение ресурсной эффективности точных алгоритмов за счет уступок по точности метод псевдократной загрузки
5.8. Выводы по главе.
6. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ В МНОГОПРИБОРНЫХ ОДНОРОДНЫХ И УСЛОВНООДНОРОДНЫХ СИСТЕМАХ
6.1. Применение приближенных и точных алгоритмов при решении задачи раскраски взвешенного графа.
6.2. Программноинформационная система ПИС поддержки имитационного решения и оптимизации распределительных задач
6.2.1. Введение
6.2.2. Организация данных и внутреннего интерфейса
6.2.3. Главное окно программы
6.2.4. Редактор опыта
6.2.5. Генерация набора опытов
6.2.6. Экспорт и импорт данных
6.2.7. Алгоритмы решения задачи
6. 3. Схема сопряжения данных с x
6.4. Выбор языка программирования и среды разработки
6.5. Выводы по главе.
ЗАКЛЮЧЕНИЕ
СПИСОК ЦИТИРУЕМЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЯ
Введение


Назначение РЗ может быть незадерживающим, если их выполнение на процессорах начинается сразу, как только это становится возможным. Не имеет смысла держать идентичные процессоры свободными, если имеются готовые к выполнению РЗ с одинаковыми временами выполнения. Однако существует ряд случаев, когда для расписаний без прерываний процессоров с различной производительностью и РЗ с различными временами выполнения, необходимо оставлять процессоры свободными, даже если имеются готовые к исполнению РЗ. В этом случае назначение РЗ и соответствующие расписания являются не задерживающими. При осуществлении назначения учитывается наличие или отсутствие закрепления тех или иных РЗ за соответствующими процессорами. Такие закрепления имеют место для специализированных процессоров. Закрепления не являются необходимыми для универсальных процессоров, но они могут вводиться искусственно в многомашинных системах с учетом особенностей расписаний. Вычислительные эксперименты основываются на программной имитации на компьютере процессов выполнения ПП двумя или более процессорами вычислительной системы в однопрограммном режиме ее работы. При этом в качестве реализации ПВГ1 используется процесс имитации на компьютере выполнения операционной модели ПП на модули многопроцессорной вычислительной системы в соответствии с исследуемыми расписаниями. Проведение экспериментов осуществляется с помощью метода статистических испытаний. Для различных сочетаний моделей программ и вычислительных систем и вариаций их параметров многократно имитируется реализации ПВП в соответствии с исследуемыми расписаниями. При каждой реализации фиксируется значение интересующих нас величин. Практически во всех случаях основной фиксируемой величиной является время 7 п выполнения ПП, в качестве которого принимается модельное время от момента начала до момента завершения соответствующего, имитируемого процесса выполнения ПП без учета времени на планирование и организацию параллельных вычислений. Полученные данные статистически обрабатываются, и производится вычисление оценок показателей эффективности. По данным большинства вычислительных экспериментов определено, что длина расписания на базе произвольного выбора операторов превышает длину оптимального расписания в среднем не более чем на . Этой оценке точности решения РЗ ГТВП и соответствуют приближенные расписания, которые могут рассматриваться как кандидаты для применения на практике немалая величина производительности, особенно для высокопроизводительных многопроцессорных систем. Необходимо отметить, что оценки эффективности расписаний, получаемые в результате вычислительных экспериментов, оказывают и более оптимистическими по сравнению с оценками, получаемыми в результате измерений на реальных вычислительных системах, поскольку в первом случае модели представляют программы и вычислительные системы в идеализированном виде, а затраты на организацию Г1ВП обычно не учитываются. В данной работе предлагается и исследуется модель распределения независимых работ на параллельно работающие устройства при различных критериях эффективности. Рассмотрим наиболее полную модель, характеризующую задачу распределения. Модель процесса упорядочения, в терминах которой формируются задачи, представлена в виде совокупности моделей, описывающих ресурсы, систему заданий, ограничения и меры оценки расписаний. В практическом большинстве изучаемых моделей ресурсы состоят просто из множества процессоров Р РР2,. Рт. В зависимости от особенностей задачи они могут быть либо идентичными, либо одинаковыми только по функциональным возможностям, но разными по быстродействию, либо разными как по возможностям, так и по быстродействию. Кроме процессоров имеется еще множество дополнительных типов ресурсов Р Я1,Я2,. Я5, некоторое подмножество которых используется на протяжении всего выполнения задания на некотором процессоре. Общая система заданий для заданного набора ресурсов может быть определена как система Г,,, у,Иу следующим образом. Т Тх,Т2,Тп набор заданий, подлежащих выполнению.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 1.069, запросов: 244