Network on Chip
(NoC) as a new network paradigm is in need of effective design tools. In this
work we concentrate on the design of efficient NoC topologies. The problem is
modeled as a given set of network nodes placed over some grid with known
communication requirements. The goal is to minimize the network's sum cost,
where each wire is assigned a cost linear to its length; it is an NP-Hard
problem. Formal definition of the problem, solution form, validation method and
a quality measure are given. Concentrating on the uniform random traffic case,
we prove lower bounds for a topology cost, and introduce an asymptotically
optimal novel topology - the StarsMesh. After formally analyzing and proving
our claims, we turn to simulations and heuristic optimizations of the topology
for non-asymptotic cases. Simulations were run for networks of up to 1225 nodes
with varying wire capacity for each. Two optimization algorithms were
simulated: the Centers-Relocation algorithm showed improvements of 5-10% for
different relevant cases, and the Fill-Spares algorithm which showed highly
variable results saving 0-65% of the network cost for different cases. The work
is laying some mathematical and algorithmic groundwork for handling more
realistic NoC design problems to be uncovered through the next decade.
