《可重构系统中的任务划分和任务调度的研究》由会员分享，可在线阅读，更多相关《可重构系统中的任务划分和任务调度的研究（55页珍藏版）》请在金锄头文库上搜索。
1、河北工业大学 硕士学位论文 可重构系统中的任务划分和任务调度的研究 姓名：马平 申请学位级别：硕士 专业：计算机应用技术 指导教师：柴欣 20061101 河北工业大学硕士学位论文 i 可重构系统中的任务划分和任务调度的研究可重构系统中的任务划分和任务调度的研究 摘摘 要要 近年来，可重构硬件技术及其相关设计、开发工具的飞速发展使得动态重构计算逐渐 走向实用化。FPGA 技术的发展使其能够在运行时对芯片进行动态部分重构，对动态重构 计算系统的实用化提供了良好的硬件基础。但相对于 FGPA 芯片时钟速度的提高来说，当 前的重构开销仍然影响系统性能的关键因素。 在 FPGA 动态自重构机制的基础上
2、， 通过对 现有可重构计算系统结构的研究分析， 论文提出了单个微处理器和单个 FPGA 芯片构成的 动态自重构计算系统结构。 可重构硬件的动态部分重构能力打破了硬件的传统应用模式， 传统的软硬件划分方法 已经不能满足动态重构计算系统的需求。论文在分析总结各种软硬件划分算法的基础上， 考虑了动态重构和重构延时等可重构硬件逻辑带来的新特征， 提出了新的任务划分和任务 调度算法。 在动态重构计算系统中， 首先将一个大规模应用分解成粒度大小合适并且具有约束关 系的多个子任务，然后根据各个子任务之间的执行先后的约束关系，画出一个表示任务约 束关系的有向无环图。对于该任务图论文中的任务划分采用基于遗传算法
3、、 遗传算法和爬 山算法的融合算法和模拟退火算法的划分算法来得到一个划分结果,并使用动态优先级调 度算法对划分结果进行评价，有效地实现了动态重构计算系统中的任务划分与调度。 最后，论文进行了性能分析和实验结果比较。实验表明，算法取得的划分能够有效地 最小化应用程序的执行时间。 论文对可重构系统中的任务划分和调度的发展做出了有益的 探索。 关键词关键词：可重构系统 任务划分 任务调度 遗传算法 模拟退火算法 可重构系统中的任务划分和任务调度的研究 ii STUDY ON TASK PARTITIONING AND TASK SCHEDULING IN THE RECONFIGURABLE SYS
4、TEM ABSTRACT The rapid development of reconfigurable hardware technology, relational design methodology and CAD tools makes reconfigurable computation (RC) practical. The dynamic partial reconfiguration capability of FPGA changed traditional mode of hardware, making component to be the new computati
5、on method between software and hardware. Former co- design of software and hardware no longer satisfy the needs of dynamic reconfiguration system. The partition and assignment of function between software and component greatly influenced the performance of system. After analyzing and working over re
6、configurable computation architectures, this thesis presented dynamic self- reconfiguration cooperate computation architecture which was composed by a microprocessor and a FPGA chip. The Application mode of hardware was changed by the partially dynamic reconfigurable ability offered by reconfigurabl
7、e hardware. And the traditional hardware- software partitioning methods cant guarantee feasible implementations for dynamically reconfigurable computing systems. Taking new features of reconfigurable hardware resource and the time cost of reconfiguration into account, this thesis bring forward the n
8、ew task partitioning and task scheduling algorithm based on analyzing and summarizing every hardware- software partitioning algorithm. In the dynamic reconfiguration system, firstly we decomposed a big application into many sub- tasks which had appropriate granularity and restricted relations. After
9、wards, according to the restricted relations of every sub- task executed early or late, we drew a directed acyclic graph which had the meaning of restricted relations. This thesis adopted genetic algorithm 、 the integration of genetic algorithm and hill- climbing algorithm and simulated algorithm to
10、 get a task partitioning result towards the task graph, and employed priority- based dynamic scheduling algorithm to evaluate the partition results, and finally efficiently implemented task partition and scheduling of the dynamic reconfiguration system. Finally, the thesis carried through performanc
11、e analysis and experimentation results comparison. Obtained results indicate that the partitioning can minimize the application execution time efficiently. The thesis made a helpful explore on the study of task partitioning and task scheduling in the reconfigurable system. KEY WORDS: reconfigurable
12、system, task partitioning, task scheduling, genetic algorithm, simulated algorithm 原创性声明原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作所取得的成 果。除文中已经注明引用的内容外，本学位论文的研究成果不包含任何他人创作的、已公 开发表或者没有公开发表的作品的内容。 对本论文所涉及的研究工作做出贡献的其他个人 和集体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 日期： 关于学位论文版权使用授权的说明关于学位论文版权使用授权的说明 本人完
13、全了解河北工业大学关于收集、保存、使用学位论文的规定。同意如下各项内 容： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和 电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索 以及提供本学位论文全文或者部分的阅览服务； 学校有权按有关规定向国家有关部门或者 机构送交论文的复印件和电子版； 在不以赢利为目的的前提下，学校可以适当复制论文的 部分或全部内容用于学术活动。 （保密的学位论文在解密后适用本授权说明） 学位论文作者签名： 日期： 导师签名： 日期： 河北工业大学硕士学位论文 1 第一章第一章 绪论绪论 1-1 选题背景选题背景 在计
14、算模式中，基于通用处理器的软件模式和设计专用的集成电路（ASIC）的硬件模式一直是两 大主流。伴随着应用领域对系统的性能、能耗、上市时间等指标需求的不断提高，传统的软件模式和 硬件模式暴露出了种种的不足。软件模式的实现方法虽然灵活性高、移植性好、复用性高，但是目前 广泛应用的通用处理器由于其考虑通用性，不是针对解决某类问题、运行某类算法而设计的，难于高 效地实现算法来满足实际应用中对计算速度的要求。ASIC 实现方法针对性强，具有很高的速度、效率 和精度，但是硬件设计、开发周期长，不易于调试和实现原型系统，难于修改，可复用性差。 在实际应用中，往往对计算速度和系统的灵活性都有要求，这时处理器和
15、 ASIC 两种方法都无法 很好的满足要求。研究人员希望有一种实现方法能兼有硬件的速度和软件实现方法的灵活性，于是就 提出了可重构计算的思想 1；可重构逻辑器件的出现和发展使得可重构计算从理论研究到实际应用成 为了可能。 可重构计算对于一些专用的复杂问题能够做到性能高、能耗低，这使得可重构计算技术在许多应 用领域特别是嵌入式应用领域有着广阔的应用前景，例如多媒体应用、加/解密应用、通信应用、高 速数字滤波器、图像压缩、硬件演化计算、定制计算(Custom Computing)等。可重构计算技术是一项 新兴的能够有效提高系统计算能力的技术。它的诞生是为了满足人们对计算性能永无穷尽的需求，在 很多
16、领域都有着广阔的应用前景。目前，可重构计算技术的研究尚处于初级阶段，还有很多技术难题 没有得到圆满解决。但是在可以预见的将来，伴随着可重构逻辑器件技术的不断进步，可重构计算技 术一定能够在更多的场合被应用，发挥出更多的效用。 目前，可重构计算的发展面临着三大难题：可重构逻辑器件的支持；软/硬件任务的划分；任务 调度的支持。可重构计算技术的发展对可重构逻辑器件有着很强的依赖性，没有可重构逻辑器件的支 持，可重构计算就只能停留在理论研究，没有办法把这项技术推广到实际应用中去。随着大规模高性 能的可编程器件的出现，特别是现场可编程门阵列（FPGA）以及具有动态可重构能力的 FPGA 的出现 和发展，为了可重构计算技术从理论研究走向实际应用奠定了坚实的物质基础。 可编程逻辑器件随着微电子制造工艺的发展取得了长足的进步。从早期的可编程只读存储器发展 到能完成中大规模的数字逻辑功能的
