In this paper we make a case for the use of NoC

paradigm to develop future FPGAs in which large computational

blocks (cores) are connected to each other through

a packet switched communication network. We propose a

methodology to develop efficient and deadlock free routing

algorithms for such NoC platforms which can be specialized

for an application or a set of concurrent applications.

Application specific topology of communicating cores as

well as information about their communication concurrency

over time is exploited to maximize communication adaptivity

and performance. We demonstrate, both through analysis

of adaptivity as well as simulation based evaluation

of latency and throughput, that our algorithm gives significantly

higher performance as compared to general purpose

deadlock free algorithms like XY and Odd-Even.

One way to specialize a general purpose multi-core chip built using

NoC principles is to provide a mechanism to configure an application

specific deadlock free routing algorithm in the underlying

communication network. A table in every router, implemented using a

writable memory, can provide a possibility of specializing the routing

algorithm according to the application requirements. In such an

implementation the cost (area) of the router will be proportional to

the size of the routing table. In this paper, we propose a method to

compress the routing table to reduce its size such that the resulting

routing algorithm remains deadlock free as well as has high

adaptivity. We demonstrate through simulation based evaluation that

our application specific routing algorithm gives much higher

performance, in terms of latency and throughput, as compared to

general purpose algorithms for deadlock free routing. We also show

that a table size of two entries for each output port gives

performance within 3\% of the uncompressed table.

In this paper, we present a methodology to specialize the routing

algorithm in routing table based NoC routers. It tries to maximize the communication performance while ensuring deadlock free routing for an application. We demonstrate through analysis that routing algorithms generated by our methodology have higher adaptiveness as compared to turn-model based deadlock free routing algorithms for a mesh topology NoC architecture. Performance evaluation is carried out by using a flit-accurate simulator on traffic scenarios generated by both synthetic and real applications. Average delay is considered as performance index for comparison purposes. The routing algorithms generated by the proposed methodology outperforms deterministic and

adaptive routing algorithms. As compared to deterministic XY routing algorithm and adaptive Odd-Even routing algorithm we observe an improvement in delay close to 50% and 30% on average respectively.

A future NoC architecture must be general enough to allow volume production and must have features to specialize and configure to match and meet application's performance requirements. In this report, we present a methodology to specialize the routing algorithm in NoC routers to optimize its communication performance while ensuring deadlock free routing. Duato's theory of deadlock free routing is extended to incorporate application's communication requirements to

improve routing adaptiveness. We demonstrate through analysis and modeling and evaluation that routing algorithms produced by our methodology have higher adaptiveness and higher performance as compared to general purpose deadlock free routing algorithms.

Region concept helps to accommodate cores larger than the tile size in mesh topology NoC architectures. In addition, it offers many new opportunities for NoC design, as well as provides new design issues and challenges. The most important among these is the design of a deadlock free routing algorithm. In this paper, we present and compare two routing algorithms for mesh topology NoC with regions. The first algorithm is borrowed from the area of fault tolerant networks and is adapted for the NoC context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases.