BC/NW 2009; №2 (15):4.1

ПАРАЛЛЕЛЬНАЯ ПОТОКОВАЯ ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА: АНАЛИЗ И МОДЕЛИРОВАНИЕ РАБОТЫ ВЫЧИСЛИТЕЛЬНОГО КОНВЕЙЕРА

Цветков В.В.

(ИППМ РАН, Москва, Россия)

Параллельная потоковая вычислительная система (ППВС) представляет собой гибридную архитектуру, совмещающую традиционный фон-неймановский принцип вычислений и принцип потока данных [1].

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

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

Базовым элементом ППВС является ядро, представляющее связанные между собой модуль ассоциативной памяти (МАП) и исполнительное устройство (ИУ). Ядра объединены через коммуникационную среду.

Целью работы является исследование работы вычислительного конвейера ППВС, анализ влияния параметров устройств ядра системы и параметров коммуникационной среды на время выполнения программы.

Структурная схема ППВС представлена на рис.1

Рис. 1. Структурная схема ППВС

Ядро системы включает в себя модуль ассоциативной памяти (МАП), буфер готовых пар (БГП), блок хеширования (ХЭШ), буфер готовых токенов (БГТ), блок параллельно работающих исполнительных устройств (ИУ) и внутренний коммутатор ядра (ВKM), через который осуществляется связь ядра с коммуникационной системой.

Сформированные в модуле МАП пакеты, содержащие указатель на программу узла, направляются для выполнения в исполнительное устройство ядра. В результате обработки пакета, на выходе исполнительного устройства генерируются токены, которые через внутренний коммутатор ядра направляются либо в коммуникационную среду, либо в МАП «своего» ядра. По модулям МАП в различных ядрах системы токены распределяются через коммуникационную среду по номеру ядра, вычисляемому в блоке хеширования в соответствии с функцией распределения.

Исследование работы ППВС проводилось на программной модели системы [2]. В работе приводятся результаты, полученные при моделировании работы системы, конфигурация которой показана на рис. 2.

Система включает набор из 16 ядер, объединенных через двухступенчатую коммуникационную среду, включающую коммутаторы КМ1и KM2. Входные токены, сформированные в устройстве ХОСТ, распределяются по ядрам системы через мультиплексор МП.

Моделирование было проведено на пакете тестовых программ обработки изображений. В данной работе в качестве примера приводятся результаты моделирования работы системы для программы пространственного усредняющего фильтра на изображении размером 32х32 элемента [3].

Рис. 2 Конфигурация моделируемой системы.

Конвейер ядра представляет собой циклическую структуру. При высоком уровне распараллеливаемости программы все ступени конвейера работают одновременно, и время выполнения программы определяется работой наиболее “медленного” звена конвейера

В рассматриваемой гибридной системе потоковой модели вычислений, на каждую операцию в АП в результате которой формируется пакет, затрачивается более одной операции в ИУ для обработки данных этого пакета. Это приводит к тому, что ИУ в конвейере обычно является наиболее “медленным” устройством, ограничивающим время выполнения программы. Преодолеть это ограничение можно, увеличивая количество ИУ в ядре, обеспечив при этом их параллельную работу. Принципиально, параллельную работу нескольких ИУ в ядре можно реализовать, поскольку формируемые в АП пакеты являются независимыми друг от друга.

На рис.3 показана зависимость коэффициента ускорения работы ядра (К_{У_Я}) от количества ИУ. Коэффициент ускорения определялся как отношение времени выполнения программы при одном ИУ в ядре ко времени выполнения программы при заданном (К_ИУ) количестве исполнительных устройств в ядре.

На начальном этапе коэффициент ускорения растет по линейному закону. Этот участок зависимости соответствует случаю, когда время работы конвейера ограничено блоком исполнительных устройств.

Максимальный диапазон изменения количества ИУ, внутри которого наблюдается увеличение К_{У_Я}, определяется отношением времени обработки узлов (включая время приема и предобработки пакета в ИУ и время выполнения программы узла) к интервалу времени между поступлениями пакетов в ИУ. На рис.3 этому случаю соответствует кривая 1. Максимальное количество активных ИУ в этом примере равно 9, которые обеспечивают 9-ти кратное ускорение работы ядра. Работа конвейера ограничивается в этом примере устройством МАП.

Рис. 3. Зависимость коэффициента ускорения ядра от количества ИУ

В некоторых случаях, в зависимости от параметров устройств конвейера, ограничение роста коэффициента ускорения может наблюдаться внутри указанного диапазона, если время работы конвейера начинает ограничиваться каким-либо другим устройством, у которого активное время работы превышает активное время работы МАП. В качестве примера, на рис.3 приведена зависимость 2, полученная при моделировании работы ядра с увеличенным временем работы блока ХЭШ. Максимальное количество активных ИУ в ядре в этом случае равно 6 и определяются ограничением, которое накладывается блоком ХЭШ на работу конвейера.

С увеличением количества ядер структура конвейера становится более сложной. Из простого циклического конвейера, как в случае одного ядра, при увеличении количества ядер конвейер преобразуется в параллельно-циклический конвейер с обменом данными между отдельными параллельно работающими кольцами. Одновременно с кольцами конвейера ядра начинают работать кольца, дополненные одной или двумя ступенями, связанными с коммуникационной системой.

Рис.4 Зависимость времени выполнения программы от Т_КОМ

Было проанализировано влияние параметров коммутаторов КМ1 и КМ2 на время выполнения программы. На рис.4 приведены зависимости, выраженные в количестве тактов моделирования, времени выполнения программы (Т), от времени коммутации (T_КОМ) в коммутаторах первого или второго уровня для системы с конфигурацией, включающей 16 ядер. Зависимость 1 получена при одном исполнительном устройстве в ядре, а зависимость 2 – при 32 ИУ. Обе зависимости имеют плоский начальный участок, соответствующий ситуации, когда время выполнения программы не зависит от значения параметра T_КОМ. На этих участках работа конвейера ограничивается либо ИУ для зависимости 1, либо МАП для зависимости 2. При дальнейшем увеличении параметра T_КОМ обе зависимости выходят на наклонный участок, соответствующий ограничению времени работы конвейера коммуникационной системой. Угол наклона прямой определяется количеством коммутируемых токенов.

Устройство, ограничивающее время работы конвейера можно определить из диаграмм интегральной загруженности устройств системы, которые приведены на рис.5.

Интегральная загруженность устройств (Р) определялась как отношение активного времени работы устройства ко времени моделирования. Активное время оценивается как минимальное время, которое может быть затрачено устройством для выполнения его доли работы в программе, при заданных установках параметров устройств конвейера. Например, для блоков МАП, активное время работы вычисляется как произведение среднего количества токенов, обработанных в каждом модуле МАП на время обработки одного токена.

На рис.5 приведены три диаграммы a), b) и c). На диаграммах a) и b) показана загруженность устройств системы при нулевом значении времени коммутации. Эти диаграмма соответствует начальным точкам на зависимостях 1 и 2 на рис.4. На диаграмме с) показана загруженность устройств при T_КОМ =12, то есть на наклонном участке зависимостей 1 и 2. Из рисунка видно, что при T_КОМ = 0, при одном ИУ в ядре максимально загруженным устройством в конвейере является ИУ, а при 32ИУ - МАП. При увеличенном времени коммутации максимально загруженным устройством, определяющим время выполнения программы, становятся коммутаторы.

Рис.5 Диаграмма интегральной загруженности устройств

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

Литература

1. А.Л. Стемпковский, Н.Н. Левченко, А.С. Окунев, В.В. Цветков Параллельная потоковая вычислительная система – дальнейшее развитие архитектуры и структурной организации вычислительной системы с автоматическим распределением ресурсов // Информационные технологии №10, 2008, с.2.

2. Левченко Н.Н., Окунев А.С., Змеев Д.Н. Расширение возможностей поведенческой блочно-регистровой модели параллельной потоковой вычислительной системы // Материалы Пятой Международной молодежной научно-технической конференции «Высокопроизводительные вычислительные системы (ВПВС 2008)», 2008, Таганрог, Россия, с. 371 – 374.

3. В.В. Цветков, Т.И. Гайдаенко // Вопросы адаптации вычислительной системы с автоматическим распределением ресурсов для решения задач линейной фильтрации изображений в пространственной области // Вестник компьютерных и информационных технологий. №12 2008.