Speaker: Xiaohong Hao
Title: Title: Fault-Tolerant and Deadlock-Free Routing Protocol for Meshes Networks
Abstract: Recently I'm working on the fault-tolerant routing algorithm for mesh topology network on chip(NoC) systems. At the beginning, a brief introduction of NoC and Basic concepts (such as deadlock, livelock and virtual channels) is given in the talk. Routing is one of the core algorithmic theoretic problems in NoC. Research in recent years has brought about substantial progress in the field. I will present two related works in my talk, X-Y routing and face routing. X-Y routing is an efficient and deadlock-free routing algorithm in Mesh without fault. And face routing is a well-known distributed routing algorithm for planar graph. By combing these two, we can have a routing algorithm which can always route messages to their reachable destinations with cost bounded by $O(n)$ times optimal results. But deadlock-avoidance for the algorithm is still open.