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

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

Климов А.В., Левченко Н.Н., Окунев А.С.
Институт проблем проектирования в микроэлектронике Российской академии наук,
Институт точной механики и вычислительной техники им. С.А. Лебедева, Москва,

aklimov@ipmce.ru, mage@hotbox.ru, anokunev@yandex.ru

Работа над созданием потоковой параллельной вычислительной системы (ППВС) ведется на протяжении ряда лет, основные идеи и принципы организации параллельных вычислительных процессов и архитектура вычислительной системы, в которой реализуются эти принципы, были разработаны еще под руководством академика В.С. Бурцева. Более подробно архитектура ППВС описана в работах [1,2], на рис. 1 приведена иерархическая система памяти ППВС.

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

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

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

Пары в ППВС образуются в модулях ассоциативной памяти (МАП). Затем по цепочке МАП — буфер готовых пар (БГП) — коммутатор пар (КМ пар) — исполнительное устройство (ИУ), поступают в свободные модули ИУ.

На данном этапе возможны следующие неравномерности вычислительного процесса:

  • П1) неравномерность, обусловленная программой узла, и, как следствие, различным временем обработки пар в исполнительных устройствах;
  • П2) неравномерность, обусловленная взрывным характером параллелизма задачи, проявляющаяся как переполнение буферов готовых пар (БГП);
  • П3) неравномерность, обусловленная различным темпом формирования пар в каждом из МАП. На данный фактор оказывают влияние хэш-функция, кратность и маскирование;
  • П4) неравномерность, обусловленная недостаточным уровнем параллелизма задачи, что приводит к недозагрузке всей системы, и отдельных ИУ в частности.
Рис. 1. Иерархическая система памяти ППВС

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

Токены в ППВС образуются в исполнительных устройствах, а также поступают извне — с ХОСТ-машины. Затем по цепочке ИУ — коммутатор токенов (КМ токенов) — буфер токенов — МАП, поступают в модули ассоциативной памяти, адреса которых формируются согласно ХЭШ-функции.

На данном этапе возможны следующие неравномерности вычислительного процесса:

  • Т1) переполнение модуля АП из-за некачественной ХЭШ-функции, в результате чего в группе модулей ассоциативной памяти образуется дисбаланс по количеству токенов;
  • Т2) программа узла, выполняемая в ИУ, может выдавать как один токен, так и неограниченное количество токенов;
  • Т3) переполнение буфера токенов может произойти, если узлы, обрабатываемые в ИУ согласно ХЭШ-функции, будут выдавать токены, направленные в одни и те же модули АП;
  • Т4) неравномерность, обусловленная обработкой множественного отклика в модуле АП, что может привести к задержке приема входных токенов;
  • Т5) неравномерность, обусловленная аппаратной реализацией группового узла, при которой он размещается в отдельном МАП, создавая повышенную нагрузку на него;
  • Т6) неравномерность, которая связана с перегрузкой отдельных направлений, приводящей к временной блокировке коммутатора токенов.

Неравномерности создают недозагруженные устройства и, как следствие, происходит падение общей производительности. Но это еще полбеды. Беда, если вследствие неравномерности происходит переполнение одного из МАП, в результате чего программа просто не может продолжать работу. Таким образом, основную проблему представляет неравномерность заполнения МАП, проявляющаяся как переполнение некоторых модулей.

Методы решения — многопоточное ИУ, перелив, откачка пар, ХЭШ-функция, откачка-подкачка токенов.

П1: перелив пар в свободные ИУ.

П2, П3: откачка пар[3]; сдерживание параллелизма[4].

П4: многозадачный режим.

Т1: иерархия АП (например, откачка-подкачка).

Т2: многопоточное ИУ.

Т4 и Т5: в условиях явно задаваемой функции распределения токенов групповой узел может быть распределен между несколькими МАП.

Т3 и Т6: адаптивная маршрутизация в коммутаторе токенов.

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

Литература

  1. Бурцев В.С. Новые принципы организации вычислительных процессов высокого параллелизма // Материалы Международной научно-технической конференции «Интеллектуальные и многопроцессорные системы — 2003». Т.1. Таганрог: Изд-во ТРТУ, 2003.
  2. Бурцев В.С. «Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ», Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ, М.:1997.
  3. Окунев А.С., Левченко Н.Н. Методы преодоления блокировки вычислительного процесса в вычислительной системе с автоматическим распределением ресурсов// Информационные технологии в науке, образовании, телекоммуникации и бизнесе. (IT + S&E'06), Гурзуф, 2006. С. 53—54.
  4. Левченко Н.Н., Окунев А.С. Аппаратно-программные методы ограничения «взрывного» параллелизма в вычислительной системе с автоматическим распределением ресурсов//Информационные технологии в науке, образовании, телекоммуникации и бизнесе. (IT + S&E'06), Гурзуф, 2006. С. 42—43.

 

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