可重构多核片上系统软硬件协同优化算法研究

摘要

可重构技术综合通用和定制两类计算的优势，提供灵活高效的运算性能。多核片上系统在单芯片中集成多种功能单元，满足多样化应用需求。两者相结合的可重构多核片上系统兼顾计算灵活性与运行效率，发挥多核计算的资源优势，利用硬件可编程性，有效满足嵌入式领域不同的应用需求。
　　上述系统在设计和应用中亦存在不少挑战。应用的灵活性和内核的多态性很难构建归一化的抽象模型;硬件加速的高效性会带来划分、调度及分配等一系列普遍认为或已被证明是NP完全或NP难的问题;资源的分时复用特性增加了管理、布局、碎片等多约束条件。因此，可重构及多核片上系统协同优化算法的研究在提升系统运算性能、增强应用可靠性等方面具有必要的现实意义。
　　本文针对可重构及多核片上系统软硬件协同应用，以优化计算性能为主要目标开展研究。首先抽象多核片上系统和可重构多核片上系统的基础框架，归纳影响系统性能提升的主要约束因素。其次结合国内外研究现状，给出相应的软硬件协同算法。最后分析算法的时空复杂度及性能优化效果。
　　本文主要工作和特色如下:
　　(1)在分析国内外典型多核片上系统和可重构多核片上系统的基础上，结合多态计算及下一代通用处理器特征，构建出一体的系统框架结构。同时结合输入任务类型、主要制约因素及性能提升目标，抽象一致的约束条件和优化模型。
　　(2)针对多核片上系统软硬件协同优化，在分析影响其运算性能的任务间依赖关系、通信代价及处理器分配等约束的基础上，提出贪心划分插入调度的GPISM算法。该算法借助于贪心划分策略，选取关键硬件路径和最长软件通路;依据系统的约束条件和优化目标，将余下零散任务插入到对应的处理器核中调度执行。GPISM算法具有多项式时间的复杂度和较小的空间开销。
　　(3)针对可重构技术硬件分时复用的特点，在分析影响系统性能和资源利用率的布局管理、放置方式及碎片度量等约束的基础上，提出VHF硬件布局管理策略。该策略包括:节省存储开销的顶点位置树VPT数据结构;减少时间开销的高权重占角优先HWC布局方式及灵巧的跳步搜索方法;降低计算成本的碎片外形边FSE度量函数。在此基础上衍生出针对永久故障的FT-VHF容错管理策略。本文所提出的硬件布局管理及容错策略以较低的时空复杂度达到高效的资源利用率和低成本的系统可靠性。
　　(4)针对在线型和离线型任务特征，在分析可重构多核片上系统协同优化中受截止期限、任务依赖性等约束的基础上，提出VHF-Online和VHF-Offline两类任务调度算法，结合VHF硬件资源管理策略，实现软硬件的协同优化。其中，VHF-Online算法以贪心的队列调度和动态的时间管理，获得较高的任务接受率;VHF-Offline算法借助循环迭代消除任务间相关性，赋予任务不同的软硬件执行优先级，综合动态划分、布局判定、优先调度等协同策略实现较短的调度总长度。