ИТМиВТ - Институт точной механики и вычислительной техники С. А. Лебедева РАН
Институт точной механики и вычислительной техники им. С. А. Лебедева РАН - научно-исследовательский институт в области информационных технологий, вычислительной техники и микроэлектроники
English
Главная страница Контактная информация Карта сайта и поиск
Об институте Решения Проекты Образование

Распределение вычислений и данных по процессорным модулям в вычислительной системе массового параллелизма

А.В. Климов, А.С. Окунев, А.М. Степанов

В вычислительной системе массового параллелизма [1,2] предполагается, что для распределения виртуальных вычислительных узлов по модулям ассоциативной памяти (МАП) используется хеш-функция, которая обеспечивает их достаточно равномерное заполнение. Для достижения еще большей равномерности загрузки исполнительных устройств (ИУ), поток заявок на выполнение («пары») перераспределяется дополнительно динамически среди близких ИУ с учетом их текущей загрузки.

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

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

Могут возразить, что это тяжелым бременем ляжет на программу и программиста, и что надо не усложнять его и без того сложную работу. И что надо обеспечить аппаратно достаточно высокие пропускные способности самого «дальнего» уровня, ориентируясь на самую «тяжелую» нагрузку. Но такое решение скорее всего будет очень дорогим. И стоимость такого сетевого оборудования будет в общей стоимости системы иметь долю 90% и выше. А в результате удельная производительность в пересчете на рубль затрат будет все равно низкой. Так не лучше ли смириться с неоднородностью сети и начать развивать адекватную технику программирования? А в тех редких случаях, когда оптимизация потоков невозможна, мириться с ограниченной производительностью, которая лимитируется фактором, имеющие заметную долю в стоимости оборудования.

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

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

Мы уверены, что система массового параллелизма [1,2], основанная на потоковой модели вычислений, обеспечивает более комфортные условия для решения этой задачи, и постараемся здесь это показать. Но сначала уточним понятие модуля, среди которых будет происходить распределение вычислений. Раньше считалось, что токены распределяются среди МАП, а образованные в них пары — независимо среди ИУ. Причем, если токены требуется направлять в строго определенные МАП (иначе может не состояться их встреча), то каждая пара может перенаправляться в произвольное ИУ.

Теперь мы объединяем МАП и ИУ (возможно в некоторой пропорции) в один модуль и будем считать, что пары, образованные в некотором МАП, должны выполняться строго в собственном ИУ того же модуля. Задача обеспечения равномерности загрузки ИУ и заполнения МАП теперь решается совместно. Модули соединяются через коммуникационную среду токенов. При выдаче токена к нему присоединяется номер модуля назначения, который вычисляется специальной программируемой аппаратурой на основе ключа. Вычисляемую функцию, которую будем называть функцией распределения, определяет программист. (Ранее предполагалось, что это некоторая фиксированная в аппаратуре хеш-функция, аргументом которой является значение ключа после обнуления разрядов, находящихся под маской.) Если вычисленный адрес назначения совпадает с номером данного модуля, происходит прямая передача токена из ИУ в МАП, минуя коммутатор. Такое внутреннее «кольцо» должно быть очень быстрым. Токены, адресованные не «к себе», поступают через выходной порт в коммутатор, откуда возвращаются через входной порт.

Теперь мы говорим, что распределяются по модулям не токены, а виртуальные узлы. Соответственно, так же распределены токены, адресованные на эти узлы. Но и программа узла после его активации выполняется здесь же. Поэтому при порождении нового токена имеет смысл говорить не только об месте назначения, но и о месте его рождения. В частности, если узел N1 посылает токен в узел N2, и оба эти узла распределены в один модуль, то посылка этого токена заведомо будет замыкаться внутри модуля.

Введем понятие расстояния между модулями. Неформально, расстояние тем больше, чем больше время передачи и чем меньше обеспеченная пропускная способность канала передачи данных. В каждой топологии будет своя неоднородность по расстоянию. Но расстояние «до себя» в любом случае будет много меньше расстояния «до другого». Можно рассматривать расстояние как некоторую условную меру затрат на передачу токена из пункта A в пункт B.

Ставится задача организовать такое распределение узлов по модулям, чтобы не только обеспечить равномерность, но и минимизировать суммарные затраты на передачу токенов. А это значит, что большая часть передач должна падать на передачи «к себе», а среди остальных также должны преобладать передачи на близкое расстояние. Хеш-функция нас теперь не устраивает, поскольку она никак не учитывает свойства программы и ведет к тому, что все связи (пересылки токенов), становятся, как правило, самыми дальними.

Предлагаемый путь — введение управляемой программистом функции распределения токенов по модулям. Однако будет неправильно, если для каждой конфигурации системы придется задавать свою функцию распределения для данной программы. Наш подход обеспечивает относительную инвариантность от конфигурации. Все модули нумеруются номерами от 0 до K-1, причем так, что близкие модули имеют, как правило, близкие номера и наоборот. При выборе функции распределения (вычисляющей номер модуля по ключу) принимается во внимание только общее число модулей  K. Можно пойти еще дальше, добиваясь, чтобы функция распределения не зависела даже от количества модулей  K. Для этого занумеруем модули не целыми, а дробными числами вида k/K, где k=0…K-1. Функция распределения, заданная программистом, вырабатывает вещественное значение из интервала [0,1], которое затем автоматически округляется до «номера модуля».

Для каждой программы вопрос выбора функции распределения решается индивидуально. Например, пусть пространство задачи устроено как двумерная решетка с координатами (i,j) так, что токены передаются к соседним узлам. Тогда будет уместной функция zip(i,j), которая скрещивает битовые представления i и j: биты i ставятся на четные места результата, биты j — на нечетные. Несколько младших битов можно отбросить (главное, чтобы оставшихся хватило на то, чтобы пространство задачи было отображено на все модули).

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

На модели изучалось прохождение задачи «Умножение матриц». Использован систолический алгоритм Кэннона [3], в котором вычислительное пространство имеет вид двумерной решетки NxN, a данные передаются только между соседними узлами. Всего выполняется 2N3 операций и 2N3 пересылок. Размер матрицы N=128, конфигурация системы — 128 модулей (по 4 модуля в чипе, 4 чипа на плате, в системе 8 плат). Мера расстояния: внутри модуля — 1, внутри чипа — 2, внутри платы — 5, между платами — 20. Были использованы два варианта распределения узлов решетки по модулям. В первом варианте использовалась стандартная хеш-функция. Во втором двумерная решетка отображалась при помощи функции zip (скрещивание двоичных разрядов), при которой на каждый модуль отображается блок вычислительной решетки размера 8×8.

В первом варианте почти 85% всех передач совершались на самом верхнем уровне иерархии, где стоимость передачи равна 20. Во втором варианте таких было лишь 1.4%. Соответственно, внутримодульных передач (стоимость 1) в первом варианте было 0.08%, а во втором — 95%. В результате общее время счета во втором варианте сократилось почти втрое, и средняя загрузка ИУ составила 95% против 36% в первом варианте. Это означает, что функция распределения zip очень хорошо выделяет локальность в данной задаче и при отображении виртуального вычислительного пространства задачи в физическое пространство сохраняет локальность способом, близким к оптимальному.

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

Суть нашего предложения выражают следующие тезисы:

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

Литература

  1. Бурцев В.С. Новые принципы организации вычислительных процессов высокого параллелизма // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы — 2003». Т.1. Таганрог: Изд-во ТРТУ, 2003.
  2. Бурцев В.С. Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ. «Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ», М.:1997.
  3. Cannon, L.E., A Cellular Computer to Implement the Kalman Filter Algorithm, PhD thesis, Montana State University, Bozeman, MT, 1969.

 

© 1948—2016 «ИТМиВТ»
Версия для печати Контактная информация