Scheduling on-chip networks
Networks-on-Chip (NoC) have been proposed to meet many challenges of modern Systems-on-Chip (SoC) design and manufacturing. At the architectural level, a clean separation of computation and communication helps integration and verification. Networking abstraction of the communication infrastructure also promotes reuse and fast development. But the benefit is most visible when it comes to circuit and physical design. Networks can be made sparse and regular and thus facilitate placement and route. It is also much easier to reach timing and power closure as NoC shield communication details away from complicating analysis. Last but not the least, networks are flexible at the design stage and adaptable post-silicon. Many techniques of tackling process variation and interconnect failure can be built upon NoC. However, when interconnects are time multiplexed in a NoC, the network’s performance will deteriorate if it is not scheduled properly. For a wide range of applications, the traffic on the network can be determined before run-time and offline scheduling offers guaranteed performance and enables simple design. We propose a synthesis flow that takes the data flow graph of the application and a network topology as inputs; and outputs an offline schedule that can be deployed directly to the NoC. We analyze the complexity of combinatorial problems that arise from this context and provide efficient heuristics when polynomial time algorithms are not available assuming P [not equal to] NP. Results on LDPC decoding and FFT designs are compared with previous ones. We further apply our findings to parallel shared memories (PSM) and formalize the PSM architecture and its scheduling problem. An efficient heuristic is derived from our algorithm for unbuffered networks. Another application exemplifies how the NoC can be reprogrammed after silicon is back from fab in order to avoid failed interconnects due to process variation. A simple statistical model is studied and the simulation result is rather interesting. We find out that high performance and yield are not always at conflict if we are able to change the network schedule based on silicon diagnosis.
Showing items related by title, author, creator and subject.
Bansal, Shweta; Khandelwal, Shashank; Meyers, Lauren Ancel (2009-12)Complex biological systems are often modeled as networks of interacting units. Networks of biochemical interactions among proteins, epidemiological contacts among hosts, and trophic interactions in ecosystems, to name a ...
Kim, Yoojung; Lee, Wei-Na (2014-03)Social networking sites (SNSs) provide a unique social venue to engage the young generation in philanthropy through their networking capabilities. An integrated model that incorporates social capital into the Theory of ...
Contact network epidemiology: Mathematical methods of modeling a mutating pathogen on a two-type network Seilheimer, Robert L. (2008-05)With the threat of diseases like Sudden Acute Respiratory Syndrome (SARS) and Avian Flu that can lead to global pandemics, it is important to be able to understand how diseases spread through a population and predict how ...