Ethan Frome

Современные информационные технологии/1. Компьютерная инженерия

Д-р техн. наук И.И. Левин, канд. техн. наук А.К. Мельников

НИИ многопроцессорных вычислительных систем имени академика

А.В. Каляева Южного федерального университета, г. Таганрог

levin@mvs.tsure.ru, mvs@mvs.tsure.ru

УПРАВЛЕНИе ГИБРИДНЫМИ ВЫЧИСЛИТЕЛЬНЫМИ СИСТЕМАМИ НА ЯЗЫКЕ SET@L*

Для гибридных высокопроизводительных вычислительных систем, приходящих согласно последним спискам ТОР-500 на смену кластерным системам, построенным из однородных процессорных узлов, необходимо изменить парадигму программирования. Для широко распространенных кластерных систем прикладная программа представляет собой множество последовательных процессов, каждый из которых реализовывался на отдельном процессорном узле. Для взаимосвязи последовательных процессов используются специальные протоколы MPI или OpenMP, ориентированные на систему передачи сообщений или использование общих ресурсов, как правило, общей оперативной памяти вычислительного комплекса. Для гибридных высокопроизводительных систем подобные технологии неэффективны. Вычислительные поля, построенные на основе взаимосвязанных кристаллов ПЛИС, имеют реальную производительность в десятки тысяч раз выше, чем процессорные узлы. Кроме того, не существует информационных каналов обменов в процессорных узлах, обеспечивающих передачи данных со скоростями в десятки Тбайт/с, как в реконфигурируемых системах.

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

Обе концепции построения вычислительных систем из универсальных процессоров или вычислительных полей на основе ПЛИС имеют как достоинства, так и недостатки. Для традиционных многопроцессорных систем, что признают все ведущие специалисты в области высокопроизводительных вычислений, имеются фундаментальные ограничения, не позволяющие для сильносвязанных задач, алгоритмы которых требуют большого числа межпроцессорных обменов, добиться высокой реальной производительности, близкой к пиковой. Реальная производительность кластерных систем при решении сильносвязанных задач составляет не более 10% от декларируемой пиковой производительности систем. Это связано с тем, что организация параллельного вычислительного процесса требует большего времени, чем его непосредственное исполнение.

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

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

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

Известно, что не все фрагменты прикладных программ эффективно выполнять структурно. К таким фрагментам относятся: вложенные условные операторы; информационно незначимые пересылки данных; рекурсивные функции. Такие фрагменты алгоритмов целесообразно реализовать процедурно. Однако не обязательно выполнять процедуры на универсальных процессорах. Это могут быть софт-процессоры, построенные на основе ПЛИС-технологии, структура и система команд которых ориентированы на выполнение конкретной вычислительной процедуры. Процессоры в высокопроизводительных гетерогенных системах не реализуют вычисления, но управляют вычислительным процессом.

Таким образом, возникает необходимость разделения прикладной задачи на вычислительную и управляющую части. При этом необходимо ориентироваться на парадигму ресурсонезависимого программирования: прикладная программа должна быть реализуемой на гибридных высокопроизводительных вычислительных системах различных архитектур и конфигураций: для вычислительных компонентов, ориентированных на решение прикладных задач на полях ПЛИС, эта проблема была решена в рамках работ [1, 2]. В то же время для управляющих частей прикладных программ, реализуемых на гибридных вычислительных комплексах, эта проблема остается открытой.

Целью ресурсонезависимого программирования гибридных вычислительных систем являются:

- возможность не изменять управляющие программы каждый раз под новую конфигурацию системы;

- возможность не переделывать программы под новую архитектуру системы.

Для обеспечения подобных возможностей необходимо рассматривать вычислительный ресурс системы как виртуальный, аналогично тому, как в традиционных вычислительных системах выступает оперативная память.

Для реализации парадигмы ресурсонезависимого программирования создан язык SET@L. Данный язык ориентирован на представление не информационных массивов, а множеств. Язык SET@L базируется на известном языке множеств SETL, в то же время между указанными языками имеется ряд существенных различий.

Язык SETL был предназначен для реализации на универсальных процессорах. Осуществлялась трансляция с теоретико-множественного описания алгоритма задачи последовательностью команд процессоров фон-неймановской архитектуры. Язык SET@L предназначен для реализации информационных графов (подграфов) на множестве взаимосвязанных кристаллов ПЛИС, поэтому параллельное теоретико-множественное представление параллельного алгоритма без семантического разрыва отображается на архитектуру гибридного вычислительного комплекса.

Кроме того, в язык SET@L введены новые понятия: горизонт, информационная неразличимость. Эти нововведения являются необходимыми для компактного и ресурсонезависимого описания информационных графов прикладной задачи. Если дана четко выделенная совокупность объектов, которая имеет некоторую индивидуальность, целостность и идентичность, то такой объект в языке SET@L является множеством, а элементы подобной совокупности являются элементами множеств. Особых свойств у элементов множества в языке SET@L не существует, участие объектов создания множества сводится к их простому присутствию. В то же время совокупностью своих элементов множество однозначно определено. Справедливо и обратное утверждение: множество однозначно определяет совокупность своих элементов и каждый элемент в отдельности. Таким образом, элементы и множества не переходят друг в друга, появляется возможность построения множества множеств. Ниже показан пример вычисления мощности множества, в котором цикл обеспечивается не процедурой последовательного изменения индекса элемента массива, а принадлежностью некоторого элемента множеству.

Set(Y) of number;

M(Y); n := 0; for x in Y do n := n+1; end; return n;

Помимо множеств, в языке SET@L существуют и другие информационные конструкции: подмножества, классы, подклассы.

Конечно, перечислимыми являются классы, чьи элементы можно однозначно занумеровать натуральными числами, меньшими некоторого наперед заданного натурального числа. Такое число однозначно определяется классом X и называется числом элементов класса X. Классы описываются с помощью специальных программных конструкций Сlsfin (Z) of Set type1, type2…

Универсум наследственно конечных множеств: X есть наследственно конечный класс, если существует класс T такой, что XÎ T и отношение R для которого справедливо Fin(T), Trans(T), ("Y, ZÎT)(YÎZ Þ YRZ & Y¹Z), причем R есть линейное упорядочение класса T, и каждое непустое множество класса T имеет в упорядочении R первый и последний элемент, описываемый следующим образом: UСlsfit (Z) of Сlsfin1, Сlsfin2…

Ниже приведен пример определения мощности вложенного множества. Здесь вложенные циклы определяются не изменением индексов многомерного массива, а принадлежностью множества множеств и определенному множеству.

MM(Y);

Set(Y) of Сlsfit(Z);

n := 0;

for X in Y do

for z in X do n := n+1; end;

end;

return n;

В языке SET@L возможно определение G:FN®V произвольной функции, для которой последовательность G(0), G(1), G(2) задает определенное направление горизонту, ограничивающего наблюдение, причем если классом наследственно конечных множеств стал класс F*V, то эта последовательность как целое исчезла бы, но ее отдельные члены и заданное ею направление не исчезнут. Считается, что определенная функциональная последовательность хотя бы на некотором продолжении за горизонтом будет плавно продолжаться. В то же время данная последовательность четко прервется либо где-то за горизонтом, либо будет уходить к новому горизонту. Это утверждение прагматично можно понимать следующим образом: пользователь может представить не только процесс в некоторый момент времени в указанном направлении, но и будет в состоянии анализировать его тогда, когда не будет в состоянии наблюдать в точности те состояния, которые наблюдает сейчас. Это значит, что пользователь может в дальнейшем анализировать процесс в развитии, хотя не сможет восстановить исходный процесс.

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

Нor V;

Function F of number to V(N);

Function g sub of F;

Set(Z:F) of number ;

n include Z if { notexist k < n & div(n,k )}

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

Анализ приведенных данных и уровня производительности современных вычислительных средств показывает, что точные распределения статистик еще долгое время не могут быть рассчитаны,

В основу метода расчета D-точных распределений могут быть положены теоретические результаты по оценке распределения вероятностей значений статистики максимальной частоты Mn = hi, позволившие ограничить мощность множества, на котором происходит расчет значений исследуемых статистик, и сделать его перечислимым за приемлемое время. Пусть для некоторого AÎ R1 необходимо вычислить с точностью D вероятность P{ Sn (x) Î A }, где х - выборка объема n из равновероятного полиномиального распределения, A - некоторое множество. Основываясь на равенстве P{ Sn (x) Î A } = P{ Sn (x) Î A, Mn >m } + P{ Sn (x) Î A, Mn £ m }, подберем m так, чтобы P{ Mn >m } £ D. Тогда 0 £ P{ Sn (x) Î A } - P{ Sn (x) Î A, Mn £ m } £ D .

Вычислять вероятность P{ Sn(x) Î A, Mn £ m } значительно легче, чем исходную вероятность P{ Sn(x) Î A } для m, чтобы P{ Mn > m } £ D .

Подобные методы распределения вычислительных ресурсов могут быть компактно описаны на языке SET@L и без семантического разрыва отображены как на вычислительные компоненты – ПЛИС, так и на управляющие компоненты – процессоры.

Литература:

1. Каляев А.В., Левин И.И. Модульно-наращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. - Москва: Изд-во “Янус-К”, 2003. - 380 с.

2. Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. Реконфигурируемые мультиконвейерные вычислительные структуры /Изд. 2-е, перераб., доп. / Под общ. ред. И.А. Каляева - Ростов-на-Дону: Изд-во ЮНЦ РАН, 2009. – 344 с. ISBN 978-5-902982-61-6.

______________________________________

*Работа выполнена при финансовой поддержке Министерства образования и науки РФ по Соглашению о предоставлении субсидии №14.578.21.0006 от 05.06.2014, уникальный идентификатор RFMEFI57814X0006, гранту Южного федерального университета №213.01-2014/014 и НИР №2257 базовой части государственного задания №2014/174.