IP Core Design of Task Scheduler to Support Out of Order Execution in an MPSoC Environment
In this paper the design of an IP core of Multiprocessor System on Chip (MPSoC) in the context of microarchitecture of the Scheduling Processor targeted for multicore systems is explored. This scheduling processor schedules the tasks i.e. units of computation in parallel for execution on different processors and IP cores. As this model is dealing with Out of Order (OoO) execution, the data dependencies like Read after Write (RAW) Write after Read (WAR) and Write after Write (WAW) imposes the challenging constraints on the direct use of techniques like register renaming and dynamic scheduling at instruction level. The scoreboarding algorithm with parameter renaming technique at task level analyzes the data dependencies in order to solve the stalling problem occurring in OoO execution. Thus the scheduler schedules different tasks in OoO manner. The model for the same has been verified by using resulting timing diagram. The results demonstrate that the model can largely release the burden on programmers as well as uncover the task level parallelism (TLP) Keywords Multiprocessor System on Chip, Out of Order execution, scoreboarding algorithm, register renaming, data dependencies, stalling, task scheduling. INTRODUCTION Multiprocessor system on chip has been seen in main stream since last few years [1] Companies like Xilinx and Altera have prime focus of research on this emerging area. The development of MPSoC begins from the multi core central processing unit. It is a platform that contains multiple processing elements with specific functionalities which are usually heterogeneous. However, due to its heterogeneous instruction set architectures, software tool chains and programming interfaces, it has presented many challenges to efficient designing and implementation of rapid prototype for diverse applications. The most promising future processor architectures are considered as the combination of reconfigurable computing and multi core technologies [1] However, there are some critical issues like computational capabilities, scalability, programmability, flexibility, power consumption and so on, which are becoming increasingly important. Such raising demands have resulted into the outgrowth of FPGA based MPSoC composed of a variety of heterogeneous computational units. Whereas, OoO execution is a paradigm used in most highperformance microprocessors to make use of instruction cycles that would otherwise be wasted by delay. In this paradigm, a processor executes instructions in out of order as soon as the input data is available, instead of their original order in a program. As it allows execution with less waiting time, the performance definitely improves. Also the process technology has improved and per units more transistors can be fitted in the same die area, hence adding new features to the system becomes effectively easy. Thus dynamic scheduling can easily be implemented to build cost effective system. In basic pipelining the system uses in order instruction issue technique due to which if an instruction stalls rest all instructions are stalled. In contrast to this, the OoO execution has capability to schedule the ready instructions independently. Therefore to solve the stalling problem OoO execution technique is used for multi cycle task execution, as this study focuses on multi cycle task execution. Dynamic scheduling is a useful scheduling technique for multi cycle instructions systems. Scoreboarding and Tomasulo are two such effective methods for dynamic scheduling, out of which this study implements scoreboarding algorithm for OoO parallel execution of task scheduling. Thus an IP core of task scheduler intending to solve the data dependencies during OoO execution using dynamic scheduling is developed in MPSoC environment. RELATED STUDY Rigorous research is being done on MPSoC regarding the critical issues like computational capabilities, programmability, flexibility, scalability and power consumption. By using parallel programming paradigm the computational capabilities can be achieved. Such parallel task execution models have been studied for parallel computing machines during the past decades. Initially, many task based parallel programming models were popular like Cilk [2] to enhance ILP to TLP. Mostly it was focused on symmetric multiprocessor but it was unable to support fully automatic parallelization. So the programmers have to handle the task scheduling and mapping International Journal of Engineering Research and General Science Volume 3, Issue 3, Part 2 May June, 2015 ISSN 2091 2730 436 www.ijergs.org schemes manually. Some of them focused on the utilization of reconfigurable FPGA platform and integration of acceleration engines, such as Chimaera [3] Platune [4] and MOLEN [5] Also models like Wave Scalar [6] combined both static and dynamic dataflow analysis in order to exploit more parallelism. Later on with the tremendous advancements in chip integration, to solve the programming wall problem, MPSoC programming models such as StarSs [7] [8] Oscar [9] and CellSs [10] are taken into consideration. These models implicitly schedule work and data, thereby saving the efforts of programmer by explicitly managing parallelism. These models share conceptual similarities with the out of order superscalar pipelines, such as dataflow scheduling and dynamic data dependency analysis. The traditional algorithms, such as Scoreboarding and Tomasulo, can dynamically schedule the instructions for OoO execution and explore ILP with multiple arithmetic units. Task Superscalar pipeline is an abstraction of out of order superscalar pipelines which can use processors as function units. It dynamically identifies task level parallelism, detects intertask data dependencies, and executes the tasks out of order [11] An objectbased dataflow execution with data dependencies analysis method achieve even more dataflow like execution and exploit higher degrees of concurrency. Using this model the parallel execution of statically sequential programs is achieved. In a dataflow fashion, it dynamically parallelizes the execution of suitably written sequential programs on multiple processing cores [12] OoOJava is a compiler assisted approach that uses developer annotations along with the static analysis to provide an easy to use deterministic parallel programming model. This method is based on task annotations that instruct the compiler to consider a code block for OoO execution [13] MP Tomasulo is a dependency aware automatic parallel task execution engine for sequential programs. It detects and eliminates WAW and WAR inter task dependencies in the dataflow execution by applying the instruction level Tomasulo algorithm to the MPSoC environment. So this system operates tasks in OoO on heterogeneous units but it has the overhead of scheduling which could be reduced [14] In order to reduce these overheads, Task scoreboarding was developed. It is a data hazards detection engine for OoO task execution. It considers IP cores and processors as function units and treats tasks as abstract instructions. It can analyze intertask data dependencies at runtime and issues tasks to heterogeneous function units automatically with parameter renaming techniques [15] PROPOSED DESIGN The OoO task scheduler proposed here is intended to provide the high speed execution by solving the stalling problem in OoO execution due to data dependency at TLP. The proposed work, execution flow for it and the algorithm implementation is discussed in this section. A. Proposed work The distinctive heterogeneous MPSoC hardware consists of multiple processors and a variety of heterogeneous IP cores for dedicated applications to extract the task level parallelism. Accountable components of such systems are computing processors, hardware IP cores, scheduling processor, interconnect modules, memory and peripherals. This paper is going to focus on the scheduling processor part, because handling immense number of tasks is a very critical job. This proposed design is a parallel task execution model for the fast execution of such system at TLP. It supports out of order execution along with register renaming mechanism by dynamically scheduling the tasks. The proposed block diagram for IP core implementation of task scheduler to support OoO execution in an MPSoC environment is shown in Fig. 1. The block diagram consists of two computing processors and three IP cores interfaced with the scheduling processor which uses scoreboarding algorithm for dynamic scheduling. Scoreboarding can provide a light weight task hazards detection engine for OoO execution, its architecture is simple, which brings smaller scheduling overheads and for TLP, WAW and WAR data dependency do not encounter as much as at instruction level [15] Therefore here scoreboarding algorithm is preferred instead of Tomasulo. Fig. 1 Block diagram for IP core design of task scheduler to support OoO execution B. Microarchitecture of scheduler processor The microarchitecture of scheduler processor is shown in Fig. 2. The scheduler processor fetches the task instructions from the register file which represents invocation of a task. It decodes each task instruction and then schedules it to the computing processors Scheduler Processor Scoreboarding Algorithm Interface 1 Interface 2 Interface 3