论文研究-基于多目标优化算法的NoC映射研究 .pdf

所需积分/C币:7 2019-08-15 13:22:29 246KB .PDF

基于多目标优化算法的NoC映射研究,郭宝兵,袁景凌,功耗问题是NoC领域研究的热点,传统NoC功耗优化算法能够很好的实现映射通讯功耗单目标优化。热量平衡是NoC映射中与功耗优化相互冲突
中国科技论又在线 如约束条件所示,映射函数=9表示的映射关系为 对应处理单元的 标号:约東条件表示映射规则是一一对应,不存在一个核映射多个资源节点或一个资 源节点映射了多个核的情况;'→'表示链路的一个单元段,为该段的带宽限制, 即衣示所有通讯任务的带宽需求满足链路的带宽限制 由此可知,最小化总通讯能耗就是在满足以上约束条件的同吋最小化目标函数。 热量模型 拓扑图上核的能耗、位置以及核的物理特性决定了每个核的温度。 等人开发的热阻模拟器 能够很有效的模拟块级的热阻。每个模块的发热以 及周围模块的热流传递都被考虑到热阻之中。定义核的热阻等于自身温度增量与 相邻节点的能耗增量的比值。在已知核布局以及物理特性的情况下,通过该模拟器,能 够得到整个上核的热阻矩阵,对于已知能耗分布的,可以通过以下公式计算 出温度分布。 热阻表示拓扑中位置对应的区域的热阻,为该区域的能耗,。在知道热阻矩 阵及区域能耗的情况下,该中每个核的温度就可以按照公式计算得来。 热量平衠的是通过最小化温度最高的热点区域的温度来实现的,目标函数可以衣示为: 其中,对应处理单儿的温度。 多目标优化算法 在科学和工程实践中,多口标优化问题是普遍存在的一类问题,许多控制和决策问题需 同时考虑多个日标优化,可描述为: 其中, 为目标函数;g≤为条件约束。对」目标存在相红冲突 的多目标优化问题而言,每个分目标之间没有优劣差别,不存在唯一的全局最优解,使所有 的目标函数同时最优,而只能找到一组目标无法翛单进行相互比较的解,即有在一组无法改 进其中一个目标而不削弱至少一个其他目标的解。这些解称为 解集。 假设∈是式所示多目标优化的两个可行解,则称与相比,是 优的,当且仅当 记作>,称支配。其中为可行解集。一次多目标算法优化得到的非支配 解集即为本次优化的 解集 本文分别将基于多目标优化的权重法、蚁群算法和基于重启策略的多目标优化算法应用 于优化约束条件下通讯能耗以及热量平衡多目标映射问题,利用这些方法求解 最优解集 多目标优化权重和算法 对于有多个目标优化问题,最直接的方法就是根据决策者的偏好把多个目标转化为单个 中国科技论又在线 目标来求解,所有这些根据偏好信息来求解的方法可通称为基于偏好的方法。 权重和法 的基本思想是为每个目标函数分配权重并将它 们通过求和的形式组合成一个目标函数,然后利用单目标优化算法对这个组合函数进行优 化,从而将多目标优化问题转化为单目标优化问题来求解,是一种经典的基于偏好的多目标 优化方法。权重就是决策者对目标偏好的标量化的表示。它也可以理解为目标与目标之闫的 相对价值或重要性。 针对多日标映射,优化日标为功耗和热量平衡,则由公式和公式可得到基于 权重和多日标优化组合日标函数为 几×+- 其中,λ是比例系数,用于调节通信功耗与热量平衡的比重,取值范围为:,优化 映射的多个目标函数转化为单一目标函数,当A时,表示只对热量平衡进行优化;当A 时,表示通信能耗优化;当λ取中间值时,体现对通信能耗和热量平衡优化的折衷。 对于组合目标函数,本文用遗传算法进行优化。 多目标优化蚁群算法 蚁群算法 是一种模拟蚁群觅食过程中高度社会行为的仿生 算法,具有并行性、正反馈机制。文献使用蚁群算法对映射通信能耗单个目标进行 优化,但是其使用的蚁群算法并不具有多目标优化的能力。用到的蚁群算法基于转移 率的搜索机制和信息素更新方式指导蚁群朝着信息素浓度高的区域进行搜索,使得蚂蚁聚集 在解空间内某一区或,最终找到最优解。然而,多目标优化问题的解不是唯一的,而是逼近 最优解集的解集,使用多目标优化方法得到的解集要求分布均匀并行保持解 的多样性,这就要求蚁群算法具有全局搜索能力。 般多目标优化蚁群算法采用蚁群算法与遗传算法相结合的方式,基于这种思想设计的 算法虽然一定程度上结合了蚁群算法的反馈机制与遗传算法的仝局收敛性,但是算法的效 率较低,这乜限制了此类组合算法在映射上的应用。 木文采用支配排序以及拥挤距离对解集进行比较,采用一种新的信息素更新方式 对标准蚁群算法进行改造,将有效的增强蚁样算法的全局搜索能力,算法称为多目标优化蚁 群算法 。设定集合为 外詺集合,存放时刻为止的解集。若蚂蚁进入集合,则增强该蚂蚁的信息素 更新;如果蚂蚁没有进入,则山挥发系数ρ适当减少信息素。若,均为可行解, 更新方式如下: 如公式所示,δ ∈,表示蚂蚁进入了 时,对蚂蚁留下信息素的増强,増强的量为解与之间的几何距离。这样,距离越大蚂 旼留下的信息素越多,会以更髙的概率指引其他蚂蚁对这个蚂蚁的位置的领域进行搜索。 根据以上改进,多目标优化蚁群算法全局搜索能力将会增强,解集的分布性也会 得到优化。 基于重启策略多目标优化算法 中国科技论文在线 遗传算法是最早被应用于多目标优化的进化算法之,其随机性、全局搜索能力使得遗 传算法十分适用于多目标优化。针对映射的多目标优化应用了著名的多目标优化算 I。然而, Ⅱ的精英个体保存策略剔除了部分差异个体,导致种群多样性 丢失。针对这个问题,本文在 Ⅱ的基础上,对算法进行了改进,将重启多样性保存 策略应用到算法的多样性保存上,提出了基于重启多样性保存策略的多目标优化算法 编码 由于论文考虑核数目与处理器数目一致的映射情况,采用直接编码法更加方便和高 效。直接编码策略首先将处理器矩阵由左到右,由上到下转换为一维矩阵,然后给核编 弓,核包含了任务的编号即为核的编号,将所有核编号组成维向量,编号代表对 应核,编号在向量中的位置,衣示该核怏射到处理器矩阵中的位置,及将该核映 射到一维处理器矩阵中相应位置的处理器上,综上每个完整无币复的核向量即为遗传算 法中的一个染色体。 快速非支配排序和拥挤距离 多目标优化的日标空间组成的向量空间中可行解的比较关系是一种向量自然序关系。依 据这种日标空间中解的支配关系,可以得到所有可行解的支配级,并进行非支配个体排序。 本文采用 Ⅱ中的快速非支配排序方法。为了区分支配级相同的个体的优劣,并保 持群体的多样性和解分布的均匀性,引入一种新的拥挤距离的概念。对于匚进行非支配级排 序的种群拥挤距离为个体与直接邻居在各个目标上的距离的总和。 多样性保存策略 每轮进化,都将种群分为内外两部分,外部种群有非支配个体集组成,内部种群为普通 个体,外部种群的作用在于保存每轮的最优个体,并在父种群的选择过程中强化最优个体的 作用,同时为了不丢失种群的多样性,算法还从内部和群中选取部分个体加入父种群。通常 选取父种群时,从外内种群中选取的个体的数目比例不低于 另外,针对 Ⅱ多样性丢失问题,采用了重启策略 当连续次迭代得到的外部非支配个体集都相同时,即断定算法进入停滞状态,重启 策略启动,算法将向父种群中直接注入个新的个体,为日标函数的个数,这个个体为 分别为日标值最小个体的交叉变异生成的新个体。新个体选择算子如下: 其中, ,为新个体,= ,衣示探测步长。 比较分析 本文分别将棊于多日标优化的权重法、蚁群算法和改进的 Ⅱ应用于优化约束条 件下通讯能耗以及热量平衡多日标映射问题。其中,权重法取组权重系数组合;蚁 群算法由改进的信息素史新策略加强精英蚂蚁的信息素,以期待其他蚂蚁对精英蚂蚁路线领 域进行搜索:而基于重启策咯的多目标优化算法 ,在保留了 Ⅱ较好的收敛 性和分布性特点的同时,其新的多样性保存方案填补了 Ⅱ的在多样性丢失问题上的 不足。 权重法对优化问题的先验知识要求比较多,除了要求目标解空间必须是凸的之外,还要 中国科技论又在线 求优化凶数具有连续性。如果目标空间中有非凵的区域,则其无法找到该区域中的 最优解,然而,前面已经提到映射属于二次分配问题的范畴,即 对于非线性目标函数,其解空间的凸凹性还没有有效的验证方法。此外,权重法求解多目标 优化问题,是通过偏好信息将问题转化为单个目标函数进行求解的,这就需要给定多组合适 的权重值,以保证它们具有相应的量级,并且求到最优的解方案形成较合理分布的 前沿。因此,权重法的先验性需求以及应对实际设计情况的适应能力给其在求解多日 标映射问题的应用形成巨大的局限 般多口标优化蚁群算法采用蚁群算法与遗传算法相结合的方式,虽然一定程度上结合 了蚁群算法的正反馈机制与遗传算法的全局收敛性,但是算法的效率较低。对于基于改进信 息素索更新策咯的多目标蚁样优化算法,实际上是采用了精英蚂蚁信息素更新强化策咯,精英 蚂蚁的指导作用得到加强,加快了算法的收敛,最初的精英群伓的素质将严重影响整个蚂蚁 种群的行为。基于改进信息素更新策略和转移策略的多目标蚁群算法在多目标问题的求解 上,还是全局搜索能力欠缺。最终得到的解集的分布性和多样性将受到局限。 本文改进著名的多目标优化算法 ∏实现了基于重启策略的多目标优化算法 在保留了 ∏较好的收敛性、分布性和较高执行效率的特点的同时,其新的 多样性保存方案填补了 ∏的在多样性丢失问题上的不足。 对于以上几和多日标优化算法表给出了综合比较。 表算法综合比较 多目标优化精英多样性适应度 块射 优点 不足 算法 保存策略保存策略分配机街 适用性 先验知识要求 权重法 目标值比 解集/不适用于 无 无较 简单、直接 映射多目标优 分布不均,只适 用于凸线性空间化要求 非支配排 全局搜索能力欠组合算法效率 序、拥挤 缺, 前沿低,不适应 无距离比较较快收敛分布性多样性差 映射要 求;非组合算法 优化能力较差 非支配排收敛较快,分布重启策略重启频 有、拥挤较均匀,多样性率有待分析,频映射效率和性 距离比较较好,全局搜索|繁注入新个体将能比较好 能力较强 影响算法效率 表通过三种算法在精英保存策略、多样性保存策略、适应度分配机制上的差别,以 及针对映射多目标优化的适用性,很明显 具有更好的性能。 结论 本文分别将基于多目标优化的权重法、蚁群算法和基于重启策略的多目标优化算法 应用于优化约束条件下通讯能耗以及热量屮衡多目标映射问题,利用这些方 法求解 最优解集,比较分析了儿种算法的特点以及它们对映射多目标优化的适 用性,其中 相对于其它方法更适用于映射针对通讯能耗和热量平衡两个冲突 中国科技论又在线 目标的优化。然而, 重启策咯的重启频率以及新个体选择算了对算法的影响并不明 确,下一步的研究将是重启策略的性能分析。同时,考虑到 Ⅱ需要维持较大进化种 群规模,如何实现适用于ˉ映射多目标优化的小种群髙效率髙性能能遗传算法将是研究 重点 参考文献 干民,尹勇生等基丁蚁群算法的映射汁算机工程与应用 刘桂萍棊于微型遗传算法的多目标优化方法及应用研究淜南大学,

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
相关内容推荐