THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM
DOI:
https://doi.org/10.18372/2310-5461.20.5682Ключові слова:
мережа на кристалі, квазіоптимальна топологія мережі на кристалі, критерій оптимальності мереж на кристаліАнотація
У роботі розглянуто основні підходи до синтезу мереж на кристалі (МнК) на основі регулярних та спеціалізованих топологій, охарактеризовано їх переваги та недоліки. Запропоновано об’єднання обох підходів до синтезу МнК на основі спеціалізованих і регулярних топологій шляхом застосування наперед заданих оптимальних та квазіоптимальних топологій, що дало можливість зменшити недоліки обох підходів, об’єднавши їхні переваги. Для цього визначено критерії оптимальності топологій мереж на кристалі, наведено новий клас квазіоптимальних топологій та визначено вимоги до квазіоптимальних топологій. Застосування методу Монте-Карло та методу еволюційних обчислень дало можливість синтезувати квазіоптимальні топології з кількістю вузлів, що сягає сотень, але таких, що знаходяться в локальному оптимумі, що не гарантує знаходження найбільш оптимальних топологій. Для проведення аналізу отриманих квазіоптимальних топологій на наближеність їх до теоретичного оптимуму було знайдено апроксимовані характеристики теоретично можливих оптимальних топологій для заданої кількості вузлів та обмежень шляхом формулювання задачі лінійного програмування та застосування математичних методів оптимізації. Проведений аналіз отриманих квазіоптимальних топологій для кількості вузлів 25 показав, що вони мають характеристику ефективності, яка лише на 1,8–3,7 % відрізняється від показника ефективності апроксимованих оптимальних топологій. Це свідчить про високу ефективність синтезованих квазіоптимальних топологій та можливість їхнього застосування до синтезу МнК.
Посилання
Axel J. Networks on Chip / J. Axel, T. Hannu // Kluwer Academic Publishers. – Dordrecht, 2003. – 303 p.
Taylor M. The Raw Processor – A Scalable 32-bit Fabric for Embedded and General Purpose Computing / M. Taylor, J. Kim, J. Miller // Proceedings of Hotchips XIII. – MIT, 2001. – pp. 3–6.
Saldana M. Routability Prediction of Network Topologies in FPGAs / M. Saldana, L. Shannon, J.S. Yue // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. – 2007. – Vol. 15. – No. 8. – pp. 948–951.
Dally W. Principles and practices of inter-connection networks / W. Dally, B. Towles. – Elseiver, 2004. – 550 p.
Корнеев В.В. Параллельные вычислительные системы / В.В. Корнеев. – М.: Нолидж, 1999. – 320 с.
Романов А.Ю. Оптимизация топологий сетей на кристалле / А.Ю. Романов // Вісник НТУ "ХПІ". Збірник наукових праць. Тематичний випуск: Інформатика i моделювання. – Харків: НТУ "ХПІ", 2011. – № 36. – С. 149–155.
Truong D.N. A 167-processor computational platform in 65 nm CMOS / D.N. Truong, W.H. Cheng, T. Mohsenin, et al. // IEEE Journal of Solid-State Circuits. – 2009. – Vol. 44. – No. 4. – pp. 1130–1144.
Romanov О. The Comparative Analysis of the Efficiency of Regular and Pseudo-optimal Topologies of Networks-on-Chip Based on Netmaker / O. Romanov, O. Lysenko // Advances and Challenges in Embedded Computing. Proceedings. – Montenegro, Bar: 2012. – pp. 13–16.
Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич // Учебное пособие для вузов. – М.: Высшая школа, 1986. – 319 с.
