Устройство и процедура барьерной синхронизации процессов в мультикомпьютерах

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

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. ЗАДАЧИ СИНХРОНИЗАЦИИ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ

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

1.2. Межпроцессорное взаимодействие в параллельных системах

1.3. Задача синхронизации и подходы к ее решению

1.4. Методы барьерной синхронизации Выводы

2. ПРОЦЕДУРА БАРЬЕРНОЙ СИНХРОНИЗАЦИИ И АЛГОРИТМ ВЗАИМОДЕЙСТВИЯ СИНХРОНИЗИРУЕМЫХ ПРОЦЕССОВ

2.1. Модель параллельной системы

2.2. Содержательная характеристика и формализованное представление задачи обеспечения синхронизации

2.3. Характеристика процедуры синхронизации

2.4. Алгоритм взаимодействия синхронизируемых процессов
2.5. Примеры использования процедуры синхронизации Выводы
3. УСТРОЙСТВО СИНХРОНИЗАЦИИ НА ОСНОВЕ СОЗДАННОЙ ПРОЦЕДУРЫ
3.1. Функциональная организация матричной МРРсистемы
3.2. Анализ работы системы при рассмотрении соответствующих режимов функционирования процессоров
4. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ СОЗДАННОЙ ПРОЦЕДУРЫ И ОЦЕНКА ПРЕИМУЩЕСТВ РАЗРАБОТАННОЙ ПРОЦЕДУРЫ И УСТРОЙСТВА
4.1. Представление процедуры синхронизации в виде сети Петри
4.2 Доказательство корректности процедуры синхронизации
4.3 Аналитическая оценка аппаратной сложности устройства синхронизации
4.4 Аналитическая оценка созданной процедуры синхронизации
4.5 Экспериментальная оценка созданной процедуры синхронизации
4.5.1. Постановка эксперимента
4.5.2. Архитектура экспериментальных программных средств
4.5.3. Результаты эксперимента
Выводы
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
Приложения
ВВЕДЕНИЕ
Актуальность


Системы с распределенной памятью и синхронизацией через разделяемые переменные, как в BBN Butterfly, называются гибридными архитектурами (класс 2). Системы, в которых память распределена по процессорам, а для взаимодействия и синхронизации используется механизм передачи сообщений он называет архитектурами с передачей сообщений, например NCube, (класс 3). В качестве уточнения классификации Джонсон отмечает возможность учитывать вид связи между процессорами: общая шина, переключатели, разнообразные сети и т. Основным параметром классификации параллельных ВС является наличие общей (SMP) или распределенной памяти (МРР). ВС с SMP-архитектурой (symmetric multiprocessing) симметричная многопроцессорная архитектура. Главной их особенностью является наличие общей физической памяти, разделяемой всеми процессорами. Память является способом передачи сообщений между процессорами, при этом все вычислительные устройства при обращении к ней имеют равные права и одну и ту же адресацию для всех ячеек памяти. Поэтому SMP-архитсктура называется симметричной. Наиболее известными SMP-системами являются SMP-сервсры и рабочие станции на базе процессоров Intel (IBM, HP, Compaq, Dell, ALR, Unisys, DG, Fujitsu и др. ВС с МРР-архитектурой (massive parallel processing) -массивно-параллельная архитектура. Главная особенность такой архитектуры состоит в том, что память физически разделена. В этом случае система строится из отдельных модулей, содержащих процессор, локальный банк оперативной памяти (ОП), два коммуникационных процессора (роутера) или сетевой адаптер, иногда -жесткие диски и/или другие устройства ввода/вывода. По сути, такие модули представляют собой полнофункциональные компьютеры. Доступ к банку ОП из данного модуля имеют только процессоры из этого же модуля. Модули соединяются специальными коммуникационными каналами. Пользователь может определить логический номер процессора, к которому он подключен, и организовать обмен сообщениями с другими процессорами. Главным преимуществом систем с раздельной памятью является хорошая масштабируемость: в отличие от SMP-систем в машинах с раздельной памятью каждый процессор имеет доступ только к своей локальной памяти, в связи с чем не возникает необходимости в потактовой синхронизации процессоров. Практически все рекорды по производительности на сегодняшний день устанавливаются на машинах МРР-архитектуры, состоящих из нескольких тысяч процессоров (ASCI Red, ASCI Blue Pacific) [3]. Именно такие ВС и являются объектом рассмотрения в настоящей работе. МРР систем, являются средства обмена данными между процессором и оперативной памятью, процессором и другими устройствами, между различными процессорами. Организация внутренних коммуникаций вычислительной системы определяется се топологией. Статические системы с шинной организацией позволяют минимизировать число межмодульных линий связи (рис. Достоинством такой организации является практическая независимость числа межмодульных соединений от числа процессорных элементов (ПЭ), а также простота подключения дополнительных Г1Э. ВС не позволяют объединять значительное (N> - ) число ПЭ. Эго обусловлено критичностью системы к росту межпроцессорного обмена, а также ограничениями электрического характера. Другим недостатком шинных структур является низкая надежность, которая фактически определяется надежностью общей шины. Одним из путей совершенствования структур с общей шиной является использование ВС с мультишинной организацией, включающих N’>1 шин. Однако, несмотря на повышенную надежность, мультишинная организация обладает высокой удельной сложностью. Например, при использовании Ы' = N общих шин затраты на каналы связи зависят от размерности ВС как 0(И2). Другим способом совершенствования структур с общей шиной является переход к иерархическим шинным ВС [4] (рис. ПЭ на совокупность не сравнимых по включению пересекающихся подмножеств, каждому из которых соответствует собственная общая шина. Обмен информацией между ПЭ, входящими в различные подмножества таких систем, производится за счет транзитной передачи сообщений через общие для этих подмножеств элементы.