基于簇的层次敏感的可重构系统任务划分算法

对于可重构计算中面积约束条件下的任务划分问题,提出一种基于簇的、层次敏感的划分LSCBP算法.该算法按照依赖优先、最早最先和碎片利用三原则构造了新的启发函数AS_Level,能够跟踪节点分配过程并进行动态调整;它克服了CBP算法机械选取节点进行划分的缺点,同时算法复杂度也增大到O{｜ V｜^2＋｜ E｜}.对随机生成的任务图（节点数小于250）的划分实验表明：对于相同的DAG,LSCBP算法能够比CBP算法获得更少的任务簇（可重构资源需求量）和簇间有向边（通信代价）.     

概率构造算法与遗传算法融合的可重构计算系统硬件任务划分

提出一种概率构造算法与遗传算法融合的算法,通过引入表示划分结果多样性的度量方法,利用概率构造算法产生具有多样性的较优的初始群体,并在此基础上利用遗传算法寻求最优解.实验结果表明,该算法能够获得比已有的基于列表的划分算法更优的划分结果,比采用完全随机初始群体的遗传算法缩短了运行时间.     

可重构混合任务调度算法

隐藏和减少配置时间是可重构任务调度的关键问题。针对同时存在相关联的软、硬件任务的可重构混合任务,提出一种可重构混合任务调度算法。通过预配置策略和优先级算法确定需要预先配置的任务及其预配置顺序,将后继任务的配置过程隐藏在前驱任务的运行时间中,并采用配置重用策略,减少相同任务的配置次数。实验仿真结果表明,同已有的算法相比,该调度算法调度效果明显,减少了可重构任务调度的整体开销。     

可重构混合任务调度算法

隐藏和减少配置时间是可重构任务调度的关键问题。针对同时存在相关联的软、硬件任务的可重构混合任务,提出一种可重构混合任务调度算法。通过预配置策略和优先级算法确定需要预先配置的任务及其预配置顺序,将后继任务的配置过程隐藏在前驱任务的运行时间中,并采用配置重用策略,减少相同任务的配置次数。实验仿真结果表明,同已有的算法相比,该调度算法调度效果明显,减少了可重构任务调度的整体开销。     

采用预配置策略的可重构混合任务调度算法

在对可重构硬件资源进行抽象的基础上,采用软硬件混合任务有向无环图来描述应用,提出一种基于列表的混合任务调度算法.该算法通过任务计算就绪顺序及可重构资源状态确定硬件任务的动态预配置优先级,按此优先级进行硬件任务预配置,隐藏硬件任务的配置时间,从而获得硬件任务运算加速.实验结果表明,针对可重构系统中的软硬件混合任务调度,能够有效地降低配置时间对应用执行时间的影响.     

优化的可重构多常数乘法器生成算法

针对线性变换中单个定点数输入与多组定点常数相乘的问题,以加/减法器、移位器和多路选择器为基本单元,提出一种可重构多常数乘法器(RMCM)生成算法。该算法分别运用局部优化和全局优化2种策略,通过计算多常数乘法器(MCM)之间的拓扑相似度,对MCM的有向无环图(DAG)进行合并,选取其中估算面积最小的DAG作为输出。实验结果表明,利用该算法生成的乘法器在面积上具有优势,可用于实现视频多标准中多组不同系数的线性变换。     

LilyTask任务并行环境中基于任务关系的初始任务分配算法

LilyTask是一个基于任务并行的并行程序设计环境,它引入了任务间关系的概念．任务间会由于这种任务依赖关系而产生等待,为了减少这种等待开销,LilyTask系统在预编译阶段分析这些数据依赖关系,并做出相应的静态任务分配．该文给出在LilyTask任务并行环境中的一族新的基于任务关系图的静态任务分配的算法——WCP算法,并在实际测试中与另外两个著名的静态分配算法ETF和MCP算法作了比较,测试结果说明WCP算法在任务计算开销与通信开销不能准确给出的情况下有更好的分配效果．     

基于DAG图的自适应代码划分优化算法

并行编译的两大工作是程序代码划分和调度。对于调度问题,目前已有大量的解决方案,但是针对代码划分提取并行性的研究工作却非常少。该文提出了通过合并结点来划分DAG图的新的划分算法。实例分析证明,该算法是一种有效的、低复杂度的自适应代码划分解决方案,并且适用于异构计算的任务图划分。     

一种基于可重构多FPGA 的任务调度与任务复制方法

在可重构多现场可编程逻辑门阵列（FPGA）系统中,任务调度是一个极其重要的研究方向。参照同构与异构计算领域的调度算法,结合可重构多FPGA计算模型的自身特点,在现有的调度算法的基础上,将任务复制方法引入到可重构多FPGA系统计算领域,如果任务余图最长路经上的父子节点不在同一FPGA上,通过寻找FPGA上的复制空间,提出的算法将父节点尽可能复制在子节点所在的FPGA上,减小了任务之间的通信开销。实验结果表明,对于任务调度有向无环图,提出方法的调度长度优于或等于前人方法的性能下界,而且,FPGA利用率有所提高。     

基于DAG图解-重构的机群系统静态调度算法

机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log^|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可     

基于HEFT和CPOP的相关任务表调度算法

DAG任务调度是当前研究的热点,DAG任务模型中任务的调度顺序一方面会影响用户服务满意质量,另一方面也会影响云服务资源的利用率,高效的任务调度算法能够使多核处理器的资源分配和并行计算能力更强.表调度算法HEFT算法以及CPOP算法在相关任务调度中存在效率较低等问题.本文基于HEFT算法和CPOP算法,提出了一种相关任务调度模型和相关任务调度算法IHEFT算法,对任务排序和任务调度两个方面进行改进.任务排序阶段,以任务的方差以及平均通信代价作为排序的依据;任务调度阶段,对满足任务复制条件的结点进行任务复制.实验证明,IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack值方面均优于HEFT算法和CPOP算法.     

可重构造网孔机器上k-近邻并行算法

最近邻问题是计算几何学中的基本问题之一 ,k 近邻是最近邻的扩展 ,它在VLSI设计、数据库检索、模式匹配以及图像处理等领域有着广泛的应用背景 对于点数为N的平面点集S ,在规模为N×N的可重构造网孔机器上 ,提出了时间复杂度为O(k)的求S中所有点k 近邻的并行算法 该算法的时间复杂度已达到了该问题本身固有时间复杂度的下界     

VLCC中的DAG并行算法

基于组件的密码学虚拟实验室（VLCC）采用有向无环图（DAG）的拓扑排序机制管理组件。在分析VLCC各组件之间的数据依赖和运行次序关系的基础上,提出一种新的基于Java多线程机制和“唤醒”机制的DAG并行算法。与拓扑排序算法相比,具有低算法时间复杂度的特点。实验结果表明,系统在新算法下较大地缩短了系统运行时间,提高资源使用效率和用户满意度,能更好地完善VLCC。     

基于可满足性模理论的多处理机通信延迟优化任务调度方法

在一组相同处理器上调度带有通信延迟的任务图以实现其最短的执行时间,这在并行计算的调度理论和实践中具有重要的意义。针对具有通信延迟的任务图调度问题,提出一种基于可满足性模理论（SMT）的改进SMT方法。首先,将处理器映射约束和任务执行顺序等约束条件进行编码,将任务图调度问题转化为SMT问题;然后,调用SMT求解器对可行解空间进行搜索,以确定问题最优解。在约束编码阶段,使用整型变量表示任务和处理器的映射关系,从而降低处理器约束编码的复杂程度;在求解器调用阶段,通过添加独立任务的约束条件减小求解器的搜索空间,进一步提升最优解的查找效率。实验结果表明,与原始SMT方法相比,改进SMT方法在20 s和1 min超时实验中的平均求解时间分别减少了65.9%与53.8%,并且在处理器数量较多时取得了更大的效率优势。改进的SMT方法可以有效求解带通信延迟的任务图调度问题,尤其适用于处理器数量较多的调度场景。     

基于多核处理器的并行编程模型

为解决传统编程模型与并行架构间存在的矛盾,针对多媒体和网络应用程序的特点,提出一种基于多核处理器的并行编程模型,该模型采用节点化的并行程序描述方式,将并行编译器划分到多个核上运行。实验结果表明,这种新的并行编程模型能有效提高程序的执行效率。     

面向并行应用程序的DAG模式复用技术

在并行应用程序设计中可以用有向无环图(DAG)表示子任务之间的依赖关系,从而实现子任务的调度。为此,针对DAG数据驱动模型中的DAG模式复用问题,提出插件式DAG模式图库。将DAG模式图模块和运行时系统模块分离,增强模块的复用性和扩展性。在Easy PDP系统中实现并扩展该模式图库。以棋盘问题为例,证明该技术可降低扩展系统所需的代价。     

基于SRIO的实时并行图像处理机

针对大视场高分辨率光电实时处理系统实时性问题,分析光电弱小目标检测的任务特点,从处理器节点、存储器和连接处理器节点的网络3个方面分析实时并行处理机的设计要点,设计一种基于SRIO技术的双DSP＋FPGA并行处理机。FPGA实现低层处理算法,DSP实现高层处理算法,任务划分采用区域分解并行算法,实验结果证明该设计具有可行性。     

基于WDAG的工作流模型优化分析

为优化过程执行,降低实际运行成本,采用加权有向无环图(WDAG)的形式对工作流进行优化分析。将WDAG中的节点、弧和权重映射为工作流模型中的事件、运行过程和付出代价,建立基于WDAG的工作流模型,针对工作流中出现频率最高的顺序运行方式,提出一种包含合并优化和并行优化2种优化策略的优化算法。模拟实验结果验证了该算法的有效性。