Interprocessor interface modeling in parallel computing system with combined topology

Vlasov Aleksandr Aleksandrovich PhD in Technical Science Associate Professor of the Department of Design and Manufacture of Electronic Computing Means at the Volga State Technological University 424006, Russia, respublika Marii El, g. Ioshkar-Ola, pr.Gagarina, 24, kv. 26 a-vlasov2002@mail.ru Other publications by this author     Nekhoroshkova Lyudmila Georgievna Associate Professor, Department of Computer Science and System Programming, Volga State University of Technology 424000, Russia, Mari El, Yoshkar-Ola, pl. Lening, 3 nehorlg@gmail.com

Shestakov Aleksei Sergeevich student, Department of Design and manufacture of electronic computing means, Volga State University of Technology 424000, Russia, Mari El, Yoshkar-Ola, pl. Lening, 3 A1EX42@yandex.ru

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

Цель работы: разработка принципов и методов построения системы моделирования коммутационных структур ПВС с топологией гиперкуб.

На первом этапе моделирования основной задачей является определение реальной пропускной способности коммуникационной среды.

Задачи которые необходимо решить для достижения поставленной цели:

1. Формирование описания топологии КС удобной для задания в ЭВМ;
2. Создание модели пакетов связей и механизма их генерации
3. Разработка модели коммуникационого процессора
4. Разработка алгоритмов и средств разрешения конфликтов в КС;
5. Разработка алгоритмов и выбор программных средств для моделирования и отображения в имитационной модели КС параллельной работы узлов ПВС;
6. Определение последовательности этапов моделирования и их содержания;

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

В качестве топологии КС исследуются топологии : двоичный гиперкуб(ДК), обобщенный гиперкуб(ОГ), обобщенный кольцевой гиперкуб (ОКГ) ^[1,2,3] иначе решетка-тор ^[4], обобщенный кольцевой гиперкуб, дополненный магистралями (ОКГМ)^[5].

Передача сообщений в коммуникационной среде, в данном случае в виде сообщений, причем для упрощения экспериментов полагается, что в одном сообщении содержится один пакет.

В качестве алгоритма маршрутизации естественно применить методы покоординатной маршрутизации ^[4]. Вопросы поддержания когерентности в работе не ставятся.

Предварительно, необходимо уточнить основные понятия, которые довольно распространены в публикациях и достаточно широко трактуются авторами.

Коммутационная структура представляет собой отображение топологии межпроцессорных связей и средств коммутации для осуществления соединений.

Коммуникационная среда это комплекс состоящий из коммутационной структуры и средств поддержки интерфейса и когерентности памяти.

Обрабатывающий процессор – процессор, который выполняет основную вычислительную работу при решении задачи.

Коммуникационный процессор – основной элемент коммуникационной среды, который решает задачи маршрутизации, организации межпроцессорного интерфейса, транзита пакета данных и его временного хранения при передаче, а также поддержания когерентности памяти.

Для исследования различных вариантов структур удобно задавать КС в виде матрицы смежности. При моделировании выбора пути нужна не только матрица смежности, но и матрица путей. Матрица путей может быть рассчитана по любому алгоритму, который определяет кратчайшие пути.

Топология задается матрицей смежности и представляет собой набор узлов и связей между ними. Узел характеризуется координатами. Все узлы равноправны.

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

В ^[6] предложена, архитектура ПВС в основу структуры, которой положена топология со смешанным типом межпроцессорных связей (ОКГМ). Коммуникационная среда на основе этой топологии позволяет сохранить достоинства топологий с непосредственными и магистральными связями и устраняет присущие им недостатки^[7].

Архитектура ПВС, в основе которой лежит такая КС, обладает следующими достоинствам:

Постоянство диаметра при масштабировании. Магистрали объединяют группы узлов в каждом измерении, и при увеличении числа узлов в любом из измерений они присоединяются к уже существующим магистралям.

Простота трансляции. Скорость выполнения трансляции по магистралям (связям типа «один-ко-многим») значительно выше, чем у структур со связями типа «один-к-одному».

Простота поддержания когерентности данных в системе Увеличение пропускной способности и получение возможности высокоскоростной доставки сообщений. Пропускная способность структуры увеличивается за счет появления новых связей. Магистрали позволяют осуществлять скоростную доставку сообщений между удаленными узлами — максимальное время доставки постоянно и не превышает число измерений N.

Возможность варьировать отдельно, вычислительной мощностью и пропускной способностью.

В качестве основного элемента КС был предложен коммуникационный процессор^[8], который обеспечивает возможность как коммутации пакетов, так и коммутации каналов .

Основные функции КП. При передаче формируется служебная информация для задания маршрута, определения состояния межпроцессорных связей и состояния самого КП в виде его слова состояния, на основе которого осуществляется выбор направления передачи данных и выполняется, собственно, передача данных другому процессору.

При приеме данных выполняются следующие функции

- установка соединения;

-собственно прием данных;

-определение адреса и направление данных для транзита при передаче пакета или передача его собственному обрабатывающему процессору.

При выполнении транзита- определение ситуации в зависимости от слова состояния процессора и параметров пакета – направление непосредственно на передачу или промежуточное хранение пакета и допустимая длительность хранения пакета

Таким образом, модель коммуникационного процессора представляют в виде

,

где - величины задержек при передаче, приеме и транзите пакета данных.

S_т– параметры, характеризующие КП, координаты, слово состояния, число связей и др..

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

Коммуникационный процессор является универсальным средством для построения сложных структур ПВС. Главным достоинством является простота построения коммуникационной среды на его основе.

Среди недостатков данного процессора, прежде всего необходимоотметить высокую сложность внутреннего устройства данного процессора. Также требуется обработка внутри процессора сравнительно больших объемов данных. Для оценки аппаратных затрат производилось моделирование узлов КП на основе ПЛИС фирмы “ALTERA” в среде MaxPlus 11.

Основные элементы системы моделирования. КС задаются матрицей смежности или инцидентности. Формирование этих матриц осуществляется на основе заданных параметров числа n измерений i, числа узлов на измерение m_i и числа магистралей b_i на одно измерение.

Модель пакета связей задается количеством передач пакетов данных и их распределением по длине пути. Пакет данных снабжается адресом приемника , адресом источника и указывается его размер. В наиболее простом случае длина пакета фиксирована. Пакет связей формируется следующим образом. Задается число межпроцессорных передач, их распределение по длинам пути, каждый пакет данных снабжается адресом источника и приемника и дополняется параметром t_ж – «время жизни». Этот параметр определяет допустимое время для передачи пакета данных при промежуточном хранении данных в памяти КП при транзите. По достижении времени транзитной передачи значения t_ж присваивается наивысший приоритет и выполняется его аварийная передача.

Цикл работы модели включает следующие этапы:

1. распределение заданного пакета межпроцессорных связей и его фиксация;

2. определение состояния всех узлов на основе формирования слов состояния каждого узла;

3. попытка передачи пакетов узлов друг другу и прокладка пути;

4. передача пакетов в среде;

5. фиксация состояния системы после передачи пакетов данных узлам

6. анализ конфликтов и определение возможностей их разрешения.

Для уменьшения количества конфликтов КС на основе ОКГМ приоритет узлов задается номером узла на магистрали, причем в случае двух магистралей на измерение, все узлы будут равноправными, так как номера их будут на одной магистрали в прямом порядке, а в другой – в обратном.

В ПГТУ была разработана ^[9] и опробована в учебном процессе система моделирования коммутационной структур типа гиперкуб ^[10]. На этой системе были получены следующие результаты:

1. Влияние цены магистрали на реальную пропускную способность при топологии КС ОКГМ.
2. Влияние распределения пакета связи по длине пути на время доставки ПД.
3. Проведено сравнение реальной пропускной способности топологий ДК, ОГ, ОКГ, ОКГМ. В результате было установлено, что введение магистралей существенно увеличивает пропускную способность топологии ОКГМ и уменьшает число конфликтов при передаче данных, при незначительном увеличении числа межпроцессорных связей.

В настоящее время система моделирования совершенствуется в следующих направлениях.

Развитие системы моделировании коммуникационной структуры ПВС.

Сложность системы диктует выбор итерационно- инкрементной модели разработки и использование объектно-ориентированного проектирования.

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

В первой итерации разрабатывается следующие функции:

1. Распределение заданного пакета связей и его фиксация;
2. Определение состояния всех узлов на этой основе формирования слов состояния каждого узла;

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

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

Третья итерация состоит из разработки средств наглядного анализа конфликтов и определение возможностей из разрешения на основе языка С# с использованием среды разработки Microsoft Visual Studio.

Четвертая итерация дополняет функциональность реализации передачи пакетов в среде.

Пятая итерация состоит в доработке возможных функциональных дополнений.

Для наглядности осуществляется отображение топологических структур в трех измерениях.