Graph Neural Network (GNN) is an important tool in deep learning to handle structured data, where graphs with nodes and edges represent entities and their relationships. Various challenges arise when GNN is tree-shaped, with irregular connectivity patterns and varying depth. It is difficult to distribute and process the dynamic structure for parallel execution on multiple GPUs. In addition, tree data dependency demands the processing of parent nodes before their children, severely limiting execution parallelism. This research aims to improve the training speed of tree-shaped GNN on multi-GPU systems. First, we introduce a cost model that estimates the running time of the training across multiple GPUs. Then, we demonstrate that finding an optimal way to distribute tree-structured data across GPUs is an NPcomplete problem on this cost model. We then propose a practical heuristic method for distributing data that improves efficiency while maintaining training quality. The heuristic method first assigns data to batches based on our cost model and then assigns data in each batch to the devices. We also show that our device-assigning algorithm is a 4-approximation algorithm. That is, it guarantees that its cost is four times the optimal running time in each training batch, ensuring that it performs effectively in practice. We implement the algorithm and conduct the experiments. The results show that our algorithm achieves a significant decrease in training time. The speedup is up to 1.86 for two GPUs, 3.43 for four GPUs, and 7.25 for eight GPUs.

As neural network models become gigantic, they increasingly demand more time and memory for training. To meet these demands, advanced parallel computing techniques have become essential. Our research focuses on hybrid parallelism, an extension of pipeline parallelism. Pipeline parallelism splits the neural network into sub-networks distributed across a sequence of processing units, enabling simultaneous processing of different data segments on each device. Hybrid parallelism extends this concept by allocating multiple devices to each sub-network. Our research focuses on optimizing hybrid parallelism by improving how the model is partitioned and how computational devices are assigned. We address these issues by modeling the neural network as a directed acyclic graph of tensor operators, and then demonstrating that optimally partitioning this graph is NP-complete. Then, we propose a two-step approach. The first step is to determine a sequence of nodes. The second step is dynamic programming, which partitions the sequence to maintain balance across the assigned devices. In transforming the graph into a sequence, we explore two methods: one employs topological sorting, while the other clusters non-sequential subgraphs. We apply both methods and select the more effective one based on performance outcomes. We implement our algorithm and conduct experiments. The results show substantial enhancements in both the speed of partitioning and training throughput, with speedups reaching up to 23 in partitioning time and a 1.3 -fold increase in training throughput.

In recent years, Transformer has become an important architecture in language models and has achieved high performance in many natural language processing tasks. However, deploying Transformer architectures efficiently faces challenges because of their large model size and high inference time. Weight pruning is a prominent model compression technique that removes some weights in a model. However, after pruning, Transformer models require repeating the whole training process, including pre-training on a large generalized dataset and fine-tuning on a small downstream dataset, to recover the accuracy. The whole training process takes a long time and requires many computation resources. To address the challenge, this work proposes a pruning method that combines with knowledge distillation to avoid a long re-training time while recovering the accuracy. We use the N:m pruning method that is extended from NVIDIA's 2:4 pruning to compress the Transformer model. After pruning, we retrain the model by leveraging knowledge distillation to make the pruned model learn from the dense model. With this method, the pruned model can achieve comparable accuracy by using only downstream datasets and take much less time than traditional retraining. The experimental results show that DistilBERT in a 1:4 structure can achieve comparable accuracy on the SQuAD v1.1 and v2.0 datasets and a$\mathbf{1.7}\times$speedups in inference time compared to the original dense model.

Convolutional neural networks (CNNs) have achieved immense success in computer vision and other field of science. Despite the achievements, state-of-the-art CNN models have grown to gigantic sizes that demand a lot of computing power and memory resources. As a model compression technique, parameter pruning can lower the computation and memory a CNN model needs. Previous work has proposed a parameter pruning method, which compresses the neural networks by eliminating the rows and columns of the weight matrices. Removing rows and columns preserves the dense structure of the weight matrix, rather than the sparse structure produced by unstructured pruning. Although row-and-column pruning effectively reduces the model size, making the model as compact as possible without sacrificing accuracy remains a challenge. We prove that the row-and-column pruning problem is an NP-complete problem, and we propose two approximation algorithms that provide solutions within twice the cost of the optimal solution. We also show that the approximation ratio cannot be improved for these two algorithms. Finally, we propose two schemes based on simulated annealing to solve the row-and-column pruning problem. The two proposed schemes improve accuracy by 2.7% and 1.6%, respectively, on the ResNet-18 model with 93% sparsity using the Food-101 dataset.

In recent years, container technology has gained significant attention in the software industry, with many businesses opting for its elasticity, cost-effectiveness, and ease of implementation. The most common way to ensure a seamless user experience is to keep a substantial number of containers active throughout the day, which causes resource over-provision. Conversely, closing the container right after handling the requests can reduce memory consumption but generate a cold start whenever the request arrives. Cold start occurrence and resource usage is a trade-off and presents a significant challenge on the container platform.To address this challenge, we observe that serving consecutive requests with the same container can notably decrease the number of cold starts. We propose TAC, a Temporal Adjacency Function Clustering algorithm, to meet the challenge. TAC selects the functions with time adjacency requests into a cluster from the historical data. TAC packs functions serving time adjacency requests into a cluster to reduce cold starts and enable efficient resource utilization. The experiment result shows that TAC reduces 8% cold start occurrences and 53% memory usage with the real-world traces compared to the state-of-the-art methods, e.g., Defuse [1] and Hybrid histogram policy [2].

Weight pruning is a technique to remove redundant or unimportant weights from the network. It can help reduce the size and computational cost of neural networks while preserving their accuracy. In this paper, we aim to design efficient CNN models with N:M pruning on the CPU. We propose a dynamic programming algorithm to find a good sparsity ratio for every layer under a total time budget based on the execution times and L1 norm of layers. After deciding the sparsity ratio of each layer, we leverage the auto-tuner of the TVM compiler to search for an optimization schedule of the pruned convolution to accelerate fine-grained pruned models. Experimental results show that our scheme can achieve 0.35% accuracy improvement and a 1.55× speedup on VGG-16 with ImageNet than the dense model.

This paper introduces a scheme that predicts the difficulty of classifying an image, reduces the image size according to the prediction, and speeds up the inference time. We observe that models such as ResNet-50 and EfficientNet can classify specific images correctly even after downsizing. We consider these correctly classified images as easy images and others as complex images. Then we collect images with different difficulties and train a difficulty model that classifies the difficulty of an image and determines whether we should downsize an image. In addition, we use an inference model that consists of multiple models for classifying images of different image sizes, and each model is trained with specific datasets to increase its accuracy for the particular image sizes. Finally, we concatenate the difficulty and inference models to get the hybrid model. Our experiments use MobileNetV3-small as the lightweight difficulty model, and ResNet- 50 and EfficientNet-B4 as the inference models. Experimental results indicate a trade-off between the inference time and the image classification accuracy, and the confidence threshold of the difficulty model affects this trade-off. If the confidence threshold of the difficulty model is high/low, the inference time and the image classification accuracy increase/decrease. As a result, the user can control the behavior of the hybrid model by adjusting the confidence threshold of the difficulty model and finding a customized balance between the inference time and the classification accuracy.

Distributed machine learning is essential for applying deep learning models with many data and parameters. Current researches on distributed machine learning focus on using more hardware devices powerful computing units for fast training. Consequently, the model training prefers a larger batch size to accelerate the training speed. However, the large batch training often suffers from poor accuracy due to poor generalization ability. Researchers have come up with many sophisticated methods to address this accuracy issue due to large batch sizes. These methods usually have complex mechanisms, thus making training more difficult. In addition, powerful training hardware for large batch sizes is expensive, and not all researchers can afford it. We propose a dual batch size learning scheme to address the batch size issue. We use the maximum batch size of our hardware for maximum training efficiency we can afford. In addition, we introduce a smaller batch size during the training to improve the model generalization ability. Using two different batch sizes in the same training simultaneously will reduce the testing loss and obtain a good generalization ability, with only a slight increase in the training time. We implement our dual batch size learning scheme and conduct experiments. By increasing 5% of the training time, we can reduce the loss from 1.429 to 1.246 in some cases. In addition, by appropriately adjusting the percentage of large and small batch sizes, we can increase the accuracy by 2.8% in some cases. With the additional 10% increase in training time, we can reduce the loss from 1.429 to 1.193. And after moderately adjusting the number of large batches and small batches used by GPUs, the accuracy can increase by 2.9%. Using two different batch sizes in the same training introduces two complications. First, the data processing speeds for two different batch sizes are different, so we must assign the data proportionally to maximize the overall processing speed. In addition, since the smaller batches will see fewer data due to the overall processing speed consideration, we proportionally adjust their contribution towards the global weight update in the parameter server. We use the ratio of data between the small and large batches to adjust the contribution. Experimental results indicate that this contribution adjustment increases the final accuracy by another 0.9%.

Online Judge Systems are designed for the reliable evaluation of source code submitted by users. The system queues the code, compiles and tests them typically in a FIFO manner. However, we found that the cloud-native design of an online judge system is still a pending issue. Many existing open-source online judge systems are hard to deploy and scale, due to the tight coupling with some specific environments and the vague boundaries in their system architectures. In addition, these online judge systems hardly provide the support of resource scheduling as they are usually more concerned about the homogeneity of the resources. In this research, we design and develop a cloud-native online judge system that is able to (1) be built and run stably in dynamic environments (2) scale vertically and horizontally to the workload (3) do resource scheduling over CPUs and GPUs. Furthermore, this research also analyzes the consequence of adopting some modernly advocated design approaches and technologies; these are: microservice architecture design, event-driven architecture, domain-driven design, and containerization technologies such as Docker and Kubernetes.

Convolution neural networks (CNNs) are essential in many machine learning tasks. Current deep learning frameworks and compilers usually treat the neutral network as a DAG (directed acyclic graph) of tensor operations and execute them one at a time according to a topological order, which respects the dependency in the DAG. There are two issues with this general approach. First, new CNNs have branch structures, and they form complex DAGs. These DAGs make it hard to find a good topology sort order that schedules operators within a GPU. Second, modern hardware has high computational power, which makes running operators sequentially on modern hardware under-utilizes resources. These two issues open the possibility of exploiting inter-operator parallelism, i.e., parallelism among independent operators in the DAG, to utilize the hardware resources more efficiently. In this work, we formally define the DAG scheduling problem that addresses the resource contention and propose an early-start-time-first algorithm with two heuristic rules for exploiting parallelism between independent operators. Experimental results show that our method improves the performance by up to 3.76× on RTX 3090 compared to the sequential execution.

Video captioning is a core technology to many important applications, such as AI-assisted medical diagnosis, video question answering, storytelling through videos, and lip-reading. Video captioning employs a hybrid CNN + RNN model. Accelerating such a hybrid model on a heterogeneous system is challenging for two reasons. First, CNN and RNN exhibit very different computing behaviors, making the mapping between computation and heterogeneous devices difficult. Second, data dependency exists between the CNN and RNN within a video frame and between adjacent RNNs across video frames. These data dependencies prohibit the full parallelization of the hybrid model. The issues also include the utilization of accelerator resources, which is critical to maximizing the performance. In this work, we propose a fine-grained scheduling scheme for mapping computation and devices within a video frame, and a pipeline scheduling scheme for exploiting maximum parallelism between the execution of the video frames. In addition, we propose two capacity-guided scheduling methods. On the server, the concurrent kernel execution mechanism is exploited for improving GPU utilization. On the edge platform, we rearrange CNN computation among the CPU and EdgeTPUs guided by the EdgeTPU’s SRAM capacity so that balanced computation is achieved and off-chip memory overhead is minimized. Experimental results show that our scheduling scheme improves video captioning performance by up to 3.24 \( \times \) with CPU + GPU collaboration over the GPU-only execution. On an edge platform with an ARM CPU and two EdgeTPUs, our CPU + EdgeTPU scheduling exhibits outstanding performance, which achieves up to 54.9 \( \times \) speedup compared to using ARM CPU only and can perform video captioning of 59 frames per second.

Deep Neural Networks (DNNs) are very popular in many machine learning domains. To achieve higher accuracy, DNNs have become deeper and larger. However, the improvement in accuracy comes with the price of the longer inference time and energy consumption. The marginal cost to increase a unit of accuracy has become higher as the accuracy itself is rising.The Branchynet, known as early exits, is an architecture to address increasing marginal cost for improving accuracy. The Branchynet adds extra side classifiers to a DNN model. The inference on a significant portion of the samples can exit from the network earlier via these side branches if they already have high confidence in the results.The Branchynet requires manually tuning the learning hyperparameters, e.g., the locations of branches and the confidence threshold for early exiting. The effectiveness of this manual tuning dramatically impacts the efficiency of the tuned networks. To the best of our knowledge, there are no efficient algorithms to find the best branch location, which is a trade-off between the accuracy and inference time on the Branchynet.We propose an algorithm to find the optimal branch locations for the Branchynet. We formulate the problem of finding the optimal branch location for the branchynet as an optimization problem, and prove that the branch placement problem is an NPcomplete problem. We then derive dynamic programming that runs in pseudo-polynomial time and solves the branch placement problem optimally.We also implement our algorithm and solve the branch placement problems on four types of VGG networks. The experiment results indicate that our dynamic programming can find the optimal branch locations for generating the maximum number of correct classifications within a given time budget. We also run the four VGG models on a GeForce RTX-3090 GPU with the branch combination found by the dynamic programming. The experiment results show that our dynamic programming accurately predicts the number of correct classifications and the execution time on the GPU.

Video captioning is the core technology to drive the development of many important multidisciplinary applications, such as AI-assisted medical diagnosis, storytelling through videos, video question answering, lip-reading, just to name a few. Video captioning employs a hybrid CNN+RNN neural network model to translate video scenes into natural language descriptions. For deep learning inference, a typical approach is running both the CNN and the RNN on a GPU. Such a GPU-only approach often suffers long inference time due to underutilization of the computing power offered by the CPU+GPU heterogeneous system architecture, which is a common architecture in modern computers.This work is an early effort to tackle the performance issue of performing deep learning inference using a hybrid CNN+RNN model on a heterogeneous system with a CPU and a GPU. This is a challenging task because of (1) CNN and RNN exhibit very different computing behaviors. This raises the question of how to split the two models into computing tasks and properly assign the tasks to the CPU and the GPU to minimize the inference time for a video frame, and (2) Data dependency exists between the CNN and the RNN within a video frame, as well as between the adjacent RNNs across two video frames. These data dependencies prohibit full parallelization of the hybrid model. To solve these two problems, we propose two optimizations: a fine-grained scheduling scheme for mapping computation and devices within a video frame, and a pipeline scheduling scheme to exploit maximum parallelism between the execution of the video frames. To facilitate our optimizations, we also develop an accurate regression-based cost model to predict the computation time of CNN/RNN operations and the communication time for moving data between CPU and GPU. Experimental results show that our optimization improves the performance of video captioning by up to 3.24× on the CPU+GPU system, compared with the GPU-only execution.

Parallel asynchronous stochastic dual coordinate descent algorithm (PASSCoDe) is an efficient method to train linear models in multi-core shared-memory systems. PASSCoDe enjoys a good speedup when the number of threads is less than 8 on sparse datasets, i.e., the percentage of nonzero elements in the training data is relatively small. However, due to the memory conflict and delayed parameter access problem in parallel execution, it often diverges or does not converge to the best accuracy as a serial dual coordinate descent algorithm does. In this paper, we propose two algorithms – Adaptive Hybrid algorithm and Lazy-Sync algorithm, to overcome the convergence issues in parallel execution. Both algorithms use the current accuracy to guide the execution and strike a balance between accuracy and efficiency. Experimental results indicate that both algorithms converge to the same high accuracy as a sequential program does on all datasets tested except on an extremely small one. On the other hand, PASSCoDe sometimes converges to a less accurate value or does not converge at all on some datasets. Our methods also outperform PASSCoDe-Fix, an improved version of PASSCoDe, in stable convergence, execution speed, and scalability. For example, the Adaptive Hybrid algorithm runs up to 2.8 times faster than PASSCoDe-Fix, and the Lazy-Sync algorithm runs 11 times faster than PASSCoDe-Fix on dataset covtype with 10 threads.

In this paper, we propose an adaptive layer expansion algorithm to reduce the training time of deep neural networks without noticeable loss of accuracy. Neural networks have become much larger to improve accuracy. The size of such networks makes them time-consuming to train. Hence, we propose an adaptive layer expansion algorithm that reduces training time by dynamically adding nodes where they are necessary to improve the training efficiency while not losing accuracy. We start with a smaller model of only a fraction of parameters of the original model, then train the network and add nodes to specific layers determined by the stability of gradients. The algorithm repeatedly adds nodes until it reaches a threshold and trains the model until the accuracy converges. The experiment results indicate that our algorithm only uses a quarter of computation time of a full model and achieves 64.1% accuracy on MobileNet with dataset CIFAR100, which is only 2% less than the complete model. The algorithm stops adding nodes when it has only half of the parameters of the original model. As a result, this new model provides fast inference in those environments where both the computation power and memory storage are limited, such as mobile devices.

Convolutional neural networks (CNN) achieves tremendous success in computer vision. However, due to the increasing number of parameters and the limitation of hardware/software resources, model compression has become an important issue, so we should reduce the size of CNN's and improve the train and inference speed. This paper focuses on channel pruning, a model compression technique that evaluates the importance of channels within a convolution layer, and prune away the less important ones.In this paper, we propose a mutual information metric to prune the network. By measuring the entropy of feature maps, we can estimate how much information goes through each channel during the label recognition and prune away those that have the least information. We compute the mutual information between feature maps and labels, which is the only information relevant to the label classification.We also propose a weighted mutual information metric that further improves the accuracy. We observe from our experiments that the weighted mutual information metric achieves better accuracy than the classic L1-norm metric [1] and the original entropy metric [2]. We also discover that the classic L1-norm pruning metric can be improved by computing the L1-norm of output filter weights (denoted as output L1) instead of input filter weights (denoted as input L1).We test our channel pruning algorithms on the SVHN, the CIFAR-10, and the CIFAR-100 datasets using Simplenet [3]. When we prune away 70% parameters for all convolution layers, our weighted mutual information method has 1.52%, 13.24%, and 7.90% higher accuracy than the output L1 metric on these three datasets. In the global pruning experiment, our weighted mutual in-formation metric has about 2% higher accuracy than the output L1 metric when we removed 55% of parameters from the SVHN dataset. On the CIFAR-100 dataset, our metric is 1.5% more accurate than the output L1 metric when there are only 53% of the parameters remain. The only exception is the CIFAR-10 dataset, where our metric is 5% less accurate than the output L1 metric when there are 40% of the parameters remain.

In this paper, we propose a bicameralism voting to improve the accuracy of a deep learning network. After we train a deep learning network with existing data, we may want to improve it with some newly collected data. However, it would be time consuming if we retrain the model with all the available data. Instead, we propose a collective framework that train models on mobile devices with new data (also collected from the mobile devices) via transfer learning. Then we collect the predictions from these new models from the mobile devices, and achieve more accurate predictions by combining their predictions via voting. The proposed bicameralism voting is different from federated learning, since we do not average the weights of models from mobile devices, but let them vote by bicameralism. The proposed bicameralism voting mechanism has three advantages. First, this collective mechanism improves the accuracy of the deep learning model. The accuracy of bicameralism voting (VGG-19 on the data set Food-101 dataset) is 77.838%, higher than that of a single model (75.517%) with the same amount of training data. Second, the bicameralism voting saves computation resource, because it only updates an existing model, and can be done in parallel by multiple devices. For example, in our experiments to update an existing model via transfer learning takes about 10 minutes on a server, but to train a model from scratch with both the original and the new data will take more than a week. Finally, the bicameralism voting is flexible. Unlike federated learning, bicameralism voting can use any architecture of model, any preprocessing of input data, and any format of model when the models are trained on different mobile devices.

Summary As mobile devices become more prevalent, users tend to reassess their expectations regarding the personalization of mobile services. The data collected by a mobile device's sensors provide an opportunity to gain insight into the user's profile. Recently, deep learning has gained momentum and has become the method of choice for solving machine learning problems. Interestingly, training a deep neural network on a mobile device is often mistakenly regarded as cumbersome. For instance, several deep learning frameworks only provide a CPU‐based implementation for prediction tasks on a mobile device. In contrast to servers, a mobile computing environment imposes many domain‐specific constraints that invite us to review the general computing approach used in a deep learning framework implementation. In this paper, we propose a deep learning framework that has been specifically designed for mobile device platforms. Our approach relies on the collaboration of the multicore CPU and the integrated GPU to accelerate deep learning computation on mobile devices. Our work exploits the shared memory architecture of mobile devices to promote CPU‐GPU collaboration without any data copying. We analyze our approach with regard to three factors: performance/portability trade‐off, power efficiency, and memory management.

Deep learning has become one of the most promising approaches to solve the artificial intelligence problems. Training large-scale deep learning models efficiently is challenging. A widely used approach to accelerate the training process is by distributing the computation across multiple nodes with a centralized parameter server. To overcome the communication overhead caused by exchanging information between workers and the parameter server, three types of optimization methods are adopted - data placement, consistency control, and compression. In this paper, we proposed modularized parameter server, an architecture composed of key components that can be overridden without much effort. This allows developers to easily incorporate optimization techniques in the training process instead of using ad-hoc ways in existing systems. With this platform, the users can analyze different combinations of techniques and develop new optimization algorithms. The experiment results show that, compared with Google's distributed TensorFlow, our distributed training system based on the proposed modularized parameter server can achieve near-linear speedup for computing and reduce half of the training time by combining multiple optimization techniques while maintaining the convergent accuracy.

Deep learning is now the most promising approach to develop human-intelligent computer systems. To speedup the development of neural networks, researchers have designed many distributed learning algorithms to facilitate the training process. In these algorithms, people use a constant to indicate the communication period for model/gradient exchange. We find that this type of communication pattern could incur unnecessary and inefficient data transmission for some training methods e.g., elastic SGD and gossiping SGD. In this paper, we propose an adaptive communication method to improve the performance of gossiping SGD. Instead of using a fixed period for model exchange, we exchange the models with other machines according to the change of the local model. This makes the communication more efficient and thus improves the performance. The experiment results show that our method reduces the communication traffic by 92%, which results in 52% reduction in training time while preserving the prediction accuracy compared with gossiping SGD.

Infrastructure-as-a-Service (IaaS) is a popular form of cloud computing that provides virtualized computing resources. The current trend of IaaS is moving from virtual machine-based into container-based. In this paper, we study the energy-efficient resource allocation problem for container-based virtualization in a data center. Our goal is to minimize the energy consumption by determining 1) the number of cores allocated to a container, 2) the operating frequency of the container, and 3) the deployment of the container to server. Every container has to meet its service level agreement (SLA). We propose dynamic programming algorithms that can be used under different scenarios, depending on the affordable time complexity. The performance of the proposed algorithms is evaluated with energy consumption data collected from experiments.

Deep learning is an increasingly important technique that can solve complex problems. Due to the growth of data and model complexity, large-scale deep learning has became an important issue. Distributed deep learning is an efficient way to address these complexity issues in training a huge model. However, in a distributed environment network bandwidth becomes a performance bottleneck for deep learning. We propose various optimizations in reducing network usage by scheduling network request events properly, so as to reduce the total training time. These scheduling optimization only requires software innovation and without the need to upgrade physical network bandwidth, thus is economically competitive. The experiments indicate that our scheduler achieves up to 25 % speedup over traditional schedulers.

Recent advances in System-on-Chip architectures have made the use of deep learning suitable for a number of applications on mobile devices. Unfortunately, due to the computational cost of neural network training, it is often limited to inference task, e.g., prediction, on mobile devices. In this paper, we propose a deep learning framework that enables both deep learning training and inference tasks on mobile devices. While being able to accommodate with the heterogeneity of computing devices technology on mobile devices, it also uses OpenCL to efficiently leverage modern SoC capabilities, e.g., multi-core CPU, integrated GPU and shared memory architecture, and accelerate deep learning computation. In addition, our system encodes the arithmetic operations of deep networks down to 8-bit fixed-point on mobile devices. As a proof of concept, we trained three well-known neural networks on mobile devices and exhibited a significant performance gain, energy consumption reduction, and memory saving.

Summary Reachability query with label constraint in an attribute graph is one of the most fundamental and important operations in semantic network analysis. However, ever‐growing graph size has resulted in intractable reachability problems on single machines. This work aims to devise efficient solutions for the reachability with label constraint problem in an attribute graph in a distributed environment. We focus on two issues in distributed processing—data localityandworkload balancing—since data locality reduces communication overhead and workload balancing improves the efficiency of cluster use. We propose three novel techniques to address the two issues: (1) a partition replication method that improves data locality while conserving community property, (2) a workload‐prediction method that accurately predicts machine workloads for a given quer, and (3) a workload balancing method that uses these predictions to shift partial workloads among machines to produce a balanced workload. Experimental results suggest that these techniques significantly improve performance and reduce total execution time by 40%.

This paper proposes a scalable and efficient cache update technique to improve the performance of in-memory cluster computing in Spark, a popular open-source system for big data computing. Although the memory cache speeds up data processing in Spark, its data immutability constraint requires reloading the whole RDD when part of its data is updated. Such constraint makes the RDD update inefficient. To address this problem, we divide an RDD into partitions, and propose the partial-update RDD (PRDD) method to enable users to replace individual partition(s) of an RDD. We devise two solutions to the RDD partition problem - a dynamic programming algorithm and a nonlinear programming method. Experiment results suggest that, PRDD achieves 4.32× speedup when compared with the original RDD in Spark. We apply PRDD to a billing system for Chunghwa Telecomm, the largest telecommunication company in Taiwan. Our result shows that the PRDD based billing system outperforms the original billing system in CHT by a factor of 24× in throughput. We also evaluate PRDD using the TPC-H benchmark, which also yields promising result.

Auto-scaling is a technique that allocates resources according to dynamic workload. This paper focuses on auto-scaling with heterogeneous container configurations. The goal is to minimize the cost of container adjustments, and to reduce the resource insufficiency penalty, while maintaining high resource utilization. It is extremely difficult to achieve the minimal cost without knowing the future workloads in advance. Thus, we first propose an optimal dynamic programming algorithm that can scale optimally when given the future workload. This optimal solution is used as the baseline to evaluate other algorithms that do not have the future workload information. Then, we propose two greedy algorithms that do not need workload information in advance, and a heuristic algorithm that first predicts the workload of the next time step using Gradient Boosting Regression, then makes scaling decisions using the optimal dynamic programming algorithm. We evaluate these four algorithms with two realistic workload traces. The experiments show that when the cost to start new servers is much higher than resource insufficiency penalty, our short-term prediction approach will only increase the total cost by only 9.6%, and decrease the utilization by only 10%, when compared with the optimal dynamic programming that knows the future workload.

As mobile devices become more capable, the need for customization of mobile services becomes increasingly important for users. Nowadays, mobile device sensors are able to collect information from users throughout the day, which gives insight into their profiles. The advent of modern System-on-Chip architectures has enabled mobile devices to tackle machine learning-oriented problems heretofore reserved to desktop computers. The recent success of deep learning makes it a method of choice for understanding the complex user patterns on mobile devices. Unfortunately, training a deep neural network is often considered as too computationally intensive on mobile devices. To address this issue, we consider transfer learning, a technique that aims to take advantage of deep learning features that have been previously learned to improve the learning performance of another neural network. In this paper, we propose a deep learning framework TransferCL, that supports transfer learning on mobile devices. Our approach relies on the collaboration of the multicore CPU and the integrated GPU to accelerate deep learning computation on mobile devices. We consider three major issues - performance/portability tradeoff, power efficiency, and memory management, propose our approaches, and conduct experiments to evaluate them.

A recent trend in computing platforms is moving from homogeneous multi-core architectures toward heterogeneous and asymmetric multi-core. Therefore, the design of new schedulers for asymmetric multi-core platform has become an important issue. However, most of the existing schedulers focus on how to distinguish workloads suitable for performance "big" cores from those for power-efficient "little" cores, without considering how to distribute jobs to asymmetric cores running at adjustable frequency. In this paper, we propose an energy-efficient scheduler for throughput guaranteed jobs running on asymmetric multi-core platforms. The proposed scheduler not only determines the frequency of cores and job-to-core assignment in order to reduce energy consumption, but also schedules the jobs so that the throughput of all jobs are guaranteed. The simulation results indicate that the proposed scheduler consumes 40% less energy than the existing Global Task Scheduler with DVFS enabled.

Full system emulators provide virtual platforms for several important applications, such as kernel and system software development, co-verification with cycle accurate CPU simulators, or application development for hardware still in development. Full system emulators usually use dynamic binary translation to obtain reasonable performance. This paper focuses on optimizing the performance of full system emulators. First, we optimize performance by enabling classic control transfer optimizations of dynamic binary translation in full system emulation, such as indirect branch target caching and block chaining. Second, we improve the performance of memory virtualization of cross-ISA virtual machines by improving the efficiency of the software translation lookaside buffer (software TLB). We implement our optimizations on QEMU, an industrial-strength full system emulator, along with the Android emulator. Experimental results show that our optimizations achieve an average speedup of 1.98X for ARM-to-X86-64 QEMU running SPEC CINT2006 benchmarks with train inputs. Our optimizations also achieve an average speedup of 1.44X and 1.40X for IA32-to-X86-64 QEMU and AArch64-to-X86-64 QEMU on SPEC CINT2006. We use a set of real applications downloaded from Google Play as benchmarks for the Android emulator. Experimental results show that our optimizations achieve an average speedup of 1.43X for the Android emulator running these applications.

To reduce container management costs, ocean carrier companies rent containers from container leasing companies. Two carrier companies can exchange their empty containers between each other at various ports to eliminate the transportation cost of empty containers. To minimize costs, a container leasing company has to find the maximum number of pairs of carrier companies that can exchange containers. We formulate this problem as maximum matching in a large general graph, and propose a distributed matching algorithm to solve this problem. We also propose several optimization techniques to improve the efficiency of our algorithm.

Many enterprises or institutes are building private clouds within their own data centers. Data centers may have different batches of physical machines due to annual upgrades, but the number of machines is fixed most of the time. Consequently it is crucial to schedule jobs with different resource requirements and characteristics to meet different job timing constraints, in such heterogeneous yet most of the time static environments. This paper describes a cloud resource management framework that dynamically allocates and reallocates computation resources for jobs that have different requirements, including deadline and priority. This framework makes decisions according to specified policies, and the framework provides four default policies for system administrators to choose to fit their specific needs. The framework is designed to be component-pluggable. The components of the framework can be hot-swapped, i.e., Replaced without shutting down the services. In addition, the framework can work as an individual cloud computing system, or as an extension of an existing cloud system. Our experiment results demonstrate that our system is capable of dynamically adjusting the resource allocation plan according to run-time statistics collected. The system also tolerates hardware failures, and will dynamically reallocate workers to compensate for the downtime in order to finish the jobs before deadline. Our experiments also suggest a trade-off between priority and deadline.

In this paper we describe a scheduling framework that allocates resources to both batch jobs and interactive jobs simultaneously in a private cloud with a static amount of resources. In the system, every job has an individual service level agreement (SLA), and violating the SLA incurs penalty. We propose a model to formally quantify the SLA violation penalty of both batch and interactive jobs. The analysis on the interactive jobs focuses on queuing analysis and response time. The analysis on batch jobs focuses on the non-preemptive job scheduling for multiple processing units. Based on this model we also propose algorithms to estimate the penalty for both batch jobs and interactive jobs, and algorithms that reduce the total SLA violation penalty. Our experiment results suggest that our system effectively reduces the total penalty by allocating the right amount of resources to heterogeneous jobs in a private cloud system.

HQEMU is a multi-threaded and re-targetable dynamic binary translator built on top of QEMU and LLVM. It combines the fast and reliable code translation in the TCG (Tiny Code Generator) of QEMU and the rich optimizations in LLVM to achieve high performance for both short running and long running applications. One weakness of HQEMU lies in the lack of efficient SIMD instruction translation. This work investigates on how to remedy that. Two approaches have been designed and tested. One simple approach is to modify the help function to emit LLVM vector IR, and a more complete approach is to add a newly introduced vector IR in the TCG phase. Although both approaches can exploit the SIMD instructions of the host machine, the second and more complete approach has superior runtime as well as compile time advantages.

Energy-efficient task scheduling is a fundamental issue in many application domains, such as energy conservation for mobile devices and the operation of green computing data centers. Modern processors support dynamic voltage and frequency scaling (DVFS) on a per-core basis, i.e., the CPU can adjust the voltage or frequency of each core. As a result, the core in a processor may have different computing power and energy consumption. To conserve energy in multi-core platforms, we propose task scheduling algorithms that leverage per-core DVFS and achieve a balance between performance and energy consumption. We consider two task execution modes: the batch mode, which runs jobs in batches, and the online mode in which jobs with different time constraints, arrival times, and computation workloads co-exist in the system. For tasks executed in the batch mode, we propose an algorithm that finds the optimal scheduling policy, and for the online mode, we present a heuristic algorithm that determines the execution order and processing speed of tasks in an online fashion. The heuristic ensures that the total cost is minimal for every time interval during a task's execution.

Cross-ISA system-mode emulation has many important applications. For example, Cross-ISA system-mode emulation helps computer architects and OS developers trace and debug kernel execution-flow efficiently by emulating a slower platform (such as ARM) on a more powerful plat-form (such as an x86 machine). Cross-ISA system-mode emulation also enables workload consolidation in data centers with platforms of different instruction-set architectures (ISAs). However, system-mode emulation is much slower. One major overhead in system-mode emulation is the multi-level memory address translation that maps guest virtual address to host physical address. Shadow page tables (SPT) have been used to reduce such overheads, but primarily for same-ISA virtualization. In this paper we propose a novel approach called embedded shadow page tables (ESPT). EPST embeds a shadow page table into the address space of a cross-ISA dynamic binary translation (DBT) and uses hardware memory management unit in the CPU to translate memory addresses, instead of software translation in a current DBT emulator like QEMU. We also use the larger address space on modern 64-bit CPUs to accommodate our DBT emulator so that it will not interfere with the guest operating system. We incorporate our new scheme into QEMU, a popular, retargetable cross-ISA system emulator. SPEC CINT2006 benchmark results indicate that our technique achieves an average speedup of 1.51 times in system mode when emulating ARM on x86, and a 1.59 times speedup for emulating IA32 on x86_64.

Dynamic Binary Instrumentation (DBI) is a core technology for building debugging and profiling tools for application executables. Most state-of-the-art DBI systems have focused on the same instruction set architecture (ISA) where the guest binary and the host binary have the same ISA. It is uncommon to have a cross-ISA DBI system, such as a system that instruments ARM executables to run on x86 machines. We believe cross-ISA DBI systems are increasingly more important, since ARM executables could be more productively analyzed on x86 based machines such as commonly available PCs and servers. In this paper, we present DBILL, a cross-ISA and re- targetable dynamic binary instrumentation framework that builds on both QEMU and LLVM. The DBILL framework enables LLVM-based static instrumentation tools to become DBI ready, and deployable to different target architectures. Using address sanitizer and memory sanitizer as implementation examples, we show DBILL is an efficient, versatile and easy to use cross-ISA retargetable DBI framework.

Dynamic binary translation (DBT) is a core technologyto many important applications such as system virtualization, dynamic binary instrumentation, and security. However, there are several factors that often impede its performance: 1) emulation overhead before translation; 2) translation and optimization overhead; and 3) translated code quality. The issues also include its retargetabilitythat supports guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs-an important feature to system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, and use a multithreaded approach to implement DBT. By running the translator and the dynamic binary optimizer on different cores with different threads, it could off-load the overhead incurred by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and Low-Level Virtual Machine (LLVM) as our building blocks, we demonstrated in a multithreaded DBT prototype, called Hybrid-QEMU (HQEMU), that it could improve QEMU performance by a factor of 2.6x and 4.1x on the SPEC CPU2006 integer and floating point benchmarks, respectively, for dynamic translation of x86 code to run on x86-64 platforms. For ARM codes to x86-64 platforms, HQEMU can gain a factor of 2.5x speedup over QEMU for the SPEC CPU2006 integer benchmarks. We also address the performance scalability issue of multithreaded applications across ISAs. We identify two major impediments to performance scalability in QEMU: 1) coarse-grained locks used to protect shared data structures, and 2) inefficient emulation of atomic instructions across ISAs. We proposed two techniques to mitigate those problems: 1) using indirect branch translation caching (IBTC) to avoid frequent accesses to locks, and 2) using lightweight memory transactions to emulate atomic instructions across ISAs. Our experimental results show that for multithread applications, HQEMU achieves 25X speedups over QEMU for the PARSEC benchmarks.

We present a data replication framework for distributed graph processing. First we partition a graph and store each partition in a machine. Then we replicate all partitions and assign replicas to machines, where each machine can store only a limited number of replicas. The goal is to replicate the partitions so that each partition has at least a certain number of replicated copies, and the cost is minimized. The cost is defined as the data traffic needed to run general graph processing algorithms. The cost metric is the overall transmission cost of all machines, and the maximum transmission cost of a single machine. We propose an optimal algorithm based on linear programming to solve the problem of minimizing the overall transmission cost. We also propose an optimal algorithm to solve a special problem of minimizing the maximum transmission cost of a node.

We introduce Kylin, an efficient and scalable graph data processing system. Kylin is based on bulk synchronization processing(BSP) model to process graph data. Although there have been some BSP-based graph processing systems, Kylin is different from these systems in two-fold. First, Kylin cooperates with HBase to achieve scalable data manipulation. Second, We propose three techniques to optimize the performance of Kylin. The proposed techniques are pull messaging, lazy vertex loading and vertex-weighted partitioning. We demonstrate Kylin outperforms other BSP-based systems, i.e. Hama and Giraph, in the experiments.

Program executions are usually repetitive, hence, we can optimize program executions if we are able to identify the program's repetition pattern. If we can accurately classify program execution intervals into phases, and use such information to accurately predict the next phase at runtime, we will be able to apply suitable optimization on the subsequent intervals. Such runtime optimization opportunity not only exists in single-threaded programs but also in multithreaded programs In this paper, we propose a framework that collects code signature of each interval from individual threads of a multi-threaded parallel program, and classify them into phases at runtime. We then use the classification results to predict the next phase in an on-line fashion. In order to efficiently classify execution intervals on-line, we only keep a fixed number of representative data in a shared table for classification purpose. The classification is very efficient and uses less than 3K bytes of memory. We also propose a confidence table to improve the prediction rate. Our experiment results with the Spec OMP2001 and the PARSEC benchmark suites on an Intel Xeon multi-core show that our system can classify intervals into phases with high homogeneity, can predict the next phase with 65% accuracy without using confidence table and with 80% accuracy when confidence table is used.

Most dynamic binary translators (DBT) and optimizers (DBO) target binary traces, i.e. frequently executed paths, as code regions to be translated and optimized. Code region formation is the most important first step in all DBTs and DBOs. The quality of the dynamically formed code regions determines the extent and the types of optimization opportunities that can be exposed to DBTs and DBOs, and thus, determines the ultimate quality of the final optimized code. The Next-Executing-Tail (NET) trace formation method used in HP Dynamo is an early example of such techniques. Many existing trace formation schemes are variants of NET. They work very well for most binary traces, but they also suffer a major problem: the formed traces may contain a large number of early exits that could be branched out during the execution. If this happens frequently, the program execution will spend more time in the slow binary interpreter or in the unoptimized code regions than in the optimized traces in code cache. The benefit of the trace optimization is thus lost. Traces/regions with frequently taken early-exits are called delinquent traces/regions. Our empirical study shows that at least 8 of the 12 SPEC CPU2006 integer benchmarks have delinquent traces.

With the ever increasing size of data sets, traditional parallel relational database solution can be prohibitively expensive and may suffer limited scalability. To perform large-scale data processing in a cost-effective manner, several NoSQL data processing systems have been proposed. In this paper, we devise a new, distributed B-tree column indexing scheme for HBase, which can support indexing for non-row-key columns, as well as parallel B-tree search in large data table. Our experiment results demonstrate both performance and scalability advantage of our indexing scheme on point queries, range queries, and aggregation operations, compared with HBase.

We present an efficient distributed graph database architecture for large scale social computing. The architecture consists of a distributed graph data processing system and a distributed graph data storage system. We leverage the advantages of both systems to achieve efficient social computing. We conduct extensive experiments to demonstrate the performance of our system. We employ four real-world, large scale social networks - YouTube, Flicker, LiveJournal and Orkut as test data. We also implement several representative social applications and graph algorithms to examine the performance of our system. We employ two main optimization techniques in our system ¡Vindexing and graph partitioning. Experimental results indicate that our system outperforms GoldenOrb, an implementation Pregel model from Google.

Web applications play a major role in various enterprise and cloud services. With the popularity of social networks and with the speed at which information can be disseminate around the globe, online systems need to face ever growing, unpredictable peak load events. Auto-scaling technique provides on-demand resources according to workload in cloud computing system. However, most of the existing solutions are subject to some of the following constraints: (1) replying on user-provided scaling metrics and threshold values, (2) employing the simple Majority Vote scaling algorithm, which is ineffective for scaling Web applications, and (3) lack of capability for predicting workload changes. In this work, we develop an auto-scaling system, WebScale, which is not subject to the aforementioned constraints, for managing resources for Web applications in data centers. We also compare the efficiency of different scaling algorithms for Web applications, and devise a new method for analyzing the trend of workload changes. The experiment results demonstrate that WebScale can keep the response time of Web applications low even when facing sudden load changing.

Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. On the dynamic binary translator itself, the issues also include its retargetability to support guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs, an important feature for system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, using multithreaded approach to implement DBT. By running the translators and the dynamic binary optimizers on different threads on different cores, it could off-load the overhead caused by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as the support of its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU, that it could improve QEMU performance by a factor of 2.4X and 4X on the SPEC 2006 integer and floating point benchmarks for x86 to x86-64 emulations, respectively, i.e. it is only 2.5X and 2.1X slower than native execution of the same benchmarks on x86-64, as opposed to 6X and 8.4X slowdown on QEMU. For ARM to x86-64 emulation, HQEMU could gain a factor of 2.4X speedup over QEMU for the SPEC 2006 integer benchmarks.

An energy conservation strategy must address two issues - placement of virtual machine images and workload characteristics of virtual machines. For performance reason most cloud systems copy a prototype image into the local disk of a physical machine before starting a virtual machine. If the physical machine that stores the image of a virtual machine is off-line, then we cannot run this virtual machine. The workload characteristics of virtual machines determine whether it is data-intensive or CPU-intensive. We assume that the system has a distributed file system therefore a physical machine can run any virtual machine even if it does not have the image. However, we observe that the performance of a data-intensive virtual machine running on a physical machine without its image could result in 60% performance loss compared with running the same virtual machine on a physical machine that has the virtual machine image. On the other hand, the performance of a CPU-intensive virtual machine is almost independent of whether the physical machine has the image or not. As a result, an energy conservation algorithm must consider the workload characteristic of a virtual machine when finding a physical machine to run it, especially for data-intensive virtual machines. This paper proposes a workload characteristics-aware virtual machine consolidation algorithms. We propose an approximation algorithm and two dynamic programmings to consolidate virtual machines and reduce the number of physical machines. We conduct experiments and compare the numbers of physical machines used by our approximation algorithm with the optimal number of physical machines found by our dynamic programming. The experiment results indicate that our approximation algorithm finds good solutions much faster than the dynamic programming.

During recent years cloud service providers have successfully provided reliable and flexible resources to cloud users. For example Amazon Elastic Block Store (Amazon EBS) and Simple Storage Service (Amazon S3) provides users storage in the cloud. Despite the tremendous efforts cloud service providers have devoted to the availability of their services, the interruption is still inevitable. Therefore just as an Internet service provider will not count on a single network provider, a cloud user should not depend on a single cloud service provider either. However, cloud service providers provide different levels of services. A more costly service is usually more reliable. As a result it is an important and challenging problem to choose among a set of service providers to fit one's need, which could be budget, failure probability, or the amount of data that can survive failure. The goal of this paper is to select cloud service providers in order to maximize the benefits with a given budget. The contributions of this paper include a mathematical formulation of the cloud service provider selection problem in which both the object functions and cost measurements are clearly defined, algorithms that selects among cloud storage providers to maximize the data survival probability or the amount of surviving data, subject to a fixed budget, and a series of experiments that demonstrateDuring recent years cloud service providers have successfully provided reliable and flexible resources to cloud users. For example Amazon Elastic Block Store (Amazon EBS) and Simple Storage Service (Amazon S3) provides users storage in the cloud. Despite the tremendous efforts cloud service providers have devoted to the availability of their services, the interruption is still inevitable. Therefore just as an Internet service provider will not count on a single network provider, a cloud user should not depend on a single cloud service provider either. However, cloud service providers provide different levels of services. A more costly service is usually more reliable. As a result it is an important and challenging problem to choose among a set of service providers to fit one's need, which could be budget, failure probability, or the amount of data that can survive failure. The goal of this paper is to select cloud service providers in order to maximize the benefits with a given budget. The contributions of this paper include a mathematical formulation of the cloud service provider selection problem in which both the object functions and cost measurements are clearly defined, algorithms that selects among cloud storage providers to maximize the data survival probability or the amount of surviving data, subject to a fixed budget, and a series of experiments that demonstrate that the proposed algorithms are efficient enough to find optimal solutions in reasonable amount of time, using price and fail probability taken from real cloud providers. that the proposed algorithms are efficient enough to find optimal solutions in reasonable amount of time, using price and fail probability taken from real cloud providers.

ZigBee, a unique communication standard designed for low-rate wireless personal area networks, has extremely low complexity, cost, and power consumption for wireless connectivity in inexpensive, portable, and mobile devices. Among the well-known ZigBee topologies, ZigBee cluster-tree is especially suitable for low-power and low-cost wireless sensor networks because it supports power saving operations and light-weight routing. In a constructed wireless sensor network, the information about some area of interest may require further investigation such that more traffic will be generated. However, the restricted routing of a ZigBee cluster-tree network may not be able to provide sufficient bandwidth for the increased traffic load, so the additional information may not be delivered successfully. In this paper, we present an adoptive-parent-based framework for a ZigBee cluster-tree network to increase bandwidth utilization without generating any extra message exchange. To optimize the throughput in the framework, we model the process as a vertex-constraint maximum flow problem, and develop a distributed algorithm that is fully compatible with the ZigBee standard. The optimality and convergence property of the algorithm are proved theoretically. Finally, the results of simulation experiments demonstrate the significant performance improvement achieved by the proposed framework and algorithm over existing approaches.

MapReduce is a widely used data-parallel programming model for large-scale data analysis. The framework is shown to be scalable to thousand of computing nodes and reliable on commodity clusters. However, research has shown that there is room for performance improvement of the MapReduce framework. One of the main performance bottlenecks is caused by the all-to-all communication between mappers and reducers, which may saturate the top-of-rack switch and inflate job execution time. Reducing cross-rack communication will improve job performance. In current MapReduce implementation, the task assignment is based on the pull-model, in which cross-rack traffic is difficult to control. In contrast, the MapReduce framework allows more flexibility in assigning reducers to the computing nodes. In this paper, we investigate the reducer placement problem (RPP), which considers the placement of reducers to minimize cross-rack traffic. We devise two optimal algorithms to solve RPP and implement the algorithms in the Hadoop system. We also propose an analytical solution for this problem. Our experiment results with a set of MapReduce applications show that our optimization achieves 9% to 32%performance improvement compared with the unoptimized Hadoop.

Power consumption is one of the most critical problems in data centers. One effective way to reduce power consumption is to consolidate the hosting workloads and shut down physical machines which become idle after consolidation. Server consolidation is a NP-hard problem. In this paper, a new algorithms Dynamic Round-Robin (DRR), is proposed for energy-aware virtual machine scheduling and consolidation. We compare this strategy with the GREEDY, ROUNDROBIN and POWERSAVE scheduling strategies implemented in the Eucalyptus Cloud system. Our experiment results show that the Dynamic Round-Robin algorithm reduce a significant amount of power consumption compared with the three strategies in Eucalyptus.

A Cloud computing system provides infrastructure layer services to users by managing virtualized infrastructure resources. The infrastructure resources include CPU, hyper visor, storage, and networking. Each category of infrastructure resources is a subsystem in a cloud computing system. The cloud computing system coordinates infrastructure subsystems to provide services to users. Most current cloud computing systems lacks pluggability in their infrastructure subsystems and decision algorithms, which restricts the development of infrastructure subsystems and decision algorithms in cloud computing system. A cloud computing system should have the flexibility to switch from one infrastructure subsystem to another, and one decision algorithm to another with ease. This paper describes Roystonea, a hierarchical distributed cloud computing system with plug gable component architecture. The component pluggability ability gives administrators the flexibility to use the most appropriate subsystem as they wish. The component pluggability of Roystonea is based on a specifically designed interfaces among Roystonea controlling system and infrastructure subsystems components. The component pluggability also encourages the development of infrastructure subsystems in cloud computing. Roystonea provides a test bed for designing decision algorithms used in cloud computing system. The decision algorithms are totally isolated from other components in Roystonea architecture, so the designers of the decision algorithms can focus on algorithm design without worrying about how his algorithm will interact with other Roystonea components. We believed that component pluggability will be one of the most important issues in the research of cloud computing system.

As the size of data set in cloud increases rapidly, how to process large amount of data efficiently has become a critical issue. MapReduce provides a framework for large data processing and is shown to be scalable and fault-tolerant on commondity machines. However, it has higher learning curve than SQL-like language and the codes are hard to maintain and reuse. On the other hand, traditional SQL-based data processing is familiar to user but is limited in scalability. In this paper, we propose a hybrid approach to fill the gap between SQL-based and MapReduce data processing. We develop a data management system for cloud, named SQLMR. SQLMR complies SQL-like queries to a sequence of MapReduce jobs. Existing SQL-based applications are compatible seamlessly with SQLMR and users can manage Tera to PataByte scale of data with SQL-like queries instead of writing MapReduce codes. We also devise a number of optimization techniques to improve the performance of SQLMR. The experiment results demonstrate both performance and scalability advantage of SQLMR compared to MySQL and two NoSQL data processing systems, Hive and HadoopDB.

This paper presents an LLVM+QEMU (LnQ)framework for building high performance and retargetable binary translators with existing compiler modules. Dynamic binary translation is a just-in-time (JIT) compilation from binary code of guest ISA to binary code of host ISA. The quality of translated code is critical to the performance of a dynamic binary translator, which translates code between different IS As, so the translated code is often carefully hand-optimized. As a result, it takes tremendous implementation efforts for software engineers to port an existing dynamic binary translator to anew host ISA. The goal of LnQ framework is to enable the process of building high performance and retarget able dynamic binary translators with existing optimizers and code generation back ends. LnQ framework consists of a translation module and an emulation engine. We design the translation module based on LLVM compiler infrastructure, and use QEMU as our emulation engine. We implement an x86-to-x86 64 dynamic binary translator with our LnQ framework to show that the framework is retarget able, and conduct experiments on SPECCPU2006 benchmarks to show that the resulting binary translator has good performance. The experiment results indicate that the x86-to-x86 64 LnQ translator achieves an average speedup of 1.62X in integer benchmarks, and 3.02X in floating point benchmarks than QEMU.

Server consolidation presents numerous opportunities for sharing memory between virtual machines. To intelligently share RAM across VMs, modern hypervisors use a technique called content-based page sharing (CBPS), in which duplicate copies of a page resident on a host are detected and a single copy of the page is shared, thereby reducing the memory footprint of resident VMs. One widely used implementation of content-based page sharing is kernel same page merging (KSM). In this paper, we conduct empirical study on the effectiveness of KSM on various kinds of workload through extensive experiments. We classify memory sharing into two classes: static sharing for memory sharing after launching the VM and before executing the application, and dynamic sharing for memory sharing during the execution of the application. We found that KSM achieves very effective static memory sharing for various workload, evidenced by its ability to consolidate 50 Windows VMs on one physical machine. KSM achieves most significant memory saving for mixed CPU and I/O workload. For CPU-bound applications, the effect of KSM on dynamic memory sharing is not as significant and it also causes higher runtime overhead. For I/O-bound applications, dynamic memory sharing reduces memory use by around 50% with very little runtime overhead. Furthermore, KSM has more significant effect on Windows based VMs than on Linux based VMs.

Compiler techniques for program optimizations have been well studied for single-thread programs. With the advance of multi-core architectures, compiler optimizations for multi-threaded parallel programs have started to draw research attention in recent years. Optimizations for multi-threaded parallel programs on multi-core architectures are much more difficult because of the complicated interaction and resource competition between threads. Therefore, identifying the appropriate code segments for performing optimization becomes one of the most challenging issues. In this work, we propose a novel technique to identify the code segments that exhibit unstable performance behavior% because of resource contention between threads, and show that by applying appropriate optimizations to such code segments, the performance of the parallel program can be improved. Our technique is based on a simple and efficient sampling method that analyzes variations in the performance variance of basic blocks to classify basic blocks into "stable" and "unstable" ones. ``Stable'' basic blocks have low average coefficient of variation(CoV) while "unstable" ones have CoV higher than a threshold value. Such analysis results can be used to determine the "unstable" code segments that may benefit from runtime optimizations. Our experiment results on the SPEC OMP2001 benchmark suite demonstrate that the proposed method is effective in finding "unstable" code segments.

SUMMARY In this paper, we consider the QoS‐aware replica placement problem. Although there has been much research on the problem, most approaches focus on the average system performance and ignore the quality assurance issue. However, quality assurance is crucial, especially in heterogeneous environments. To fill this research gap, we proposed four heuristic algorithms to determine the locations of replicas in order to satisfy the quality requirements imposed by data requests. Three of the algorithms are greedy heuristics called Greedy‐Cover, Cover‐Partition and Multi‐Source. The fourth algorithm is based on the Simulated Annealing technique. Our experiment results indicated that Greedy‐Cover and the Simulated Annealing‐based algorithms can find effective solutions efficiently. Copyright © 2011 John Wiley & Sons, Ltd.

With the emergence of large-scale storage systems that separate metadata management from file read/write operations, and with requests targetting metadata account for over 80% of the total number of I/O requests, metadata management has become an interesting research problem on its own. When designing a metadata server cluster, the partitioning of the metadata among the servers is of critical importance for maintaining efficient metadata operations and balanced load distribution across the cluster. We propose a dynamic programming method combined with binary search to solve the partitioning problem. With theoretical analysis and extensive experiments, we show that our algorithm finds the partitioning that minimizes load imbalance among servers and maximize efficiency of metadata operations.

This paper introduces techniques in scheduling jobs on a master/workers platform where the bandwidth is shared by all workers. The goal is to minimize the total makespan. The jobs are independent and each job requires a fixed amount of bandwidth to download input data before execution. The master can communicate with multiple workers simultaneously, provided that the bandwidth used by the master and the workers do not exceed their bandwidth limits. We proposed two models for this limited-bandwidth problem. If the data transfer cannot be interrupted, then we prove that the scheduling problem is NP-complete. Nevertheless we propose heuristic algorithms and experimentally test their performance. If the data transfer can be interrupted, we propose an algorithm that produces optimal makespan. The algorithm is based on a binary search on the completion time, and an efficient feasibility verification process for a given completion time.

P2P network is the one of the most important application models in Internet. Numerous structured and unstructured P2P models have been proposed in the last ten years, and both models do have distinctive advantages and disadvantages. We proposed a hybrid model to strike a balance between these two models using peer grouping. Since the size of peer groups is essential to performance, we analyze the effect of group size on the maintenance cost, which is measured in terms of the number of maintenance messages. Experimental results suggest that the group size obtained from our theoretical analysis is very close to the actual best group size obtained from simulation, and the hybrid model uses less messages in maintaining a P2P network than Chord does.

We study the replication transition problem (RTP) in the Grid systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to data access pattern, and a good strategy can improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another in order to cope with the dynamic data access pattern. This paper focuses on the RTP problem for Grid systems in four communication models that have different communication capabilities, i.e., whether message forwarding is allowed and whether network capacity is uniform among different links. We show that there exists a polynomial time algorithm that provides optimal solution for the RTP problem when forwarding is not allowed and the communication links are uniform. We also propose heuristic algorithms for solving variants of the RTP problem and conduct experiments to evaluate their performances. The experimental results indicate that our proposed heuristics are very effective.

Data replications is a typical strategy for improving access performance and data availability in data grid systems. Current works on data replication in grid systems focus on the infrastructure for data replication and the mechanism of replicas creation and deletion.The important problem of choosing suitable locations for placing replicas in data grids has not been fully studied. This paper addresses replica placement problem in data grids when given a sequence of priority lists that specify the forwarding policies for data requests. We propose the concept of priority list to address two issues. First, a user may have limited authority in accessing the resources, and thus his/her data requests should be prohibited from accessing some of the sites. Second, a static policy may not satisfy a data request with special requirements (e.g. quality of service requirement). In this priority-list-based model we propose a placement algorithm that finds optimal locations for replicas so that the workload among the replicas is balanced. We also propose an algorithm that determines the minimum number of replicas when the maximum workload capacity of each replica is given.

We study the replication transition problem in distributed hierarchical systems. Most distributed systems replicate data to increase data access efficiency. A replication strategy dictates where the replicas are stored in respond to the data access pattern, therefore a good strategy can effectively improve data access efficiency. However, the access pattern in a distributed system is constantly changing. As a result, a good replication strategy must evolve accordingly. The replication transition problem is to seek an efficient transition from one replication strategy to another, in order to cope with the dynamic access pattern. This paper focuses on solving the replication transition problem on tree topology, which is one of the most important models in data grid systems and Web proxy systems from the literature. To the best of our knowledge, our work is the first that proposes an optimal algorithm for the replication transition problem on tree topology. The algorithm has a time complexity of O(n log Deltalog(nLambda)), where n is the number of sites, Delta is the maximum degree in the tree and Lambda is the largest communication delay in the network.

Almost every computation job requires input data in order to find the solution, and the computation cannot proceed without the required data becoming available. As a result a proper interleaving of data transfer and job execution has a significant impact on the overall efficiency. In this paper we analyze the computational complexity of the shared data job scheduling problem, with and without consideration of storage capacity constraint. We show that if there is an upper bound on the server capacity, the problem is NP-complete, even when each job depends on at most three data. On the other hand, if there is no upper bound on the server capacity, we show that there exists an efficient algorithm that gives optimal job schedule when each job depends on at most two data. We also give an efficient heuristic algorithm that gives good schedule for cases where there is no limit on the number of data a job may access.

Grid computing is an important mechanism for utilizing distributed computing resources. These resources are distributed in different geographical locations, but are organized to provide an integrated service. In order to speed up data access efficiency data grid systems replicate essential data in multiple locations, so that a user can access the data from a site in his vicinity. This paper studies replica placement in data grid systems, taking into account several important issues described below. First, the replicas should be placed in proper server locations so that the workload on each server is balanced. Second, we choose the optimal number of replicas to balance the data access efficiency, and the expensive maintenance costs for multiple copies of data. Clearly, optimizing access cost of data requests and reducing the cost of replication are two conflicting goals. Finding a good balance between them is a challenging task. We propose efficient algorithms for selecting optimal locations for placing the replicas so that the workload among these replicas is balanced. Also when given the data usage from each user site and the maximum workload allowed for each replica server, our algorithm efficiently determines the minimum number of replicas required, as well as their locations.

This paper introduces a new graph theory problem called generalized edge coloring (g.e.c). A generalized edge coloring is similar to traditional edge coloring, with the difference that a vertex can be adjacent to up to k edges that share the same color. The concept of generalized edge coloring can be used to formulate the channel assignment problem in multi-channel multi-interface wireless networks. We provide theoretical analysis for this problem. Our theoretical findings can be useful for system developers of wireless networks. We show that when k = 3, there are graphs that do not have generalized edge coloring that could achieve the minimum number of colors for every vertex. On the contrary, when k = 2 we show that if we are given one extra color, we can find a generalized edge coloring that uses the minimum number of colors for each vertex. In addition, we show that for certain classes of graphs we are able to find a generalized edge coloring that uses the minimum number of colors for every vertex without the extra color. These special classes of graphs include bipartite graph, graphs with a power of 2 maximum degree, or graphs with maximum degree no more than 4

We investigate the problem of scheduling parallel I/O operations on systems that provide data replication. The objective is to direct each compute node to access data from an I/O node where the data is duplicated, in such a way that requests for data are evenly distributed among I/O nodes. We identify a necessary and sufficient condition on whether the current data request pattern can be improved, in terms of the maximum number of data requests on any I/O node. We propose an augmenting path algorithm that examines this necessary and sufficient condition, and adjusts the current data request pattern accordingly. Using network flow technique, we show that the augmenting path algorithm finds an optimal assignment in O(nmlogn+n/sup 2/Iog/sup 3/2/n) time.

Wormhole switching has become the most widely used switching technique for multicomputers. However, the main drawback of wormhole switching is that blocked messages remain in the network, prohibiting other messages from using the occupied links and buffers. To address the deadlock problem without compromising communication latency and the incremental expansion capability that irregular networks can offer, we propose a simple topology called extended incremental triangular mesh (EITM) for switch-based networks. EITM is an extension of a previous ITM (incremental triangular mesh) topology with a more flexible structure. We also show that EITM is highly scalable, allows incremental expansion of systems, has guaranteed deadlock freedom, and can support contention-free multicast. First, we show that for an EITM, any shortest path routing method will not deadlock, therefore EITM networks are ideal for the escape paths in adaptive routing networks. Second, we show that it is possible to arrange the nodes of an EITM in a circular order so that two messages from independent parts of the circular order will not interfere with each other - this is extremely useful for implementing contention-free multicast and other collective communication operations. We also present the results on the relation between ITM/EITM, outer planar graphs and chordal graphs. We show that chordal graphs are strongly related to the freedom of deadlock for shortest path routing, and ITM in our previous paper is indeed maximum outer planar graph.

Wormhole switching has become the most widely used switching technique for multicomputers. However the main drawback of wormhole switching is that blocked messages remain in the network, prohibiting other messages from using the occupied links and buffers. To address the deadlock problem without compromising communication latency and the incremental expansion capability that irregular networks can offer we propose a simple topology called Incremental Triangular Mesh (ITM) for switch-based networks. ITM is highly scalable, allows incremental expansion of systems, has guaranteed deadlock freedom, and can support contention-free multicast. First, we show that on an ITM, shortest path routing method will not deadlock, therefore it is ideal to be used as the escape paths in adaptive routing networks. Secondly, we show that it is possible to arrange the nodes of an ITM in a circular order so that two messages from independent parts of the circular order will not interfere with each other, and we can find a circular order for every ITM that has this contention-free property. This is extremely useful for implementing contention-free multicast and other collective communication operations. Our experimental results demonstrate that ITM provides better throughput than up-down routing.

This paper presents a simple atomic model of message-passing multicomputers. Within one synchronous time step each processor can receive one atomic message, perform local computation, and send one message. When several messages are destined to the same processor, then one is transmitted and the rest are blocked. Blocked messages cannot be retrieved by their sending processors; each processor must wait for its blocked message to clear before sending more messages into the network. Depending on the traffic pattern, messages can remain blocked for arbitrarily long periods. The model is conservative when compared with existing message-passing systems. Nonetheless, we prove linear message throughput when destinations are chosen at random; this rigorously justifies an instance of folklore. Based on this result we also prove linear speedup for backtrack and branch-and-bound searches using simple randomized algorithms.

Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity complicates the design of efficient collective communication protocols. For example, it is a very hard combinatorial problem to find an optimal reduction schedule for such heterogeneous clusters. Nevertheless, we show that a simple technique called slowest-node-first (SNF) is very effective in designing efficient reduction protocols for heterogeneous clusters. First, we show that SNF is actually an approximation algorithm with competitive ratio two. In addition, we show that SNF does give the optimal reduction time when the cluster consists of two types of processors, anal the ratio of communication speed between them is at least two.

C.17D=174,>)EF=)+*F3(12-9= 24H3C#9>**D31 MD3<=1NIOMP\tQR 9U 1NIOMP\tQR [C(./\\ =VC@ 29110-43290 * 2,- VC@ 29110-43290 IU(*VS^\\a?&((G4&(11(&./b&(5?5J<3=7&(c9= 939> -40160 ?&((G4&(11( F=(<= 17 15600-39120 G4&(11(&./b&(5 oqphi Ers]r_"Ot uv40. 90-38070 k 27420-39120 ./b&(5?5J<3=7&(c9= F= 90-38070 k 27420-39120 ./b&(5?5J<3=7&(c9= F=(<= MF3M 714?V./$F3 9=561|D= /$F3 15000-35970 0-37020 5 \\ 561|D= /$F3 15000-35970 0-37020 5?5J<3=7&(c9= rs]r}12(8U^V./(_F39U561UD= &N1>&C*\t|&(1<= U561UD= *F=CF:rs$ry7H0939U (4%&(5?9>\\./4 U \tH1*eI=\\ >\\./4 U *( 28829-29700 JF=D= U 5?5J<3=7&( O[ !@ 1.

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance implementation. Our implementation was guided by the need to keep solutions simple and general. We use a technique for implicitly representing a dynamic global tree across multiple processors which substantially reduces the programming complexity as well as the performance overheads of distributed memory architectures. The contributions include methods to vectorize the computation and minimize communication time which are theoretically and experimentally justified. The code has been tested by varying the number and distribution of bodies on different configurations of the Connection Machine CM-5. The overall performance on instances with 10 million bodies is typically over 48 percent of the peak machine rate, which compares favorably with other approaches.

Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study trade-offs between computation overhead (load imbalance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies.

This paper gives an overview of the VGDS (Virtual Global Data Structure) project.The VGDS effort focuses on developing an integrated, distributed environment that allows fast prototyping of a diverse set of simulation problems in scientific and engineering domains, including regular, irregular, and adaptive problems.The framework defines three base libraries, Array, Graph, and Tree, that capture major data structures involved in scientific computation.The framework defines multiple layers of class libraries which work together to provide data-parallel representations to application developers while encapsulate parallel implementation details into lower Layers of the fmmework.The layered approach enables easy extension of the base libraries to a variety of application-specific data structures.Experimental results on a Sun UltraSparc workstation cluster is reported.

This paper describes an implementation of a platform-independent parallel C++ N-body framework that can support various scientific simulations that involve tree structures, such as astrophysics, semiconductor device simulation, molecular dynamics, plasma physics, and fluid mechanics. Within the framework the users will be able to concentrate on the computation kernels that differentiate different N-body problems, and let the framework take care of the tedious and error-prone details that care common among N-body applications. This framework was developed based on the techniques we learned from previous CM-5 C implementations, which have been rigorously justified both experimentally and mathematically. This gives us confidence that our framework will allow fast prototyping of different N-body applications, to run on different parallel platforms, and to deliver good performance as well.

This paper describes our experiences developing high-performance code for astrophysical N-body simulations. Recent N-body methods are based on an adaptive tree structure. The tree must be built and maintained across physically distributed memory; moreover, the communication requirements are irregular and adaptive. Together with the need to balance the computational work-load among processors, these issues pose interesting challenges and tradeoffs for high-performance implementation.

Article Free Access Share on An atomic model for message-passing Authors: Pangfeng Liu View Profile , William Aiello View Profile , Sandeep Bhatt View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 154–163https://doi.org/10.1145/165231.165251Published:01 August 1993Publication History 25citation266DownloadsMetricsTotal Citations25Total Downloads266Last 12 Months11Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF