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

• Автор: Бобынцев, Денис Олегович
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Курск
• Количество страниц: 146 с. : ил.

Оглавление
Введение
Г лава 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.2.1. Оценка степени уменьшения коммуникационной задержки и степени её близости к нижней оценке
3.2.2. Оценка реальной производительности вычислительной системы при планировании размещения подпрограмм
3.3.3. Оценка времени программной реализации алгоритмов планирования размещения
3.3. Выводы по главе

Глава 4. Акселератор вычислительного процесса определения коммуникационной задержки
4.1. Структурно-функциональная организация акселератора вычислительного процесса определения коммуникационной задержки
4.2. Организация блока определения промежуточных значений коммуникационной задержки
4.3. Оценка времени определения коммуникационной задержки и аппаратной сложности 2 и 3 ступени акселератора
4.4. Выводы по главе
Заключение
Библиографический список
Приложение А
Приложение В
Приложение С
Приложение Б

Введение
Актуальность темы. Создание многопроцессорных вычислительных систем (ВС) является одним из наиболее важных приоритетов развития вычислительной техники. Данные системы нашли применение при решении вычислительных задач, которые имеют ограничения по времени выполнения. Частный случай таких систем - матричные мультипроцессоры (ММГТ), которые являются перспективным базисом для построения систем реального времени (СРВ). Сочетание в архитектуре ММП таких свойств, как параллельность и однородность, создает необходимые условия для реализации комплексных алгоритмов теоретически неограниченной сложности, а устойчивость ММП к отказам отдельных процессоров и межпроцессорных каналов связи обеспечивает повышенный уровень надежности ВС. Многомодульность позволяет повысить производительность ВС при сопоставимой тактовой частоте процессорных модулей и умеренном энергопотреблении.
Одной из важных задач в ММП является планирование размещения подпрограмм по множеству обрабатывающих процессоров. Целью планирования является минимизация величин коммуникационных задержек при передаче данных между процессорами, что особенно важно при решении сильносвязных задач. Длинные составные и перекрывающиеся маршруты транзитной передачи данных приводят к возрастанию коммуникационных задержек, что существенно снижает реальную производительность ВС.
Теория параллельной организации и планирования размещения подпрограмм в многопроцессорных системах достаточно широко разработана. Большой вклад в эту область внесли работы отечественных и зарубежных ученых: В.П. Гергеля, A.B. Каляева, И.А. Каляева, И.И. Левина, И.В. Зотова, Вл.В. Воеводина, В.В. Воеводина, В.М. Курейчика, Д. Гроссмана, Р. Хокни, М. Бергера и др. В данных работах вопросы минимизации величин коммуникационных задержек рассматривались, но без
В основе алгоритмов планирования размещения лежит метод целенаправленных перестановок подпрограмм, позволяющий многократно ускорить процесс планирования размещения за счёт допустимого снижения оптимальности получаемого варианта размещения. При этом используется минимаксный критерий поиска варианта размещения, заключающийся в выборе такого варианта размещения подпрограмм, при котором максимальная коммуникационная задержка во всевозможных парах процессоров минимальна. Недостатком данного метода, как было сказано в п. 1.4, является отсутствие учёта перекрывающихся маршрутов передачи данных, которые могут привести к существенному увеличению задержки после маршрутизации.
В то же время анализ перекрывающихся маршрутов предполагает обработку больших объёмов данных при большом количестве процессоров, что существенно увеличивает вычислительную сложность задачи определения коммуникационной задержки. Поэтому актуальной задачей является аппаратная реализация определения коммуникационной задержки, предполагающая анализ топологии вычислительной системы и учёт перекрытий маршрутов передачи данных.