Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
Национальный исследовательский университет «Высшая школа
экономики»
Московский институт электроники и математики Национального
исследовательского университета «Высшая школа экономики»
Допущен к защите
Заведующий кафедрой ВСиС
___________ А.В. Вишнеков
«__» ____________ 2013 г.
Орлов Иван Алексеевич
МОДЕЛИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ НА РАСПРЕДЕЛЕННОЙ СИСТЕМЕ ОБЪЕКТНО-АТРИБУТНОЙ АРХИТЕКТУРЫ
Направление 23.01.00.68 - Информатика и вычислительная техника
Магистерская программа - Сети ЭВМ и телекоммуникации
Магистерская диссертация
Научный руководитель
|
Салибекян С.М.
|
подпись
подпись
Москва 2013
Аннотация.
В диссератации описаны принципы имитационного моделирования разработанной в МИЭМ НИУ ВШЭ объектно-атрибутной (ОА) архитектуры вычислительных систем (ВС), реализующих принцип управления вычислениями с помощью потока данных (dataflow-парадигма), и результаты имитационного моделирования dataflow-ВС, полученные в рамках выполнения НИР по разработке и моделированию архитектуры суперкомпьютерной dataflow-ВС по Федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2007-2013 годы» при финансовой поддержке Минобрнауки России. Описание dataflow-прадигмы приводится во введении.
Для имитационного моделирования dataflow-ВС была расширена среда программирования и имитационного моделирования, основанная и работающая принципах ОА-архитектуры. С использованием данной среды было проведено имитационное моделирования ОА-суперкомпьютерной системы. Описание ОА-архитектуры и среды программирования и моделирования приводится в разделе №1.
Также, с целью оценки производительности и определения различных параметров вычислительной системы, в данной среде были разработаны тесты, решающие задачи разных классов. Принципы моделирования и разработка тестов описаны в разделах № 2 и № 3 соответственно.
Все тесты были запущены в данной среде, результаты тестирования и их анализ приведены в разделе № 4.
Содержание
1 Введение 4
2.1 Описание программной реализации ОА-архитектуры 20
3.1 Выбор и обоснование критериев оценки моделируемой системы 27
3.2 Выбор и обоснование параметров моделируемой системы 28
5.1 Тестовые прогоны на модели ОА-архитектуры dataflow-ВС задач расчета напряженности электростатического поля 57
5.2 Тестовые прогоны на модели ОА-архитектуры dataflow-ВС задач бенчмарка GRAPH500 на основе алгоритмов решения теоретико-графовых задач 64
5.3 Тестовые прогоны на модели ОА-архитектуры dataflow-ВС задач бенчмарка GREP – алгоритма сопоставления файловых строк шаблонам команды 71
5.4 Анализ результатов тестовых прогонов на модели ОА-архитектуры dataflow-ВС 75
Выводы 80
Список используемой литературы 81
Введение
В архитектурах вычислительных сетей на сегодняшний день преобладающую роль играют ВС, управляемые потоком команд – Control Flow. Такая парадигма вычислений ориентирована на последовательные вычисления. Она основывается на понятии программного счетчика, который хранит адрес ячейки памяти, из которой считывается выполняемая на текущий момент времени команда. Признаки control-flow-архитектуры видны также и на программном уровне: в настоящее время наиболее популярными языками программирования являются императивные языки (Pascal, С, C++, Java и др). Было предпринято множество попыток создания аппаратных систем, управляемых потоком данных, однако особых успехов они не принесли, т.к. ядром подобных систем являлся вычислитель фон-неймановской архитектуры.
Одним из перспективных способов оптимизации вычислительного процесса является применение dataflow-парадигмы, т.е. метода управления вычислительным процессом потоком данных. Данная парадигма известна уже более тридцати лет. Работы по аппаратной и программной реализаций этой концепции проводились различных исследовательских центрах. Например, в Массачусетском технологическом институте (процессор Tagget Token), лабораториях корпорации Tеxas Instruments (США), в Манчестерском университете (Англия). Но всё же наивысшим успехом данных проектов было создание экспериментальных прототипов.
В dataflow-системах очередность выполнения вычислительных задач зависит от готовности операндов. Как только необходимое число операндов приходит на исполнительное устройство, оно тут же начиняет выполнять свою вычислительную задачу. Стоит отметить, что очередность исполнения команд может коренным образом отличаться от очередности записи команд в программе. Налицо одно из главных преимуществ data-flow парадигмы: разные итерации одного цикла могут выполняться одновременно, на разных вычислительных узлах. Более того, (i+1)-я итерация цикла способна начаться исполняться быстрее, чем i-я, при условии наличия всех необходимых операндов. Система состоит из множества исполнительных устройств, каждое из которых может быть настроено «узко»: например, на выполнение вычислительных операций лишь одного типа.
С помощью данной концепции возможно преодолеть слабое место скалярных процессоров, которое заключается в потери времени на процедуры управления данными и спекулятивные вычисления.
Анализ существующих решений в области dataflow-ВС
В истории науки проводились попытки создания эффективных систем dataflow не только на аппаратном уровне, но и на уровне программном. В реализации на программном уровне были достигнуты некоторые положительные результаты: создание объектно-ориентированной парадигмы программирования (ООП), частично работающий по событийному принципу (в особенности язык Smalltalk); некоторые функциональные языки (например, Mozart, Sisal). Итак, перечислим некоторые решения, связанные с программной реализацией принципа dataflow.
Сети Кана
Рисунок 1 – Процессная сеть Кана
Считается, что предтечей всех dataflow-языков являются сети Кана (англ. Kahn) (Рисунок 1), в которых вычислительный процесс представляется в виде модулей (акторов) обменивающихся между собой сообщениями по линиям связи, установленными между ними. На линиях связи имеются очереди сообщений для того, чтобы в них помещались сообщения, которые ввиду занятости модуля-приёмника, не могут быть в данный момент приняты на обработку. Данная модель вычислений была предложена в 1974 году.
U-язык
Рисунок 2 – U-язык
Данный язык (Рисунок 2) используется для описания токенов, передаваемых по дугам потокового графа в машинах с памятью фреймов.
Каждый токен включает в себя два поля:
- активное имя;
- данные.
Активное имя, в свою очередь, включает в себя тег, который состоит из полей:
- адрес инструкции (n);
- поле контекста (c), уникально идентифицирующий контекст, в который входит инструкция;
- номер итерации (i), который идентифицирует активную итерацию цикла;
в том случае, если узел, куда пересылаются данные, имеет несколько входных аргументов, то в тег включается номер порта назначения узла-адресата (p).
LUCID (1976)
Язык основан на концепции потока: даже константы, представляют собой поток (числовые константы – это поток состоящий из повторений данной числовой константы). Язык по сути функциональный. Потоки могут быть как бесконечные, так и конечные (конечным поток будет, если в качестве его хвоста использована специальное значение eod (end of data). Арифметические операции применяются к потокам поэлементно.
Одна из версий языка под названием Granular Lucid (GLU), разработанная в калифорнийской компании SRI International, предназначена для описания алгоритма крупнозерниского dataflow: dataflow-программа пишется на языке LUCID, а «зерна» - на языке Си. «Зёрна» оформляются в виде функций на языке Си, расположенных в отдельном файле.
ID (IRVINE DATAFLOW) 1978
Язык используется для программирования dataflow-систем Массачусетского технологического института (MIT) и системы Monsoon фирмы Motorola. Концепция данного языка высокого уровня была предложена Арвиндом и Гостлоу (англ. Arvind and Gostelow). Язык предназначен для программирования параллельных архитектур, в том числе, и динамического dataflow. Основные черты языка: однократное присвоение значений переменным, блочная структуризация программы, функциональная парадигма. Типы переменных не задаются напрямую, а определяются по значению, которое было в них помещено. Структуры данных и массивы не различаются между собой: элементы структуры могут адресоваться как с помощью индекса, так и с помощью строковых идентификаторов (например, «, t[‘‘height’’]»). Над структурами данных определены две операции select (выбор), предназначенный для того, чтобы получить значение из поля данных структуры, и append (добавить), необходимая, чтобы создать новую структуру путём копирования полей другой структуры данных или чтобы записать значение в поле структуры данных.
Id-программа состоит из набора свободных выражений и подвыражений, которые могут выполняться в любом порядке в зависимости от наличия данных (операндов) для их выполнения.
VAL (A Value-oriented Algorithmic Language) 1979
Язык был разработан а Массачусетском технологическом университете. VAL – это язык программирования высокого уровня, который не содержит машинозависимых элементов, что обеспечивает переносимость программы на различные аппаратные платформы. Язык предназначен для реализации статической потоковой архитектуры (следовательно, не реализуются рекурсивные вызовы). По синтаксису напоминает язык Pascal. Функции и выражения могут возвращать сразу несколько значений. У каждой переменной имеется специальное значение «Ошибка». Это нужно для того, чтобы сохранить необходимый порядок вычислений: если значение переменной еще не получено, то переменная содержит значение «Ошибка». Язык обеспечивает скрытое описание параллелизма. В данном языке переменные могут определяться только один раз (до определения в переменной хранится значение «пусто», а после присвоения значения, содержимое переменной меняться уже не может). Во время декларации массивов их размерность не указывается: размерность можно задать и определить с помощью специальных команд.
В VAL весьма ограничены возможности ввода/вывода и не поддерживается рекурсия из-за того, что программа транслируется напрямую в потоковый граф.
SISAL (Streams and Iterations in a Single Assignment Language) 1983 г.
Язык SISAL ориентирован на поддержку научных вычислений и представляет собой дальнейшее развитие языка VAL. Язык появился на свет благодаря сотрудничеству Ливерморской национальной лаборатории имени Лоренца, Университета штата Колорадо, Манчестерского университета (Великобритания) и Digital Equipment Corporation (DEC). Создатели языка ставили перед собой следующие задачи: 1. язык должен эффективно работать на машинах как последовательной, так и параллельной архитектур; 2. обеспечить создание независимого от языка и целевой архитектуры промежуточного представления программы в виде потокового графа; 3. разработать технику оптимизации параллельных программ; 4. внедрить функциональный стиль программирования для сложных научных расчётов; 5. обеспечить программирование микропроцессорных ВС с распределённой памятью.
Хотя SISAL и относится к разряду функциональных языков, однако ему присущи и элементы декларативной парадигмы программирования. Причём декларативная часть программы свободна от побочных эффектов: программа представляет собой набор последовательных императивных процедур, связанных между собой обменом данными. Оптимизирующий компилятор языка SISAL освобождает пользователя от работы по распараллеливанию программы, беря на себя всю нагрузку по планированию операций, передачу данных, синхронизацию вычислений, управлению памятью, что позволяет программисту сконцентрироваться именно на описании логики программы, не больше ни на чём.
Язык получил большую популярность в 90-е годы благодаря тому, что существовал компилятор, который мог переводить программу на этом языке в язык С, и потому программы, написанные на SISAL могли запускаться на любой машине, где был реализован С-компилятор. Еще одна причина популярности языка кроется в весьма удачной концепции модулей и интерфейсов, когда описание функций находится в интерфейсе, а алгоритм самих функций помещается в модуле.
POST
Язык дает обширные возможности по программированию:
- возможность влияния на стратегию вычислений уже в процессе выполнения программы;
- структуры данных, являющие одновременно синхронными и асинхронными;
- взаимодействие между вычислениями, чтобы прекратить вычисления по лишним ветвям алгоритмов.
Однако синтаксис программы чрезвычайно неудобен для понимания.
ПИФАГОР 1995
Этот функциональный язык разработан в Красноярском Государственном Техническом Университете (КГТУ).
Программа в ПИФАГОР представляет собой граф программы, описываемый с помощью специальных языковых конструкций. Данные передаются по дугам графа посредством токенов, переносящих как скалярные и векторные величины, так и функции преобразования данных.
Модель вычислительного процесса задается с помощью тройки
M = ( G, P, S0 ),
где G – ациклический граф, что определяет информационную структуру программы (ее информационный граф),
P - набор правил, определяющих динамику функционирования модели (механизм формирования разметки),
S0 – начальная разметка.
Информационный граф G, в свою очередь, задаётся двойкой:
G = ( V, A ),
где V - множество вершин определяющих программо-формирующие операторы,
A - множество дуг, задающих пути передачи информации между ними.
Программно-формирующие операторы, являющиеся вершинами графа, осуществляют информационные преобразования данных, их структуризацию и размножение. Существуют следующие типы операторов:
- Интерпретации. Узел данного типа имеет два входа (по одному поступает аргумент, что требуется преобразовать с помощью функции, код которой поступает на второй вход; преобразованная величина поступает на единственный выход).
- Константный оператор. Данный узел выдает фишку с константой.
- Копирования данных. Копирует пришедшие на единственный вход данные на несколько выходов.
- Группировки в список: данные, пришедшие на несколько входов, группируются в один список.
- Группировки в параллельный список: пришедшие данные группируются в параллельный список (элементы параллельного списка рассматриваются оператором интерпретации как независимые аргументы).
- Группировки в список задержанных вычислений. (На рисунке данный оператор представлен в виде прямоугольника, выделяющего определенный подграф). С помощью этого оператора в графе программы выделяется отдельный подграф, выполнение которого активизируется не только по приходе всех необходимых для вычисления данных, но и при снятии задержки, т.е. разрушении границ подграфа.
Ввиду того, что программа ориентирована на непосредственное описание графа программы, синтаксис языка весьма отличается от общепринятого синтаксиса. Например, в языке не поддерживаются инфиксные бинарные операции, отсутствуют модульное построение программы, раздельная трансляция и интеграция стандартных библиотек, что не могло сказаться на популярности данного языка программирования. Отсутствие циклов в языке Пифагор компенсируется возможностью использования рекурсии. А сочетание механизма перегрузки функций и динамических типов, определяемых пользователем, обеспечивает написание эволюционно расширяемых параллельных программ. К тому же в языке реализован механизм перегрузки функций, что позволяет производить безболезненное масштабирование программы.
Mozart
В данном языке программирования, поддерживающим множество парадигм вычислений, реализуется и стратегия dataflow. Для этой цели существует команда Wait, которая используется для синхронизации по данным нескольких параллельных нитей вычислений. Нить, в коде которой встречается команда Wait(A), (A – переменная), дойдя до данной команды, будет ожидать, пока другая нить не запишет данные в переменную A. Как только данные в переменную будут записаны, нить продолжит свою работу. Принцип dataflow может использоваться в языке Mozart и более широко (Листинг 1): здесь в переменную S поступают значения — если переменная S пустая (не заполненная), то поток, реализующий данную программу останавливается до того момента, когда данные поступят (как очередная порция данных поступить нить вычислений возобновится, и снова остановится для ожидания следующией порции данных и так далее, пока не поступят все данные).
for Msg in S do
...
end
Листинг 1. Считывание потока данных в языке Mozart
Smalltalk
Язык Smalltalk основывается на следующих понятиях:
1. Объект. Вся программа состоит из совокупности объектов, обменивающимися сообщениями между собой. Объекты состоят из полей (данные) и методов (подпрограмм, обрабатывающих пошедшие сообщения). Каждому объекту соответствует свой протокол.
2. Класс. Однотипные объекты объединяются в классы, а каждый объект является экземпляром класса.
3. Метод. Подпрограмма, предназначенная для обработки сообщения, пришедшего от другого объекта. Каждому типу сообщения соответствует свой метод его обработки. Основная задача метода — при приходе сообщения соответствующим образом изменить состояние объекта и выслать ответ на пришедшее сообщение.
4. Операторы. Существует всего три оператора: посылка сообщения, выдача ответа, присваивание значения переменной. Синтаксис оператора посылки сообщения несколько напоминает синтаксис естественного языка (подлежащее - сказуемое - дополнение): объект-получатель ИмяСообщения, [объекты-атрибуты], например:
5 factorial - объекту 5 посылается сообщение с именем "factorial";
а – 3 - объекту "а" посылается сообщение с именем "-" и аргументом 3;
pen move:east by:10 - объекту pen посылается сообщение "move:eastby:10" , где "move" и "by" — селекторы ключевых слов, по которым метод идентифицирует пришедшие с сообщением аргументы, а "east" и "10" — сами аргументы (":" - обозначение того, что после селектора идет указание параметра).
Хотя Smalltalk очень близок по духу к концепции dataflow, однако он до конца, все же, не уходит от командной парадигмы: по сути сообщение — это завуалированное описание одной фон-неймановской команды. Можно сказать, что программная среда Smalltalk создает среду из виртуальных объектов, которые обмениваются между собой командами.
DCF
Язык DCF – это расширение языка C для работы в режиме dataflow. Модель, реализованная в DCF, относится к классу data-control flow (система, сочетающая в себе модель управления вычислениями с помощью потоков команд и данных). DCF зиждется на двух ключевых понятиях: нить и токен. Нить является классическим легковесным процессом (цепочка последовательно выполняемых команд). Нить начинает выполняться, как только для программы этой нити приходят все необходимые данные. Функция, реализуемая в виде отдельной нити вычислений, описывается с помощью ключевого слова «thread» вместо типа возвращаемого значения: thread Func( int N, float Var ) { … }. Выполнение программы начинается с функции-потока с именем main. Функции-нити могут порождать другие нити; выполнение программы считается завершённым, когда завершаются все вычислительные нити.
Данные же передаются с помощью токенов, которые состоят из тега, идентифицирующего получателя данных; самих данных типов int, float, char языка Си, другую описывающую информацию о передаваемых данных. Тег состоит из двух полей: имя функции-получателя данных и «цвет», задающую номер итерации цикла. С помощью токенов происходит запуск и возобновление работы функций. Токены «обитают» в неком «пространстве» токенов, где они хранятся и где происходит их сбор и объединение в группы: каждая группа — это набор токенов, необходимых для запуска определённой нити вычислений (полностью скомплектованная группа содержит токены, хранящие данные для всех аргументов активируемой функции-потока).
Модель акторов
Модель исходит из того, что вся программа делится на несколько независимых программ (акторов), обменивающихся между собой сообщениями: если актору приходят данные необходимые для выполнения одного из заложенных в него привил, он производит вычисление и выдает сообщение с результатами другим акторам по специальным линиям связи (реальным или виртуальным). Актор может иметь внутреннее состояние и менять его в соответствии с заложенным в него алгоритмом. Во избежание потери информации, организуются очереди сообщений: если актор занят обработкой данных, то пришедшее сообщение помещается в очередь. Модель весьма хорошо подходит для реализации на распределенных ВС, т.к. каждый актор может существовать в изолированном адресном пространстве (связь осуществляется только через очереди сообщений). Термин "актор" был впервые предложен Карлом Хьюиттом (Carl Hewit) в 1970-х годах, который пытался с его основе разработать концепцию «мыслящих исполнительных устройств» (autonomous reasoning agents). Идея акторов применительно к модели параллельных вычислений была затем развита в научных работах Агха.
Акторная модель состоит из двух составляющих:
Описание акторов (в описание входят интерфейс актора (описание входов и выходов актора), параметры (они обычно задаются перед началом вычислений и во время вычислительного процесса не меняются), алгоритм получения выходных результатов);
Описание соединений акторов, по которым они обмениваются сообщениями (задаётся с помощью XML-файла, специального графического редактора или программы, использующей специальных аппаратно-программный интерфейс (например, SystemC)).
Приведём описание актора на языке Caltrop (листинг 2):
actor AddAndMultiply2[T] (T k) T A, T B → T C :
action [a], [b] → [k ∗ (a + b)] : endaction
action [a], [] → [k ∗ a] : endaction
action [], [b] → [k ∗ b] : endaction
endactor
Листинг 2. Описание актора на языке Caltrop
Здесь в качестве входных значений выступают A и B, а в качестве выходного — C, в качестве параметра актора выступает k (T – обозначение типа переменной); и описаны три действия (action), которые активизируются при:
приходе двух операндов;
приходе только операнда А;
приходе только операнда В.
Данный подход уже давно используется в системах Simulink от The Mathworks, LabVIEW от National Instruments, ML-Designer, ПИФАГОР, Erlang, Caltrop и т.д.
Графическое программирование
 
Рисунок 3 – Среда LabView Рисунок 4 – Среда моделирования MLDesigner
Программы, выполненные в данной парадигме, представляют алгоритм не в виде текста, а в графическом виде: элементарные операторы и сложные функции иллюстрируются с помощью определённых графических объектов, а передача операндов (скалярных величин или информационных конструкций) от одной операции или функции к другой — графическими линиями связи (Link). Во время выполнения программы по link-ам будут передаваться токены с данными или ссылками на информационные конструкции. Можно сказать, такая графическая модель как раз и служит отражением графа потока данных. В качестве представителей данной парадигмы следует упомянуть системы программирования LabView (Рисунок 3) и MLDesigner (Рисунок 4). Первая система применяется для решения любых вычислительных задач, вторая — в основном для моделирования различных систем. Данный подход весьма похож на модель акторов (графические элементы являются акторами, которые по виртуальным линиям связи обмениваются различными сообщениями). Родоначальником такой парадигмы программирования можно считать Джека Денниса, который предложил описывать алгоритмы dataflow-машин с помощью изображения потокового графа.
-
Выводы по анализу программных решений dataflow
Как было показано выше, в основном для реализации систем dataflow применяется функциональная парадигма программирования. Это объясняется тем, что данная парадигма не задаёт чёткой «траектории» вычислений (т.е. последовательности операций), как в классической процедурной (императивной) парадигме вычислений. Именно отсутствие программного счётчика и позволяет произвести полноценное распараллеливание вычислений, и управление вычислительным процессом с помощью потока команд. Однако функциональная парадигма в среде программистов, к сожалению, не получила должной популярности. Чрезвычайно популярная объектно-ориентированная же парадигма больше тяготит к процедурному стилю программирования и не обеспечивает полноценную работу в режиме dataflow. Единственным объектно-ориентированным языком, полностью соответствующим парадигме управления вычислительным процессом с помощью потока данных, является Smaltalk, который, к сожалению, не очень-то любим в среде программистов.
Многие языки, что разрабатывались под конкретные dataflow-машины (например, VAL), со временем были забыты. Универсальные же языки (например, SISAL), которые поддерживали кроссплатформенность развиваются и до сих пор.
Весьма выгодным оказывается направление по созданию гибридных покового-командных языков, таких как DCF: они позволяют программисту работать в привычной процедурной (императивной) парадигме, по возможности добавляя элементы dataflow-стиля.
Акторная модель весьма удобна для реализации на гетерогенных ВС, однако она имеет очень существенный недостаток: программа делится на множество маленьких кусков, которые не очень-то легко воспринимаются как единое целое.
В заключение следует отметить, что до сих пор не создано dataflow-языка программирования, который был бы безоговорочно принят в программистской среде — сейчас наиболее популярна процедурная (императивная) и объектно-ориентированная парадигмы, которые соответствуют концепции control flow.
ОА-архитектура
В данной работе предлагается использование объектно-атрибутной архитектуры ВС (или ОА-архитектуры). В отличие от классической ВС, ОА-архитектура работает по иным принципам, т.к. не имеет фон-неймановской архитектуры вычислительного ядра. Более того, ОА-архитектура может быть применима как к аппаратной, так и к программной частям ВС. Для аппаратной части приведем описание атрибутной (А-архитектурой), а для программной – описание ОА-архитектуры.
В атрибутной архитектуре вычислительная аппаратура представляется в виде набора функциональных устройств (ФУ). Взаимодействуют эти устройства с помощью информационных пар (ИП) – совокупности данных и характеризующего их атрибута. По сути, ИП представляет собой простейший токен. Такая организация вычислительной сети позволяет отойти от использования стандартных фон-неймановских команд, и, следовательно, обойти фон-неймановскую архитектуру в целом. Это позволяет намного повысить производительность вычислительной системы при выполнении параллельных вычислений.
Для программной реализации можно модернизировать А-архитектуру:
Несколько информационных пар более оптимально группировать в единую структуру данных – капсулу. С помощью этой группировки можно описывать объекты в рамках одной конструкции данных.
Функциональные устройства заменяются на виртуальные функциональные устройства (ВФУ). Для реализации удобнее разработать универсальный интерфейс ВФУ (например, в виде подпрограммы или класса).
Данные изменения способствуют применению программной реализации в качестве среды моделирования: количество виртуальных функциональных устройств может быть ограниченно только ресурсами вычислительной машины, на которой проводится моделирование.
Однако, для проведения моделирования на ОА-архитектуре требуется отличный от классического подход к программированию ВС. Это связано с совершенно иным способом управления вычислительным процессом, которым в данной архитектуре управляют сами ВФУ.
|
