基于流水线的优先级队列排序的VLSI实现

优先级队列排序是众多队列调度算法硬件实现的主要瓶颈。文章提出了一种基于流水线的优先级队列的硬件快速排序结构。该结构具有O（1）的时间复杂度，支持上万个优先级队列，满足OC-192甚至更高网络传输速率的要求。     

Priority queue schedulers with approximate sorting inoutput-buffered switches

All recently proposed packet-scheduling algorithms for output-buffered switches that support quality-of-service (QoS) transmit packets in some priority order, e.g., according to deadlines, virtual finishing times, eligibility times, or other time stamps that are associated with a packet. Since maintaining a sorted priority queue introduces significant overhead, much emphasis on QoS scheduler design is put on methods to simplify the task of maintaining a priority queue. In this paper, we consider an approach that attempts to approximate a sorted priority queue at an output-buffered switch. The goal is to trade off less accurate sorting for lower computational overhead. Specifically, this paper presents a scheduler that approximates the sorted queue of an earliest-deadline-first (EDF) scheduler. The approximate scheduler is implemented using a set of prioritized first-in/first-out (FIFO) queues that are periodically relabeled. The scheduler can be efficiently implemented with a fixed number of pointer manipulations, thus enabling an implementation in hardware. Necessary and sufficient conditions for the worst-case delays of the scheduler with approximate sorting are presented. Numerical examples, including traces based on MPEG video, demonstrate that in realistic scenarios, scheduling with approximate sorting is a viable option     

基于逆序层优先的柔性综合调度算法

针对以往柔性综合调度算法均考虑正向调度，导致需要考虑目标工序的多紧前工序约束条件，难以合理安排相关工序进而影响产品完工时间的问题，该文提出一种基于逆序层优先的柔性综合调度算法。首先，提出逆序层优先策略，将各工序分配至逆序层待调度工序集；其次，提出动态拟长路径策略，确定各逆序层待调度工序集中工序的调度顺序；然后，分别提出设备选择策略和设备抢占策略以确定目标工序的加工设备以及加工时间；最后，提出基于完工时间翻转的调度方案转换策略，将逆序调度方案转换为正序调度方案。实例表明，和已有主流算法相比，该算法在不提高算法复杂度的前提下能够缩短产品完工时间。     

二进制堆排序算法的改进研究

基于对网络服务质量中队列调度算法的介绍和分析,从队列的优先级角度出发,对经典的二进制堆Heap调度排序算法进行了改进,提出了一种新的Heap＋算法,该算法充分利用原算法出队、入队操作数固定的特点,使其在保证硬件实现复杂度低的情况下能够做到出队、入队操作的流水化,从而达到高度的并行性。且具备很高的资源利用率和可扩展性,可用于高速链路上高精度虚拟时间的排序操作。     

Arbitrated Time-to-First Spike CMOS Image Sensor With On-Chip Histogram Equalization

This paper presents a time-to-first spike (TFS) and address event representation (AER)-based CMOS vision sensor performing image capture and on-chip histogram equalization (HE). The pixel values are read-out using an asynchronous handshaking type of read-out, while the HE processing is carried out using simple and yet robust digital timer occupying a very small silicon area (0.1times0.6 mm²). Low-power operation (10 nA per pixel) is achieved since the pixels are only allowed to switch once per frame. Once the pixel is acknowledged, it is granted access to the bus and then forced into a stand-by mode until the next frame cycle starts again. Timing errors inherent in AER-type of imagers are reduced using a number of novel techniques such as fair and fast arbitration using toggled priority (TP), higher-radix, and pipelined arbitration. A verilog simulator was developed in order to simulate the effect of timing errors encountered in AER-based imagers. A prototype chip was implemented in AMIS 0.35 mum process with a silicon area of 3.1times3.2 mm². Successful operation of the prototype is illustrated through experimental measurements     

一种基于优先级队列的集群动态反馈调度算法

在分析现有面向LVS集群的负载均衡调度算法优缺点的基础上,提出了一种新的调度算法—基于优先级队列的动态反馈调度算法。该算法根据定期采集到的各服务器负载信息动态地调整各服务器的权值,并根据权值建立优先级调度队列借以实现连接的调度。算法可保证良好的负载均衡性,且时间复杂度降低至O(1)。     

EPON中保证QoS的动态带宽分配算法

作为一种新技术，EPON系统采取在下行信道使用广播方式而在上行信道使用时分多址(TDMA)方式，为用户提供共享传输介质的接入方式，因此就需要一种接入控制机制来为用户分配带宽。为了使EPON系统更好地支持QoS并且进一步提高带宽利用率，提出了一种新的固定周期轮询动态带宽分配算法，针对不同时延特性业务采用不同的授权分配算法。算法包括两部分：OLT时ONU的调度以及ONU内部不同优先级的队列之间的调度。最后讨论了包时延、系统吞吐量等仿真结果和性能分析。     

A hierarchical fair service curve algorithm for link-sharing,real-time, and priority services

We study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with priority (decoupled delay and bandwidth allocation). We extend the service curve based quality of service (QoS) model, which defines both delay and bandwidth requirements of a class in a hierarchy, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting fair service curve (FSC) link-sharing model formalizes the goals of link-sharing, real-time and priority services and exposes the fundamental trade-offs between these goals. In particular, with decoupled delay and bandwidth allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called hierarchical fair service curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the service curves of leaf classes, thus ensures real-time and priority services, while trying to minimize the discrepancy between the actual services provided to and the services defined by the FSC link-sharing model for the interior classes. We have implemented the H-FSC scheduler in NetBSD. By performing analyzes, simulations and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation overhead     

Synthesis of pipelined DSP accelerators with dynamic scheduling

To construct complete systems on silicon, application specific DSP accelerators are needed to speed up the execution of high throughput DSP algorithms. In this paper, a methodology is presented to synthesize high throughput DSP functions into accelerator processors containing a datapath of highly pipelined, bit-parallel hardware units. Emphasis is put on the definition of a controller architecture that allows efficient run-time schedules of these DSP algorithms on such highly pipelined data paths. The methodology is illustrated by means of an image encoding filter bank     

On achieving throughput in an input-queued switch

We establish some lower bounds on the speedup required to achieve throughput for some classes of switching algorithms in a input-queued switch with virtual output queues (VOQs). We use a weak notion of throughput, which will only strengthen the results, since an algorithm that cannot achieve weak throughput cannot achieve stronger notions of throughput. We focus on priority switching algorithms, i.e., algorithms that assign priorities to VOQs and forward packets of high priority first. We show a lower bound on the speedup for two fairly general classes of priority switching algorithms: input priority switching algorithms and output priority switching algorithms. An input priority scheme prioritizes the VOQs based on the state of the input queues, while an output priority scheme prioritizes the VOQs based on their output ports. We first show that, for output priority switching algorithms, a speedup S/spl ges/2 is required to achieve weak throughput. From this, we deduce that both maximal and maximum size matching switching algorithms do not imply weak throughput unless S/spl ges/2. The bound of S/spl ges/2 is tight in all cases above, based on a result in Dai et al. Finally, we show that a speedup S/spl ges/3/2 is required for the class of input priority switching algorithms to achieve weak throughput.     

Underload instabilities in packet networks with flow schedulers

Instability in packet-switching networks is normally associated with overload conditions, since queueing network models show that, in simple configurations, only overload generates instability. However, some results showing that instability can happen also in underloaded queueing networks began to appear about a decade ago. Underload instabilities can be produced by: 1) customer routes that visit the same queues several times; 2) variations of the customer service times at the different queues; and 3) complex scheduling algorithms. We study, using fluid models and adversarial queueing theory, possible underload instabilities due to flow schedulers in packet networks, focusing on output queued switches with strict priority (SP) schedulers and Generalized Processor Sharing (GPS) schedulers. The considered scenarios always refer to acyclic packet routes and consider customer service times that vary only according to channel capacities, thus resembling the approaches being currently considered to provide QoS in the Internet. Our (in)stability results are rather surprising: SP schedulers appear to be more robust than GPS schedulers whenever exact information on the effective average packet flow rates is not available.     

车联网中交通安全消息动态优先调度机制

车联网中两类交通安全消息共享有限控制信道带宽,在消息突发状态下无法保证事件触发消息的传播性能,导致预警失效.基于差异化的消息传播性能需求提出了一种动态优先级区分的调度机制,按事件优先级分别进行队列管理,赋予事件触发消息优先权,通过设置优先级调度阈值实现对事件触发消息的动态调度.当优先队列长度高于阈值时,其抢占调度时隙.当队列长度低于阈值一半,退出抢占过程,恢复非抢占优先调度方法.仿真显示,所提调度机制能够减小事件触发消息的端到端时延约1.3 ms,提高周期性消息的公平性约0.22.     

An on-demanded data broadcasting scheduling considering the data item size

Compared with conventional data broadcasting, on-demand data broadcasting is adaptive and real-time, which can better reflect the actual needs of mobile users. Current researches do not consider the attribute of data item size, and the constantly changing characteristics of data item size in on-demand data broadcasting is non-ignorable. This paper introduces the split strategies and backpacks theories into on-demand data broadcasting scheduling to deal with the inconsistencies of data item size, and proposes two scheduling models under different split strategies: (1) equal split scheduling model ES-LxRxW, which proposes the equal splitting strategy (ES) and a deadline adjust strategy. (2) Unequal split scheduling model US-LxRxW, which proposes the unequal split strategy (US) and two effective scheduling algorithms priority first (PF) and propriety and bandwidth first (PxBF). Extensive experiments shows that ES-LxRxW and US-LxRxW can both improve bandwidth utilization and dynamically adjust to the real-time situation of data item size, which takes into account data item size, bandwidth, cycle and scheduling priority of data item. The two proposed scheduling models could reach or outperform the other state-of-the-art scheduling algorithms without considering data item size in the performance of request drop ratio. US-LxRxW can also better reflect the real-time changes of data items than ES-LxRxW, and the proposed PF and PxBF algorithms can effectively improve the bandwidth utilization and reduce the split times.

     

Randomized scheduling algorithms for high-aggregate bandwidth switches

The aggregate bandwidth of a switch is its port count multiplied by its operating line rate. We consider switches with high-aggregate bandwidths; for example, a 30-port switch operating at 40 Gb/s or a 1000-port switch operating at 1 Gb/s. Designing high-performance schedulers for such switches with input queues is a challenging problem for the following reasons: (1) high performance requires finding good matchings; (2) good matchings take time to find; and (3) in high-aggregate bandwidth switches there is either too little time (due to high line rates) or there is too much work to do (due to a high port count). We exploit the following features of the switching problem to devise simple-to-implement, high-performance schedulers for high-aggregate bandwidth switches: (1) the state of the switch (carried in the lengths of its queues) changes slowly with time, implying that heavy matchings will likely stay heavy over a period of time and (2) observing arriving packets will convey useful information about the state of the switch. The above features are exploited using hardware parallelism and randomization to yield three scheduling algorithms - APSARA, LAURA, and SERENA. These algorithms are shown to achieve 100% throughput and simulations show that their delay performance is quite close to that of the maximum weight matching, even when the traffic is correlated. We also consider the stability property of these algorithms under generic admissible traffic using the fluid-model technique. The main contribution of this paper is a suite of simple to implement, high-performance scheduling algorithms for input-queued switches. We exploit a novel operation, called MERGE, which combines the edges of two matchings to produce a heavier match, and study of the properties of this operation via simulations and theory. The stability proof of the randomized algorithms we present involves a derandomization procedure and uses methods which may have wider applicability.     

Implementing scheduling algorithms in high-speed networks

The fluid generalized processor sharing (GPS) algorithm has desirable properties for integrated services networks and many packet fair queueing (PFQ) algorithms have been proposed to approximate GPS. However, there have been few high-speed implementations of PFQ algorithms that can support a large number of sessions with diverse rate requirements and at the same time maintain all the important properties of GPS. The implementation cost of a PFQ algorithm is determined by: (1) computation of the system virtual time function; (2) maintenance of the relative ordering of the packets via their timestamps (scheduling); and (3) regulation of packets based on eligibility time, in some algorithms. While most of the recently proposed PFQ algorithms reduce the complexity of computing the system virtual time function, the complexity of scheduling and traffic regulation is still a function of the number of active sessions. In addition, while reducing the algorithmic or asymptotic complexity has been the focus of most analysis, it is also important to reduce the complexity of basic operations in order for the algorithm to run at high speed. We develop techniques to reduce both types of complexities for networks of both fixed and variable size packets. Regulation and scheduling are implemented in an integrated architecture that can be viewed as logically performing sorting in two dimensions simultaneously. By using a novel grouping architecture, we are able to perform this with an algorithmic complexity independent of the number of sessions in the system at the cost of a small controllable amount of relative error. To reduce the cost of basic operations, we propose a hardware-implementation framework and several novel techniques that reduce the on-chip memory size, off-chip memory bandwidth, and off-chip access latency. The proposed implementation techniques have been incorporated into commercial ATM switch and IP router products     

Benes switching fabrics with O(N)-complexity internal backpressure

Multistage buffered switching fabrics are the most efficient method for scaling packet switches to very large numbers of ports. The Benes network is the lowest-cost switching fabric known to yield operation free of internal blocking. Backpressure inside a switching fabric can limit the use of expensive off-chip buffer memory to just virtual-output queues in front of the input stage. This article extends the known credit-based flow control (backpressure) architectures to the Benes network. To achieve this, we had to successfully combine per-flow backpressure, multipath routing (inverse multiplexing), and cell resequencing. We present a flow merging scheme that is needed to bring the cost of backpressure down to O(N) per switching element, and for which we have proved freedom from deadlock for a wide class of multipath cell distribution algorithms. Using a cell-time-accurate simulator, we verify operation free of internal blocking, evaluate various cell distribution and resequencing methods, compare performance to that of ideal output queuing, the iSLIP crossbar scheduling algorithm, and adaptive and randomized routing, and show that the delay of well-behaved flows remains unaffected by the presence of congested traffic to oversubscribed output ports.     

Approximate analysis of coupled queueing in ATM networks

We discuss a scheduling discipline for multiclass traffic in asynchronous transfer mode network nodes. The scheduler provides minimum bandwidth guarantees for each class of traffic and is well suited for high-speed implementation. The scheme is a modification of static head-of-line priority queueing, and was originally presented in a slightly different form by Huang and Wu (1993). We begin by considering a system with two queues which is analyzed by decoupling the system into separate M/G/1 queues. The analysis provides a very good estimate for the mean response time of customers in each queue. We also demonstrate the applicability of the analysis to a system with n⩾2 queues     

Improving DL-MU-MIMO performance in IEEE 802.11ac networks through decoupled scheduling

The IEEE 802.11ac standard introduces new downlink multi-user MIMO (DL-MU-MIMO) transmissions to up to four users in order to increase spatial reuse in wireless local area networks (WLANs). We argue that even better WLAN performance can be achieved by slightly modifying the DL-MU-MIMO scheduling. To this end we propose a new queuing mechanism based on the decoupling of EDCA and DL-MU-MIMO scheduling (DEMS) to avoid head-of-line blocking. We show that DEMS outperforms traditional 802.11ac scheduling based on first in, first out transmission queues. The improvement is shown in terms throughput achieved with: (a) more efficient channel usage, (b) increased probability of transmission of high priority traffic, and (c) decreased competition between frames destined to distinct users.

     

The iSLIP scheduling algorithm for input-queued switches

An increasing number of high performance internetworking protocol routers, LAN and asynchronous transfer mode (ATM) switches use a switched backplane based on a crossbar switch. Most often, these systems use input queues to hold packets waiting to traverse the switching fabric. It is well known that if simple first in first out (FIFO) input queues are used to hold packets then, even under benign conditions, head-of-line (HOL) blocking limits the achievable bandwidth to approximately 58.6% of the maximum. HOL blocking can be overcome by the use of virtual output queueing, which is described in this paper. A scheduling algorithm is used to configure the crossbar switch, deciding the order in which packets will be served. Previous results have shown that with a suitable scheduling algorithm, 100% throughput can be achieved. In this paper, we present a scheduling algorithm called iSLIP. An iterative, round-robin algorithm, iSLIP can achieve 100% throughput for uniform traffic, yet is simple to implement in hardware. Iterative and noniterative versions of the algorithms are presented, along with modified versions for prioritized traffic. Simulation results are presented to indicate the performance of iSLIP under benign and bursty traffic conditions. Prototype and commercial implementations of iSLIP exist in systems with aggregate bandwidths ranging from 50 to 500 Gb/s. When the traffic is nonuniform, iSLIP quickly adapts to a fair scheduling policy that is guaranteed never to starve an input queue. Finally, we describe the implementation complexity of iSLIP. Based on a two-dimensional (2-D) array of priority encoders, single-chip schedulers have been built supporting up to 32 ports, and making approximately 100 million scheduling decisions per second