论文部分内容阅读
在硬实时系统的设计中,高可靠性、高性能、低成本是三个非常重要但相互冲突的需求。为了解决高性能和低成本之间的冲突,异构多核系统如异构多处理器片上系统(MPSoC)被广泛采用。为了提高系统的可靠性并尽可能保持系统的性能,轻量级容错技术如检查点恢复技术被广泛采用,它通过载入“检查点”中存储的正确信息将系统从错误状态中恢复。虽然检查点恢复技术能在系统出现错误时大幅减少恢复所需要的时间,但由于系统需要隔一段时间制造“检查点”,该技术会增加系统在无错误时的运行时间。此外,越来越多的系统采用新型的非易失性内存(NVM)作为主存。NVM具有很多优良的性质,但其写入寿命有限。检查点的存储会造成NVM的写入,这也是可靠系统设计中应该考虑的问题。本文的目标是针对特定应用,采用检查点恢复技术设计专用的高可靠性高性能系统。为了提高系统性能,本文采用了流水线并行技术。在这样的系统设计中,需要决定三个因素:(1)由于应用中的任务数量可能远远超过系统能提供的计算资源(核心数),任务需要被分割成组,每一个分组对应一个流水线阶段,由一个核心来执行,称为“应用分割”;(2)由于核心的异构性,同一个任务在不同核心上的运行时间也会不同。因此,在系统设计时需要决定执行每一个流水线阶段的核心,称为“核心分配”;(3)为了在提高系统可靠性的同时尽量保证系统的性能以及NVM的寿命,在系统设计中需要仔细决定生成检查点的时机并尽量减少检查点的数量,称为“检查点放置”。本文首先提出一个整数线性规划模型(ILP)来获取最优的应用分割、核心分配以及检查点放置,即得到问题的最优解。然而,ILP模型的求解时间复杂度过大,只能得到小规模实例的最优解。因此,本文提出定理指出最优解的性质,并基于此定理提出了一个快速有效的最优算法。实验结果显示,本文提出的最优算法能在几秒内求得问题的最优解,而ILP模型在应用内任务的数量达到11个以上时便无法在合理的时间内(24小时)给出问题的可行解。本文提出的最优算法具有极强的解空间搜索能力,相比其他已知算法,最优算法平均减少了44%的检查点数量,充分证明了本算法的有效性。最后,得益于最优算法的高效性,它可以用来获取设计空间的Pareto前沿,能够给系统设计者提供更多的选择。