基于Memetic算法的多处理器嵌入式系统容错设计方法研究

Shrinking transistor geometries, aggressive voltage scaling, higher working frequency and heat dissipation increase the probability of both transient and permanent faults on electronic systems. Thus fault-tolerance is becoming an increasingly important issue in electronic system design, especially for multiprocessor embedded systems. Fault-tolerant design of multiprocessor embedded systems has become a severe challenge faced by electronic and computer science field. Many of the design problems belong to complex large-scale combinatorial optimization problem, while the traditional design space exploration (DSE) techniques no longer apply. In recent years, as a new category of meta-heuristic algorithm framework, memetic algorithms (MAs) have achieved remarkable success in a wide range of real-world applications. MAs employ general meta-heuristics (such as genetic algorithms) as global search and problem-specific heuristic as local search. With an appropriate coordination, MAs cannot only exhibit a good explorative ability as a population-based global search algorithm does but also deliver a good exploitive performance as a local search algorithm does. This project intends to develop MA-based DSE techniques for the key issues in the fault-tolerant design of multiprocessor embedded systems, including 1) joint optimization of hardening selection and task mapping based on co-evolutionary MAs and 2) checkpoint placement optimization based on multi-objective MAs for handling transient faults, and 3) task migration (or remapping) optimization based on dynamic MAs for handling permanent faults This object will provide important theory and techniques for the development of fault-tolerant design tools of multiprocessor embedded systems.

不断缩小的器件尺寸、越来越低的工作电压、越来越高的工作频率、以及越来越严重的散热问题使得电子系统的错误率日益提高，容错设计成为嵌入式系统设计中必不可少的重要内容。多处理器嵌入式系统的容错设计面临许多新的设计难题，多属于复杂的大规模组合优化问题，传统技术不再适用。Memetic算法是演化计算领域一类新兴优化技术，可以有效结合特定问题的启发式知识，获得较高的求解质量和求解效率。本项目针对当前多处理器嵌入式系统容错设计中存在的若干关键问题，基于Memetic算法思想，从新的角度出发，研究有效的求解方法，包括：1）基于Memetic协同演化算法，研究硬化选择和任务映射联合优化方法，2）基于Memetic多目标演化算法，研究检查点布局优化方法，和3）基于Memetic动态演化算法，研究任务迁徙优化方法。本项目的研究将为多处理器嵌入式系统EDA容错设计工具的研发提供重要的理论与技术准备。

不断缩小的器件尺寸、越来越低的工作电压、越来越高的工作频率、以及越来越严重的散热问题使得电子系统的错误率日益提高，容错设计成为嵌入式系统设计中必不可少的重要内容。多处理器嵌入式系统的容错设计面临许多新的设计难题，多属于复杂的大规模组合优化问题，传统技术不再适用。模因算法是演化计算领域一类新兴优化技术，可以有效结合特定问题的启发式知识，获得较高的求解质量和求解效率。本项目针对当前多处理器嵌入式系统容错设计中存在的若干关键问题，基于模因算法思想，从新的角度出发，研究有效的求解方法。特别的，由于多核片上系统的容错协同综合问题的解空间巨大，当前基于演化算法的协同综合方法效率较低。本项目首次提出在容错协同综合中将副本任务的映射和原始任务的映射在求解过程中独立出来：即采用演化算法优化原始任务的映射，采用启发式算法构造副本任务的映射。该方法极大地降低了演化搜索的搜索空间。进一步，本项目提出采用协同演化算法优化任务硬化和原始任务映射，从而对两个联合优化问题进行了相对独立的高效求解。另外，为进一步提高协调演化算法的效率，本项目结合优化任务硬化和原始任务映射的特点，设计了问题相关的局部搜索算子，并嵌入到协同演化过程中。我们在大规模的多核片上系统的容错协同综合问题上验证了我们的方法。此外，三模块冗余和两模块冗余是最常用的基于任务冗余的容错技术，但是它们有不同的时间和成本代价。为实现最优的设计，我们必须非常仔细地考虑对每个任务采用哪种技术。本项目考虑联合的任务硬化和任务映射问题，证明了一旦确定任务硬化，可以通过最小最大权值匹配得到任务映射的最优解。进一步，由于不同冗余技术的代价不同，我们采用了一种模因多目标优化方法。大量的实验验证了所提方法的有效性，通过结合模因多目标算法和传统多目标算法可以得到高度精确的最优解。本项目的研究为多处理器嵌入式系统EDA容错设计工具的研发提供了重要的理论与技术准备。本项目已发表SCI论文5篇，EI论文2篇。