Параллельно-последовательный акселератор для быстрого субоптимального разбиения параллельных алгоритмов логического управления

• Автор: Ватутин, Эдуард Игоревич
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Курск
• Количество страниц: 155 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
1. ПОСТАНОВКА ЗАДАЧИ ПОИСКА ОПТИМАЛЬНЫХ РАЗБИЕНИЙ. ОБЗОР СХОЖИХ ТРУДНЫХ ЗАДАЧ И МЕТОДОВ ИХ РЕШЕИЯ
1.1. Обзор существующих трудных задач и подходов к уменьшению затрат вычислительного времени при их решении.

1.2. Классификация методов решения задачи формирования субоптимальных разбиении

2. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАЗБИЕНИЯ. АЛ1 ОРИТМЫ ЭТАПОВ МЕТОДА ПАРАЛЛЕЛЬНОПОСЛЕДОВАТЕЛЬНОЙ ДЕКОМПОЗИЦИИ

2.1. Формализованное описание алгоритма управления

2.2. Постановка задачи выбора оптимального разбиения

2.3. Приведение графсхемы алгоритма к ациклической форме.

2.4. Классификация бинарных отношений между вершинами алгоритма.

2.5. Уменьшение размерности решаемой задачи путем введения обобщенных вершин

2.6. Представление алгоритма управления в виде множества сечений
2.7. Практическая реализация операций над выражениями и их свойства
2.7.1. Представление выражений в виде деревьев.
2.7.2. Операция проверки принадлежности вершины дереву
2.7.3. Операция определения мощноста дерева.
2.7.4. Операция проверки отношения нестрого включения выражений гиэоморфизма деревьев.
2.7.5. Операция удаления изоморфпого поддерева
2.7.6. Операция вставки поддерева.
2.7.7. Операция раскрытия скобок
2.7.8. Операция удаления пропусков
2.8. Оценка интенсивности межблочных взаимодействий.
2.9. Синтез блоков разбиения с использованием множества сечений.
2 Алгоритм параллельнопоследовательного построения субоптимальпых разбиеиий
2 Оценка асимптотической временной и емкостной сложност и алгоритмов этапов и метода параллельнопоследовательной декомпозиции в целом
3. СТРУКТУРНОФУНКЦИОНАЛЬНАЯ ОРГАНИЗАЦИЯ АКСЕЛЕРАТОРА ОПЕРАЦИЙ НАД ВЫРАЖЕНИЯМИ.
3.1. Особенности аппаратноориентированного табличного представления Двыражений
3.2. Структурнофункциональная организация комбинаторнологического акселератора
3.3. Однородная среда для хранения электронной модели дерева
3.4. Загрузка данных в ОСЭМД
3.5. Комбинационные схемы формирования и преобразования оптовых последовательностей .
3.5.1. Схема подсчет бит СПБ
3.5.2. Схема маскировки неиспользуемых позиций СМНП.
3.5.3. Схема сравнения битовых векторов ССБВ
3.5.4. Схемы выделения заданных граничных значении
3.5.5. Схема определения типа соответствия предка СОТСП.
3.6. Операция определения принадлежности вершины дереву
3.7. Операция определения мощности дерева
3.8. Операция проверки отношения нестрогого включения
3.9. Операция удаления поддерева.
3 Операция вставки поддерева.
3 Операция раскрытия скобок
3 Операция удаления пустых позиций пропусков.
4. ЭКСПЕРИМЕТНАЛЬНЫЕ ИССЛЕДОВАНИЯ И ОЦЕНКИ.
4.1. Программноаппаратный комплекс для синтеза разбиений параллельных алгоритмов управления.
4.2. Синтез выборки алгоритмов управления со случайной структурой
4.3. Сравнение качества решений методов синтеза разбиений на выборках случайных алгоритмов.
4.4. Оценка аппаратной сложности акселератора
4.5. Оценка быстродействия акселератора
ЗАКЛЮЧЕНИЕ.
БИБЛИОГРАФИЧЕСКИЕ СПИСОК
ПРИЛОЖЕНИЕ.
ВВЕДЕНИЕ
Актуальность


К ним относятся классические задачи комбинаторики задача о расстановке ладей или ферзей на шахматной доске, задача об укладке рюкзака и т. Они имеют схожую комбинаторную природу и решаются точно по крайней мере, в теории с использованием математического аппарата выборок . Второе направление задач зачастую имеет скорее хрестоматийное, фундаментальное значение несмотря на то, тгго многие прикладные задачи могут бьггь сведены к задачам этого направления непосредственно или с небольшими модификациями. Например, одной из задач, решаемых оптимизирующими компиляторами, является задача оптимального размещения переменных в ограниченном множестве регистров процессора, сводимая к задаче отыскания минимальной раскраски графа . Методы первого направления имеют непосредственное практическое применение и весьма важное значение, выражающееся в первую очередь в уменьшении стоимости компоновка элементов и топология их межсоединений на печатных платах или в составе микросхем или повышении быстродействия мультипроцессорные системы готовых изделий за счет отыскания более близких к оптимуму решений. Поиск оптимальных решений обозначенных задач зачастую возможен лишь в теоретическом плане ввиду их ЛРполноты и, следовательно, экспонешщального или факториального роста временных затрат с ростом размерности решаемой задачи. На практике при этом обычно ограничиваются использованием эвристических алгоритмов, характеризующихся полиномиальными временными затратами на поиск решения и обеспечивающими пусть и не всегда оптимальное, но зачастую достаточно близкое обычно уступающее оптимальному порядка нескольких процентов в значении оптимизируемого интегрального критерия к нему решение за приемлемое время. О я3 достаточно мало распространены на практике . Однако даже полиномиальные алгоритмы, относительно быстро решающие небольшие размерностью порядка 0 4 задачи, могут потребовать очеггь больших временных затрат при решении задач большой размерности, к которым, в частности, относятся задачи трассировки межсоединений элементов современных СБИС мри разработке заказных микросхем насчитьшающих на данный момент уже более 2 миллиардов транзисторов или размещении их функционально законченных фрагментов при ПЛИС реализации насчитывающих на данный момент до миллионов вентилей . В таком случае обычно используются два существенно различных подхода, целью которых является уменьшение вычислительного времени при сохранении качества получаемых решений. Первый из них заключается в распараллеливании алгоритмов решения задачи или разработке специализированных хорошо распараллеливаемых модификаций известных методов с использованием различных форм параллелизма крупноблочного, векторного БМО и т. Примерами решения подобных задач являются, например, задача об укладке рюкзака и применяемый дя ее параллельного решения модифицированный метод ГоровицаСахни, адаптированный под параллельную многопроцессорную реализацию , или задача о выполнимости заданной булевой функции отыскании решений уравнения Х 1, где булева функция, а X ,, х2,. Многие физические задачи, обычно описываемые системами дифференциальных уравнений например, задачи моделирования климата и предсказания погоды , распространения теплопроводности, электрических или механических воздействий в различных средах, задачи геологической разведки , также допускают эффективное решение при переходе к параллельной редшзации. Достаточно интересным направлением является получающее все большее распространение использование гридтехнологий, когда вместо создания специализированного суперкомпьютера или вычислительного кластера решением задачи занимаются разрозненные и в общем случае географически удаленные друг от друга компьютеры. В качестве вычислительных элементов подобных систем кроме специализированных могут выступать домашние ши офисные машины пользователей участников проект известно, что большую часть рабочего времени вычислительные ресурсы машин подобного класса простаивают или имеют очень низкую загрузку, чго позволяет проводить необходимые вычисления в фоновом режиме, не мешая работе пользователя.