Software & Systems

Для решения проблем коммуникации архитектур мультипроцессорных вычислительных систем в работах [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].

Здесь 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.

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

Для каждого шага приводятся значения потребляемой энергии, количество связей, общая длина путей и количество маршрутизаторов [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.