Scheduling And Mapping Algorithms For Real-Time Applications On NoC

As semiconductor technology continuing to develop, more and more cores will be integrated on a single die to offer high-computing-capacity and low-power-consumption processors. Conventional point-to-point and bus-based communication mechanism cannot afford the rapidly increasing on-chip communication Networks-on-Chip (NoC), which connects cores together by networks and offers packet switched communication among cores, provides very high on-chip communication bandwidth. It has been widely accepted that the NoC paradigm will be the default design choice for future large-scale multi-core processors.Scheduling real-time communication set in NoC is different from multiple resource scheduling, since the special structure of NoC, a communication task may simultaneously occupy multiple physical links, which leads to competing physical links. For real-time applications, the current study can only solve some specific cases in real-time communication scheduling, which is lack of versatility. Due to cyclic communication in NoCs and its architecture feature, this thesis proposes a new application scheduling algorithm EPOGen. Based on preamble related research, this algorithm provides a real-time scheduling scheme for complex cyclic communication set, which can solve various types of real-time scheduling problem of communication set.Because of the network-like architecture feature of NoC, a critical step in the system design on NoCs is the application’s mapping. If tasks are allocated to different locations, the sources and destinations of the communications would be changed accordingly. Therefore, the different mapping strategies between tasks and processing elements will affect the real-time performance of communications. This thesis proposes a new mapping polynomial algorithm RTMAP. This algorithm is divided into three steps:preliminary mapping, further mapping and optimaized mapping. In the premise of minimum communication cost, this mapping algorithm further enhances real-time performance of EPOGen algorithm scheduling communication set.Experimental results show that, RTMAP improves the real-time performance of applications and minimize the total communication cost. Compared with classical algorithm FPA and NMAP, EPOGen and RTMAP algorithm in this thesis can significantly improve real-time of application with a little communication cost.