面向MPSoC的确定性结构化并行程序设计与分析方法研究

Multi-core processors have been widely used in embedded and realtime systems to meet the needs on high performance computing of compute-intensive applications. However, current approaches to parallel programming based on threading model lead to overly complexity in program reasoning and analysis. The challenges of parallel programming, as well as the non-deterministic execution of parallel programs, lead to unreliable and unpredictable softwares for embeded and real-time systems. Structured parallel programming is a more promising approach to design and implement parallel algorithms, as efficent and reliable programs can be designed with the composition of a number of common parallel patterns. Some of the well choosed paralel structures not only lead to a proper program structure, but also is deterministic in semantics. This research introduces deterministic and structured parallel programming for MPSoC(multiprocessor System-on-Chip) platforms to simplify the reasoning and analysis of parallel programs. The objective is to develop simple and domain specific parallel constructs for embedded applications. In addition to build a sound and complete race detector to verify the determinism of these programs, this project also explores various program analysis based on the proper program structure, including WCET analysis, deterministic profiling based energy analysis and optimization. The greatest impact of this project will be a novel programming approach for MPSoC platforms and technologies to improve software productivity, reliability and predictability in embedded and realtime systems.

为满足计算密集型应用对高性能计算的需求，多核处理器目前已经在嵌入式和实时系统中得到了广泛的应用，然而现有基于线程模型的并行程序设计方法使并行程序的推理与分析变得非常困难，程序的执行也具有不确定性，因此极大地影响了嵌入式实时系统的可靠性和可预测性。结构化并行程序设计中采用特定并行结构及其组合嵌套完成并行算法的描述，程序具有良好的结构特征，且部分并行结构能够从语义上保证执行的确定性。本课题提出将确定性结构化并行程序设计方法引入到嵌入式多核系统中，探讨使用精确和完全的数据竞争检测技术对该类程序进行确定性验证的方法；研究如何利用程序的良好结构特征简化并行程序的推理与分析工作；结合嵌入式多核平台的硬件特征，探讨确定性结构化并行程序的WCET分析算法，基于profiling技术的系统能耗分析与优化方法。本课题的研究对提高嵌入式并行软件的设计与验证效率，提高实时系统的可靠性和可预测性具有重要的意义。

现有基于线程模型的并行程序设计方法使并行程序的推理与分析变得非常困难，程序的执行也具有不确定性，因此极大地影响了嵌入式实时系统的可靠性和可预测性。结构化并行程序设计中采用特定并行结构及其组合嵌套完成并行算法的描述，程序具有良好的结构特征，且部分并行结构能够从语义上保证执行的确定性。本课题提出将确定性结构化并行程序设计方法引入到嵌入式多核系统中。课题组成员经过3年的研究取得如下研究成果：1）基于脚本语言设计并实现了结构化并行程序的确定性验证方法；2）面向MPSoC系统，提出一种基于脚本语言的结构化并行程序设计框架，能够对硬件系统和软件系统进行建模，可以方便地实现从逻辑任务到硬件执行单元的映射；3）设计并实现了适用于结构化并行程序的基于访问集合的数据竞争检测算法，能够对结构化并行程序的确定性进行验证；4）课题还进一步分析了结构化并行程序的WCET分析方法，基于任务级Trace的获取方法以及相应的分析方法，讨论了Cache/SPM存储分配方法。本课题的研究对提高嵌入式并行软件的设计与验证效率，提高实时系统的可靠性和可预测性具有重要的意义。