Software technologies for homogenous computing environment.pdf Однородными вычислительными средами (ОВС) принято называть специализированные вычислительные системы, которые образованы из одинаково соединенных друг с другом универсальных вычислительных элементов, каждый из которых программно настраивается на выполнение арифметической или логической функции, а также функции соединения с соседними элементами [1, 2]. При этом под универсальным процессорным элементом (ПЭ), как правило, подразумевается однобитный процессор, выполняющий последовательную обработку данных, которые поступают на его входы от соседних процессоров. Основным достоинством однородных вычислительных сред является изначально присущий им массовый параллелизм вычислений. Кроме того, регулярность ОВС позволяет наращивать ее вычислительные возможности путем простого увеличения размеров матрицы, позволяя при этом организовать достаточно простые методы контроля и диагностики ОВС в процессе производства и эксплуатации. Избыточность, изначально присущая однородной среде, позволяет, благодаря наличию резервных элементов в схеме, обеспечить при необходимости высокую живучесть вычислительной системы. Указанные выше достоинства ОВС позволяют эффективно использовать их при построении функционально-ориентированных процессоров (ФОП) для систем реального времени. При этом номенклатура реализуемых алгоритмов может быть весьма велика: - цифровая обработка сигналов и изображений; - распознавание образов; - решение систем уравнений (алгебраических и дифференциальных); - логико-комбинаторные алгоритмы, прежде всего, сортировка и поиск. Программирование ОВС представляет собой технологический процесс настройки массива ПЭ на выполнение операций обработки и передачи данных, который завершается «укладкой» графа алгоритма в вычислительную решетку. Настоящая работа посвящена рассмотрению некоторых компонентов этого технологического процесса, а также проблемам, с которыми сталкиваются создатели подобных платформ. В первом разделе рассматриваются вопросы применимости универсальных языков для программирования параллельных вычислительных систем и сравниваются основные подходы, которые применяются при создании соответствующих программных платформ. Второй раздел посвящен анализу опыта применения традиционного подхода к созданию специальных языков программирования параллельных вычислительных систем. Специфические особенности программирования вычислительных систем, управляемых потоками данных, рассматриваются в третьем разделе. В четвертом разделе рассмотрен опыт реализации комплексного технологического процесса программирования потоковых вычислительных систем. В заключении дан краткий анализ перспектив применения современных параллельных программных средств для программирования ОВС. 1. Применение традиционных подходов для программирования однородных вычислительных систем 1.1. Адаптация традиционных языков программирования Достоинством данного подхода является возможность плавной миграции всего комплекса современных программных продуктов на новые высокопроизводительные параллельные вычислительные системы. Однако на сегодняшний день многочисленные проекты по созданию универсальных векторизующих компиляторов показывают обнадеживающие результаты только при решении весьма ограниченного класса задач [3], ни один из них не увенчался сколько-нибудь заметными успехами в распараллеливании последовательной программы произвольного вида [4-6]. «Параллельная невыразительность» традиционных языков программирования может быть устранена путем ввода специальных лексических конструкций, которые позволяют программисту описывать и организовывать параллельные вычислительные процессы. Как показывает опыт, при практической реализации данного подхода могут возникать очень серьезные трудности, которые применительно к параллельному языку HPF (High Perfomance Fortran) описаны в отчетной работе [7] группой основных разработчиков. Примечательно, что программисты в качестве основных недостатков указывали отсутствие возможности оценки (прогнозирования) времени выполнения программы HPF на конкретной вычислительной архитектуре. Сегодня наибольшее распространение получило применение параллельных расширений (диалектов) существующих последовательных языков для программирования вычислительных структур, которые имеют заранее определенную архитектуру, как правило, это кластеры универсальных процессоров или гибридные вычислители, состоящие из универсальных вычислителей и векторных сопроцессоров (GPU/CPU). Поскольку в этом случае вычислительные комплексы содержат компоненты с классической архитектурой, дополнительные преимущества при их программировании получают именно те платформы, которые максимально используют возможности последовательных языков программирования (Open CL, Open MP, UPC и т.д.). 1.2. Языки параллельного программирования Работы по созданию универсальных параллельных языков проводились компаниями Cray, SUN и IBM в период с 2002 по 2010 г. по заказу агентства перспективных проектов (Defense Advanced Research Projects Agency - DARPA) Министерства обороны США в рамках программы создания высокопроизводительных вычислительных систем (High Productivity Computing Systems - HPCS) и завершились представлением языков программирования Chapel (2009 г.), Fortress (2008 г.) и X10 (2004 г.) [8]. Эти языки основаны на модели разделяемого адресного пространства Partitioned Global Address Space (PGAS), причем X10 в большей степени, чем Chapel и Fortress, опирается на традиционный синтаксис и базовые понятия последовательных языков. Тот факт, что даже самый близкий к традиционным из указанных языков (Х10) не получил заметного распространения, разработчики объясняют неготовностью сообщества программистов жертвовать удобством процесса программирования ради повышения его эффективности [9]. В то же время приведенные в [10, 11] выводы о большей выразительности и универсальности Chapel по сравнению с X10 указывают на ограниченные возможности применения традиционных методов для программирования систем с массовым параллелизмом вычислений. В условиях отсутствия универсальных инструментов параллельные проблемно-ориентированные языки (ПОЯ) (Domain Specific Language - DSL) позволяют достичь требуемой эффективности и выразительности программирования за счет существенного сокращения области применения языков [12]. Применение ПОЯ, как правило, предполагает полную осведомленность программиста об особенностях организации вычислительного процесса в программируемом устройстве, что позволяет наиболее полно использовать специфические возможности данного вычислителя [14]. Поэтому ПОЯ в первую очередь оказываются полезными в качестве временного решения на этапе макетирования вычислительных систем [13]. 1.3. Перспективы применения традиционных программных средств для программирования ОВС Практически все рассмотренные выше языки, как и подавляющее большинство современных языков программирования, являются императивными и основаны на принципе обработки данных потоками команд (Control Flow). Повсеместное распространение императивных языков программирования определяется их точным соответствием требованиям и особенностям организации вычислительного процесса на вычислителях с классической архитектурой от фон Неймана. Однако в тех случаях, когда архитектура программируемого вычислителя отличается от классической, это преимущество императивных языков программирования превращается в недостаток, который будет проявляться тем сильнее, чем сильнее различаются архитектуры вычислителей. Например, применение императивных языков для программирования систем c архитектурой Data Flow, которую образует массив исполнительных устройств и устройств сопоставления соединенных с контекстно-адресуемым запоминающим устройством, вызывает серьезные проблемы, связанные с побочными эффектами и ограниченной доступностью данных [15]. Примечательно, что в последнее время создаются серьезные проекты, основанные на модели вычислений Data Flow. Так, в частности, разработчики крупного европейского проекта TERAFLUX по созданию высокопроизводительных вычислительных структур отмечают, что применение модели организации вычислительного процесса Data Flow позволяет максимально выявлять и использовать параллелизм вычислений и преодолеть ряд существенных ограничений, присущих традиционной модели Control Flow [16]. Эти результаты, безусловно, следует принимать во внимание при выборе системы программирования ОВС, поскольку модель организации вычислительного процесса Data Flow гораздо лучше, чем Control Flow, подходит для описания вычислений в ОВС, а форма графа потоков данных, используемая для указания информационных связей между операндами выражения, вычисляемого в системе DataFlow, по сути, представляет собой архитектуру ОВС, которая обеспечивает вычисление данного выражения. 2. Применение альтернативных подходов для программирования однородных вычислительных систем 2.1. Программирование вычислений, управляемых потоками данных (Data Flow) Обобщенные в отчете [15] результаты многочисленных исследований показывают, что ключевым фактором, который способен обеспечить требуемую эффективность программирования вычислителей, управляемых потоком данных, являются радикальные изменения понятия переменной и процедуры присваивания. В обзоре [17] приведены результаты использования адаптированного языка C для программирования алгоритмов обработки изображений на реконфигурируемом вычислителе, построенном на FPGA семейства Virtex (Xilinx, США). Язык программирования SA-C представляет собой диалект, наиболее характерными отличиями от базового языка C являются: - принцип однократного присваивания значений переменным (single assignment); - исключение операций с компонентами общей памяти; - ориентированность на выражения (expression oriented - любая языковая конструкция обязательно возвращает как минимум одно значение). В ряде случаев для обеспечения выразительности и адекватности описания вычислительного процесса в потоковых вычислительных системах с массивным параллелизмом платформы программирования, основанные на императивных языках, вынуждены перенимать базовые принципы декларативной концепции программирования [18, 19]. К преимуществам использования декларативных языков для программирования однородных вычислительных систем следует отнести отсутствие конструкций и понятий, которые не имеют адекватного отображения в ОВС, - такие как общая память, переменные, указатели, индексы, циклы. Главными факторами, которые сдерживают применение и распространение декларативной парадигмы программирования, долгое время оставались отсутствие зрелых платформ программирования и психологическая неготовность сообщества программистов к радикальному изменению своего инструментария [20, 21]. Однако за последние несколько лет отношение разработчиков программного обеспечения к декларативным языкам стало меняться, что привело к появлению гибридных языков и новых декларативных платформ для программирования параллельных вычислителей. 2.2. Не-императивныеязыки программирования Анализ динамики (по данным Wikipedia) создания новых языков программирования за последние 15 лет показывает устойчивое уменьшение среди новых языков программирования доли чистых императивных языков (-24%) и такой же устойчивый рост доли гибридных языков, которые поддерживают декларативный стиль программирования (+34%). Объяснить это можно двумя причинами: 1) отсутствием заметного прогресса в применении императивных программных систем для программирования вычислителей с массивным параллелизмом вычислений; 2) появлением и все более широким внедрением распределенных облачных и туманных вычислений (cloud, fog computing); основной тенденцией в организации вычислительных процессов становится уход от классической схемы фон Неймана, что уменьшает область эффективного применения чистых императивных языков программирования. Гибридные языки, по замыслу разработчиков, должны сочетать в себе основные достоинства указанных выше парадигм программирования: - наглядность (простота восприятия) программного кода, наличие мощных инструментов для его создания и отработки, которые свойственны современным императивным языкам программирования; - автоматическое выявление ветвей параллельных вычислений, отсутствие побочных эффектов при их выполнении, которые свойственны чистым декларативным языкам программирования. В качестве примеров реализации подобных решений в последнем разделе будут рассмотрены платформа программирования FPGA-сопроцессоров, основанная на гибридном языке Mitrion-С, и платформа программирования параллельных вычислений, основанная на декларативном языке SquenceL. Поскольку данные платформы способны обеспечить массовый параллелизм вычислительного процесса, основные принципы их построения и опыт реализации могут быть использованы при создании систем программирования однородных вычислительных сред. 3. Платформы программирования систем с массовым параллелизмом вычислений 3.1. Платформа, основанная на гибридном языке программирования Платформа компании Mitrion включает в себя все компоненты, которые необходимы для реализации полного цикла программирования сопроцессоров, построенных на FPGA: - транслятор Mition-C, который предназначен для лингвистической верификации исходного кода, написанного на языке программирования высокого уровня, и формирования объектного кода программы; - виртуальный процессор Mitrion, который обеспечивает отладку объектного кода программы на интерпретаторе с использованием FPGA - независимого эмулятора; - блоки конфигурирования (Processor Configuration Unit, SPR Tool), которые выполняют размещение вычислительных компонентов на FPGA, создание соединений между ними (Place & Route) и обеспечивают формирование загрузочного кода (FPGA bitstream - код укладки программы) с учетом специфики выбранной аппаратной платформы FPGA. По замыслу разработчиков платформы Mitrion, язык программирования должен обеспечивать интеллектуальную поддержку программиста в обеспечении параллельного выполнения программ и в то же время быть достаточно простым для изучения и использования [22]. Поскольку лексика языка Mition-C не опирается явно на принятые в декларативных языках механизмы описания шаблонов функций, она, на первый взгляд, гораздо ближе к лексике императивных языков программирования. Декларативный характер Mition-C подчеркивается также принятыми в данном языке программирования способами определения и использования переменных; присвоение значения переменной в языке программирования Mition-C представляет собой не выражение, как это принято в императивных языках программирования, а утверждение. Отличие заключается в том, что единожды определенное при помощи процедуры присваивания значение переменной Mition-C может затем многократно использоваться (например, для определения значений других переменных), но, в то же время, не может изменяться (переопределяться) [22]. Особый интерес при этом, безусловно, представляют оценки выразительности нетрадиционных лингвистических конструкций языка Mition-C. Действительно, многие испытатели отмечают, что им требовалось определенное время для того, чтобы привыкнуть к специфическим особенностям программирования на Mition-C [23, 24]. Большинство из них, однако, при этом указывают, что после завершения адаптации процесс программирования уже не у них вызывал значительных затруднений. При этом программисты по достоинству оценили оригинальные решения разработчиков языка, которые обеспечивают возможность управления точностью представления данных [23] и функциональную полноту платформы, которая обеспечивает выполнение предварительной отладки программных решений на интерпретаторе [25]. Предварительные сравнительные оценки средств программирования FPGA-сопроцессоров [24, 26-28] показывают, что платформа Mitrion (язык Mitrion-С) имеет преимущество в эффективности по отношению к традиционным программным средствам (Impulse-C и Dime-C), но уступает как средствам аппаратного (VHDL и Verilog), так и графического (DLPlogic) программирования. Рассматривая эти результаты, не стоит забывать о том, что только программные платформы способны обеспечить мобильность программного кода и востребованную сегодня возможность его независимой отладки [25, 29]. Не вызывает сомнения, что перспективы применения для программирования ОВС платформ, основанных на гибридных языках, во многом будут определяться совокупностью взаимно исключающих требований удобства программирования и степени абстрагирования от архитектуры вычислительного устройства. Основываясь на изложенном выше (здесь уместно будет вспомнить опасения [5] разработчиков Chapel), можно предположить, что чем больше императивных возможностей разработчик гибридного языка оставит программисту, тем менее приспособленный для параллельного выполнения код получит транслятор. Поэтому значительно более перспективным представляется применение для программирования ОВС решений, которые основаны на чистых декларативных языках программирования. Как будет показано далее, лаконичность программных конструкций в совокупности с развитыми процедурами выявления параллелизма позволяет успешно решать многие проблемы, с которыми могут столкнуться разработчики систем программирования однородных вычислительных сред. 3.2. Платформа, основанная на декларативном языке программирования Очевидно, что максимально эффективной (по определению) будет программа, которая наиболее точно адаптирована к архитектуре вычислительной системы. Важно при этом определить, на какой именно стадии создания программы и каким образом должна происходить эта адаптация. Наиболее неудачным представляется вариант, когда программа изначально строится на основе типового алгоритма, который не учитывает ни структуру обрабатываемых данных, ни архитектуру вычислительной системы, а потом под них адаптируется программистом или компилятором. Проблема заключается в том, что алгоритм сам по себе уже является адаптацией выполняемой задачи, как правило, для классической архитектуры фон Неймана, поэтому его автоматическая адаптация компилятором сводится к решению описанной ранее проблемы построения «универсального векторизующего компилятора» [3], а процесс ручной адаптации рано или поздно возвращает программиста к условиям поставленной задачи. Значительно более продуктивным поэтому представляется процесс построения программы непосредственно из условий решаемой задачи с одновременным учетом структур обрабатываемых данных и доступных функций. Во многом подобный процесс реализован в системе программирования, основанной на языке SequenceL, представляющем собой чистый декларативный язык высокого уровня, который предназначен для программирования распределенных и потоковых вычислений [29]. Отличительными особенностями этого языка программирования является очень лаконичный синтаксис и развитые механизмы неявного распараллеливания вычислений. По замыслу создателей, эти особенности языка SequenceL позволяют избавить программиста от алгоритмического планирования вычислительного процесса, что особенно важно для программирования реконфигурируемых систем с массированным параллелизмом вычислений, когда структура (архитектура) вычислительного устройства не определена на момент создания программы. В то же время лаконичная семантика SequenceL поощряет программиста формулировать решаемые задачи в форме, которая способствует выявлению и использованию скрытого параллелизма вычислений [28]. Как следует из названия языка, базовым элементом данных в SequenceL являются последовательности, элементами которых также могут быть последовательности. Скаляр представляется в SequenceL в виде 0-мерной последовательности, которая состоит из одного элемента, вектор представляется одномерной последовательностью, матрица - двумерной (последовательность векторов) и т.д. Размерность (Type - тип) аргументов указывается в определениях функций и операторов SequenceL и играет ключевую роль для распараллеливания их вычислений [30]. В случае, если тип аргумента при обращении к некоторой функции превышает значение типа, которое было задано при ее определении, для этого аргумента фиксируется состояние «превышение типа» (overtyping), которое влечет за собой выполнение для него и для данной функции комплекса согласующих операций - NTD (Normalize-Transpose-Distribute). Назначение операций NTD поясняется приводимым ниже примером умножения (скалярная операция) на вектор, который взят из [30]: 10 * [1,2,3] (normalize) ^ [[10,10,10],[1,2,3]] (transpose) ^ [[10, 1],[10,2],[10,3]] (distribute) ^ [[10*1],[10*2],[10*3]] ^ [10,20,30] Применение комплекса NTD в языке SequenceL позволяет на стадии трансляции выражений автоматически выявлять скрытый параллелизм их вычисления и одновременно избавляет программиста от необходимости использования дополнительных программных конструкций для управления вычислительным процессом [30]. Интересно отметить, что хотя описанные выше основные принципы построения языка программирования SequenceL были представлены разработчиками еще в прошлом веке [28], заметное распространение этот язык начал получать только в последние несколько лет. В апреле 2012 г. основанная разработчиками языка компания Texas Multicore Technologies (ТМТ) представила бета-версию коммерческого компилятора SequenceL, который использовался в качестве пре-процессора к языку С++ для автоматического распараллеливания вычислений. В декабре 2014 г. ТМТ, уже будучи одним из партнеров AMD в области разработки программного обеспечения, представила новую версию своей платформы, которая обеспечивала совместное использование SequenceL с такими языками программирования, как Java, C#, Python и Fortran, что обеспечило успешное применение для программирования распределенных вычислений. Как показывают испытания, сегодня платформа программирования ТМТ, которая включает в себя интерпретатор, отладчик, компилятор SequenceL и системные библиотеки для поддерживаемых языков программирования, позволяет автоматически создавать программы, которые превосходят написанные вручную по эффективности использования вычислительных ресурсов [31]. Опыт разработки и внедрения платформы программирования ТМТ подтверждает представленное выше предположение о растущем интересе к системам, которые основаны на не-императивных языках программирования в связи с наблюдаемыми системными изменениями в организации вычислительного процесса (тенденция ухода от классической схемы фон Неймана). 3.3. Общие требования к платформе программирования ОВС Представленный выше анализ текущего состояния и тенденций развития технологий программирования систем с массовым параллелизмом вычислений позволяет определить основные требования к составу и функциям компонентов платформы программирования однородных вычислительных сред. Основными компонентами такой платформы должны быть собственно система программирования и система построения загрузочного кода (компоновки). Система программирования, по нашему мнению, должна быть построена на декларативном языке и обеспечивать синтаксическую и семантическую отладку управления точностью и разрядностью вычислений. Система трансляции предназначена для формирования объектного кода разработанной программы с учетом особенности организации вычислительного процесса в ОВС и специфики их компоновки, а при необходимости - автоматического эквивалентного преобразования объектного кода. Система компоновки должна быть построена по блочно-модульному принципу с тем, чтобы обеспечить итеративную форму адаптации объектного кода для оптимизации процесса построения загрузочного кода и возможность дальнейшего развития системы. Наличие, кроме естественной временной метрики обработки данных (потактные вычисления потоков данных на массивах ПЭ), еще и явно выраженной пространственной метрики (прямоугольная матрица локально связанных ПЭ) обусловливает «геометрический» характер функционирования компилятора. Он должен учитывать возможные траектории распространения потоков данных в двумерном пространстве ПЭ и оптимизировать длины этих траекторий. Это принципиально отличает принципы построения и функционирования компиляторов ОВС от компиляторов современных систем параллельной обработки данных. Отмеченные особенности ложатся в основу создания технологии программирования ОВС, при этом первым этапом становится создание языка и принципов построения ОВС-компилятора. Заключение ОВС представляют собой класс архитектур с массовым параллелизмом, реализуемым на двумерных массивах локально связанных процессорных элементов. По принципу обработки информации это реконфигурируемые машины потоков данных с однородной структурой. Поэтому основными чертами технологии программирования ОВС являются декларативный принцип языка программирования, структурно-функциональный принцип работы компилятора, учитывающий топологию ОВС и возможность программного управления архитектурой ОВС (реконфигурации) при возникновении соответствующих условий и проблем.

Скачать электронную версию публикации