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

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

СОДЕРЖАНИЕ
Введение.

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. Средства программирования вычислительных устройств, построенных на основе ПЛИСтехнологии, сочетающих конвейерные и параллельные методы одновременной обработки
V информации
3.3. Реализация генетического алгоритма на вычислительном устройстве, построенном на основе ПЛИСтехнологии при сочетании параллельной и конвейерной одновременной обработки информации.
3.4. Выводы.
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Данная работа посвящена увеличению абсолютных значений верхней границы сложности обозначенного класса задач при фиксированных значениях нижней границы в условиях временных, материально-технических, массогабаритных и финансовых ограничений за счет повышения эффективности применения создаваемых проблемно-ориентированных ВС. Отметим, что задачи, попадающие в класс вычислительно-трудоемких, могут обладать существенно разными свойствами. Решение широкого класса вычислительно-трудоемких задач может требовать применения ВС, обладающих принципиально различными конфигурациями вычислительных ресурсов. По закону возрастания вычислительной сложности в зависимости от размера входных данных задачи принято делить на два класса: имеющие полиномиальную сложность и имеющие более чем полиномиальную (например, экспоненциальную) сложность. Отметим, что вычислительнотрудоемкими могут быть и те, и другие, но, как правило, задачи, имеющие более чем полиномиальную сложность, при меньшем размере входных данных попадают в класс вычислительно-трудоемких. Отметим, что увеличение размера задачи требует, как минимум, адекватного закону сложности увеличения аппаратных ресурсов. Понятно, что при решении задач с экспоненциальной сложностью увеличение размера входа приведет к экспоненциальному росту затрат на оборудование, а, следовательно, при заданных ограничениях задача может попасть в класс вычислительно-неразрешимых. Стремление к решению такой задачи диктует необходимость предъявления новых требований к применяемым вычислительным ресурсам, в том числе, к математическому обеспечению ВС. Классическим методом повышения производительности ВС за счет увеличения количества аппаратных ресурсов является реализация одновременного выполнения операций [8]. В настоящее время широко используются обе формы одновременных вычислений: распараллеливание и конвейеризация. Эти две формы отличаются, прежде всего, порядком обработки операндов. Для того чтобы дать корректное определение каждой из указанных форм, необходимо ввести понятия информационной зависимости и информационного графа задачи. Информационной зависимостью обычно называют такой тип связи между операторами программы, осуществляющими преобразование информации, при котором аргументом одного оператора являются результаты работы другого [9]. Под информационным графом задачи будем понимать такое графическое представление структуры программы, при котором каждому оператору, осуществляющему преобразование информации, соответствует некоторая вершина, а наличие или отсутствие ребра (связи между вершинами) определяется наличием или отсутствием информационной зависимости между операторами []. Таким образом, информационный граф программы является ориентированным ациклическим графом. ЯПФ). В этом случае вершины, осуществляющие преобразование информации, располагаются на ярусах, причем информационные связи существуют лишь между вершинами, принадлежащими разным ярусам. Число ярусов в ЯПФ называется ее высотой, а число вершин в самом широком ярусе - шириной ЯПФ. ЯПФ минимальной высоты называется максимальной []. Вернемся к формам одновременных вычислений. Определение 1. Параллельной обработкой называется частный случай одновременной обработки, когда каящое устройство системы независимо обходит вершины информационного графа задачи, причем в один момент времени обрабатываются только информационно-независимые вершины. Параллельной обработке характерно такое выполнение вычислений, при котором входные данные выполняющейся в конкретный момент на данном устройстве операции могут, в общем случае, содержать выходные данные операций, выполнявшихся на любых устройствах ВС в любые предшествующие моменты времени. Как правило, в этом случае каждое устройство обработки данных (процессор) выполняет свою программу или обрабатывает свою часть данных в соответствии с общей для нескольких процессоров программой. Такую организацию вычислений называют также мультипроцедурной. Отсутствие заданного заранее, на этапе проектирования ВС порядка обработки операндов существенно расширяет сферу эффективного применения данной формы одновременного выполнения операций при решении задач различных классов.