Journal of Computer Applications ›› 2013, Vol. 33 ›› Issue (03): 862-865.DOI: 10.3724/SP.J.1087.2013.00862

• Typical applications • Previous Articles     Next Articles

Dual priority dynamic scheduling algorithm based on multi-FPGA

DU Shuangzhi1, WANG Yong2*, TAO Xiaoling3   

  1. 1.College of Electronic Engineering and Automation, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
    2.College of Computer Science and Engineering, Guilin University of Electronic Technology, Guilin Guangxi 541004, China; 3.College of Information and Communication, Guilin University of Electronic Technology, Guilin Guangxi 541004, China
  • Received:2012-08-28 Revised:2012-10-23 Online:2013-03-01 Published:2013-03-01
  • Contact: DU SHUANGZHI

基于多片FPGA的双优先级动态调度算法

杜双枝1,王勇2*,陶晓玲3   

  1. 1.桂林电子科技大学 电子工程与自动化学院,广西 桂林 541004;
    2.桂林电子科技大学 计算机科学与工程学院,广西 桂林 541004;
    3.桂林电子科技大学 信息与通信学院,广西 桂林 541004
  • 通讯作者: 杜双枝
  • 作者简介:杜双枝(1986-),女,湖北随州人,硕士研究生,主要研究方向:计算机网络流量分类; 王勇(1964-),男,四川阆中人,教授,博士,主要研究方向:计算机网络、信息安全、计算智能; 陶晓玲(1977-),女,江苏金华人,副研究员,硕士,主要研究方向:网络安全、计算智能。
  • 基金资助:

    国家自然科学基金资助项目(61163058); 广西自然科学基金资助项目(2011GXNSFB018076); 广西科学研究与技术开发计划项目(桂科攻11107006-21)。

Abstract: 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 it can also reduce miss rate of soft real-time periodic tasks caused by preemption.

Key words: parallel processing, tasks scheduling, multiple Field-Programmable Gate Array (FPGA), dual priority scheduling algorithm, relaxation degree

摘要: 针对单片现场可编程门阵列(FPGA)在处理高速网络中海量数据时存在效率低下的问题,结合多处理器的双优先级调度算法,在所构建的多片FPGA并行处理的高速数据采集和处理模型上,提出一种基于多片FPGA的双优先级动态调度算法,并对处于低优先级段的强实时周期任务提出一种最早截止期临界松弛调度(EDCL)算法。根据任务的松弛度确定任务的优先级,若提升时间到达时仍未完成,则将其提升到高优先级段; 对软实时周期任务,设置在中优先级段,通过延长当前任务截止期至动态模糊阈值进行调度。实验结果表明,该算法能很好地调度强实时周期任务,保证重要任务的优先执行,并能降低由于抢占造成的软实时周期任务错失率。

关键词: 并行处理, 任务调度, 多片现场可编程门阵列, 双优先级调度算法, 松弛度

CLC Number: