（通信与信息系统专业论文）基于空时映射的多维可重构数字系统资源与任务管理.pdf

摘要摘要可重构数字系统是在通用计算机和专用集成电路的基础上发展起来的，它兼具通用计算机的灵活性和专用集成电路的高效性。可重构数字系统的动态重构能力使其能够在运行时动态地重构硬件，以较少的硬件资源分时完成较大的时序系统整体功能。可重构数字系统在重构过程中会出现功能上的不连续。为保证其功能正确且进一步提高性能，需要采用相应的资源和任务管理策略。基于多重上下文的动态可重构数字系统与局部可重构数字系统是两种不同的动态可重构方案。目前国内相关领域的研究主要集中在局部可重构数字系统上，基于多重上下文的动态可重构数字系统的资源与任务管理策略研究相对滞后。本文据此提出一种基于多重上下文的多维可重构数字系统资源管理模型多维空时( m d s t ) 资源管理模型，在此基础上对其资源与任务管理策略展开深入研究，主要包括以下内容。首先简要介绍可重构数字系统的任务与模块划分方法，并讨论划分结果对资源与任务管理的影响，研究多维可重构数字系统任务模型的一般形式；分析现有的一维、二维资源管理模型的主要特点，指出其对多维可重构数字系统资源管理模型建模的借鉴意义。其次讨论多维可重构数字系统资源管理模型建模的一般方法，提出m d s t 资源管理模型；通过对空时映射的研究提出将多维模型转化为二维模型的降维方法，并讨论了在不同限制条件下如何调整空时映射关系。最后在外部存储器利用率最高与系统执行时间最短两种不同的限制条件下，针对于m d s t 资源管理模型设计不同的资源与任务管理策略，并对策略进行详细地分析与评估。关键词：可重构，多重上下文，管理模型，管理策略，空时映射a b s t r a c ta b s t r a c tr e c o n f i g u r a b l ed i g i t a ls y s t e m sh a v e b e e nd e v e l o p e do nt h eb a s i so fm i c r o p r o c e s s o ra n da s l c s ，w h i c hc a na c h i e v em u c hb e t t e rp e r f o r m a n c et h a nm i c r o p r o c e s s o ra n dm a i n t a i n sah i g h e rl e v e lo ff l e x i b i l i t yt h a na s i c s t h ed y n a m i cr e c o n n g u r a t i o nc a p a c i t ye n a b l e st h es y s t e m st od y n a m i c a l l yr e c o n f i g u r et h e i rh a r d w a r ew h i l ew o r k i n g t h u st h ew h o l ef u n c t i o no fai a l g e rs e q u e n t i a ls y s t e mc a nb er e a l i z e ds t e pb ys t e pv i aas m a l l e rh a r d w a r ec a p a c i t y i nt h ep r o c e s so fr e c o n f i g u r i n g ，t h es y s t e mm i g h tw o r kd i s c o n t i n u o u s l y , a n dt h e r e f o r ei ti sn e c e s s a r yt ou s ec o r r e s p o n d i n gr e s o u r c ea n dt a s km a n a g e m e n ts t r a t e g i e ss oa st oe n s u r et h a tt h es y s t e mo p e r a t e sc o r r e c t l ya n dh a sab e t t e rp e r f o r m a n c e r e c o n f i g u r a b l ed i g i t a ls y s t e m sb a s e do nm u l t i c o n t e x t sa n dp a r t i a l l yr e c o n f i g u r a b l ed i g i t a ls y s t e r n sa l et w od i s t i n c tk i n d so fd y n a m i cr e c o n f i g u r a b l es c h e m e s a tp r e s e n t ，r e s e a r c ho ns t r a t e g i e so fr e s o u r c ea n dt a s km a n a g e m e n tb a s e do nm u l t i c o n t e x tr e e o n f i g u r a b l ed i g i t a ls y s t e m si sf a rb e h i n d f o rm o s to ft h ed o m e s t i cr e s e a r c h e si nt h er e l a t e df i e l d sf o c u so n l yo np a r t i a l l yr e c o n f i g u r a b l ed i g i t a ls y s t e m s b e c a u s eo ft h i s ，t h ep r e s e n tt h e s i sp r o p o s e sam o d e l t h em u l t i - d i m e n s i o n a ls p a c e t i m e ( m d s 日r e s o r c em a n a g e m e n tm o d e la p p l i c a b l et or e c o n f i g u r a b l ed i g i t a ls y s t e m sb a s e do nm u l t i c o n t e x t s a n dr e p o r t sa ni n - d e p t hs t u d yo nc o r r e s p o n d i n gs t r a t e g i e su s e df o rr e s o u r c ea n dt a s km a n a g e m e n to nt h eb a s i so ft h em o d e l t h et h e s i sc o n s i s t so ft h ef o l l o w i n gp a r t s t h ef i r s tp a r ti n t r o d u c e sm e t h o d so fd i v i d i n gt a s k sa n dm o d u l e si nr e c o n f i g u r a b l ed i g i t a ls y s t e m s ，f o l l o w e db yad i s c u s s i o no nt h ei m p a c t b o u g h tb yt h ed i v i s i o no u t c o m e so nt a s ka n dr e s o u r c em a n a g e m e n t t h e ni ta n a l y z e st h eg e n e r a lf o r mo fat a s km o d e l i nm u l t i - d i m e n s i o n a lr e c o n t i g u r a b l ed i g i t a ls y s t e m sa n dh i g h l i g h t st h em a i nf e a t u r e so ft h ee x i s t i n go n e d i m e n s i o n a la n dt w o d i m e n s i o n a lm o d e l so fr e s o u r c em a n a g e m e n tf o r t h er e f e r e n c eo fm o d d i n gr e s o u r c em a n a g e m e n ti nm u l t i d i m e n s i o n a lr e c o n f i g u r a b l ed i g i t a ls y s t e m s t h es e c o n dp a r td i s c u s s e st h eg e n e r a la p p r o a c ho fr e s o u r c em a n a g e m e n tm o d e l i n gi nm u l t i d i m e n s i o n a lr e c o n f i g u r a b l ed i g i t a ls y s t e m s i tp r o p o s e sam d s tr e s o u r c em a n a g e m e n tm o d e la n dd i s c u s s e sh o ws u c ham o d e lc a nb et a n s f o r m e di n t ot w o d i m e n s i o n a lm o d e l st h r o u g ht h es p a c e t i m em a p p i n gm e t h o d ，a n dh o wt oa d j u s tt h es p a c e t i m em a p p i n gr e l a t i o n s h i pw i t h i nt h ec o n s t r a i n t su n d e rd i f f e r e n tc o n d i t i o n s t h ef i n a lp a r tp r e s e n t st h ed e s i g no fs t r a t e g i e sb a s e do nm d s tr e s o u r c em a n a g e m e n tm o d e l d e t a i l e da n a l y s e sa n de v a l u a t i o n so ft h es t r a t e g i e sa r ea l s oc o n d u c t e d ，u s i n gan u m b e ro fp a r a m e t e r s ，u n d e rt h ec o n d i t i o nt h a tt h es y s t e m su t i l i t yo ft h ee x t e r n a lm e m o r yi sa tm a x i m u mo ri t se x e c u t i o nt i m ei sa tm i n i m u m k e y 、s o r d s ：r e c o n f i g u r a b l e ，m u l t i c o n t e x t ，m a n a g e m e n tm o d e l s ，m a n a g e m e n ts t r a t e g y , t i m i n g s p a c em a p p i n gh图目录图1 1图1 2图1 3图2 1图2 2图2 3图2 4图2 5图2 - 6图2 7图3 1图3 2图3 3图3 - 4图3 5图3 - 6图3 7图3 8图3 - 9图3 1 0图3 1 l图3 1 2图3 1 3图3 1 4图3 1 5图3 1 6图3 一1 7图4 一l图4 2图4 3图4 4图4 5图4 6图4 7图目录m s 2 系统架构示意图一4x p p 6 4 系统架构示意图4z m s 0 5 处理器架构示意图5从系统级到流水线级并行一9两种不同的任务划分方式1 0划分任务时发生死锁1 0一维资源管理模型示意图1 2空时二维资源管理模型示意图1 3空空二维模型示意图l5基点禁放区域示意图16两种不同的动态可重构数字系统架构2 1多重上下文可重构系统任务放置的空间自由度示意图2 3同一任务的不同放置方式2 3m d s t 资源管理模型示意图：2 4任务图范例2 4任务图和上下文之间最基本的映射关系2 5改进后的任务图2 6最基本的流水线配置过程2 6改进后的流水线配置过程2 7将任务图转化为一般的有向图3 0外部存储器队列3 2任务因资源受限而无法配置k 3 3基于二级队列的外部存储器管理方法_ 3 4采用二级队列管理上下文的配置过程3 4任务执行时间与上下文激活时间3 5采用时域拆分法进行映射调整_ ；3 6时域拆分后导致激活时间小于配置时间：3 7外部存储器中的数据与上下文3 9确定t _ 和t m + i 的相对位置4 0多种不同的成功放置方案4 l任务集合吸收合并条件示意图4 2两种不同标识方式形成的不同的集合划分4 3点边着色的顺序示意图4 4已放置任务的布局与待放置任务4 5v表目录图4 8图4 9图4 1 0图4 1 l图4 1 2图4 1 3图4 1 4图4 1 5图4 1 6图4 1 7图4 1 8图4 1 9图5 一l图5 2图5 3图5 4图5 5图5 6图5 7图5 8图5 - 9图5 1 0图5 一l l满足系统剩余资源受限条件仍无法放置4 6用赋权图表征系统时序4 8点v 3 插入后赋权图的变化4 8时域拆分后边赋权的变化4 9时域拆分的正确表示4 9数据处理单元与数据储存单元的关系5 0t m 与t m 在系统资源模型中的位置5l最小赋权值拆分前后对比5 2未产生实际效果的时域拆分5 3基于集合划分的时域拆分法流程图5 5有效拆分后的四种结果5 7改进后的基于集合划分的时域拆分法流程5 8占用四个资源单元格时的任务布局方式6 0两种存在数据交互的任务图6 l随机得到的一个实验样本6 2执行点边着色策略后得到的上下文6 3式5 1 集合所生成上下文对应的执行过程6 3三种策略性能曲线6 4针对单向数据交互任务图的点边着色策略执行时间测试结果6 5任务占用资源多少与策略运行时间统计关系曲线6 6配置时间对策略性能的影响7 0重构时间占系统运行总时间的比重7 l增加任务执行时间限制后的策略性能7 2表目录表5 1任务模型的高度宽度和面积对照表。、6 l表5 2系统执行总时间最短条件下策略性能对比6 9v i缩略词表英文缩写英文全称a l ua s i cb fc l bc md m af i f of p g af fl l pm d s tm f so t fp a cp a ep eq ar cr b ls o cv l s i缩略词表a r i t h m e t i cl o g i cu n i ta p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i tb e s tf i tc o n f i g u r a b l el o g i cb l o c kc o n f i g u r a t i o nm a n a g e rd i r e c tm e m o r ya c c e s sf i m ti nf i r s t0 u tf i e l dp r o g r a m m a b l eg a t ea r r a yf i r s t f i ti n t e g e rl i n e a rp r o g r a m m i n g ，m u l t i d i m e n s i o n a ls p a c e - t i m em a x i m u mf r e es u b n e to nt h ef l yp r o c e s s i n ga r r a yc l u s t e rp r o c e s s i n ga r r a ye l e m e n t sp r o c e s s i n ge l e m e n t sq u i c k l ya d a p tr e c o n f i g u r a b l ec e l lr i g h tb o r d e rl i n es y s t e mo nc h i pv e r yl a r g es c a l ei n t e g r a t e dc i r c u i tv i i中文释义算术逻辑单元专用集成电路最佳适合可配置逻辑块配置管理器直接内存存取先进先出存储器现场可编程门阵列最初适合整数线性规划多维空时最大空闲子网飞翔处理阵列簇处理阵列元件处理单元快速适配可重构处理单元右边界片上系统大规模集成电路独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：商红爱日期：7 0 0 q 年- 5 月了e l关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后应遵守此规定)签名：垄垒至导师签名：日期：加矿第一章绪论第一章绪论本章简要介绍可重构计算技术的发展现状，对本课题研究的意义进行分析，最后确定本论文的研究内容。1 1 研究背景当前，越来越多的应用领域要求计算兼具高性能和灵活性，a i s c 和微处理器两种实现方式显示出了各自的不足；计算密集的应用需要比以前更多的计算能力来支持，例如科学计算、流视频、图像识别和处理以及交互式服务。对功耗、生产成本和上市时间的需求也在日益增长。尤其是在嵌入式系统领域。面对这些挑战，可重构计算成为最有优势的计算形式川。1 1 1 可重构数字系统简介1 9 6 3 年加里福尼亚大学的g e r a l de s t r i n 首先提出可重构计算的概念1 2 l 。但由于受到半导体工艺的限制，作为可重构计算硬件平台的可重构数字系统的发展一直非常缓慢。直到上世纪9 0 年代末期，v l s i 技术的发展促进了可重构数字系统的完善，一些研究机构和公司逐步推出了一系列具有实用价值的可重构数字系统。典型的可重构数字系统由一个或多个处理器和可重构功能单元阵列组成。处理器完成任务调度、过程控制等功能，可重构功能单元阵列完成运算密集型大数据量运算。根据重构功能单元的操作数宽度【3 j ，可重构数字系统可分为粗粒度可重构数字系统和细粒度可重构数字系统两大类：( 1 ) 细粒度可重构数字系统以商用化f p g a 为典型代表。x i l i n x 公司的v i r t e x i i 系列f p g a 以c l b 为最小重构单元，每次可对一列c l b 阵列进行重新配置【4 l 。细粒度可重构数字系统可以直接重构位( b i t ) 级单元，具有很强的灵活性。但细粒度可重构数字系统在配置时需要大量的配置数据，导致重构时间很长。随着可重构技术的发展，动态、实时重构越来越成为研究的重点。由于细粒度可重构数字系统配置时间过长，很难满足动态、实时重构的要求，近年来研究的热点逐渐转向粗粒度可重构数字系统。电子科技大学硕士学位论文( 2 ) 与细粒度可重构数字系统相对应的粗粒度可重构数字系统以字( w o r d ，由多个位组成) 级单元为基本重构单元，因高效而适于计算密集型应用。由于其配置数据相对较少，所需配置时间较短，可以满足动态、实时配置的要求。进入2 l 世纪以来，国外多家研究机构发布了多款粗粒度可重构数字系统。国内也有国防科技大学等院校从事粗粒可重构数字系统的体系架构研究并取得了系列成果。虽然粗粒度可重构数字系统尚未出现如f p g a 那样大规模商用化的器件，但已有多家国外公司发布了他们自行研发的相关产品。这一切都预示着粗粒度可重构数字系统的大规模实用化即将到来。1 1 2 可重构数字系统资源与任务管理策略可重构数字系统的动态重构能力使其能够在运行时动态地重构硬件，以较小的电路规模分时完成较多的功能。当可重构数字系统处于重构状态时，系统功能部分或全部处于不连续状态。为保证可重构数字系统功能正确且进一步提高系统性能，需要采用相应的资源和任务管理策略。可重构数字系统资源与任务管理策略主要需完成以下几方面工作：( 1 ) 保障可重构数字系统整体功能正确。由可重构数字系统实现较大的时序系统时，不同的功能在可重构数字系统中轮流实现。如何保证系统的时序在重构前后不发生混乱以至于系统不能正常工作，是可重构数字系统资源与任务管理策略所要考虑的首要问题。( 2 ) 提高系统资源的利用率。可重构硬件同时承载的任务越多，任务布局与空闲资源的管理越复杂。正如处理器对内存资源的使用一样，任务在可重构硬件上的不断添加和删除也会造成资源碎片。因此，既要对可重构资源进行管理以提高分配速度，又需要良好的布局方法减小系统在运行过程中产生的资源碎片，以提高可重构资源的利用率和可重构系统的性能【5 】。( 3 ) 减少重构时问。可重构数字系统需要通过配置其重构单元实现功能的改变以完成不同的功能。在这一过程中需要从外部存储器向可重构数字系统的配置管理器写入数据。数据传递的过程需要消耗时间，这段时问被称为重构时问1 6 】。在重构时间内，可重构数字系统的全部或部分电路处于无法工作的状态。重构时间的长短直接影响到可重构数字系统的工作效率。采用资源与任务管理策略减少重构时间以提升可重构数字系统的性能是需要关注的另一重点。2第一章绪论( 4 ) 提高系统执行并发任务的能力。可重构数字系统相对于通用微处理器的优势在于可以同时处理多个任务，因而提高了处理速度【刀。通过系统资源与任务管理策略使任务尽可能地被同时执行是进一步挖掘可重构数字系统计算能力的重要手段。在研究和评估策略时也需要给予充分的关注。1 2 研究现状可重构计算技术已经成为当前国际上研究的热门课题，多个国家的大学、研究所均有学者加入到数字系统动态可重构技术的研究工作之中。研究者分布在计算机、集成电路、信号处理、电子设计、软件开发等各领域，从不同的角度开展研究。近年来随着v l s i 技术的进一步发展和可重构计算、可重构数字系统研究的深入，可重构数字系统硬件平台的研究取得了一定进展。可重构数字系统资源与任务管理策略也随着平台研究的进步而更加深入地开展起来。1 2 1 可重构数字系统硬件平台研究进入2 1 世纪后，粗粒度可重构数字系统成为研究热点。德国k a i s e r s l a u t e r n 大学的r h a r t e n s t e i n 教授对过去1 0 年来的粗粒度可重构体系结构进行了总结，认为粗粒度可重构平台由于弥补了a s i c 和微处理器各自的不足，已占主流地位【8 】。参考文献 9 1 6 中介绍了近年来提出的多种粗粒度可重构数字系统体系结构及其硬件平台。其中加州大学的m o r p h s y 方案、p a c t 公司的x p p ( e x t r e m ep r o c e s s i n gp l a t f o r m ) 结构是较早提出也是较为经典的两种结构。2 0 0 8 年1 2 月2 9 日，新加坡创新( c r e a t i v e ) 公司发布了其投入2 5 年时间，1 0 亿美金和1 万余名研发人员研制的s o c 芯片“z m s 0 5 ”。“z m s 0 5 ”集微处理器、主板、s d k 、中间件、操作系统于一体，它的诞生标志着粗粒度可重构数字系统商用化时代的来临。m o r p h s y 方案以可重构单元( r e c o n f i g u r a b l ec e l l ，r c ) 阵列作为可重构处理单元，面向图像处理、数据加密、数字信号处理等领域。整个系统由一个可重构阵列，一个控制处理器，数据缓冲器和d m a 控制器组成。这是一个粗粒度结构，具有1 6 b i t s 的数据通路宽度。主要控制任务由片上的主处理器完成。可重构单元构成了一个8 8 阵列，支持多上下文( c o n t e x t ) 配置。每个r c 包括一个配置寄存器、两个选通器、一个舢l u 、一个乘法器、一个移位器、一个由四个1 6 位寄存器构成的寄存器堆。8 x 8 阵列分成四个子阵列，r c 之间的连接采用二维网格连接和3n 于科技人学硕f 峙0 位论文千阵列内的行列完全连接。r c 阵列的配馏信息存储在片上的上下文存储器中。存储器中不同的内容决定了各个r c 所实现的功能、r c 之问的互联结构等m 】。目前加州大学己推出第二代产品即m s 2 芯片，其框架图如图1 - i 所示。浚芯片具有多重上下文存储器，可以通过切换不同的上下文存储器在几纳秒内完成重构。这种重构力式的实现足动态可重构技术发展的主要标志。目前已经有研究者利用该，| 台实现了8 0 21 1 w l a n 物理层信号处理相关算法【1 。幽1 1m s 2 系统架构i 意幽x p p 系统主要山处理阵列元件( p r o c e s s i n g a r r a y e l e m e n t s ，p a e ) 、基于包交换、自动同步的通信网络、用户透明的层次化配置管理器( c o n 矗g i l r a l i o nm a n a g e r , c m )树、i o 模块等几2 ： | ；分组成，其系统架构如图1 - 2 所示f ”i 。霪二豢凹1 - 2x p p 9 4 系统架构示意图x p p 是根据数据流束工作的，支持任务级并行。一个p a e 与其相应的c m 台起米被称为一个处理阵y u g ( p r o c e s s i n g a r r a yc l u s t e r ，p a c ) 。该c m 负责向p a e 中的可配置对象写入配置数据。c m 树的根节点称为s c m ，即s u p e r v i s i n gc m 。只有第一章绪论s c m 与外部存储器相连接。外部的主处理器通过总线控制数据的输入输出，并控制配置流在外部存储器和x p p 中的c m 之间的流动。一个配置处理一系列被称为流的数据。计算的结果可以存储在分布式存储器或f i f o 中，以备后续配置使用。配置流根据资源的可用性自动调整1 2 0 1 。z m s ：0 5 处理器集成了两个a r m 一9 2 6 核心和4 8 个可编程处理器单元( p e ) ，浮点计算能力1 0 1 5 g f l o p s ，可以根据应用程序的需要实时自我重新编程，而且可以根据负载开启或关闭部分p e 核，比如在运行3 d 游戏或者播放高清视频时就会启动更多p e 。其架构如图1 3 所示。图l - 3z m s 一0 5 处理器架构不葸图该处理器设计的最大特点是无限扩展性。据称其可以在a 4 纸大小的空间里组成一台t f l o p s 级别超级计算机，在5 7 6 个刀片服务器里安装1 4 7 4 5 6 颗z m s 处理器后就能达到p f l o p s 级别，与当今性能最强的i b mr o a d r u n n e r 相差无几。这种特性和干细胞颇为相似，所以创新提出了“干细胞计算( s t e m c e l lc o m p u t i n g ) 的新概念【2 。但就其本质而言，仍属于可重构计算。从以上例子可以看出现行粗粒度可重构数字系统的基本模式是；主处理器+ 可重构处理单元阵列。主处理器完成整个系统的过程控制，并配置、管理可重构处理单元阵列。可重构处理单元阵列则完成大数据量运算密集型的计算任务。主处理器可以通过对可重构处理单元阵列进行重新配置让其完成不同功能。通过合理地管理可重构处理单元阵列的资源并合理地分配其执行的任务，可进步挖掘其潜力。圈围圆圈回团圈圈困围囤园围围困园园困团圈围困园园囤围圈围园圈圈园园园圃固电子科技大学硕士学位论文1 2 2 可重构数字系统资源与任务管理研究可重构数字系统资源与任务管理的研究和硬件平台的发展关系密切。可重构数字系统硬件的重构特性决定了系统资源与任务管理的研究模型。不同的可重构数字系统硬件平台，按照其支持的运行时重构特性可以分为4 类：( 1 ) 全局配置可重构数字系统：任何时候只能有一种功能在可重构数字中配置运行，要替换其功能必须全部重新进行配置；( 2 ) 一维可重构数字系统：允许在垂直或水平方向上的全部或某部分满足最小宽度区域进行部分重配置，即一维结构；( 3 ) 二维可重构数字系统：允许任务按照其资源需求被放置到可重构单元阵列的任意的空白区域中，即二维结构；( 4 ) 多维可重构数字系统：以m s 2 为代表的一批可重构数字系统具备多重的上下文存储器，因此不能简单地将其等同于二维可重构数字系统，必须采用多维模型才能更详尽地描述其可重构特性。由于全局配置可重构数字系统很难进行资源与任务管理，研究人员对此关注不大。一维可重构数字系统的资源与任务管理曾一度引起研究者的关注，但随着硬件平台的发展已经较少将其作为研究对象。近年来研究者大量关注二维可重构数字系统，并提出了f f b f ( f i r s tf i t b e s tf i t ) 、r b l l 2 2 1 、q a 捌以及s b a t 2 4 】等管理策略。目前尚较少见研究者讨论多维可重构数字系统的资源与任务管理策略。1 3 研究内容和意义1 3 1 研究内容目前的可重构数字系统资源与任务管理策略研究主要基于二维模型开展，并未考虑到多重上下文存储器与重构的时序特性对资源与任务管理策略带来的影响。本研究试图建立一种多维可重构数字系统资源管理模型，并讨论基于该模型的策略。本文主要分以下几个部分：6第一章绪论论文首先介绍基于可重构数字系统硬件平台的任务划分与模块划分方法，并讨论划分结果对资源与任务管理带来的影响。分析现有的一维、二维模型，指出其存在的缺陷与不足。论文进而针对现有一维、二维模型的缺陷，提出一种多维可重构数字系统管理模型多维空时资源管理模型，讨论了基于空时映射的降维方法。通过研究任务之间的时序关系与任务在多维资源管理模型中的空问相对位置之间的映射方法，将多维模型转化为多个二维模型进行管理。同时讨论在系统资源容量、执行时间等条件的约束下，如何改进映射方法。论文最后分析了在外部存储器利用率最高、系统运行总时间最少条件下的资源与任务管理策略所要满足的不同要求，讨论重构时间对资源与任务管理策略所带来的影响。根据要求的不同，研究多种适用于不同条件的资源与任务管理策略。通过仿真得到不同约束条件下不同资源与任务管理策略实施后的评估参数，在此基础上对策略的优缺点进行详细的分析与评估。1 3 2 研究意义随着v l s i 技术的继续发展，基于多重上下文的可重构数字系统硬件平台实现的难度逐渐降低。基于多重上下文的可重构数字系统因其重构时间上的优势，在需要完成动态、实时重构的领域中有很好的发展前景。多重上下文带来的空间扩展性以及动态、实时重构对时序的要求使得该系统不应当用简单的二维模型进行描述。在多维空间上研究该系统，必将进一步挖掘其运算能力并推进其实用化进程。本文主要贡献：在分析现有一、二维模型缺陷的基础上，提出了一种多维可重构数字系统资源管理模型m d s t 资源管理模型；在该模型的基础上探究基于空时映射的多维可重构数字系统资源管理模型的降维方法，使现有基于二维模型的管理策略可以继续得到应用。由于不同的约束条件下空时映射的具体方式有所不同，本文提出了多种资源与任务管理策略并进行详细评估。这些管理策略对可重构数字系统资源与任务管理的深入研究具有借鉴意义。7电子科技大学硕士学位论文i 4 论文结构第一章绪论介绍课题的研究背景，在归纳国内外相关研究的基础上，概括本文的主要研究内容和研究意义，最后给出了论文的组织结构。第二章分析可重构数字系统中的任务划分及其对任务与资源管理带来的影响，着重介绍目前常用的一维、二维资源管理模型及基于该模型的一些研究成果，分析可重构数字系统的建模方法。第三章针对目前一维、二维模型所存在的缺陷，提出一种多维可重构数字系统管理模型- m d s t 资源管理模型并讨论基于空。时映射的降维方法。第四章分别介绍在外部存储器利用率最高、系统执行总时间最短两种不同约束条件下的任务与资源管理策略。第五章详细评估第四章中介绍的任务与资源管理策略并得出结论第六章总结全文，并对未来工作做出展望。8第二章现有可重构数字系统资源管理模型与任务模型简介第二章现有可重构数字系统资源管理模型与任务模型简介进入2 1 世纪以来，国际国内的一些研究者在可重构数字系统资源与任务管理领域发表了一些研究成果。其中可重构数字系统资源管理模型与任务模型是所有研究的立足点与出发点。资源管理模型是对可重构数字系统计算资源以及系统运行时任务占用资源行为的抽象，而任务模型是指如何表征任务占用资源的情况。瞵7 】目前常见的资源管理模型主要是一维模型和二维模型。本章首先介绍可重构数字系统中的任务划分及其对资源和任务管理的影响以及任务模型的一般形式；然后详细介绍目前常见的一维和二维资源管理模型；最后将分析资源管理模型建模的一般方法。2 1 可重构数字系统中的任务划分在动态可重构数字系统中，当时序系统所需的资源大于硬件能够提供的资源时，需要将系统划分为多个子系统、任务、循环等。时域划分是把一个系统在时间上划分成互相关联的任务，划分的结果直接影响系统最终效率。可重构数字系统一次可载入多个任务，每一个任务可以包含多个系统级、循环级、指令级、流水线级并发操作。通过不同层次上的并行运算，可重构数字系统实现了运算加速。不同等级的并行运算示意图如图2 1 所示【2 8 1 。系统级并行曰圈圈圈任务级并行循环级并行指令级并行图2 1从系统级到流水线级并行9电子科技大学硕士学位论文由于有的任务只包含一个循环，有的任务包含多个循环，本文将任务和循环统称为任务，着重在任务级建立模型并展开讨论。由于划分过程复杂，早期可重构系统任务划分均由开发人员手工完成【z 9 】，后来研究者尝试采用算法自动进行任务划分。p u m a 等人给出了2 个简单的划分算法：逐层划分( 1 e v e lb a s e d ) 算法和聚集划分( c l u s t e rb a s e d ) 算法【3 0 1 。与此同时k a u l 等人提出采用整数线性规划( i n t e g e rl i n e a rp r o g r a m m i n g ，i l p ) 方法求解划分问题 3 1 10 此后不久t a k a y a m a 等人给出了一种综合考虑提高操作并行度和减少模块间通信量的划分算法【3 2 1 。不同的算法各有优缺点，其划分结果对可重构数字系统的资源与任务管理产生不同的影响。图2 2 展示了两种不同的任务划分方式。图2 - 2 两种不同的任务划分方式任务划分时必须注意以下问题3 3 】：( 1 ) 避免死锁：表示时序系统的数据流图是有向图，如果一个节点的前驱节点被分配到后继模块中，就会引发死锁现象。图2 3 给出了这种情况的图示，其中节点c 被分配给模块p 2 ，而c 的后继g 却在模块p l ，从而引发死锁。图2 3 划分任务时发生死锁1 0第二章现有可重构数字系统资源管理模型与任务模型简介( 2 ) 资源约束：因为可重构硬件资源有限，划分时必须考虑资源约束。资源约束直接关系到最终模块数。在理想情况下，模块数的下界由下式决定：l b ( p ) = r g r t o t a l ( 2 - 1 )式2 1 中：r g 为整个系统所需的资源，r t o t a l 为可重构硬件资源。在实际划分中，使得每个模块尽可能充分利用硬件资源，从而减少模块数，达到减少配置时间的目的。( 3 ) 提高并行度和降低通信量之间的折中：单个模块的关键路径越短，则该模块的处理速度越快。因此应尽量将能够并行的操作划分到同一个模块中。但这样将会导致跨模块数据传输量有所增加( 一般认为数据传输量和数据传输时间成正比) 。因此必须在提高并行度和降低通信量之间寻求适当的平衡，以达到较好的综合划分效果。可重构数字系统中的任务划分方法是一个独立的研究课题，本文并不将其作为讨论的重点。但可重构数字系统任务划分所产生的一系列指标将对资源与任务管理带来影响，因此在研究资源与任务管理策略时必须加以考虑。任务划分所产生的以下多个指标对资源与任务管理产生影响：( 1 ) 任务个数：不同的任务划分方法会导致划分后所得到任务的个数出现差别。一般而言，任务个数越多，资源与任务管理策略越复杂；任务越少，资源与任务管理策略越简单。与之相对应的是任务个数越多，资源与任务管理方式越灵活；任务个数越少，资源与任务管理方式越单一。( 2 ) 单个任务中包含的操作( o p e r a t i o n ) 个数：在系统功能确定的前提下，任务划分后各个任务中包含的操作个数与任务个数成反比。任务个数越多，则单个任务中包含操作的平均数越少，反之则越多。任务中包含的操作个数与任务所需要占用的资源多少直接相关。任务中所包含的操作越多，需要的资源越多。因此单个任务中包含的操作数绝不能超过资源的限制。同理，同时运行的任务所占用总资源也不能超过这一限制。这是可重构数字系统资源与任务管理应考虑的基本条件。( 3 ) 任务之间的时序关系：任务之间的时序关系在很大程度上决定任务载入可重构数字系统的先后顺序。具有执行先后顺序的任务不能同时被载入，而多个并发任务却可以在系统中同时运行。电子科技大学硕士学位论文( 4 ) 任务的持续时间：任务的持续时间关系到资源的占用与释放。当任务处于执行状态时，其所占用的资源不能被其它任务所占用。因此在进行资源管理时需要将可用资源与不可用资源区分开来。某任务持续的时间越长，则其它任务在某一段时间内可利用的资源越受限；某任务持续的时间越短，则其它任务可尽早地利用其已释放的资源。以上若干项指标和系统的整体功能以及任务划分的具体方法都有密切的联系。确定这些指标是一系列比较复杂和仔细的过程，且不在本文的讨论范围之内。因此，以上各项指标在本文中均被假设为确定的已知量，作为研究的前提条件。2 2 一维资源管理模型一维模型要求硬件任务可被布局在水平方向上的任何位置，但在竖直方向上，每列不能同时存在一个以上的硬件任务，如图2 - 4 所示。：“0 ，ie 。：邙j ? ?，、，j：。ip，7 i”? ，、| ? ；t at 4 _ 。?。? ：，、j丑?一，07 ：，o ，u ：幽j i ，口i ，南f一一j t 。一，毫j：，4 j5 。j j 。j 。! ? ：、jj ，t i。，：一! v jj t 3，r”，1 。+、 jj i 。图2 - 4一维资源管理模型示意图一维资源管理模型来源于被大规模地应用的商用化f p g a ，如x i l i n x 的v i r t e xi i 系列1 4 1 f p g a 要求：可重构模块的高度是整个器件的高度+ ；可重构模块的宽度最小是四个s l i c e ，最大可以达到整个器件的宽度，但必须是四个s l i c e 宽度的整数倍；可重构模块放置的水平坐标必须是四个s l i c e 边界的整数倍。可重构模块一旦确定，其边界不能改变，与其它模块之间的通信只能通过总线宏。为了保证重构时系统的时序正确，需要额外的握手信号，同时需要在可重构过程前后保存可重构模块内存储元素的状态。1 2第二章现有可重构数字系统资源管理模型与任务模型简介一维资源管理模型只允许在水平方向上存在多个任务， 3 4 1 所需的资源通常转化为宽度进行描述。在一维模型的约束下，资源与任务管理算法主要研究如何将某一宽度的任务放置到垂直方向上，同时尽可能地减小任务与任务之间的间隔以避免产生无法利用的资源“碎片”。以s t u f f i n g 算法【3 5 】为代表的一系列算法针对此问题进行了详细的探讨。但多数论文并不单纯以一维模型作为研究对象，研究者通常将时间作为研究的另一维度进行分析，实际上形成了下一节要介绍的空一时二维资源管理模型。2 3 二维资源管理模型建立二维资源管理模型需同时考虑两个不同的变量，主要包括空时二维资源管理模型和空一空二维资源管理模型。2 3 1 空时二维资源管理模型空一时二维资源管理模型是在一维模型基础上发展而来的。研究者在基于一维模型进行研究时不仅考虑当前任务在剩余资源中的放置策略，还考虑到任务的持续时间和先后顺序。由于增加了时间这一参数，研究模型从原来只具备水平方向的一维模型变换为具备水平方向一时间两个维度的模型，如图2 5 所示 3 6 l 。图2 5空时二维资源管理模型示意图电子科技大学硕士学位论文图2 5 中，横轴x 表示一维模型中水平方向的宽度。整个水平方向被划分为8列，每个任务至少占用其中一列。图中表示任务的矩形框t n 的宽度即反映了该任务占用可重构数字系统资源的数量。纵轴t 表示时间，整个系统的运行时间被划分成l o 个时间片，每一个任务至少持续一个时间片。图中表示任务的矩形框t n 的下边沿确定了该任务的起始时间，上边沿确定了该任务的结束时间。整个矩形框t n的高度反映了该任务所需要持续的时间。在空时二维模型上研究资源与任务管理策略可以把第n 个任务用4 维向量t n( w ，s ，t ，e ) 表示。向量中w 表示该任务宽度，s 表示该任务在整个数字系统中处于哪一级( s t a g e ) 以确定其与其它任务之间的时序关系，t 表示该任务的持续时间，e 表示该任务的过期时间。若要确定第n 个任务在二维模型中所处的位置，至少需要通过资源与任务管理策略确定两个参数：任务的起始时间( 即矩形框t n 的下边沿所在位置) 及其所占资源的起始位置( 即矩形框t n 左边沿所在位置) 。可用2 维向量p n ( d ，l ) 来表示这两个参数。若资源与任务管理策略用函数f ( ) 表示，则有 p i ，p 2 p n ) = f ( t l ，t 2 t n )( 2 2 )p