Типовые схемы коммуникации в многопроцессорных вычислительных системах.

Временные задержки при передаче данных в мультикомпьютерных системах могут быть существенными. Как результат, коммуникационная трудоемкость алгоритма оказывает существенное влияние на выбор параллельного способа решения задачи. Структура линий связи между процессорами (топология сети) определяется с учетом возможности эффективной технической реализации. Важную роль при этом играет анализ интенсивности информационных потоков.

Схемы: полный граф, линейка (труба), кольцо, звезда, двумерная решетка, трехмерная решетка. Полный граф – система, в которой между любой парой процессоров имеется прямая линия связи. Данная топология имеет минимальные затраты при передаче данных, но она сложно реализуема при большом числе процессоров. Линейка – система, в которой все процессоры перенумерованы по порядку, и каждый процессор, кроме первого и последнего, имеет связи с двумя соседями. Кольцо получается из линейки, если соединить первый и последний узел. В звезде все процессоры имеют связь с некоторым управляющим процессором или узлом. Эта структура эффективна при организации централизованных схем параллельных вычислений. Решетка – это система, в которой граф линий связи образует прямоугольную сетку.

Гиперкуб – данная топология представляет собой частный случай решетки, если в каждой размерности имеется только два процессора. Гиперкуб содержит 2^n процессоров. Данный тип характеризуется следующими особенностями: два процессора имеют соединения, если двоичное представление их номеров имеют только одну различающуюся позицию; в n-мерном гиперкубе каждый процессор связан с n соседями; n-мерный гиперкуб может быть разделен на 2 (n-1)-мерных гиперкуба; кратчайший путь между любыми двумя процессорами имеет длину, совпадающую с количеством различающихся битовых значений. Данная величина известна как расстояние Хэмминга. При построении кластерных систем очень часто используют коммутатор. В этом случае связь представляет полный граф. Однако одновременное выполнение нескольких коммуникационных операций является ограниченным. В данный момент времени каждый процессор может принимать участие только в одной операции приема-передачи. Из–за этого параллельно могут выполняться только те коммуникационные операции, в которых взаимодействующие пары процессоров не пересекаются между собой. Основными характеристиками различных топологий являются:

1. диаметр – показатель, определяемый как максимальное расстояние между двумя процессорами сети. Диаметр характеризует необходимое время для передачи данных между узлами.
2. связность – показатель, отражающий наличие разных маршрутов передачи данных между узлами. Может быть определен, как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области.
3. ширина бинарного деления – определяется как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера.
4. стоимость – определяется общим количеством линий передачи данных.

Классификация Хокни.

Множественный поток команд может быть обработан двумя способами: либо одним конвейерным устройством обработки, работающим в режиме разделения времени; либо каждый поток обрабатывается своим собственным устройством. В первом классе (переключаемые) находятся МВС, в которых возможна прямая связь каждого процессора с каждым. Во втором классе (сети) находятся МВС, в которых прямая связь процессора возможна только с ближайшими соседями по сети. При этом взаимодействие удаленных процессоров поддерживается системой маршрутизации. При рассмотрении сетевой организации дальнейшая классификация проводится в соответствии с топологией сети. Классификация Фенга.

Основана на 2 признаках: число битов в машинном слое, обрабатываемых параллельно; число слов, обрабатываемых одновременно. Функционирование любого компьютера представляется как параллельная обработка n-битовых слоев, на каждом из которых независимо преобразуются n бит. В этом случае вторая характеристика может быть названа шириной битового слоя. Каждую систему можно описать парой чисел. Их произведение определяет интегральную характеристику потенциала параллельности архитектуры или максимальную степень параллелизма. Иными словами это значение представляет собой пиковую производительность. Рассмотрим компьютер TI ASC. Работает с 64-разрядным словом, АЛУ имеет 64 слоя, параллельно обрабатываются 32 бита. Все МВС согласно этой терминологии можно разделить на 4 класса: разрядно-последовательные, пословно-последовательные – в каждый момент эти машины обрабатывают 1 двоичный разряд; разрядно-параллельные, пословно-последовательные; разрядно-последовательные, пословно-параллельные; разрядно-параллельные, пословно-параллельные. Недостаток этой классификации связан со способом вычисления ширины битового слоя, т.е. не делается различия, за счет чего обрабатывается более одного слоя. Если в системе находится n независимых процессоров, каждый имеет f конвейерных устройств с длиной конвейера l, то ширина будет определяется как их произведение.

Классификация Хендлера.

В ней заложено явное описание возможности параллельной и конвейерной обработки информации и не рассматриваются способы связи между узлами. Классификация основана на различии между тремя уровнями обработки данных: уровень выполнения программы – опираясь на счетчик команд, УУ проводит выборку и дешифрацию команд; уровень выполнения команд – АЛУ исполняет команду, выданную УУ; уровень битовой обработки – все элементарные логические схемы процессора (ЭЛС) разбиваются на группы, необходимые на выполнение операций над двоичным кодом. Предполагается, что МВС содержит несколько процессоров. Каждый обладает своим УУ. Каждое УУ связано с несколькими АЛУ, исполняющих одну и ту же операцию в данный момент времени. Каждое АЛУ объединяет несколько групп ЭЛС. Таким образом число устройств управления к, число АЛУ d и число групп ЭЛС w составляют тройку чисел для описания системы.

Ключевые элементы интерфейса OpenMP.

1. конструкции для создания потоков parallel.
2. конструкции для распределения работы между потоками Do/for/section.
3. конструкции для управления работы с данными shared, private.
4. конструкции для синхронизации потоков critical, atomic, barrier.
5. процедуры библиотеки поддержки времени выполнения omp_get_thread_num
6. переменные окружения omp_num_threads.

Для реализации параллельного выполнения блока в код программы добавляется директива pragma, а также используются функции библиотеки omp периода выполнения. OpenMP поддерживает директиву parallel, parallel for, section, sections, single, master, critical, flush, ordered, atomic. Они служат для задания механизмов разделения работы или синхронизации. Данная директива сообщает компилятору, что структурированный блок кода должен быть выполнен параллельно в нескольких потоках. Каждый поток будет выполнять один и тот же поток команд.

Условие гонки: в случае, если два или более потока одновременно пытаются изменить общие ресурсы, возникает условие гонки. Чтобы его избежать, используют средство блокировки и минимизируют обращение к общим ресурсам. Директива omp for относится к директивам разделения работы. В конце параллельного региона выполняется барьерная синхронизация. При разработки данные делятся на частные (private) и общие (shared). Общие данные доступны всем потокам из группы. Для частных переменных каждый поток данной группы располагает их отдельными экземплярами. В этой связи изменение в одном потоке никак не сказывается на копии в других потоках. По умолчанию все переменные в параллельном регионе общие, кроме индексов параллельных циклов for, локальных переменных блоков параллельных регионов, переменные разделов private, firstprivate, lastprivate, reduction. Раздел private говорит о том, что для каждого потока создается частная копия переменных, которая инициализируется значением по умолчанию. OpenMP используется для распараллеливания циклов, однако он поддерживает параллелизм и на уровне функций. Данный механизм называется секции. При одновременном выполнении нескольких потоков имеется необходимость синхронизации. Один из типов – неявная барьерная синхронизация. Выполняется в конце каждого параллельного региона. Этот вид выполняется в конце каждого блока pragma omp for, pragma omp single, pragma omp section. Второй тип – явная барьерная. Включается она при помощи ключевого слова barrier. В параллельных регионах часто встречаются блоки кода, доступ к которым желательно предоставлять только одному потоку. Для этого служит директива pragma omp single. Для завершения всех операций над памятью используется директива pragma omp flush. Директивы pragma должны обрабатываться всеми потоками из группы, либо вообще не обрабатываться.