THE ANALYSIS OF QUASI-OPTIMAL TOPOLOGIES OF NETWORKS-ON-CHIP ON MEETING THE GLOBAL OPTIMUM

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.