文档介绍：湖南大学
硕士学位论文
动态可重构系统实时任务调度算法研究
姓名:焦铬
申请学位级别:硕士
专业:计算机科学与技术
指导教师:李仁发;包国庆
20100105
摘要在动态可重构系统中,,秸叩挠诺悖芄提供硬件的高效性和软件的可编程性,是当前热门的研究课题之一。动态部分可重构技术是可重构计算技术的最新进展之一。该技术能够在可重构系统正常工作的情况下,配置其中部分可重构资源,使得一部分任务的执行能够与另一部分任务的配置同时进行。动态重构技术能提高系统的灵活性和资源利用率,从而提升整个系统的性能。素之一。为了尽量提高系统芯片的利用率,降低硬件任务的拒绝率和调度时间开销,这就需要采用高质量的调度算法来对硬件任务进行合理的调度和管理。本文针对实时任务在二维可重构器件上的在线放置和调度问题,主要完成了以下工作:疚目悸墙布挝癜凑粘ぁ⒖砑暗鞫仁奔涔钩梢桓鋈试茨P停每个硬件任务看成是一个空间块,提出了一种基于三维空间邻接度的放置算法。该算法首先对可重构资源进行编码,到达的任务总是通过某个顶点依附另一个任务的边界被放置,确定候选的放置顶点;然后以到达任务与已放置在三维空间的邻接度为代价函数,选择代价函数值最大的顶点放置任务,从而使得到达任务与已放置任务在三维空间接触的邻接面最大。可使任务安排得更紧凑,减小对系统资源的浪费,提高芯片利用率。疚奶岢隽艘恢只诙サ懔幢淼挠布挝窦渥钚】占涞鞫人惴∕,该算法充分考虑利用任务的松弛时间内的调度延迟,采用基于三维空间邻接度的放置方法,选择松弛时间内使得邻接度最大的放置顶点和任务开始执行时间来执行任务,使得任务更加整齐、紧密的放置,从而降低任务拒绝率,提高硬件任务执行的并发度和资源利用率。杓品抡媸笛椋玀鞫人惴ǚ直鸷蚐伍算法、惴ā算法,从任务拒绝率、可重构资源面积利用率和时间复杂度上进行比较。四种算法采用相同的参数,实验结果表明,算法在任务调度成功率和芯片利用率明显优于已有算法,同时在运行时间和开销上并未明显增加。关键词:可重构计算;动态可重构系统;动态部分可重构;实时任务调度;代价函数;空间邻接度动态可蕈构系统实时任务调度算法研究
甀鷄鏻,琫瑃,.,,习.—,琫琕猙,畂琲琣琣,瑀甌琧甋,趟恫费宦畚..畂—
篟伍;如;动态可重构系统实时任务调度算泫研究琲.,.瑀瓵,籇;籖猼Ⅳ、
插图索引图单上下文模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图多上下文⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图硬件、软件和可重构实现方法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图软硬件无缝集成模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图基于顶点链表的任务放置⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图可重构芯片的编码和顶点队列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图面积差代价函数示例⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图空问邻接度放置算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图最大邻接边任务放置图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图最大空间邻接度任务放置图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图址胖盟惴ㄈ挝窬芫时冉贤肌图硬件任务调度模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.算法流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..算法任务调度图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯算法任务调度图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.算法运行过程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.算法运行结果图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图可重构资源利用率分析图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图经薅┑腗氲继宸⒄骨摺图静态重构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..图动态重构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图部分可重构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图可重构资源模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图试茨P汀图至咽纠矩阵⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..图初始任务放置图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..图任务拒绝数分析图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯工干罕硕卜学位论文
附表索引表三种实现方法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.表放置/分配算法的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表三任务的实例任务集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯调度算法示例任务集⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.表四种算法任务拒绝数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯