确定性并行编程模型下任务调度策略的研究

Research on the Strategy of Task Scheduling in Deterministic Parallel Programming Model

并行程序执行的不确定性给并行程序的开发、调试和测试带来了挑战,严重阻碍了并行软件的发展。确定性并行编程模型是保证并行程序确定性的途径之一,但是程序可能因保证确定性而带来性能损失。文章以dedup基准程序为案例,探索确定性共享内存并行编程模型DetSM下的任务调度策略。文章首先分析了原dedup的程序架构和调度模型,然后结合DetSM的特点,将两种确定性的调度策略--"轮询"和"一对一"相结合来设计适合本应用的任务调度策略。实验结果表明,本文最后改进的调度策略是很有效的,它使得改写的dedup在性能上可以和原dedup相比较,甚至超越原dedup。

The uncertainty in executing parallel program leads to some challenges for the developing, debugging and testing of parallel program, which severely blocks the development of parallel programs. The deterministic parallel programming model is one of the approaches of guaranteeing the certainty of parallel program, but the program may bring to some overhead due to ensuring certainty. This paper takes a benchmark, dedup, as an example to explore the strategy of task scheduling in a deterministic parallel programming model, DetSM. The authors first analyse the program framework and scheduling model of the original dedup. Then combining with the characteristics of DetSM, the paper designs a strategy suitable for this application by combining two deterministic scheduling strategies, round-robin and peer-to-peer. The experimental result shows that the proposed strategy is effective, which makes the performance of the rewriting dedup can match and even exceed that of the original one.