Speech-language models (SLMs) offer a promising path toward unifying speech and text understanding and generation. However, challenges remain in achieving effective cross-modal alignment and high-quality speech generation. In this work, we systematically investigate the role of speech tokenizer designs in LLM-centric SLMs, augmented by speech heads and speaker modeling. We compare coupled, semi-decoupled, and fully decoupled speech tokenizers under a fair SLM framework and find that decoupled tokenization significantly improves alignment and synthesis quality. To address the information density mismatch between speech and text, we introduce multi-token prediction (MTP) into SLMs, enabling each hidden state to decode multiple speech tokens. This leads to up to 12× faster decoding and a substantial drop in word error rate (from 6.07 to 3.01). Furthermore, we propose a speaker-aware generation paradigm and introduce RoleTriviaQA, a large-scale role-playing knowledge QA benchmark with diverse speaker identities. Experiments demonstrate that our methods enhance both knowledge understanding and speaker consistency.

Artificial intelligence (AI) has been increasingly applied to gaming, with large language models (LLMs) playing a key role in character control. However, efficiently co-locating game rendering and LLM inference on one GPU presents challenges due to resource constraints, diverse latency requirements, and fine-grained task scheduling. We propose LEGO, an algorithm-system co-design that enables the efficient co-location of LLM inference and game rendering tasks. Algorithmwise, LEGO features a resource-oriented layer-skipping adaptor, which distills knowledge from skipped layers to reduce computational demand while maintaining inference accuracy. System-wise, LEGO proposes a headroom-maximizing LLM scheduler, which dynamically partitions inference tasks to utilize available rendering headroom. Evaluations on an Nvidia RTX 4090 show that LEGO meets latency targets in all scenarios, improves rendering headroom utilization by up to 28.6 %, and reduces LLM inference accuracy loss by up to 86.3 % compared to current layer-skipping approaches.

Applications based on Large Language Models (LLMs) contain a series of tasks to address real-world problems with boosted capability, which have dynamic demand volumes on diverse backends. Existing serving systems treat the resource demands of LLM applications as a blackbox, compromising end-to-end efficiency due to improper queuing order and backend warm up latency. We find that the resource demands of LLM applications can be modeled in a general and accurate manner with Probabilistic Demand Graph (PDGraph). We then propose Hermes, which leverages PDGraph for efficient serving of LLM applications. Confronting probabilistic demand description, Hermes applies the Gittins policy to determine the scheduling order that can minimize the average application completion time. It also uses the PDGraph model to help prewarm cold backends at proper moments. Experiments with diverse LLM applications confirm that Hermes can effectively improve the application serving efficiency, reducing the average completion time by over 70% and the P95 completion time by over 80%.

Transformer-based Large Language Models (LLMs) have become increasingly important. However, scaling LLMs to longer contexts incurs slow inference speed and high GPU memory consumption for caching key-value (KV) vectors. This paper presents RetrievalAttention, a training-free approach to both accelerate the decoding phase and reduce GPU memory consumption by pre-building KV vector indexes for fixed contexts and maintaining them in CPU memory for efficient retrieval. Unlike conventional KV cache methods, RetrievalAttention integrate approximate nearest neighbor search (ANNS) indexes into attention computation. We observe that off-the-shelf ANNS techniques often fail due to the out-of-distribution (OOD) nature of query and key vectors in attention mechanisms. RetrievalAttention overcomes this with an attention-aware vector index. Our evaluation shows RetrievalAttention achieves near full attention accuracy while accessing only 1-3\% of the data, significantly reducing inference costs. Remarkably, RetrievalAttention enables LLMs with 8B parameters to handle 128K tokens on a single NVIDIA RTX4090 (24GB), achieving a decoding speed of 0.107 seconds per token.

Integrating GPUs into serverless computing platforms is crucial for improving efficiency. Many GPU functions, such as DNN inferences and scientific services, benefit from GPU usage, which requires only tens to hundreds of milliseconds for pure computation. Under these circumstances, fast data loading is imperative for function performance. However, existing GPU serverless systems face significant data stall issues, leading to extremely low GPU efficiency. Faced with the above problems, we observe opportunities to optimize data loading, such as data preloading and deduplicated data loading. However, these optimizations are impossible in existing GPU serverless systems due to the lack of insights into data information, such as data sizes and read-write attributes of function inputs. To address this, we propose a novel GPU serverless system, EDAS. EDAS first enhances user request specifications, allowing users to annotate data retrieved by GPU functions from the database with additional attributes. Based on this, EDAS takes over data loading from GPU functions and proposes two innovative data loading management schemes: a parallelized data loading scheme and a multi-stage resource exit scheme. Our experimental results show that EDAS reduces function duration by 16.2× and improves system throughput by 1.91× compared with the state-of-the-art serverless platform.

In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing file to the local cache can be significant. Recent studies have revealed that successive requests for the same missing file before the fetching process completes could still suffer latency (so-called delayed hits). Motivated by the practical scenarios, we study the online general file caching problem with delayed hits and bypassing,i.e., a request may be bypassed and processed directly at the remote data center. The objective is to minimize the total request latency. We present a general reduction that turns a traditional file caching algorithm into one that can handle delayed hits. Based on this reduction, we propose an efficient online file caching algorithm, calledCaLa, with an asymptotically tight competitive ratio as$O(Z \log K)$, whereZis the maximum fetching latency of any file andKis the cache size. Extensive simulations on the production data trace from Google and the Yahoo benchmark illustrate thatCaLacan reduce the latency by up to 8.48% compared with the state-of-the-art schemes dealing with delayed hits without bypassing, and this improvement increases to 26.00% if bypassing is allowed. Furthermore, by upgrading the method for estimating files’ weights inCaLa, we proposeCaLa+, which further reduces the total latency by more than 5%.

Serverless edge computing is an efficient way to execute event-driven, short-duration, and bursty IoT data processing tasks on resource-limited edge servers, using on-demand resource allocation and dynamic auto-scaling. In this paradigm, function requests are handled in virtualized environments,e.g., containers. When a function request arrives online, if there is no container in memory to execute it, the serverless platform will initialize such a container with non-negligible latency, known as cold start. Otherwise, it results in a warm start with no latency in previous studies. However, based on our experiments, we find there is a remarkable third case called Late-Warm,i.e., when a request arrives during the container initializing, its latency is less than a cold start but not zero. In this paper, we study online container caching in serverless edge computing to minimize the total latency with Late-Warm and other practical issues considered. We proposeOnCoLa, a novel$O(T_{c}K)$-competitive algorithm supporting request relaying on multiple edge servers. Here,$T_{c}$and$K$are the maximum container cold start latency and the memory size, respectively. Extensive simulations on two real-world traces demonstrate thatOnCoLaconsistently outperforms the state-of-the-art container caching algorithms and reduces the latency by$23.33\%$. Experiments on Raspberry Pi and Jetson Nano show thatOnCoLareduces latency by up to$21.38\%$compared with the representative lightweight policy.

Serverless edge computing is an efficient way to execute event-driven, short-duration, and bursty IoT data processing tasks on resource-limited edge servers, using on-demand resource allocation and dynamic auto-scaling. In this paradigm, function requests are handled in virtualized environments, e.g., containers. When a function request arrives online, if there is no container in memory to execute it, the serverless platform will initialize such a container with non-negligible latency, known as cold start. Otherwise, it results in a warm start with no latency in previous studies. However, based on our experiments, we find there is a remarkable third case called Late-Warm, i.e., when a request arrives during the container initializing, its latency is less than a cold start but not zero. In this paper, we study online container caching in serverless edge computing to minimize the total latency with Late-Warm and other practical issues considered. We propose OnCoLa, a novel$O(T_{c}^{3}/2K)$-competitive algorithm supporting request relaying on multiple edge servers. Here, Tc and$K$are the maximum container cold start latency and the memory size, respectively. Experiments on Raspberry Pi and Jetson Nano with OpenFaaS and faasd using common IoT data processing tasks show that OnCoLa reduces latency by up to 21.38% compared with representative lightweight policies. Extensive simulations on two real-world traces demonstrate that OnCoLa consistently outperforms the state-of-the-art container caching algorithms and reduces the latency by 27.8%.

The computational challenges of Large Language Model (LLM) inference remain a significant barrier to their widespread deployment, especially as prompt lengths continue to increase. Due to the quadratic complexity of the attention computation, it takes 30 minutes for an 8B LLM to process a prompt of 1M tokens (i.e., the pre-filling stage) on a single A100 GPU. Existing methods for speeding up prefilling often fail to maintain acceptable accuracy or efficiency when applied to long-context LLMs. To address this gap, we introduce MInference (Milliontokens Inference), a sparse calculation method designed to accelerate pre-filling of long-sequence processing. Specifically, we identify three unique patterns in long-context attention matrices-the A-shape, Vertical-Slash, and Block-Sparse-that can be leveraged for efficient sparse computation on GPUs. We determine the optimal pattern for each attention head offline and dynamically build sparse indices based on the assigned pattern during inference. With the pattern and sparse indices, we perform efficient sparse attention calculations via our optimized GPU kernels to significantly reduce the latency in the pre-filling stage of longcontext LLMs. Our proposed technique can be directly applied to existing LLMs without any modifications to the pre-training setup or additional fine-tuning. By evaluating on a wide range of downstream tasks, including InfiniteBench, RULER, PG-19, and Needle In A Haystack, and models including LLaMA-3-1M, GLM-4-1M, Yi-200K, Phi-3-128K, and Qwen2-128K, we demonstrate that MInference effectively reduces inference latency by up to 10x for pre-filling on an A100, while maintaining accuracy. Our code is available at https://aka.ms/MInference.

Online video streaming has fundamental limitations on the transmission bandwidth and computational capacity and super-resolution is a promising potential solution. However, applying existing video super-resolution methods to online streaming is non-trivial. Existing video codecs and streaming protocols (e.g., WebRTC) dynamically change the video quality both spatially and temporally, which leads to diverse and dynamic degradations. Furthermore, online streaming has a strict requirement for latency that most existing methods are less applicable. As a result, this paper focuses on the rarely exploited problem setting of online streaming video super resolution. To facilitate the research on this problem, a new benchmark dataset named LDV-WebRTC is constructed based on a real-world online streaming system. Leveraging the new benchmark dataset, we propose a novel method specifically for online video streaming, which contains a convolution and Look-Up Table (LUT) hybrid model to achieve better performance-latency trade-off. To tackle the changing degradations, we propose a mixture-of-expert-LUT module, where a set of LUT specialized in different degradations are built and adaptively combined to handle different degradations. Experiments show our method achieves 720P video SR around 100 FPS, while significantly outperforms existing LUT-based methods and offers competitive performance compared to efficient CNN-based methods. Code is available at https://github.com/quzefan/ConvLUT.

Deep neural network (DNN) foundation models are currently exhibiting high prediction accuracy and strong adaptability to broad tasks with remarkably large model scales. They are increasingly becoming the backend support of DNN-driven real-time online services, e.g., Siri and Instagram. Such services require low-latency and cost-efficiency for quality-of-service and commercial competitiveness. When deployed in a cloud environment, these services call for an appropriate selection of cloud configurations (i.e., specific types of VM instances), as well as a considerate device placement plan that places the operations of the model to multiple GPUs via model parallelism for cost-efficiency. Currently, the deployment mainly relies on service providers’ manual efforts, which is not only onerous but also far from satisfactory oftentimes due to the huge joint search space of cloud configurations and device placement plans (for a same service, a poor deployment can incur significantly more costs by tens of times). In this paper, we attempt to efficiently automate the cloud deployment for real-time foundation model inference with minimum costs under the constraint of acceptably low latency. This attempt is enabled by 1) jointly leveraging the Bayesian Optimization and Deep Reinforcement Learning to adaptively unearth the (nearly) optimal cloud configuration and device placement with limited search time, and 2) enhancing the cost-efficiency of the deployment based on the probing-informed block multiplexing mechanism and Tensor Algebra SuperOptimizer. We implement a prototype system based on TensorFlow, conduct extensive experiments on top of Microsoft Azure, and demonstrate the generality and scalability of our solution. Results show that for lightweight DNN models and foundation models, our solution essentially saves inference costs by up to 15% and 47% with 57% and 38% lower search overheads respectively, compared with non-trivial baselines.

In Mobile Edge Computing, edge servers have limited storage and computing resources that can only support a small number of functions. Meanwhile, mobile applications are becoming more complex, consisting of multiple dependent tasks, modeled as a Directed Acyclic Graph (DAG). When a request arrives, typically in an online manner with a deadline specified, we need to configure the servers and assign the dependent tasks for efficient processing. This work jointly considers the problem of dependent task placement and scheduling with on-demand function configuration on edge servers, aiming to meet as many deadlines as possible. For a single request, when the configuration on each edge server is fixed, we derive FixDoc to find the optimal task placement and scheduling. When the on-demand function configuration is allowed, we propose GenDoc , a novel approximation algorithm, and analyze its additive error from the optimal theoretically. For multiple requests, we derive OnDoc , an online algorithm easy to deploy in practice. Our extensive experiments show that GenDoc outperforms state-of-the-art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24%. The number of deadlines that OnDoc can satisfy is at least 1.9× that of the baselines.

This paper proposes ElasticFlow, an elastic serverless training platform for distributed deep learning. ElasticFlow provides a serverless interface with two distinct features: (i) users specify only the deep neural network (DNN) model and hyperparameters for a job, but not the number of GPUs; (ii) users specify the deadline for a job, but not the amount of time to occupy GPUs. In contrast to existing server-centric platforms, ElasticFlow provides performance guarantees in terms of meeting deadlines while alleviating tedious, low-level, and manual resource management for deep learning developers. The characteristics of distributed training introduce two challenges. First, the training throughput scales non-linearly with the number of GPUs. Second, the scaling efficiency is affected by worker placement. To address these challenges, we propose Minimum Satisfactory Share to capture the resource usage of training jobs to meet deadlines, and ElasticFlow performs admission control based on it. We develop a greedy algorithm that dynamically allocates resources to admitted jobs based on diminishing returns. We apply buddy allocation to worker placement to eliminate the effect of topology. Evaluation results on a cluster of 128 GPUs show that ElasticFlow increases the number of jobs that can meet their deadlines by 1.46–7.65× compared to existing solutions.

Deep learning training on cloud platforms usually follows the tradition of the separation of storage and computing. The training executes on a compute cluster equipped with GPUs/TPUs while reading data from a separate cluster hosting the storage service. To alleviate the potential bottleneck, a training cluster usually leverages its local storage as a cache to reduce the remote IO from the storage cluster. However, existing deep learning schedulers do not manage storage resources thus fail to consider the diverse caching effects across different training jobs. This could degrade scheduling quality significantly.

The separation of compute and storage in modern cloud services eases the deployment of general applications. However, with the development of accelerators such as GPU/TPU, Deep Learning (DL) training is suffering from potential IO bottlenecks when loading data from storage clusters. Therefore, DL training jobs need to either create local cache in the compute cluster to reduce the bandwidth demands or scale up the IO capacity with higher bandwidth cost. It is full of challenges to choose the best strategy due to the heterogeneous cache/IO preference of DL models, shared dataset among multiple jobs and dynamic GPU scaling of DL training. In this work, we exploit the job characteristics based on their training throughput, dataset size and scalability. For fixed GPU allocation of jobs, we propose CBA to minimize the training cost with a closed-form approach. For clusters that can automatically scale the GPU allocations of jobs, we extend CBA to AutoCBA to support diverse job utility functions and improve social welfare within a limited budget. Extensive experiments with production traces validate that CBA and AutoCBA can reduce IO cost and improve total social welfare by up to 20.5% and 2.27×, respectively, over the state-of-the-art schedulers for DL training.

Dynamic sparsity, where the sparsity patterns are unknown until runtime, poses a significant challenge to deep learning. The state-of-the-art sparsity-aware deep learning solutions are restricted to pre-defined, static sparsity patterns due to significant overheads associated with preprocessing. Efficient execution of dynamic sparse computation often faces the misalignment between the GPU-friendly tile configuration for efficient execution and the sparsity-aware tile shape that minimizes coverage wastes (non-zero values in tensor).

Summary Seismic P‐wave first arrival picking is one of the critical problems in seismic source research. At present, the picking of seismic P‐wave first arrival mainly relies on the combination of traditional methods and manual picking. However, traditional algorithms have poor picking performance and low manual picking efficiency, which cannot meet the needs of research and application. Based on the deep learning network InceptionResNet‐V2, this paper proposes an improved network (EQK‐IncResNet) that can be used for seismic P‐wave first arrival picking. Compared with traditional methods, this model does not need to set the threshold manually and only needs to input the three‐component data of the seismic waveform data to intelligently identify the first‐arrival of the seismic P‐wave. This model has a lightweight structure and excellent feature extraction capabilities, which can effectively identify low signal‐to‐noise ratio data. The experimental results show that within the error thresholds of 0.1, 0.3, and 0.5 s, the hit rate of this method is 74.45%, 96.79%, and 98.68%, respectively. The average picking error is 0.031 s, which is better than the traditional methods such as AR‐AIC + STA/LTA and the mainstream deep learning methods such as GRU.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous studies in edge computing mainly focused on optimizing a single utility function across all jobs, e.g., linear, sigmoid, or the hard deadline. In this paper, we design online job dispatching and scheduling strategies in which different jobs can be categorized by different non-increasing utility functions. Our goal is to maximize the total utility of all scheduled jobs. We first prove that no online deterministic algorithm could achieve a competitive ratio better than the lower bound$\Omega \left({\frac {1}{\sqrt {\epsilon }}}\right)$under the$(1+\epsilon)$-speed augmentation model. We proceed to propose an online algorithm, named asO4A, for handling jobs with heterogeneous utilities. We prove thatO4Ais$O\left({\frac {1}{\epsilon ^{2}}}\right)$-competitive. We also design its distributed version, i.e.,DO4A. We implementO4AandDO4Aon an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate thatO4Acan increase the total utility by up to 50% compared with state-of-the-art methods. Besides, the performance loss ofDO4Ais only 2% compared withO4Awith a small communication overhead involved. Moreover, both of our algorithms are robust to estimation errors in job processing time and transmission delay.

In latency-sensitive file caching systems such as Content Delivery Networks (CDNs) and Mobile Edge Computing (MEC), the latency of fetching a missing file to the local cache can be significant. Recent studies have revealed that successive requests of the same missing file before the fetching completes could still suffer latency (so-called delayed hits).Motivated by the practical scenarios, we study the online general file caching problem with delayed hits and bypassing, i.e., a request may be bypassed and processed directly at the remote data center. The objective is to minimize the total request latency. We show a general reduction that turns a traditional file caching algorithm to one that can handle delayed hits. We give an O(Z3/2logK)-competitive algorithm called CaLa with this reduction, where Z is the maximum fetching latency of any file and K is the cache size, and we show a nearly-tight lower bound Ω(Z logK) for our ratio. Extensive simulations based on the production data trace from Google and the Yahoo benchmark illustrate that CaLa can reduce the latency by up to 9.42% compared with the state-of-the-art scheme dealing with delayed hits without bypassing, and this improvement increases to 32.01% if bypassing is allowed.

Job dispatching is a fundamental problem in edge computing for load balancing among multiple edge servers. When implementing an edge computing system with distributed job dispatchers in a sizable network, such as a metropolitan area network (MAN), the highly dynamic transmission latency is nonnegligible, which could lead to outdated information being shared. Moreover, the fully observed system state is beyond reach as the reception of any broadcast is time consuming. In this article, we investigate the online distributed job dispatching problem in edge computing, where multiple access points (APs) collect jobs and then dispatch each job to an edge server. The distributed dispatcher on each AP would receive partially and outdated information exchanged via periodic broadcast. Hence, we formulate the distributed job dispatching problem by leveraging the partially observable Markov decision process (POMDP) and propose a novel approximate Markov decision process (MDP) solution framework, calledDecMDP, that bypasses the huge time complexity of conventional POMDP solutions. Both analytical and semi-analytical performance lower bounds are derived for the approximate MDP solution. Furthermore, we extendDecMDPto handle a more general scenario wherea prioriknowledge of the system is absent. Finally, extensive simulations based on the Google Cluster traces show that our policy can achieve the best performance when compared with heuristic baselines, e.g., achieving 20.67% reduction in average job response time, and consistently performs well under various parameter settings.

Heterogeneous cellular networks (HetNets), where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs), can significantly improve the spectrum efficiency by Pico- and Macro base station collaboration. Due to cross-tier interference, joint detection of uplink signals is widely adopted so that Pico-BS can either detect the uplink signals locally or forward them to Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process. We propose an efficient algorithm, calledOLIUS, that can deal with the exponentially growing state and action space. Furthermore,OLIUSis online learning-based which does not require any prior knowledge on user behavior or channel characteristics. We prove the convergence ofOLIUSand derive an upper bound on its approximation error. Extensive experiments in various scenarios show our algorithm outperforms existing methods in reducing delay and power consumption.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently due to the popularity of computations as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we deriveSPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present howSPINsolves it with a rounding-based randomized approximation approach. Our analysis indicatesSPINachieves a good performance guarantee efficiently. Moreover,SPINis robust against misestimation of job execution time by theoretically bounding its negative impact. We implementSPINon a production-trace driven testbed with 40 GPUs. Our extensive experiments show thatSPINcan reduce the job makespan and the average job completion time by up to$3\times $and$4.68\times $, respectively.SPINalso demonstrates better robustness to execution time misestimation compared with state-of-the-art heuristic baselines.

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We can also choose to fetch files from the memory to caches and conduct file replacement if necessary. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform costs. We propose an O(logK)-competitive randomized online multiple caching algorithm (named Camul) and an O(K)-competitive deterministic algorithm (named Camul-Det), where K is the total number of slots in all caches. Both of them achieve asymptotically optimal competitive ratios. Moreover, our algorithms can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform state-of-the-art schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and performs consistently well on various settings of experiment parameters.

To improve the application-level data efficiency, the scheduling of coflows, defined as a collection of parallel flows sharing the same objective, is prevailing in recent data centers. Meanwhile, optical circuit switches (OCS) are gradually applied to provide high data rate with low power consumption. However, so far few research outputs have covered the flow, let alone the coflow, scheduling in the context of OCS. In this work, we investigate coflow scheduling in OCS-based data centers. We first derive a novel operation called regularization processed respectively on the flow traffic demands and the flow start times, which can be efficiently implemented and reduce the circuit reconfiguration frequency dramatically. We then propose a 2-approximation algorithm, called Reco-Sin, for single coflow scheduling to minimize the coflow completion time (CCT). For multiple coflows, we derive Reco-Mul to minimize the total weighted CCT, which can transform any non-preemptive multi-coflow scheduling in packet switches to a scheduling scheme in OCS. Reco-Mul can achieve a constant approximation under the assumption that no tiny flows will be transmitted in OCS. To get rid of this assumption, we present another multiple coflow scheduling scheme, named Reco-Mul+, which has an approximation ratio of O(K). Here, K is the total number of coflows. Extensive simulations based on Facebook data traces show that our approaches outperform state-of-the-art schemes significantly, i.e., one single coflow can be finished up to 1.97× faster with Reco-Sin, and multiple coflows can be completed up to more than 2× faster with Reco-Mul and Reco-Mul+.

The Bulk Synchronous Parallel (BSP) paradigm is gaining tremendous importance recently because of the pop-ularity of computations such as distributed machine learning and graph computation. In a typical BSP job, multiple workers concurrently conduct iterative computations, where frequent synchronization is required. Therefore, the workers should be scheduled simultaneously and their placement on different computing devices could significantly affect the performance. Simply retrofitting a traditional scheduling discipline will likely not yield the desired performance due to the unique characteristics of BSP jobs. In this work, we derive SPIN, a novel scheduling designed for BSP jobs with placement-sensitive execution to minimize the makespan of all jobs. We first prove the problem approximation hardness and then present how SPIN solves it with a rounding-based randomized approximation approach. Our analysis indicates SPIN achieves a good performance guarantee efficiently. Moreover, SPIN is robust against misestimation of job execution time by theoretically bounding its negative impact. We implement SPIN on a production-trace driven testbed with 40 GPUs. Our extensive experiments show that SPIN can reduce the job makespan and the average job completion time by up to 3× and 4.68×, respectively. Our approach also demonstrates better robustness to execution time misestimation compared with heuristic baselines.

Real-time online services using pre-trained deep neural network (DNN) models, e.g., Siri and Instagram, require low-latency and cost-efficiency for quality-of-service and commercial competitiveness. When deployed in a cloud environment, such services call for an appropriate selection of cloud configurations (i.e., specific types of VM instances), as well as a considerate device placement plan that places the operations of a DNN model to multiple computation devices like GPUs and CPUs. Currently, the deployment mainly relies on service providers' manual efforts, which is not only onerous but also far from satisfactory oftentimes (for a same service, a poor deployment can incur significantly more costs by tens of times). In this paper, we attempt to automate the cloud deployment for real-time online DNN inference with minimum costs under the constraint of acceptably low latency. This attempt is enabled by jointly leveraging the Bayesian Optimization and Deep Reinforcement Learning to adaptively unearth the (nearly) optimal cloud configuration and device placement with limited search time. We implement a prototype system of our solution based on TensorFlow and conduct extensive experiments on top of Microsoft Azure. The results show that our solution essentially outperforms the nontrivial baselines in terms of inference speed and cost-efficiency.

Edge computing systems typically handle a wide variety of applications that exhibit diverse degrees of sensitivity to job latency. Therefore, a multitude of utility functions of the job response time need to be considered by the underlying job dispatching and scheduling mechanism. Nonetheless, previous works in edge computing mainly focused on either one kind of utility function (e.g., linear, sigmoid, or the hard deadline) or different kinds of utilities separately. In this paper, we investigate online job dispatching and scheduling strategies under the setting of coexistence of heterogeneous utilities, i.e., various coexisting jobs can employ different non-increasing utility functions. The goal is to maximize the total utility over all jobs in an edge system. Besides heterogeneous utilities, we here adopt a practical online model where the unrelated machine model and the upload and download delay are considered. We proceed to propose an online algorithm, O4A, to dispatch and schedule jobs with heterogeneous utilities. Our theoretical analysis shows that O4A is O(1/ɛ2)-competitive under the (1 + ɛ)-speed augmentation model, where ɛ is a small positive constant. We implement O4A on an edge computing testbed running deep learning inference jobs. With the production trace from Google Cluster, our experimental and large-scale simulation results indicate that O4A can increase the total utility by up to 39.42% compared with state-of-the-art utility-agnostic methods. Moreover, O4A is robust to estimation errors in job processing time and transmission delay.

In this paper, we investigate online distributed job dispatching in an edge computing system residing in a Metropolitan Area Network (MAN). Specifically, job dispatchers are implemented on access points (APs) which collect jobs from mobile users and distribute each job to a server at the edge or the cloud. A signaling mechanism with periodic broadcast is introduced to facilitate cooperation among APs. The transmission latency is non-negligible in MAN, which leads to outdated information sharing among APs. Moreover, the fully-observed system state is discouraged as reception of all broadcast is time consuming. Therefore, we formulate the distributed optimization of job dispatching strategies among the APs as a Markov decision process with partial and outdated system state, i.e., partially observable Markov Decision Process (POMDP). The conventional solution for POMDP is impractical due to huge time complexity. We propose a novel low-complexity solution framework for distributed job dispatching, based on which the optimization of job dispatching policy can be decoupled via an alternative policy iteration algorithm, so that the distributed policy iteration of each AP can be made according to partial and outdated observation. A theoretical performance lower bound is proved for our approximate MDP solution. Furthermore, we conduct extensive simulations based on the Google Cluster trace. The evaluation results show that our policy can achieve as high as 20.67% reduction in average job response time compared with heuristic baselines, and our algorithm consistently performs well under various parameter settings.

In this article, we study online deadline-aware task dispatching and scheduling in edge computing. We jointly considerthe management of the networking and computing resources to meet the maximum number of deadlines. We propose an online algorithm, named Dedas, which greedily schedules newly arriving tasks and considers whether to replace some existing tasks in order to make the new deadlines satisfied. We derive a non-trivial competitive ratio of Dedas theoretically, and our analysis is asymptotically tight. Besides, we implement a distributed approximation D - Dedas with a better scalability and less than 10 percent performance loss compared with the centralized algorithm Dedas. We then build DeEdge, an edge computing testbed installed with typical latency-sensitive applications such as IoT sensor monitoring and face matching. We adopt a real-world data trace from the Google cluster for large-scale emulations. Extensive testbed experiments and simulations demonstrate that the deadline miss ratio of Dedas is stable for online tasks, which is reduced by up to 60 percent compared with state-of-the-art methods. Moreover, Dedas performs well in minimizing the average task completion time.

Motivated by practical scenarios in areas such as Mobile Edge Computing (MEC) and Content Delivery Networks (CDNs), we study online file caching on multiple caches, where a file request might be relayed to other caches or bypassed directly to the memory when a cache miss happens. We take the relaying, bypassing and fetching costs altogether into consideration. We first show the inherent difficulty of the problem even when the online requests are of uniform cost. We propose an O(log K)-competitive randomized algorithm Camul and an O(K)-competitive deterministic algorithm Camul-Det, where K is the total number of slots in all caches. Both online algorithms achieve asymptotically optimal competitive ratios, and can be implemented efficiently such that each request is processed in amortized constant time. We conduct extensive simulations on production data traces from Google and a benchmark workload from Yahoo. It shows that our algorithms dramatically outperform existing schemes, i.e., reducing the total cost by 85% and 43% respectively compared with important baselines and their strengthened versions with request relaying. More importantly, Camul achieves such a good total cost without sacrificing other performance measures, e.g., the hit ratio, and can perform consistently well on various settings of experiment parameters.

In Mobile Edge Computing (MEC), each edge server can be configured with only a small number of functions due to the limited capacity of various resources. Meanwhile, mobile applications become more complicated, consisting of multiple dependent tasks which are typically modeled as a Directed Acyclic Graph (DAG). In edge computing, when an application arrives, we need to place and schedule its tasks onto edge servers and/or the remote cloud, where the functions to execute the tasks are configured. In this work, we jointly consider the problem of dependent task placement and scheduling with on-demand function configuration on servers. Our objective is to minimize the application completion time. Specifically, for the special case when the configuration on each edge server is fixed, we derive an algorithm to find the optimal task placement and scheduling efficiently. When the on-demand function configuration is allowed, we propose a novel approximation algorithm, named GenDoc, and analyze theoretically its additive error from the optimal solution. Our extensive experiments on the cluster trace from Alibaba (including 20365 unique applications with DAG information) show that GenDoc outperforms state-of-the-art baselines in processing 86.14% of these unique applications, and reduces their average completion time by at least 24% (and up to 54%). Moreover, GenDoc consistently performs well on various settings of key parameters.

In edge-cloud computing, a set of servers (called edge servers) are deployed near the mobile devices to allow these devices to offload their jobs to and subsequently obtain their results from the edge servers with low latency. One fundamental problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of the job and the arrival of the computation result at the device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and at arbitrary times at the mobile devices and then offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time of all the jobs. The weight is set based on how latency-sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any small constant ε > 0. Moreover, OnDisc can be easily implemented in distributed systems. We also extend OnDisc with a fairness knob to incorporate the trade-off between the average job response time and the degree of fairness among jobs. Extensive simulations based on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs’ resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs’ resource demands. Most approaches in the latter category are heuristic and lack theoretical performance guarantees. In this paper, we formulate the dynamic VM management as a large-scale Markov decision process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, we show that MadVM can be implemented in a distributed system with at most two times of the optimal migration cost. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage, and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage computing task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the total weighted coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources, such as link bandwidth. To minimize the total weighted CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow. We then derive a competitive ratio bound of our problem and prove that the competitive ratio of OMCoflow is nearly tight. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently and avoids frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OMCoflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the total weighted CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER).

Deep learning (DL) is popular in data-center as an important workload for artificial intelligence. With the recent breakthrough of using graphics accelerators and the popularity of DL framework, GPU server cluster dominates DL training in current practice. Cluster scheduler simply treats DL jobs as black-boxes and allocates GPUs as per job request specified by a user. However, other resources, e.g. CPU, are often allocated with workload-agnostic approaches. Kubeflow[1] performs heuristic static CPU resource assignment based on task types (e.g., worker, parameter-server), while [2] evenly divides CPUs of a server to each GPU. Despite the traditional impression that GPU is critical in DL, our observation suggests that the importance of CPU is undervalued. Identifying an appropriate CPU core number in a heterogeneous cluster is challenging yet performance critical to DL jobs. The diverse CPU usage characteristic is not well recognized in the following three aspects.

Heterogeneous cellular networks (HetNets) can significantly improve the spectrum efficiency, where low-power low-complexity base stations (Pico-BSs) are deployed inside the coverage of macro base stations (Macro-BSs). Due to cross-tier interference, joint detection of the uplink signals is widely adopted so that a Pico-BS can either detect the uplink signals locally or forward them to the Macro-BS for processing. The latter can achieve increased throughput at the cost of additional backhaul transmission. However, in existing literature the delay of the backhaul links was often neglected. In this paper, we study the delay-optimal uplink scheduling problem in HetNets with limited backhaul capacity. Local signal detection or joint signal detection is scheduled in a unified delay-optimal framework. Specifically, we first prove that the problem is NP-hard and then formulate it as a Markov Decision Process problem. We propose an efficient and effective algorithm, called OLIUS, that can deal with the exponentially growing state and action spaces. Furthermore, OLIUS is online learning based which does not require any prior statistical knowledge on user behavior or channel characteristics. We prove the convergence of OLIUS and derive an upper bound on its approximation error. Extensive experiments in various scenarios show that our algorithm outperforms existing methods in reducing delay and power consumption.

In edge-cloud computing, a set of edge servers are deployed near the mobile devices such that these devices can offload jobs to the servers with low latency. One fundamental and critical problem in edge-cloud systems is how to dispatch and schedule the jobs so that the job response time (defined as the interval between the release of a job and the arrival of the computation result at its device) is minimized. In this paper, we propose a general model for this problem, where the jobs are generated in arbitrary order and times at the mobile devices and offloaded to servers with both upload and download delays. Our goal is to minimize the total weighted response time over all the jobs. The weight is set based on how latency sensitive the job is. We derive the first online job dispatching and scheduling algorithm in edge-clouds, called OnDisc, which is scalable in the speed augmentation model; that is, OnDisc is (1 + ε)-speed O(1/ε)-competitive for any constant ε ϵ (0,1). Moreover, OnDisc can be easily implemented in distributed systems. Extensive simulations on a real-world data-trace from Google show that OnDisc can reduce the total weighted response time dramatically compared with heuristic algorithms.

Motivated by practical scenarios, we study congestion games with failures. We investigate two models. The first model is congestion games with both resource and agent failures, where each agent chooses the same number of resources with the minimum expected cost. We prove that the game is potential and hence admits at least one pure-strategy Nash equilibrium (pure-NE). We also show that the Price of Anarchy and the Price of Stability are bounded (equal to 1 in some cases). The second model is congestion games with only resource failures (CG-CRF), where resources are provided in packages, and their failures can be correlated with each other. Each agent can choose multiple packages for reliability’s sake and utilize the survived one having the minimum cost. CG-CRF is shown to be not potential. We prove that it admits at least one pure-NE by constructing one efficiently. Finally, we discuss various applications of these two games in the networking field. To the best of our knowledge, this is the first paper studying congestion games with the coexistence of resource and agent failures, and we give also the first proof of the existence of a pure-NE in congestion games with correlated package failures.

Efficient virtual machine (VM) management can dramatically reduce energy consumption in data centers. Existing VM management algorithms fall into two categories based on whether the VMs' resource demands are assumed to be static or dynamic. The former category fails to maximize the resource utilization as they cannot adapt to the dynamic nature of VMs' resource demands. Most approaches in the latter category are heuristical and lack theoretical performance guarantees. In this work, we formulate dynamic VM management as a large-scale Markov Decision Process (MDP) problem and derive an optimal solution. Our analysis of real-world data traces supports our choice of the modeling approach. However, solving the large-scale MDP problem suffers from the curse of dimensionality. Therefore, we further exploit the special structure of the problem and propose an approximate MDP-based dynamic VM management method, called MadVM. We prove the convergence of MadVM and analyze the bound of its approximation error. Moreover, MadVM can be implemented in a distributed system, which should suit the needs of real data centers. Extensive simulations based on two real-world workload traces show that MadVM achieves significant performance gains over two existing baseline approaches in power consumption, resource shortage and the number of VM migrations. Specifically, the more intensely the resource demands fluctuate, the more MadVM outperforms.

Current large-scale computing services, such as online social networking and web searching, make the wired links in the data centers with an Ethernet infrastructure oversubscribed. Therefore, researchers consider to augment the data centers with wireless communication, called a hybrid data center network (HDCN), to improve the communication flexibility and network capacity. In this paper, we investigate how to use the wireless communication in hybrid DCNs from a cross-layer view. In the network layer, we propose a routing protocol to minimize the number of hops for data flows, and a congestion control protocol to reduce the congestion and deal with sporadic link failure. In the physical layer, we study the channel and power allocation problem with the SINR and QoS constraints in hybrid DCNs. In single channel scenarios, we prove the problem to be a geometric programming problem. In multi-channel scenarios, we prove the problem to be NP-hard and propose a Greedy based Online Channel and Power Allocation (GOCPA) algorithm. Our proposed protocols in network and physical layers collaborate to manage the wireless communication in hybrid DCNs. Extensive simulations show that our protocols can significantly increase the network throughput, decrease the latency, and moreover increase the robustness of the networks.

In Cognitive Radio Networks (CRNs), a fundamental operation for the secondary users (SUs) is to establish communication through choosing a common available channel at the same time slot, which is referred to as rendezvous. In this paper, we study fast rendezvous for two SUs.

In Hybrid networks, which synergistically mix together wired and wireless links to achieve flexible and reliable communication, it is particularly challenging to routing selfish tasks since each task wish to finish transmission as early as possible and its decision could have impacts on the others. In this paper, we investigate the problem to route a given set of selfish tasks in hybrid networks. Under a unified cost model, the competitive behaviors of selfish players are modeled as a noncooperative game. We show the game is ordinal potential, and the existence of a pure-Nash Equilibrium (pure-NE) is therefore guaranteed. We also design a routing scheme, called Selfish Task-Driven Routing (STaR), to achieve a pure-NE. Extensive simulations show that our scheme can not only efficiently converge to an equilibrium but also outperform other source routing protocols regarding the completion time and load balancing.