Структурный синтез вычислительной системы с помощью генетических алгоритмов

• Автор: Трекин, Антон Геннадиевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 111 с. : ил.

Содержание
Введение

Характеристики задачи

Цель работы

Методы исследования

Структура работы

1. Основные понятия и формальная постановка задачи

1.1. Модель поведения программы

1.2. Расписание

. Аппаратные средства

1.3.1 Множество процессоров

1.3.2. Коммутационная среда.
1.4. Оценка времени выполнения расписания
1.5. Формальная постановка задачи структурного синтеза ВС
2. Характеристика задачи и существующие методы решения
2.1. Характеристика задачи структурного синтеза ВС
2.2. Жадные алгоритмы
2.3. Алгоритмы случайного поиска
2.4. Алгоритмы имитации отжига
2.5. Генетические и эволюционные алгоритмы
2.6. Выводы
3. Коммутационные среды параметры, функции стоимости и времени передачи данных
3.1. Полносвязная бесконфликтная КС
3.1.1. Функция вычисления времени передачи данных
3.1.2. Функция стоимости КС
3.2. Шинные архитектуры
3.2.1. Примеры шинных архитектур
3.2.2. Функция вычисления времени передачи данных
3.2.3. Функция стоимости КС
3.3. Локальносвязные архитектуры
3.3.1. Архитектура Трехмерный тор
3.3.2. Архитектура Гиперкуб
3.3.2.1. Примеры архитектур
3.4. Выводы
4. Построение генетических алгоритмов для решения задачи структу рного синтеза ВС
4.1. Схема работы генетического алгоритима
4.2. Проблемы применения генетических алгоритмов для решения задачи структурного синтеза ВС
4.3. Кодирование решений
4.3. Алгоритм восстановления порядка выполнения рабочих интервалов на каждом процессоре5
4.4. Задание начального приближения
4.5. Критерий останова и функция выживаемости
4.6. Операция селекции
4.7. Операции мутации и скрещивания
4.8. Оценка операционной сложности генетического алгоритма
4.9. Экспериментальное исследование генетического алгоритма
4.9.1. Экспериментальное исследование стабильности работы генетического алгоритма
4.9.2. Экспериментальное исследование качества работы генетического алгоритма
4.9.3. Применение генетического алгоритма для синтеза структуры ВС для решения задачи нахождения координат источников сигнала в фазированных
антенных рештках
4.9.4. Результаты экспериментального исследования
4. Определение области эффективного применения алгоритма
5. Настройка параметров генетического алгоритма
5.1. Проблема настройки параметров генетического алгоритма
5.2. Метод настройки параметров ГА
5.3. Регрессионная модель для определения значений параметров генетического алгоритма
Заключение
Литература


Известны примеры успешного применения ГА для решения задач составления расписаний и синтеза структур ВС на различных уровнях проектирования. Из вышесказанного следует, что ГА являются перспективным методом для решения задачи синтеза структур ВС. Однако, ГА - это скорее схема, чем конкретный алгоритм. Применение ГА для решения задачи синтеза структуры ВС с одновременным построением расписания требует выбора способа кодирования решений, разработки основных операций ГА, задания функции выживаемости и настройки параметров ГА. Целью данной работы является разработка и исследование применимости ГА для решения задачи синтеза структуры ВС. Предлагаемый алгоритм должен позволять автоматизировать решение задачи синтеза ВС на абстрактном и системном уровнях проектирования. ГЛ на исходные данные и тип решаемой задачи. В данной работе предлагается метод решения задачи синтеза структуры ВС с помощью генетических алгоритмов (ГЛ). ВС из перечисленных выше. При построении ГА для синтеза структуры ВС использовались теория генетических и эволюционных алгоритмов, методы регрессионного анализа, а также методы теории эксперимента и математической статистики. Данная диссертационная работа состоит из пяти глав. В первой главе даётся формальная постановка задачи синтеза структуры ВС реального времени, подробно описываются модели аппаратных и программных средств ВС и приводится постановка задачи синтеза с труктуры ВС в виде задачи дискретной (комбинаторной) оптимизации с ограничениями. Вторая глава посвящена рассмотрению существующих методов решения задачи синтеза структуры ВС. Рассматриваются алгоритмы, наиболее часто используемые для решения задач дискретной оптимизации. Проводится сравнительный анализ алгоритмов, исследуется возможность их применения для решения задачи синтеза структуры ВС, выявляются их преимущества и недостатки. Также рассматриваются известные примеры применения ГА для решения подобных задач. В третьей главе рассматриваются наиболее часто используемые во встроенных ВС топологии коммутационных сред (КС). Для рассматриваемых КС выделяются параметры КС, которые могут быть настроены алгоритмом и строятся функции вычисления времени передачи данных и стоимости КС. В четвёртой главе описывается алгоритм, разработанный для решения задачи структурного синтеза ВС [И, ]. Предлагается метод кодирования решения, позволяющий учитывать различные наборы оптимизируемых параметров и предотвращающий возникновение некорректных решений. В главе рассматривается построение функции выживаемости для ГА на основе целевой функции и ограничений для задачи синтеза структуры ВС, для предлагаемой схемы кодирования определяются генетические операции: скрещивание, мутация, селекция. Также рассматривается три метода задания начального приближения и их влияние на скорость сходимости алгоритма и качество получаемых решений. Приводятся результаты экспериментальных исследований, и методом сгатистических испытаний доказывается стабильность работы алгоритма при фиксированных параметрах и начальном приближении. Определяются вычислительная сложность и область эффективного применения алгоритма, оценивается качество получаемых решений. Приводятся результаты экспериментального использования ГА для построения структуры ВС реального времени для решения задачи обнаружения угловых координат источников сигналов в фазированных антенных решетках. Пятая глава посвящена построению метода настройки алгоритма на входные данные. В главе анализируются существующие методы настройки параметров ГА и выделяются характеристики входных данных, влияющие на качество работы алгоритма, параметры алгоритма, значения которых зависят от входных данных, и с помощью метода регрессионного анализа строится функция вычисления значений параметров ГА по характерно гикам входных данных. В заключении формулируются основные результаты работы и рассматриваются направления развития предложенного метода для решения задачи синтеза структуры ВС. В приложении 1 приводятся результаты сравнения двух способов задания функции выживаемости. В приложении 3 приводятся результаты экспериментального исследования качества получаемых алгоритмом решений.