一种基于输入缓冲交叉开关的调度算法

研究了交叉(Crossbar)开关的架构和缓冲策略。在已有的循环优先级多次匹配(RRM)算法和指针滑动多次迭代循环优先级匹配(iSLIP)算法的基础上提出了一种基于优先级列表的轮询调度(PB-RRM2)算法,该算法每次迭代只需要2步,减少了算法的调度时间,提高了Crossbar开关的运行速度。同时采用优先级列表的轮询(Round Robin)指针修改方式消除了指针的同步,提高了吞吐量。理论分析和仿真试验表明,算法在吞吐量和平均信元时延方面与iSLIP算法相当。     

1553B网络BC的SPN建模与分析

针对1553B网络中BC节点采用不同的实时任务调度算法将影响轮询总线表实时任务实施次数,进而影响到总线网络的吞吐量和数据传输时延,为研究实时任务调度算法对1553B总线网络通信的影响,建立了BC节点采用静态调度算法下的任务集SPN模型,模型分析结果表明固定优先级高的任务使轮询总线表任务不能实时执行,容易被阻塞,影响了总线网络的通信效果,因此BC节点适宜采用动态调度算法。     

基于自适应调度间隔的雷达事件调度算法

针对雷达事件调度中基于固定调度间隔进行调度时雷达资源利用率不高、调度成功率较低的问题,提出一种基于自适应调度间隔的调度算法：设置一时间指针,调取该指针下所有可执行事件,依次计算这些事件收益并选取收益最高事件执行;递推该指针直至该调度间隔内无法执行任何事件;提前结束该调度间隔并将该间隔剩余资源“传递”至下一调度间隔;重复上述步骤直至调度完结。仿真实验表明,与基于固定调度间隔的调度算法相比,基于自适应调度间隔的调度算法能够有效减少“时间碎片”的形成,提高实现价值率与时间利用率。     

高速交换矩阵调度器的FPGA设计

提出了一种并行迭代算法调度器的可编程逻辑门阵列(FPGA)的实现方法。调度器主要由仲裁器和有限状态机2部分组成,采用温度型可编程优先编码器的设计方法,大大降低了仲裁器输入输出的时延,提高了调度器的工作速度;同时,采用流水线设计进一步减少了每次调度需要的时钟周期数,有效地解决了输入端口和输出端口的阻塞。设计方法可以用于目前所有基于RR指针的三步迭代算法的设计。     

孔径分割多功能雷达的任务调度研究

针对孔径分割多功能雷达实时任务调度中资源利用不充分的问题,提出了一种基于扩展域的任务自适应调度方法。方法以时间指针为对象,对该时刻的任务分析范围从当前调度间隔扩展到整个调度时间轴,从整个调度时间轴上所有满足时间指针处执行条件的任务中,选择一个优先级最高的任务,可实现任务间的紧密安排,有效减少空闲资源的浪费,使得孔径分割雷达能够在有限的资源内调度执行更多的任务。最后,将该方法与传统多任务并行调度方法进行对比仿真,仿真结果证明了该方法的有效性和优越性。     

战术局域网TDMA动态优先级轮询调度算法研究

主要针对战术局域网动态时隙分配的优先级轮询调度算法进行了研究。传统的战术局域网集中式轮询算法不能很好地满足节点报文传输的动态时隙需求。为此,文章提出了一种动态时隙分配的优先级轮询调度算法。     

LTE系统级仿真的关键技术与研究

以3GPP在技术规范中对LTE系统仿真所提要求为标准,对LTE系统级仿真的整体流程与基本框架进行了概括与分析,介绍了链路级映射的2种方法,在分析各功能模块的基础上搭建了系统级仿真平台,实现了LTE的系统级仿真。以下行调度算法为对象,通过系统级仿真平台对轮询、最大载干比和比例公平这3种经典分组调度算法进行了仿真与分析,为LTE系统级仿真平台的进一步完善和发展提供了理论参考。     

码分多址反向链路调度算法与处理时延的关系

研究了码分多址反向链路数据传输采用不同的调度算法受系统处理时延影响的程度，这种影响与信道估计误差有关，也与传输速率的更新时间有关。通过对CDMA2000的动态系统级仿真，其结果显示反向链路上的最大速率与轮询结合的算法、最小路径损耗算法、以及轮询算法在有处理时延时吞吐量性能都会降低，其中最大速率与轮询结合的算法降低的程度最小，轮询算法降低程度最大，最小路径损耗算法介于中间。性能降低也与快衰信道类型相关，信道变化越快算法性能受到的影响越大。提出了一种对调度算法的改进方法，即根据移动台处理时延的变化，为近期处理时延较小的移动台分配更多的资源，结果表明该方法改善了系统吞吐量。     

支持优先级与公平策略的队列规程

首先介绍了队列调度算法在流量控制中的关键地位,然后讨论了现有队列调度算法,如基于优先级的调度算法、轮询调度算法与公平队列调度算法,最后提出了一种新的队列规程,该队列规程融合了优先级调度算法与DRR调度算法。在网络正常情况下,不同业务流公平地共享网络带宽,在网络出现拥塞的情况下,高优先级业务流能够抢占带宽,保证其较低的丢包率,并能够实现两种调度算法的快速切换。     

多输出队列网络的轮询权重自适应调度算法

队列调度对于网络QoS至关重要。常见的多队列轮询调度算法对不同的输出队列设置不同的固定权值,这类算法在一定程度上能改善队列调度的公平性,但对于网络数据类型和流量变化较大的场合适应性较差。本文提出一种队列轮询权重自适应的方法,能较好的满足不同类型数据分组的QoS需求。     

分布式传感器调度模型与自适应概率粒子群优化算法

不同体制的多个传感器通常部署于不同位置,据此采用分布式计算思想研究其调度问题.设计了传感器指控模块和传感器模块,探讨两者间的信息交互过程,给出基于最小调度时间间隔的传感器探测任务分解方法,建立传感器探测目标的匹配度计算模型.针对调度方案生成子模块设计了一种自适应概率粒子群算法,算法中粒子的分量根据方案适应值大小以不同的概率取相应值,体现粒子在迭代过程中的思考.实例分析表明,该算法能在迭代前期较快地收敛到一个较优值,这一特点使得在迭代次数有限的情况下,算法仍可获得较好的调度方案,满足调度方案实时高效的要求.     

Cooperative scheduling and its application to steelmaking processes

A cooperative approach to scheduling problems is proposed, and its application to creating daily schedules for steelmaking processes is described. In cooperative scheduling, procedures, rules, and the user cooperate to make a feasible schedule efficiently. The procedures, collectively called a scheduling engine, work as a local constraint satisfier to solve general primitive constraints. Rules that represent domain-dependent knowledge then solve the domain-specific constraints by means of a pattern-matching function. The user evaluates the schedule and modifies it by means of a user-friendly interface with direct-manipulation functions. The user interaction is therefore included in the system architecture as a global constraint satisfier. The iteration of this cycle improves the schedule until it becomes feasible. Experimental results obtained with Scheplan, the scheduling environment that applies this approach to scheduling steelmaking processes, show that the daily scheduling time is much less than in manual scheduling and the quality of the schedule is much improved     

Queueing analysis of scheduling policies in copy networks ofspace-based multicast packet switches

Space-based multicast switches use copy networks to generate the copies requested by the input packets. In this paper our interest is in the multicast switch proposed by Lee (1988). The order in which the copy requests of the input ports are served is determined by the copy scheduling policy and this plays a major part in defining the performance characteristics of a multicast switch. In any slot, the sum of the number of copies requested by the active inputs of the copy network may exceed the number of output ports and some of the copy requests may need to be dropped or buffered. We first propose an exact model to calculate the overflow probabilities in an unbuffered Lee's copy network. Our exact results improve upon the Chernoff bounds on the overflow probability given by Lee by a factor of more than 10. Next, we consider buffered inputs and propose queueing models for the copy network for three scheduling policies: cyclic service of the input ports with and without fanout splitting of copy requests and acyclic service without fanout splitting. These queueing models obtain the average delay experienced by the copy requests. We also obtain the sustainable throughput of a copy network, the maximum load that can be applied to all the input ports without causing an unstable queue at any of the inputs, for the scheduling policies mentioned above     

Priority-based grant-aware scheduling for low-latency switching

This paper introduces new scheduling algorithms supporting low-latency switching. The proposed grant-aware (GA) algorithm improves the average delay performance by using the grant information of previous iteration. The simulation result shows that the average delay of GA algorithm is about one-tenth of the existing algorithm in high-load condition. We also introduce two priority-based scheduling algorithms grant-aware and priority-aware (GAPA) algorithm and cyclic scheduling with the longest-queue-first (C-LQF) algorithm. In the priority-based scheduling, the scheduling priority of VoQ is determined based on its queue size. GAPA and C-LQF consider the priority only after the first iteration to prevent the starvation problem. The simulation result shows that GAPA and C-LQF scheduling achieves better performance than GA in terms of average delay, maximum delay, and hotspot throughput.     

A pipeline-based approach for maximal-sized matching scheduling ininput-buffered switches

This letter proposes an innovative pipeline-based maximal-sized matching scheduling approach, called PMM, for input-buffered switches. It dramatically relaxes the timing constraint for arbitration with a maximal matching scheme. In the PMM approach, arbitration operates in a pipelined manner. Each subscheduler is allowed to take more than one time slot for its matching. Every time slot, one of them provides the matching result. The subscheduler can adopt a pre-existing efficient round-robin-based maximal matching algorithm. We show that PMM provides 100% throughput under uniform traffic since it preserves a desynchronization effect of the round-robin pointers as in the preexisting algorithm. In addition, PMM maintains fairness for best-effort traffic due to the round-robin-based arbitration     

Degree-sequenced matching algorithms for input-queued switches

This paper presents a class of algorithms for scheduling packets in input-queued switches. As opposed to previously known algorithms that focus only on achieving high throughput, these algorithms seek to achieve low average delay without compromising the throughput achieved. Packet scheduling in input-queued switches based on the virtual-output-queued architecture is a bipartite graph matching problem wherein ports are represented by vertices and the traffic flows by the edges. The set of matched edges determine the packets that are to be transferred from the input ports to the output ports. Current matching algorithms implicitly prioritize high-degree vertices, i.e., ports with a large number of flows, causing longer delays at ports with a smaller number of flows. Motivated by this observation, we present three matching algorithms based on explicitly prioritizing low-degree vertices and the edges through them. Using both real gateway traffic traces as well as synthetically generated traffic, we present simulation results showing that this class of algorithms achieves a low average delay as compared to other scheduling algorithms of equivalent complexity while still achieving similar throughput. We also show that these algorithms determine the maximum size matching in almost all cases.     

基于任务生灭过程模型的边缘计算批处理调度算法分析与设计

移动边缘计算技术为低时延要求、资源敏感的计算任务需求提供解决方案,通过研究任务请求特征以提高调度算法效率是边缘计算的重要研究方向。不同于现有研究将任务请求特征建模为单一随机变量的做法,提出基于任务请求生灭过程模型的边缘计算架构,将求解最优调度决策的过程建模为无限期平均成本马尔可夫决策过程。在使用贝尔曼方程分析问题的过程中,利用任务的生灭特性对未来的请求到达做出估计以判断当前决策对未来系统时延能耗成本的影响,进而辅助确定当前状态的最优决策,并结合任务相关性感知提出批处理任务调度控制算法。所提算法根据生灭状态信息对策略迭代的状态空间和决策空间进行剪枝以降低策略改进的复杂度,突破了策略迭代算法的复杂度瓶颈。仿真结果表明,所提算法相较于传统的策略迭代算法具有明显的低复杂度优势,且能在不同系统条件下保持低时延、能耗成本。     

Packet-mode scheduling in input-queued cell-based switches

We consider input-queued switch architectures dealing at their interfaces with variable-size packets, but internally operating on fixed-size cells. Packets are segmented into cells at input ports, transferred through the switching fabric, and reassembled at output ports. Cell transfers are controlled by a scheduling algorithm, which operates in packet-mode: all cells belonging to the same packet are transferred from inputs to outputs without interruption. We prove that input-queued switches using packet-mode scheduling can achieve 100% throughput, and we show by simulation that, depending on the packet size distribution, packet-mode scheduling may provide advantages over cell-mode scheduling.     

基于云进化算法的3D NoC测试端口优化选择

针对于三维片上网络测试时,如何选择测试端口以提高测试效率的难题,采用基于云模型的进化算法对三维片上网络测试端口进行位置寻优,并对IP核的测试数据进行合理分配,在测试功耗约束条件下,以重用片上网络作为测试访问机制,基于XYZ路由算法和非抢占式测试调度方式,对三维片上网络IP核实施并行测试,以提高测试效率。研究结果表明,该方法可对测试端口的位置及组合方案进行精确寻优,且有效减少了测试时间。     

Fast scheduling algorithm for input and output buffered ATM switchwith multiple switching planes

A new scheduling method is presented, two-dimensional round-robin scheduling with multiple selections (2DRRMS), for an input and output buffered ATM switch. In the switch, both input and output ports are divided into several groups and multiple switching planes are used. In the 2DRRMS method the multiple cells for transfer to an input buffer module are selected and the switching planes which the selected cells are to use in the transmission are concurrently determined