Research Of Memory-Access Management And Scheduling Optimization In Functional Parallelism

With the development of multi-core architecture,improving application's performance via parallelization has become the trend of future.To decrease difficulty of parallel programming and increase efficiency of computing resource utilization,functional parallelism programming model now is widely used in practice.Most of practical problems are belong to class of unstructured parallel program.Control flow in implementation of traditional functional parallelism programming model can introduce artificial latency in parallel applications.Additionally,functional parallelism programming model usually utilizes random work stealing scheduling algorithm to keep load balance when scheduling tasks in the application among different threads.However,in multi-core architecture,randomness in scheduling can cause unfriendly cache behaviour in memory access and lead to a performance loss.A task dependence graph programming model is proposed for unstructured parallel applications to relieve performance bottleneck.On the one hand,a program can be expressed as a directed acyclic graph consisted of task nodes and dependency edges and the scheduling of tasks in the program is directly driven by dependency relationship between tasks,which means part of tasks can be executed out of order in control flow,thus enhancing the performance.On the other hand,the runtime system in task dependence graph programming model uses work stealing scheduling algorithm to balance workload between computing resources.Adding affinity preference to thread which is attempting to stealing task in runtime system via collecting topology information of hardware on target machine,and thus reducing unnecessary cache miss during the execution of a program.Implementing task dependence graph programming model in functional programming framework FunctionFlow.The experiment results show that for several important parallel applications in numerical computation-QR factorization,Cholesky factorization and LU factorization of dense matrix,the waiting time of tasks in benchmarks written in dependence graph programming model is reduced and the performance can be improved by 38.8%,47.0%,51.4% respectively with a high scalability in the best case in comparison to traditional functional programming model.