Mixed Integer Linear Programming (MILP) Based Aging-Aware Routing Algorithm for NoCs

Developed by Kshitij Bhardwaj, Dr. Koushik Chakraborty, Dr. Sanghamitra Roy of Utah State University’s Electrical and Computer Engineering Department


Technical Summary

Network-on-Chip (NoC) architectures have emerged as an impressive replacement of the traditional bus-based communication. However continuous technology scaling has made aging mechanisms, which limit the lifetime of the device, primary concerns in NoC designs. The two predominant aging problems are Negative Bias Temperature Instability (NBTI) and electromigration. Because the NoC performance directly affects the system level performance, it is critical to address these challenges efficiently.


The MILP based aging-aware routing algorithm is a novel method and apparatus for aging-aware routing. This method combines aging-aware constraints with other power-performance constraints and optimizes them using a formalized multi-objective approach. The invention includes an aging module that calculates an aging score for links and routers in a NoC for a previous epoch. Because a smaller number or routers are used a larger portion of the time, this algorithm balances the flow so that all routers receive a more equal amount of traffic. This is done by having a routing module dynamically route a flow through the links and the routers to satisfy routing criteria including a least total aging score for the links and the routers of the flow.


Competitive Advantages of MILP-based Aging Aware Routing

•  62% overhead reduction in the network latency.

•  46% overhead reduction in Energy-Delay-Product-Per-Flit (EDPPF).

•  41% increase in instructions per cycle.


Commercial Applications

•  Very Large Scale Integration (VLSI) Circuit Design

•  Any NoC related application

•  Anything involving microprocessors



•  U.S. Patent Application Publication: 2013/0235877 A1

•  Bhardwaj, K.; Chakraborty, K.; Roy, S., "An MILP-based aging-aware routing algorithm for NoCs," in Design, Automation & Test in Europe Conference & Exhibition (DATE), 2012 , vol., no., pp.326-331, 12-16 March 2012

•  Bhardwaj, K.; Chakraborty, K.; Roy, S., "Towards graceful aging degradation in NoCs through an adaptive routing algorithm," in Design Automation Conference (DAC), 2012 49th ACM/EDAC/IEEE , vol., no., pp.382-391, 3-7 June 2012


Patent Information:
Computer Science
For Information, Contact:
Christian Iverson
Utah State University
Koushik Chakraborty Sanghamitra Roy Kshitij Bhardwaj