Research On Migration And Optimization Of SPMD Programs

The parallel and heterogeneous systems which consist of multi-core and many-core have been applied to many aspects of society. However, parallel programs for these systems lack of portability. On the one hand, the current multi-core and many-core architectures have great difference in system structures. Programmers must consider the influence of different architectures when programming; On the other hand, parallel applications become more complex, which brings many different designs of parallel programming models. These parallel programming models have different characters and lack of uniform standards. Therefore, researchers work hard to seek a general programming model and method, which could make programs run on different parallel architectures without changing. This goal will help to improve the reality that compiler and corresponding tool is far behind the development of multi-core and many-core processor, and relieve the pressure of software development in multi-core and many-core programming.SPMD is one of the most important programming models in parallel field. Extending the migration ability of SPMD program could make the same application run on architectures with different parallel granularity. This thesis pays attention to the key technology of SPMD program migration, which includes migration framework establishment, tasks and memory abstraction, migration algorithm design and implementation and so on. The main research contents and contributions are as follows:1. This thesis proposes a thread mapping model and hierarchical processing mechanism, on which the SPMD program can be migrated between architectures with different parallel granularity. Hierarchical thread organization is one of SPMD programs features. Fine-grained threads often communicate through synchronization, while thread blocks with coarse granularity can be independent of each other. Based on the coarse-grained parallelism of traditional multi-core architecture, through processing fine-grained threads serially and simulating synchronous communication, the SPMD migration could migrate for multi-core or many-core architectures with different parallel granularity.2. A synchronization detection and processing method based on dependency analysis is proposed, which can process explicit and implicit synchronization between threads correctly. Communications between threads in a SPMD program mainly rely on synchronization. However, SPMD programs not only have explicit synchronication implemented by synchronized statements, but also have implicit synchronization maintained by hardware parallel execution. When migrate SPMD programs to different parallel architectures, the semantic of explicit and implicit synchronization must be maintained. By dependence analysis, SPMD implicit synchronization is detected and treated with explicit synchronization together, which solves the problem efficiently.3. A weighted priority register allocation method is proposed. It maps SPMD memory model to the target architecture efficiently. The memory model map is one of the key factors affecting the running speed of SPMD program after transplantation. The memory hierarchies of target multi-core or many-core architecture is fixed, therefore, the program variables must be allocated in the most reasonable style. Based on weighted priority, the register allocation algorithm is able to allocate variables to registers or memory reasonably, which solves the problem of register allocation efficiently.4. This thesis accomplishs the whole function vectorization in SSA form, accelerating program performance after migtation. Optimization is one of the most important stages in the software migration. Most of current multi-core and many-core architectures have SIMD components, and vectorization in reasonable way can accelerate program running after translation. Through implmenting whole function vectorization in the SSA low level expression, the influence of complicated control flow is weakened and the program gets faster speed.5. A method of convergence and scalar identification is proposed. This method improves the whole function vectorization and accelerates the speed of the program furtherly. Redundant instruction and data exist between threads of SPMD program. Through analysing control and data information in the control dependence graph, convergent control flow paths and scalar instructions are identified. Convergence path does’ t need add predicate vectors and scalar variables need not be converted into vector data. Therefore, the effects of vectoration are enhanced.The proposed model and the related algorithm have been realized and applied in the system developed by research group. The experiment result shows that the model and algorithm are reasonable, correct and effective.