NAU Harvester System
THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM
Наукові журнали Національного Авіаційного Університету
View Archive Info| Field | Value | |
| Title |
THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM
АНАЛИЗ КВАЗИОПТИМАЛЬНЫХ ТОПОЛОГИЙ СЕТЕЙ НА КРИСТАЛЛЕ НА СООТВЕТСТВИЕ ГЛОБАЛЬНОМУ ОПТИМУМУ THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM |
|
| Creator |
Yaganov, P. O.
Pavlov, L. M. Romanov, O. Y. |
|
| Subject |
—
network-on-chip, quasi-optimal network-on-chip topology; networks-on-chip optimality criterion UDC 004.722 — сеть на кристалле; квазиоптимальная топология сети на кристалле; критерий оптимальности сетей на кристалле УДК 004.722 — мережа на кристалі; квазіоптимальна топологія мережі на кристалі; критерій оптимальності мереж на кристалі УДК 004.722 |
|
| Description |
The article considers the main approaches to the synthesis of networks-on-chip (NoC) on the basis of regular and specialized topologies; their advantages and disadvantages are characterized. The association of both approaches to the NoC synthesis based on the specialized and regular topologies by applying predefined optimal and quasi-optimal topologies is proposed; it makes possible to reduce the disadvantages of both approaches by combining their advantages. Therefore, the criteria of NoC topology optimality are defined. Besides, a new class of quasi-optimal topologies is proposed and also the requirements to quasi-optimal topologies are specified. The applications of Monte-Carlo method and evolutionary computation method makes it possible to synthesize quasi-optimal topologies with the number of nodes amounting the hundreds, but being in the local optimum, that does not guarantee the most optimal topologies finding. For the analysis of the obtained quasi-optimal topologies on their proximity to the theoretical optimum the approximated characteristics of theoretically possible optimal topologies for the given number of nodes and constraints by linear programming problem formulation and application of mathematical methods of optimization are found. The analysis of the obtained quasi-optimal topologies for the number of nodes of 25 shows that they have the efficiency characteristic, which is only 1,8–3,7% different from the efficiency characteristic of approximated optimal topologies. This demonstrates the high efficiency of the synthesized quasi-optimal topologies and the possibility of their application to the synthesis of NoCs.
В статье рассмотрены основные подходы к синтезу сетей на кристалле (СнК) на основе регулярных и специализированных топологий, охарактеризованы их преимущества и недостатки. Предложено объединение обоих подходов к синтезу СнК на основе специализированных и регулярных топологий путем применения заданных оптимальных и квазиоптимальных топологий, что дало возможность уменьшить недостатки обоих подходов, объединив их преимущества. Для этого определены критерии оптимальности топологий СнК и предложен новый класс квазиоптимальных топологий, а также определены требования к квазиоптимальным топологиям. Применение метода Монте-Карло и метода эволюционных вычислений позволило синтезировать квазиоптимальные топологии с количеством узлов, достигающим сотен, но находящихся в локальном оптимуме, что не гарантирует нахождение наиболее оптимальных топологий. Для проведения анализа полученных квазиоптимальных топологий на их близость к теоретическому оптимуму найдены аппроксимированные характеристики теоретически возможных оптимальных топологий для заданного количества узлов и ограничений путем формулирования задачи линейного программирования и применения математических методов оптимизации. Проведенный анализ полученных квазиоптимальных топологий для количества узлов 25 показал, что они имеют характеристику эффективности, которая лишь на 1,8–3,7 % отличается от показателя эффективности аппроксимированных оптимальных топологий. Это свидетельствует о высокой эффективности синтезированных квазиоптимальных топологий и возможности их применения к синтезу СнК. У роботі розглянуто основні підходи до синтезу мереж на кристалі (МнК) на основі регулярних та спеціалізованих топологій, охарактеризовано їх переваги та недоліки. Запропоновано об’єднання обох підходів до синтезу МнК на основі спеціалізованих і регулярних топологій шляхом застосування наперед заданих оптимальних та квазіоптимальних топологій, що дало можливість зменшити недоліки обох підходів, об’єднавши їхні переваги. Для цього визначено критерії оптимальності топологій мереж на кристалі, наведено новий клас квазіоптимальних топологій та визначено вимоги до квазіоптимальних топологій. Застосування методу Монте-Карло та методу еволюційних обчислень дало можливість синтезувати квазіоптимальні топології з кількістю вузлів, що сягає сотень, але таких, що знаходяться в локальному оптимумі, що не гарантує знаходження найбільш оптимальних топологій. Для проведення аналізу отриманих квазіоптимальних топологій на наближеність їх до теоретичного оптимуму було знайдено апроксимовані характеристики теоретично можливих оптимальних топологій для заданої кількості вузлів та обмежень шляхом формулювання задачі лінійного програмування та застосування математичних методів оптимізації. Проведений аналіз отриманих квазіоптимальних топологій для кількості вузлів 25 показав, що вони мають характеристику ефективності, яка лише на 1,8–3,7 % відрізняється від показника ефективності апроксимованих оптимальних топологій. Це свідчить про високу ефективність синтезованих квазіоптимальних топологій та можливість їхнього застосування до синтезу МнК. |
|
| Publisher |
National Aviation University
|
|
| Contributor |
—
— — |
|
| Date |
2013-02-08
|
|
| Type |
—
— — |
|
| Format |
application/pdf
|
|
| Identifier |
http://jrnl.nau.edu.ua/index.php/SBT/article/view/5682
10.18372/2310-5461.20.5682 |
|
| Source |
Наукоємні технології; Том 20, № 4 (2013); 394-397
Science-based technologies; Том 20, № 4 (2013); 394-397 Наукоемкие технологии; Том 20, № 4 (2013); 394-397 |
|
| Language |
uk
|
|