Application of Exhaustive Search, Branch and Bound, Parallel Computing and Monte-Carlo Methods for the Synthesis of Quasi-Optimal Network-on-chip Topologies

P. 1–6.

Romanov A., Romanova I., Ivannikov A.

On the basis of an integrated network-on-chip (NoC) topologies optimality criterion, as well as applying the adjacency matrix to describe NoC topologies, exhaustive search method and its modification by using branch and bound and Monte Carlo methods are extended to the synthesis of NoC quasi-optimal topologies. Designed ScaNoC suboptimal topology synthesis algorithm is implemented on a high-level programming language which makes it possible to generate quasi-optimal topological solutions in accordance with the requirements to reduce hardware costs and the average distance between nodes. Proposed quasi-optimal topologies synthesis algorithm improvement by using the method of parallel computing allows speeding up the process of synthesis to 2117 times and getting topologies with the number of nodes up to 18.

Keywords: метод Монте-Карло, сеть на кристалле, network-on-chip, quasi-optimal network-on-chip topology, квазиоптимальная топология сети на кристалле, NoC design, NoC synthesis, проектирование СтнК, Monte-Carlo Method, синтез СтнК

In book

Proceedings of XV IEEE East-West Design & Test Symposium (EWDTS'2017)

Piscataway: IEEE, 2017.