Multi-level Spm Based Parallel Programme Optimization

The hardware-managed memory hierarchy, which is represented by cache memory hierarchy, has gain great success as a solution to the "Memory Wall" problem. However, with the development of technics and technology, lots of limitations and defects of the problem emerge gradually, specifically in the aspects of performance, power consumption, chip area and so on. To solve these problems, the software-managed memory hierarchy has been proposed, which has attracted many researchers'attention. Scratchpad Memory (SPM), as a software-managed on-chip memory, shows more advantages than hardware management based cache in performance, power consumption, chip area and other aspects.Multi-level scratchpad memory hierarchy has great significance for the performance of on-chip multi-processor. The paper mostly focuses on the study of parallel optimization of the on-chip multi-processor system with multi-level scratchpad memory hierarchy, and proposed three algorithms with heuristic policy for associated scheduling of task and data. The first algorithm is a local greedy scheduling algorithm (LGA). The algorithm gets the data partition based on the list scheduling of tasks with local greedy policy. To remedy the defects caused by the local greedy policy in LGA, a second global prediction scheduling algorithm (GPA) was introduced. The paper also researched a rotation scheduling algorithm for the development of inter-iteration parallelism, which is based on the dependent retiming technology. The author implemented the algorithm in a compiler, which automatically carries out the parallel optimization method.Meanwhile, the software architectural simulation technology is important to the research of multi-level scratchpad memory hierarchy, which serves as a means of validation of the algorithms proposed in this paper. The author developed Sim-SPM, a simulator for the research of multi-processor on chip with multi-level scratchpad memory hierarchy, which is based on the SimpleScalar simulator. During the design and development process, the author successfully resolved several obstacles of implementing the Sim-SPM simulator, such as the multi-processor environment simulation, extensions of memory management instructions and the virtual memory space simulation of scratchpad memory. The compatibility of the existing instruction set in Sim-SPM makes the simulator quite practicable. To attain simulation speed and accuracy of the simulator, the author carried out a detailed evaluation test and validated that the Sim-SPM simulator can meet very well the verification needs of the on-chip multi-processor with multi-level scratchpad memory hierarchy.Finally, the author tested the three algorithms proposed in this paper with several typical benchmarks on the Sim-SPM simulator. Several aspects had been verified through the experiment, including a preliminary performance comparison, comparion with the approximate optimal solution, the influence of target architecture on algorithm performance and so on. The experimental results show that the proposed algorithms for task scheduling and data partition have a guiding significance for the software management of multi-scratchpad memory hierarchy on the multi-processor system on-chip.