Date of Award

Spring 2013

Project Type

Thesis

Program or Major

Computer Science

Degree Name

Master of Science

First Advisor

Michel Charpentier

Abstract

To create a viable network on chip, many technical challenges need to be solved. One of the aspects of solutions is the routing algorithm: how to route packets from one component (e.g., core CPU) to another without deadlock or livelock while avoiding congestion or faulty routers. Routing algorithms must deal with these problems while remaining simple enough to keep the hardware cost low.

We have created a simple to implement, deadlock free, and livelock free routing algorithm that addresses these challenges. This routing algorithm, Weighted Non-Minimal OddEven (WeNMOE), gathers information on the state of the network (congestion/faults) from surrounding routers. The algorithm then uses this information to estimate a routing cost and routes down the path with the lowest estimated cost.

A simulator was developed and used to study the performance and to compare the new routing algorithm against other state of the art routing algorithms. This simulator emulates bit reverse, complement, transpose, hotspots, and uniform random traffic patterns and measures the average latency of delivered packets.

The results of the simulations showed that WeNMOE outperformed most routing algorithms. The only exception was the XY routing algorithm on uniform random and complement traffic. In these traffic patterns, the traffic load is uniformly distributed, limiting the opportunity for an improved route selection by WeNMOE.

Download

Share

COinS