Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Cybernetics and programming
Reference:

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

DOI:

10.7256/2306-4196.2014.4.12606

Received:

01-08-2014


Published:

15-08-2014


Abstract: The report reviews tasks that shall be solved during interprocessor interface modeling in parallel computing system with combined (mixed) topology based on hypercubes: binary, generalized, generalized ring, generalized ring hypercube with multiple buses. The first three of those structures can be modeled based on the last one because the algorithms of specifying their topologies are practically the same. Modeling of the hypercube with multiple buses has its own specifics because the presence of buses considerably affects diameter, capacity and complexity of the inteprocessor interface structure, because the data can be transferred between the nodes of the structure using both direct connections and buses. As the result of this the it is important to find the optimal path for transferring data taking into account the state of closest nodes, congestion of bus (buses) linked to the current node. For that purpose a status word is formed, representing busyness of a bus and direct links of connected to the node, the state of the node itself, data acceptance, transfer or transit. To simplify selection of the direction and rout the model uses the cost of a bus. Simulation of routing and transactions are rather simple because the structure has a high degree of dimension.  The main element of the modeling system is switching processor that carries out the main functions of the commutation environment. The process of developing the modeling system has the following requirements for the designing of the software based on the iterative-incremental model using object-oriented approach and DBMS due to the need to work with large amount of data at the high speed of processing. It also requires high-level programming languages, which allows building real-time applications with features of multithreading and scalability. The project uses analytical methods of the theory of computing systems, simulation method, methodology of object-oriented design. This article discusses problems related to the study of existing and emerging types of parallel computing system topologies based on hypercubes. The novelty of the study lies in the fact that for the first time the topology of the parallel computing system based on the generalized hypercube with multiple buses is presented. The main parameters are defined, the characteristics are studied on the base of the simulation, the comparison of the parameters with the well-known hypercube topologies is given.


Keywords:

binary hypercube, generalized ring hypercube, grid-tor, generalized hypercube, translation, routing, switching structure, simulation, links package, interprocessor interface


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

References
1. Bhuyan L. N. Agrawal D. P., “Generalized Hypercube and Hyperbus Structures for a Computer Network,” IEEE Transactions on Computers, December 1984 (vol. 33 no. 12), rr. 323–333.
2. Karavai M. F., Podlazov V. S. Rasshirennyi obobshchennyi giperkub kak otkazoustoichivaya sistemnaya set' dlya mnogoprotsessornykh sistem // Upravlenie bol'shimi sistemami. 2013. vyp. 45. M.: IPU RAN. s. 344–371. URL: http://ubs.mtas.ru/upload/library/UBS4515.pdf
3. Arimili B., Arimili R., Chung V. et al. The PERCS High-Performance Interconnect // 18th IEEE Symposium on High Performance Interconnects. 2009. p. 75–82.
4. Gergel' V.P., Strongin, R.G. Osnovy parallel'nykh vychislenii dlya mnogoprotsessornykh vychislitel'nykh sistem.// Nizhnii Novgorod: Izd-vo NNGU im. N.I. Lobachevskogo, 2003. 184 s.
5. Vlasov A.A. Mikheev P.V Kommunikatsionnaya sreda na osnove odnorodnoi kommutatsionnoi struktury // Trudy mezhdunar. konf. po inform. setyam i sistemam. ICINAS-2000.–SPb., 2000. S. 439-452.
6. Vlasov A.A. Parallel'naya vychislitel'naya sistema s masshtabiruemoi strukturoi // Tr. nauch. konf. po itogam n.-i. rabot Mar. gos. tekhn. un-ta. Ioshkar-Ola, 19-23 marta, 2001. / Ioshkar-Ola: MarGTU, 2001.-C. 54-70.--Dep. v VINITI 11.02.2002 № 277-V2002.
7. Artamonov G.T., Tyurin V.D. Topologiya setei EVM i mnogoprotsessornykh sistem. – M.: Radio i svyaz', 1991. – 248 s..
8. Vlasov A.A., Mikheev P.V. Kommunikatsionnyi protsessor, patent RU 2260841 C2, 20.09.2005
9. Sistema modelirovaniya kommunikatsionnoi sredy tipa giperkub. Svidetel'stvo ob ofitsial'noi registratsii programmy dlya EVM №2003611049 Zaregistri¬rovana v reestre programm dlya EVM. Moskva 05.05.2003
10. Vlasov A.A Kommutatsionnye struktury i kommunikatsionnye sredy. Laboratornyi praktikum. – Ioshkar-Ola 2002. – 100s