可重构系统硬件任务布局布线技术研究

作     者：肖庆辉 

作者单位：解放军信息工程大学 

学位级别：硕士

导师姓名：韩国栋

授予年度：2011年

学科分类：080902[工学-电路与系统] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主      题：可重构系统 异质模型 关联任务 布局布线 碎片量化 任务布局处理方案 

摘      要：可重构系统中,良好的硬件任务布局布线算法能够将更多的任务同时布局到可重构器件上,并对有通信需要的任务进行布线连通,加快系统执行任务的进程,提高器件的资源利用率。随着芯片工艺不断改进,可重构FPGA所提供逻辑资源的种类和规模的迅速增加使其内部结构异质化,原有基于同质器件模型的任务布局布线算法已不再适应异质化的器件结构;又任务在器件内动态增添和删除,造成器件内空闲资源碎片化,影响了后续任务的布局布线。因此,研究异质可重构器件模型下的硬件任务布局布线算法和碎片量化方法具有重要意义。 本文在分析可重构FPGA内部结构基础之上,改进了已有的异质可重构器件模型与硬件任务模型,提出了一种能够对多类型硬件任务同时布局布线的算法DRS-TCW,最后提出了一种支持FCTD碎片连续度量化方法的硬件任务布局处理方案。主要研究内容如下: 1.改进了已有的异质可重构器件模型与硬件任务模型,分别用数值矩阵和邻接矩阵对器件与任务模型进行描述。在分析可重构FPGA内部结构和部分重构技术之后,改进了异质的器件与任务模型,基于任务间的通信需要对任务进行了分类。通过数据结构设计,分别用数值矩阵和邻接矩阵对器件的使用状态和任务间的通信联系进行了数学描述,有效实现了对逻辑资源和任务的数字化管理,为后续研究任务布局布线算法奠定了基础。 2.提出了一种能够对多类型硬件任务同时布局和布线的算法DRS-TCW。深入分析任务布局和布线的资源需求,在任务队列设置分类窗口TCW,统筹兼顾各子队列中任务的资源需求,任务类型不同布局策略不同,并对关联任务进行方向性的DRS布线搜索连通。仿真表明,与FF算法相比,DRS-TCW算法提高了器件的资源利用率,并且具有较高的布线连通率。 3.提出了一种基于三维装箱模型的碎片连续度三维量化方法FCTD。该方法对任务布局造成的资源碎片进行三维抽象,从三维角度对碎片的连续度进行量化,并用量化结果指导后续任务的布局。仿真表明,该方法减少了布局碎片的产生,有效提高了器件资源利用率。 4.提出了一种支持FCTD碎片量化方法的硬件任务布局处理方案。将FCTD方法应用到任务的布局过程中,对不同类型任务进行区别性量化,进一步提高了系统的资源利用率。