As the leading candidate for quantum error correction, the surface code faces substantial overhead, such as redundant physical qubits and prolonged execution time. Reducing the space-time cost of circuit execution can significantly improve the throughput of modern quantum cloud platforms. While utilizing more physical qubits can reduce execution time, different quantum circuits vary in their ability to leverage chip resources. Therefore, optimizing the compilation of surface code circuits on quantum chips becomes critical. In this work, we address the mapping and scheduling problem in compiling surface code to reduce the cost. First, we introduce a novel metric Circuit Parallelism Degree to characterize circuit properties in detail and select the most suitable chip from a list of available options. Next, we will quantitatively assess the resources to determine if they are sufficient for the circuit. We then propose a resource-adaptive mapping and scheduling method called Ecmas+ , which customizes the initialization of chip resources for each circuit. Ecmas+ significantly reduces execution time in the double defect and lattice surgery models. Extensive numerical tests on practical datasets demonstrate that Ecmas+ outperforms state-of-the-art methods, reducing execution time by an average of 46% for the double defect model and 29.7% for the lattice surgery model.

Quantum computing has been accumulating tremendous attention in recent years. In current superconducting quantum processors, each qubit can only be connected with a limited number of neighbors. Therefore, the original quantum circuit should be converted to a hardware-dependent circuit, and this process is called qubit mapping and routing, in which typically extra SWAP gates need to be inserted. Due to a limited qubit lifetime, one of the main objectives of qubit mapping and routing is to minimize the circuit depth, which is a time-consuming process. By studying several existing greedy mappers, we extract and analyze two patterns that significantly impact the mapping and routing performance. Then, we propose a sliding window method named SWin, which dramatically reduces the computational cost with negligible performance degradation. For devices with constrained executable circuit depth, we propose SWin+, which introduces adaptive circuit slicing methods with VF$2+ {+}$subgraph isomorphism initial mapping methods. Compared with the state-of-the-art greedy methods, SWin can find an effective result by up to 39% depth decrease, on average of 16% for large-scale circuits. Moreover, SWin can be easily modified to be noise-aware, while the depth reduction will yield better performance for real execution. Furthermore, SWin still performs well for various chip couplings. SWin+ significantly enhances processing efficiency, achieving improvements up to$22.3\times $, with an average increase of$6.1\times $. Concurrently, it maintains the effectiveness of the transformed circuit depth.

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.

As the leading candidate of quantum error correction codes, surface code suffers from significant overhead, such as execution time. Reducing the circuit's execution time not only enhances its execution efficiency but also improves fidelity. However, finding the shortest execution time is NP-hard. In this work, we study the surface code mapping and scheduling problem. To reduce the execution time of a quantum circuit, we first introduce two novel metrics: Circuit Parallelism Degree and Chip Communication Capacity to quantitatively characterize quantum circuits and chips. Then, we propose a resource-adaptive mapping and scheduling method, named Ecmas, with customized initialization of chip resources for each circuit. Ecmas can dramatically reduce the execution time in both double defect and lattice surgery models. Furthermore, we provide an additional version Ecmas-ReSu for sufficient qubits, which is performance-guaranteed and more efficient. Extensive numerical tests on practical datasets show that Ecmas outperforms the state-of-the-art methods by reducing the execution time by 51.5 % on average for double defect model. Ecmas can reach the optimal result in most benchmarks, reducing the execution time by up to 13.9 % for lattice surgery model.

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%.

Online convex optimization in distributed systems has shown great promise in collaboratively learning on data streams with massive learners, such as in collaborative coordination in robot and IoT networks. When implemented in communication-constrained networks like robot and IoT networks, two critical yet distinct objectives in distributed online convex optimization (DOCO) are minimizing the overall regret and the communication cost. Achieving both objectives simultaneously is challenging, especially when the number of learners$n$and learning time$T$are prohibitively large. To address this challenge, we propose novel algorithms in typical adversarial and stochastic settings. Our algorithms significantly reduce the communication complexity of the algorithms with the state-of-the-art regret by a factor of$\mathcal {O}(n^{2})$and$\tilde{\mathcal {O}}(\sqrt{nT})$in adversarial and stochastic settings, respectively. We are the first to achieve nearly optimal regret and communication complexity simultaneously up to polylogarithmic factors. We validate our algorithms through experiments on real-world datasets in classification tasks. Our algorithms with appropriate parameters can achieve$90\%\sim 99\%$communication saving with close accuracy over existing methods in most cases. The code is available athttps://github.com/GGBOND121382/Communication-Efficient_Regret-Optimal_DOCO.

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.

The traffic bandwidth costs comprise a significant amount of operating expenditure in CDNs, induced by the traffic from the end-users to edge servers (edge cost) and from the edge to the center servers (midgress cost). Traffic allocation is the main approach to minimizing the total bandwidth cost. The joint optimization of the total costs is challenging, specifically when the percentile charging mechanism as well as some other practical issues are considered, such as the dynamicity of midgress traffic and the granularity of traffic allocation. In this work, based on our novel miss ratio prediction mechanism, we propose the first online framework, named Iris, jointly optimizing the edge and midgress costs under the 95th percentile charging in commercial CDNs. Iris can theoretically achieve a competitive ratio of$1+\frac{p_{e}}{\beta\cdot p_{c}}$, when the miss ratio of all domains is set as$\beta$. Here$p_{e}$and$p_{c}$are the unit bandwidth price of the edge and midgress cost, respectively. Iris is tolerant to prediction errors which can be deployed in practical CDN systems. Extensive experiments based on real data indicate that Iris can dramatically reduce bandwidth costs by about 8.149% compared with the SOTA schemes, potentially saving millions of dollars per month for our large-scale commercial CDN collaborator.

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.

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+.

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.

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 scheduling in the context of OCS, let alone the coflow scheduling problems. In this paper, we investigate coflow scheduling in the OCS-based data centers. We first derive a novel operation called regularization processed respectively on the flow traffic demands and the flow start times. Regularization 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 another approximation algorithm, called Reco-Mul, to minimize the total weighted CCT, which can transform any non-preemptive multi-coflow scheduling in packet switches to that in OCS. Extensive simulations based on Facebook data traces show that Reco-Sin and Reco-Mul outperform state-of-the-art schemes significantly, i.e., one single coflow can be finished up to 2.72× faster with Reco-Sin, and multiple coflows can be completed up to 3.44× faster with Reco-Mul.

Coflow is gradually prevalent as a new traffic structure in data centers, which allows applications to convey their application-level semantics into the network. Meanwhile, optical circuit switches (OCS) are increasingly deployed in data centers due to the superiority in hardware, such as high bandwidth and low energy consumption. However, few works in the literature considered both coflow scheduling with OCS. In this paper, we study the coflow scheduling problem in an OCS-based data center network, with an aim to minimize the coflow completion time (CCT). We derive an online algorithm called OMCO to solve this problem. OMCO can not only optimize the circuit utilization but also minimize the number of circuit reconfigurations. Extensive simulations with real-world data traces show that OMCO outperforms other existing solutions dramatically. Compared with a FIFO-based scheme and the shortest-coflow-first heuristic, OMCO reduces the average coflow completion time by up to 61% and 62%, respectively.