Касаркин Алексей Викторович Методы и средства создания параллельно-конвейерных программ для решения графовых NP-полных задач на реконфигурируемых вычислительных системах

Краткое описание

Касаркин Алексей Викторович Методы и средства создания параллельно-конвейерных программ для решения графовых NP-полных задач на реконфигурируемых вычислительных системах
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Касаркин Алексей Викторович
ВЕДЕНИЕ

1. МЕТОДЫ И СРЕДСТВА РЕШЕНИЯ ГРАФОВЫХ №-ПОЛНЫХ ЗАДАЧ

1.1 Задачи теории графов

1.2 Многопроцессорные вычислительные системы, используемые для решения графовых задач

1.3 Реконфигурируемые вычислительные системы

1.4. Языки программирования реконфигурируемых вычислительных систем

1.5. Принципы решения графовых №-полных задач на реконфигурируемых вычислительных системах

1.6 Выводы

2. БАЗОВЫЕ МАКРООПЕРАЦИИ ТЕОРИИ МНОЖЕСТВ

2.1 Обобщение операций добавления и удаления элемента из множества

2.2 Операция объединения множеств

2.3 Операция разность множеств

2.4 Библиотека программ типовых операций для решения задач теории множеств на реконфигурируемых вычислительных системах

2.5 Выводы

3. РЕШЕНИЕ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА МЕТОДОМ РАСПАРАЛЛЕЛИВАНИЯ ПО СЛОЯМ

3.1 Сравнение алгоритмов

3.2 Параллельные реализации задачи поиска максимальных клик графа на классических вычислительных системах

3.3 Реализация задачи поиска максимальных клик графа на РВС методом распараллеливания по слоям

3.4 Экспериментальные исследования метода распараллеливания по слоям

3.5 Выводы

4. РЕШЕНИЕ ЗАДАЧИ ПОИСКА МАКСИМАЛЬНЫХ КЛИК ГРАФА ИТЕРАЦИОННЫМИ МЕТОДАМИ

4.1. Предел роста производительности метода распараллеливания по слоям

4.2. Метод распараллеливания по итерациям

4.3. Реализация алгоритма задачи поиска максимальных клик графа на РВС итерационными методами

4.4. Модернизации метода распараллеливания по итерациям графовых ЫР-полных задач

4.5. Экспериментальные исследования метода распараллеливания по итерациям

4.6. Методика выбора эффективного варианта распараллеливания

4.7. Выводы

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ 1. Макрооперации теории множеств

П.1.1. Операция определения принадлежности потока элементов множеству

П.1.2. Операция добавления элемента в множество

П.1.3. Операция удаления элемента из множества

П.1.4. Операция пересечение множеств

П.1.5. Операция симметрическая разность множеств

ПРИЛОЖЕНИЕ 2. Теоретическая оценка времени решения задачи поиска

максимальных клик графа на современном процессоре

ПРИЛОЖЕНИЕ 3. Подготовка начальных данных для алгоритма Брона-

Кербоша на основе упорядочивания по вырождению

ПРИЛОЖЕНИЕ 4. Расчет предела роста производительности метода

распараллеливания по слоям

ПРИЛОЖЕНИЕ 5. Акты о внедрении и использовании результатов диссертации

ВЕДЕНИЕ