检索结果-内蒙古大学图书馆

Low-Complexity Switch scheduling algorithms: Delay Optimality in Heavy Traffic

IEEE-ACM TRANSACTIONS ON NETWORKING 2022年第1期30卷 464-473页

作者： Jhunjhunwala, Prakirt Raj Maguluri, Siva Theja Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn ISyE Atlanta GA 30332 USA

Motivated by applications in data center networks, in this paper, we study the problem of scheduling in an input queued switch. While throughput maximizing algorithms in a switch are well-understood, delay analysis was developed only recently. It was recently shown that the well-known MaxWeight algorithm achieves optimal scaling of mean queue lengths in steady state in the heavy-traffic regime, and is within a factor less than 2 of a universal lower bound. However, MaxWeight is not used in practice because of its high time complexity. In this paper, we study several low complexity algorithms and show that their heavy-traffic performance is identical to that of MaxWeight. We first present a negative result that picking a random schedule does not have optimal heavy-traffic scaling of queue lengths even under uniform traffic. We then show that if one picks the best among two matchings or modifies a random matching even a little, using the so-called flip operation, it leads to MaxWeight like heavy-traffic performance under uniform traffic. We then focus on the case of non-uniform traffic and show that a large class of low time complexity algorithms have the same heavy-traffic performance as MaxWeight, as long as it is ensured that a MaxWeight matching is picked often enough. We also briefly discuss the performance of these algorithms in the large scale heavy-traffic regime when the size of the switch increases simultaneously with the load. Finally, we perform empirical study on a new algorithm to compare its performance with some existing algorithms.

关键词： Switches Throughput Schedules Job shop scheduling Complexity theory Delays scheduling algorithms Data centers MaxWeight scheduling state space collapse power-of-d bipartite matching

来源：评论

学校读者我要写书评

暂无评论

Efficient routing and centralized scheduling algorithms for IEEE 802.16 Mesh Networks

引用

INTERNATIONAL JOURNAL OF NETWORK MANAGEMENT 2011年第6期21卷 494-512页

作者： Lo, Shou-Chih Ou, Lyu-Chen Natl Dong Hwa Univ Dept Comp Sci & Informat Engn Shoufeng 974 Haulien Taiwan

An IEEE 802.16 wireless system can provide broadband wireless access to subscriber stations and operate in mesh mode. The communication between a subscriber station and a base station can pass through one or more intermediate subscriber stations. The IEEE 802.16 standard provides a centralized scheduling mechanism that supports contention-free and resource-guarantee transmission services in mesh mode. However, the corresponding algorithm to this schedule is quite primitive in the standard. In this paper, we propose a more efficient way to realize this schedule by maximizing channel utilization. Our designs are divided into two phases: routing and scheduling. First, a routing tree topology is constructed from a given mesh topology by our proposed tree construction algorithm. Secondly, we allocate channel resources to the edges in the routing tree by our proposed scheduling algorithm. To further support the quality-of-service schedule, we extend our designs by addressing some issues such as service class, admission control and fairness. Simulation results show the superiority of our proposed algorithms over others. Copyright (C) 2011 John Wiley & Sons, Ltd.

关键词： scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

An Analytical Review and Performance Measures of State-of-Art scheduling algorithms in Heterogenous Computing Enviornment

引用

ARCHIVES OF COMPUTATIONAL METHODS IN ENGINEERING 2024年第5期31卷 3091-3113页

作者： Ahmad, Wakar Gautam, Gaurav Alam, Bashir Bhati, Bhoopesh Singh Indian Inst Informat Technol Dept Comp Sci & Engn Sonepat 131001 India Fac Engn & Technol Dept Comp Engn Jamia Millia Islamia New Delhi 110025 India

Task scheduling and resource utilization have always been among the most critical issues for high performance in heterogeneous computing. The heterogeneity of computation costs on a given set of computing elements and the communication costs among computing elements increase the complexity of the scheduling problem. Extensive research proves that the list-based task scheduling algorithms generate the most efficient schedules for complex workflow applications in the heterogeneous computing environment. The workflow applications comprise thousands of interconnected tasks with dependencies. In the last decades, various list-based scheduling algorithms have been proposed to achieve some kinds of performance objectives such as minimization of makespan and energy consumption and maximization of resource utilization and reliability. In this article, various list-based workflow scheduling algorithms have been reviewed from the last two decades with the assumption of heterogeneous computing systems being used as the underlying computing infrastructure. This review process categorizes the algorithms based on scheduling objectives. For a better analysis of the algorithms, each algorithm is compared with other algorithms based on its objectives, merits, comparison metrics, workload type, experimental scale, experimental environment, and results compared. Finally, experimental analysis of seven state-of-art algorithms has been conducted on randomly generated workflow to understand the working of list-scheduling algorithms. The main purpose of this article is to give proper direction to new researchers who are willing to work in workflow scheduling in heterogeneous computing environments.

关键词： scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamic Order-Based scheduling algorithms for Automated Retrieval System in Smart Warehouses

引用

IEEE ACCESS 2021年 9卷 158340-158352页

作者： Liu, Jialei Liew, Soung-Yue Ooi, Boon Yaik Qin, Donghong Univ Tunku Abdul Rahman Fac Informat & Commun Technol Kampar Malaysia Guangxi Univ Nationalities Fac Artificial Intelligence Nanning 530000 Peoples R China

In typical e-commerce warehouse operations, upon receiving the orders from customers, the purchased items need to be retrieved from shelves and then packaged accordingly for delivery. To automate and speed up the item retrieval process, a Smart Warehouse usually employs a management system, called the Automated Retrieval System (ARS), to control and schedule the retrieval jobs. The working principle of ARS is crucial to the Smart Warehouse because it will have a great impact on the subsequent downstream processes. In short, all the items in a particular order should be considered as an integral part;if one of these items encounters a much larger retrieval delay than others do, then the entire order may experience an unnecessary latency. In the past, the integrality of order has not received much attention for the parallel retrieval process of multiple stackers. To take this into account, this paper proposes using an Order Tag to label all the items that belong to the same order for retrieval job scheduling. The way of calculating the Order Tags will then determine the scheduling discipline of the ARS. With the objectives of minimizing the average delay and ensuring the fairness, two algorithms are proposed. They are named as Dynamic Order-Based (DOB) and Dynamic Order-Based with Threshold (DOBT) scheduling algorithms, respectively. Compared with the First-Come-First-Serve and other approaches, the simulation results show that DOB and DOBT are able to reduce the average order retrieval delay by at least 30%, and generate less backlog pressure to the downstream operations.

关键词： Packaging Licenses Heuristic algorithms Delays Sequential analysis scheduling algorithms scheduling Warehouse automation automated retrieval system order integrality job scheduling algorithm design and analysis

来源：评论

学校读者我要写书评

暂无评论

Dwell scheduling algorithms for Phased Array Antenna

引用

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS 2013年第1期49卷 42-54页

作者： Spasojevic, Zoran Dedeo, Scot Jensen, Reed MIT Lincoln Lab Lexington MA 02420 USA

In a multifunctional radar performing searching and tracking operations, the maximum number of targets that can be managed is an important measure of performance. One way a radar can maximize tracking performance is to optimize its dwell scheduling. The problem of designing efficient dwell scheduling algorithms for various tracking and searching scenarios with respect to various objective functions has been considered many times in the past and many solutions have been proposed. We consider the dwell scheduling problem for two different scenarios where the only objective is to maximize the number of dwells scheduled during a scheduling period. We formulate the problem as a distributed and a nondistributed bin packing problem and present optimal solutions using an integer programming formulation. Obtaining an optimal solution gives the limit of radar performance. We also present a more computationally friendly but less optimal solution using a greedy approach.

关键词： Algorithm design and analysis Arrays Radar tracking Schedules scheduling algorithms Target tracking

来源：评论

学校读者我要写书评

暂无评论

Performance Comparison of Offline scheduling algorithms for the Time-Aware Shaper (TAS)

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2024年第7期20卷 9736-9748页

作者： Stueber, Thomas Eppler, Manuel Osswald, Lukas Menth, Michael Univ Tubingen Chair Commun Networks D-72074 Tubingen Germany

Time-sensitive networking is an emerging technology that enables deterministic and reliable transmission in bridged Ethernet networks. The enhancement for scheduled traffic defined in IEEE 802.1Qbv [1] allows to implement time-aware shaping (TAS) which grants periodic slices for transmission to various priority queues of a bridge. TAS is an enabler for traffic scheduling, i.e., frame transmissions of periodic streams at senders and the TAS on intermediate bridges are configured such that these frames experience no loss and hardly any queuing delay. Thereby, deterministic bounds on delay and jitter can be guaranteed to such streams. However, the standard does not provide an algorithm to compute transmission schedules. Therefore, more than 100 research works [St & uuml;ber et al. (2023)] propose various algorithms for computing such schedules. Nevertheless, there are still many challenges to solve in this area. In this work, we implement eleven of these algorithms and compare their performance under various conditions with regard to schedule quality and runtime. It reveals that the performance of the algorithms varies a lot and points out their shortcomings. The set of problem instances for this study covers a wide range of parameters and is released to the public so that the performance of new algorithms can be easily compared to those in this study.

关键词： Streams Schedules Job shop scheduling scheduling algorithms Delays Bridges Routing Communication technology ethernet low latency communication optimization performance evaluation scheduling algorithms time-aware shaper time-sensitive networking

来源：评论

学校读者我要写书评

暂无评论

Parallelizing Hardware Tasks on Multicontext FPGA With Efficient Placement and scheduling algorithms

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2018年第2期37卷 350-363页

作者： Liang, Hao Sinha, Sharad Zhang, Wei Hong Kong Univ Sci & Technol Dept Elect & Comp Engn Hong Kong Hong Kong Peoples R China Nanyang Technol Univ Singapore Singapore

Field programmable gate arrays (FPGAs) are often used to accelerate multiple tasks simultaneously, working in a tightly coupled processor-coprocessor architecture. Recently, with the fast development of emerging memory technologies, multi-context FPGAs with high-density memories that support fast dynamic reconfiguration have become feasible. Compared with single-context FPGAs, multicontext FPGAs have a much higher on-chip configuration memory capacity but have not been thoroughly investigated to exploit their capabilities. In this paper, we investigate how to best utilize the capacity advantage of the multicontext FPGAs. We first propose a static placement strategy to place the requested hardware tasks with minimal area on the FPGA. We then optimize the running time of the static placement without sacrificing its solution quality. Along with the static placement, we propose collaborated online placement and scheduling strategies to manage the actual execution and reconfiguration of hardware tasks on a multicontext FPGA. Our experiments show that the static placement algorithm generates high quality placement solutions within a short time. Starting from the static placement solution, our collaborated online placer and scheduler schedules and places simultaneous acceleration tasks and reduces the acceleration task rejection rate significantly compared to a baseline design.

关键词： Genetic algorithms reconfigurable architectures scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Toward Minimum WCRT Bound for DAG Tasks Under Prioritized List scheduling algorithms

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2022年第11期41卷 3874-3885页

作者： Chang, Shuangshuang Bi, Ran Sun, Jinghao Liu, Weichen Yu, Qi Deng, Qingxu Gu, Zonghua Northeastern Univ Sch Comp Sci & Engn Shenyang 110819 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore Dalian Univ Technol Sch Comp Sci & Technol Dalian 116024 Peoples R China Umea Univ Dept Appl Phys & Elect S-90187 Umea Sweden

Many modern real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Recent studies show that the worst-case response time (WCRT) bound of a DAG task can be significantly reduced when the execution order of the vertices is determined by the priority assigned to each vertex of the DAG. How to obtain the optimal vertex priority assignment, and how far from the best-known WCRT bound of a DAG task to the minimum WCRT bound are still open problems. In this article, we aim to construct the optimal vertex priority assignment and derive the minimum WCRT bound for the DAG task. We encode the priority assignment problem into an integer linear programming (ILP) formulation. To solve the ILP model efficiently, we do not involve all variables or constraints. Instead, we solve the ILP model iteratively, i.e., we initially solve the ILP model with only a few primary variables and constraints, and then at each iteration, we increment the ILP model with the variables and constraints which are more likely to derive the optimal priority assignment. Experimental work shows that our method is capable of solving the ILP model optimally without involving too many variables or constraints, e.g., for instances with 50 vertices, we find the optimal priority assignment by involving 12.67% variables on average and within several minutes on average.

关键词： Task analysis Real-time systems Time factors Parallel processing scheduling algorithms Multicore processing Sun Directed acyclic graph (DAG) integer linear programming (ILP) prioritized list scheduling (PLS) response time bound

来源：评论

学校读者我要写书评

暂无评论

Online EV scheduling algorithms for Adaptive Charging Networks with Global Peak Constraints

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING

引用

IEEE TRANSACTIONS ON SUSTAINABLE COMPUTING 2022年第3期7卷 537-548页

作者： Alinia, Bahram Hajiesmaili, Mohammad H. Lee, Zachary J. Crespi, Noel Mallada, Enrique Telecom SudParis Inst Mines Telecom Dept Networks & Mobile Multimedia Serv RS2M F-91000 Evry France Univ Massachusetts Coll Informat & Comp Sci Amherst MA 01003 USA CALTECH Dept Elect Engn Pasadena CA 91125 USA Johns Hopkins Univ Dept Elect & Comp Engn Baltimore MD 21218 USA

This paper tackles online scheduling of electric vehicles (EVs) in an adaptive charging network (ACN) with local and global peak constraints. Given the aggregate charging demand of the EVs and the peak constraints of the ACN, it might be infeasible to fully charge all the EVs according to their charging demand. Two alternatives in such resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). The technical challenge is the need for online solution design since in practical scenarios the scheduler has no or limited information of future arrivals in a time-coupled underlying problem. For the fractional model, we devise both offline and online algorithms. We prove that the offline algorithm is optimal. Using competitive ratio as the performance measure, we prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is strongly NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. For offline setting, we devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases. Extensive trace-driven experimental results show that the performance of the proposed online algorithms is close to the offline optimum, and outperform the existing solutions.

关键词： Approximation algorithms scheduling Electric vehicle charging scheduling algorithms Adaptive systems Electronic mail Charging stations Electric vehicle online scheduling approximation algorithm competitive analysis

来源：评论

学校读者我要写书评

暂无评论

Low-Complexity scheduling algorithms for Multichannel Downlink Wireless Networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2012年第5期20卷 1608-1621页

作者： Bodas, Shreeshankar Shakkottai, Sanjay Ying, Lei Srikant, R. Univ Texas Austin Dept Elect & Comp Engn Austin TX 78712 USA Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA

This paper considers the problem of designing scheduling algorithms for multichannel (e.g., OFDM-based) wireless downlink networks, with a large number of users and proportionally large bandwidth. For this system, while the classical MaxWeight algorithm is known to be throughput-optimal, its buffer-overflow performance is very poor (formally, it is shown that it has zero rate function in our setting). To address this, a class of algorithms called iterated Heaviest matching with Longest Queues First (iHLQF) is proposed. The algorithms in this class are shown to be throughput-optimal for a general class of arrival/channel processes, and also rate-function-optimal (i.e., exponentially small buffer overflow probability) for certain arrival/channel processes. iHLQF, however, has higher complexity than MaxWeight (n(4) versus n(2), respectively). To overcome this issue, a new algorithm called Server-Side Greedy (SSG) is proposed. It is shown that SSG is throughput-optimal, results in a much better per-user buffer overflow performance than the MaxWeight algorithm (positive rate function for certain arrival/channel processes), and has a computational complexity (n(2)) that is comparable to the MaxWeight algorithm. Thus, it provides a nice tradeoff between buffer-overflow performance and computational complexity. These results are validated by both analysis and simulations.

关键词： Large deviations low complexity scheduling algorithms small buffer

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：