Multicore, Multithreaded Processors, Task Scheduling Study

This paper focuses on task scheduling for multi-core and multi-thread processor. Three duplication based task scheduling algorithms are presented. These algorithms have good performance, and its application on a real multi-core and multi-thread processor (network processor IXP) are demonstrated. It also show that how a uniform network programming environment could be built through address translation and iterative compilation techniques. Finally it describes a new network task scheduling algorithm which considers both throughput and latency. The contributions of this paper are as below:Proposed a new duplication based task scheduling algorithm for Fork-Join graph considering the communication limits between different processors, named TDC_FJ. The test results show that TDC_FJ is flexible and effective for Fork-Join graph and it achieves good performance and reduces the requirements of processors.Proposed a duplication based task scheduling algorithm with communication limits for general task graph, TDMSCL. It converts the ordinary task graph into fork and join graph, then apply the optimized result of fork and join graph to the scheduling of general task graph. TDMSCL converts task scheduling process into the process of optimizing a topological sequence. The algorithm tries to schedule each task node at its earliest start time to obtain good performance of the whole task. The merging is based on greedy policy to obtain deep coupling with low time complexity. The algorithm considers the occupation of communication channel. Compare to other task scheduling algorithms, TDMSL has better performance, which has less processor consumption and lower time complexity.Proposed an algorithm named RTE to eliminate redundant tasks, which resolves the redundant task problem of task scheduling base on duplication. The redundant tasks waste computing resources. RTE can act as an assistant method to improve the performance of duplication based task scheduling algorithm. Any duplication based task scheduling algorithm can integrate it easily. The test results show it can increase the performance of existing duplication based task scheduling algorithm in different degree.Built a uniform compiler back-end based on whirl2c for network programming environment Shangri-La. By address translation it resolved the problem of pointer sharing problem arose by the difference of memory access methods. By a iterative compilation framework it made the code size under control. By these techniques Shangri-la integrated two compilers for two different kinds of processors and hide the complicated network processor architecture to network programmers. This uniform programming environment simplifies the work of programming nowadays complicated network processors.Proposed a task scheduling algorithm LTTS for network application. Network application is different from normal parallel program, which mostly is data parallel. And network applications'performances are measured by throughput and latency while the normal ones measured by scheduling length. This paper presents a cost model based on network application and IXP architecture, and designed a network task scheduling algorithm LTTS for network application. This algorithm considers...