Search

Along with the development of cloud computing, more and more applications are migrated into the cloud. An important feature of cloud computing is pay-as-you-go. However, most users always should pay more than their actual usage due to the one-hour billing cycle. In addition, most cloud service providers provide a certain discount for long-term users, but short-term users with small computing demands cannot enjoy this discount. To reduce the cost of cloud users, we introduce a new role, which is cloud broker. A cloud broker is an intermediary agent between cloud providers and cloud users. It rents a number of reserved VMs from cloud providers with a good price and offers them to users on an on-demand basis at a cheaper price than that provided by cloud providers. Besides, the cloud broker adopts a shorter billing cycle compared with cloud providers. By doing this, the cloud broker can reduce a great amount of cost for user. In addition to reduce the user cost, the cloud broker also could earn the difference in prices between on-demand and reserved VMs. In this paper, we focus on how to configure a cloud broker and how to price its VMs such that its profit can be maximized on the premise of saving costs for users. Profit of a cloud broker is affected by many factors such as the user demands, the purchase price and the sales price of VMs, the scale of the cloud broker, etc.. Moreover, these factors are affected mutually, which makes the analysis on profit more complicated. In this paper, we first give a synthetically analysis on all the affecting factors, and define an optimal multiserver configuration and VM pricing problem which is modeled as a profit maximization problem. Second, combining the partial derivative and bisection search method, we propose a heuristic method to solve the optimization problem. The near-optimal solutions can be used to guide the configuration and VM pricing of the cloud broker. Moreover, a series of comparisons are given which show that a cloud broker can save a considerable cost for users. [ABSTRACT FROM AUTHOR]

On multi-core processors, applications are run sharing the cache. This paper presents optimization theory to co-locate applications to minimize cache interference and maximize performance. The theory precisely specifies MRC-based composition, optimization, and correctness conditions. The paper also presents a new technique called footprint symbiosis to obtain the best shared cache performance under fair CPU allocation as well as a new sampling technique which reduces the cost of locality analysis. When sampling and optimization are combined, the paper shows that it takes less than 0.1 second analysis per program to obtain a co-run that is within 1.5 percent of the best possible performance. In an exhaustive evaluation with 12,870 tests, the best prior work improves co-run performance by 56 percent on average. The new optimization improves it by another 29 percent. Without single co-run test, footprint symbiosis is able to choose co-run choices that are just 8 percent slower than the best co-run solutions found with exhaustive testing. [ABSTRACT FROM PUBLISHER]

Efficiently analyzing geo-distributed datasets is emerging as a major demand in a cloud-edge system. Since the datasets are often generated in closer proximity to end users, traditional works mainly focus on offloading proper tasks from those hotspot edges to the datacenter to decrease the overall completion time of submitted jobs in a one-shot manner. However, optimizing the completion time of current job alone is insufficient in a long-term scope since some datasets would be used multiple times. Instead, optimizing the data distribution is much more efficient and could directly benefit forthcoming jobs, although it may postpone the execution of current one. Unfortunately, due to the throwaway feature of data fetcher, existing data analytics systems fail to re-distribute corresponding data out of hotspot edges after the execution of data analytics. In order to minimize the overall completion time for a sequence of jobs as well as to guarantee the performance of current one, we propose to re-distribute the data along with task offloading, and formulate corresponding $\varepsilon$ ɛ -bounded data-driven task scheduling problem over wide area network under the consideration of edge heterogeneity. We design an online schema $run$ r u n Data, which offloads proper tasks and related data via piggybacking to the datacenter based on delicately calculated probabilities. Through rigorous theoretical analysis, $run$ r u n Data is proved concentrated on its optimum with high probability. We implement $run$ r u n Data based on Spark and HDFS. Both testbed results and trace-driven simulations show that $run$ r u n Data re-distributes proper data via piggybacking and achieves up to 37 percent reduction on average response time compared with state-of-the-art schemas. [ABSTRACT FROM AUTHOR]

Mobile micro-clouds are promising for enabling performance-critical cloud applications. However, one challenge therein is the dynamics at the network edge. In this paper, we study how to place service instances to cope with these dynamics, where multiple users and service instances coexist in the system. Our goal is to find the optimal placement (configuration) of instances to minimize the average cost over time, leveraging the ability of predicting future cost parameters with known accuracy. We first propose an offline algorithm that solves for the optimal configuration in a specific look-ahead time-window. Then, we propose an online approximation algorithm with polynomial time-complexity to find the placement in real-time whenever an instance arrives. We analytically show that the online algorithm is $O(1)$ -competitive for a broad family of cost functions. Afterwards, the impact of prediction errors is considered and a method for finding the optimal look-ahead window size is proposed, which minimizes an upper bound of the average actual cost. The effectiveness of the proposed approach is evaluated by simulations with both synthetic and real-world (San Francisco taxi) user-mobility traces. The theoretical methodology used in this paper can potentially be applied to a larger class of dynamic resource allocation problems. [ABSTRACT FROM PUBLISHER]

The multi-valued evaluations of quality of service (QoS), the complicated constraints between cloud services (CSs) and the collaborative resource assignments add many difficulties to the problem of CS composition for data-intensive applications (DiA) in a hybrid cloud (CSCD-HC). Solving the CSCD-HC problem has become a challenging task due to the uncertain QoS, the diverse hardware configurations and the flexible pricing about CSs. This paper proposes a collaborative optimization approach for CSCD-HC. This approach models a DiA as a role-based collaboration (RBC) system and employs the environments—classes, agents, roles, groups, and objects (E-CARGO) model to formalize the CSCD-HC problem with complicated constraints. To deal with the multi-valued QoS evaluations, this paper exploits the cloud model theory to analyze the performance of CSs, and presents a new method utilizing the Mahalanobis distance to improve the similarity calculation of QoS cloud models. Based on it, the qualification of candidate CSs can be precisely measured for supporting CS composition. A solution via the IBM ILOG CPLEX optimization package is put forward to solve the CSCD-HC problem. The experimental results demonstrate that the proposed approach is effective and feasible for optimizing CSCD-HC. [ABSTRACT FROM AUTHOR]

In multicore processor systems, being able to accurately predict the future provides new optimization opportunities, which otherwise could not be exploited. For example, an oracle able to predict a certain application's behavior running on a smart phone could direct the power manager to switch to appropriate dynamic voltage and frequency scaling modes that would guarantee minimum levels of desired performance while saving energy consumption and thereby prolonging battery life. Using predictions enables systems to become proactive rather than continue to operate in a reactive manner. This prediction-based proactive approach has become increasingly popular in the design and optimization of integrated circuits and of multicore processor systems. Prediction transforms from simple forecasting to sophisticated machine learning based prediction and classification that learns from existing data, employs data mining, and predicts future behavior. This can be exploited by novel optimization techniques that can span across all layers of the computing stack. In this survey paper, we present a discussion of the most popular techniques on prediction and classification in the general context of computing systems with emphasis on multicore processors. The paper is far from comprehensive, but, it will help the reader interested in employing prediction in optimization of multicore processor systems. [ABSTRACT FROM AUTHOR]

The problem of partitioning dense matrices into sets of sub-matrices has received increased attention recently and is crucial when considering dense linear algebra and kernels with similar communication patterns on heterogeneous platforms. The problem of load balancing and minimizing communication is traditionally reducible to an optimization problem that involves partitioning a square into rectangles. This problem has been proven to be NP-Complete for an arbitrary number of partitions. In this paper, we present recent approaches that relax the restriction that all partitions be rectangles. The first approach uses an original mathematical technique to find the exact optimal partitioning. Due to the complexity of the technique, it has been developed for a small number of partitions only. However, even at a small scale, the optimal partitions found by this approach are often non-rectangular and sometimes non-intuitive. The second approach is the study of approximate partitioning methods utilizing recursive partitioning algorithms. In particular we use the work on optimal partitioning to improve pre-existing algorithms. In this paper we discuss the different perspectives this approach opens and present two algorithms, SNRPP which is a $\sqrt{\frac{3}{2}}$ approximation, and NRPP which is a $\frac{2}{\sqrt{3}}$ approximation. While sub-optimal, the NRRP approach works for an arbitrary number of partitions. We use the first exact approach to analyse how close to the known optimal solutions the NRRP algorithm is for small numbers of partitions. [ABSTRACT FROM AUTHOR]

GPUs are widely used to accelerate the training of machine learning workloads. As modern machine learning models become increasingly larger, they require a longer time to train, leading to higher GPU energy consumption. This paper presents GPOEO, an online GPU energy optimization framework for machine learning training workloads. GPOEO dynamically determines the optimal energy configuration by employing novel techniques for online measurement, multi-objective prediction modeling, and search optimization. To characterize the target workload behavior, GPOEO utilizes GPU performance counters. To reduce the performance counter profiling overhead, it uses an analytical model to detect the training iteration change and only collects performance counter data when an iteration shift is detected. GPOEO employs multi-objective models based on gradient boosting and a local search algorithm to find a trade-off between execution time and energy consumption. We evaluate the GPOEO by applying it to 71 machine learning workloads from two AI benchmark suites running on an NVIDIA RTX3080Ti GPU. Compared with the NVIDIA default scheduling strategy, GPOEO delivers a mean energy saving of 16.2% with a modest average execution time increase of 5.1%. [ABSTRACT FROM AUTHOR]

Federated Learning (FL) enables the multiple participating devices to collaboratively contribute to a global neural network model while keeping the training data locally. Unlike the centralized training setting, the non-IID, imbalanced (statistical heterogeneity) and distribution shifted training data of FL is distributed in the federated network, which will increase the divergences between the local models and the global model, further degrading performance. In this paper, we propose a flexible clustered federated learning (CFL) framework named FlexCFL, in which we 1) group the training of clients based on the similarities between the clients’ optimization directions for lower training divergence; 2) implement an efficient newcomer device cold start mechanism for framework scalability and practicality; 3) flexibly migrate clients to meet the challenge of client-level data distribution shift. FlexCFL can achieve improvements by dividing joint optimization into groups of sub-optimization and can strike a balance between accuracy and communication efficiency in the distribution shift environment. The convergence and complexity are analyzed to demonstrate the efficiency of FlexCFL. We also evaluate FlexCFL on several open datasets and made comparisons with related CFL frameworks. The results show that FlexCFL can significantly improve absolute test accuracy by $+10.6\%$ + 10. 6 % on FEMNIST compared with FedAvg, $+3.5\%$ + 3. 5 % on FashionMNIST compared with FedProx, $+8.4\%$ + 8. 4 % on MNIST compared with FeSEM, $+4.7\%$ + 4. 7 % on Sentiment140 compare with IFCA. The experiment results show that FlexCFL is also communication efficient in the distribution shift environment. [ABSTRACT FROM AUTHOR]

In this article, we describe our efforts to reproduce results reported in the SC19 article by Hidayetoğlu et al., titled “MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization”. MemXCT's single-device performance, parallelized via OpenMP and MPI, was characterized using AMD Zen2 CPU cores and NVIDIA V100 GPU devices running on the Microsoft Azure cloud. We were able to reproduce most of the results, and exceed the performance of larger inputs, on an AMD EPYC HBv2 cluster. We were also able to reproduce the strong scaling trends for optimized CPU and GPU versions. Slight variations in performance of the CPU version were observed due to differences in the underlying hardware, input size, and number of available nodes. Digital artifacts from these experiments are available at: 10.5281/zenodo.5598108 [ABSTRACT FROM AUTHOR]

It is common that multiple cores reside on the same chip and share the on-chip cache. As a result, resource sharing can cause performance degradation of co-running jobs. Job co-scheduling is a technique that can effectively alleviate this contention and many co-schedulers have been reported in related literature. Most solutions however do not aim to find the optimal co-scheduling solution. Being able to determine the optimal solution is critical for evaluating co-scheduling systems. Moreover, most co-schedulers only consider serial jobs, and there often exist both parallel and serial jobs in real-world systems. In this paper a graph-based method is developed to find the optimal co-scheduling solution for serial jobs; the method is then extended to incorporate parallel jobs, including multi-process, and multi-threaded parallel jobs. A number of optimization measures are also developed to accelerate the solving process. Moreover, a flexible approximation technique is proposed to strike a balance between the solving speed and the solution quality. Extensive experiments are conducted to evaluate the effectiveness of the proposed co-scheduling algorithms. The results show that the proposed algorithms can find the optimal co-scheduling solution for both serial and parallel jobs. The proposed approximation technique is also shown to be flexible in the sense that we can control the solving speed by setting the requirement for the solution quality. [ABSTRACT FROM PUBLISHER]

The open shortest path first (OSPF) protocol has been widely applied to intra-domain routing in today’s Internet. Since a router running OSPF distributes traffic uniformly over equal-cost multi-path (ECMP), the OSPF-based optimal traffic engineering (TE) problem (i.e., deriving optimal link weights for a given traffic demand) is computationally intractable for large-scale networks. Therefore, many studies resort to multi-protocol label switching (MPLS) based approaches to solve the optimal TE problem. In this paper we present a generalized routing framework to realize the optimal TE, which can be potentially implemented via OSPF- or MPLS-based approaches. We start with viewing the conventional optimal TE problem in a fresh way, i.e., optimally allocating the residual capacity to every link. Then we make a generalization of network utility maximization (NUM) to close this problem, where the network operator is associated with a utility function of the residual capacity to be maximized. We demonstrate that under this framework, the optimal routes resulting from the optimal TE are also the shortest paths in terms of a set of non-negative link weights that are explicitly determined by the optimal residual capacity and the objective function. The network entropy maximization theory is employed to enable routers to exponentially, instead of uniformly, split traffic over ECMP. The shortest-path penalizing exponential flow-splitting (SPEF) is designed as a link-state protocol with hop-by-hop forwarding to implement our theoretical findings. An alternative MPLS-based implementation is also discussed here. Numerical simulation results have demonstrated the effectiveness of the proposed framework as well as SPEF. [ABSTRACT FROM AUTHOR]

Much progress has recently been made in global optimization, with particular attention devoted to robust nature-inspired stochastic methods for difficult, high-dimensional problems. This paper presents a computational study of an adaptation of one such method, particle swarm optimization (PSO), which is analyzed for parallelization on readily-available heterogeneous parallel computational hardware: specifically, multicore technologies accelerated by graphics processing units (GPUs), as well as Intel Xeon Phi co-processors accelerated with vectorization. In this heterogeneous approach, computationally-intensive, task-parallel components are performed with multicore parallelism and data-parallel elements are executed via co-processing (GPUs or vectorization). A computationally intensive adaptive PSO technique is parallelized according to this schema. In experiments with two high-dimensional and complex functions, large speedups can be obtained. Thus, a heterogeneous approach mitigates the time complexity of PSO adaptations, suggesting that other time-intensive stochastic methods can also benefit from the techniques proposed here. [ABSTRACT FROM PUBLISHER]

With the development of computer architecture, even for embedded systems, GPU devices can be integrated, providing outstanding performance and energy efficiency to meet the requirements of different industries, applications, and deployment environments. Data analytics is an important application scenario for embedded systems. Unfortunately, due to the limitation of the capacity of the embedded device, the scale of problems handled by the embedded system is limited. In this paper, we propose a novel data analytics method, called G-TADOC, for efficient text analytics directly on compression on embedded GPU systems. A large amount of data can be compressed and stored in embedded systems, and can be processed directly in the compressed state, which greatly enhances the processing capabilities of the systems. Particularly, G-TADOC has three innovations. First, a novel fine-grained thread-level workload scheduling strategy for GPU threads has been developed, which partitions heavily-dependent loads adaptively in a fine-grained manner. Second, a GPU thread-safe memory pool has been developed to handle inconsistency with low synchronization overheads. Third, a sequence-support strategy is provided to maintain high GPU parallelism while ensuring sequence information for lossless compression. Moreover, G-TADOC involves special optimizations for embedded GPUs, such as utilizing the CPU-GPU shared unified memory. Experiments show that G-TADOC provides 13.2× average speedup compared to the state-of-the-art TADOC. G-TADOC also improves performance-per-cost by 2.6× and energy efficiency by 32.5× over TADOC. [ABSTRACT FROM AUTHOR]

Owing to its attractive features such as fast identification and relatively long interrogating range over the classical barcode systems, radio-frequency identification (RFID) technology possesses a promising prospect in many practical applications such as inventory control and supply chain management. However, unknown tags appear in RFID systems when the tagged objects are misplaced or unregistered tagged objects are moved in, which often causes huge economic losses. This paper addresses an important and challenging problem of unknown tag identification in large-scale RFID systems. The existing protocols leverage the Aloha-like schemes to distinguish the unknown tags from known tags at the slot level, which are of low time-efficiency, and thus can hardly satisfy the delay-sensitive applications. To fill in this gap, two filtering-based protocols (at the bit level) are proposed in this paper to address the problem of unknown tag identification efficiently. Theoretical analysis of the protocol parameters is performed to minimize the execution time of the proposed protocols. Extensive simulation experiments are conducted to evaluate the performance of the protocols. The results demonstrate that the proposed protocols significantly outperform the currently most promising protocols. [ABSTRACT FROM AUTHOR]

Delay tolerant networks (DTNs) are characterized by high end-to-end latency, frequent disconnection, and opportunistic communication over unreliable wireless links. In this paper, we design and validate a dynamic trust management protocol for secure routing optimization in DTN environments in the presence of well-behaved, selfish and malicious nodes. We develop a novel model-based methodology for the analysis of our trust protocol and validate it via extensive simulation. Moreover, we address dynamic trust management, i.e., determining and applying the best operational settings at runtime in response to dynamically changing network conditions to minimize trust bias and to maximize the routing application performance. We perform a comparative analysis of our proposed routing protocol against Bayesian trust-based and non-trust based (PROPHET and epidemic) routing protocols. The results demonstrate that our protocol is able to deal with selfish behaviors and is resilient against trust-related attacks. Furthermore, our trust-based routing protocol can effectively trade off message overhead and message delay for a significant gain in delivery ratio. Our trust-based routing protocol operating under identified best settings outperforms Bayesian trust-based routing and PROPHET, and approaches the ideal performance of epidemic routing in delivery ratio and message delay without incurring high message or protocol maintenance overhead. [ABSTRACT FROM AUTHOR]

Programming hybrid CPU-GPU clusters is hard. This paper addresses this difficulty and presents the design and runtime implementation of Unicorn—a parallel programming model for hybrid CPU-GPU clusters. In particular, this paper proves that efficient distributed shared memory style programing is possible and its simplicity can be retained across CPUs and GPUs in a cluster, minus the frustration of dealing with race conditions. Further, this can be done with a unified abstraction, avoiding much of the complication of dealing with hybrid architectures. This is achieved with the help of transactional semantics (on shared global address spaces), deferred bulk data synchronization, workload pipelining and various communication and computation scheduling optimizations. We describe the said abstraction, our computation and communication scheduling system and report its performance on a few benchmarks like Matrix Multiplication, LU Decomposition and 2D FFT. We find that parallelization of coarse-grained applications like matrix multiplication or 2D FFT using our system requires only about 30 lines of C code to set up the runtime. The rest of the application code is regular single CPU/GPU implementation. This indicates the ease of extending parallel code to a distributed environment. The execution is efficient as well. When multiplying two square matrices of size $65,536\times 65,536$ , Unicornachieves a peak performance of 7.88 TFlop/s when run over a cluster of 14 nodes with each node equipped with two Tesla M2070 GPUs and two 6-core Intel Xeon 2.67 GHz CPUs, connected over a 32 Gbps Infiniband network. In this paper, we also demonstrate that the Unicorn programming model can be efficiently used to implement high level abstractions like MapReduce. We use such an extension to implement PageRank and report its performance. For a sample web of 500 million web pages, our implementation completes a page rank iteration in about 18 seconds (on average) on a 14-node cluster. [ABSTRACT FROM AUTHOR]

Due to the increasing usage of cloud computing applications, it is important to minimize energy cost consumed by a data center, and simultaneously, to improve quality of service via data center management. One promising approach is to switch some servers in a data center to the idle mode for saving energy while to keep a suitable number of servers in the active mode for providing timely service. In this paper, we design both online and offline algorithms for this problem. For the offline algorithm, we formulate data center management as a cost minimization problem by considering energy cost, delay cost (to measure service quality), and switching cost (to change servers’s active/idle mode). Then, we analyze certain properties of an optimal solution which lead to a dynamic programming based algorithm. Moreover, by revising the solution procedure, we successfully eliminate the recursive procedure and achieve an optimal offline algorithm with a polynomial complexity. For the online algorithm, We design it by considering the worst case scenario for future workload. In simulation, we show this online algorithm can always provide near-optimal solutions. [ABSTRACT FROM PUBLISHER]

In a large-scale computing cluster, the job completions can be substantially delayed due to two sources of variability, namely, variability in the job size and that in the machine service capacity. To tackle this issue, existing works have proposed various scheduling algorithms which exploit redundancy wherein a job runs on multiple servers until the first completes. In this paper, we explore the impact of variability in the machine service capacity and adopt a rigorous analytical approach to design scheduling algorithms using redundancy and checkpointing. We design several online algorithms which can dynamically vary the number of redundant copies for jobs. We also provide new theoretical performance bounds for these algorithms in terms of the overall job flowtime by introducing the notion of a speedup function, based on which a novel potential function can be defined to enable the corresponding competitive ratio analysis. In particular, by adopting the online primal-dual fitting approach, we prove that our SRPT+R Algorithm in a non-multitasking cluster is $(1+\epsilon)$ (1 + ε) (1 + ε) -speed, $\ O(\frac{1}{\epsilon })$ O (1 ε) O (1 ε) -competitive. We also show that our proposed Fair+R and LAPS+R($\beta$ β β ) Algorithms for a multitasking cluster are $(4+\epsilon)$ (4 + ε) (4 + ε) -speed, $\ O(\frac{1}{\epsilon })$ O (1 ε) O (1 ε) -competitive and ($2 + 2\beta + 2\epsilon)$ 2 + 2 β + 2 ε) 2 + 2 β + 2 ε) -speed $O(\frac{1}{\beta \epsilon })$ O (1 β ε) O (1 β ε) -competitive respectively. We demonstrate via extensive simulations that our proposed algorithms can significantly reduce job flowtime under both the non-multitasking and multitasking modes. [ABSTRACT FROM AUTHOR]

Nowadays, by integrating the cloud radio access network (C-RAN) with the mobile edge cloud computing (MEC) technology, mobile service provider (MSP) can efficiently handle the increasing mobile traffic and enhance the capabilities of mobile devices. But the power consumption has become skyrocketing for MSP and it gravely affects the profit of MSP. Previous work often studied the power consumption in C-RAN and MEC separately while less work had considered the integration of C-RAN with MEC. In this paper, we present an unifying framework for the power-performance tradeoff of MSP by jointly scheduling network resources in C-RAN and computation resources in MEC to maximize the profit of MSP. To achieve this objective, we formulate the resource scheduling issue as a stochastic problem and design a new optimization framework by using an extended Lyapunov technique. Specially, because the standard Lyapunov technique critically assumes that job requests have fixed lengths and can be finished within each decision making interval, it is not suitable for the dynamic situation where the mobile job requests have variable lengths. To solve this problem, we extend the standard Lyapunov technique and design the VariedLen algorithm to make online decisions in consecutive time for job requests with variable lengths. Our proposed algorithm can reach time average profit that is close to the optimum with a diminishing gap (1/V) for the MSP while still maintaining strong system stability and low congestion. With extensive simulations based on a real world trace, we demonstrate the efficacy and optimality of our proposed algorithm. [ABSTRACT FROM AUTHOR]

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

Previous work on optimizing resource provisioning in virtualized environments focused either on mapping virtual machines (VMs) to physical machines (PMs) or mapping application components to VMs. In this paper, we argue that these two optimization problems influence each other significantly and in a highly non-trivial way. We define a sophisticated problem formulation for the joint optimization of the two mappings, taking into account sizing aspects, colocation constraints, license costs, and hardware affinity relations. As demonstrated by the empirical evaluation on a real-world workload trace, the combined optimization leads to significantly better overall results than considering the two problems in isolation. [ABSTRACT FROM PUBLISHER]

Nowadays it is becoming more and more attractive to execute workflow applications in the cloud because it enables workflow applications to use computing resources on demand. Meanwhile, it also challenges traditional workflow scheduling algorithms that only concentrate on optimizing the execution time. This paper investigates how to minimize execution cost of a workflow in clouds under a deadline constraint and proposes a metaheuristic algorithm L-ACO as well as a simple heuristic ProLiS. ProLiS distributes the deadline to each task, proportionally to a novel definition of probabilistic upward rank, and follows a two-step list scheduling methodology: rank tasks and sequentially allocates each task a service which meets the sub-deadline and minimizes the cost. L-ACO employs ant colony optimization to carry out deadline-constrained cost optimization: the ant constructs an ordered task list according to the pheromone trail and probabilistic upward rank, and uses the same deadline distribution and service selection methods as ProLiS to build solutions. Moreover, the deadline is relaxed to guide the search of L-ACO towards constrained optimization. Experimental results show that compared with traditional algorithms, the performance of ProLiS is very competitive and L-ACO performs the best in terms of execution costs and success ratios of meeting deadlines. [ABSTRACT FROM AUTHOR]

In the last decade, several GPU implementations of Support Vector Machine (SVM) training with nonlinear kernels were published. Some of them even with source codes. The most effective ones are based on Sequential Minimal Optimization (SMO). They decompose the restricted quadratic problem into a series of smallest possible subproblems, which are then solved analytically. For large datasets, the majority of elapsed time is spent by a large amount of matrix-vector multiplications that cannot be computed efficiently on current GPUs because of limited memory bandwidth. In this paper, we introduce a novel GPU approach to the SVM training that we call Optimized Hierarchical Decomposition SVM (OHD-SVM). It uses a hierarchical decomposition iterative algorithm that fits better to actual GPU architecture. The low decomposition level uses a single GPU multiprocessor to efficiently solve a local subproblem. Nowadays a single GPU multiprocessor can run thousand or more threads that are able to synchronize quickly. It is an ideal platform for a single kernel SMO-based local solver with fast local iterations. The high decomposition level updates gradients of entire training set and selects a new local working set. The gradient update requires many kernel values that are costly to compute. However, solving a large local subproblem offers an efficient kernel values computation via a matrix-matrix multiplication that is much more efficient than the matrix-vector multiplication used in already published implementations. Along with a description of our implementation, the paper includes an exact comparison of five publicly available C++ SVM training GPU implementations. In this paper, the binary classification task and RBF kernel function are taken into account as it is usual in most of the recent papers. According to the measured results on a wide set of publicly available datasets, our proposed approach excelled significantly over the other methods in all datasets. The biggest difference was on the largest dataset where we achieved speed-up up to 12 times in comparison with the fastest already published GPU implementation. Moreover, our OHD-SVM is the only one that can handle dense as well as sparse datasets. Along with this paper, we published the source-codes at https://github.com/OrcusCZ/OHD-SVM. [ABSTRACT FROM AUTHOR]

As demands for cloud-based data processing continue to grow, cloud providers seek effective techniques that deliver value to the businesses without violating Service Level Agreements (SLAs). Cloud right-sizing has emerged as a very promising technique for making cloud services more cost-effective. In this paper, we present CRED, a novel framework for cloud right-sizing with execution deadlines and data locality constraints. CRED jointly optimizes data placement and task scheduling in data centers with the aim of minimizing the number of nodes needed while meeting users’ SLA requirements. We formulate CRED as an integer optimization problem and present a heuristic algorithm with provable performance guarantees to solve the problem. Competitive ratios of the proposed algorithm are quantified in closed form for arbitrary task parameters and cloud configurations. We also extend our work to obtain a resilient solution, which allows successful recovery at run time from any single node failure and is guaranteed to meet both deadline and locality constraints. Simulation results using Google trace show that our proposed algorithm significantly outperforms existing heuristics such as first-fit by reducing the number of required active servers by up to 47 percent, and achieves near-optimal performance. We also show that our algorithm can significantly improve utilization of both computational resources and storage space by up to 28 and 15 percent, respectively. [ABSTRACT FROM AUTHOR]

Web-scale knowledge graphs containing billions of entities are common nowadays. Querying these graphs can be modeled as a subgraph matching problem. Since knowledge graphs are incomplete and noisy in nature, it is important to discover answers matching exactly as well as answers similar to queries. Existing graph matching algorithms usually use graph indices to accelerate query processing. For billion-node graphs, it may be infeasible to build the graph indices due to the amount of work and the memory/storage required. In this paper, we propose an efficient algorithm for finding the best $k$ answers for a given query without precomputing graph indices. An answer’s quality is measured by a matching score that is computed online. To accelerate query processing, we propose a novel technique for bounding the matching scores during the computation. By using bounds, the low quality answers can be efficiently pruned. The bounding technique can be implemented in a distributed environment, allowing our approach to efficiently query web-scale knowledge graphs. We evaluate the effectiveness and the efficiency of our approach on real-world datasets. The result shows that our bounding technique can reduce the running time up to two orders of magnitude comparing to an approach without using bounds. [ABSTRACT FROM AUTHOR]

Rollback is an effective technique to resume the system execution from a recorded intermediate state upon failures, without having to restart the entire system. However, in virtualized environments, rollback of a virtual machine cluster (VMC) produces high network traffic and long service disruption, particularly for a large cluster used for scientific computing, thereby imposing significant overhead both on network and applications. This paper proposes Piccolo, a fast and efficient rollback system, to restore a VMC from snapshot files over data center network. First, we exploit the similarity among VMC snapshots and leverage multicast to deliver the identical pages across VMs placed on disperse hosts, thereby bypassing unnecessary transmission of a large number of pages. Second, we analyze the impact on network traffic of varying VM placements in data center network, formulate the traffic aware placement as an optimization problem, and design a two-tier approximation algorithm that efficiently solves the problem. In addition to presenting Piccolo, we detail its implementation, and evaluate it by a set of experiments. The results show that Piccolo could achieve a significant reduction in terms of total sent data, network traffic and rollback latency compared to the existing generic techniques. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a unified framework for studying various cloud traffic management problems, ranging from geographical load balancing to backbone traffic engineering. We first abstract these real-world problems as a multi-facility resource allocation problem, and then present two distributed optimization algorithms by exploiting the special structure of the problem. Our algorithms are inspired by Alternating Direction Method of Multipliers (ADMM), enjoying a number of unique features. Compared to dual decomposition, they converge with non-strictly convex objective functions; compared to other ADMM-type algorithms, they not only achieve faster convergence under weaker assumptions, but also have lower computational complexity and lower message-passing overhead. The simulation results not only confirm these desirable features of our algorithms, but also highlight several additional advantages, such as scalability and fault-tolerance. [ABSTRACT FROM AUTHOR]

Contemporary cloud networks are being challenged by the rapid increase of user demands and growing concerns about global warming, due to their substantial energy consumption. This requires future data centers to be both energy efficient and sustainable, which calls for leveraging cutting-edge features and the flexibility provided by the modern smart grids. To fulfill those goals, this paper puts forward a systematic approach to designing energy-aware traffic-efficient geographical load balancing schemes for data-center networks that are not only optimal, but also computationally efficient and amenable to distributed implementation. Under this comprehensive approach, workload and power balancing schemes are designed jointly across the network, both delay-tolerant and interactive workloads are accommodated, novel smart-grid features such as energy storage units are incorporated to cope with renewables, and incentive pricing mechanisms are adopted in the design. To further account for the spatio-temporal variation of demands, energy prices and renewables, the task is formulated as a two-timescale stochastic optimization. Leveraging dual stochastic approximation and the fast iterative shrinkage-thresholding algorithm (FISTA), the proposed optimization is decomposed across time slots (first-stage) and data centers (second-stage). While the resultant online algorithm is strictly feasible and provably optimal under a Markovian assumption for the underlying random processes, extensive numerical tests further demonstrate that it also works well in real-data scenarios, where the underlying randomness is highly correlated across time. [ABSTRACT FROM PUBLISHER]

Deep Neural Networks (DNNs) have recently been shown to significantly outperform existing machine learning techniques in several pattern recognition tasks. DNNs are the state-of-the-art models used in image recognition, object detection, classification and tracking, and speech and language processing applications. The biggest drawback to DNNs has been the enormous cost in computation and time taken to train the parameters of the networks-often a tenfold increase relative to conventional technologies. Such training time costs can be mitigated by the application of parallel computing algorithms and architectures. However, these algorithms often run into difficulties because of the cost of inter-processor communication bottlenecks. In this paper, we describe how to enable Parallel Deep Neural Network Training on the IBM Blue Gene/Q (BG/Q) computer system. Specifically, we explore DNN training using the data-parallel Hessian-free 2nd order optimization algorithm. Such an algorithm is particularly well-suited to parallelization across a large set of loosely coupled processors. BG/Q, with its excellent inter-processor communication characteristics, is an ideal match for this type of algorithm. The paper discusses how issues regarding programming model and data-dependent imbalances are addressed. Results on large-scale speech tasks show that the performance on BG/Q scales linearly up to 4,096 processes with no loss in accuracy. This allows us to train neural networks using billions of training examples in a few hours. [ABSTRACT FROM AUTHOR]

Load balancing is a widely accepted technique for performance optimization of scientific applications on parallel architectures. Indeed, balanced applications do not waste processor cycles on waiting at points of synchronization and data exchange, maximizing this way the utilization of processors. In this paper, we challenge the universality of the load-balancing approach to optimization of the performance of parallel applications. First, we formulate conditions that should be satisfied by the performance profile of an application in order for the application to achieve its best performance via load balancing. Then we use a real-life scientific application, EULAG MPDATA kernel, to demonstrate that its performance profile on a modern parallel architecture, Intel Xeon Phi, significantly deviates from these conditions. Based on this observation, we propose a method of performance optimization of scientific applications through load imbalancing. In the case of data parallel application, the method uses functional performance models of the application to find partitioning that minimizes its computation time but not necessarily balances the load of processors. We apply this method to optimization of MPDATA on Intel Xeon Phi. Experimental results demonstrate that the performance of this carefully optimized load-balanced application can be further improved by 15percent using the proposed load-imbalancing technique. [ABSTRACT FROM PUBLISHER]

Modern day data centers coordinate hundreds of thousands of heterogeneous tasks and aim at delivering highly reliable cloud computing services. Although offering equal reliability to all users benefits everyone at the same time, users may find such an approach either inadequate or too expensive to fit their individual requirements, which may vary dramatically. In this paper, we propose a novel method for providing elastic reliability optimization in cloud computing. Our scheme makes use of peer-to-peer checkpointing and allows user reliability levels to be jointly optimized based on an assessment of their individual requirements and total available resources in the data center. We show that the joint optimization can be efficiently solved by a distributed algorithm using dual decomposition. The solution improves resource utilization and presents an additional source of revenue to data center operators. Our validation results suggest a significant improvement of reliability over existing schemes. [ABSTRACT FROM PUBLISHER]

A big parallel processing job can be delayed substantially as long as one of its many tasks is being assigned to an unreliable or congested machine. To tackle this so-called straggler problem, most parallel processing frameworks such as MapReduce have adopted various strategies under which the system may speculatively launch additional copies of the same task if its progress is abnormally slow when extra idling resource is available. In this paper, we focus on the design of speculative execution schemes for parallel processing clusters from an optimization perspective under different loading conditions. For the lightly loaded case, we analyze and propose one cloning scheme, namely, the Smart Cloning Algorithm (SCA) which is based on maximizing the overall system utility. We also derive the workload threshold under which SCA should be used for speculative execution. For the heavily loaded case, we propose the Enhanced Speculative Execution (ESE) algorithm which is an extension of the Microsoft Mantri scheme to mitigate stragglers. Our simulation results show SCA reduces the total job flowtime, i.e., the job delay/ response time by nearly $6$ percent comparing to the speculative execution strategy of Microsoft Mantri. In addition, we show that the ESE Algorithm outperforms the Mantri baseline scheme by $71$ percent in terms of the job flowtime while consuming the same amount of computation resource. [ABSTRACT FROM AUTHOR]

The traditional single-level checkpointing method suffers from significant overhead on large-scale platforms. Hence, multilevel checkpointing protocols have been studied extensively in recent years. The multilevel checkpoint approach allows different levels of checkpoints to be set (each with different checkpoint overheads and recovery abilities), in order to further improve the fault tolerance performance of extreme-scale HPC applications. How to optimize the checkpoint intervals for each level, however, is an extremely difficult problem. In this paper, we construct an easy-to-use two-level checkpoint model. Checkpoint level 1 deals with errors with low checkpoint/recovery overheads such as transient memory errors, while checkpoint level 2 deals with hardware crashes such as node failures. Compared with previous optimization work, our new optimal checkpoint solution offers two improvements: (1) it is an online solution without requiring knowledge of the job length in advance, and (2) it shows that periodic patterns are optimal and determines the best pattern. We evaluate the proposed solution and compare it with the most up-to-date related approaches on an extreme-scale simulation testbed constructed based on a real HPC application execution. Simulation results show that our proposed solution outperforms other optimized solutions and can improve the performance significantly in some cases. Specifically, with the new solution the wall-clock time can be reduced by up to 25.3 percent over that of other state-of-the-art approaches. Finally, a brute-force comparison with all possible patterns shows that our solution is always within $1$ percent of the best pattern in the experiments. [ABSTRACT FROM PUBLISHER]

MapReduce, originally developed by Google for search applications, has recently become a popular programming framework for parallel and distributed environments. This paper presents an energy-efficient architecture design for MapReduce on Field Programmable Gate Arrays (FPGAs). The major goal is to enable users to program FPGAs with simple MapReduce interfaces, and meanwhile to embrace automatic performance optimizations within the MapReduce framework. Compared to other processors like CPUs and GPUs, FPGAs are (re-)programmable hardware and have very low energy consumption. However, the design and implementation of MapReduce on FPGAs can be challenging: firstly, FPGAs are usually programmed with hardware description languages, which hurts the programmability of the MapReduce design to its users; secondly, since MapReduce has irregular access patterns (especially in the reduce phase) and needs to support user-defined functions, careful designs and optimizations are required for efficiency. In this paper, we design, implement and evaluate Melia, a MapReduce framework on FPGAs. Melia takes advantage of the recent OpenCL programming framework developed for Altera FPGAs, and abstracts FPGAs behind the simple and familiar MapReduce interfaces in C. We further develop a series of FPGA-centric optimization techniques to improve the efficiency of Melia, and a cost- and resource-based approach to automate the parameter settings for those optimizations. We evaluate Melia on a recent Altera Stratix V GX FPGA with a number of commonly used MapReduce benchmarks. Our results demonstrate that 1) the efficiency and effectiveness of our optimizations and automated parameter setting approach, 2) Melia can achieve promising energy efficiency in comparison with its counterparts on CPUs/GPUs on both single-FPGA and cluster settings. [ABSTRACT FROM AUTHOR]

Erasure codes tolerate disk failures by pre-storing a low degree of data redundancy, and have been commonly adopted in current storage systems. However, the attached requirement on data consistency exaggerates partial stripe write operations and thus seriously downgrades system performance. Previous works to optimize partial stripe writes are relatively limited, and a general mechanism is still absent. In this paper, we propose a Parity-Switched Data Placement (PDP) to optimize partial stripe writes for any XOR-coded storage system. PDP first reduces the write operations by arranging continuous data elements to join a common parity element's generation. To achieve a deeper optimization, PDP further explores the generation orders of parity elements and makes any two continuous data elements associate with a common parity element. Intensive evaluations show that for tested erasure codes, PDP reduces up to 31.9 percent of write operations and further increases the write speed by up to 59.8 percent when compared with two state-of-the-art data placement methods. [ABSTRACT FROM PUBLISHER]

System scaling becomes essential and indispensable for distributed storage systems due to the explosive growth of data volume. Considering that fault-protection is a necessity in large-scale distributed storage systems, and Cauchy Reed-Solomon (CRS) codes are widely deployed to tolerate multiple simultaneous node failures, this paper studies the scaling problem of distributed storage systems with CRS codes. In particular, we formulate the scaling problem with an optimization model in which both the post-scaling encoding matrix and the data migration policy are assumed to be unknown in advance. To minimize the I/O overhead, we propose a three-phase optimization scaling scheme for CRS codes. Specifically, we first derive the optimal post-scaling encoding matrix under a given data migration policy, then optimize the data migration process using the selected post-scaling encoding matrix, and finally exploit the Maximum Distance Separable (MDS) property to further optimize the designed data migration process. Our scaling scheme requires minimal data movement while achieving uniform data distribution. Moreover, it requires to read fewer data blocks than conventional minimum data migration schemes, but still guarantees the minimum amount of migrated data. To validate the efficiency of our scheme, we implement it atop a networked file system. Extensive experiments show that our scaling scheme uses less scaling time than the basic scheme. [ABSTRACT FROM PUBLISHER]

Virtual appliances store the required information to instantiate a functional Virtual Machine (VM) on Infrastructure as a Service (IaaS) cloud systems. Large appliance size obstructs IaaS systems to deliver dynamic and scalable infrastructures according to their promise. To overcome this issue, this paper offers a novel technique for virtual appliance developers to publish appliances for the dynamic environments of IaaS systems. Our solution achieves faster virtual machine instantiation by reducing the appliance size while maintaining its key functionality. The new virtual appliance optimization algorithm identifies the removable parts of the appliance. Then, it applies active fault injection to remove the identified parts. Afterward, our solution assesses the functionality of the reduced virtual appliance by applying the—appliance developer provided—validation algorithms. We also introduce a technique to parallelize the fault injection and validation phases of the algorithm. Finally, the prototype implementation of the algorithm is discussed to demonstrate the efficiency of the proposed algorithm through the optimization of two well-known virtual appliances. Results show that the algorithm significantly decreased virtual machine instantiation time and increased dynamism in IaaS systems. [ABSTRACT FROM AUTHOR]

With the increased complexity of platforms coupled with data centers' servers sprawl, power consumption is reaching unsustainable limits. Researchers have addressed data centers' performance-per-watt management at different hierarchies going from server clusters to servers to individual components within the server platform. This paper addresses performance-per-watt maximization of memory subsystems in a data center. Traditional memory power management techniques rely on profiling the utilization of memory modules and transitioning them to some low-power mode when they are sufficiently idle. However, fully interleaved memory presents an interesting research challenge because data striping across memory modules reduces the idleness of individual modules to warrant transitions to low-power states. In this paper, we present a novel technique for performance-per-watt maximization of interleaved memory by dynamically reconfiguring (expanding or contracting) the degree of interleaving to adapt to incoming workload. The reconfigured memory hosts the application's working set on a smaller set of modules in a manner that exploits the platform's memory hierarchy architecture. This creates the opportunity for the remaining memory modules to transition to low-power states and remain in those states for as long as the performance remains within given acceptable thresholds. The memory power expenditure is minimized subject to application memory requirements and end-to-end memory access delay constraints. This is formulated as a performance-per- watt maximization problem and solved using an analytical memory power and performance model. Our technique has been validated on a real server using SPECjbb benchmark and on a trace-driven memory simulator using SPECjbb and gcc memory traces. On the server, our techniques are shown to give about 48.8 percent (26.7 kJ) energy savings compared to traditional techniques measured at 4.5 percent. The maximum improvement in performance-per-watt was measured at 88.48 percent. The simulator showed 89.7 percent improvement in performance-per-watt compared to thebest performing traditional technique. [ABSTRACT FROM AUTHOR]

Adaptable computing is an increasingly important paradigm that specializes system resources to variable application requirements, environmental conditions, or user requirements. Adapting computing resources to variable application requirements (or application phases) is otherwise known as phase-based optimization. Phase-based optimization takes advantage of application phases, or execution intervals of an application that behave similarly, to enable effective and beneficial adaptability. In order for phase-based optimization to be effective, the phases must first be classified to determine when application phases begin and end, and ensure that system resources are accurately specialized. In this paper, we present a survey of phase classification techniques that have been proposed to exploit the advantages of adaptable computing through phase-based optimization. We focus on recent techniques and classify these techniques with respect to several factors in order to highlight their similarities and differences. We divide the techniques by their major defining characteristics—online/offline and serial/parallel. In addition, we discuss other characteristics such as prediction and detection techniques, the characteristics used for prediction, interval type, etc. We also identify gaps in the state-of-the-art and discuss future research directions to enable and fully exploit the benefits of adaptable computing. [ABSTRACT FROM AUTHOR]

Recent advances in composing Cloud applications have been driven by deployments of inter-networking heterogeneous microservices across multiple Cloud datacenters. System dependability has been of the upmost importance and criticality to both service vendors and customers. Security, a measurable attribute, is increasingly regarded as the representative example of dependability. Literally, with the increment of microservice types and dynamicity, applications are exposed to aggravated internal security threats and externally environmental uncertainties. Existing work mainly focuses on the QoS-aware composition of native VM-based Cloud application components, while ignoring uncertainties and security risks among interactive and interdependent container-based microservices. Still, orchestrating a set of microservices across datacenters under those constraints remains computationally intractable. This paper describes a new dependable microservice orchestration framework GA-Par to effectively select and deploy microservices whilst reducing the discrepancy between user security requirements and actual service provision. We adopt a hybrid (both whitebox and blackbox based) approach to measure the satisfaction of security requirement and the environmental impact of network QoS on system dependability. Due to the exponential grow of solution space, we develop a parallel Genetic Algorithm framework based on Spark to accelerate the operations for calculating the optimal or near-optimal solution. Large-scale real world datasets are utilized to validate models and orchestration approach. Experiments show that our solution outperforms the greedy-based security aware method with 42.34 percent improvement. GA-Par is roughly 4x faster than a Hadoop-based genetic algorithm solver and the effectiveness can be constantly guaranteed under different application scales. [ABSTRACT FROM AUTHOR]

The adoption of large-scale MPSoCs and the globalization of the IC design flow give rise to two major concerns: high power density due to continuous technology scaling and security due to the untrustworthiness of the third-party intellectual property (3PIP) cores. However, little work has been undertaken to consider these two critical issues jointly during the design stage. In this paper, we propose a design methodology that minimizes the energy consumption while simultaneously protecting the MPSoC against the effects of hardware trojans. The proposed methodology consists of three main stages: 1) Task scheduling to introduce core diversity in the MPSoC in order to detect the presence of malicious modifications in the cores, or mute their effects at runtime, 2) Vendor assignment to the cores using a novel heuristic that chooses vendor-specific cores with operating speed that minimizes the total energy consumption of the MPSoC, and 3) Explore optimization opportunities for further energy savings by minimizing idle periods on the cores, which are caused by the inter-task data dependencies. Experimental results show that our solutions consume only 1/3 energy of existing solutions without increasing schedule length while satisfying the security constraints. [ABSTRACT FROM AUTHOR]

One of the critical goals in code optimization for Multiprocessor-System-on-a-Chip (MPSoC) architectures is to minimize the number of off-chip memory accesses. This is because such accesses can be extremely costly from both performance and power angles. Although conventional data locality optimization techniques can be used for improving data access pattern of each processor independently, such techniques usually do not consider locality for shared data. This paper proposes a strategy that reduces the number of off-chip references due to shared data. It achieves this goal by restructuring a parallelized application code in such a fashion that a given data block is accessed by parallel processors within the same time frame so that its reuse is maximized while it is in the on-chip memory space. This tends to minimize the number of off-chip references, since the accesses to a given data block are clustered within a short period of time during execution. Our approach employs a polyhedral tool that helps us isolate computations that manipulate a given data block. In order to test the effectiveness of our approach, we implemented it by using a publicly available compiler infrastructure and conducted experiments with 12 data-intensive embedded applications. Our results show that optimizing data locality for shared data elements is very useful in practice. [ABSTRACT FROM AUTHOR]

Transparent data replication is a promising technique for improving the system performance of a large distributed network. Transcoding is an important technology which adapts the same multimedia object to diverse mobile appliances; thus, users' requests for a specified version of a multimedia object could be served by a more detailed version cached according to transcoding. Therefore, it is particularly of theoretical and practical necessity to determine the proper version to be cached at each node such that the specified objective is achieved. In this paper, we address the problem of multimedia object placement for transparent data replication. The performance objective is to minimize the total access cost by considering both transmission cost and transcoding cost. We present optimal solutions for different cases for this problem. The performance of the proposed solutions is evaluated with a set of carefully designed simulation experiments for various performance metrics over a wide range of system parameters. The simulation results show that our solution consistently and significantly outperforms comparison solutions in terms of all the performance metrics considered. [ABSTRACT FROM AUTHOR]

Recently, intelligent scheduling approaches using surrogate models have been proposed to efficiently allocate volatile tasks in heterogeneous fog environments. Advances like deterministic surrogate models, deep neural networks (DNN) and gradient-based optimization allow low energy consumption and response times to be reached. However, deterministic surrogate models, which estimate objective values for optimization, do not consider the uncertainties in the distribution of the Quality of Service (QoS) objective function that can lead to high Service Level Agreement (SLA) violation rates. Moreover, the brittle nature of DNN training and the limited exploration with low agility in gradient-based optimization prevent such models from reaching minimal energy or response times. To overcome these difficulties, we present a novel scheduler that we call GOSH for Gradient Based Optimization using Second Order derivatives and Heteroscedastic Deep Surrogate Models. GOSH uses a second-order gradient based optimization approach to obtain better QoS and reduce the number of iterations to converge to a scheduling decision, subsequently lowering the scheduling time. Instead of a vanilla DNN, GOSH uses a Natural Parameter Network (NPN) to approximate objective scores. Further, a Lower Confidence Bound (LCB) optimization approach allows GOSH to find an optimal trade-off between greedy minimization of the mean latency and uncertainty reduction by employing error-based exploration. Thus, GOSH and its co-simulation based extension GOSH*, can adapt quickly and reach better objective scores than baseline methods. We show that GOSH* reaches better objective scores than GOSH, but it is suitable only for high resource availability settings, whereas GOSH is apt for limited resource settings. Real system experiments for both GOSH and GOSH* show significant improvements against the state-of-the-art in terms of energy consumption, response time and SLA violations by up to 18, 27 and 82 percent, respectively. [ABSTRACT FROM AUTHOR]

Convolutional Neural Networks (GCNs) have emerged as promising tools for graph-based machine learning applications. Given that GCNs are both compute- and memory-intensive, this constitutes a major challenge for the underlying hardware to efficiently process large-scale GCNs. In this article, we introduce SGCNAX, a scalable GCN accelerator architecture for the high-performance and energy-efficient acceleration of GCNs. Unlike prior GCN accelerators that either employ limited loop optimization techniques, or determine the design variables based on random sampling, we systematically explore the loop optimization techniques for GCN acceleration and propose a flexible GCN dataflow that adapts to different GCN configurations to achieve optimal efficiency. We further propose two hardware-based techniques to address the workload imbalance problem caused by the unbalanced distribution of zeros in GCNs. Specifically, SGCNAX exploits an outer-product-based computation architecture that mitigates the intra-PE (Processing Elements) workload imbalance, and employs a group-and-shuffle approach to mitigate the inter-PE workload imbalance. Simulation results show that SGCNAX performs 9.2×, 1.6× and 1.2× better, and reduces DRAM accesses by a factor of 9.7×, 2.9× and 1.2× compared to HyGCN, AWB-GCN, and GCNAX, respectively. [ABSTRACT FROM AUTHOR]

This work extends our previous research entitled “MemXCT: Memory-centric X-ray CT Reconstruction with Massive Parallelization” that was originally published at SC19 conference (Hidayetoğlu et al., 2019) with reproducibility of the computational imaging performance. X-ray computed tomography (XCT) is regularly used at synchrotron light sources to study the internal morphology of materials at high resolution. However, experimental constraints, such as radiation sensitivity, can result in noisy or undersampled measurements. Further, depending on the resolution, sample size and data acquisition rates, the resulting noisy dataset can be in the order of terabytes. Advanced iterative reconstruction techniques can produce high-quality images from noisy measurements, but their computational requirements have made their use an exception rather than the rule. We propose a novel memory-centric approach that avoids redundant computations at the expense of additional memory complexity. We develop a memory-centric iterative reconstruction system, MemXCT, that uses an optimized SpMV implementation with two-level pseudo-Hilbert ordering and multi-stage input buffering. We evaluate MemXCT on various supercomputer architectures involving KNL and GPU. MemXCT can reconstruct a large (11K×11K) mouse brain tomogram in 10 seconds using 4096 KNL nodes (256K cores). The results presented in our original article at the SC19 were based on large-scale supercomputing resources. The MemXCT application was selected for the Student Cluster Competition (SCC) Reproducibility Challenge and evaluated on a variety of cloud computing resources by universities around the world in the SC20 conference. We summarize the results of the top-ranked SCC Reproducibility Challenge teams and identify the most pertinent measures for ensuring the reproducibility of our experiments in this article. [ABSTRACT FROM AUTHOR]

Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that, a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, incurring significant performance overhead. This paper presents a performance debugging framework, PERFPLAY, to facilitate the identification of unnecessary lock contentions and to guide programmers to improve the program performance by eliminating the unnecessary lock contentions. Since the performance debugging of unnecessary lock contentions is input-sensitive, we first identify the representative inputs for performance debugging. Next, PERFPLAY quantifies the performance impact of unnecessary lock contention code regions for each candidate input. Taking into account conflicting attribute of performance impact and input coverage in the real world, we finally make the tradeoff between performance impact and input coverage to recommend the optimal unnecessary lock contention code regions. Our final results on five real-world programs and PARSEC benchmarks demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PERFPLAY in troubleshooting the target unnecessary lock contention code regions with the consideration of both performance impact and input coverage. [ABSTRACT FROM AUTHOR]

Significant progress has been made in the development of programming languages and tools that are suitable for hybrid computer architectures that group several shared-memory multicores interconnected through a network. This paper addresses important limitations in the code generation for partitioned global address space (PGAS) languages. These languages allow fine-grained communication and lead to programs that perform many fine-grained accesses to data. When the data is distributed to remote computing nodes, code transformations are required to prevent performance degradation. Until now code transformations to PGAS programs have been restricted to the cases where both the physical mapping of the data or the number of processing nodes are known at compilation time. In this paper, a novel application of the inspector-executor model overcomes these limitations and allows profitable code transformations, which result in fewer and larger messages sent through the network, when neither the data mapping nor the number of processing nodes are known at compilation time. A performance evaluation reports both scaling and absolute performance numbers on up to 32,768 cores of a Power 775 supercomputer. This evaluation indicates that the compiler transformation results in speedups between 1.15$\times$ and 21 $\times$ over a baseline and that these automated transformations achieve up to 63 percent the performance of the MPI versions. [ABSTRACT FROM AUTHOR]

The processing of massive numbers of small files is a challenge in the design of distributed file systems. Currently, the combined-block-storage approach is prevalent. However, the approach employs the traditional file systems such as ExtFS and may cause inefficiency when accessing small files randomly located in the disk. This paper focuses on optimizing the performance of data servers in accessing massive numbers of small files. We present a Flat Lightweight File System (iFlatLFS) to manage small files, which is based on a simple metadata scheme and a flat storage architecture. iFlatLFS is designed to substitute the traditional file system on data servers and can be deployed underneath distributed file systems that store massive numbers of small files. iFlatLFS can greatly simplify the original data access procedure. The new metadata proposed in this paper occupies only a fraction of the metadata size based on traditional file systems. We have implemented iFlatLFS in CentOS 5.5 and integrated it into an open source Distributed File System (DFS), called Taobao FileSystem (TFS), which is developed by a top B2C service provider, Alibaba, in China and is managing over 28.6 billion small photos. We have conducted extensive experiments to verify the performance of iFlatLFS. The results show that when the file size ranges from 1 to 64 KB, iFlatLFS is faster than Ext4 by 48 and 54 percent on average for random read and write in the DFS environment, respectively. Moreover, after iFlatLFS is integrated into TFS, iFlatLFS-based TFS is faster than the existing Ext4-based TFS by 45 and 49 percent on average for random read access and hybrid access (the mix of read and write accesses), respectively. [ABSTRACT FROM AUTHOR]