THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM
DOI:
https://doi.org/10.18372/2310-5461.20.5682Keywords:
network-on-chip, quasi-optimal network-on-chip topology, networks-on-chip optimality criterionAbstract
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.References
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 с.
