Federated Learning (FL) enables devices to collaboratively train a global model without centralizing raw data. However, heterogeneous data distributions often hinder a single global model from performing optimally across diverse clients. In this paper, we introduce two personalized federated learning methods to address the aforementioned challenge. First, we introduce a gradient-fusion approach that merges global gradients aggregated via a learnable collaboration matrix with local gradients tailored to each client's data. This fusion harmonizes collective intelligence with device-specific knowledge, thereby improving personalization under data heterogeneity. Second, we propose a gradient-decoupling method that mitigates the limitations of relying solely on a collaboration matrix for balancing knowledge sharing and personalization. By decoupling the tasks and regularizing local updates through the incorporation of extracted collective intelligence, we introduce an inductive bias that significantly improves generalization. Extensive evaluations on four computed tomography and pathology imaging datasets covering a wide range of heterogeneity show that our frameworks substantially outperform existing baselines. We also provide theoretical analyses that establish performance bounds and convergence guarantees under mild assumptions.

Focusing on a distributed aircraft manufacturing scenario that supports cloud-edge collaboration, this study formulates an extended Flexible Job Shop Scheduling Problem (EFJSP) incorporating task area partitioning and cross-region machine travel time constraints. The inclusion of additional constraints increases the complexity of the scheduling problem. To ensure both solution quality and computational efficiency, we propose an end-to-end deep reinforcement learning (DRL)-based approach. First, the EFJSP is represented as a disjunctive graph with node and edge features capturing area partitioning and machine travel time. A dual graph attention network (DGAT) is then employed to extract node embeddings from the operation and machine subgraphs. Machine processing and travel times are unified into a single temporal dimension and incorporated into the operation-machine features, which, together with the node embeddings, support high-quality decision-making. Finally, under the Proximal Policy Optimization (PPO) framework, a scale-invariant policy and value network interact iteratively with a simulation environment for training. Experiments on synthetic datasets show that the proposed method outperforms priority dispatching rules (PDRs), matches or exceeds exact methods within time limits. Additionally, it exhibits superior computational efficiency over exact methods and strong generalization capabilities for large-scale problems.

Approximate Nearest Neighbor Search (ANNS) is a critical component of modern AI systems, such as recommendation engines and retrieval-augmented large language models (RAG-LLMs). However, scaling ANNS to billion-entry datasets exposes critical inefficiencies: CPU-based solutions are bottlenecked by memory bandwidth limitations, while GPU implementations underutilize hardware resources, leading to suboptimal performance and energy consumption. To address these challenges, we introduce UpANNS, a novel framework leveraging Processing-in-Memory (PIM) architecture to accelerate billion-scale ANNS. UpANNS integrates four key innovations, including 1) architecture-aware data placement to minimize latency through workload balancing, 2) dynamic resource management for optimal PIM utilization, 3) co-occurrence optimized encoding to reduce redundant computations, and 4) an early-pruning strategy for efficient top-k selection. Evaluation on commercial UPMEM hardware demonstrates that UpANNS achieves 4.3x higher QPS than CPU-based Faiss, while matching GPU performance with 2.3x greater energy efficiency. Its near-linear scalability ensures practicality for growing datasets, making it ideal for applications like real-time LLM serving and large-scale retrieval systems.

Learned indexes provide significant performance advantages over classical ordered indexes. However, current learned indexes face challenges regarding tradeoffs between performance and space, as well as scalability issues in platforms with multiple NUMA nodes. These limitations hinder the practical application of learned indexes in production environments. This article presents DiffLex, a learned index with high-performance, memory-efficiency, and NUMA-awareness. The core design of DiffLex is to perform differentiated management based on the popularity of data. For optimal performance, DiffLex stores newly inserted data in sparse delta arrays and frequently accessed data in sparse hot cache arrays. However, for cold data that occupy a majority of the storage space, DiffLex stores them in dense arrays and conducts compression to reduce memory costs. DiffLex ensures NUMA-awareness by partitioning sparse deltas and replicating the hot cache arrays across multiple NUMA nodes. Additionally, we propose a persistent version of DiffLex tailored for emerging persistent memory devices. Our evaluation results demonstrate that DiffLex achieving 3.88× and 1.82× performance improvements compared to state-of-the-art learned indexes, while maintaining a compact index size.

Data deduplication is an effective technique for reducing redundant data storage space in various storage systems. Generally, deduplication consists of four steps: chunking, fingerprinting, fingerprint lookup, and data management. Recently, Non-volatile Memory (NVM) as an emerging storage device has received widespread attention. Directly applying the deduplication technique on NVM for storage cost savings faces many challenges: (a) deduplication on NVM devices suffers from computation bottleneck instead of the I/O bottleneck faced by deduplication on traditional storage devices (such as HDD and SSD); (b) new fingerprint indexes and metadata are required to be re-designed to adapt to NVM characteristics; (c) inline deduplication on NVM is more sensitive to the latency. To solve these challenges, we propose a novel Samp ling prediction-based inline data Dedup lication method ( SampDedup ) on NVM devices. It aims to ensure high deduplication ratios while reducing computation costs and latency by optimizing data chunking , fingerprinting , and fingerprint lookup . (a) For data chunking , a sampling prediction-based chunking method ( SampChunk ) is proposed to leverage chunk similarity to distinguish duplicate chunks and skip them for chunking. This method can be easily integrated into most sliding-window based and non-window based CDC chunking algorithms. (b) For fingerprinting , the commonly used SHA-1 algorithm is further optimized to reduce the extra computational overhead introduced by SampChunk, and an asynchronous fingerprinting method is proposed to reduce the fingerprinting latency of unique chunks. (c) For fingerprint lookup , we design a header fingerprint index and metadata table for each data chunk constructed by SampChunk on NVM, and we use a fast-read buffer to replace the traditional slow LRU cache to improve search efficiency. Experiments on four real-world datasets demonstrate that SampDedup consistently presents high inline data deduplication ratios on NVM with different workloads and data partitioning algorithms while saving more than 90% chunking time compared with state-of-the-art deduplication baselines.

In video analytics, accuracy and efficiency are two important metrics and there tend to be a tradeoff between each other. In this paper, we consider accuracy-efficiency optimization for small object detection in surveillance video, which is important and has been widely used in many scenarios such as license plate detection in the traffic domain. Given that small objects tend to being attached to big objects, multi-stage object detection is supposed to be an effective approach to achieve high accuracy for small objects by detecting big objects first and then small objects within the ROIs (Region of interests) of big objects. However, existing studies considered the accuracy-efficiency optimization for small object detection only within the single-stage scenario by changing the frame resolution or sampling rate configuration of video data, which are not suitable for multi-stage detection given that its accuracy-efficiency result is determined by the results of all stages jointly. In this paper, we propose an Adaptive and Collaborative frame Sampling approach named ACS for accuracy-efficiency optimization in the multi-stage small object detection. To improve the efficiency significantly while guaranteeing a given accuracy threshold, ACS dynamically adjusts the sampling rates of all stages collaboratively and periodically using the Karush-Kuhn-Tucker (KKT) condition based on the Lagrangian multiplier method. Additionally, we introduce a tuning knob to allow users to flexibly balance accuracy and efficiency, while ensuring a given accuracy threshold λ. Extensive experiments demonstrate the effectiveness of our approach in improving detection efficiency while guaranteeing diverse accuracy requirements.

Deep Learning Recommendation Models (DLRMs) have gained popularity in recommendation systems due to their effectiveness in handling large-scale recommendation tasks. The embedding layers of DLRMs have become the performance bottleneck due to their intensive needs on memory capacity and memory bandwidth. In this paper, we propose UpDLRM, which utilizes real-world processing-in-memory (PIM) hardware, UPMEM DPU, to boost the memory bandwidth and reduce recommendation latency. The parallel nature of the DPU memory can provide high aggregated bandwidth for the large number of irregular memory accesses in embedding lookups, thus offering great potential to reduce the inference latency. To fully utilize the DPU memory bandwidth, we further studied the embedding table partitioning problem to achieve good workload-balance and efficient data caching. Evaluations using real-world datasets show that, UpDLRM achieves much lower inference time for DLRM compared to both CPU-only and CPU-GPU hybrid counterparts.

Vector data management systems (VDMSs) have become an indispensable cornerstone in large-scale information retrieval and machine learning systems like large language models. To enhance the efficiency and flexibility of similarity search, VDMS exposes many tunable index parameters and system parameters for users to specify. However, due to the inherent characteristics of VDMS, automatic performance tuning for VDMS faces several critical challenges, which cannot be well addressed by the existing auto-tuning methods. In this paper, we introduce VDTuner, a learning-based automatic performance tuning framework for VDMS, leveraging multi-objective Bayesian optimization. VDTuner overcomes the challenges associated with VDMS by efficiently exploring a complex multi-dimensional parameter space without requiring any prior knowledge. Moreover, it is able to achieve a good balance between search speed and recall rate, delivering an optimal configuration. Extensive evaluations demonstrate that VDTuner can markedly improve VDMS performance (14.12% in search speed and 186.38 % in recall rate) compared with default setting, and is more efficient compared with state-of-the-art baselines (up to 3.57 x faster in terms of tuning time). In addition, VDTuner is scalable to specific user preference and cost-aware optimization objective. VDTuner is available online at https://github.com/tiannuo-yanWVDTuner.

In Serverless Computing, function cold-start is a major issue that causes delay of the system. Various solutions have been proposed to address function cold-start issue, among which keeping containers alive after function completion is an easy and commonly adopted way in real serverless clouds. However, when reusing warm containers for function warm starts, existing systems only match functions to containers with the same configurations. This greatly limits the warm resource utilization. Our analysis of real-world applications reveals that many serverless applications share the same operating system and language frameworks. Thus, we propose multi-level container reuse that tries to reduce the startup latency of functions using "similar" containers to greatly improve warm resource utilization. Due to the complexity of selecting the best container reuse solutions, we designed a Deep Reinforcement Learning (DRL) based scheduler to efficiently and effectively address the problem. Moreover, we released a new serverless benchmark named FStartBench that contains detailed package information for comparing the effectiveness of different function cold-start methods. Experiments based on FStartBench show that, given a warm resource pool with fixed size, our DRL-based scheduler can achieve up to 53% reduction on the average function startup latency compared to state-of-the-art solutions.

Heuristic-based workload redistribution is the most commonly adopted solution to provide enhanced service performance in large-scale Internet Data Centers (IDCs). However, statistics show that they cannot perform as well as expected in real-world IDCs. In this paper, we rethink existing solutions based on real-world trace data and pinpoint two major pitfalls: (i) Sensitive to hand-tuning parameters; (ii) Reassigning only a few workloads locally at a time. The two of them jointly limit the universal applicability of existing solutions in optimizing multiple objectives fairly. To address such issues, we propose the matching-theory-based solution for workload redistribution, namely Themis. It is an efficient and universal solution for large-scale IDCs, which can avoid empirical parameters in optimization and reassign several workloads globally each time. Moreover, the newly proposed Themis can optimize multiple objectives (e.g., resource utilization balancing and communication efficiency improving) simultaneously and fairly. In addition to its own performance advantages, our proposed Themis is also compatible with existing methods, thus adapting to a wider range of deployment scenarios. Extensive evaluations based on the trace data from two real-world IDCs demonstrate that our proposed Themis outperforms multiple comparison solutions, as well as the compatibility of parameter changes (i.e., stability properties in terms of parameter configuration).

Federated learning (FL) enables multiple IoT devices to collaboratively train a global model without centralizing raw data. However, achieving optimal performance for each device is challenging due to the heterogeneity of IoT data. Moreover, IoT devices, constrained in computational power and energy, necessitate innovative privacy protection solutions in FL. In this paper, we propose privacy-enhanced FL methods to address data heterogeneity in IoT. Our approach includes a dual-model framework for each device, combining a shared model to facilitate inter-client communication with a personalized model. This personalized model is developed from local aggregation, utilizing layer-wise aggregation weights generated by local hypernetworks. This integration effectively balances collective intelligence with client-specific knowledge, addressing data heterogeneity for improved personalization. Additionally, we propose a Local Gradient Shielding (LGS) method to protect training data. This method conceals gradients in locally trained personalized models, preventing data reconstruction and ensuring client privacy with minimal resource consumption. Extensive evaluations on benchmark datasets, showcasing various types and degrees of data heterogeneity, demonstrate the superiority of our approaches over current baselines.

Workload consolidation is a widely used approach to enhance resource utilization in modern data centers. However, the concurrent execution of multiple jobs on a shared server introduces contention for essential shared resources such as CPU cores, Last Level Cache, and memory bandwidth. This contention negatively impacts job performance, leading to significant degradation in throughput. To mitigate resource contention, effective resource isolation techniques at the software or hardware level can be employed to partition the shared resources among colocated jobs. However, existing solutions for resource partitioning often assume a limited number of jobs that can be colocated, making them unsuitable for scenarios with a large-scale job colocation due to several critical challenges. In this study, we propose Lavender, a framework specifically designed for addressing large-scale resource partitioning problems. Lavender incorporates several key techniques to tackle the challenges associated with large-scale resource partitioning, ensuring efficiency, adaptivity, and optimality. We conducted comprehensive evaluations of Lavender to validate its performance and analyze the reasons for its advantages. The experimental results demonstrate that Lavender significantly outperforms state-of-the-art baselines. Lavender is publicly available at https://github.com/yanxiaoqi932/OpenSourceLavender.

The emerging persistent memory (PM) is increasingly being leveraged to construct high-performance and persistent indexes. By exploiting data distribution, recent learned indexes open up a new index design paradigm. Some prior studies try to refit the learned index according to the features of PM. However, they neglect to analyze the performance of existing learned index schemes on PM. In this paper, we provide a comprehensive analysis of learned indexes on PM and propose two optimization methods to improve the performance. In particular, we evaluate ALEX, PGM-index, and XIndex after converting them to persistent indexes. With appropriate modifications, some design choices of volatile learned index still show favorable performance on PM under workloads with simple data distribution. But they perform poorly when the data distribution becomes complex. According to the experiment results, we summarize some instructive insights and optimize persistent learned indexes for complex data distributions with two methods: 1) a cost-based insertion pattern selection to minimize PM writes and 2) recoverable internal nodes selective persistence to decrease the overhead of internal lookups. Our evaluations demonstrate the performance of optimized ALEX is 2.09x/1.53x of the original ALEX in insert/search. Meanwhile, it also outperforms the specific-designed persistent learned index.

Pay-as-you-go caching systems are now widely used as storage services in cloud computing. However, users’ data caching requirements not only change over time, but also they are affected by workload characteristics, making it difficult to always ensure high efficient use of cache resources. Cache resource sharing is an effective way to improve the efficiency of cache usage. To incentivize users to share caches, it is essential to ensure long-term fairness among multiple users. However, traditional resource allocation strategies canonly guarantee memory less fairness among users,which is not applicable to long-term cache sharing systems. In this paper, we propose a fair allocation policy named FairCache for Pay-as-you-go cache resources. First, FairCache can satisfy four desirable properties of resource allocation: sharing incentive, pay-as-you-usefairness, strategy proofness, and pare to efficiency. Second, FairCache is an efficiency-fairness resource allocation policy based on the efficiency knob θ. The strategy keeps sensitive to the constantly changing cache demands of multiple users within the system by adjusting the efficiency knob θ, thus ensuring long-term multi-user fairness while maximizing the efficiency of cache usage. In addition, FairCache also has an anti-cheating mechanism to avoid possible free-rider problems when multiple users cache access files. Finally, this paper implements the FairCache policy in Alluxio. The experimental results show that FairCache is a lightweight scheduler and that it can maximize the efficiency usage of cache resources while ensuring the long-term for multiple users in the pay-as-you-go Cache systems fairness.

Time series databases play a critical role in large-scale performance monitoring systems. Metrics are required to be observable immediately after being generated to support real-time analysis. However, the commonly used Log-Structured Merge-Tree structure suffers from periodically visible delay spikes when a new segment is created due to the instantaneous index construction pressure.

Colocating multiple jobs on the same server has been a commonly used approach for improving resource utilization in cloud environments. However, performance interference due to the contention over shared resources makes resource partitioning an important research problem. Partitioning multiple resources coordinately is particularly challenging when multiple latency-critical (LC) jobs are colocated with best-effort (BE) jobs, since the QoS needs to be protected for all the LC jobs. So far, this problem is not well-addressed in the literatures.

With the explosive increase of big data in industry and academic fields, it is important to apply large-scale data processing systems to analyze Big Data. Arguably, Spark is the state-of-the-art in large-scale data computing systems nowadays, due to its good properties including generality, fault tolerance, high performance of in-memory data processing, and scalability. Spark adopts a flexible Resident Distributed Dataset (RDD) programming model with a set of provided transformation and action operators whose operating functions can be customized by users according to their applications. It is originally positioned as a fast and general data processing system. A large body of research efforts have been made to make it more efficient (faster) and general by considering various circumstances since its introduction. In this survey, we aim to have a thorough review of various kinds of optimization techniques on the generality and performance improvement of Spark. We introduce various data management and processing systems, machine learning algorithms and applications supported by Spark. Additionally, we make a discussion on the open issues and challenges for large-scale in-memory data processing with Spark.

Learned indexes that utilize machine learning models can offer significant performance advantages over traditional indexes. However, existing learned indexes suffer from space-performance tradeoffs and they cannot scale well in multiple NUMA-nodes machines. These issues limit the development of learned indexes in production environments. In this paper, we propose DiffLex, a high-performance, memory-efficient and NUMA-aware learned index. The core idea of DiffLex is to differentiate key management based on hotness. To achieve high performance, DiffLex stores newly inserted keys in sparse deltas and frequently accessed keys in a sparse hot cache. For cold keys that take up most of the storage space, however, DiffLex stores them in dense arrays to save memory costs. DiffLex also makes sparse deltas and hot cache NUMA-aware by partitioning sparse deltas and replicating hot cache across different NUMA nodes. Our evaluation shows that DiffLex outperforms the state-of-the-art ALEX by 3.88x and 1.82x for insert and search operations, respectively, while maintaining a small index size.

The performance of modern multi-core systems is reliant upon two crucial configurations: how the resources are partitioned among the co-located applications to mitigate resource contention, and the setting of the parameters of applications. However, finding the optimal resource partition configuration and parameter setting for the co-located applications is challenging due to the prohibitively large search space and the high interdependency between resource partitioning and parameter tuning.

Colocating multiple jobs on the same server has been widely applied for improving resource utilization in cloud datacenters. However, the colocated jobs would contend for the shared resources, which could lead to significant performance degradation. An efficient approach for eliminating performance interference is to partition the shared resources among the colocated jobs. However, this makes the resource management in datacenters very challenging. In this paper, we propose JointOPT, the first resource management framework that optimizes job assignment and resource partitioning jointly for improving the throughput of cloud datacenters. JointOPT uses a local search based algorithm to find the near optimal job assignment configuration, and uses a deep reinforcement learning (DRL) based approach to dynamically partition the shared resources among the colocated jobs. In order to reduce the interaction overhead with real systems, it leverages deep learning to estimate job performance without running them on real servers. We conduct extensive experiments to evaluate JointOPT and the results show that JointOPT significantly outperforms the state-of-the-art baselines, with an advantage from 13.3% to 47.7%.

Colocating multiple throughput-oriented jobs on the same server is a commonly used approach for improving system throughput in modern datacenters. The shared resources of the server are usually partitioned among the colocated jobs in order to prevent performance interference caused by resource contention. However, how to properly partition the shared resources among the colocated jobs is nontrival, because it usually has to trade off between two conflict objectives, as datacenter manager wants to maximize server throughput while job owners hope to experience a fair slowdown. Moreover, a desirable resource partitioning strategy should also be efficient, autonomous and adaptive. So far, this problem is not well-addressed in the literature due to several critical challenges. In this paper, we propose an online learning based framework, namedOrchid, to address the multi-objective resource partitioning problem. Orchid leverages contextual multi-armed bandit (CMAB) to model the resource partitioning problem and uses a light-weight online learning algorithm to learn the optimal partitioning configuration according to some easy-to-collect runtime system status. Orchid has two distinguished properties compared to the existing solutions: first, it has the ability to trade off between the two objectives flexibly according to the aspiration of decision maker; second, it has the awareness about runtime system status, which can help to improve the efficiency of finding the optimal partitioning configuration and the adaptivity to dynamic environment changes. Moreover, Orchid does not require any prior knowledge of jobs, and incurs a very small computational overhead. Our evaluations show that Orchid achieves all the desired properties of a good resource partitioning strategy, which outperforms the state-of-the-art baselines with significant margins.Orchidis publicly available athttps://github.com/OpenSourceOrchid/Orchid.

In-memory Key-Value (KV) stores are widely deployed in modern data centers. These systems generally use DRAM as their storage medium, causing huge hardware costs. The emerging persistent memory (PMEM) is a potential substitute for DRAM, which has a lower price and larger capacity, but lower access speed and bandwidth. Many prior studies strive to build hybrid memory systems to retain both the advantages of DRAM and PMEM. However, they are either application agnostic or simply take DRAM as a cache, which are both not efficient for in-memory KV stores. In this paper, we propose SwapKV, a well-designed in-memory KV store for hybrid DRAM-PMEM system. SwapKV has several promising properties. First, SwapKV combines DRAM and PMEM to a uniform memory pool and only stores one copy of data, which maximizes capacity utilization. Second, SwapKV maps all writing operations to DRAM and migrates data to PMEM with large blocks asynchronously, which mitigates the intrinsic inefficiency of PMEM for writing operations. Third, SwapKV maintains the hot data in DRAM through an efficient hotness filtering and data swapping mechanism, which ensures high system throughput and responsiveness. We implement SwapKV and evaluate it under various workload patterns. The results demonstrate that SwapKV improves the throughput by 11\%$\sim$41\% compared to the state-of-the-art alternatives.

Commercial search engines generally maintain hundreds of thousands of machines equipped with large sized DRAM which incurs high hardware cost since DRAM is expensive. Recently, NVM Optane SSD has been considered as a promising underlying storage device due to its price advantage and speed advantage. However, to achieve a comparable efficiency performance with in-memory index, applying NVM to both latency and I/O bandwidth critical applications still face non-trivial challenges, because NVM has much lower I/O speed and bandwidth compared to DRAM. In this paper, we propose an NVM SSD-optimized query processing framework, aiming to address both the latency and bandwidth issues of using NVM in search engines. First, we propose a pipelined query processing methodology which significantly reduces the I/O waiting time. Second, we propose a cache-aware query reordering algorithm which enables queries sharing more data to be processed adjacently. Third, we propose a data prefetching mechanism which reduces the extra thread waiting time and improves bandwidth utilization. Moreover, we propose intra-query parallel mechanisms for long-tail queries, including query subtask scheduling, heap concurrent access strategy, query parallelism prediction and adaptive pipelining. Extensive experimental studies show that our framework significantly outperforms the state-of-the-art baselines, which obtains comparable processing latency and throughput with DRAM in both inter-query and intra-query parallel scenarios.

Recent research on deep convolutional neural networks (CNNs) has provided a significant performance boost on efficient super-resolution (SR) tasks by trading off the performance and applicability. However, most existing methods focus on subtracting feature processing consumption to reduce the parameters and calculations without refining the immediate features, which leads to inadequate information in the restoration. In this paper, we propose a lightweight network termed DDistill-SR, which significantly improves the SR quality by capturing and reusing more helpful information in a static-dynamic feature distillation manner. Specifically, we propose a plug-in reparameterized dynamic unit (RDU) to promote the performance and inference cost trade-off. During the training phase, the RDU learns to linearly combine multiple reparameterizable blocks by analyzing varied input statistics to enhance layer-level representation. In the inference phase, the RDU is equally converted to simple dynamic convolutions that explicitly capture robust dynamic and static feature maps. Then, the information distillation block is constructed by several RDUs to enforce hierarchical refinement and selective fusion of spatial context information. Furthermore, we propose a dynamic distillation fusion (DDF) module to enable dynamic signals aggregation and communication between hierarchical modules to further improve performance. Empirical results show that our DDistill-SR outperforms the baselines and achieves state-of-the-art results on most super-resolution domains with much fewer parameters and less computational overhead.

Server re-consolidation refers to online migrating applications among servers for minimizing the number of servers used. To avoid interruptions to online services, resources (i.e., transient resources) are occupied at both original and destination servers during the migrations. Transient resources reduce the remaining capacity of servers, making server re-consolidation challenging. To tackle this problem, we leverage the previously proposed concept of resource exchange, which refers to a set of resource configurations such that an application running under any one of them has similar performance, thus these configurations are exchangeable and such a set is called exchangeable configuration set (ECS). Moreover, we adjust the load pressure of an application to change its ECS when there is no suitable configuration, and such a strategy is called load adjustment. In this paper, we propose a new server re-consolidation problem that maintains applications' QoS target and availability at the same time. We leverage a machine-learning algorithm to estimate the performance of applications, based on which the ECSs are constructed efficiently. We design a simulated annealing-based (SA) algorithm to optimally solve the scheduling plan. We evaluate the proposed approach using data from real-world latency-critical applications. The results show that the proposed approach outperforms two state-of-the-art baselines in terms of reducing the number of used servers by 10% on average and up to 29%. To our knowledge, this is the first time that resource exchange and load adjustment strategies have been applied to the server re-consolidation problem.

Interactive graphics applications are generally latency-critical, while using multiple GPUs to accelerate such applications becomes possible recently with support from both hardware and software. Split frame rendering (SFR) is a popular approach for multi-GPU rendering, which splits a frame into disjoint regions and assigns the regions to different GPUs. Load scheduling of SFR is a crucial but challenging issue for achieving maximum rendering performance in real-time rendering, which is not well addressed by the existing solutions. In this paper, we propose SPIDER, a load scheduler which leverages fuzzy PID (proportional integral derivative) controller to schedule the rendering workload among GPUs. SPIDER has several distinguished properties: it is a feedback based mechanism which does not need a full knowledge of the dynamic system; it is very computationally efficient and easy to implement; it is highly robust to dynamic workload changes. Extensive experiments are conducted to evaluate SPIDER and the results show that SPIDER always achieves near-optimal performance for various workload patterns, which outperforms the state-of-the-art baselines signif-icantly.

Recent uses of heterogeneous mobile and lightweight devices encourage computations to be abstracted remotely as black box systems. This same concept applies for cloud gaming in which computer games are located and run inside remote rendering servers (RSes). While cloud gaming enables lightweight devices with sufficient input capabilities and network connection to be able to play desktop games, latency and cost issue become significant hindrances in recent applications. In this paper, we came up with our edge-cloud gaming architecture which reduces the overall workload in RSes while increasing playerbase coverage by using edge RSes. Furthermore, we also proposed our allocation algorithm in order to assign incoming players to RSes. From our experiments, our proposed architecture has higher playerbase coverage while our allocation algorithm significantly reduces the cost in both single and batch player arrival pattern.

Cloud gaming has been very popular in recent years, but issues relating to maintaining low interaction delay to guarantee satisfactory user experience are still prevalent. We observe that the server-side processing delay in cloud gaming system could be heavily influenced by how the resources are partitioned among processes. However, finding the optimal partitioning policy that minimizes the response delay faces several critical challenges. First, fine-grained resource partitioning is non-trivial due to the limitations of hardwre-based resource isolation techniques. Second, game wokload is highly dynamic and unpredictable, making the design of efficient resource partitioning policy more challenging. In this article, we propose an online resource partitioning framework for reducing response delay in cloud gaming, which has several promising properties. First, we divide the processes into disjoint groups and partition resources among process groups, which greatly simplifies the resource partitioning problem while ensuring high partitioning effectiveness. Second, to tackle dynamic workload changes, we classify game workloads into several clusters and maintain separate process grouping plan for each cluster. Third, we leverage reinforcement learning to adaptively choose the best actions for minimizing response delay in real time. We evaluate the proposed framework in a real cloud gaming environment using several real games. The experimental results show that our approach can reduce the response delay by 22 to 41 percent compared to a system without resource partitioning, and outperforms other resource partitioning policies significantly.

Fairness and efficiency are two important metrics for users in modern data center computing system. Due to the heterogeneous resource demands of CPU, memory, and network I/O for users’ tasks, it cannot achieve the strict 100 percent fairness and the maximum efficiency at the same time. Existing fairness-efficiency schedulers (e.g., Tetris) can balance such a tradeoff elastically by relaxing fairness constraint for improved efficiency using the knob. However, their approaches areunawareof fairness degradation under different knob configurations, which makes several drawbacks. First, it cannot tell how muchrelaxedfairness can be guaranteed given a knob value. Second, it fails to meet several essential properties such as sharing incentive. To address these issues, we propose a new fairness-efficiency scheduler,QKnober, to balance the fairness and efficiency elastically and flexibly using a tunable fairness knob. QKnober is afairness-sensitivescheduler that can maximize the system efficiency while guaranteeing the$\theta$-soft fairness by modeling the whole allocation as a combination offairness-orientedallocation andefficiency-orientedallocation. Moreover, QKnober satisfies fairness properties of sharing incentive, envy-freeness and pareto efficiency given a proper knob value. We have implemented QKnober in YARN and evaluated it using both testbed and simulated experiments. The results show that QKnober outperforms its alternatives DRF and Tetris by 31.2 and 4.5 percent, respectively.

With the explosive increase of big data in industry and academic fields, it is important to apply large-scale data processing systems to analyze Big Data. Arguably, Spark is the state-of-the-art in large-scale data computing systems nowadays, due to its good properties including generality, fault tolerance, high performance of in-memory data processing, and scalability. Spark adopts a flexible Resident Distributed Dataset (RDD) programming model with a set of provided transformation and action operators whose operating functions can be customized by users according to their applications. It is originally positioned as afastandgeneraldata processing system. A large body of research efforts have been made to make it more efficient (faster) and general by considering various circumstances since its introduction. In this survey, we aim to have a thorough review of various kinds of optimization techniques on the generality and performance improvement of Spark. We introduce Spark programming model and computing system, discuss the pros and cons of Spark, and have an investigation and classification of various solving techniques in the literature. Moreover, we also introduce various data management and processing systems, machine learning algorithms and applications supported by Spark. Finally, we make a discussion on the open issues and challenges for large-scale in-memory data processing with Spark.

Blockchain-based artificial intelligence (BC-AI) has been applied for protecting deep neural network (DNN) data from being tampered with, which is expected to further boost trusted distributed AI applications in many fields. However, due to smart contract execution environment architectural defects, it is challenging for previous BC-AI systems to support computing-intensive tasks on-chain performing such as DNN convolution operations. They have to offload computations and a large amount of data from blockchain to off-chain platforms to execute smart contracts as native code. This failure to take advantage of data locality has become one of the major critical performance bottlenecks in BC-AI system. To this end, in this article, we propose SmartVM with optimization methods to support on-chain DNN inference for BC-AI system. The key idea is to design and optimize the computing mechanism and storage structure of smart contract execution environment according to the characteristics of DNN such as high computational parallelism and large data volume. We decompose SmartVM into three components: 1) a compact DNN-oriented instruction set to describe computations in a short number of instructions to reduce interpretation time. 2) a memory management mechanism to make SmartVM memory dynamic free/allocated according to the size of DNN feature maps. 3) a block-based weight prefetching and parallel computing method to organize each layer's computing and weights prefetching in a pipelined manner. We perform the typical image classification in a private Ethereum blockchain testbed to evaluate SmartVM performance. Experimental results highlight that SmartVM can support DNN inference on-chain with roughly the same efficiency against the native code execution. Compared with the traditional off-chain computing, SmartVM can speed up the overall execution by70×,16×,11×, and12×over LeNet5, AlexNet, ResNet18, and MobileNet, respectively. The memory footprint can be reduced by84%,90.8%,94.3%, and93.7%over the above four models, while offering the same level model accuracy. This article sheds light on the design space of the smart contract virtual machine for DNN computation and is promising to further boost BC-AI applications.

Applying deep neural networks (DNNs) to video analytics tasks has drawn attention from both academic and industry communities. However, due to the high computational complexity of DNN models and the explosion of video data, it is challenging to process massive concurrent video queries efficiently and effectively. In this paper, we propose a video analytics system named DVQShare to process DNN-based video queries in a batch mode. The key idea is sharing, including time sharing, spatial sharing, and logical sharing. In principle, sharing across queries can help us reduce the overall amount of frames to be analyzed, which can help us improve the overall performance and reduce the monetary cost. Two modules are designed to process video queries by exploiting the above three sharing opportunities. First, an analysis module is integrated to guide the generation of query processing plans. Within this module, temporal sharing is considered to reuse historical results produced by other queries to remove pending frames that have been analyzed, and spatial sharing is adopted to avoid redundant processing over overlapping video clips. Additionally, we utilize logical sharing to further improve system's overall performance by considering the logical relationship between queries. Second, a query processing engine is devised to execute the query pipeline generated by the analysis module and return the final results. In experiments, we implement a prototype of the DVQShare system based on MXNet, and results show that it can achieve up to 2X performance speedup.

Workload consolidation is a commonly used approach for improving resource utilization of commodity servers. However, colocated workloads often suffer from significant performance degradations due to resource contention, which makes resource partitioning an important research problem. Partitioning multiple resources coordinately is particularly challenging due to the complex contention behaviors and huge solution space, which is not well-addressed in the literature.

Cloud gaming abstracts the concept of traditional gaming and places the gaming activities on remote rendering servers (RSes). Although this allows heterogeneous devices to gain access to multiple game titles, latency issue is always unavoidable. Each game input must go through a complete round trip between the player's device and the cloud gaming server. Hence, cloud games are not as responsive as traditional computer games where the game logic runs locally. Moreover, in order to have an acceptable level of game playability, the latency level must be within a certain threshold. This also prevents some players who are located in remote regions from playing the game due to high latency. Therefore, in this paper, we employ edge servers in order to reach those players by activating lower capability RSes which are more geographically distributed. Furthermore, we also allow workload splitting of foreground and background rendering between edge and cloud RSes to ease the burden of each individual RS with a trade-off between cost and latency constraints. From our experiments, our architecture and allocation scheme results in reduction of play request rejections for up to 28% compared to traditional cloud gaming approach.

With the development of virtualization technology, it is practical and necessary to integrate virtual machine software into embedded systems. I/O scheduling is important for embedded systems, because embedded systems always face different situations and their requests have more diversity on the requirement of real-time and importance. However, the semantic information associated with the I/O data is completely lost when crossing the virtualized I/O software stack. Here, we present an I/O scheduling framework to connect the semantic gap between the application threads in virtual machines and hardware schedulers in the host machine. Therefore, the details for the I/O request can be passed through the layers of the software stack and each layer can get the specific information about the device environment. Also, various scheduling points have been provided to implement different I/O strategies. Our framework was implemented based on Linux operating system, KVM, QEMU and virtio protocol. A prototype scheduler, Orthrus, was implemented to evaluate the effectiveness of the framework. Comprehensive experiments were conducted and the results show that our framework can guarantee the real-time requirements, and reserve more system resources for critical tasks, with negligible memory consumption and throughput overhead.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. However, prior work regarding colocating games either ignores the performance interference between games or uses simple performance model to charaterize it, which may make inefficient game colocation decisions and cause QoS violations. In this article, we address the resource allocation issues for colocating games in cloud gaming. We first propose a novel machine learning-based performance model, which is able to capture the complex relationship among the performance interference, the contention features of colocated games and resource partition. Guided by the performance model, we then propose efficient and effective algorithms for two resource allocation scenarios in cloud gaming. We evaluate the proposed solutions through extensive experiments using a large number of real popular games. The results show that our performance model is able to identify whether a colocated game satisfies QoS requirement within an average error of 5 percent, which significantly outperforms the alternatives. Our resource allocation algorithms are able to increase the resource utilization by up to 60 percent compared to the state-of-the-art solutions.

In this paper, we introduce a deep reinforcement learning (DRL) framework for solving the problem of partitioning LLC and memory bandwidth coordinately in an end-to-end manner. To this end, we formulate the problem as a markov decision process and utilize DRL algorithm to derive the optimal partition. To avoid the extensive cost of training the policy on physical server, we present a model-based solution, where a reward prediction model is leveraged to train the partitioning policy offline. To construct a precise reward prediction model, we introduce a novel representation for the partitioning scheme, where graph convolutional networks (GCN) is employed to represent the LLC partition as a bipartite graph so that those heterogeneous but identical partitions could result in the same representations and thus eases the prediction task.

Commercial search engines generally maintain hundreds of thousands of machines equipped with large sized DRAM in order to process huge volume of user queries with fast responsiveness, which incurs high hardware cost since DRAM is very expensive. Recently, NVM Optane SSD has been considered as a promising underlying storage device due to its price advantage over DRAM and speed advantage over traditional slow block devices. However, to achieve a comparable efficiency performance with in-memory index, applying NVM to both latency and I/O bandwidth critical applications such as search engine still faces non-trivial challenges, because NVM has much lower I/O speed and bandwidth compared to DRAM.

Load balance is one of the major issues in large-scale search engines. A commonly used load balancing approach in search engine datacenters is to reassign index shards among machines. However, reassigning shards within stringent resource environments is challenging due to transient resource constraints (during reassignment, some resources are consumed simultaneously by a shard on the initial machine and its copy on the target machine).

Cloud gaming services enable users with heterogeneous device capabilities to get access to game titles with hardware demanding specifications. While visual quality requirements are to be satisfied by the cloud rendering servers, latency is one of the major problems which arises as most of the tasks are offloaded remotely. Cloud gaming players must experience latency below a certain acceptable limit for the game to be responsive with playable visual quality under limited bandwidth capacity. Playing multiplayer games in the cloud needs to cater for player interactions and their commonality especially if they are playing in the same virtual space. The main characteristic of cloud gaming is that the whole rendering pipeline occurs in the cloud; therefore, rendering optimization by reusing common information across players is possible by taking advantage of multi-view rendering. In this paper, we propose a cloud gaming architecture for MMORPGs which involves hundreds of players as well as online optimization heuristic algorithms on rendering server allocations in order to minimize rendering server rental cost from game provider’s point of view. In addition, we also compare the performance of those online heuristics with an offline lower bound in order to observe the scalability of the online scenario.

Data caching and sharing is an effective approach for achieving high performance to many applications in shared platforms such as the cloud. DRAM and SSD are two popular caching devices widely used by many large-scale data application systems such Hadoop and Spark. Due to the limited size of DRAM as well as the large access latency of SSD (relative to DRAM), there is a trend of integrating DRAM and SSD (called semi-external memory) together for large-scale data caching.

Cloud gaming has been very popular recently, but providing satisfactory gaming experiences to players at a modest cost is still challenging. Colocating several games onto one server could improve server utilization. To enable efficient colocations while providing Quality of Service (QoS) guarantees, a precise quantification of performance interference among colocated games is required. However, achieving such precise interference prediction is very challenging for games due to the complexity introduced by the contention on many shared resources across CPU and GPU. Moreover, the distinctive properties of cloud gaming require that the prediction model should be constructed beforehand and the prediction should be made instantaneously at request arrivals, which further increases the difficulty. The existing solutions are either not applicable or not effective due to many limitations. In this paper, we present GAugur, a novel methodology that enables highly accurate prediction of the performance interference among games arbitrarily colocated. By leveraging machine learning technologies, GAugur is able to capture the complex relationship between the interference and the contention features of colocated games. We evaluate GAugur through extensive experiments using a large number of real popular games. The results show that GAugur is able to identify whether a colocated game satisfies QoS requirement within an average error of 5%, and is able to quantify the performance degradation of a colocated game within an average error of 7.9%, which significantly outperforms the alternatives. Moreover, GAugur incurs an offline profiling cost linear to the number of games, and negligible overhead for online prediction. We apply GAugur to guiding efficient game colocations for cloud gaming. Experimental results show that GAugur is able to increase the resource utilization by 20% to 60%, and improve the overall performance by up to 15%, compared to the state-of-the-art solutions.

Secure Multi-Party Computation (MPC) is a promising privacy-preserving technology to enable multiple trustless parties to compute a function jointly without revealing private inputs to each other. With the fast development of MPC protocols, software implementation, and underlying computation infrastructure, MPC has developed from purely theoretical interest to tangible platform implementations for real-world applications. In this paper, we investigate multiple mechanisms to design efficient MPC algorithms by avoiding costly MPC operations and leveraging parallel operations. In order to speed up database table searching, a machine learning-based approach is proposed to completely avoid equality-check operations, playing the trade-off between efficiency and accuracy. According to our experimental results, a well-designed MPC algorithm could improve performance and scalability significantly, and thus make MPC technology practicable.

Cloud gaming has been increasing in popularity recently, but issues relating to maintaining low interaction delay for users to guarantee satisfactory gaming experience is still prevalent. Interaction delays caused by server-side processing are heavily influenced by how the processes partition the resources. However, finding the optimal partitioning policy that minimizes the response delay is complicated by several critical challenges. In this paper, we propose Themis, a system that enables efficient and adaptive online resource partitioning for reducing response delay in cloud gaming. Briefly, Themis employs machine learning technology to build a performance model which is able to capture the complex relationships between resource partition and system performance. With this model, Themis divides the processes into disjoint groups and partitions resources among process groups, which greatly simplifies the resource partition problem while ensuring high partitioning effectiveness. To tackle dynamic workload changes, Themis leverages reinforcement learning to learn how different partitioning actions affect system performance in an online manner, and adaptively choose the best actions for minimizing response delay in real time. We evaluate Themis in a real cloud gaming environment using several real games. The experimental results show that Themis can reduce the response delay by 17% to 36% compared to a system without resource partitioning, and outperforms other resource partitioning policies significantly. To the best of our knowledge, this is the first work to optimize response delay in cloud gaming through resource partitioning.

Search engines encounter a time vs. space trade-off: search responsiveness (i.e., a short query response time) comes at the cost of increased index storage. We propose a hybrid method which uses both (a) the recently published mapping-matrix-style index BitFunnel (BF) for search efficiency, and (b) the state-of-the-art Partitioned Elias-Fano (PEF) inverted-index compression method. We use this proposed hybrid method to minimize time while satisfying a fixed space constraint, and to minimize space while satisfying a fixed time constraint. Each document is stored using either BF or PEF, and we use a local search strategy to find an approximately optimal BF-PEF partition. Since performing full experiments on each candidate BF-PEF partition is impractically slow, we use a regression model to predict the time and space costs resulting from candidate partitions (space accuracy 97.6%; time accuracy 95.2%). Compared with a hybrid mathematical index (Ottaviano et al., 2015), the time cost is reduced by up to 47% without significantly exceeding its size. Compared with three mathematical encoding methods, the hybrid BF-PEF index allows performing list intersection between around 16% to 76% faster (without significantly increasing the index size). Compared with BF, the index size is reduced by 45% while maintaining an intersection time comparable to that of BF.

Containerization has been used in many applications for isolation purposes due to its lightweight, scalable, and highly portable properties. However, to apply containerization in large-scale Internet data centers faces a big challenge. Services in data centers are always instantiated as a group of containers, which often generate heavy communication workloads and therefore resulting in inefficient communications and downgraded service performance. Although assigning the containers of the same service to the same server can reduce the communication overhead, this may cause heavily imbalanced resource utilization since containers of the same service are usually intensive to the same resource. To reduce communication cost as well as balance the resource utilization in large-scale data centers, we further explore the container distribution issues in a real industrial environment and find that such conflict lies in two phases-container placement and container reassignment. The objective of this paper is to address the container distribution problem in these two phases. For the container placement problem, we propose an efficient communication aware worst fit decreasing algorithm to place a set of new containers into data centers. For the container reassignment problem, we propose a two-stage algorithm called Sweep&Search to optimize a given initial distribution of containers by migrating containers among servers. We implement the proposed algorithms in Baidu's data centers and conduct extensive evaluations. Compared with the state-of-the-art strategies, the evaluation results show that our algorithms perform better up to 70% and increase the overall service throughput up to 90% simultaneously.

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice.

With the development of the information age, many large database applications have introduced distributed in-memory object caching systems, of which Memcached is one of the most typical. However, Memcached does not have fault-tolerant capabilities. In order to make Memcached enable fault tolerance, Cocytus introduced Reed-Solomon codes and distributed protocols into Memcached. Cocytus saves significant memory compared to primary-backup replication when tolerating the same number of failures. However, the relatively complex finite-field calculations used by RS codes and the high network transmission cost during data reconstruction are becoming new bottlenecks. This paper introduces RDP codes into distributed Memcached to optimize the calculation performance in Cocytus. In addition, this paper adopts RDOR scheme and Collective Reconstruction Read to speed up the data reconstruction. Compared with Cocytus, which uses RS codes for fault tolerance, the new distributed Memcached with 4 data nodes and 2 check parity nodes reduces reconstruction overhead by up to 31 %.

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe that the index shard replication strategy could have a significant impact on the resource utilization of machines. In this paper, we investigate the index shard replication problem with the goal of improving the resource utilization of machines in search engine datacenters. We formulate the problem as a variant of the Multi-Dimensional Vector Bin Packing Problem and propose several strategies to approximate the optimal solution. The proposed strategies are evaluated by extensive experiments using data from real commercial search engines. The results demonstrate the effectiveness of the proposed strategies. Our work also yields many insights about the impact of different input properties on the performance and the key factors that each strategy is sensitive to. We believe that this paper will provide valuable guidance to the choice of the index shard replication strategy in practice.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. With MCG, a game server and a set of rendering servers for the players need to be located and launched in the clouds for each game session. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. The MCG server allocation problem is hard to solve optimally. We propose several efficient heuristics to address the problem and carry out theoretical analysis for the proposed hill-climbing algorithm. We conduct extensive experiments using real Internet latency and cloud pricing datasets to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on, and cross-platform. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that the software storage cost could be substantial compared to the server running cost in cloud gaming using elastic cloud resources. Therefore, in this article, we address the server provisioning problem for cloud gaming to optimize both the server running cost and the software storage cost. We find that the distribution of game software among servers and the selection of server types both trigger tradeoffs between the software storage cost and the server running cost in cloud gaming. We formulate the problem with a stochastic model and employ queueing theory to conduct a solid theoretical analysis of the system behaviors under different request dispatching policies. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed Ordered and Genetic algorithms are computationally efficient, nearly cost-optimal, and highly robust to dynamic changes.

Containers have been used in many applications for isolation purposes due to the lightweight, scalable and highly portable properties. However, to apply containers in virtual network functions (VNFs) faces a big challenge because high-performance VNFs often generate frequent communication workloads among containers while the container communications are generally not efficient. Compared with hardware modification solutions, properly distributing containers among hosts is an efficient and low-cost way to reduce communication overhead. However, we observe that this approach yields a trade-off between the communication overhead and the overall throughput of the cluster. In this paper, we focus on the communication-aware container redistribution problem to optimize the communication overhead and the overall throughput jointly for VNF clusters. We propose a solution called FreeContainer which utilizes a novel two-stage algorithm to re-distribute containers among hosts. We implement FreeContainer in Baidu clusters with 6000 servers and 35 services deployed. Extensive experiments on real networks are conducted to evaluate the performance of the proposed approach. The results show that FreeContainer can increase the overall throughput up to 90% with significant reduction on communication overhead.

Cloud gaming has gained significant popularity recently due to many important benefits such as removal of device constraints, instant-on and cross-platform, etc. The properties of intensive resource demands and dynamic workloads make cloud gaming appropriate to be supported by an elastic cloud platform. Facing a large user population, a fundamental problem is how to provide satisfactory cloud gaming service at modest cost. We observe that software maintenance cost could be substantial compared to server running cost in cloud gaming. In this paper, we address the server provisioning problem for cloud gaming to optimize both server running cost and software maintenance cost. We find that the distribution of game softwares among servers triggers a trade-off between the software maintenance cost and server running cost. We formulate the problem with a stochastic model and employ queueing theories to conduct solid theoretical analysis. We then propose several classes of algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using real-world parameters. The results show that the proposed algorithms are computationally efficient, nearly cost-optimal and highly robust to dynamic changes.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by “pay-as-you-go” billing. The above job dispatching problem can be modeled as a variant of the dynamic bin packing (DBP) problem known as MinUsageTime DBP. In this paper, we study the competitiveness bounds of MinUsageTime DBP. We establish an improved lower bound on the competitive ratio of Any Fit family of packing algorithms, and a new upper bound of μ + 3 on the competitive ratio of the commonly used First Fit packing algorithm, where μ is the max/min job duration ratio. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Cloud-based systems often face the problem of dispatching a stream of jobs to run on cloud servers in an online manner. Each job has a size that defines the resource demand for running the job. Each job is assigned to run on a cloud server upon its arrival and the job departs after it completes. The departure time of a job, however, is not known at the time of its arrival. Each cloud server has a fixed resource capacity and the total resource demand of all the jobs running on a server cannot exceed its capacity at all times. The objective of job dispatching is to minimize the total cost of the servers used, where the cost of renting each cloud server is proportional to its running hours by "pay-as-you-go" billing. The above job dispatching problem can be modeled as a variant of the Dynamic Bin Packing (DBP) problem known as MinUsageTime DBP. In this paper, we develop new approaches to the competitive analysis of the commonly used First Fit packing algorithm for the MinUsageTime DBP problem, and establish a new upper bound of μ+4 on the competitive ratio of First Fit packing, where μ is the ratio of the maximum job duration to the minimum job duration. Our result significantly reduces the gap between the upper and lower bounds for the MinUsageTime DBP problem to a constant value independent of μ, and shows that First Fit packing is near optimal for MinUsageTime DBP.

Advances in cloud computing and GPU virtualization are allowing the game industry to move into a cloud gaming era. While shifting standalone video games to the cloud gaming mode is straightforward, adapting multiplayer online games to the cloud gaming paradigm faces unique challenges. In this paper, we consider multiplayer cloud gaming (MCG), which is the natural integration of multiplayer online gaming and cloud gaming paradigms. We formulate an MCG server allocation problem with the objective of minimizing the total server rental and bandwidth cost charged by the cloud to support an MCG session. We propose several efficient heuristics to address the MCG server allocation problem which is hard to solve optimally. We conduct extensive experiments using real Internet latency and cloud pricing data to evaluate the effectiveness of our proposed algorithms as well as several alternatives. Experimental results show that our best algorithm can achieve near-optimal cost under real-time latency constraints.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used overtime. It is motivated by the request dispatching problem arising from cloud gaming systems. We analyze the competitive ratios of the modified versions of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently open bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than μ + 1, where μ is the ratio of the maximum item duration to the minimum item duration. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than 1/β of the bin capacity (β> 1 is a constant), the competitive ratio has an upper bound of β/β-1·μ+3β/β-1+ 1. For the general case, the competitive ratio of First Fit packing has an upper bound of 2μ + 7. We also propose a Hybrid First Fit packing algorithm that can achieve a competitive ratio no larger than 5/4 μ + 19/4 when μ is not known and can achieve a competitive ratio no larger than μ + 5 when μ is known.

In this demonstration, we propose MASTER, a set of toolkits for cross-platform application streaming that is able to utilize elastic resources on public clouds. MASTER has many useful features. It provides full control of resource acquisition and request dispatching, requires only a browser on the client side for user interactions, and incorporates an input transformer to assist touchscreen device users to naturally interact with desktop applications that need keystroke and mouse control. MASTER also supports session concurrency (serving multiple streaming sessions on a single cloud server instance), thereby improving resource utilization and cutting the cloud bill.

Cloud gaming is becoming increasingly popular. The basic idea of cloud gaming is to run games on cloud servers and let players interact with games through thin clients. As the player population grows, the cloud gaming service provider needs to maintain a large number of cloud servers for running the game instances requested by the players. A primary concern of the cloud gaming service provider is the total running cost of the cloud servers. In this paper, we study the problem of how to dispatch the play requests to the cloud servers in a cloud gaming system. We show that the dispatching strategy of play requests may heavily affect the total service cost of the cloud gaming system. The play request dispatching problem can be considered as a variant of the dynamic bin packing problem. However, we show that the classical bin packing algorithms such as First Fit (FF) and Best Fit (BF) are not efficient in terms of resource usage in cloud gaming due to the diurnal workload pattern of online games. To address this issue, we propose an efficient request dispatching algorithm that assigns play requests according to the predicted ending times of game sessions. We also assess several classes of prediction algorithms and select a neural-network-based algorithm to predict the ending times of game sessions. We conduct extensive evaluations of the proposed algorithms using real traces from different types of online games. The experimental results show that the proposed dispatching algorithm with neural-network-based prediction can reduce the resource waste of the cloud servers and thus decrease the total service cost compared to the FF and BF algorithms. The reduction in the resource waste is particularly significant for match-based games such as Defense of the Ancient and World of Tank.

In Distributed Virtual Environments (DVEs), the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. In the zone-based Multi-server Distributed Virtual Environment (MSDVE), zone mapping and client assignment are two key issues in the design of an efficient and scalable MSDVE. Most of the existing work on the zone mapping and client assignment issues in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or reduce transmission delay. In this paper, we study the zone mapping and client assignment issues from a new perspective aiming to reduce the inconsistency of a DVE. Using the time-space inconsistency metric, we formally formulate the problem as a mix integer programming problem. The zone mapping and client assignment strategy is proposed which consists of a centralized algorithm for initialization and a distributed adaptive tuning algorithm for running system. Extensive experiments were conducted both by simulation and real system for evaluating the performance of the proposed solutions and results are reported in the paper.

Dynamic Bin Packing (DBP) is a variant of classical bin packing, which assumes that items may arrive and depart at arbitrary times. Existing works on DBP generally aim to minimize the maximum number of bins ever used in the packing. In this paper, we consider a new version of the DBP problem, namely, the MinTotal DBP problem which targets at minimizing the total cost of the bins used over time. It is motivated by the request dispatching problem arising in cloud gaming systems. We analyze the competitive ratios of the commonly used First Fit, Best Fit, and Any Fit packing (the family of packing algorithms that open a new bin only when no currently opened bin can accommodate the item to be packed) algorithms for the MinTotal DBP problem. We show that the competitive ratio of Any Fit packing cannot be better than the max/min item interval length ratio μ. The competitive ratio of Best Fit packing is not bounded for any given μ. For First Fit packing, if all the item sizes are smaller than W⁄k (W is the bin capacity and k≥1 is a constant), it has a competitive ratio of k⁄k-1μ + 6k⁄k-1 + 1. For the general case, First Fit packing has a competitive ratio of 2μ + 13. We also propose a Modified First Fit packing algorithm that can achieve a competitive ratio of 8⁄7μ + 55⁄7 when μ is not known and can achieve a competitive ratio of μ + 8 when μ is known.

By sharing resources among peers in peer-to-peer network, application layer multicast (ALM) has been shown an efficient way to improve the scalability and reduce the latency of communication. To deploy ALM in peer-to-peer distributed interactive applications (DIAs), the property of many-to-many communication of DIA demands multiple multicast trees to be constructed in the overlay. Therefore, how to efficiently allocate resources among multiple trees to maximize the benefit is an important and challenging issue. In this paper, we study the problem of building ALM trees with minimum total end-to-end delay to receivers in peer-to-peer DIAs with resource constraints on network bandwidth. The end-to-end delay from a sender to receivers in a multicast tree consists of the link delay as well as the packet queuing delay at intermediate peers, while the latter is often ignored or not well studied in the previous work. In this paper, we explicitly establish the relationship between the queuing delay at peers and the topology of multicast trees in peer-to-peer DIAs. Based on the relationship, the above mentioned problem is defined and we prove that it is NP-complete. We present a centralized heuristic algorithm to obtain an approximate solution. Moreover, distributed algorithms are also investigated to refine the topology in practical systems with dynamic changes. Extensive experiments were conducted by simulations to evaluate the proposed algorithms and results are reported in the paper.

In DVEs, the primary task is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. One of the key issues in the design of an efficient and scalable Multi-server Distributed Virtual Environment (MSDVE) is the partitioning, which concerns with efficiently distributing the workload generated in the virtual environment among multiple servers in the system. Most of the existing work on the partitioning issue in MSDVE aims to either balance workload among servers, reduce inter-server communication, and/or improve the interactivity of DVE. In this paper, we study the partitioning issue from a new perspective and aim to reduce the time-space inconsistency of a DVE. Time-space inconsistency is a consistency metric, which has been proven to be an effective performance measure of DVEs. Using the time-space inconsistency metric, we formally formulate our partitioning problem as a mix integer programming problem and propose a solution based on Alternating Optimization (AO) technique. An iterative partitioning algorithm is also developed accordingly. The algorithm gives a partition as well as the corresponding update schedule to minimize the total time-space inconsistency. Different from most of the existing work, the resulted partition is avatar-based rather than zone/region-based. To evaluate the performance of the proposed partitioning algorithm, extensive experiments were conducted and results are reported in the paper.

The primary task of distributed virtual environments (DVEs) is to maintain a consistent view of the virtual world among all users. Multi-server architecture has been shown to have good scalability to support a large population of users in DVEs. However, some of the servers' resources like CPU, memory and network bandwidth can still get saturated as the scale of DVE increases. In this case, state updates cannot be disseminated timely and the consistency of the virtual world cannot be guaranteed. In this paper, we investigate how to efficiently use the limited resources for state update to minimize inconsistency in multi-server DVEs. Using time-space inconsistency metric, we firstly prove that periodic state update will result in minimal inconsistency for each replica. Then, in order to determine the optimal update periods for replicas to minimize the total time-space inconsistency of the DVE, we formulate the problem as a convex optimization problem with inequality constraints. Finally, an interior point method is adopted to solve the problem and the performance is evaluated using simulation results.

In this paper, we propose an innovative debugging tool called MKtrace to help programmers identify bugs in multi-threaded programs on multiprocessor systems with little overhead. Unlike the traditional debugging tools, we use the trace log to analyze the cause of a crash or any abnormal behaviour. Bugs can be identified within the log file, not directly at run time. Also, a key advantage of MKtrace is its insignificant overhead. The main idea of MKtrace is to monitor all the processes or threads from a program when they switch out in the kernel. We log the call stack of each thread, and then we analyze the log in the user space. We implemented MKtrace on Linux AS3 with two processors and achieved promising results during our experiments.