可重构环境下软硬件协同设计的算法研究

在高性能嵌入式系统设计中，对给定的程序确定哪些模块为软件实现哪些模块为硬件实现，被称作软硬件划分问题。模块的软件实现代价小、便于移植，但运行速度较慢。硬件实现则可加速其运行，但代价较高。权衡目标系统的运行时间、成本、功耗等性能指标之间的利弊，使得软硬件划分问题具有NP难解性。随着当今重构技术的快速发展，实现某项任务的硬件在其重构后可被重新用来实现其他任务。这一可重构的硬件环境改变了传统设计过程的许多基本假设，然而现有的研究成果很少考虑到这一硬件实现的可塑性，可重构环境下的软硬件协同设计技术呈现出欠缺甚至是空白。本项目将对这一领域中的技术难题进行算法研究，探讨更贴近现实的计算模型与实用算法。分别在动态软硬件划分及任务调度、多选择的软硬件划分、多目标优化的协同设计、以及动态软硬件划分的高效混成技术方面，构造可行的求解策略，建立并完善动态软硬件协同设计的基础理论，并为其关键问题探索新算法。

课题组紧紧围绕预定的研究目标与相关研究内容，设计积极可行的研究方案，对课题中的各项难题展开技术攻关。面向硬件资源可重构的动态环境，提出了基于0-1背包问题求解的软硬件划分计算模型， 并给出了相应的软硬件划分算法；算法针对任务图中硬件任务所在的关键路径实施任务调度，提出了最早截止时间的FPGA重构算法；同时提出了一种基于迭代排序思想的NodeRank算法，旨在通过迭代排序计算结点通信代价的期望值，进而求解出软硬件划分问题的优质启发解。在多选择的软硬件划分问题上， 构造了多种计算模型以及相应的有效算法；比较了三种智能优化方法（Tabu 搜索、模拟退火、遗传算法）求解该问题的性能，得出Tabu搜素算法为可取的软硬件划分算法；针对树形结构的特殊应用，设计了多选择的动态规划算法， 为适当规模的问题给出了精确解，为众多启发式算法提供了性能上的参照。课题在双目标优化方面有了突破，在粗粒度的软硬件划分问题上建立了相应的计算模型，并用多目标规划的理论，将双目标的问题转化为单目标问题，提出了快速启发式算法，并给出求解适当规模划分问题完全解的动态规划算法；在细粒度的划分问题上研究了以代价作为限制条件、目标定为最小化运行时间和系统功耗的优化问题， 并涵盖了通讯对运行时间和系统功耗的影响。课题组将软硬件划分问题抽象为图的划分问题，并将划分问题延伸到任务图中子图的归约，给出了一系列图的划分与归约算法， 用于软硬件划分问题的混成求解过程中。在可重构算法设计方面，完成了并行重构算法的设计， 并将相关技术推广到三维结构上；提出的并行重构技术体现在多线程并行策略与分治求解策略上，构造了三维逻辑结构互连长度的紧致下界；根据阵列结构的潜在并行特点，设计了基于VHDL硬件描述语言的并行重构算法;实现了对高级语言程序映射到FPGA的寄存器的快速评估。.在课题的资助下，课题组主要成员发表各类学术论文65篇，其中22篇被SCI收录、46篇被EI收录， 在中国计算机学会指定的A类国际期刊IEEE TC、TPDS上发表2篇，大幅超额完成了课题预定的各项任务指标。