The Program Parallelization Method For Multi-core Platform

With the continues evolution of semiconductor process technology, it is now possible to integrate tens or hundreds of processors in a single chip and make an multiprocessor system-on-chip (MPSoC). But putting multiple cores on a chip dose not translate into performance unless well-formulated scalable parallel codes for the multicore is produced. The problem of parallel programming in an efficient way is regarded as the most difficult challenge faced by MPoC designs. Firstly, programmers have been already used to programming in a sequential style in a really long time. Secondly, decades of writing applications using the C/C++ language have left us a huge amount of legacy codes for a wide range of applications, and those are often used as reference implementations for MPSoC software. Finally, it is difficult to find an unified method to parallelize the various applications based to different multicore platforms.To solve those problems mentioned above, we propose a parallelization method for C programs which changes the sequential codes to parallel and can goes in depth for extracting pipeline parallelism in multi-layer loops. A tool for analyzing dependence relations hidden in the applications is developed by ourselves. The purpose of this method is to guide the parallel processing and improve its performance with as less as possible evolvement of programmers.The proposed method, firstly provides profiling and dependence analyzing for the source code to build the task dependence graph (TDG). Secondly, it transforms the original TDG to a directed acyclic graph model, which is defined as a task dependence graph after transfroamtion (TDGAT). Then, the tasks in the TDGAT are set with two-level priorities and hierarchically scheduled to generate a satisfied parallel scheme by successive refinement. Finally, the tasks are transformed into parallel objects and run on the target multi-core platform.The efficiency of our method is confirmed through case studies of two typical streaming applications, AES and T264 decoder. The experimental results on an eight-core emulation platform show that significant speedups,5.62x for T264 decoder and 5.12x for AES program, are achieved by the parallel programs generated using the proposed method.The method in the thesis is a heuristic approach with the following properties:1) The task dependence graph (TDG) model which can record both the control dependences and data dependences in a program is defined. This model is appropriate for any type of aplications.2) For solving the intricate dependence relations in the TDG, a special transformation method is proposed which is different from the conventional transformations for task graph model. It introduces different techniques for branches, loops and inter-iteration dependences respectively to eliminate the circle depedences.3) we set both dynamic priority and static priority for scheduling tasks. The dynamic priority makes the tasks on the critical path run prior, while the static one takes takes into account both the execution time and memory consumption of tasks. The goal of the scheduling is to minimize the execution time, and also takes into account mutually exclusive of conditional branch structures.4) we do research not only on the task parallelism but also on the pipeline parallelism for multilayer loop structures.