Binary Modular Dataflow Machine ( BMDFM ) — это программный пакет, который позволяет параллельно запускать приложения на компьютерах с симметричной многопроцессорной обработкой (SMP) с общей памятью, используя несколько процессоров для ускорения выполнения отдельных приложений. BMDFM автоматически идентифицирует и использует параллелизм благодаря статическому и главным образом динамическому планированию последовательностей команд потока данных , полученных из ранее последовательной программы.
Подсистема динамического планирования BMDFM выполняет эмуляцию симметричной многопроцессорной обработки (SMP) машины потока данных с тегированными токенами, чтобы обеспечить прозрачную семантику потока данных для приложений. Никаких директив для параллельного выполнения не требуется.
Современные SMP с параллельной общей памятью представляют собой сложные машины, в которых для достижения высокой производительности необходимо одновременно учитывать большое количество архитектурных аспектов. Современные серийные SMP-машины для технических вычислений могут иметь множество тесно связанных ядер (хорошими примерами являются SMP-машины на базе многоядерных процессоров Intel ( Core или Xeon ) или IBM ( Power )). Согласно заявлениям производителей компьютеров, количество ядер на узел SMP планируется удваивать каждые несколько лет.
Многоядерные процессоры предназначены для использования параллелизма на уровне потоков, определяемого программным обеспечением. Следовательно, наиболее сложной задачей является поиск эффективного способа использования мощности многоядерных процессоров для параллельной обработки прикладной программы. Существующая парадигма статического распараллеливания OpenMP с библиотекой времени выполнения fork-join работает довольно хорошо только для регулярных вычислений на основе массивов с интенсивным циклом, однако методы распараллеливания времени компиляции в целом слабы и практически неприменимы для нерегулярных приложений:
Технология 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 и потока данных):
BMDFM предназначен для использования в роли механизма параллельного выполнения (вместо обычной библиотеки времени выполнения с разветвлением и объединением), способного автоматически параллельно запускать нерегулярные приложения. Благодаря прозрачной семантике потока данных BMDFM представляет собой простой метод распараллеливания для прикладных программистов и, в то же время, гораздо лучшую технологию параллельного программирования и компиляции для многоядерных компьютеров SMP.
Базовая концепция BMDFM опирается на стандартное оборудование SMP, доступное на рынке. Обычно поставщики SMP предоставляют свою собственную операционную систему (ОС) SMP с интерфейсом SVR4/POSIX UNIX (Linux, HP-UX, SunOS/Solaris, Tru64OSF1, IRIX, AIX, BSD, MacOS и т. д.). Поверх ОС SMP механизм выполнения многопоточного потока данных выполняет программную эмуляцию машины потока данных. Такая виртуальная машина имеет интерфейсы к языку виртуальной машины и C, обеспечивающие прозрачную семантику потока данных для обычного программирования.
BMDFM построен как гибрид нескольких архитектурных принципов:
Прикладная программа (входная последовательная программа) обрабатывается в три этапа: предварительная реорганизация кода (реорганизатор кода), статическое планирование операторов (статический планировщик) и компиляция/загрузка (компилятор, загрузчик). Результатом статического планирования является поток из нескольких кластеров, который передает многопоточный механизм через интерфейс, разработанный таким образом, чтобы избежать узких мест. Поток с несколькими кластерами можно рассматривать как скомпилированную входную программу, разделенную на маршалированные кластеры, в которых все адреса разрешаются и расширяются контекстной информацией. Разделение на маршалированные кластеры позволяет загружать их в многопоточном режиме. Контекстная информация позволяет обрабатывать итерации параллельно. Поток прослушивателя упорядочивает выходной поток после обработки нарушения порядка.
Подсистема динамического планирования 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 предоставляется в виде полных многопоточных версий для: