Search

The document is the table of contents for the February 2024 issue of IEEE Transactions on Semiconductor Manufacturing. It includes editorials, regular issue papers, and announcements. The regular issue papers focus on topics such as energy-aware scheduling, adaptive photolithography scheduling, integrated scheduling, gas-delivery fluid-mechanical timescales, machine learning on optical metrology, yield modeling, and more. The document also includes announcements for joint call for papers and a call for papers for other IEEE transactions. [Extracted from the article]

In modern discrete flexible manufacturing systems, dynamic disturbances frequently occur in real time and each job may contain several special operations in partial-no-wait constraint due to technological requirements. In this regard, a hierarchical multiagent deep reinforcement learning (DRL)-based real-time scheduling method named hierarchical multi-agent proximal policy optimization (HMAPPO) is developed to address the dynamic partial-no-wait multiobjective flexible job shop scheduling problem (DMOFJSP-PNW) with new job insertions and machine breakdowns. The proposed HMAPPO contains three proximal policy optimization (PPO)-based agents operating in different spatiotemporal scales, namely, objective agent, job agent, and machine agent. The objective agent acts as a higher controller periodically determining the temporary objectives to be optimized. The job agent and machine agent are lower actuators, respectively, choosing a job selection rule and machine assignment rule to achieve the temporary objective at each rescheduling point. Five job selection rules and six machine assignment rules are designed to select an uncompleted job and assign the next operation of which together with its successors in no-wait constraint on the corresponding processing machines. A hierarchical PPO-based training algorithm is developed. Extensive numerical experiments have confirmed the effectiveness and superiority of the proposed HMAPPO compared with other well-known dynamic scheduling methods. Note to Practitioners—The motivation of this article stems from the need to develop real-time scheduling methods for modern discrete flexible manufacturing factories, such as aerospace product manufacturing and steel manufacturing, where dynamic events frequently occur, and each job may contain several operations subjected to the no-wait constraint. Traditional dynamic scheduling methods, such as metaheuristics or dispatching rules, either suffer from poor time efficiency or fail to ensure good solution quality for multiple objectives in the long-term run. Meanwhile, few of the previous studies have considered the partial-no-wait constraint among several operations from the same job, which widely exists in many industries. In this article, we propose a hierarchical multiagent deep reinforcement learning (DRL)-based real-time scheduling method named HMAPPO to address the dynamic partial-no-wait multiobjective flexible job shop scheduling problem (DMOFJSP-PNW) with new job insertions and machine breakdowns. The proposed HMAPPO uses three DRL-based agents to adaptively select the temporary objectives and choose the most feasible dispatching rules to achieve them at different rescheduling points, through which the rescheduling can be made in real time and a good compromise among different objectives can be obtained in the long-term schedule. Extensive experimental results have demonstrated the effectiveness and superiority of the proposed HMAPPO. For industrial applications, this method can be extended to many other production scheduling problems, such as hybrid flow shops and open shop with different uncertainties and objectives. [ABSTRACT FROM AUTHOR]

To support higher demand for datacenter networks, networking researchers have proposed hybrid electrical/optical datacenter networks (Hybrid-DCN) that leverages optical circuit switching (OCS) along with traditional electrical packet switching (EPS). However, due to the high reconfiguration delay of OCS, OCS is used only for bulk data transfers between racks to amortize the reconfiguration delay. Existing job schedulers for data-parallel frameworks are not designed for Hybrid-DCN, since they neither place tasks to aggregate data traffic to take advantage of OCS, nor schedule tasks to minimize the Coflow completion time (CCT). In this paper, we describe the mismatch between existing job schedulers and the advanced Hybrid-DCN, introduce the requirements for the new scheduler, and present the implementation of Co-scheduler, a job scheduler for data-parallel frameworks that aims to improve job performance by placing the tasks of jobs to aggregate enough data traffic to better leverage OCS to minimize the CCT in Hybrid-DCN. Specifically, for every job, Co-scheduler computes guidelines on how many racks to place the job’s input data and the job’s tasks. The guidelines are dynamically generated based on the real-time job characteristics or predictable job characteristics from prior runs, with the aim of leveraging OCS whenever possible and efficient and minimizing CCT of jobs. Co-scheduler then schedules the tasks of jobs based on the guidelines. We evaluate the effectiveness of Co-scheduler using trace-driven simulation. The evaluation demonstrates that Co-scheduler can improve makespan, average job completion time, and average CCT of a workload by up to 56%, 61%, and 79%, respectively, compared to the state-of-the-art schedulers. [ABSTRACT FROM AUTHOR]

Recent advances in 5G and edge computing enable rapid development and deployment of edge-cloud systems, which are ideal for delay-sensitive machine learning (ML) applications such as autonomous driving and smart city. Distributed ML jobs often need to train a large model with enormous datasets, which can only be handled by deploying a distributed set of workers in an edge-cloud system. One common approach is to employ a parameter server (PS) architecture, in which training is carried out at multiple workers, while PSs are used for aggregation and model updates. In this architecture, one of the fundamental challenges is how to dispatch ML jobs to workers and PSs such that the average job completion time (JCT) can be minimized. In this work, we propose a novel online preemptive scheduling framework to decide the location and the execution time window of concurrent workers and PSs upon each job arrival. Specifically, our proposed scheduling framework consists of: i) a job dispatching and scheduling algorithm that assigns each ML job to workers and decides the schedule to train each data chunk; ii) a PS assignment algorithm that determines the placement of PS. We prove theoretically that our proposed algorithm is $D_{max}(1+1/\epsilon)$ -competitive with $(1 + \epsilon)$ -speed augmentation, where $D_{max}$ is the maximal number of data chunks in any job. Extensive testbed experiments and trace-driven simulations show that our algorithm can reduce the average JCT by up to 30% compared with state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

For wireless caching networks, the scheme design for content delivery is non-trivial in the face of the following tradeoff. On one hand, to optimize overall throughput, users can associate their nearby APs with great channel capacities; however, this may lead to unstable queue backlogs on APs and prolong request delays. On the other hand, to ensure queue stability, some users may have to associate APs with inferior channel states, which would incur throughput loss. Moreover, for such systems, how to conduct predictive scheduling to reduce delays and the fundamental limits of its benefits remain unexplored. In this paper, we formulate the problem of online user-AP association and resource allocation for content delivery with predictive scheduling under a fixed content placement as a stochastic network optimization problem. By exploiting its unique structure, we transform the problem into a series of modular maximization sub-problems with matroid constraints. Then we devise PUARA, a Predictive User-AP Association and Resource Allocation scheme which achieves a provably near-optimal throughput with queue stability. Our theoretical analysis and simulation results show that PUARA can not only perform a tunable control between throughput maximization and queue stability, but also incur a notable delay reduction with predicted information. [ABSTRACT FROM AUTHOR]

Time-sensitive networking (TSN) can help standardize deterministic Ethernet across industrial automation. The deterministic guarantee of TSN is based on network resource scheduling in the unit of flow. However, the state-of-the-art TSN single flow scheduling scheme cannot meet the coordinated scheduling requirements of multiple data flows in advanced industrial applications (e.g., control and safety applications). In this article, we propose a TSN chain flow abstraction, TC-Flow, for a coordinated multiple-flow scheduling model in industrial control and safety applications. Based on the proposed TC-Flow model, we design an offline TC-Flow scheduling algorithm using integer linear programming and an online heuristic TC-Flow scheduling algorithm to handle network dynamics. To deploy the proposed TC-Flow model and scheduling algorithms in the TSN, we design a CF-TSN network architecture that is compatible with the existing TSN single-flow scheduling scheme. Finally, we implement the proposed CF-TSN architecture and TC-Flow scheduling algorithms in real-world network environments. Experimental results show that the proposed scheduling algorithms can increase the number of schedulable flows by 26 percent compared to the state-of-the-art TSN scheduling benchmark. [ABSTRACT FROM AUTHOR]

This paper firstly proposes a greedy online packet scheduling algorithm for the problem raised by Mao, Koksal and Shroff that allows arbitrary hard deadlines in multi-hop networks aiming at maximizing the total revenue. With the same assumption of ρM/ρm = O(1) where ρM and ρm are the maximum and minimum revenue a packet may carry, our algorithm is O (PM)-competitive improving on MKS algorithm by a factor of O (log PM), where PM is the length of the longest path a packet may travel in the network. We prove that it is asymptotically optimal by presenting a lower bound of PM on the competitiveness for this problem. Secondly, this paper studies the extension of this problem that includes routing as a part of the solution. We prove that using the fastest path algorithm for the routing part, the greedy online algorithm also achieves asymptotically optimal competitiveness for the extended problem. Furthermore, we present a non-greedy online algorithm that not only is asymptotically optimal, but also can adaptively achieve a better competitiveness when the network has a larger Cmin, where Cmin is the minimum link capacity in the network. Finally, simulation results are reported, showing that not only do the greedy online algorithms achieve asymptotically optimal bounds, but also practically achieve better performance than the previously proposed algorithms. [ABSTRACT FROM AUTHOR]

Datacenters are evolving to host heterogeneous workloads on shared clusters to reduce the operational cost and achieve higher resource utilization. However, it is challenging to schedule heterogeneous workloads with diverse resource requirements and QoS constraints. On one hand, latency-critical jobs need to be scheduled as soon as they are submitted to avoid any queuing delays. On the other hand, best-effort long jobs should be allowed to occupy the cluster when there are idle resources to improve cluster utilization. The challenge lies in how to minimize the queuing delays of short jobs while maximizing cluster utilization. In this article, we propose and develop BIG-C, a container-based resource management framework for data-intensive cluster computing. The key design is to leverage lightweight virtualization, a.k.a, containers, to make tasks preemptable in cluster scheduling. We devise two types of preemption strategies: immediate and graceful preemptions and show their effectiveness and tradeoffs with loosely-coupled MapReduce workloads as well as iterative, in-memory Spark workloads. Based on the mechanisms for task preemption, we further develop job-level and task-level preemptive policies as well as a preemptive fair share cluster scheduler. Our implementation on Yarn and evaluation with synthetic and production workloads show that low job latency and high resource utilization can be both attained when scheduling heterogeneous workloads on a contended cluster. [ABSTRACT FROM AUTHOR]

Outsourcing data to a third-party cloud provider has become quite common with the increasing use of cloud computing. This brings convenience, as well as the concern for data security and privacy. It is believed that data encryption alone is often not enough to protect users’ privacy from the cloud provider. According to previous work, the sequence of storage locations accessed by the client can leak up to 90% of the sensitive information, even with data encrypted. In this context, Oblivious RAM (ORAM) is proposed. ORAM algorithms allow the client to hide its access pattern from the service provider while introducing a lot of extra operations. Among all the prototypes, Path ORAM is one of the most promising designs. However, there are still redundant memory accesses that can be removed without harming the security of traditional ORAM as we observed. We came up with three optimization techniques, including path merging, ORAM request scheduling, and merging aware caching. We also propose a prefetching technique to further decreasing the access overhead. Moreover, we also illustrate the compatibility of Fork Path and some state-of-the-art Path ORAM optimizations. Compared to traditional Path ORAM approaches, our Fork Path ORAM can reduce overall performance overhead and power consumption of memory system by 65% and 44%, while the design overhead is trivial. [ABSTRACT FROM AUTHOR]

Serverless computing has emerged as a new cloud computing execution model that liberates users and application developers from explicitly managing ‘physical’ resources, leaving such a resource management burden to service providers. In this article, we study the problem of resource allocation for multi-tenant serverless computing platforms explicitly taking into account workload fluctuations including sudden surges. In particular, we investigate different root causes of performance degradation in these platforms where tenants (their applications) have different workload characteristics. To this end, we develop a fine-grained CPU cap control solution as a resource manager that dynamically adjusts CPU usage limit (or CPU cap) concerning applications with same/similar performance requirements, i.e., application groups. The adjustment of CPU caps applies primarily to co-located worker processes of serverless computing platforms to minimize resource contention, which is the major source of performance degradation. The actual adjustment decisions are made based on performance metrics (e.g., throttled time and queue length) using a group-aware scheduling algorithm. The extensive experimental results performed in our local cluster confirm that the proposed resource manager can effectively eliminate the burden of explicit reservation of computing capacity, even when fluctuations and sudden surges in the incoming workload exist. We measure the robustness of the proposed resource manager by comparing it with several heuristics which extensively used in practice, including the enhanced version of round robin and the least length queue scheduling policies, under various workload intensities driven by real-world scenarios. Notably, our resource manager outperforms other heuristics by decreasing skewness and average response time up to 44 and 94 percent, respectively, while it does not over-use the CPU resources. [ABSTRACT FROM AUTHOR]

Multipath transport protocols utilize multiple network paths (e.g., WiFi and cellular) to achieve improved performance and reliability, compared with their single-path counterparts. The scheduler of a multipath transport protocol determines how to distribute the data packets onto different paths. However, state-of-the-art multipath schedulers face the challenge when dealing with heterogeneous paths with dynamic path characteristics (i.e., packet loss, fluctuation of delay). In this paper, we propose Peekaboo, a novel learning-based multipath scheduler that is aware of the dynamic characteristics of the heterogeneous paths. Peekaboo is able to learn scheduling decisions to adopt over time based on the current path characteristics and dynamicity levels - from both deterministic and stochastic perspectives. We implement Peekaboo in Multipath QUIC (MPQUIC) and compare it with state-of-the-art multipath schedulers for a wide range of dynamic heterogeneous environments, upon both emulated and real networks. Our results show that Peekaboo outperforms the other schedulers by up to 31.2% in emulated networks and up to 36.3% in real network scenarios. [ABSTRACT FROM AUTHOR]

In this paper, an aircraft ground centralized deicing monitoring system of multi-information integration is proposed. The multi-information integration system consists of system architecture, database, and monitoring terminal. Among them, the prediction module of ice accumulation calculates ice thickness of the aircraft based on the meteorological data that are collected by the data acquisition module and saved in the database. At the same time, the system uses the methods that GIS is used for making map to locate deicing vehicle precisely, data are transmitted through GPRS, and computer scheduling is adopted, which can ensure the smooth aircraft deicing process and improve the efficiency of the aircraft ground deicing. The practical results show that the proposed monitoring system of aircraft ground centralized deicing increases the efficiency of deicing by 26%. Furthermore, the feasibility and effectiveness of the proposed system are verified.

Pervasive computing requires to build systems every day more complex and heterogeneous. Smart devices must be able to carry on sensing and actuation alongside with computation and communication. As such, many different technologies must be packed within the same object. Digital HW and SW coexist with analog components and Micro-Electro-Mechanical systems capable of sensing and controlling the physical environment. For this reason, the design of such devices must rely on the integration of many different descriptions belonging to different design domains. The high-level of heterogeneity involved in the modeling phase of the system development makes harder the validation of the system functionality, since holistic system simulation would require the integration of many different simulators. In this article, we propose a set of automatic abstraction techniques for multi-disciplines analog components. Then, we define a scheduling strategy to integrate the execution of continuous-time analog sub-components with automatically abstracted models of the digital HW parts of the system. As a final result, the proposed methodology produces a C++ virtual platform providing a holistic simulation of complex and heterogeneous devices. [ABSTRACT FROM AUTHOR]

Energy-efficiency is a critical requirement for computation-intensive real-time applications on multi-core embedded systems. Multi-core processors enable intra-task parallelism, and in this work, we study energy-efficient real-time scheduling of constrained deadline sporadic parallel tasks, where each task is represented as a directed acyclic graph (DAG). We consider a clustered multi-core platform where processors within the same cluster run at the same speed at any given time. A new concept named speed-profile is proposed to model per-task and per-cluster energy-consumption variations during run-time to minimize the expected long-term energy consumption. To our knowledge, no existing work considers energy-aware real-time scheduling of DAG tasks with constrained deadlines, nor on a clustered multi-core platform. The proposed energy-aware real-time scheduler is implemented upon an ODROID XU-3 board to evaluate and demonstrate its feasibility and practicality. To complement our system experiments in large-scale, we have also conducted simulations that demonstrate a CPU energy saving of up to 67 percent through our proposed approach compared to existing methods. [ABSTRACT FROM AUTHOR]

LoRa has been recognized as one of the most promising low-power wide-area (LPWA) techniques. Since LoRa devices are usually powered by batteries, energy efficiency (EE) is an essential consideration. In this paper, we investigate the energy efficient resource allocation in LoRa networks to maximize the system EE (SEE) and the minimal EE (MEE) of LoRa users, respectively. Specifically, our objective is to maximize the corresponding EE by jointly exploiting user scheduling, spreading factor (SF) assignment, and transmit power allocations. To solve them efficiently, we first propose a suboptimal algorithm, including the low-complexity user scheduling scheme based on matching theory and the heuristic SF assignment approach for LoRa users scheduled on the same channel. Then, to deal with the power allocation, an optimal algorithm is proposed to maximize the SEE. To maximize the MEE of LoRa users assigned to the same channel, an iterative power allocation algorithm based on the generalized fractional programming and sequential convex programming is proposed. Numerical results show that the proposed user scheduling algorithm achieves near-optimal EE performance, and the proposed power allocation algorithms outperform the benchmarks. [ABSTRACT FROM AUTHOR]

Recently, the Internet of Things (IoT) topology has used to collect physical, physiological, vital signs of patients in consumer-centric e-health or consumer’ wellness care services. In such healthcare systems, varieties of medical sensors are attached to the patients to collect vital signs from those who are under observation. The data gathering process in IoT-enabled Wireless Sensor Network (WSN) suffers from the congestion problem. The effect of this translates on missing packets, a decrease of reliability and throughput degradation in IoT-enabled WSN. This article proposes a distributed congestion control algorithm for IoT-enabled WSNs to effectively resolve the congestion for healthcare applications. The proposed scheme alleviates congestion by a priority-based data routing strategy. Furthermore, this article presents a priority queue based scheduling scheme for better reliability. We analyze the properties of the proposed congestion control mechanism mathematically and validate its performance through extensive simulation and real-life experiments. The application of this work can be used to an early warning system in detecting abnormal heart rate, blood pressure, ECG, EMG in the hospital/home care environment to the state-of-art diagnosis. [ABSTRACT FROM AUTHOR]

Cloud computing has long been the main backbone that Internet of Things (IoT) devices rely on to accommodate their storage and analytical needs. However, the fact that cloud systems are often located quite far from the IoT devices and the emergence of delay-critical IoT applications urged the need for extending the cloud architecture to support delay-critical services. Given that fog nodes possess low resource capabilities compared to the cloud, matching the IoT services to appropriate fog nodes while guaranteeing minimal delay for IoT services and efficient resource utilization on fog nodes becomes quite challenging. In this context, the main limitation of existing approaches is addressing the scheduling problem from one side perspective, i.e., either fog nodes or IoT devices. To address this problem, we propose in this paper a multi-criteria intelligent IoT-Fog scheduling approach using game theory. Our solution consists of designing (1) preference functions for the IoT and fog layers to enable them to rank each other based on several criteria latency and resource utilization and (2) centralized and distributed intelligent scheduling algorithms that capitalize on matching theory and consider the preferences of both parties. Simulation results reveal that our solution outperforms the two common Min-Min and Max-Min scheduling approaches in terms of IoT services execution makespan and fog nodes resource consolidation efficiency. [ABSTRACT FROM AUTHOR]

MapReduce jobs need to shuffle a large amount of data over the network between mapper and reducer nodes. The shuffle time accounts for a big part of the total running time of the MapReduce jobs. Therefore, optimizing the makespan of shuffle phase can greatly improve the performance of MapReduce jobs. A large fraction of production jobs in data centers are recurring with predictable characteristics, and the recurring jobs split the network into periodic busy and idle time slots, which allows us to better schedule the shuffle data in order to reduce the makespan of shuffle phase with the future predictable network status available. In this paper, we formulate the shuffle scheduling problem with the aim to minimize the makespan of MapReduce shuffle phase by leveraging the predictable periodic network status. We then propose a simple yet effective network-aware shuffle scheduling algorithm (NAS) to reduce the number of idle time slots required to transfer the shuffle data so as to reduce the shuffle makespan. We also prove that the proposed algorithm NAS is a $\frac {3}{2}$ -approximation algorithm to the shuffle scheduling problem when all the future idle time slots have the same duration. We finally conduct experiments through simulations. Experimental results demonstrate the proposed algorithm can effectively reduce the makespan of MapReduce shuffle phase and increase network utilization. [ABSTRACT FROM AUTHOR]

With the advent of the Internet of Things (IoT), energy-harvesting nonvolatile processors (NVPs) have become promising platforms due to their durability when running on an intermittent power supply and fast read/write operations. However, the penalties caused by an increasing amount of data to be processed and growing communication demands pose critical challenges in the scheduling of tasks on energy-harvesting NVP platforms with tight energy and latency budgets. Together with the high power switching overhead that is induced under unstable power conditions, an increase in the amount of data to be processed significantly degrades the system performance. To overcome the problems of high communication and switching overheads for energy-harvesting NVP platforms, this article proposes a novel communication-aware task-scheduling technique. The algorithm first selects one or more executable tasks to be performed based on the task benefits and then calls a task partitioning algorithm to dynamically divide the scheduled tasks. We evaluate the performance of our proposed algorithm in comparison with the performance-aware task scheduling (PATH) and greedy iterative (GI) algorithms. Experimental results show that the proposed algorithm can reduce the execution time by 17.08% and 13.72% on average compared with the PATH and GI algorithms, respectively. [ABSTRACT FROM AUTHOR]

Large-Scale Antenna System (LSAS) has played an important role in the emerging fifth-generation mobile systems (5G) due to its potential for excellent spectral efficiency. However, it may cause a mass of pilot overhead that is not conducive to the application of LSAS in massive Machine-Type Communications (mMTC), one of three typical traffic modes of 5G. In this paper, we present a pilot-efficient scheduling strategy for mMTC systems, in which the Base Stations (BS) are equipped with large-scale antennas, from a cross-layer perspective. Our scheme can not only schedule the massive devices to access the spectrum, but also allocate the BS’ power without the need for much pilot overhead. More particularly, the users allowed to access the spectrum can be selected based on their queue state information without any channel estimations, while the power allocation only needs the channel estimations for scheduled users. We shall show the optimality of the presented policy based on the Lyapunov optimization theory. To solve the Lyapunov optimization problem, we present a low complexity two-layer iteration algorithm for more practical purposes. Simulation results demonstrate the substantial gain of our presented method over existing scheduling protocols of massive MIMO. [ABSTRACT FROM AUTHOR]

In Infrastructure as a Service (IaaS) Clouds, users are charged to utilize cloud services according to a pay-per-use model. If users intend to run their workflow applications on cloud resources within a specific budget, they have to adjust their demands for cloud resources with respect to this budget. Although several scheduling approaches have introduced solutions to optimize the makespan of workflows on a set of heterogeneous IaaS cloud resources within a certain budget, the hourly-based cost model of some well-known cloud providers (e.g., Amazon EC2 Cloud) can easily lead to a higher makespan and some schedulers may not find any feasible solution. In this article, we propose a novel resource provisioning mechanism and a workflow scheduling algorithm, named Greedy Resource Provisioning and modified HEFT (GRP-HEFT), for minimizing the makespan of a given workflow subject to a budget constraint for the hourly-based cost model of modern IaaS clouds. As a resource provisioning mechanism, we propose a greedy algorithm which lists the instance types according to their efficiency rate. For our scheduler, we modified the HEFT algorithm to consider a budget limit. GRP-HEFT is compared against state-of-the-art workflow scheduling techniques, including MOACS (Multi-Objective Ant Colony System), PSO (Particle Swarm Optimization), and GA (Genetic Algorithm). The experimental results demonstrate that GRP-HEFT outperforms GA, PSO, and MOACS for several well-known scientific workflow applications for different problem sizes on average by 13.64, 19.77, and 11.69 percent, respectively. Also in terms of time complexity, GRP-HEFT outperforms GA, PSO and MOACS. [ABSTRACT FROM AUTHOR]

Motivated by medium access control for resource-challenged wireless Internet of Things (IoT) networks, we consider the problem of queue scheduling with reduced queue state information. In particular, we consider a time-slotted scheduling model with $N$ wireless links, such that links $i$ and $i+1$ , $1 \leq i \leq N-1$ cannot transmit together. Our aim in this paper is to study throughput-optimal, and even delay optimal, scheduling policies that require only the empty-nonempty state of the packet queues associated with these links (Queue Nonemptiness Based, or QNB, policies). We focus on Maximum Size Matching (MSM) policies, and provide an analysis of all the QNB-MSM policies for $N=3$ , thereby comparing their performance, and revisiting a delay optimal scheduling result. Our study shows that, while scheduling a maximum size matching would seem intuitive, there are important performance differences between different QNB-MSM policies. Further, it is not necessary for a QNB policy to be MSM for it to be throughput optimal. We develop a new Policy Splicing technique to combine scheduling policies for small networks to construct throughput-optimal policies for larger networks, some of which also aim for low delay. For $N=3$ there exists a QNB-MSM policy that is sum-queue optimal over the entire stability region. We show, however, that for $N \geq 4$ , there is no QNB scheduling policy that is sum-queue length optimal over all arrival rate vectors in the capacity region. Our throughput-optimality results rely on two new arguments: a Lyapunov drift lemma specially adapted to policies that are queue length-agnostic, and a priority queueing analysis for showing strong stability. We then extend our results to a more general class of interference constraints that we call cluster-of-cliques (CoC) conflict graphs. We consider two types of CoC networks, namely, Linear Arrays of Cliques (LAoC) and Star-of-Cliques (SoC) networks. We develop QNB policies for these classes of networks, study their stability and delay properties, and propose and analyze techniques to reduce the amount of state information to be disseminated across the network for scheduling. [ABSTRACT FROM AUTHOR]

Industrial Internet of Things (IIoT) is an architecture that facilitates the feasibility of the distributed control of the modernized industrial systems mainly through the Internet of Things and cloud computing. This article proposes an optimal scheduling framework for the real-time operation of smart microgrids in the IIoT environment using an average consensus-based algorithm. The introduced framework suggests a fog layer as a complementary layer of IIoT to reduce latency and provide local computation and data storage for the proposed industry. Security of the system against probable attacks is the other concern that should be observed. To this end, this article sets out to evaluate the impact of a particular type of attack called the denial of service on the performance of the proposed method. Accuracy, feasibility, and fast response of the scheme are demonstrated through simulation results on a microgrid test system in the presence of dispatchable and nondispatchable generation units with heterogeneous devices. [ABSTRACT FROM AUTHOR]

Along with the development of 5G, NS plays an important role in the application of mobile networks to meet all kinds of personalized requirements. In terms of NS concept, network operators can vertically split a physical network into multiple logically separate networks to flexibly meet QoS requirements, which are mainly represented as higher bandwidth and lower latency. In this article, we propose a novel QoS framework of NS in 5G and beyond networks based on SDN and NFV to guarantee key QoS indicators for different application scenarios, such as eMBB, mMTC and URLLC. In this QoS framework, a 5G network is divided into three parts, RAN, TN and CN, to form three types of NS with different network resource allocation algorithms. The performance evaluation in the simulation environment of Mininet shows that the proposed QoS framework can steer different flows into different queues of OVS, schedule network resources for various NS types and provide reliable E2E QoS for users according to preconfigured QoS requirements. [ABSTRACT FROM AUTHOR]

With limited wireless resources but increasing demands for wireless applications, non-orthogonal multiple access (NOMA) has been considered as a promising technology for future wireless networks. Nevertheless, it remains challenging on motivating the mobile users (MU) to join NOMA networks, scheduling MUs on the same sub-bands, reducing interference among the MUs and setting optimal transmit power in the NOMA networks. In this paper, first we consider the quantization error due to the limitation of receivers’ equipments and the decoding error during the successive interference cancellation (SIC) procedure. Second, we model the resource allocation problems as the four-level equilibrium problems with equilibrium constraints (EPEC), where the wireless operator, on behalf of each MU, first predicts the utilities and assign the MU as a NOMA user (NMU) or a traditional MU (TMU). For the NMUs, the interference penalty pricing strategy of other NMUs are proposed. Based on the announced prices of all the NMUs, the sub-channel allocation is managed in either distributed or collaborative ways. According to the announced interference prices of other NMUs and the coalition results, the optimal transmit power to gain the maximum utility is considered. Through extensive simulation analysis, the superior performance obtained by using the proposed scheme is demonstrated. [ABSTRACT FROM AUTHOR]

User scheduling, beamforming and energy coordination are investigated in smart-grid powered cellular networks (SGPCNs), where the base stations are powered by a smart grid and natural renewable energy sources. Heterogeneous energy coordination is considered in SGPCNs, namely energy merchandizing with the smart grid and energy exchanging among the base stations. A long-term grid-energy expenditure minimization problem with proportional-rate constraints is formulated for SGPCNs. Since user scheduling is coupled with the beamforming vectors, the formulated problem is challenging to handle via standard convex optimization methods. In practice, the beamforming vectors need to be updated over each slot according to the channel variations. User scheduling needs to be updated over several slots (frame) since the frequent scheduling of user equipment can cause reliability issues. Therefore, the Lyapunov optimization method is used to decouple the problem. A practical two-scale algorithm is proposed to schedule users at each frame, and obtain the beamforming vectors and amount of exchanged natural renewable energy at each slot. We prove that the proposed two-scale algorithm can asymptotically achieve the optimal solutions via tuning a control parameter. Numerical results verify the performance of the proposed two-scale algorithm. [ABSTRACT FROM AUTHOR]

This work is motivated by the need of collecting fresh data from power-constrained sensors in the industrial Internet of Things (IIoT) network. A recently proposed metric, the Age of Information (AoI) is adopted to measure data freshness from the perspective of the central controller in the IIoT network. We wonder what is the minimum average AoI the network can achieve and how to design scheduling algorithms to approach it. To answer these questions when the channel states of the network are time-varying and scheduling decisions are restricted to both bandwidth and power consumption constraint, we first decouple the multi-sensor scheduling problem into a single-sensor constrained Markov decision process (CMDP) by relaxing the hard bandwidth constraint. Next we exploit the threshold structure of the optimal policy for the decoupled single sensor CMDP and obtain the optimum solution through linear programming (LP). Finally, an asymptotically optimal truncated policy that can satisfy the hard bandwidth constraint is built upon the optimal solution to each of the decoupled single-sensor. Our investigation shows that to obtain a small average AoI over the network: (1) The scheduler exploits good channels to schedule sensors supported by limited power; (2) Sensors equipped with enough transmission power are updated in a timely manner such that the bandwidth constraint can be satisfied. [ABSTRACT FROM AUTHOR]

Fog computing (FC) has the potential to process computation-intensive tasks in Industrial Internet of Things (IIoT) systems. In parallel with the development of FC, non-orthogonal multiple access (NOMA) has been recognized as a promising technique to significantly improve the spectrum efficiency. In this paper, a NOMA-based FC framework for IIoT systems is considered, where multiple task nodes offload their tasks via NOMA to multiple nearby helper nodes for execution. We formulate a joint task scheduling and subcarrier allocation problem, with an objective to minimize the total cost in terms of the delay and energy consumption, while taking into account the practical communication and computation constraints. Note that the task scheduling includes task, computation resource, and power allocations. Since the task and subcarrier allocations involve binary variables, it is challenging to obtain an optimal solution for such a combinatorial problem. To this end, we solve the task scheduling and subcarrier allocation problem in an online learning fashion. During the online learning process, we propose an iterative algorithm to jointly optimize the subcarrier allocation and task scheduling in each time episode. Simulation results show that the proposed scheme can significantly reduce the sum cost compared to the baseline schemes. [ABSTRACT FROM AUTHOR]

We consider an energy harvesting sensor transmitting latency-sensitive data over a fading channel. We aim to find the optimal transmission scheduling policy that minimizes the packet queuing delay given the available harvested energy. We formulate the problem as a Markov decision process (MDP) over a state-space spanned by the transmitter’s buffer, battery, and channel states, and analyze the structural properties of the resulting optimal value function, which quantifies the long-run performance of the optimal scheduling policy. We show that the optimal value function (i) is non-decreasing and has increasing differences in the queue backlog; (ii) is non-increasing and has increasing differences in the battery state; and (iii) is submodular in the buffer and battery states. Taking advantage of these structural properties, we derive an approximate value iteration algorithm that provides a controllable tradeoff between approximation accuracy, computational complexity, and memory, and we prove that it converges to a near-optimal value function and policy. Our numerical results confirm these properties and demonstrate that the resulting scheduling policies outperform a greedy policy in terms of queuing delay, buffer overflows, energy efficiency, and sensor outages. [ABSTRACT FROM AUTHOR]

Cloud computing has been increasingly concerned in scientific computing area. More and more enterprises and research institutes have migrated their applications to the clouds. Due to the complexity of cloud computing system in structural and behavioral aspects, how to design the fault tolerant cloud computing system becomes a challenging problem. This paper investigates the modeling and analysis of fault tolerant strategy for deadline constrained task scheduling in cloud computing. First, a formal description language is defined to accurately model the different components of cloud application, and use it to characterize the operational mechanisms and fault behaviors. Second, we propose a fault tolerant strategy, which includes the scheduling mechanism, synchronization mechanism, and exception mechanism, to dynamically compute the execution mode and required virtual machine for tasks, thus ensuring the reliability and real-time requirement of cloud application. An enforcement algorithm is also designed to realize the proposed strategy. Third, the techniques of Petri nets are provided to analyze and validate the correctness of proposed method. Finally, several experiments are done to illustrate that the reliability of cloud application is improved and its deadline is met. [ABSTRACT FROM AUTHOR]

Emerging 5G systems will need to efficiently support both enhanced mobile broadband traffic (eMBB) and ultra-low-latency communications (URLLC) traffic. In these systems, time is divided into slots which are further sub-divided into minislots. From a scheduling perspective, eMBB resource allocations occur at slot boundaries, whereas to reduce latency URLLC traffic is pre-emptively overlapped at the minislot timescale, resulting in selective superposition/puncturing of eMBB allocations. This approach enables minimal URLLC latency at a potential rate loss to eMBB traffic.We study joint eMBB and URLLC schedulers for such systems, with the dual objectives of maximizing utility for eMBB traffic while immediately satisfying URLLC demands. For a linear rate loss model (loss to eMBB is linear in the amount of URLLC superposition/puncturing), we derive an optimal joint scheduler. Somewhat counter-intuitively, our results show that our dual objectives can be met by an iterative gradient scheduler for eMBB traffic that anticipates the expected loss from URLLC traffic, along with an URLLC demand scheduler that is oblivious to eMBB channel states, utility functions and allocation decisions of the eMBB scheduler. Next we consider a more general class of (convex/threshold) loss models and study optimal online joint eMBB/URLLC schedulers within the broad class of channel state dependent but minislot-homogeneous policies. A key observation is that unlike the linear rate loss model, for the convex and threshold rate loss models, optimal eMBB and URLLC scheduling decisions do not de-couple and joint optimization is necessary to satisfy the dual objectives. We validate the characteristics and benefits of our schedulers via simulation. [ABSTRACT FROM AUTHOR]

Full-duplex (FD) wireless is an attractive communication paradigm with high potential for improving network capacity and reducing delay in wireless networks. Despite significant progress on the physical layer development, the challenges associated with developing medium access control (MAC) protocols for heterogeneous networks composed of both legacy half-duplex (HD) and emerging FD devices have not been fully addressed. Therefore, we focus on the design and performance evaluation of scheduling algorithms for infrastructure-based heterogeneous HD-FD networks (composed of HD and FD users). We first show that centralized Greedy Maximal Scheduling (GMS) is throughput-optimal in heterogeneous HD-FD networks. We propose the Hybrid-GMS (H-GMS) algorithm, a distributed implementation of GMS that combines GMS and a queue-based random-access mechanism. We prove that H-GMS is throughput-optimal. Moreover, we analyze the delay performance of H-GMS by deriving lower bounds on the average queue length. We further demonstrate the benefits of upgrading HD nodes to FD nodes in terms of throughput gains for individual nodes and the whole network. Finally, we evaluate the performance of H-GMS and its variants in terms of throughput, delay, and fairness between FD and HD users via extensive simulations. We show that in heterogeneous HD-FD networks, H-GMS achieves 16– $30\times $ better delay performance and improves fairness between HD and FD users by up to 50% compared with the fully decentralized Q-CSMA algorithm. [ABSTRACT FROM AUTHOR]

Densely-deployed femtocell networks are used to enhance wireless coverage in public spaces such as office buildings, subways, and academic buildings. These networks can increase user throughput, but edge users can suffer from co-channel interference and service outages. This paper introduces a distributed algorithm for network configuration, called Radius Reduction and Scheduling (RRS), to improve the performance and fairness of the network. RRS works by jointly adapting femtocell transmission power, allocating user to femtocells, and scheduling resource blocks so as to increase fairness and reduce outage probability in dense femtocell networks. RRS produces a network configuration that guarantees either user or area coverage depending on the management needs. A prototype implementation confirms the benefits of RRS in a real environment. Furthermore, extensive simulations show that RRS reduces the outage probability of up to 50%, and provides better fairness, with an increase in Jain’s index of 190%, with respect to a baseline algorithm which works with fixed power and best-effort scheduling and to a previous approach to resource management in femtocell networks. [ABSTRACT FROM AUTHOR]

Managing Network Function (NF) service chains requires careful system resource management. We propose NFVnice, a user space NF scheduling and service chain management framework to provide fair, efficient and dynamic resource scheduling capabilities on Network Function Virtualization (NFV) platforms. The NFVnice framework monitors load on a service chain at high frequency (1000Hz) and employs backpressure to shed load early in the service chain, thereby preventing wasted work. Borrowing concepts such as rate proportional scheduling from hardware packet schedulers, CPU shares are computed by accounting for heterogeneous packet processing costs of NFs, I/O, and traffic arrival characteristics. By leveraging cgroups, a user space process scheduling abstraction exposed by the operating system, NFVnice is capable of controlling when network functions should be scheduled. NFVnice improves NF performance by complementing the capabilities of the OS scheduler but without requiring changes to the OS’s scheduling mechanisms. Our controlled experiments show that NFVnice provides the appropriate rate-cost proportional fair share of CPU to NFs and significantly improves NF performance (throughput and latency) by reducing wasted work across an NF chain, compared to using the default OS scheduler. NFVnice achieves this even for heterogeneous NFs with vastly different computational costs and for heterogeneous workloads. [ABSTRACT FROM AUTHOR]

To fully utilize the resources of a main memory database cluster, we additionally take the independent parallelism into account to parallelize multiple pipelines of one query. However, scheduling resources to multiple pipelines is an intractable problem. Traditional static approaches to this problem may lead to a serious waste of resources and suboptimal execution order of pipelines, because it is hard to predict the actual data distribution and fluctuating workloads at compile time. In response, we propose a dynamic scheduling algorithm, List with Filling and Preemption (LFPS), based on two novel techniques. (1) Adaptive filling improves resource utilization by issuing more extra pipelines to adaptively fill idle resource “holes” during execution. (2) Rank-based preemption strictly guarantees scheduling the pipelines on the critical path first at run time. Interestingly, the latter facilitates the former filling idle “holes” with best efforts to finish multiple pipelines as soon as possible. We implement LFPS in our prototype database system. Under the workloads of TPC-H, experiments show our work improves the finish time of parallelizable pipelines from one query up to 2.5X than a static approach and 2.1X than a serialized execution. [ABSTRACT FROM AUTHOR]

Link scheduling, i.e., which links should transmit together and for how long, has been and remains a cornerstone optimization problem in wireless networking. In minimum-time scheduling, the task is to minimize the amount of time before emptying the data demand residing at the source nodes. We derive a complete structural characterization of the solution that unifies and significantly extends the known results. First, we approach link scheduling with a general system model without restrictions on the shape of the achievable rate region. Then, we give and prove a solution characterization of optimality that is conceptually simple yet powerful. We demonstrate several applications of this characterization for analysis of optimality and problem tractability. Next, we consider a significant extension by including deadline constraints, under which optimal scheduling becomes much more complex. Yet, we show how our formulation yields a solution description for that problem as well. [ABSTRACT FROM AUTHOR]

This paper presents an application-transparent execution context for mobile operating systems that reflects the criticality of current execution on the user interactivity. We track Android / Linux system-level events including semantic syscalls, UI actions, and standard inter-process and intra-process communication interfaces that signal the initiation and propagation of interactivity-related executions. This interactive context enables new optimizations in CPU scheduling and power state management. We recognize that online resource scheduling is susceptible to inaccurate contexts—e.g., misidentifying an interactive execution as background leads to possible priority inversion by schedulers. In particular, low-level OS events such as kernel block / wake-up carry ambiguous semantics that could induce false context propagations. We selectively expose such uncertainties to the schedulers so that executions with uncertain contexts are prioritized behind interactive executions but otherwise run as fast as possible to minimize the priority inversion. We further recognize the importance of prompt propagation of the interactivity context at the earliest possible moment to facilitate immediate prioritization. We utilize the interactivity context to enable differential per-core frequency control and background workload consolidation. Experiments on a quad-core smartphone with a dozen mobile workload scenarios show that we can, on average, save 13 percent energy with only 1 percent degradation on the interactive performance. [ABSTRACT FROM AUTHOR]

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average $19.13 \times $ speedup compared to the state-of-the-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee. [ABSTRACT FROM AUTHOR]

Software-defined radio (SDR) provides stability, flexibility, and reconfigurability to radio frequency signal processing. Applied to oscillator characterization in the context of ultrastable clocks, stringent filtering requirements are defined by spurious signal or noise rejection needs. Since real-time radio frequency processing must be performed in a field-programmable array to meet timing constraints, we investigate optimization strategies to design filters meeting rejection characteristics while limiting the hardware resources required and keeping timing constraints within the targeted measurement bandwidths. The presented technique is applicable to scheduling any sequence of processing blocks characterized by a throughput, resource occupation and performance tabulated as a function of configuration characteristics, as is the case for filters with their coefficients and resolution yielding rejection and the number of multipliers. [ABSTRACT FROM AUTHOR]

General-purpose graphics processing units (GPGPUs), due to their enormous parallelism, have found ubiquitous applications in parallel computing. However, their peak power rating has also increased over the years. As a consequence, near-threshold computing (NTC) has come to the rescue. However, a severe device-level delay variability arising from process variation (PV) can significantly diminish the NTC system performance. In this article, we examine choke points—a unique device-level characteristic of PV at NTC—that can exacerbate the delays of the GPGPU parallel warps. In order to improve the NTC GPU performance, we propose a family of holistic circuit-architectural solutions, referred to as choke-point-aware warp speculator (CPAWS). CPAWS identifies the choke point-induced critical warps in GPGPU applications and improves their execution latencies. Compared to a state-of-the-art warp scheduling policy, our best scheme improves the performance and energy efficiency of an NTC GPU by ~39% and ~31%, respectively. [ABSTRACT FROM AUTHOR]

Time-sensitive networking (TSN) is a set of extended standards for the IEEE 802.3 Ethernet under development by the IEEE 802.1 TSN task group. TSN depends on two key components, scheduling and fault tolerance, to provide real-time and reliable transmission. There is a strong motivation to replace the widely used field-buses with TSNs in industrial networking applications. However, industrial network devices are typical application-specific embedded systems with limited memory resources. Time-sensitive (TS) transmission certainly prefers on-chip memory, which is even more scarce for embedded systems. As a result, it is critical for TSNs to develop memory-efficient switching techniques with scalable schedulability and elegant fault-tolerance support. This paper proposes a time-triggered switch-memory-switch (SMS) architecture for memory-efficient TSN switches. First, based on the SMS shared memory, our architecture makes it possible to statically schedule memory allocation with full utilization for TS traffic and the remaining memory for other traffic. Compared with per-port memory, the shared memory achieves a ratio of (${n^{n}}/{n!}$) (${\approx }({e^{n}}/{\sqrt {2 \pi n}}), {n\rightarrow \infty }$), where ${n}$ is the port number, in the feasible solution space under memory constraints and thus significantly improves scheduling memory ability and flexibility. Moreover, we develop a fault-tolerance scheme for reliable transmission. It facilitates a memory-efficient implementation of the popular multiline redundancy in industrial networks. The scheme is validated by five classes of memory conflicts and a case study on two-line redundancy. [ABSTRACT FROM AUTHOR]

Confronted with the challenge of high performance for applications and the restriction of hardware resources for field-programmable gate arrays (FPGAs), partial dynamic reconfiguration technology is anticipated to accelerate the reconfiguration process and alleviate the device shortage. In this paper, we propose an integrated optimization framework for task partitioning, scheduling, and floorplanning on partially dynamically reconfigurable FPGAs. The partition, schedule, and floorplan of the tasks are represented by the partitioned sequence triple (P-ST) (PS, QS, RS), where (PS, QS) is a hybrid nested sequence pair for representing the spatial and temporal partitions, as well as the floorplan, and RS is the partitioned dynamic configuration order of the tasks. The floorplanning and scheduling of task modules can be computed from the P-ST in ${O}$ (${n}^{{2}}$) time. To integrate the exploration of the scheduling and floorplanning design space, we use a simulated annealing-based search engine and elaborate a perturbation method, where a randomly chosen task module is removed from the partition sequence triple and then reinserted into a proper position selected from all the ${O}$ (${n}^{ {3}}$) possible combinations of partition, schedule and floorplan. We also prove a sufficient and necessary condition for the feasibility of the partitioning of tasks and scheduling of task configurations, and derive conditions for the feasibility of the insertion points in a P-ST. The experimental results demonstrate the efficiency and effectiveness of the proposed framework. [ABSTRACT FROM AUTHOR]

Motivated by the increasing computational capacity of wireless user equipments (UEs), e.g., smart phones, tablets, or vehicles, as well as the increasing concerns about sharing private data, a new machine learning model has emerged, namely federated learning (FL), that allows a decoupling of data acquisition and computation at the central unit. Unlike centralized learning taking place in a data center, FL usually operates in a wireless edge network where the communication medium is resource-constrained and unreliable. Due to limited bandwidth, only a portion of UEs can be scheduled for updates at each iteration. Due to the shared nature of the wireless medium, transmissions are subjected to interference and are not guaranteed. The performance of FL system in such a setting is not well understood. In this paper, an analytical model is developed to characterize the performance of FL in wireless networks. Particularly, tractable expressions are derived for the convergence rate of FL in a wireless setting, accounting for effects from both scheduling schemes and inter-cell interference. Using the developed analysis, the effectiveness of three different scheduling policies, i.e., random scheduling (RS), round robin (RR), and proportional fair (PF), are compared in terms of FL convergence rate. It is shown that running FL with PF outperforms RS and RR if the network is operating under a high signal-to-interference-plus-noise ratio (SINR) threshold, while RR is more preferable when the SINR threshold is low. Moreover, the FL convergence rate decreases rapidly as the SINR threshold increases, thus confirming the importance of compression and quantization of the update parameters. The analysis also reveals a trade-off between the number of scheduled UEs and subchannel bandwidth under a fixed amount of available spectrum. [ABSTRACT FROM AUTHOR]

In the power system parallel transient stability simulation (TSS), the parallel overhead will rise significantly with the increase in concurrency, which will seriously affect the efficiency of parallel computing. However, there are relatively few studies on the parallel overhead in the power system research field at present. In this paper, the geneses of the parallel overhead are introduced from the point of view of computer technology. The composition of the parallel overhead of the bordered block diagonal form (BBDF) method and the nested BBDF (NBBDF) method of the power system parallel TSS is analyzed. The time consumption of computing tasks and the parallel overhead of the BBDF method and the NBBDF method implemented by message passing interface (MPI) and OpenMP under different thread scheduling patterns are tested in detail in the 2383wp system and two practical power systems (13 490 node and 24 886 node). On this basis, an efficient implementation of the NBBDF method based on subnet-core mapping and mixed programming of MPI and OpenMP is suggested, which can further reduce the parallel overhead and increase the speedup ratio to more than 17x with 64 cores in the 24 886-node system. At last, some rules are summarized based on the test results. [ABSTRACT FROM AUTHOR]

Deep learning (DL) has been widely adopted in various domains of artificial intelligence (AI), achieving dramatic developments in industry and academia. Besides giant AI companies, numerous small and medium-sized enterprises, institutes, and universities (EIUs) have focused on the research and development (R&D) of DL. Considering the high cost of datacenters and high performance computing (HPC) systems, EIUs prefer adopting off-the-shelf GPU clusters as a DL R&D platform for multiple users and developers to process diverse DL workloads. In such scenarios, the scheduling of multiple DL tasks on a shared GPU cluster is both significant and challenging in terms of efficiently utilizing limited resources. Existing schedulers cannot predict the resource requirements of diverse DL workloads, leading to the under-utilization of computing resources and a decline in user satisfaction. This paper proposes GENIE, a QoS-aware dynamic scheduling framework for a shared GPU cluster, which achieves users’ QoS guarantee and high system utilization. In accordance with an exhaustive characterization, GENIE analyzes the key factors that affect the performance of DL tasks and proposes a prediction model derived from lightweight profiling to estimate the processing rate and response latency for diverse DL workloads. Based on the prediction models, we propose a QoS-aware scheduling algorithm to identify the best placements for DL tasks and schedule them on the shared cluster. Experiments on a GPU cluster and large-scale simulations demonstrate that GENIE achieves a QoS-guarantee percentage improvement of up to 67.4 percent and a makespan reduction of up to 28.2 percent, compared to other baseline schedulers. [ABSTRACT FROM AUTHOR]

In this paper, a mobile edge computing framework with multi-user computation offloading and transmission scheduling for delay-sensitive applications is studied. In the considered model, computation tasks are generated randomly at mobile users along the time. For each task, the mobile user can choose to either process it locally or offload it via the uplink transmission to the edge for cloud computing. To efficiently manage the system, the network regulator is required to employ a network-wide optimal scheme for computation offloading and transmission scheduling while guaranteeing that all mobile users would like to follow (as they may naturally behave strategically for benefiting themselves). By considering tradeoffs between local and edge computing, wireless features and noncooperative game interactions among mobile users, we formulate a mechanism design problem to jointly determine a computation offloading scheme, a transmission scheduling discipline, and a pricing rule. A queueing model is built to analytically describe the packet-level network dynamics. Based on this, we propose a novel mechanism, which can maximize the network social welfare (i.e., the network-wide performance), while achieving a game equilibrium among strategic mobile users. Theoretical and simulation results examine the performance of our proposed mechanism, and demonstrate its superiority over the counterparts. [ABSTRACT FROM AUTHOR]

In this paper, we consider the scenario in which a mobile charger (MC) periodically travels within a sensor network to recharge the sensors wirelessly. We design joint charging and scheduling schemes to maximize the Quality of Monitoring (QoM) for stochastic events, which arrive and depart according to known probability distributions of time. Information is considered captured if it is sensed by at least one sensor. We focus on two closely related research issues, i.e., how to choose the sensors for charging and decide the charging time for each of them, and how to schedule the sensors’ activation schedules according to their received energy. We formulate our problem as the maximum QoM CHArging and SchEduling problem (CHASE). We first ignore the MC's travel time and study the resulting relaxed version of the problem, which we call CHASE-R. We show that both CHASE and CHASE-R are NP-hard. For CHASE-R, we prove that it can be formulated as a submodular function maximization problem, which allows two algorithms to achieve $1/6$ 1 / 6 - and $1/(4 + \epsilon)$ 1 / (4 + ε) -approximation ratios. Then, for CHASE, we propose approximation algorithms to solve it by extending the CHASE-R results. We conduct simulations to validate our algorithm design. [ABSTRACT FROM AUTHOR]

Smart grid delivers power with two-way flows of electricity and information with the support of information and communication technologies. Electric vehicles (EVs) with rechargeable batteries can be powered by external sources of electricity from the grid, and thus charging scheduling that guides low-battery EVs to charging services is significant for service quality improvement of EV drivers. The revolution of communications and data analytics driven by massive data in smart grid brings many challenges as well as chances for EV charging scheduling, and how to schedule EV charging in a smart and resilient way has inevitably become a crucial problem. Toward this end, we in this paper leverage the techniques of software defined networking and vehicular edge computing to investigate a joint problem of fast charging station selection and EV route planning. Our objective is to minimize the total overhead from users’ perspective, including time and charging fares in the whole process, considering charging availability and electricity price fluctuation. A deep reinforcement learning (DRL) based solution is proposed to determine an optimal charging scheduling policy for low-battery EVs. Besides, in response to dynamic EV charging, we further develop a resilient EV charging strategy based on incremental update, with EV drivers’ user experience being well considered. Extensive simulations demonstrate that our proposed DRL-based solution obtains near-optimal EV charging overhead with good adaptivity, and the solution with incremental update achieves much higher computation efficiency than conventional game-theoretical method in dynamic EV charging. [ABSTRACT FROM AUTHOR]

We study scheduling of computation tasks across $n$ workers in a large scale distributed learning problem with the help of a master. Computation and communication delays are assumed to be random, and redundant computations are assigned to workers in order to tolerate stragglers. We consider sequential computation of tasks assigned to a worker, while the result of each computation is sent to the master right after its completion. Each computation round, which can model an iteration of the stochastic gradient descent (SGD) algorithm, is completed once the master receives $k$ distinct computations, referred to as the computation target. Our goal is to characterize the average completion time as a function of the computation load, which denotes the portion of the dataset available at each worker, and the computation target. We propose two computation scheduling schemes that specify the tasks assigned to each worker, as well as their computation schedule, i.e., the order of execution. Assuming a general statistical model for computation and communication delays, we derive the average completion time of the proposed schemes. We also establish a lower bound on the minimum average completion time by assuming prior knowledge of the random delays. Experimental results carried out on Amazon EC2 cluster show a significant reduction in the average completion time over existing coded and uncoded computing schemes. It is also shown numerically that the gap between the proposed scheme and the lower bound is relatively small, confirming the efficiency of the proposed scheduling design. [ABSTRACT FROM AUTHOR]

A new random channel access framework, named as zigzag-division multiple access (ZDMA), is proposed for wireless networks with long and heterogeneous propagation delays to achieve system throughput significantly larger than 1. The key idea is to allow simultaneous transmissions at the transmitters and employ zigzag decoding at the receiver. After studying the zigzag decoding, we present three new random access protocols. Extensive numerical studies show that incorporating ZDMA in existing slotted Aloha and tree splitting protocols can significantly increase system throughput. The third protocol of greedy scheduling with ZDMA achieves the highest throughput performance. [ABSTRACT FROM AUTHOR]