Search

Since its creation, the ImageNet-1k benchmark set has played a significant role as a benchmark for ascertaining the accuracy of different deep neural net (DNN) models on the image classification problem. Moreover, in recent years it has also served as the principal benchmark for assessing different approaches to DNN training. Finishing a 90-epoch ImageNet-1k training with ResNet-50 on a NVIDIA M40 GPU takes 14 days. This training requires $10^{18}$1018 single precision operations in total. On the other hand, the world's current fastest supercomputer can finish $3 \times 10^{17}$3×1017 single precision operations per second (according to the Nov 2018 Top 500 results). If we can make full use of the computing capability of the fastest supercomputer, we should be able to finish the training in several seconds. Over the last two years, researchers have focused on closing this significant performance gap through scaling DNN training to larger numbers of processors. Most successful approaches to scaling ImageNet training have used the synchronous mini-batch stochastic gradient descent (SGD). However, to scale synchronous SGD one must also increase the batch size used in each iteration. Thus, for many researchers, the focus on scaling DNN training has translated into a focus on developing training algorithms that enable increasing the batch size in data-parallel synchronous SGD without losing accuracy over a fixed number of epochs. In this paper, we investigate supercomputers' capability of speeding up DNN training. Our approach is to use a large batch size, powered by the Layer-wise Adaptive Rate Scaling (LARS) algorithm, for efficient usage of massive computing resources. Our approach is generic, as we empirically evaluate the effectiveness on five neural networks: AlexNet, AlexNet-BN, GNMT, ResNet-50, and ResNet-50-v2 trained with large datasets while preserving the state-of-the-art test accuracy. Compared to the baseline of a previous study from Goyal et al. [1] , our approach shows higher test accuracy on batch sizes that are larger than 16K. When we use the same baseline, our results are better than Goyal et al. for all the batch sizes (Fig. 20). Using 2,048 Intel Xeon Platinum 8160 processors, we reduce the 100-epoch AlexNet training time from hours to 11 minutes. With 2,048 Intel Xeon Phi 7250 Processors, we reduce the 90-epoch ResNet-50 training time from hours to 20 minutes. Our implementation is open source and has been released in the Intel distribution of Caffe, Facebook's PyTorch, and Google's TensorFlow. The difference between this paper and the conference-version of our work [2] includes: (1) we implement our approach on Google's cloud Tensor Processing Unit (TPU) platform, which verifies our previous success on CPUs and GPUs. (2) we scale the batch size of ResNet-50-v2 to 32K and achieve 76.3 percent accuracy, which is better than the 75.3 percent accuracy achieved in our conference paper. (3) we apply our approach to Google's Neural Machine Translation (GNMT) application, which helps us to achieves 4× speedup on the cloud TPUs. [ABSTRACT FROM AUTHOR]

This report describes The University of Texas Student Cluster Competition team’s effort to reproduce the results of “MemXCT: memory-centric X-ray CT reconstruction with massive parallelization” (Hidayetoğlu et al., 2019). The article details a new memory-centric approach that reconstructs X-ray computed tomography (XCT) from noisy raw data. In our reproduction experiments, we utilized Microsoft Azure’s CycleCloud tool to provision, orchestrate, and manage our computing cluster in the cloud. In particular, we scheduled and benchmarked reconstruction workloads using Azure’s CPU-based HC44rs and GPU-based NC12s v2 virtual machine (VM) types to evaluate the scalability properties of the reconstruction approach and the performance differences between architectures. The HC44rs VMs contained 44 Intel Xeon Platinum cores, while the NC12s v2 VM was equipped with two NVIDIA P100 GPUs. We used a recent version of Intel’s compiler stack with the MKL library for our CPU code along with CUDA 11.1 on GPUs. Overall, our results confirm the findings of the original article, demonstrating similar acceleration on GPUs and scalability properties on CPUs. Digital artifacts from these experiments are available at: 10.5281/zenodo.5598108 [ABSTRACT FROM AUTHOR]

This special section focuses on the state-of-the-art technologies on parallel and distributed computing techniques for artificial intelligence (AI), machine learning (ML), and deep learning (DL). AI, ML, and DL can enable computers the ability to learn from a large amount of data and use the learned model to optimize a complex problem or discover rules in a complicated system. AI, ML and DL can be applied to push forward the boundaries for many domains and significantly influence our daily life. [ABSTRACT FROM AUTHOR]

In this technical report, we focus on reproducing the results reported in the paper “MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization” [1]. MemXCT is a scalable approach to X-ray Computed Tomography reconstruction which removes redundant computation. We reproduced the single CPU/GPU performance as well as strong scaling experiments. We set up our configurations on Microsoft Azure CycleCloud and have two clusters. One cluster has 4 nodes with 60 CPUs on each node and the other cluster has 4 nodes with 4 NVIDIA V100 GPUs on each node. Both clusters come with InfiniBand. The original author conducted his experiments on Theta and Blue Waters supercomputers. We were able to reproduce part of the results in the original paper, however, failed to produce similar performance on other experiments. This report was submitted as part of the reproducibility challenge in SC20 Student Cluster Competition. Digital artifacts from these experiments are available at: 10.5281/zenodo.5598108. [ABSTRACT FROM AUTHOR]

This paper presents F2C, a cooperative resource management system for Infrastructure-as-a-Service (IaaS) clouds. Inspired by group-buying mechanisms in real product and service markets, F2C advocates a group of cloud tenants (called tenant coalition) to buy resource capacity in bulk and share the resource pool in the form of virtual machines (VMs). Tenant coalitions leads to vast opportunities for fine-grained resource sharing among multiple tenants. However, resource sharing, especially for multiple resource types, poses several challenging problems in pay-as-you-use cloud environments, such as sharing incentive, free-riding, lying and economic fairness. To address those problems, we propose Reciprocal Resource Fairness (RRF) , a novel resource allocation mechanism to enable fair sharing on multiple resource types within a tenant coalition. RRF is implemented in two complementary and hierarchical mechanisms: inter-tenant resource trading and intra-tenant weight adjustment. RRF satisfies several highly desirable properties to ensure fairness. We implement F2C in Xen platform. The experimental results show F2C is promising for both cloud providers and tenants. For cloud providers, F2C improves VM density and cloud providers’ revenue by 2.2X compared to the current IaaS cloud models. For tenants, F2C improves application performance by 45 percent and guarantees 95 percent economic fairness among multiple tenants. [ABSTRACT FROM PUBLISHER]

Hundreds of papers on job scheduling for distributed systems are published every year and it becomes increasingly difficult to classify them. Our analysis revealed that half of these papers are barely cited. This paper presents a general taxonomy for scheduling problems and solutions in distributed systems. This taxonomy was used to classify and make publicly available the classification of $109$ scheduling problems and their solutions. These $109$ problems were further clustered into ten groups based on the features of the taxonomy. The proposed taxonomy will facilitate researchers to build on prior art, increase new research visibility, and minimize redundant effort. [ABSTRACT FROM PUBLISHER]

This report analyzes the reproducibility of the paper “MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization” by Hidayetoğlu et al. in the cloud as part of the SC20 Virtual Student Cluster Competition (VSCC). To reproduce the results from the original work, the ETH Zürich SC20 VSCC team performed a series of CT reconstructions and performed a scaling study using three provided sinograms. All experimental runs were performed during the SC20 VSCC on an HPC cluster hosted in the Microsoft Azure CycleCloud. In this paper, we describe discrepancies in results as a factor of the differences in experiment environments and insufficient parameter tuning. We successfully reproduce the single device performance and partially reproduce the strong scaling behavior. Digital artifacts from these experiments are available at: 10.5281/zenodo.5598108. [ABSTRACT FROM AUTHOR]

Hidayetoğlu et al. propose a novel memory-centric algorithm to reconstruct X-ray CT images in the SC19 article entitled “MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization”. They formulate the reconstruction with several SpMVs, and propose two memory-centric optimizations to improve cache locality for better memory bandwidth utilization, i.e., a two-level pseudo-Hilbert ordering and a multi-stage input buffering. In this article, we present our results on reproducing that article to show its effectiveness and generality, as part of the SC20 Student Cluster Competition Reproducibility Challenge. We reproduce the execution time and memory bandwidth tests in that article on various architectures, including Intel CPUs, AMD CPUs, and NVIDIA GPUs. We further analyze the bottleneck on different architectures by comparing the achieved memory bandwidth with the peak bandwidth on those architectures. We then reproduce the strong scaling test on CPU and GPU clusters with different scales, and use the proposed algorithm to reconstruct three new X-ray computed tomograms. [ABSTRACT FROM AUTHOR]

One of the tasks for the SC19 Student Cluster Competition is to reproduce the results in the reproducibility challenge article “Computing Planetary Interior Normal Modes with a Highly Parallel Polynomial Filtering Eigensolver”, by J. Shi et al., which describes a highly parallel algorithm for computing planetary normal modes. In running experiments from the article, we study the weak and strong scalability of the algorithm, as well as the relationship between model size, degree of polynomial filter, and execution time. We investigate these findings on a two-node, 64-core Intel Skylake-based Xeon cluster. Unfortunately, we are able to confirm some, but not all, of the original findings, with discrepancies possibly due to a low number of experimental runs due to competition time limits as well as nonuniform scaling of compute resources. [ABSTRACT FROM AUTHOR]

In this special section we bring you a practice and experience effort in reproducibility for large-scale computational science at SC20. This section includes nine critiques, each by a student team that reproduced results from a paper published at SC19, during the following year’s Student Cluster Competition. The paper is also included in this section and has been expanded upon, now including an analysis of the outcomes of the students’ reproducibility experiments. Lastly, this special section encapsulates a variety of advances in reproducibility in the SC conference series technical program. [ABSTRACT FROM AUTHOR]

The article presents the discussion on exploring new foundational and translational research towards enabling exascale computing for emerging scientific and societal challenges. Topics include high-performance computing (HPC) simulations, artificial intelligence (AI), and extreme data-driven computing; and advances in applications, programming environments, runtimes, libraries, innovative algorithms, domain-specific frameworks, and systems architecture.

This article reproduces the results of the Supercomputing 2019 article, MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization by Hidayetoğlu et al. as part of the Supercomputing 2020 Student Cluster Competition Reproducibility Challenge. We reproduce the single CPU-GPU performance experiments and the strong scaling experiments and compare the results to the original article. Although we are not able to use the exact HPC system from the original article, we use similar hardware and configurations to recreate the original environment in Microsoft Azure Cloud services. We were not able to demonstrate exact performance characteristics from the original article due to hardware limitations in our environment, but we are able to reproduce similar performance trends for both single-node and scaling experiments. [ABSTRACT FROM AUTHOR]

The papers in this special section present the state-of-the-art technologies and the challenges of parallel and distributed computing techniques for artificial intelligence (AI), machine learning (ML), and deep learning (DL). AI, ML, and DL have established themselves in a multitude of domains because of their ability to process and model unstructured input data. [ABSTRACT FROM AUTHOR]

Unreliable failure detectors are abstract devices that, when added to asynchronous distributed systems, enable solving distributed computing problems (e.g., Consensus) that otherwise would be impossible to solve in these systems. This paper focuses on two classes of failure detectors defined by Chandra and Toueg, namely, the classes denoted ◇P (eventually perfect) and ◇S (eventually strong). Both classes include failure detectors that eventually detect permanently all process crashes, but while the failure detectors of ◇P eventually make no erroneous suspicions, the failure detectors of ◇S are only required to eventually not suspect a single correct process. Informally, in a one-shot agreement problem, a new problem instance is created each time the processes propose new values to be decided on (e.g. Consensus is one-shot). In such a context, this paper addresses the following question related to the comparative power of these classes, namely: ‘Are there one-shot agreement problems that can be solved in asynchronous distributed systems with reliable links but prone to process crash failures augmented with ◇P, but cannot be solved when those systems are augmented with ◇S?’ Surprisingly, the paper shows that the answer to this question is ‘no.’ An important consequence of this result is that ◇P cannot be the weakest class of failure detectors that enables' solving one-shot agreement problems in unreliable asynchronous distributed systems. [ABSTRACT FROM AUTHOR]

The author provides updates to the January 2008 issue of the journal. He relates that the time of publication of a paper has been cut down from 26 months to 18 months, which includes reviews, minor/major revisions and time to print after a paper is accepted. He also mentions that the journal is taking steps to post the accepted papers electronically ahead of the paper print, and that reprint will be available on the Computer Society Digital Library within one week of the receipt.

An introduction to the journal is presented in which the editor discusses various reports within the issue on topics including trustworthy operations for cellular networks, content leakage during video streaming, and trustworthy service evaluation .

The article invites authors to submit papers related to security, trust, and privacy of developing parallel and distributed systems and also presents guidelines for submission.

This report analyzes the reproducibility of the article “Computing Planetary Interior Normal Modes with A Highly Parallel Polynomial Filtering Eigensolver” by Jia Shi et al. (Shi, 2018). To reproduce the results we perform different weak and strong scaling studies using a series of Mars models. All experimental runs were performed during the SC19 Student Cluster Competition on a four node Intel Skylake cluster. We show that the findings of the original article can be reproduced in a different environment. [ABSTRACT FROM AUTHOR]

In this article we present our results from the SC19 Student Cluster Competition Reproducibility Challenge. The challenge entails reproducing the article entitled “Computing Planetary Interior Normal Modes with A Highly Parallel Polynomial Filtering Eigensolver” presented at SC’18, which proposes a parallel polynomial filtered Lanczos algorithm to directly calculate the planetary normal modes of heterogeneous planets. The proposed algorithm showed excellent performance with relatively low memory consumption and high parallel efficiency. In this work, we reproduce the scaling tests in that article on a cluster using Intel Cascade Lake architecture and use the proposed algorithm to illustrate specific normal modes of Mars. We compare the results obtained on our cluster with those in the original article. We also design a new metric to better analyze the results. In addition, we use the profiling tool Intel VTune Amplifier to explain our discoveries. Our results demonstrate that the given models show great scalability, which is similar to the original article. The required normal modes of Mars are also successfully calculated and visualized. [ABSTRACT FROM AUTHOR]

For the 2020 Student Cluster Competition, we reproduced results from “MemXCT: Memory-Centric X-ray CT Reconstruction with Massive Parallelization” (Hidayetoğlu et al.). Reproducibility is of critical importance to the scientific community, not just to verify correctness of results but also to see how easily others can understand and work with the given methods. MemXCT is an approach for image reconstruction in X-ray ptychography, which has a broad range of applications in materials science. MemXCT is not the only X-ray tomography algorithm, though; as opposed to compute-centric algorithms, it is designed to scale better by optimizing for memory bandwidth and memory latency. MemXCT also applies several key optimizations in order to ease memory pressure. In this article, we test the performance and strong scaling of MemXCT on 1 to 256 AMD CPU cores (1-4 nodes) and 1-16 Nvidia V100 GPUs (1-4 nodes). We confirm the impact of MemXCT’s optimizations. Still, we find that the performance of some important loops in the MemXCT kernel is much lower on the AMD processors (with AVX2) of our CPU nodes compared to the Intel CPUs (with AVX-512) used in the original article. We also confirm MemXCT performance on Tesla V100 GPUs, as reported in the article. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various articles within the issue on topics including cloud computing service implementation, resource allocation for cloud computing and protection of the confidentiality of customer data.

The paper surveys the state of the art of task scheduling in Desktop Grid computing systems. We describe the general architecture of a Desktop Grid system and the computing model adopted by the BOINC middleware. We summarize research papers to bring together and examine the optimization criteria and methods proposed by researchers so far for improving Desktop Grid task scheduling (assigning tasks to computing nodes by a server). In addition, we review related papers, which address non-regular architectures, like hierarchical and peer-to-peer Desktop Grids, as well as Desktop Grids designed for solving interdependent tasks. [ABSTRACT FROM AUTHOR]

Non-volatile memory express (NVMe) solid-state drives (SSDs) have been widely adopted in multi-tenant cloud computing environments or multi-programming systems. The on-board DRAM cache inside NVMe SSDs can efficiently reduce the disk accesses and extend the lifetime of SSDs. Current SSD cache management research either improves cache hit ratio while ignoring fairness, or improves fairness while sacrificing overall performance. In this paper, we present MLCache, a space-efficient shared cache management scheme for NVMe SSDs. By learning the impact of reuse distance on cache allocation, a workload-generic neural network model is built. At runtime, MLCache continuously monitors the reuse distance distribution for the neural network module to obtain space-efficient allocation decisions. MLCache also proposes an efficient parallel writing back strategy based on hit ratio and response time, to improve fairness. Experimental results show MLCache improves the write hit ratio when compared to baseline, and MLCache strongly safeguards the fairness of SSDs with parallel write-back and maintains a low level of degradation. [ABSTRACT FROM AUTHOR]

The tridiagonal solver is an important kernel and is widely supported in mainstream numerical libraries. While parallel algorithms have been studied for many-core architectures, the performance of current algorithms and implementations is still hindered by input size sensitivity and cross-platform portability. In this paper, we propose a novel algorithm WM-pGE for the batched solution of diagonally dominant tridiagonal systems. The algorithm balances the key design objectives, including computation complexity, memory complexity, parallelism, and input size sensitivity, better than existing algorithms. Moreover, an elegant formulation is presented to show the implementation and cross-platform optimization without loss of efficiency and generality, by extracting the platform-dependent works into only four vector operators. The results from our batched tridiagonal experiments show that the proposed algorithm outperforms the prior work PCR-pThomas by 25% and 12% on NVIDIA Tesla V100 in single and double precision, respectively. On Intel KNL, our method achieves a 10% improvement in performance over PCR-pThomas in double precision. [ABSTRACT FROM AUTHOR]

Once started, existing hash tables cannot change their pre-defined hash functions, even if the incoming data cannot be evenly distributed to the hash table buckets. In this paper, we present DHash, a type of hash table for shared memory systems, that can change its hash function and rebuild the hash table on the fly, without noticeably degrading its service. The major technical novelty of DHash stems from an efficient distributing mechanism that can atomically distribute every node when rebuilding, without locking the corresponding hash table buckets. This not only enables non-blocking lookup, insert, and delete operations, but more importantly, makes DHash independent of the implementation of hash table buckets, such that DHash allows programmers to select the set algorithms that meet their requirements best from a variety of existing lock-free and wait-free set algorithms. Evaluations show that DHash can efficiently change its hash function on the fly. Moreover, when rebuilding, DHash consistently outperforms the state-of-the-art hash tables in terms of throughput and response time of concurrent operations, at different concurrency levels, and with different operation mixes and average load factors. [ABSTRACT FROM AUTHOR]

The interconnection network comprises a significant portion of the cost of large parallel computers, both in economic terms and power consumption. Several previous proposals exploit large-radix routers to build scalable low-distance topologies with the aim of minimizing these costs. However, they fail to consider potential unbalance in the network utilization, which in some cases results in suboptimal designs. Based on an appropriate cost model, this paper advocates the use of networks based on incidence graphs of projective planes, broadly denoted as Projective Networks. Projective Networks rely on generalized Moore graphs with uniform link utilization and encompass several proposed direct (PN and demi-PN) and indirect (OFT) topologies under a common mathematical framework. Compared to other proposals with average distance between 2 and 3 hops, these networks provide very high scalability while preserving a balanced network utilization, resulting in low network costs. [ABSTRACT FROM PUBLISHER]

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]

The ongoing digitalization enables stable control processes and smooth operations of Industrial Control Systems (ICSs). A direct consequence of the highly interconnected architecture of ICSs is the introduced cyber vulnerability and increasing cyber security threats to ICSs. Numerous researches pay attention to the security problem of ICSs. However, most current studies face two challenges. First, the interaction problem between the cyber layer and the physical layer of ICSs may result in incorrect attack response strategies. Second, ICSs are real-time systems, but existing defense decision algorithms based on game theory or reinforcement learning techniques have high computational complexity, which prevents them from making decisions quickly. In this paper, we design a new multi-attribute based method for quantifying rewards and propose a multi-attribute based Q-learning algorithm to resolve the interaction problem. In addition, to overcome the limitation of slow convergence, we develop an effective parallel Q-learning (PQL) algorithm to quickly find the optimal strategy. The experimental results show the effectiveness of the PQL algorithm. Compared with the Q-learning algorithm (QL) and the deep Q-network (DQN) algorithm, our proposed solution can reduce the average completion time by 12.5 to 37 percent. [ABSTRACT FROM AUTHOR]

The article presents the profiles of the new members of the editorial board as well as the editorial changes incorporated to the journal "IEEE Transactions on Parallel and Distributed Systems," Volume 21. It highlights the pursuit of the individuals behind the journal to improve their quality and impact factor by encouraging the submission of short papers and survey papers. The brief backgrounds of its new editorial board members including Yiming Hu, Keqin Li, and Amiya Nayak are also provided.

To support their massively-multithreaded architecture, GPUs use very large register file (RF) which has a capacity higher than even L1 and L2 caches. In total contrast, traditional CPUs use tiny RF and much larger caches to optimize latency. Due to these differences, along with the crucial impact of RF in determining GPU performance, novel and intelligent techniques are required for managing GPU RF. In this paper, we survey the techniques for designing and managing GPU RF. We discuss techniques related to performance, energy and reliability aspects of RF. To emphasize the similarities and differences between the techniques, we classify them along several parameters. The aim of this paper is to synthesize the state-of-art developments in RF management and also stimulate further research in this area. [ABSTRACT FROM PUBLISHER]

Analysis of reliability, power, and performance at hardware and software levels due to heterogeneity is a crucial requirement for heterogeneous multicore embedded systems. Escalating power densities have led to thermal issues for heterogeneous multicore embedded systems. This paper proposes a peak-power-aware reliability management scheme to meet power constraints through distributing power density on the whole chip such that reliability targets are satisfied. In this paper, we consider peak power consumption as a system-level power constraint to prevent system failure. To balance the power consumption, we also employ a Dynamic Frequency Scaling (DFS) method to further reduce peak power consumption and satisfy thermal constraints on the chip. We illustrate the benefits of our scheme by comparing it with state-of-the-art schemes, resulting in average in 26.5 percent less peak power consumption (up to 54.3 percent). [ABSTRACT FROM AUTHOR]

Proliferation of virtualized systems opens a new opportunity to improve the scalability of multi-core architectures. Among the scalability bottlenecks in multi-cores, cache coherence has been one of the most critical problems. Although snoop-based protocols have been dominating commercial multi-core designs, it has been difficult to scale them for more cores, as snooping protocols require high network bandwidth and power consumption for snooping all the caches.In this paper, we propose a novel snoop-based cache coherence protocol, called virtual snooping, for virtualized multi-core architectures. Virtual snooping exploits memory isolation across virtual machines and prevents unnecessary snoop requests from crossing the virtual machine boundaries. Each virtual machine becomes a virtual snoop domain, consisting of a subset of the cores in a system. Although the majority of virtual machine memory is isolated, sharing of cachelines across VMs still occur. To address such data sharing, this paper investigates three factors, data sharing through the hypervisor, virtual machine relocation, and content-based sharing. In this paper, we explore the design space of virtual snooping with experiments on emulated and real virtualized systems including the mechanisms and overheads of the hypervisor. In addition, the paper discusses the scheduling impact on the effectiveness of virtual snooping. [ABSTRACT FROM AUTHOR]

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]

Optimal resource provisioning is essential for scalable big data analytics. However, it has been difficult to accurately forecast the resource requirements before the actual deployment of these applications as their resource requirements are heavily application and data dependent. This paper identifies the existence of effective memory resource requirements for most of the big data analytic applications running inside JVMs in distributed Spark environments. Provisioning memory less than the effective memory requirement may result in rapid deterioration of the application execution in terms of its total execution time. A machine learning-based prediction model is proposed in this paper to forecast the effective memory requirement of an application given its service level agreement. This model captures the memory consumption behavior of big data applications and the dynamics of memory utilization in a distributed cluster environment. With an accurate prediction of the effective memory requirement, it is shown that up to 60 percent savings of the memory resource is feasible if an execution time penalty of 10 percent is acceptable. The accuracy of the model is evaluated on a physical Spark cluster with 128 cores and 1TB of total memory. The experiment results show that the proposed solution can predict the minimum required memory size for given acceptable delays with high accuracy, even if the behavior of target applications is unknown during the training of the model. [ABSTRACT FROM AUTHOR]

The Internet of Things (IoT) technology provisions unprecedented opportunities to evolve the interconnection among human beings. However, the latency brought by unstable wireless networks and computation failures caused by limited resources on IoT devices prevents users from experiencing high efficiency and seamless user experience. To address these shortcomings, the integrated Mobile Edge Computing (MEC) with remote clouds is a promising platform to enable delay-sensitive service provisioning for IoT applications, where edge-clouds (cloudlets) are co-located with wireless access points in the proximity of IoT devices. Thus, computation-intensive and sensing data from IoT devices can be offloaded to the MEC network immediately for processing, and the service response latency can be significantly reduced. In this paper, we first formulate two novel optimization problems for delay-sensitive IoT applications, i.e., the total utility maximization problems under both static and dynamic offloading task request settings, with the aim to maximize the accumulative user satisfaction on the use of the services provided by the MEC, and show the NP-hardness of the defined problems. We then devise efficient approximation and online algorithms with provable performance guarantees for the problems in a special case where the bandwidth capacity constraint is negligible. We also develop efficient heuristic algorithms for the problems with the bandwidth capacity constraint. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are promising in reducing service delays and enhancing user satisfaction, and the proposed algorithms outperform their counterparts by at least 10.8 percent. [ABSTRACT FROM AUTHOR]

Delay-tolerant networks (DTNs) are a promising network architecture which can provide reliable multi-hop message transmission between participating mobile nodes in an unfavorable environment that is prone to link disruption and disconnection by replicating and relaying messages without any need of physical infrastructure. Additionally, DTNs can also operate as cooperative DTNs to extend the coverage of other type of networks by carrying the messages that originate from farther away base station in a multi-hop fashion to the base station. In this paper, we focus on these cooperative DTNs and propose a novel routing scheme, ring distribution routing (RDR), that controls the replication and forwarding based on the source node surroundings. This paper also analyzes the reliability and buffer efficiency in RDR. Furthermore, we show that RDR provides the reliable and immediate message delivery in any environment through extensive computer simulations. [ABSTRACT FROM AUTHOR]

There are plenty of idle computational resources on the Internet, which could potentially be used for accomplishing huge tasks. More and more applications are being designed for exploring those idle resources. In this paper, we focus on the idle computational resources, including both human intelligence and machine computing abilities, in mobile social networks (MSNs). Based on the unique features of MSN, we design a new cooperative system, called social-crowdsourcing. The distributed and infrastructure-free features of the system make it more attractive than traditional crowdsourcing platforms. In the proposed system, a huge work is gradually partitioned into smaller pieces, and is propagated from node to node. However, how to partition and allocate these segments is a critical problem, which directly affects the work’s completion time and system throughput. Due to the lack of global information, independent relay nodes are likely to make conflicted decisions, which will cause an unbalanced workload distribution on participating nodes. In this paper, we find that, for a work at different processing stages, one should adopt distinct workload exchanging schemes, moving from a progressive method to a conservative one. Based on this observation, we propose an adaptive workload allocation scheme, in which a participating node can gradually switch his decision strategy according to the workload statuses of neighboring nodes. By using our approach, system throughput can be significantly improved, and large works can finish within a nearly optimal time. Unlike in traditional scheduling problems, we take a human’s rejection, contact delay, and social similarity into consideration. Extensive simulation results show that our proposed algorithms can successfully make full use of the idle resources in MSNs. [ABSTRACT FROM PUBLISHER]

Shi et al. (2018) proposed a highly parallel polynomial filtering eigensolver for the computation of planetary normal modes. As a challenge at the Student Cluster Competition in The International Conference for High Performance Computing, Networking, Storage and Analysis (SC19), we reproduce the computational efficiency of the polynomial filtering eigensolver on our Intel Xeon machine. We present the weak scalability, scaling of runtime with model size (in a fixed interval) and the strong scalability results in this report. [ABSTRACT FROM AUTHOR]

Brain modeling has been receiving significant attention over the years, both for its neuroscientific potential and for its challenges in the context of high-performance computing. The development of physiologically plausible neuron models comes at the cost of increased complexity. In this work, we have selected a highly computationally demanding model of the Inferior-Olivary Nucleus (InfOli) based on the Hodgkin-Huxley (HH) neuron model. This brain region, functionally coupled with the cerebellum, is of vital importance for motor skills and time-sensitive cognitive functions. The computing fabric of choice is an Intel Xeon/Xeon Phi system, which is a typical node of modern computing infrastructure. The target application is parallelized with various combinations of MPI and OpenMP and performance is measured on the target platform. The different implementations are compared and the best one is chosen. Further optimization of this implementation is presented in detail. Its behaviour is then examined when scaling up to neuron populations representative of realistic, human Inferior-Olivary neuronal networks. The evaluation’s results highlight the importance of examining a network’s size and density before choosing the best platform for its simulation. All the parallelization and vectorization options presented in the current paper are available on a public repository for further examination. [ABSTRACT FROM AUTHOR]

Multi-Processor Systems-on-Chip (MPSoCs) have emerged as an evolution trend to meet the growing complexity of embedded applications with increasing computation parallelism. Particularly, real-time applications make out a significant portion of the embedded field. Networks-on-Chip (NoCs) are the backbone of communications in an MPSoC platform. However, the use of NoCs in real-time systems imposes complex constraints on the overall design. This paper discusses the challenges faced, when designing NoCs for real-time applications. Contributions in this area are surveyed on the level of guaranteed Quality-of-Service (QoS) support, adaptivity, and energy efficient techniques. Furthermore, the evaluation methodologies and experimental performance measurements of real-time NoCs are examined. This survey provides a comprehensive overview of existing endeavors in real-time NoCs and gives an insight towards future promising research points in this field. [ABSTRACT FROM AUTHOR]

Graph coloring—in a generic sense—is used to identify subsets of independent tasks in parallel scientific computing applications. Traditional coloring heuristics aim to reduce the number of colors used as that number also corresponds to the number of parallel steps in the application. However, if the color classes produced have a skew in their sizes, utilization of hardware resources becomes inefficient, especially for the smaller color classes. Equitable coloring is a theoretical formulation of coloring that guarantees a perfect balance among color classes, and its practical relaxation is referred to here as balanced coloring. In this paper, we consider balanced coloring models in the context of parallel computing. The goal is to achieve a balanced coloring of an input graph without increasing the number of colors that an algorithm oblivious to balance would have used. We propose and study multiple heuristics that aim to achieve such a balanced coloring for two variants of coloring problem, distance-1 coloring (the standard coloring problem) and partial distance-2 coloring (defined on a bipartite graph). We present parallelization approaches for multi-core and manycore architectures and cross-evaluate their effectiveness with respect to the quality of balance achieved and performance. Furthermore, we study the impact of the proposed balanced coloring heuristics on a concrete application-viz. parallel community detection, which is an example of an irregular application. In addition, we propose several extensions to our basic balancing schemes and evaluate their balancing efficacy and performance characteristics. The thorough treatment of balanced coloring presented in this paper from algorithms to application is expected to serve as a valuable resource to parallel application developers who seek to improve parallel performance of their applications using coloring. [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]

Group services are highly important for a variety of computing application domains. In this paper, we study the fundamental problem of allocating a set of service patrons to a set of service groups in an attempt to maximize the total profit gained by the grouping platform. The problem under consideration is unique in that group service is not provided at all unless its lower bound requirement is satisfied. In addition, we allow each service patron to join multiple groups. In this paper, after proving the hardness property of the problem, we focus first on a special case of the problem. To this end, we propose two approaches. One aims at providing a suboptimal solution using a 1/2-approximation algorithm. The other approach turns to seeking an optimal solution using a branch and bound technique. For this purpose, we introduce a theorem that captures a useful property of an optimal allocation. Based on this theorem, we design an efficient branch and bound algorithm to find an optimal solution. We then extend these methods to solve the general problem. Extensive experiments show that our branch and bound algorithm is able to obtain an optimal solution with a small amount of computation time in many different settings. [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]

An editorial is presented on advancing reproducibility in parallel and distributed systems research. Topics include reproducibility is foundational to solid scientific and technical research and responding to the recommendations of the National Academies; and Transactions on Parallel and Distributed Systems (TPDS) is committed to enabling reproducible research through transparency and the availability and potential reuse of code and data.

The study of atmospheric chemistry-climate interactions is one of today's great computational challenges. Advances in the architecture of Graphics Processing Units (GPUs) in both raw computational power and memory bandwidth sparked the interest for General-Purpose computing on graphics accelerators in scientific applications. However, the introduction of GPUs in the High Performance Computing (HPC) landscape increased the complexity of software development, due to the inherent heterogeneity requirements of programming models and design approaches, creating a gap in uptake and attainable performance in the presently available scientific community codes. This paper provides an overview of the challenges encountered when using GPU accelerators to achieve optimal performance to calculate the kinetics of chemical tracers in climate models, the techniques used to address them and the insights gained from the process. The paper presents the development of a chemical kinetics code-to-code parser to automatically generate chemical kinetics calculations on three different generations of GPU accelerators (M2070, K80, and P100). The accelerated portion of the application achieves a speedup of up to 22×, equivalent to performance gains of +19 percent up to +90 percent compared with the processor-only version, when using a cluster of 8 Nodes with dual Intel E5-2680 v3 processor and a Kepler architecture (K80), allowing faster completion of the simulations. The paper also provides practical insights and relevant considerations for the development and acceleration of complex applications. [ABSTRACT FROM AUTHOR]

Heterogenerous multi-cores utilize the strength of different architectures for executing particular types of workload, and usually offer higher performance and energy efficiency. In this paper, we study the worst-case response time (WCRT) analysis of typed scheduling of parallel DAG tasks on heterogeneous multi-cores, where the workload of each vertex in the DAG is only allowed to execute on a particular type of cores. The only known WCRT bound for this problem is grossly pessimistic and suffers the non-self-sustainability problem. In this paper, we propose two new WCRT bounds. The first new bound has the same time complexity as the existing bound, but is more precise and solves its non-self-sustainability problem. The second new bound explores more detailed task graph structure information to greatly improve the precision, but is computationally more expensive. We prove that the problem of computing the second bound is strongly NP-hard if the number of types in the system is a variable, and develop an efficient algorithm which has polynomial time complexity if the number of types is a constant. Experiments with randomly generated workload show that our proposed new methods are more precise than the existing bound while having good scalability. [ABSTRACT FROM AUTHOR]