Scheduling In Network-on-Chip

With the development of technology, traditional interconnection based on bus can not guarantee the requirement of system's communications, so network on chip emerges. This new kind of interconnection take switch as node, when it require routing, it can substitute switch with router, so this brings reuse technology to interconnection and forms network on chip based on network topology.Currently one of the main research is to assign tasks to proper processing element and schedule them as well as possible. Meanwhile, people represent this task by using node-labeled and edge-labeled Directed Acyclic Graphs (DAGs), The DAG scheduling problem has shown to be NP complete in general. So in this paper we focus on the DAG scheduling problem. At present the common DAG scheduling algorithms are List Scheduling, Clustering, Task Duplication, Genetic Algorithm and Simulated Annealing algorithms.The objective of traditional scheduling algorithm is to achieve best performance, but when it comes to heterogeneous multi-processors in Noc, we must also focus on the low-power scheduling problems. In this paper, we present an innovative low power scheduling algorithm for coarse-grained and fine-grained communication model. The experiment shows that compared with the traditional scheduling algorithms, the new algorithms can save significant energy.