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

• Автор: Борзов, Дмитрий Борисович
• Шифр специальности: 05.13.05
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Курск
• Количество страниц: 180 с. : ил

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

1. Задачи, модели и методы оптимального размещения.

1.1 Архитектура современных параллельных систем

1.1.1 Архитектура массивнопараллельных компьютеров на примере 3

1.1.2 Системы с неоднородным доступом к памяти на

примере II .

1.1.3 Массивнопараллельная система I

1.2 Размещение задач в параллельных системах

1.2.1 Топологии параллельных систем и их роль в решении задачи размещения

1.2.2 Формулировка задачи размещения для параллельных систем.

1.3 Классификация моделей и методов оптимального размещения.
1.4 Анализ моделей и методов размещения в коммутационномонтажном проектировании.
Выводы.
2 оптимальное размещение задач в кольцевых параллельных системах
2.1 Формализованная постановка задачи.
2.2 Общие принципы решения .
2.3 Процесс оптимального размещения.
2.4 Получение нижней оценки длины маршрутов между задачами
2.5 олучение нижней оценки интенсивности межмодульных взаимодействий.
2.6 Описание процедуры оптимальною размещения.
2.6.1 Процедура оптимального размещения
2.6.2 Пример работы процедуры
2.7 Анализ эффективности процедуры
3 Размещение задач в параллельных системах с матричной организацией
3.1 Модель параллельной системы и размещения алгоритмов
3.2 Формализованная постановка задачи
3.3 Общие принципы решения.
3.4 Алгоритм поиска нижней оценки
3.5 Описание процедуры.
3.6 ример работы процедуры.
3.7 Анализ эффективности процедуры.
3.7.1 Постановка эксперимента.
3.7.2 Результаты эксперимента.
3.8 Выводы.
4 Аппартные модели и устройства оптимального размещения.
4.1 Принципы аппаратного моделирования задач размещения
4.2 Организация взаимодействия с акселератором
4.3 Аппаратное представление задачи.
4.4 Оценка предельных параметров размещения.
4.4.1 Модель для получения нижней оценки интенсивности взаимодействия подзадач в Г1С
4.4.2 Модель получения нижней оценки длины маршрутов взаимодействующих подзадач в ПС.
4.5 Аппаратная модель оптимального размещения задач в ПС с
кольцевой структурой.
4.6 Оценка временных свойств и аппаратных затрат моделей
4.7 Аппаратная реализация.
4.7.1 Устройство для оценки степени оптимальности размещения
4.7.2 Устройство для формирования субоптималыюго размещения и
ею оценки.
Выводы.
Заключение
Список литературы


К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через высокоскоростную коммуникационную среду. Компьютер CRAY T3D - это массивно-параллельный компьютер с распределенной памятью, объединяющий от до процессоров. В компьютерах с распределенной памятью нет общей шины, по которой можно обращаться к памяти. Каждый процессор обращается к собственной локальной памяти. Тот процессор, который хочет обратиться к памяти другого процессора, должен передать ему копии необходимых данных. Обычно такая передача данных называется передачей сообщений (message-passing) и получила практическое применение в программных библиотеках. Для запуска программы на таком компьютере необходимо решить, как должны быть распределены данные между локальной памятью каждого процессора. При таком подходе рост степени параллелизма невозможен. Ключевые циклы в программе будут требовать много структур данных; каждый при этом должен быть распределен так, чтобы выполнить этот цикл параллельно. Результат - бескомпромиссный подход к параллелизму па распределенных машинах памяти. В дополнение необходимо отметить, что много программных данных по своему размеру больше, чем отдельная локальная память, поэтому невозможно запустить программу без ее предварительного распараллеливания. I le-трудно понять, что в системах динамического размещения такая стратегия размещения неприменима. CRAY T3D подключается к хост-компьютеру, роль которого, в частности, может исполнять CRAY Y-MP С. Вся предварительная обработка и подготовка программ, выполняемых на CRAY T3D, проходит на хост-компьютере (например, компиляция). Связь хост-машины и T3D идет через высокоскоростной канат передачи данных. CRAY T3D имеет в своем составе три основные компоненты: сеть межпроцессорного взаимодействия (коммуникационную сеть), вычислительные узлы и узлы ввода/вывода. Вычислительный узел состоит из двух процессорных элементов (ПЭ), сетевого интерфейса, контроллера блочных передач. Оба процессорных элемента, входящих в состав вычислительного узла, идентичны и могут работать независимо друг от друга. Каждый ГТЭ содержит микропроцессор, локальную память и некоторые вспомогательные схемы. Микропроцессор - это -х разрядный RISC процессор ALPHA фирмы DEC, имеющий внутреннюю кэш-память команд и кэшпамять данных. Локальная память каждого процессорного элемента является частью физически распределенной, но логически разделяемой (или общей) памяти всего компьютера. В самом деле, память физически распределена, так как каждый ПЭ содержит свою локальную память. В то же время, память разделяется всеми ПЭ, так как каждый ПЭ может обращаться к памяти любого другого ПЭ, не прерывая его работы. Обращение к памяти другого ПЭ лишь в 6 раз медленнее, чем обращение к своей собственной локальной памяти. Сетевой интерфейс формирует передачи перед посылкой через коммуникационную сеть другим вычислительным узлам или узлам ввода/вывода, а также принимает приходящие сообщения и распределяет их между двумя процессорными элементами узла. Контроллер блочных передач - это контроллер асинхронного прямого доступа в память, который помогает перераспределять данные, расположенные в локальной памяти разных ПЭ компьютера СИЛУ ТЗП) без прерывания работы самих ПЭ. Коммуникационная сеть (рис. Сеть образует трехмерную решетку, соединяя сетевые маршрутизаторы узлов в направлениях X, У, 7. Каждая элементарная связь между двумя узлами - это два однонаправленных канала передачи данных, что допускает одновременный обмен данными в противоположных направлениях. Все узлы в коммуникационной сети в размерностях X и X расположены с чередованием, что позволяет минимизировать длину максимального физического соединения между ПЭ (рис. При выборе маршрута для обмена данными между двумя узлами сетевые маршрутизаторы сначала выполняют смещение по размерности Ху затем по У, а в конце по Z. Так как смещение может быть как положительным, так и отрицательным, то этот механизм помогает минимизировать число перемещений по сети и обойти поврежденные связи. Рис. Рис.