杜双枝;王勇;陶晓玲网上订书
【摘 要】When single Field-Programmable Gate Array (FPGA) deals with the huge amounts of data in high-speed network, low efficiency problem occurs. According to dual priority schedule algorithm for multi-processor and high-speed data acquisition and processing model based on multi-FPGA, a dual priority dynamic scheduling algorithm was proposed based on multi-FPGA. For strong real-time periodic tasks set in low priority queue, the Earliest Deadline Critical Laxity ( EDCL) scheduling algorithm was given to determine the priority of task according to the degree of relaxation of the tasks. If the task was not finished when the promotion time was up, it would be promoted to high priority queue. For soft real-time periodic tasks, an algorithm was put forward to assign the tasks to middle priority queue and schedule them by delaying the deadline of tasks to dynamic blur threshold. The experimental results show that the proposed algorithms can well schedule strong real-time periodic tasks and guarantee the priority execution of important tasks, and i
t can also reduce miss rate of soft real-time periodic tasks caused by preemption.%针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法.根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段；对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度.实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率. 【期刊名称】《计算机应用》
【年(卷),期】2013(033)003
dots【总页数】4页(P862-865)
【关键词】并行处理;任务调度;多片现场可编程门阵列;双优先级调度算法;松弛度
【作 者】杜双枝;王勇;陶晓玲
【作者单位】桂林电子科技大学电子工程与自动化学院,广西桂林541004;桂林电子科技大学计算机科学与工程学院,广西桂林541004;桂林电子科技大学信息与通信学院,广西桂林541004
【正文语种】中 文
【中图分类】TP393.08
0 引言
随着计算机网络技术的发展和互联网规模的扩大，保障网络的可靠运行变得越来越重要。为了实现对网络安全的有效监控，必须及时处理网络中的海量流量信息。而现场可编程门阵列(Field-Programmable Gate Array，FPGA)由于其高度的并行性，可使数据分析、处理、替换等并行进行，因此被广泛地应用于高速数据采集系统中［1－5］。但单片FPGA由于芯片资源的限制往往不足以胜任全部系统功能，即使可以胜任，在开发一块高密度FPGA时，很可能面临模块分割、综合布线、系统维护等方面的困难，从而导致开发效率下降。根据一定的耦合关系使用多片FPGA构建一个大规模处理器是解决这个问题的有效方法。
在高速数据采集系统中，为了快速处理海量的数据包，可以采用多片FPGA级联的结构并行处理流量数据。一个合理的任务调度算法，应使多片FPGA处理效率最高，任务执行时间最短。虽然多片FPGA的任务调度问题报道不多，但是多处理器的任务调度算法一直是个重要的研究课题，调度算法层出不穷［6－11］。
多处理器调度中的双优先级算法与EDF(Earliest Deadline First)、ESF(Earliest Start time First)、MPF(Minimum Processor time First)、MLF(Minimum Laxity First)等复杂算法相比，它是将全局调度和局部调度相结合，具有开销小、性能高、实现简单的优点，比较适合处理实时调度问题。其最早在1993年由Burns和Wellings提出并应用于实时系统的任务调度，以充分利用处理器的容量;1995年Davis和Wellings利用双优先级算法调度软实时和强实时任务，在保证强实时任务满足时限的情况下，调度软实时任务。Banus等［12］又将双优先级算法应用在多核处理器系统中，提出基于多核处理器系统的强实时周期任务和非周期任务的混合调度算法;刘怀等［13］将双优先级算法进行改进，使之可以在单核上调度强实时周期性任务、软实时周期性任务和非周期性任务;朱俊超［14］在文献［13］的基础上改进双优先级算法，使之可以在多处理器系统中调度强实时周期性任务和软实时周期性任务。
由于多片FPGA与多处理器的任务调度问题类似，因此本文借鉴多处理器双优先级调度算法，针对采用多片FPGA级联并行处理海量数据包的任务调度问题，提出一种基于多片FPGA的双优先级动态调度算法，并对强实时周期任务的优先级判定方法加以改进。
谢冰莹
1 基于多片FPGA的双优先级任务调度模型
1.1 多片FPGA并行高速数据处理模型
现有的高速数据采集和处理系统大多是以单片FPGA为控制核心实现的，本文实现的系统是以单片FPGA为核心，多片FPGA级联并行处理数据包。首先，硬件电路从千兆以太网口捕获的网络数据包经过RJ45接口通过A/D转换电路进入到网络接口模块;然后网络接口模块与FPGA处理模块中的千兆以太网IP核通过标准的SGMII接口连接，实现网络数据包的采集;最后，采集到的网络数据包由FPGA处理模块根据CAM内容寻址存储器的用户规则进行相应的分析处理后，根据各个FPGA上的负载情况，采取适当的调度策略和负载均衡策略，将任务分配到各片FPGA上，以使系统完成时间最短，资源利用率最高。其模型如图1所示。
图1 多片FPGA并行高速数据处理模型
多片FPGA任务调度是将n个任务分配到m片FPGA上，每个任务可以分配到任意一片FPGA上执行。其可调度性判断依据为:
对于单片FPGA:
对于m片FPGA:
其中:U和U′表示系统总利用率，Ci为周期任务的最坏执行时间，Pi为任务的周期。只有满足式(1)和式(2)的条件，才可能处理所有负载。
北京饭店二期1.2 双优先级任务调度模型
太极十二拍定义1 强实时周期任务。必须在规定的时间内完成，不允许错失截止期限的任务。如果出现超出错失截止期限的强实时任务，则会对系统造成不可估量的损失。
定义2 软实时周期任务。通常允许任务错失截止期限，错失截止期限后的计算结果仍然有一定的意义，但其意义随着超时时间的增加而下降。
定义3 最坏执行时间。任务在最坏情况下无中断地执行所需的处理器时间。
定义4 任务周期。周期任务两次执行的时间间隔。
定义5 截止期。指一个时刻t，在此时刻t之前要求实时任务完成它的执行。
定义6 强实时周期任务优先级提升时间。指强实时周期任务实例的优先级从低优先级提升到高优先级的时间。
据此，本文对强实时周期任务和软实时周期任务作如下形式化描述:
强实时周期任务集表示为 Sh={τh1，τh2，…，τhn}(n ≥1)，每个强实时周期任务 τhi描述为 τhi= 〈Chi，Thi，Dhi，Phi〉(i=1，2，…，n)，其中 Chi、Thi、Dhi、Phi分别表示任务 τhi的最坏执行时间、任务周期、截止期和优先级提升时间。
软实时周期任务集表示为 Ss={τs1，τs2，…，τsn}(n ≥1)，每个软实时周期任务 τsi描述为 τsi=〈Csi，Tsi，Dsi〉(i=1，2，…，n)，其中 Csi、Tsi、Dsi分别表示任务 τsi最坏执行时间、任务周期和截止期。沈阳航空航天大学学报
根据多核多任务调度模型，把双优先级调度算法应用到多片FPGA调度中，提出基于多片FPGA的双优先级算法的任务调度模型如图2所示。
图2 基于多片FPGA的双优先级任务调度模型
如图2所示，本文采用集中式调度，初始时，把强实时周期任务放到低优先级段(Low Priority Queue，LPQ)，经过各个任务优先级提升后，占有高优先级段(High Priority Queue，HPQ);软实时周期任务放入到中优先级段(Middle Priority Queue，MPQ)中。各片FPGA上也有各自的优先级队列。
1.3 强实时周期任务优先级判定及调度算法改进
定义7 剩余执行时间。任务完成时刻与当前时刻之间的差值。
定义8 松弛度。从当前时刻直到其截止期的时间与其剩余执行时间之间的差。
基于多处理器的双优先级算法中，直接将单处理器的单调速率调度(Rate-Monotonic Scheduling，RMS)算法应用到多处理器环境中，此时的RMS算法已不是最优算法，因此本文提出一种最早截止期临界松弛调度(Earliest Deadline Critical Laxity，EDCL)算法调度处于低优先级段中的强实时周期任务。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议