多核嵌入式系统并行优化若干关键技术研究

摘要

现今计算机已深入人们的日常生活，随着嵌入式系统设备的普及，嵌入式应用向着深度嵌入、泛载互联、普适计算方向发展。为了提高嵌入式系统的性能，高性能嵌入式计算变得尤为重要。如传统计算机的发展趋势一般，嵌入式系统也进入了多核时代，但与之而来的高能耗和存储瓶颈却限制了嵌入式系统的发展。如何在充分利用多核结构的优势基础上，降低系统能耗，提高存储资源利用率，是嵌入式多核系统并行优化所关注的问题。嵌入式多核系统的并行优化是近年来计算机学术界研究的一个重点。
　　并行优化包含很多问题，设计过程的软硬件划分、任务调度、数据存储分配、内联网络设计等问题都是其中的重点和难点。本文针对这四个不同的问题，分别引入了智能算法、动态规划算法等经典算法，并结合其他并行优化技术进行研究。并行优化通常采用折衷嵌入式系统面积、能耗、时间性能的策略。本文主要的研究工作如以下几个方面所述:
　　(1)嵌入式系统通常采用软硬件协同设计的方式，软硬件划分则是软硬件协同设计中最重要的阶段，在有限的系统硬件资源前提下，最大化嵌入式系统的性能;即保持硬件面积不变的情况下，缩短系统的执行时间，相应地由于任务执行时间的减少，系统的能耗也随之降低。针对上述问题，本文通过DAG图将软硬件划分问题看作为0-1问题，引入了混合蛙跳算法对该问题进行优化，由于原始的蛙跳算法是针对连续优化问题，因此在其局部更新策略中采取了将连续值转化为离散值的机制。本文的蛙跳算法具有较好的收敛性，与经典的模拟退火算法和贪婪模拟退火算法相比，在基准测试程序集上关键路径任务完成时间性能分别能提高16.65％和11.46％。
　　(2)任务调度是多核系统中不可回避的重要问题，新存储技术——非易失性存储的出现，引发了存储技术的革新。新的存储技术可以有效降低系统能耗，在嵌入式系统中被应用在主存和缓存，数字信号处理和多媒体应用方面。由于程序中的循环部分通常是最耗时且功耗最大，多核非易失性存储嵌入式系统任务调度研究主要针对数字信号处理和多媒体等带循环的嵌入式应用。利用旋转调度技术对循环进行调度，减少循环单次迭代中任务的完成时间，并结合数据迁移和数据重计算技术，减少对非易失性主存的写操作，进一步减少任务的完成时间。同时对于旋转调度后的可分配任务，本文采用最大二分匹配的方式求解出其最优的分配。与采用旋转尽快调度策略相比，基础测试程序的实验表明，在系统任务的完成时间、对非易失性存储的写次数和系统能耗上分别有着20.5％、15.03％和34.5％的性能改进，该算法有着极大的可用性。
　　(3)任务数据的存储分配问题是任务调度完成后必须面临的重要问题。同时采用SRAM和非易失性存储的混合便笺式存储代替传统硬件控制缓存是一个极优解决方案，传统的数据存储分配工作主要针对单核结构或者单一结构的便笺式存储。针对采用混合便笺式存储结构的任务数据分配问题，本文将数据迁移技术与动态规划策略相结合，提出基于数据迁移的动态数据分配优化算法。在混合了SRAM和非易失性存储的便笺式存储器高速缓存上，将应用任务划分为多个并行区域，通过本文提出的算法对数据存储类型的分配，获得整个并行区域数据分配的近似最优解。同样本文提出的算法，能在多项式时间内获得该近似最优解。与迭代数据优化分配技术相比，在基准测试程序上的试验表明，本文提出的算法在系统任务数据的访问时间、对非易失性存储的写次数、系统能上分别有着33.82％、24.27％和10.00％的性能改进。
　　(4)处理核之间的通信问题是多核系统中不可避免的问题，其是处理完多核间任务调度和任务数据分配之后的重要问题，根据具体应用处理核之间的通信，进行核间内联网络的定制和设计是一个可行的研究方向。设计出满足系统核间通信需求、占用系统面积少、低能耗的内联网络是该研究的目标。本文中针对该问题提出了基于任务节点和任务数据的通信调度算法，通过采用总线的点对点连接方式构建内联网络，在不增加系统调度长度的前提下，构造出满足系统核间通信需求，核间点对点连接数最少的内联网络。同时文中根据核间通信调度确定算法和内联网络构造算法，为内联网络的设计提供依据。实验表明，本文提出的两种算法的混合，优于HLEFT算法和ASAP算法的混合，与单独采用任务节点通信调度算法相比，该混合算法可以减少总线中15.02％的核间点对点连接。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景

1．2 研究内容

1．3 本文组织结构

第2章 相关研究

2．1 软硬件划分相关研究

2．2 循环中任务调度算法研究

2．3 非易失性存储的研究

2．4 便笺式存储的研究

2．5 多核嵌入式系统内联网络研究

第3章 理论和技术基础

3．1 系统计算模型

3．1．1 DFG图模型

3．1．2 DAG图模型

3．2 相关技术

3．2．1 重定时技术

3．2．2 数据迁移技术

3．2．3 数据重计算技术

3．3 相关模拟器

3．3．1 SimpleScalar

3．3．2 NVSim

3．3．3 CACTI

3．4 相关测试程序

3．4．1 随机测试程序

3．4．2 基准测试程序

第4章 基于SFLA算法的软硬件划分

4．1 本章引言

4．2 软硬件划分模型

4．2．1 硬件结构

4．2．2 计算模型

4．3 基于SFLA算法的软硬件划分

4．3．1 SFLA算法描述

4．3．2 基于SFLA算法的软硬件划分

4．4 实验

4．4．1 基准测试程序集的软硬件划分实验

4．4．2 随机程序集上的软硬件划分实验

4．5 本章小结

第5章 多核嵌入式系统任务优化调度

5．1 本章引言

5．2 硬件架构和计算模型

5．2．1 硬件架构

5．2．2 计算模型

5．3 实例说明

5．4 旋转最大二分匹配算法(RMBM)

5．4．1 旋转调度技术

5．4．2 数据迁移技术

5．4．3 数据重计算技术

5．4．4 旋转最大二分匹配算法

5．5 实验

5．5．1 DSPStone基准测试程序

5．5．2 Mediabench基准测试程序

5．5．3 不同核基准测试程序比较

5．6 本章小结

第6章 基于数据迁移的任务数据优化分配

6．1 本章引言

6．2 硬件和计算模型

6．3 实例说明

6．4 基于数据迁移的任务数据优化分配

6．4．1 问题描述

6．4．2 全局近似最优的数据分配方案

6．5 实验

6．5．1 基准测试程序的算法性能评估

6．5．2 随机程序(DAG)的算法性能评估

6．6 本章小结

第7章 多核嵌入式系统内联网络优化调度

7．1 本章引言

7．2 基本原理

7．2．1 多核嵌入式系统结构模型

7．2．2 多任务应用建模

7．2．3 研究动机

7．3 内联网络优化调度

7．3．1 核间数据传输问题定义

7．3．2 任务节点的通信优化调度

7．3．3 数据传输的通信优化调度

7．4 实验

7．4．1 基准测试程序集实验

7．4．2 随机程序集实验

7．4．3 不同处理核之间的性能比较

7．5 本章小结

结论

参考文献

致谢

附录A 攻读学位期间所完成的论文

附录B 攻读学位期间主持和参加的科研课题