The Optimization Research Of Parallel Recursive Program Based On Cilk

Along with the fast development of multi-core architecture, it becomes more and more important how to realize efficient parallel programming to make use of the parallelism provided by the multi-core.However, when writing parallel program on traditional parallel programming languages, programmers need to know the bottom details and the structure of the program well; thereby it's needed that a new programming model for realizing parallel simply and efficiently. Studies have pointed out that the use of divide and conquer and recursive is great useful in realizing the aim. There is an algorithmic multithreaded language——Cilk, which can realize parallel recursion naturally. As a faithful extension of C, when building a Cilk program, a programmer can concentrate on structuring his program to expose parallelism and exploit locality, leaving the runtime system with the responsibility of scheduling the computation to run efficiently on the given platform. But too many procedures may be spawned which leads to excessive overhead when the parallelism is much more than de number of the CPUs. Even worse, it may lead to that the performance of parallel program is worse than serial program. So we need to reduce the cost of the too much spawning improve the performance.According to the computing process of the parallel recursion, we can summarize an performance model, which can infer the effect of the cost of spawning on the performance. Farther more, we can infer how much reducing the cost will affect the performance. A static optimization is proposed first, which contains optimization of parallel degree and optimization of balance. The former limits the total number of procedures according to the hardware platform, and it will stop procedure spawning and turn to invoke the serial clone when the procedure having spawned has become to some degree, which reduces the cost of paralleling. The latter limits the depth that the procedure can spawn. The differences of the ability to spawn procedure by procedure become much smaller and the work gap of different threads is also reduced. As a result, the performance increases steadily. And then a dynamic optimization is proposed, which maintenances a balance bound of procedures. It holds a certain parallel degree and load balance while little cost of spawning procedures is created.Then this paper extends the famous data reuse theory for circulation to a parallel recursion domain and proposes parallel data reuse theories for Cilk. The theory analyses a parallel data reuse model based on recursion and the reuse in Cilk parallel recursive programs based on static scheduling. Then it gives the measurement of them on different conditions.