论文部分内容阅读
可重构计算技术结合了通用处理器(General-Purpose Processor, GPP)和专用集成电路(Application Specific Integrated Circuits, ASIC)两者的优点,能够提供硬件的高效性和软件的可编程性,是当前热门的研究课题之一。动态部分可重构技术是可重构计算技术的最新进展之一。该技术能够在可重构系统正常工作的情况下,配置其中部分可重构资源,使得一部分任务的执行能够与另一部分任务的配置同时进行。动态重构技术能提高系统的灵活性和资源利用率,从而提升整个系统的性能。在动态可重构系统中,硬件任务的调度是影响动态可重构系统性能的关键因素之一。为了尽量提高系统芯片的利用率,降低硬件任务的拒绝率和调度时间开销,这就需要采用高质量的调度算法来对硬件任务进行合理的调度和管理。本文针对实时任务在二维可重构器件上的在线放置和调度问题,主要完成了以下工作：(1)本文考虑将硬件任务按照长、宽及调度时间构成一个三维资源模型,将每个硬件任务看成是一个空间块,提出了一种基于三维空间邻接度的放置算法。该算法首先对可重构资源进行编码,到达的任务总是通过某个顶点依附另一个任务的边界被放置,确定候选的放置顶点；然后以到达任务与已放置在三维空间的邻接度为代价函数,选择代价函数值最大的顶点放置任务,从而使得到达任务与已放置任务在三维空间接触的邻接面最大。可使任务安排得更紧凑,减小对系统资源的浪费,提高芯片利用率。(2)本文提出了一种基于顶点链表的硬件任务间最小空间调度算法MSSA (minimun space scheduling algorithm),该算法充分考虑利用任务的松弛时间内的调度延迟,采用基于三维空间邻接度的放置方法,选择松弛时间内使得邻接度最大的放置顶点和任务开始执行时间来执行任务,使得任务更加整齐、紧密的放置,从而降低任务拒绝率,提高硬件任务执行的并发度和资源利用率。(3)设计仿真实验,将MSSA调度算法分别和Stuffing算法、MGS算法、CR算法,从任务拒绝率、可重构资源面积利用率和时间复杂度上进行比较。四种算法采用相同的参数,实验结果表明,MSSA算法在任务调度成功率和芯片利用率明显优于已有算法,同时在运行时间和开销上并未明显增加。