异构多核系统低功耗算法研究
第1章 绪论
1.1 课题研究的背景和意义
嵌入式系统自 20 世纪单片机的出现至今 40 多年的发展史中，逐步成为信息社会的核心基础，信息时代与数字时代的快速发展为嵌入式产品带来了极大地发展商机。因其体积小、系统精简、高实时性及可靠性等特征在工业制造、通信、仪器仪表、汽车、航空航天、国防电子等各领域中均有广泛应用。在系统结构方面，由于半导体工艺的限制，仅通过提高单核主频难以维持摩尔;定律，传统的体系结构已濒临淘汰，多核处理器成为当前主流处理器。与此同时，Amdahl 定律限制了通过增加同种内核以提升处理器性能的设计。在此背景下，异构多核处理器系统应运而生。另一方面，消费类电子产品需求的日新月异使得降低系统功耗成为嵌入式系统设计中的顶级任务之一，降低设备功耗等同于延长设备的有效工作时间，传统设计中通过增加电池容量延长设备工作时间，但电池容量的增加带来了设备重量和体积的负担，设备小体积、高性能与电池容量发生冲突，且电池的发展速度与系统的低功耗设计发展差距甚大。嵌入式系统低功耗设计目的是在满足成本、体积等性能需求的前提下，尽可能降低系统的能耗，避免不必要的能量损耗。
嵌入式系统低功耗设计贯穿于整个数字系统设计流程，以达到系统性能的最佳结合为目的，学者们开始了新一轮的设计方法探索，其中，软硬件协同设计(Hardware/Software Codesign)脱颖而出，其设计流程如图1-1所示。由图可知软硬件划分是软硬件协同设计的重要环节和组成部分。嵌入式系统的基本实现方法包括软件和硬件，硬件实现执行速度快功耗低但成本较高，而软件执行速度慢，但容易维护，灵活性高。如何依据软硬件实现特点合理分配系统任务以实现系统设计的最佳平衡点成为系统设计的核心环节。
1.2 异构多核低功耗设计研究现状与展望
1.2.1 国外研究现状与应用
近年来，在多核技术与系统低功耗需求的双重驱动下，探求有效的异构多核处理器系统下的低功耗设计技术迫在眉睫，当今最有效的解决方案是将问题分为软硬件划分及划分后的任务调度两个阶段，每个阶段分别采用有效的启发式算法，以达到最终的设计目的。
软硬件划分问题是复杂组合优化问题，上世纪 90 年代初期，众多学者便针对该问题展开探索。1992 年，GUPTA和DEMICHELI提出的软/硬件划分的迭代算法是基于协处理器和通用处理器，同年， EMST与HENEL共同提出了名为COSYMA的划分算法，该算法建立在模拟退火法的基础上，主要面向软件方向，在实现过程中允许用户自定义并发和时间约束，其缺点在于算法时间复杂度过高且处理器及协调器无法并发工作。文献[8]中由alavade提出了一种改进的表调度算法，该算法将任务分别映射到软件及硬件部分，可以自定义系统所对应的时间与面积权重。20世纪末，Henel利用减少系统空闲时间的方式达到降低系统功耗的目的，提出了基于IP核的嵌入式系统软硬件划分算法。进入新世纪，处理器结构的更新换代，使得研究者们不得不更新和优化各式各样的搜索算法。
任务调度的主要任务是明确一系列任务的执行顺序，它在嵌入式系统设计中是一个古老而深远的话题，有效的调度算法对高效地达到系统设计目标起着不可忽视的关键作用。Liu和Layland为任务调度的研究做出了巨大的贡献。二人最先建立了周期任务的调度模型，并在此模型上提出了单调速率算法和最早截止期优先算法这两种重要算法，针对单核处理器，二者又连续提出了FCFS、DMS、RR等算法。近年来，多核处理器的广泛应用吸引了大批专家的关注，并以此提出众多經典算法，如基于关键路径的CPOP算法和异构最早结束时间算法HEFT等，此外，Max-min、Min-min、Sufferage 等算法也有广泛应用。Shnits教授在研究中注意到了局部调度和全局调度的重要性，在文献中提出了一个多项式时间的全局调度算法。并在文献中研究了在多核处理器上具有截止时间约束的周期任务调度。文献中采用了与文献相似的任务模型，给出了一个在能耗约束条件下实时任务调度的近似优化算法。除此以外，在不同的应用需求下，各研究者提出了对应的多种调度算法。如关键路径快速复制算法，有限复制的调度算法，分簇调度算法等，在传统的复杂多任务系统中，高效的任务调度方案是保证任务可以顺利完成的关键，文献通过非精确计算来建立任务模型，有效提高了算法的调度成功率。
第2章 相关技术概述
2.1 引言
本文第一章分析了当今嵌入式技术的研究现状和发展趋势，确定了将异构多核处理器作为目标体系结构，并采用划分与调度相结合的方法达到降低系统功耗的设计目标。只有了解并掌握研究过程中的重要技术，才能设计出恰当合理的解决方案。本章将详细介绍研究过程中运用的技术手段，第二节是对软硬件划分技术的概述，第三节主要介绍了任务调度的目的及分类，第四节讲解了系统建模中常用的几种方法，第五节对本章做出总结。
2.2 软硬件划分技术
2.2.1 软硬件划分的结构分类
嵌入式设计主要包括软件和硬件两种实现方式。每个模块实现方式的不同直接影响着系统的成本和整体性能。通过软硬件协同技术为每个模块合理划分实现方式将最大限度的保证系统的最优性能比，其中，软硬件划分是软硬件协同设计的重要环节和组成部分，目标结构与系统需求的差异决定了软硬件划分可分为以下四类：
1．单目标二路划分 单目标二路划分是软硬件划分的基础，简易的系统只需要一个CPU和一个 ASIC，CPU表示软件单元，ASIC表示硬件单元。
2．单目标多路划分 二路划分是多路划分的基础，多路划分基于多个硬件单元，多个软件单元，而且类型也可能不同，划分较为复杂。本文提出了一种量子遗传划分算法与优先级表调度算法相结合的单目标多路划分方法，合理解决任务分配问题并完成任务的调度和性能评价。
3．多目标多路划分 在算法设计过程中，设计人员往往需要考虑实际应用中的多项设计目标，如系统性能、成本、工作时间、功耗等，因此需要有多个拥有不同参考值的目标函数，在多路划分过程中也常常出现偏向某项设计需求的情况。
4．动态可重构系统的软硬件划分 嵌入式技术的迅猛发展使得越来越多的设计者采用可重构系统结构，动态可重构系统的划分实际上是通过可重构计算改变自身系统结构，在不同时间段内用同一个可重构器件执行不同的功能，达到不同的设计目标。
2.2.2 常用软硬件划分方法
早期的软硬件划分方法都是研究者根据经验通过手工划分完成，随着嵌入式领域的不断扩展，传统的软硬件划分方法逐步被淘汰，软硬件自动划分随之产生，在复杂的软硬件划分过程中，设计者们首先要遵循的原则包括性能原则、性价比原则及资源利用率原则，在遵循以上基本原则的基础上，研究者们进行了大量的探索和尝试，提出了不同方式下的划分算法，主要的經典算法主要包括：
遗传算法(Geic Algorithm ，GA)模拟达尔文提出的自然界优胜劣汰、适者生存;的原理产生下一代种群，并通过交叉、变异等算子产生新的个体，最终求得到问题的一组 Pareto 解，但过多的算子选择会导致搜索过程陷入局部最优，且容易引起种群个体的差异性降低，致使算法停留在某个现实徘徊不前，产生早熟现象。
第3章 基于量子遗传算法的异构多核软硬件划分策略 ............. 15
3.1 引言 .................. 15
3.2 异构多核系统模型设计 ................. 15
第4章 异构多核低功耗表调度算法 ............... 28
4.1 引言 .............. 28
第5章 仿真及实验结果分析 .............. 35
5.1 引言 ................... 35
5.2 实验平台设计 .................. 35
第5章 仿真及实验结果分析
5.1实验平台设计
DVS 技术被运用到实时系统的前提条件是：实时系统所依附的硬件设备支持 DVS 技术，DVS 技术毕竟是纯软件节能技术，软件节能技术必须依附硬件设备才能发挥出软件节能技术的作用，本文在第三章建立的系统模型的基础上，设计了一个基于异构多核平台的模拟仿真系统对算法进行评估。
该系统主要由实验参数生成、算法实现及实验结果分析三大部分构成。各部分需要实现的主要任务如表5-1所示：
结论
随着嵌入式系统的迅速发展，在单芯片内集成多个异构处理器核成为可能，然而，处理器性能大幅度提升的同时，功耗问题成为制约多核处理器在计算领域内普及的重要因素，有效的任务分配与调度算法能为系统节省更多的功耗，而现有的相关研究算法多针对单核处理器系统，异构多核处理器系统中各核之间指令集的不同使得低功耗设计算法更为复杂。
异构多核处理器系统的软硬件划分及任务调度是經典的NP组合优化问题。目前还没有一个完备的划分方法，绝大多数的划分结果并不一定是最优解，而是接近最优解的近似优化解，并且传统的研究算法都面临着时间复杂度过高的窘境。本文主要贡献有两方面工作：一个是基于量子遗传算法的软硬件划分方法，一个是基于动态电压缩放技术的表调度算法。在软硬件划分部分采用的是多路划分，其目标就是在系统给定的时间、硬件面积及软件内存约束的条件下优化系统的整体功耗。量子遗传算法结合了量子计算强大的并行性及遗传算法特殊的启发特性，量子位的编码使得每个量子染色体可以表述的任务与处理单元的匹配情况是任务数目的 2 的指数次幂，量子旋转门更新操作使得该算法能够在短时间内趋向群体的最优解并能够为后期的低功耗调度算法提供更加丰富的划分方案，为达到降低系统功耗的目的奠定了良好的前提基础。在异构多核处理器系统的低功耗调度阶段，基于动态电压缩放技术的表调度策略与低功耗技术结合，电压的调整引起任务属性的变化，导致各个任务的优先级改变，从而产生新的任务执行顺序，动态电压缩放技术能够在延长任务执行时间的同时降低系统功耗，在任务截止期内，根据每次调度后的松驰时间大小对任务节点进行电压缩放。本文采用DAG建模方式对系统进行建模，准确描述了系统的构成，方便了算法的研究。本文主要分三个功能模块，从功耗降低率及算法时间复杂度两个方面对算法性能进行评估，为公平起见，每个阶段的参数都是利用TGFF 工具中相同的配置文件数据生成。在不同阶段分别对本文提出的 QGA、DVS_PLSA 算法及对比算法 GA、ASG_VTS 进行 C 语言编程验证。实验结果表明，在各阶段相同的配置参数及迭代参数环境下，QGA 算法与 DVS_PLSA 算法均能优于对比算法，能够有效的降低系统功耗，在时间复杂度方面，虽然DVS_PLSA 算法与 ASG_VTS 算法相差无几，但由于 QGA 算法在任务的划分阶段利用量子计算强大的并行性特征能够在很短的时间内处理海量数据，因此算法整体的时间复杂度较低。
参考文献（略）