Двоичная модульная машина потока данных

BMDFM работает на различных операционных системах

Линукс

Windows 10

MacOS

Андроид

Binary Modular Dataflow Machine ( BMDFM ) — это программный пакет, который позволяет параллельно запускать приложения на компьютерах с симметричной многопроцессорной обработкой (SMP) с общей памятью, используя несколько процессоров для ускорения выполнения отдельных приложений. BMDFM автоматически идентифицирует и использует параллелизм благодаря статическому и главным образом динамическому планированию последовательностей команд потока данных, полученных из ранее последовательной программы.

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

Предыстория [ править ]

Современные SMP с параллельной общей памятью представляют собой сложные машины, в которых для достижения высокой производительности необходимо одновременно учитывать большое количество архитектурных аспектов. Современные серийные SMP-машины для технических вычислений могут иметь множество тесно связанных ядер (хорошими примерами являются SMP-машины на базе многоядерных процессоров Intel ( Core или Xeon ) или IBM ( Power )). Согласно заявлениям производителей компьютеров, количество ядер на узел SMP планируется удваивать каждые несколько лет.

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

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

Прозрачная семантика потока данных BMDFM [ править ]

Технология BMDFM в основном использует динамическое планирование для использования параллелизма прикладной программы, таким образом, BMDFM позволяет избежать упомянутых недостатков методов времени компиляции. ^[1]^[2] BMDFM — это среда параллельного программирования для многоядерных SMP, которая обеспечивает:

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

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

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

Предположим, у нас есть фрагмент кода, показанный ниже:

(  setq   a   (  foo0   i  ))          #   a   =   foo0  (  i  );  (  setq   b   (  foo1   (  +   i   1  )))    #   b   =   foo1  (  i  +  1  );  (  setq   b   (  ++   b  ))            #   b  ++  ;  (  outf   "a = %d  \n  "   a  )        #   printf  (  "a = %d  \n  "  ,   a  );  (  outf   "b = %d  \n  "   b  )        #   printf  (  "b = %d  \n  "  ,   b  );

Два первых оператора независимы, поэтому механизм потока данных BMDFM может запускать их на разных процессорах или ядрах процессора. Два последних оператора также могут выполняться параллельно, но только после вычисления «a» и «b». Механизм потока данных автоматически распознает зависимости благодаря своей способности динамически строить граф потока данных во время выполнения. Кроме того, механизм потока данных правильно упорядочивает выходной поток для последовательного вывода результатов. Таким образом, даже после внеочередной обработки результаты будут проявляться естественным образом.

Предположим, что приведенный выше фрагмент кода теперь вложен в цикл:

(  for   i   1   1   N   (  progn          #   for   (  i   =   1  ;   i   <=   N  ;   i  ++  )   {    (  setq   a   (  foo0   i  ))          #     a   =   foo0  (  i  );    (  setq   b   (  foo1   (  +   i   1 )  )))    #     b   =   foo1  (  i   +   1  );    setq  b   (   ++  b   )  )            #     b  ++  (    (  outf   "a = %d  \n  "   a  )        #     printf  (  "a = %d  \n  ";  ,   a  );    (  outf   "b = %d  \n  "   b  )        #     printf  (  "b = %d  \n  "  ,   b  ))  #                           }   ) ;

Механизм потока данных BMDFM будет хранить переменные «a» и «b» в уникальных контекстах для каждой итерации. На самом деле это разные копии переменных. Контекстная переменная существует до тех пор, пока на нее не ссылаются потребители инструкций. Более поздние контексты, на которые нет ссылок, будут собирать мусор во время выполнения. Таким образом, механизм потока данных может использовать как локальный параллелизм внутри итерации, так и глобальный параллелизм, а также одновременно выполнять несколько итераций.

Архитектура [ править ]

BMDFM — удобная среда параллельного программирования и эффективный механизм выполнения многоядерных SMP благодаря унификации MIMD нескольких архитектурных парадигм (фон-Неймана, SMP и потока данных):

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

BMDFM предназначен для использования в роли механизма параллельного выполнения (вместо обычной библиотеки времени выполнения с разветвлением и объединением), способного автоматически параллельно запускать нерегулярные приложения. Благодаря прозрачной семантике потока данных BMDFM представляет собой простой метод распараллеливания для прикладных программистов и, в то же время, гораздо лучшую технологию параллельного программирования и компиляции для многоядерных компьютеров SMP.

Базовая концепция BMDFM опирается на базовое аппаратное обеспечение SMP, доступное на рынке. Обычно поставщики SMP предоставляют свою собственную операционную систему (ОС) SMP с интерфейсом SVR4/POSIX UNIX (Linux, HP-UX, SunOS/Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS и т. д.). Поверх ОС SMP механизм выполнения многопоточного потока данных выполняет программную эмуляцию машины потока данных. Такая виртуальная машина имеет интерфейсы к языку виртуальной машины и C, обеспечивающие прозрачную семантику потока данных для обычного программирования.

BMDFM построен как гибрид нескольких архитектурных принципов:

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

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

Подсистема динамического планирования BMDFM представляет собой эффективный эмулятор SMP машины потока данных с тегированными токенами. Пул общей памяти разделен на три основные части: ввода-вывода порт кольцевого буфера (IORBP), буфер данных (DB) и очередь операций (OQ). Виртуальная внешнего управления машина статически планирует входную прикладную программу и помещает кластерные инструкции и данные входной программы в IORBP. Процессы службы кольцевого буфера (IORBP PROC) перемещают данные в БД, а инструкции — в OQ. Процессы обслуживания очереди операций (OQ PROC) помечают инструкции как готовые к выполнению, если доступны необходимые данные операндов. Процессы исполнения (CPU PROC) выполняют инструкции, которые помечаются как готовые и выводят вычисленные данные в БД или в IORBP. Кроме того, IORBP PROC и OQ PROC отвечают за освобождение памяти после обработки контекстов. Контекст — это специальный уникальный идентификатор, представляющий копию данных в разных телах итерации в соответствии с архитектурой потока данных с тегированными токенами. Это позволяет динамическому планировщику обрабатывать несколько итераций параллельно.

При работе под управлением ОС SMP процессы будут занимать все доступные процессоры и ядра процессоров реальной машины. Чтобы разрешить нескольким процессам одновременный доступ к одним и тем же данным, динамический планировщик BMDFM блокирует объекты в пуле общей памяти с помощью семафорных операций SVR4/POSIX. Политика блокировки обеспечивает множественный доступ только для чтения и эксклюзивный доступ для внесения изменений.

Поддерживаемые платформы [ править ]

Каждая машина, поддерживающая ANSI C и POSIX ; UNIX System V (SVR4) может запускать BMDFM.

BMDFM предоставляется в виде полных многопоточных версий для:

x86 : Linux/32, FreeBSD/32, OpenBSD/32, NetBSD/32, MacOS/32, SunOS/32, UnixWare/32, Minix/32, Android/32, Win-Cygwin/32, Win-UWIN/32, Win-СФУ-СУА/32;
x86-64 : Linux/64, FreeBSD/64, OpenBSD/64, NetBSD/64, MacOS/64, SunOS/64, Android/64, Win-Cygwin/64;
ВАКС : Ультрикс/32;
Альфа : Tru64OSF1/64, Linux/64, FreeBSD/64, OpenBSD/64;
IA-64 : HP-UX/32, HP-UX/64, Linux/64, FreeBSD/64;
XeonPhiMIC : Linux/64;
МЦСТ-Эльбрус : Linux/32, Linux/64;
PA-RISC : HP-UX/32, HP-UX/64, Linux/32;
SPARC : SunOS/32, SunOS/64, Linux/32, Linux/64, FreeBSD/64, OpenBSD/64;
MIPS : IRIX/32, IRIX/64, Linux/32, Linux/64;
MIPSel : Linux/32, Linux/64, Android/32, Android/64;
PowerPC : AIX/32, AIX/64, MacOS/32, MacOS/64, Linux/32, Linux/64, FreeBSD/32, FreeBSD/64;
PowerPCle : Linux/32, Linux/64;
S/390 : zOS-USS/32, zOS-USS/64, Linux/32, Linux/64;
M68000 : Linux/32;
ARM : Linux/32, Linux/64, FreeBSD/64, Android/32, Android/64, MacOS/64;
ARMbe : Linux/64;
RISC-V : Linux/32, Linux/64;
ЛунгАрч : Linux/64;
и ограниченная однопоточная версия для x86 : Win/32.

См. также [ править ]

Ссылки [ править ]

^ Почаевец, Александр (2006). BMDFM: гибридная среда распараллеливания потоков данных для мультипроцессоров с общей памятью (Диссертация). Технический университет Мюнхена (ТУМ), Германия (опубликовано 25 февраля 2006 г.).
^ "urn:nbn:de:bvb:91-diss20060316-1748151609" . URN NBN Resolver для Германии и Швейцарии. 22 марта 2006 г.

Внешние ссылки [ править ]

[1] Почаевец, Александр (2006). BMDFM: гибридная среда распараллеливания потоков данных для мультипроцессоров с общей памятью (Диссертация). Технический университет Мюнхена (ТУМ), Германия (опубликовано 25 февраля 2006 г.).

[2] "urn:nbn:de:bvb:91-diss20060316-1748151609" . URN NBN Resolver для Германии и Швейцарии. 22 марта 2006 г.

[1]

[2]