A Scheduling Algorithm for Network on Chip

Network on chip can be viewed as processors from various families residing on a chip. Programs issued to a particular processor type can be divided into sequential and parallel code. The processors are assumed to be connected to each other as a directed graph. The parallel code is called as a task. Each task is characterized by an estimated time for completion. This paper proposes a method to determine the allocation of the parallel tasks during program execution to the processors of the same type to achieve optimal execution time. The proposed model assumes shared memory model. A linear programming model is developed to determine the number of tasks allotted to each processor belonging to a family for any parallel code, given the average waiting time for each of the processors in the family. The proposed algorithm is simulated with an example which gives 18% improvement in performance over round robin allocation of tasks.