（通信与信息系统专业论文）认知无线终端重构中的资源调度算法研究.pdf

摘要 可重构的认知无线网络是当前无线领域内的一个热点问题，而其中终端重构 问题是影响终端与网络之间协同性能的关键技术。认知无线电系统的资源管理包 括无线资源管理，计算资源管理以及应用资源管理等。认知无线终端( c o g n i t i v e r a d i ot e r m i n a l ，c r t ) 的重构主要涉及对计算资源和应用资源的重新分配，它实质 上是一个异构计算平台上的任务调度过程。如何高效的实现终端的重构关系到认 知无线网络的性能。 本文在认知无线电背景下，描述了认知无线终端系统特征，对认知无线终端 的应用资源和计算资源进行建模。根据现有的调度算法，提出两种高效资源调度 算法：演进的动态级调度( e d l s ) 算法和聚类优先级( c p s ) 算法。e d l s 改进了任务 聚类方法，并与动态级调度算法相结合，能够有效地进行时间编辑。而基于表调 度的c p s 算法方法将改进的聚类方法与改进的h e f t 算法结合起来，与e d l s 性 能接近。两种算法被用于终端重构过程中的资源调度，充分考虑了任务之间的数 据交互，提高了多处理器任务调度的效率，进而有效地减少认知无线终端平台重 构时间。 关键词：认知无线电异构终端重构任务调度 a bs t r a c t i ti sah o ti s s u et or e s e a r c ho nr e c o n t i g u r a b l ec o g n i t i v er a d i on e t w o r k s ，a n dt h e r e c o n f i g n r a t i o no fac o g n i t i v er a d i ot e r m i n a l ( c r t ) i sak e yt e c h n o l o g yi nc o o r d i n a t i o n b e t w e e nt h et e r m i n a la n dt h en e t w o r k t h es y s t e mr e s o u r c em a n a g e m e n to f c o g n i t i v e r a d i oc o n s i s t so f r a d i o ，c o m p u t i n ga n da p p l i c a t i o nr e s o u r c e t h er e e o n f i g u r a t i o no f a c r tw h i c hi se s s e n t i a l l yat a s ks c h e d u l i n gp r o c e s so nh e t e r o g e n e o u sc o m p u t i n g p l a t f o r mp r i n c i p a l l yd e a l sw i t ht h er e a l l o c a t i o no fc o m p u t i n ga n da p p l i c a t i o nr e s o u r c e s h o wt oi m p l e m e n tt h er e c o n f i g u r a t i o no fac r t e f f e c t i v e l yc o n c e r n st h ep e r f o r m a n c e o fc o g n i t i v er a d i on e t w o r k u n d e rt h eb a c k g r o u n do fc o g n i t i v er a d i o ，t h i sp a p e rr e p r e s e n t st h ef e a t u r eo f c o g n i t i v er a d i ot e r m i n a ls y s t e ma n dm o d e l so fc o g n i t i v ew i r e l e s st e r m i n a la p p l i c a t i o n r e s o u r c ea n dc o m p u t i n gr e s o u r c e a c c o r d i n gt ot h ee x i s t i n gs c h e d u l i n ga l g o r i t h m ，t h i s p a p e rp r o p o s e st w oe f f i c i e n tr e s o u r c es c h e d u l i n ga l g o r i t h m ：t h ee v o l v e dd y n a m i cl e v e l s c h e d u l i n g ( e d l s ) a l g o r i t h ma n dc l u s t e r i n ga n dp r i o r i t ys c h e d u l i n g ( c p s ) a l g o r i t h m e d l s ，w h i c hc o m b i n e st h ei m p r o v e dt a s kc l u s t e r i n gm e t h o d ，a n dt h ed y n a m i cl e v e l s c h e d u l i n ga l g o r i t h m ，i sa ne f f e c t i v ec o m p i l e t i m es c h e d u l i n gt e c h n i q u e c p sm e t h o d w h i c hi sb a s e do nt h el i s ts c h e d u l i n g ，c o m b i n e st h ei m p r o v e dt a s kc l u s t e r i n gm e t h o d a n dt h ei m p r o v e dh e f t a l g o r i t h m t w oa l g o r i t h m sw h i c ha r eu s e df o rr e s o u r c e s s c h e d u l i n go f t h et e r m i n a lr e c o n f i g u r a t i o np r o c e s s ，f u l l yc o n s i d e r i n gt h ed a t ae x c h a n g e b e t w e e nt h et a s k s ，e n h a n c et h et a s ks c h e d u l i n ge f f i c i e n c yo f m u l t i p r o c e s s o r s a r c h i t e c t u r e sa n dd e c r e a s et h er e c o n f i g u r a t i o nt i m eo fc r t k e y w o r d s ：c o g n i t i v er a d i oh e t e r o g e n e o u st e r m i n a lr e e o n f i g u r a t i o nt a s k s c h e d u l i n g 第一章绪论 第一章绪论 1 1 选题背景与意义 异构无线接入技术的共存是现代无线通信的特征。例如，新兴的3 g 系统，并 不试图取代世界范围可用的2 g 服务，也不和无线局域网( w l a n ) 或无线个人区 域网( w p a n ) 服务竞争。这些无线接入技术在一定程度上相互补充：2 g 系统提 供承载语音业务和低速数据的世界漫游；3 g 系统为多媒体服务提供更高数据速率； w l a n 系统在访问全局信息时以低代价提供非常高的数据速率，而w p a n 系统无 线互联个人设备。更多的无线接入技术在未来会被引进。因此，一个能感知周围 环境的资源管理对于充分利用异构和动态无线接入网络来说是必要的。这就导致 了认知无线电的产生。 认知无线电是一种智能无线通信系统，它能感知周围环境，从周围环境中获 取信息，并通过实时改变传输参数来适应运行环境的变化。从定义中可以看出， 认知无线电应当具备的两大主要特征是认知能力和重新配置能力。认知能力能够 使认知无线电和周围环境进行交互活动，进而决定适合的通信参数来适应环境的 无线频谱资源；重新配置能力能够不改变任何硬件部分而调整发射参数。从认知 方面来看，认知无线电看起来像信号处理和机器学习过程；从重新配置方面来看， 认知无线电看起来像认知无线终端在执行通过认知能力获得的任务，在无线接入 技术之间动态切换，为异构无线通信系统引入了灵活性【l j 。认知无线电从广义上来 讲是指认知无线终端具有足够的智力或认知能力，通过对周围无线环境的历史和 当前情况进行检测、分析、学习、推理和规划，利用相应结果调整自己的传输参 数，只用最合适的无线资源完成无线传输。 可重构的认知无线网络是当前无线领域内的一个热点问题，而其中终端重构 问题是影响终端与网络之间协同性能的关键技术。认知无线电的主要资源是无线 资源，应用资源和计算资源。认知无线终端重构，正是由无线接入技术之间的动 态切换引起的硬件平台的计算资源的重新分配，因此认知无线终端的重构是认知 无线电的重要组成部分。 而在目前很少有文献提出怎样具体的实现认知无线终端的重构。由于认知无 线终端设备与现在的通用计算设备之间具有很大的相似性，认知无线终端的重构 实质上是一个异构计算平台上的任务调度过程。因此，适用于异构处理器平台的 映射和调度算法都可用于认知无线终端的重构。本文给出认知无线电的系统资源 特征并进行资源建模，并结合现有异构计算平台上的任务调度算法，提出以减少 2 认知无线终端重构中的资源调度算法研究 认知无线终端重时间为目标的调度算法，对认知无线终端重构算法进行了研究与 探索。 1 2 1 静态调度 1 2 调度算法的发展 现在的调度算法的研究都是基于并行多任务的处理。在进行多任务处理时， 人们大量利用并行处理方式来节省时间，提高处理效率。并行处理是能满足大量 并行进程的计算要求的一个有效的方法。但是，它也提出了在顺序处理中不会遇 到的问题，例如设计一个应用程序的并行算法，将应用程序分割成任务，协调通 信和同步和将任务调度在处理器上。目前已经有大量的人员致力于此方面的研究。 调度和分配是一个重要的问题，因为一个不合适的任务调度不能充分利用系统的 潜能并且会抵消并行化获得的增益。调度的目标是通过适当的将任务分配在处理 器上来最小化并行应用程序的完成时间1 2 】。 并行任务调度的分类如图1 1 所示： 图1 1并行任务调度分类 从图中可知，将一组任务调度到一组处理器上的并行调度问题可以分为两个 方面：作业调度和调度与映射，前者是将独立任务调度在分布式计算系统的处理 器上来优化总的系统性能。而调度与映射问题要求一个并行程序的多个交互任务 的分配来最小化在并行计算系统上的完成时间。 从广义上来讲，调度与映射问题又可以分为两种形式：动态的和静态的。在 静态调度中，一个并行程序的特征( 任务处理时间，通信，数据依赖和同步要求) 在程序执行之前就已经知道。在动态调度中，在执行之前只能得出一些关于并行 程序的假设，并且调度决定在运行中做出。动态调度算法的目标不仅包括程序完 第一章绪论 3 成时间的最小化而且也包括构成运行调度器付出代价的重要部分的调度开销最小 化。在本论文中，作者只介绍与研究方向相关的静态调度。 静态调度中调度的任务分为两种形式：任务交互图和任务优先图。任务交互 图中顶点代表并行进程而定点之间的连线代表进程之间的交互。任务交互图一般 用于松耦合通信进程在分布式系统中的静态调度过程，因为所有的任务被认为是 同步的并且可以独立的执行，并没有暂时的执行依赖。调度的目标是通过将任务 适当的映射给处理器来最小化并行程序的在完成时间。这就需要在平衡处理器之 间的计算负载同时尽可能降低通信代价。 在任务优先图模型或有向无环图( d i r e c t e d a c y c l i eg r a p h ，d a g ) 中，结点 代表任务而有向边线代表了执行依赖性和通信量。因此d a g 通常被用于紧耦合任 务的并行程序在多处理器上的静态调度。调度目标是最小化应用执行时间。对于 绝大多数的并行应用程序，一个任务优先图能够更精确的模型化应用因为它能够 描述任务之间的暂时的依赖关系。在论文中介绍的算法中我们都是用这种模型。 在d a g 调度中，目标计算系统是一个处理元件的网络。处理元件包括一个处 理器和一个本地存储单元，因此通信仅仅依赖于传递的信息。处理器可能是同构 的或异构的。处理器的异构性意味着处理器有不同的处理速度或处理能力。 这些处理元件被一个具有一定拓扑结构的互联网络连接。这个拓扑结构可能是完 全连接的或是一个超立方体或网孔状的。 早期的静态调度研究提出了关于简化并行应用程序和并行处理系统结构的假 设，例如统一的结点权重( 执行时间) ，0 边权重( 通信数据) 和无限的可用的处 理器数目。然而，即使在这些假设存在的前提下，调度问题仍然被证明是一个n p 完全问题。现在普遍研究的调度问题是任务优先图在异构多处理器平台上的调度。 综上所述，调度问题除了一些极个别简化了的个例外，是一个n p 完全问题。 1 2 2 调度算法简介 一个高速网络连接的处理器集合构成了一个异构计算系统。它能够支持计算 密集并行和分布式应用的执行。一个应用的任务在可用处理器资源上的有效地调 度是获得高性能的关键因素。一般的任务调度问题包括将一个应用的任务分配给 合适的处理器的问题和在每个处理器上对要执行的任务进行优先级确认的问题。 并行任务在多处理器平台上的调度是一个非常有活力的研究领域。调度算法 的研究已经有较长的历史在很多文献中提出了许多不同的探索。到目前为止，大 多数文献中提出的调度算法都是以减少执行时间为目标的，并且已经有了较好的 4 认知无线终端重构中的资源调度算法研究 性能。根据采用方式的不同，这些调度算法被分为多种类型( 例如表调度算法， 聚类算法，基于复制的算法，引导随机搜索算法) 【3 j 。 一些考虑了任务之间通信的调度算法假设可用无限数目的处理器。这种类型 的算法被称作u n c ( u n b o u n d e dn u m b e ro fc l u s t e r s ) 调度算法。一部分u n c 算法 采用的技术被称作聚类，因此又被称为聚类算法。聚类算法在调度过程的初始阶 段，每一个结点都被看做是一个群集。在随后的步骤中，如果合并能减少完成时 间，那么两个群集被合并在一起。这个合并过程一直持续到没有群集可合并为止。 若两个任务被分配给一个群集，那么它们将会在同一个处理器上执行。聚类算法 背后的原理是它们能够利用更多的处理器来进一步的减少调度长度。然而，聚类 算法中产生的群集需要一个后续处理来将群集映射到处理器上，因为可用的处理 器的数目可能会少于群集的数目。结果，最终的解决方案的质量依赖于群集- 映射 步骤【4 】。聚类调度算法主要有： e z ( e d g e z e r o i n g ) 算法：在任务图边权重基础上选择要合并的群集，每步将 有最大权重的边设为0 ； l c ( l i n e a rc l u s t e r i n g ) 算法：在关键路径基础上迭代的将结点合并成为一个 单个的群集。已经合并的结点被移走而合并过程重复进行； d s c ( d o m i n a n ts e q u e n c ec l u s t e r i n g ) 算法：算法设计的基础是一个图形的主 导序列( d o m i n a n ts e q u e n c e ，d s ) 。d s 是部分调度的d a g 的关键路径。算法最 主要的特点是为了降低时间复杂度，一个节点的t 层级被逐渐的计算而b 等级保 持不变直到结点被调度； m d ( m o b i l i t yd i r e c t e d ) 算法：算法是在一个叫做相对移动性的属性的基础上 选择调度的结点； d c p ( d y n a m i cc r i t i c a lp a t h ) 算法：算法是在一个移动性的值的基础上设计的， 并采用一个向前看的策略来为给定的结点找到一个更好的群集。 由于上述算法需要一个无限制的处理器个数，因此不能被实际应用。 t d b ( t a s kd u p l i c a t i o nb a s e d ) 调度算法同样假设无限制数量的处理器的使 用，但是调度重复的任务来进一步减少调度长度。t d b 算法的理由是通过冗余的 将一些任务分配到多个处理器上来削减通信开销【5 l 【6 】。在基于重复的调度中，可以 采用不同的策略来选择用于复制的原始结点。一些算法只复制直接前驱而另外一 些试图复制所有可能的前驱【7 1 。主要的t d b 算法有： p y ( p a p a d i m i t r i o ua n dy a n n a k a k i s ) 算法：使用一个属性值来逼近一个节点 的开始时间的绝对可达到的较低的界限，产生的调度长度距离最优有一个2 的偏 差； l w b ( l o w e r b o u n d ) 算法：先确定每个节点的较低界限的开始时间，然后识 别d a g 中一组关键边。包含关键边的路径被调度到同一个处理器上； 第一章绪论 5 d s h ( d u p l i c a t i o ns c h e d u l i n gh e u r i s t i c ) 算法：先确定结点在处理器上的开始 时间而不进行结点的复制，然后考虑在处理器上最后一个调度的结点的结束时间 到现在正在考虑的节点的开始时间之间的空闲时隙中复制： b t d h ( b o t t o m u pt o p d o w nd u p l i c a t i o nh e u r i s t i c ) 算法：是d s h 算法的一 个扩展。它怀着开始时间会最终最小化的希望持续复制一个节点的前驱，即使复 制时隙已经被用完； l c t d ( l i n e a rc l u s t e r i n gw i t ht a s kd u p l i c a t i o n ) 算法：先构造线性群集然后 识别群集间决定完成时间的边线。它根据这些边线试图复制群集中一些节结点的 前驱来削减它们的开始时间； c p f d ( c r i t i c a lp a t hf a s td u p l i c a t i o n ) 算法：此算法是基于将d a g 分成三种 类型：关键路径结点，分支节点和其他结点。它试图尽可能早的开始调度关键路 径结点，通过递归的复制接入到它的分支结点。 但是这些算法的算法复杂度要远远高于其他种类的算法，比如b t d h 算法， d s h 算法，c p f d 算法的复杂度是o ( m 4 ) ，其中m 为任务个数。因此此种算法也 不适用于实际的应用。 而另外一些算法假设一个有限的处理器个数，因此这种调度被称作b n p ( b o u n d e dn u m b e ro fp r o c e s s o r s ) 调度算法。在这种算法中就不需要像u n c 算法 中的后续处理，因此此种算法更加实用并且具有比其他种类的算法更好的性能。 多数的b n p 调度算法是基于所谓的表调度技术。表调度的基本思想是通过分配给 要调度的任务一些优先级来建造一个调度表，然后重复的执行下面两个步骤，直 到图中所有的节点都被分配完为止：( 1 ) 移出调度表中的第一个结点；( 2 ) 将该 节点分配给能够最早开始执行该节点的的处理器。有很多种方法来判定结点的优 先级，例如最高层级最先( h i g h e s tl e v e lf i r s t ，h l f ) ，最长处理时间( l o n g e s t p r o c e s s i n gt i m e ，l p t ) ，关键路径( c r i t i c a lp a t h ，c p ) 嘲等。 表调度算法分为静态表调度和动态表调度。在静态表调度算法中，调度表在 节点分配之前是静态构造的，并且最重要的是，表中的先后顺序在结点分配过程 中是不会修改的。相反，在每一次分配之后，动态表算法重新计算未调度结点的 优先级，然后用新计算的优先级重新排列表中结点的先后顺序。因此这些算法关 键采用以下三步：( 1 ) 判定所有未调度节点的优先级；( 2 ) 选择拥有最高优先级 的结点进行调度；( 3 ) 将节点分配给能够最早开始执行的处理器。明显地，采用 上述三个步骤的方法的调度算法等够产生更好的调度。然而一个动态表方法会增 加调度算法的时间复杂度。主要的表调度算法有： h l f e t ( h i g h e s tl e v e lf i r s t 谢t l le s t i m a t e dt i m e s ) 算法：这是一个最简单的表 调度算法，使用静态b 层级作为节点优先级； 6 认知无线终端重构中的资源调度算法研究 i s h ( i n s e r t i o ns c h e d u l i n gh e u r i s t i c ) 算法：使用将节点插入由于部分调度产生 的漏洞这样一个简单有效的方法； e t f ( e a r l i e s tt i m ef i r s t ) 算法：每一步计算所有就绪结点的最早开始时间， 然后通过彻底检查结点在所有处理器上的开始时间，选择拥有最小开始时间的结 点： m c p ( m o d i f i e dc r i t i c a lp a t h ) 算法：使用一个叫做a l a p 的属性值作为结点 的优先级。此种算法的复杂度较低，一般为o ( n m 2 ) ，其中n 为处理器个数。 还有一种b n p 算法是引导随机搜索技术。引导随机搜索技术，或随机化技术 使用随机选择来引导自己通过问题控件，这和随机搜索方法中仅仅进行随机游动 是不一样的。这些技术总和从带有一些随机化特征的先前搜索结果中得到的信息 来产生新的结果。由于任务调度问题的一些特色，遗传算法( g e n e t i c a l g o r i t h m s ， g a s ) 【9 】是最流行并且应用最广泛的技术。然而，它们的运行时间远高于那些启发 式技术。另外，一个遗传算法中的一些参数也要合适的判定。用于调度一个任务 图的最优的控制参数集合对于另外一个任务图来说可能不能给出最好的结果。除 g a s 之外，模拟退火【1 0 】和局部搜索方法也属于引导随机搜索技术。 在上述两类算法中，处理器被假设为是完全连接的，并且不考虑链路冲突或 用来通信的路由策略。还有一些算法的设计基于最普遍的由一个专用网络拓扑组 成的链路不是无冲突的系统模型。这些算法被称为a p n ( a r b i t r a r yp r o c e s s o r s n e t w o r k ) 。除了调度任务，a p n 算法也调度在网络通信链路上的消息。消息的调 度可能会依赖于基础网络采用的路由策略。在这种无约束情况下优化调度长度使 得a p n 调度算法的设计是错综复杂的和有挑战性的。a p n 算法主要有： m h ( m a p p i n gh e u r i s t i c ) 算法：通过计算所有节点的静态b 层级来分配优先级。 一个就绪的结点列表被初始化为包括降序排列的所有进入结点。每个节点被调度 到给出最小开始时间的处理器上； d l s ( d y n a m i cl e v e ls c h e d u l i n g ) 算法：使用一个叫做动态级的属性值作为结点 的优先级，就是一个节点的静态级和它的在一个处理器上的最早开始时间的差别； b u ( b o t t o mu p ) 算法：首先找出一个d a g 的关键路径并将关键路径上的所有 结点立刻分配到相同的处理器上。然后，算法以逆序拓扑顺序将那个剩余的结点 分配给处理器。结点的分配由试图平衡在所有给出的处理器上的负载的一个负载 均衡处理器选择启发来指导； b s a 饵u b b l es c h e d u l i n ga n da l l o c a t i o n ) 算法：通过将所有结点注入到拥有最高 等级的中心处理器上来逐渐构造一个调度，然后通过将一个结点转移到中心处处 理器的相邻处理器上来减小每个节点的开始时间，如果这个转移能够减小这个结 点的开始时间的话。此种算法的复杂度要高于b n p 算法，比如d l s 算法的复杂度 为o f n m 3 1 ，但是总体上低于t d b 算法。 第一章绪论 7 由于一般调度问题的难解性，我们采用了两种主要的方法：牺牲有效性来得到 最优性和牺牲最优性来得到有效性。因此在以后介绍中，若是对算法的的性能进 行改善，那么它的复杂性多数都会增加，也就意味着有效性的降低。而各种早期 的基础算法虽然性能不够理想，或采用的模型并不适合于现有的异构计算平台上 的任务调度，但是它们的思想可以被利用来进行新的算法的设计，或者将它们的 优势结合起来，例如将聚类算法和表调度等算法结合起来，会获得更好的算法性 能。 1 3 论文的主要内容及结构安排 本论文重点研究了认知无线终端重构的资源调度算法。目前尚无很多对于认 知无线终端重构算法的研究，只有一种基于减少计算资源占用的t 映射算法。本论 文根据认知无线终端的系统资源特征，根据它与现有的可重构异构计算平台的相 似性，在现有的异构计算平台调度算法的基础上，给出两种新的认知无线终端重 构算法：演进的动态级调度和聚类优先级算法。 本文的内容安排如下： 第一章为绪论部分，简要介绍认知无线终端重构的概念和调度算法的发展，并 简要介绍论文的主要工作和具体的结构安排。 第二章详细介绍认知无线电系统特征，并对系统资源进行建模。随后介绍认知 无线终端重构过程和具体的重构要求。 第三章详细描述改进的动态级调度算法，此算法将改进的任务聚类算法和动态 级调度结合起来，并与性能有效任务调度算法进行对比，并给出相应的仿真结果。 第四章介绍一种聚类优先级算法，此算法主要是将改进的任务聚类算法和异构 最早结束时间算法结合起来，并与另外一种改进的异构最早结束时间算法进行对 比，给出仿真结果。 第五章是结束语，介绍认知无线终端重构算法的后续研究方向。 8 一一一坠塑垂垡鳖塑重塑笪童婆塑鏖篁鎏婴壅 - _ _ _ - i _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ l _ _ _ _ _ _ - - _ _ _ _ _ - _ - - _ - _ - _ _ _ - _ _ - _ _ - _ - 一一。 一 第二章认知无线终端系统分析 9 第二章认知无线终端系统分析 随着现代信息技术的演进，新的无线接入技术，例如通用移动通信系统 ( u n i v e r s a lm o b i l et e l e c o m m u n i c a t i o ns y s t e m ，u m t s ) 或者无线局域网络的i e e e 8 0 2 1 l 族群的引入，现存的全球移动通信系统( g l o b a ls y s t e mf o rm o b i l e c o m m u n i c a t i o n ，g s m ) ，通用分组无线业务( g e n e r a lp a c k e tr a d i os e r v i c e ，g p r s ) 的相互兼容和对于新的分化型的用户服务的增长性需求需要灵活的终端收发机解 决方法。 由于上述原因，通用处理器( g e n e r a l p u r p o s ep r o c e s s o r s ，g p p s ) ，数字信号处 理器( d i g i t a ls i g n a lp r o c e s s o r s ，d s p s ) ，现场可编程门阵列( f i l e d p r o g r a m m a b l eg a t e a r r a y s ，f p g a s ) ，微阵列，片上网络，片上多处理器系统的灵活性在特定用途可集 成电路( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ，a s i c ) 的能量效率上正在获得较好 性能。现代技术的可重构设备，包括处理器阵列，在适度的功率消耗下提供高计 算容量。这就允许了数字的和可重构的无线设备的扩展，同时减少模拟和不可重 构电路。由于认知无线终端和现有的通用异构计算平台及设备的相似性，我们可 以对认知无线终端进行建模，更好的进行重构方法的研究。 认知无线电系统的资源包括无线资源、计算资源以及应用资源等。无线资源 主要是无线频谱资源，计算资源主要包括数字电路和模拟电路的平台处理和带宽 资源，额外的计算资源是物理存储容量和电池功率。应用资源是用软件定义的用 于无线通信的信号处理模块。认知无线终端( c o g n i t i v er a d i ot e r m i n a l ，c r t ) 的 重构主要涉及计算资源和应用资源。不同的应用资源到认知计算平台的映射会引 起平台的重新配置，从一种执行模式转变为另一种执行模式【i i 】。因此，重新配置 能力就是c r t 重新配置能力，或者c r t 重构能力。 2 1 1 应用资源模型 2 1 认知无线终端系统模型 c r t 平台的计算环境主要由异构多处理器平台( 计算资源) 和软件定义的信号 处理链( 应用资源) 构成。一个应用资源是由描绘一个接收机或发射机的软件定义 处理层的特定r a t 的函数链组成。一个函数( 按照习惯也可以称为一个任务) 是 一个信号处理模块，比如一个调制器或一个均衡器。它没必要由一个整体的二进 制代码模块实现，而是作为一些进程的组合来实现。一个进程是最小的可管理单 元并且象征一个独立的二进制码。一个认知无线电信号处理链是由软件实施的认 l o 认知无线终端重构中的资源调度算法研究 知无线电收发机的一部分。它可以被理解为连续处理和传输实时数据的一组并行 进程的集合。这个处理链并不是特制的，而是可以在任何有足够计算能力的通用 平台上可执行的【1 2 l 。 应用资源模型包括函数，数据流，和阶段模型。一个应用资源由相互之间有 优先约束关系的m 个函数f = ，：，f = l ，2 ，m ) 组成。我们采用有向无环图( d i r e c t e d a c y c l i cg r a p h ，d a g ) 表示应用资源模型，并且采用一种逻辑上的编号方式：如果z 向f 发送数据，则f 1 ) 上。因此在此种阶段分层中，相同阶段中的 函数之间是彼此独立的，并没有依赖关系。图2 1 是一个有l o 个函数的d a g ，如 图所示它的阶段模型s = 1 , 2 ，2 ，2 ，2 ，2 ，3 ，3 ，3 ，4 。 m m 蹦 l 2 - - “； 2 1 2 计算资源模型 图2 1 一个有1 0 个任务的d a g 实例 一个c r t 平台代表一个移动台或基站。这些平台由多个异构处理设备， f p g a s ，d s p s ，和g p p s 组成，并且这些设备之间相互通信。例如一个f p g a 的 主要计算资源是用于并行处理的逻辑区域，当使用定义好的基准( 滤波器，f f t ) 时也可以转化为每单位时间的乘法一累加操作。图2 2 显示了一个认知无线终端异 构可重构平台设计实例【1 4 1 。 p r m p a r t i a l i c a p - i n t e r n a lc o n f i g u r a t i l em o d u l e s o na c c e s sp o r t p r r p a r t i a l l yr e c o n f i g u r a b l er e g i o n s 1 2 一 认知无线终端重构中的资源调度算法研究 s r a m - s t a t i cr a n d o ma c c e s sm e m o 拶 e m i f e x t e r n a lm e m o 巧i n t e r f a c e c n a c o m m u n i c a t i o n sn e t w o r ka r c h i t e c t u r e 图2 2 实际的c r t 平台结构 结合实际c r t 结构，本文假定异构计算系统由n 个不同类型的完全相互连接 的处理器组成，用p = p j ，j = l 。 表示。图2 3 所示为一个简化了的有3 个处 理器的计算系统。我们认为处理器的处理能力和处理器之间的传输带宽是c r t 平 台的主要计算资源。一个处理器的处理能力表现为处理一个函数的时间。函数在 处理器上的执行时间由m x n 矩阵e 表示，如下所示： e l n 、 l e l ni 1 。：l i e j 。m n m n 其中表示函数z ( 1 5 f m ) 在处理器p ，( 1 j n ) 上的估计计算时间。为了表 述明确，可将表示为e ( z ，p j ) 。一个函数在不同处理器上的执行时间是不同的， 这取决于处理器的计算能力。并且即使处理器以处理一个函数的速度比处理器p 。 快，也不能由此确定它们处理其它函数相对速度的快慢。表2 1 所示为图2 1 中的 各函数在图2 3 中的处理器上执行的时间。从表2 1 中可以看出函数在不同处理器 上的时间各有差别。 处理器之间的带宽与数据传输速率相对应，用一个n x n 矩阵r 表示，如下所 示： q n 、 l 毛n 1 i ：i l e n n n n 其中表示以和p ，之间的带宽，这里l x m ，l y n 。两个处理器之间的带 宽是双向对称的，并且链路速率与处理器网络的类型有关。 两个处理器见和p ，之问的通信代价取决于发送方见和接收方p ，的通道初始 化和在通道上的通信时间。通道初始化时间假设为是可以忽略的，因此从函数f ( 分配在处理器以) 到函数乃( 分配在处理器p ，) 的传输数据的时间勺刀由等式 ( 2 1 ) 定义： c 4 碍= d 口| ( 2 - 1 ) ! 趁； 眦 勃； 印 印劬； 刚，。l = e 2 2 眨 玩毛： km ；h ，。 = r 第二章认知无线终端系统分析 另外，当函数z 和乃分配在一个处理器上时，勺= 0 。 2 2 1 映射过程 图2 3 处理器模型 表2 1图l 中所有函数的计算时间 p lp 2p s f l 1 41 69 龟 1 31 91 8 6 l l 1 31 9 1 38 1 7 6 1 21 31 0 名 1 31 69 f ：7 71 51 1 氐 5 1 11 4 岛 1 81 22 0 r i o 2 l71 6 2 2c r t 重构过程 由于c r t 平台与通用异构计算平台的相似性，我们认为通用资源调度方法对 于c r t 系统是可用的。合适的映射和调度技术的引入对于r a t 之间的动态级切换 是至关重要的，会改变认知无线终端的设计。映射描述了将软件模块分配给硬件 资源的过程，而调度决定了这些模块的执行时间。我们将他们认为是认知无线终 端重构的两个互补的方面。 c r t 系统显示了一些详细的方面，着重考虑了灵活性和有效性，这些在异构 计算中并没有联合考虑。这些方面是：传输媒质的基于时隙的划分( 无线时隙) ， 连续的数据传输和接收，r a t 具体的服务质量( q u a l i t y - o f - s e r v i c e ，q o s ) 目标， 1 4 认知无线终端重构中的资源调度算法研究 实时计算要求和有限的计算资源，对于不同的r a t 和无线条件的不同的计算约束 和负荷，协议栈的动态重构和异构多处理器平台。 图2 4 显示了应用程序到计算平台的映射过程。其上部描述了数据通路导向的 应用程序在异构硬件平台上的映射。当考虑到可移植性和可互用性的需要时，这 个映射是一个非常关键的问题。由于在d s p ，f p g a 和g p p 组成的平台上涉及到 不同的链路接口，信号模块问题中，可重构平台的连通性和同步也是c r t 需要考 虑的问题。为了能够解决问题，c r t 假设一个硬件抽象层( h a r d w a r ea b s t r a c t i o n l a y e r ，p h a l ) 中间设备或执行环境来提供一个在异构计算平台的顶部的伪齐次 计算环境，致力于在异构平台上提供统一的服务。它管理所有处理器上同步的执 行和流水型和缓冲机制，为了能够进行合适的和及时的数据传输。 有着标准接口的部件建模在图2 4 的底部给出。这个目标导向的展示以高层次 的抽象显示了函数在处理器上分配时的重构管理。从图中可以看出，每个函数与 外部应该有四个接口：数据入，数据出，配置控制和操作控制，形象的描述了重 构过程中应用资源的映射过程。 图2 4 应用资源到计算资源的映射 为了能够更详细的说明函数在处理器平台上的执行过程，已有研究者设计出 c r t 元件适配器，进行重构过程中的细节控制。图2 5 显示了一个元件适配器，更 加具体的给出了重构的细节。图中元件给出以下接口。“定时数据入 和“定时数 据出”接口负责控制可用的数据分别来产生和消耗数据。本质上这些接口产生用 于处理函数的可用的信号。r x ( t x ) 数据接口接收数据并处理( 给出处理过的数 第二章认知无线终端系统分析 据) 。最后“定时重构”接口在重构过程中提供处理模式( 空闲，初始，运行) 和 用于维持在数据传输接口中的数据的配置信号。图中的握手信号统一对数据出入 和重构进行定时控制。 2 2 2 时隙的划分 图2 5 处理函数的具体实现 只要有数据发送或接收，在无线链路上发送或接收的数据就需要被处理。一 个应用将会通常在整个用户会话过程中执行，即使会出现没有数据发送的时期。 在一个单个用户会话过程中一个应用被另一个应用取代的事实并不会影响这种连 续的数据处理。作者提议通过把时间划分为相等的时隙和把应用划分为流水线操 作阶段，将连续的执行分解为周期性地执行。一个应用程序的流水型的执行确定， 在任何一个时隙内，所有的函数处理和传播一部分应用要处理的数据。这就意味 着，对不同数据部分的相同的处理和数据传输在每个时隙内重复进行。图2 6 表示 了这种划分。时隙的引入，提供了c r t 重构的的基本机制，并且对于满足应用程 序的最大时延要求特别有用。 基于一个可行的映射和上述假设的情况下，通常复杂的调度进程就简化为n 个独立的局部调度任务。特别的，一个处理器的局部调度器能够组织相应的函数 部分的执行顺序和它们在给定的时隙限制内的数据传递。这就保证了任何一个或 一组应用程序模块的输入数据按照它们的到达速度进行处理，因此在处理链中的 任何地方没有数据累积，满足最后期限要求。 时隙的时间长度，。乘以时隙个数。就是在每个处理器上的一个可行映射情况 下的时延。我们将，。说明为： 1 6 认知无线终端重构中的资源调度算法研究 。：l 。o ，xt s e r s ( 2 - 2 ) 以此来满足最大允许时延k 。其中s p t s 代表每时隙的秒数。这个时延是在 无线服务提供商和用户之间的依据服务和q o s 协议的一个无线通信链路的可容许 的端到端时延。时隙个数由应用程序的阶段数决定。例如u m t s 无线链路用1 0 m s 时长的帧来和它的接收方同步数据传输，因此它的时隙长度f ，。= 0 0 1 1 7 = 0 5 8 8 1 0 。3 s p t s ，其中1 7 是u m t s 应用程序的阶段数。 阶段l ； 阶段2 ； 阶段3 ； 阶段4 口嚣警徽 p i 内部 链路 外部 链路 p 2 匿圈映射到处理 器2 上的任务 一个可行的应用程序到c r t 平台的映射必须能够在一个时隙内完成，即c r t 的重构有一个最后期限。否则超过了最后期限，就无法进行c r t 的重构，进而会 导致无法在r a t 之间进行切换，导致用户会话进程的中断。因此，我们必须尽可 能的减少函数的完成时间，使重构能够正常进行。而由此可知，应用资源在计算 资源上的调度是个周期性的资源调度。在无线通信这种硬实时系统中，应用执 行不仅要在逻辑上正确，而且要能及时完成。在一个分布式实时系统中，满足任 务最后期限的能力很大程度上取决于任务分配，因此我们需要个考虑了实时要 求的任务分配算法。而端到端系统中分布式设备的响应时间显著的被任务间的通 信影响，因此提出的算法要考虑在任务分配决定做出时任务间的通信引起的延迟 和优先约束的影响1 1 5 j 。 2 3 本章小结 本章首先介绍了认知无线终端的系统特征；其次结合当前的研究现状给出了 应用资源和计算资源的模型和相对于资源调度算法的需要的先决条件；最后介绍 第二章认知无线终端系统分堑 1 7 了认知无线终端与通用异构计算平台相比在重构方面的一些细节，例如高的实时 性的要求和时隙的引入，为下一章中新的资源调度算法的提出做了理论铺垫。 第三章演进的动态级调度算法 1 9 第三章演进的动态级调度算法 3 1 引言 根据第二章中论文对c r t 系统模型的描述及现有的资源调度算法，作者提出 的算法都是以最小化终端的重构时间即应用资源的完成时间为目标的。目前并无 许多关于c r t 重构算法的研究。v u km a r o j e v i c 等人提出一种k 映射算法。t 映 射算法的目标是最小化计算资源的占用，并不考虑任务的完成时间。t w 映射算法 的资源模型和本论文第二章中描述的资源模型有一定的相似之处。应用资源模型 是d a g 图而处理器