M.Sc Thesis

M.Sc StudentShavit Ehud
SubjectNetwork on Chip (NoC) Topologies - A Cost-Minimization
Design Approach
DepartmentDepartment of Electrical and Computer Engineering
Supervisors PROF. Idit Keidar


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.