ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Mathematic model of the user Network-on-Chip

The article was published in issue no. № 3, 2012 [ pp. 249-252 ]
Abstract:Microelectronics development provided implementation of complex electronic systems in integrated-circuit form. CAD systems, integral technologies and design cycle during design of electronic system are selected to reduce time of their creation, increase reliability and quality of the final product. The effectiveness of the design process can be improved with different approaches, e.g. SoC – system on a chip, SiP – system in a package, MCM – multi chip module etc. For design of complex MPSoC – Multiprocessors System on a Chip it was provided NoC technology – network on a chip. Architectures of specialized MPSoC applications include numerous heterogeneous computing cores and memory modules. Each core provides a limited set of applicable functions. Such projects can be provided with simple inter-core communication. NoC technology is used for design of communication environment that provides communication between different system modules. NoC consists of routers that are physically connected with each other. Each computation core and memory blocks are connected to NoC by means of interface to the network (RNI-interface). In general case, NoC technology suggests the use of homogeneous topology – the grid, which provides connection of the same number of cores to each switch that form the domain. Domains in the system interact and they represent a regular structure. Alternative solution presents usage of heterogeneous topology; this fact assumes consideration of specific core features during design stage of the designed system. Number of routers and switching method are selected with the purpose of minimization of signal latency, chip size and power consumption. Heterogeneous topology helps to design specialized applications with minimal versatile properties. There is provided mathematical model of the user network-on-chip (NoC). There is provided search shortest path in the flow chart. Obtained outputs of algorithm operation for NoC topology optimization are provided.
Аннотация:Развитие микроэлектроники обеспечило возможность реализации сложных электронных систем в интегральном исполнении. При разработке этих систем выбирают такие САПР, интегральные технологии и маршруты проектиро-вания, которые позволят сократить сроки проектирования, повысить надежность и качество получаемого решения. Для повышения эффективности процесса проектирования предлагаются различные методологии, например, система на кристалле (SoC – system on a chip), система в корпусе (SiP – system in a package), многокристальные модульные системы (MCM – multi chip module) и др. Для проектирования сложных мультипроцессорных систем на кристалле (MPSoC – Multiprocessors System on a Chip) была предложена технология «Сеть-на-кристалле» (NoC – network on a chip). Архитектуры специализированных приложений MPSoC включают многочисленные однородные вычислительные ядра и модули памяти. Каждое ядро обеспечивает ограниченный набор прикладных функциональных возможностей. Для таких проектов можно представить однозначные схемы межъядерной коммуникации. Технологию NoC используют при проектировании для построения коммуникационной среды, обеспечивающей взаимодействие модулей системы. NoC состоит из маршрутизаторов, физически связанных друг с другом. Каждое вычислительное ядро и модули памяти подключены к NoC через интерфейс ресурса к сети (RNI-interface). В общем случае технология NoC предполагает использование однородной топологии – решетки, которая обеспечивает подключение к каждому ком-мутатору одинакового числа ядер, образующих домен. Домены системы взаимодействуют и представляют регулярную структуру. Альтернативным решением является использование неоднородной топологии, что предполагает учет на этапе проектирования специфических особенностей ядер разрабатываемой системы. Выбор количества маршру-тизаторов и способа коммутации выполняют с целью минимизации задержки сигналов, площади кристалла и уровня энергопотребления. Использование неоднородной топологии ориентировано на проектирование специализированных приложений, обладающих минимальной универсальностью. Предложена математическая модель пользовательской сети-на-кристалле (NoC). Приведен алгоритм поиска кратчайшего пути в графе. Представлены полученные результаты работы алгоритма для оптимизации топологии NoC.
Authors: Mosin S.G. (smosin@vpti.vladimir.ru) - Vladimir State University named after Alexander and Nikolay Stoletovs, Vladimir, Russia, Ph.D, (dipuuu@gmail.com) - , (dipuuu@gmail.com) -
Keywords: irregular noc, design automation of noc, network-on-chip (noc)
Page views: 7914
Print version
Full issue in PDF (7.64Mb)
Download the cover in PDF (1.33Мб)

Font size:       Font:

Для решения проблем коммуникации архитектур мультипроцессорных вычислительных систем в работах [1, 2] предложена сеть-на-кристалле (NoC). Она состоит из физически связанных маршрутизаторов. Каждое ядро вычисления или хранения взаимодействует с NoC через сетевой интерфейс ресурса. NoC изменяема, поддерживает коммуникацию, основанную на пакетной коммутации, через многократные домены синхронизации, а также высокую полосу пропускания, что позволяет использовать параллельные коммуникационные технологии.

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

Для описания сети-на-кристалле использован математический аппарат теории графов. Сеть представляют ориентированным графом G(V, E), где каждый viÎV обозначает либо вычислительное ядро, либо единицу памяти, а ориентированное ребро графа ek=(vi, vj)ÎE обозначает канал связи от vi к vj.

Дополнительно введены следующие параметры, которые используются при автоматизированном проектировании топологии NoC.

·       Вес w(ek) каждого ребра ek=(vi, vj)ÎE обозначает пропускную способность каналов передачи данных.

·       Архитектура маршрутизатора характеризуется следующими параметрами: Yi – мощность, потребляемая на одной полосе пропускания трафика, поступающего в направлении входа для любого порта маршрутизатора; Y0 – мощность, потребляемая на одной полосе пропускания трафика, поступающего в направлении выхода для любого порта маршрутизатора.

·       Модель мощности физического канала передачи данных, где Yl обозначает мощность, потребляемую на одну полосу пропускания трафика, поступающего через канал, на единицу длины канала.

·       Общая топологическая структура ядер системного уровня.

·       Максимальное расстояние между маршрутизаторами Dmax.

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

Архитектуру представим через множество J(R, L, C), где R обозначает набор маршрутизаторов, используемых в будущей архитектуре; L – набор связей между двумя маршрутизаторами; C:V®R – функция преобразования типа «многие к одному», обозначающая подключение ядра к маршрутизатору.

Минимизацию расхода энергии выражаем как

где dist(j, l) – манхэттенское расстояние между двумя маршрутизаторами j и l [3, 4]. Минимизация энергопотребления происходит за счет синтеза оптимального маршрута между двумя узлами в сети (первичная цель) и уменьшения количества маршрутизаторов (вторичная цель). Математически цель минимизации может быть представлена двумя слагаемыми:

где s(i, k)=w(i, k)×yl, x(j, l) – x-рассогласование между двумя маршрутизаторами; y(j, l) – y-рас­согласование между двумя маршрутизаторами. Для этого нужно построить набор B кортежей маршрутизаторов, где каждый кортеж bi(ri, rj, …, rk)ÎB, ri, rj, …, rkÎR обозначает маршрут для пути e(vi, vk)ÎE(C(vi)=ri, C(vk)=rk) между двумя ядрами vi и vk таким образом, чтобы выполнялись первичная и вторичная цели.

Для достижения первичной цели предложено использовать алгоритм поиска кратчайшего пути в графе (алгоритм Дейкстры) [5]:

Присвоим d[a]=0, p[a]=a.

Для всех uÎV, отличных от a,

      присвоим d[u]=¥.

Пока $ vÏU,

      пусть vÏU – вершина с минимальным d[v].

Добавим вершину v к U.

      Для всех vÏU, таких, что vuÎE,

      если d[u]>d[v]+w[v, u], то

      изменим d[u]=d[v]+w[v, u],

      изменим p[u]=p[v].

Подпись:  а)                                б)
Примечание: а) алгоритм из [1]; б) предложенный алгоритм
Рис. 2. Сравнение различных техник синтеза 
топологии NoC
Здесь v – элемент множества вершин графа V; E – множество ребер графа; w[i, j] – вес (пропускная способность связи) ребра ij; a – вершина, от которой ищутся расстояния до других вершин; U – множество посещенных вершин; d[u] – результирующая переменная, значение которой по окончании работы алгоритма равно длине кратчайшего пути из a в u.

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

Для нахождения минимальных путей между маршрутизаторами используем тот же алгоритм, что и при поиске минимального пути внутри маршрутизатора, но со следующими обозначениями: V – множество маршрутизаторов; E – множество связей между маршрутизаторами; w[i, j] – вес (длина, время задержки) связи ij; a – маршрутизатор, от которого ведется поиск; U – множество посещенных маршрутизаторов; d[u] – по окончании работы алгоритма равно длине кратчайшего пути из a до u; p[u] – по окончании работы алгоритма содержит кратчайший путь из a в u.

После нахождения кратчайшего пути между маршрутизаторами кратчайший путь между ядрами можно найти следующим образом (рис. 1).

Вначале необходимо задать параметры отправителя ( src) и получателя (des).

Если src и des находятся внутри одного маршрутизатора, тогда используем найденные ранее минимальные пути внутри маршрутизатора и передаем данные по ним.

Если же src и des находятся в разных маршрутизаторах, тогда сначала сформируем минимальный путь между маршрутизаторами, а потом локально внутри каждого маршрутизатора.

Так как src и des находятся в разных маршрутизаторах, сначала строится путь между маршрутизаторами.

Рассмотрим пример работы алгоритма (рис. 2б) со следующими ограничениями: максимальная длина пути – 2,5 мм, количество портов на маршрутизаторе – 3.

Алгоритм включает пять шагов (см. табл.).

Шаг

Преобразование

Общая потребляемая мощность, мВт

Количество связей, шт.

Общая длина всех связей, мм

Количество маршрутизаторов, шт.

1

Начальная топология

375

11

6,5

0

2

Генерация ядер

490

24

26

0

3

Отображение ядер в маршрутизаторы

481

24

26

6

4

Поиск минимальных путей

286

6

5,25

6

5

Оптимизация топологии

250

5

5

5

Подпись:  
Рис. 3. Результат сравнения энергопотребления NoC, синтезированной алгоритмом из [1] (а) 
и предложенным алгоритмом (б)
Для каждого шага приводятся значения потребляемой энергии, количество связей, общая длина путей и количество маршрутизаторов [6, 7]. Очевидно, что после оптимизации топологии количество потребляемой энергии сократилось почти в 1,5 раза, количество связей – в 2 раза, длина путей уменьшилась с 6,5 мм до 5мм.

Проведенный анализ показал, что предложенный алгоритм позволяет получить топологию NoC с энергопотреблением на 30 % ниже, чем NoC из [1] (рис. 3).

В работе предложены математическая модель и алгоритм минимизации длины путей и энергопотребления сетей-на-кристалле с пользовательской топологией. Было проведено сравнение алгоритма синтеза NoC из [1] и предложенного алгоритма. Результатом является выигрыш в энергопотреблении на 30 %.

Литература

1.     Borkae S. Thousand core chips-a technology perspective // Proc. 44th Annual Design Automation Conference (DAC), 2007, pp. 746–749.

2.     Chathak K.S., Srinivasan K., Konjevod G. // Automated Techniques for Synthesis of Application-Specific Network-on-Chip Architectures, IEEE Tran. on Computer-Aided Design of Integrated Circuits and Systems, 2008, Vol. 27, no. 8, pp. 1425–1438.

3.     Benini L., Micheli G.D. Networks on chips: A new SoC paradigm // IEEE Computer, Vol. 35, no. 1, Jan., 2002, pp. 70–78.

4.     Мосин С.Г., Хассан Мд. Муид. Подход к синтезу специализированной сети-на-кристалле с неоднородной топологией // Проектирование и технология электронных средств. 2009. № 3. С. 8–12.

5.     Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. 960 с.

6.     Mosin S.G., Md. Muid Hassan. Design flow Oriented on INOC // In Proc. IEEE 2nd International Conference on Signals, Systems and Automation (ICSSA-2011). Gujarat, India, 2011.

7.     Mosin S.G., Md. Muid Hassan. The CAD Subsystem Supporting Design of Electronics Devices Based on Irregular NOC // The Proc. of Xth IEEE International Conference «The Experience of Designing and Application of CAD Systems in Microelectro­nics», Polyana-Svalyava, Ukraine, 23–25 Feb., 2011, pp. 178–180.


Permanent link:
http://swsys.ru/index.php?page=article&id=3253&lang=en
Print version
Full issue in PDF (7.64Mb)
Download the cover in PDF (1.33Мб)
The article was published in issue no. № 3, 2012 [ pp. 249-252 ]

Back to the list of articles