Search

The proliferation of GPUs and accelerators in recent supercomputing systems,so called heterogeneous architectures, has led to increased complexity inexecution environments and programming models as well as to deeper memoryhierarchies on these systems. In this work, we discuss challenges that arise inin situ code coupling on these heterogeneous architectures. In particular, wepresent data and execution model extensions to the SENSEI in situ frameworkthat are targeted at the effective use of systems with heterogeneousarchitectures. We then use these new data and execution model extensions toinvestigate several in situ placement and execution configurations and toanalyze the impact these choices have on overall performance.

Conflict-free replicated data types (CRDTs) are a promising tool fordesigning scalable, coordination-free distributed systems. However,constructing correct CRDTs is difficult, posing a challenge for even seasoneddevelopers. As a result, CRDT development is still largely the domain ofacademics, with new designs often awaiting peer review and a manual proof ofcorrectness. In this paper, we present Katara, a program synthesis-based systemthat takes sequential data type implementations and automatically synthesizesverified CRDT designs from them. Key to this process is a new formal definitionof CRDT correctness that combines a reference sequential type with alightweight ordering constraint that resolves conflicts between non-commutativeoperations. Our process follows the tradition of work in verified lifting,including an encoding of correctness into SMT logic using synthesized inductiveinvariants and hand-crafted grammars for the CRDT state and runtime. Katara isable to automatically synthesize CRDTs for a wide variety of scenarios, fromreproducing classic CRDTs to synthesizing novel designs based on specificationsin existing literature. Crucially, our synthesized CRDTs are fully,automatically verified, eliminating entire classes of common errors andreducing the process of producing a new CRDT from a painstaking paper proof ofcorrectness to a lightweight specification.

The upcoming exascale computing systems Frontier and Aurora will draw much oftheir computing power from GPU accelerators. The hardware for these systemswill be provided by AMD and Intel, respectively, each supporting their own GPUprogramming model. The challenge for applications that harness one of theseexascale systems will be to avoid lock-in and to preserve performanceportability. We report here on our results of using Kokkos to accelerate a real-worldapplication on NERSC's Perlmutter Phase 1 (using NVIDIA A100 accelerators) andthe testbed system for OLCF's Frontier (using AMD MI250X). By porting toKokkos, we were able to successfully run the same X-ray tracing code on bothsystems and achieved speed-ups between 13% and 66% compared to the originalCUDA code. These results are a highly encouraging demonstration of using Kokkosto accelerate production science code.

High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs because of three challenges: (1) the difficulty of coming up with graph building blocks, (2) load imbalance on parallel hardware, and (3) graph problems having low arithmetic intensity. To address some of these challenges, GraphBLAS is an innovative, on-going effort by the graph analytics community to propose building blocks based on sparse linear algebra, which allow graph algorithms to be expressed in a performant, succinct, composable, and portable manner. In this paper, we examine the performance challenges of a linear-algebra-based approach to building graph frameworks and describe new design principles for overcoming these bottlenecks. Among the new design principles is exploiting input sparsity, which allows users to write graph algorithms without specifying push and pull direction. Exploiting output sparsity allows users to tell the backend which values of the output in a single vectorized computation they do not want computed. Load-balancing is an important feature for balancing work amongst parallel workers. We describe the important load-balancing features for handling graphs with different characteristics. The design principles described in this paper have been implemented in "GraphBLAST", the first high-performance linear algebra-based graph framework on NVIDIA GPUs that is open-source. The results show that on a single GPU, GraphBLAST has on average at least an order of magnitude speedup over previous GraphBLAS implementations SuiteSparse and GBTL, comparable performance to the fastest GPU hardwired primitives and shared-memory graph frameworks Ligra and Gunrock, and better performance than any other GPU graph framework, while offering a simpler and more concise programming model.

WarpX is a general purpose electromagnetic particle-in-cell code that was originally designed to run on many-core CPU architectures. We describe the strategy, based on the AMReX library, followed to allow WarpX to use the GPU-accelerated nodes on OLCF's Summit supercomputer, a strategy we believe will extend to the upcoming machines Frontier and Aurora. We summarize the challenges encountered, lessons learned, and give current performance results on a series of relevant benchmark problems.

The distributed matrix multiplication problem with an unknown number ofstragglers is considered, where the goal is to efficiently and flexibly obtainthe product of two massive matrices by distributing the computation across Nservers. There are up to N - R stragglers but the exact number is not known apriori. Motivated by reducing the computation load of each server, a flexiblesolution is proposed to fully utilize the computation capability of availableservers. The computing task for each server is separated into several subtasks,constructed based on Entangled Polynomial codes by Yu et al. The final resultscan be obtained from either a larger number of servers with a smaller amount ofcomputation completed per server or a smaller number of servers with a largeramount of computation completed per server. The required finite field size ofthe proposed solution is less than 2N. Moreover, the optimal design parameterssuch as the partitioning of the input matrices is discussed. Our constructionscan also be generalized to other settings such as batch distributed matrixmultiplication and secure distributed matrix multiplication.

X-ray scattering experiments using Free Electron Lasers (XFELs) are apowerful tool to determine the molecular structure and function of unknownsamples (such as COVID-19 viral proteins). XFEL experiments are a challenge tocomputing in two ways: i) due to the high cost of running XFELs, a fastturnaround time from data acquisition to data analysis is essential to makeinformed decisions on experimental protocols; ii) data collection rates aregrowing exponentially, requiring new scalable algorithms. Here we report ourexperiences analyzing data from two experiments at the Linac Coherent LightSource (LCLS) during September 2020. Raw data were analyzed on NERSC's CoriXC40 system, using the Superfacility paradigm: our workflow automatically movesraw data between LCLS and NERSC, where it is analyzed using the softwarepackage CCTBX. We achieved real time data analysis with a turnaround time fromdata acquisition to full molecular reconstruction in as little as 10 min --sufficient time for the experiment's operators to make informed decisions. Byhosting the data analysis on Cori, and by automating LCLS-NERSCinteroperability, we achieved a data analysis rate which matches the dataacquisition rate. Completing data analysis with 10 mins is a first for XFELexperiments and an important milestone if we are to keep up with datacollection trends.

The volume of data moving through a network increases with new scientific experiments and simulations. Network bandwidth requirements also increase proportionally to deliver data within a certain time frame. We observe that a significant portion of the popular dataset is transferred multiple times to different users as well as to the same user for various reasons. In-network data caching for the shared data has shown to reduce the redundant data transfers and consequently save network traffic volume. In addition, overall application performance is expected to improve with in-network caching because access to the locally cached data results in lower latency. This paper shows how much data was shared over the study period, how much network traffic volume was consequently saved, and how much the temporary in-network caching increased the scientific application performance. It also analyzes data access patterns in applications and the impacts of caching nodes on the regional data repository. From the results, we observed that the network bandwidth demand was reduced by nearly a factor of 3 over the study period.

In recent years, the increasing complexity in scientific simulations andemerging demands for training heavy artificial intelligence models requiremassive and fast data accesses, which urges high-performance computing (HPC)platforms to equip with more advanced storage infrastructures such assolid-state disks (SSDs). While SSDs offer high-performance I/O, thereliability challenges faced by the HPC applications under the SSD-relatedfailures remains unclear, in particular for failures resulting in datacorruptions. The goal of this paper is to understand the impact of SSD-relatedfaults on the behaviors of complex HPC applications. To this end, we proposeFFIS, a FUSE-based fault injection framework that systematically introducesstorage faults into the application layer to model the errors originated fromSSDs. FFIS is able to plant different I/O related faults into the data returnedfrom underlying file systems, which enables the investigation on the errorresilience characteristics of the scientific file format. We demonstrate theuse of FFIS with three representative real HPC applications, showing how eachapplication reacts to the data corruptions, and provide insights on the errorresilience of the widely adopted HDF5 file format for the HPC applications.

Maintaining computational load balance is important to the performantbehavior of codes which operate under a distributed computing model. This isespecially true for GPU architectures, which can suffer from memoryoversubscription if improperly load balanced. We present enhancements totraditional load balancing approaches and explicitly target GPU architectures,exploring the resulting performance. A key component of our enhancements is theintroduction of several GPU-amenable strategies for assessing compute work.These strategies are implemented and benchmarked to find the most optimal datacollection methodology for in-situ assessment of GPU compute work. For thefully kinetic particle-in-cell code WarpX, which supports MPI+CUDA parallelism,we investigate the performance of the improved dynamic load balancing via astrong scaling-based performance model and show that, for a laser-ionacceleration test problem run with up to 6144 GPUs on Summit, the enhanceddynamic load balancing achieves from 62%--74% (88% when running on 6 GPUs) ofthe theoretically predicted maximum speedup; for the 96-GPU case, we find thatdynamic load balancing improves performance relative to baselines without loadbalancing (3.8x speedup) and with static load balancing (1.2x speedup). Ourresults provide important insights into dynamic load balancing and performanceassessment, and are particularly relevant in the context of distributed memoryapplications ran on GPUs.

Can cloud computing infrastructures provide HPC-competitive performance for scientific applications broadly? Despite prolific related literature, this question remains open. Answers are crucial for designing future systems and democratizing high-performance computing. We present a multi-level approach to investigate the performance gap between HPC and cloud computing, isolating different variables that contribute to this gap. Our experiments are divided into (i) hardware and system microbenchmarks and (ii) user application proxies. The results show that today’s high-end cloud computing can deliver HPC-competitive performance not only for computationally intensive applications, but also for memory- and communication-intensive applications – at least at modest scales – thanks to the high-speed memory systems and interconnects and dedicated batch scheduling now available on some cloud platforms.

Can cloud computing infrastructures provide HPC-competitive performance for scientific applications broadly? Despite prolific related literature, this question remains open. Answers are crucial for designing future systems and democratizing high-performance computing. We present a multi-level approach to investigate the performance gap between HPC and cloud computing, isolating different variables that contribute to this gap. Our experiments are divided into (i) hardware and system microbenchmarks and (ii) user application proxies. The results show that today’s high-end cloud computing can deliver HPC-competitive performance not only for computationally intensive applications, but also for memory- and communication-intensive applications – at least at modest scales – thanks to the high-speed memory systems and interconnects and dedicated batch scheduling now available on some cloud platforms.

Network performance monitoring collects heterogeneous data suchas networkflow data to give an overview of network performance,and other metrics,necessary for diagnosing and optimizing servicequality. However, due todisparate and heterogeneity, to obtainmetrics and visualize entire data fromseveral devices, engineershave to log into multiple dashboards.In this paper wepresent NetGraf, a complete end-to-end networkmonitoring stack, that usesopen-source network monitoring toolsand collects, aggregates, and visualizesnetwork measurements on asingle easy-to-use real-time Grafana dashboard. Wedevelop a novelNetGraf architecture and can deploy it on any network testbedsuchas Chameleon Cloud by single easy-to-use script for a full view ofnetworkperformance in one dashboard.This paper contributes to the theme of automatingopen-sourcenetwork monitoring tools software setups and their usabilityforresearchers looking to deploy an end-to-end monitoring stack ontheir owntestbeds.

Geothermal heat, as renewable energy, shows great advantage with respect toits environmental impact due to its significantly lower CO2 emissions thanconventional fossil fuel. Open and closed-loop geothermal heat pumps, whichutilize shallow geothermal systems, are an efficient technology for cooling andheating buildings, especially in urban areas. Integrated use of geothermalenergy technologies for district heating, cooling, and thermal energy storagecan be applied to optimize the subsurface for communities to provide them withmultiple sustainable energy and community resilience benefits. The utilizationof the subsurface resources may lead to a variation in the undergroundenvironment, which might further impact local environmental conditions.However, very few simulators can handle such a highly complex set of coupledcomputations on a regional or city scale. We have developed high-performancecomputing (HPC) based hydrothermal finite element (FE) simulator that cansimulate the subsurface and its hydrothermal conditions at a scale of tens ofkm. The HPC simulator enables us to investigate the subsurface thermal andhydrologic response to the built underground environment (such as basements andsubways) at the community scale. In this study, a coupled hydrothermalsimulator is developed based on the open-source finite element library deal.II.The HPC simulator was validated by comparing the results of a benchmark casestudy against COMSOL Multiphysics, in which Aquifer Thermal Energy Storage(ATES) is modeled and a process of heat injection into ATES is simulated. Theuse of an energy pile system at the Treasure Island redevelopment site (SanFrancisco, CA, USA) was selected as a case study to demonstrate the HPCcapability of the developed simulator. The simulator is capable of modelingmultiple city-scale geothermal scenarios in a reasonable amount of time.

This paper proposes a system, entitled Concealer that allows sharingtime-varying spatial data (e.g., as produced by sensors) in encrypted form toan untrusted third-party service provider to provide location-basedapplications (involving aggregation queries over selected regions over timewindows) to users. Concealer exploits carefully selected encryption techniquesto use indexes supported by database systems and combines ways to add faketuples in order to realize an efficient system that protects against leakagebased on output-size. Thus, the design of Concealer overcomes two limitationsof existing symmetric searchable encryption (SSE) techniques: (i) it avoids theneed of specialized data structures that limit usability/practicality of SSE inlarge scale deployments, and (ii) it avoids information leakages based on theoutput-size, which may leak data distributions. Experimental results validatethe efficiency of the proposed algorithms over a spatial time-series dataset(collected from a smart space) and TPC-H datasets, each of 136 Million rows,the size of which prior approaches have not scaled to.

This article focuses on the new privacy challenges that arise in smart homes. Specifically, the article focuses on inferring the user's activities-which may, in turn, lead to the user's privacy-via inferences through device activities and network traffic analysis. We develop techniques that are based on a cryptographically secure token circulation in a ring network consisting of smart home devices to prevent inferences from device activities, via device workflow, i.e., inferences from a coordinated sequence of devices' actuation. The solution hides the device activity and corresponding channel activities, thus preserving the individual's activities. We also extend our solution to deal with a large number of devices and devices that produce large-sized data by implementing parallel rings. Our experiments also evaluate the performance in terms of communication overheads of the proposed approach and the obtained privacy.

Data outsourcing allows data owners to keep their data at \emph{untrusted}clouds that do not ensure the privacy of data and/or computations. One usefulframework for fault-tolerant data processing in a distributed fashion isMapReduce, which was developed for \emph{trusted} private clouds. This paperpresents algorithms for data outsourcing based on Shamir's secret-sharingscheme and for executing privacy-preserving SQL queries such as count,selection including range selection, projection, and join while using MapReduceas an underlying programming model. Our proposed algorithms prevent anadversary from knowing the database or the query while also preventingoutput-size and access-pattern attacks. Interestingly, our algorithms do notinvolve the database owner, which only creates and distributes secret-sharesonce, in answering any query, and hence, the database owner also cannot learnthe query. Logically and experimentally, we evaluate the efficiency of thealgorithms on the following parameters: (\textit{i}) the number ofcommunication rounds (between a user and a server), (\textit{ii}) the totalamount of bit flow (between a user and a server), and (\textit{iii}) thecomputational load at the user and the server.\B

The central importance of large-scale eigenvalue problems in scientific computation necessitates the development of massively parallel algorithms for their solution. Recent advances in dense numerical linear algebra have enabled the routine treatment of eigenvalue problems with dimensions on the order of hundreds of thousands on the world's largest supercomputers. In cases where dense treatments are not feasible, Krylov subspace methods offer an attractive alternative due to the fact that they do not require storage of the problem matrices. However, demonstration of scalability of either of these classes of eigenvalue algorithms on computing architectures capable of expressing massive parallelism is non-trivial due to communication requirements and serial bottlenecks, respectively. In this work, we introduce the SISLICE method: a parallel shift-invert algorithm for the solution of the symmetric self-consistent field (SCF) eigenvalue problem. The SISLICE method drastically reduces the communication requirement of current parallel shift-invert eigenvalue algorithms through various shift selection and migration techniques based on density of states estimation and k-means clustering, respectively. This work demonstrates the robustness and parallel performance of the SISLICE method on a representative set of SCF eigenvalue problems and outlines research directions that will be explored in future work.

In [Van Beeumen, et. al, HPC Asia 2020,https://www.doi.org/10.1145/3368474.3368497] a scalable and matrix-freeeigensolver was proposed for studying the many-body localization (MBL)transition of two-level quantum spin chain models with nearest-neighbor $XX+YY$interactions plus $Z$ terms. This type of problem is computationallychallenging because the vector space dimension grows exponentially with thephysical system size, and averaging over different configurations of the randomdisorder is needed to obtain relevant statistical behavior. For each eigenvalueproblem, eigenvalues from different regions of the spectrum and theircorresponding eigenvectors need to be computed. Traditionally, the interioreigenstates for a single eigenvalue problem are computed via theshift-and-invert Lanczos algorithm. Due to the extremely high memory footprintof the LU factorizations, this technique is not well suited for large number ofspins $L$, e.g., one needs thousands of compute nodes on modern highperformance computing infrastructures to go beyond $L = 24$. The matrix-freeapproach does not suffer from this memory bottleneck, however, its scalabilityis limited by a computation and communication imbalance. We present a fewstrategies to reduce this imbalance and to significantly enhance thescalability of the matrix-free eigensolver. To optimize the communicationperformance, we leverage the consistent space runtime, CSPACER, and show itsefficiency in accelerating the MBL irregular communication patterns at scalecompared to optimized MPI non-blocking two-sided and one-sided RMAimplementation variants. The efficiency and effectiveness of the proposedalgorithm is demonstrated by computing eigenstates on a massively parallelmany-core high performance computer.

Identifying similar protein sequences is a core step in many computational biology pipelines such as detection of homologous protein sequences, generation of similarity protein graphs for downstream analysis, functional annotation, and gene location. Performance and scalability of protein similarity search have proven to be a bottleneck in many bioinformatics pipelines due to increase in cheap and abundant sequencing data. This work presents a new distributed-memory software PASTIS. PASTIS relies on sparse matrix computations for efficient identification of possibly similar proteins. We use distributed sparse matrices for scalability and show that the sparse matrix infrastructure is a great fit for protein similarity search when coupled with a fully-distributed dictionary of sequences that allow remote sequence requests to be fulfilled. Our algorithm incorporates the unique bias in amino acid sequence substitution in search without altering basic sparse matrix model, and in turn, achieves ideal scaling up to millions of protein sequences.

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. We introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

ABSTRACT This paper presents a catalogue of optimized pointings for differential photometry of 23 779 quasars extracted from the Sloan Digital Sky Survey (SDSS) Catalogue and a Score for each indicating the quality of the Field of View (FoV) associated with that pointing. Observation of millimagnitude variability on a time-scale of minutes typically requires differential observations with reference to an ensemble of reference stars. For optimal performance, these reference stars should have similar colour and magnitude to the target quasar. In addition, the greatest quantity and quality of suitable reference stars may be found by using a telescope pointing which offsets the target object from the centre of the FoV. By comparing each quasar with the stars which appear close to it on the sky in the SDSS Catalogue, an optimum pointing can be calculated, and a figure of merit, referred to as the ‘Score’ is calculated for that pointing. Highly flexible software has been developed to enable this process to be automated and implemented in a distributed computing paradigm, which enables the creation of catalogues of pointings given a set of input targets. Applying this technique to a sample of 40 000 targets from the fourth SDSS quasar catalogue resulted in the production of pointings and Scores for 23 779 quasars based on their magnitudes in the SDSS r-band. This catalogue is a useful resource for observers planning differential photometry studies and surveys of quasars to select those which have many suitable celestial neighbours for differential photometry.

Identifying similar protein sequences is a core step in many computational biology pipelines such as detection of homologous protein sequences, generation of similarity protein graphs for downstream analysis, functional annotation, and gene location. Performance and scalability of protein similarity search have proven to be a bottleneck in many bioinformatics pipelines due to increase in cheap and abundant sequencing data. This work presents a new distributed-memory software PASTIS. PASTIS relies on sparse matrix computations for efficient identification of possibly similar proteins. We use distributed sparse matrices for scalability and show that the sparse matrix infrastructure is a great fit for protein similarity search when coupled with a fully-distributed dictionary of sequences that allow remote sequence requests to be fulfilled. Our algorithm incorporates the unique bias in amino acid sequence substitution in search without altering basic sparse matrix model, and in turn, achieves ideal scaling up to millions of protein sequences.

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. We introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

Scientific computing sometimes involves computation on sensitive data. Depending on the data and the execution environment, the HPC (high-performance computing) user or data provider may require confidentiality and/or integrity guarantees. To study the applicability of hardware-based trusted execution environments (TEEs) to enable secure scientific computing, we deeply analyze the performance impact of AMD SEV and Intel SGX for diverse HPC benchmarks including traditional scientific computing, machine learning, graph analytics, and emerging scientific computing workloads. We observe three main findings: 1) SEV requires careful memory placement on large scale NUMA machines (1×−3.4× slowdown without and 1×−1.15× slowdown with NUMA aware placement), 2) virtualization−a prerequisite for SEV−results in performance degradation for workloads with irregular memory accesses and large working sets (1×−4× slowdown compared to native execution for graph applications) and 3) SGX is inappropriate for HPC given its limited secure memory size and inflexible programming model (1.2×−126× slowdown over unsecure execution). Finally, we discuss forthcoming new TEE designs and their potential impact on scientific computing.

One of the most computationally intensive tasks in computational biology isde novo genome assembly, the decoding of the sequence of an unknown genome fromredundant and erroneous short sequences. A common assembly paradigm identifiesoverlapping sequences, simplifies their layout, and creates consensus. Despitemany algorithms developed in the literature, the efficient assembly of largegenomes is still an open problem. In this work, we introduce newdistributed-memory parallel algorithms for overlap detection and layoutsimplification steps of de novo genome assembly, and implement them in thediBELLA 2D pipeline. Our distributed memory algorithms for both overlapdetection and layout simplification are based on linear-algebra operations oversemirings using 2D distributed sparse matrices. Our layout step consists ofperforming a transitive reduction from the overlap graph to a string graph. Weprovide a detailed communication analysis of the main stages of our newalgorithms. diBELLA 2D achieves near linear scaling with over 80% parallelefficiency for the human genome, reducing the runtime for overlap detection by1.2-1.3x for the human genome and 1.5-1.9x for C. elegans compared to thestate-of-the-art. Our transitive reduction algorithm outperforms an existingdistributed-memory implementation by 10.5-13.3x for the human genome and 18-29xfor the C. elegans. Our work paves the way for efficient de novo assembly oflarge genomes using long reads in distributed memory.

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel invarious graph, scientific computing and machine learning algorithms. In thispaper, we consider SpGEMMs performed on hundreds of thousands of processorsgenerating trillions of nonzeros in the output matrix. Distributed SpGEMM atthis extreme scale faces two key challenges: (1) high communication cost and(2) inadequate memory to generate the output. We address these challenges withan integrated communication-avoiding and memory-constrained SpGEMM algorithmthat scales to 262,144 cores (more than 1 million hardware threads) and canmultiply sparse matrices of any size as long as inputs and a fraction of outputfit in the aggregated memory. As we go from 16,384 cores to 262,144 cores on aCray XC40 supercomputer, the new SpGEMM algorithm runs 10x faster whenmultiplying large-scale protein-similarity matrices.

Measurements of absolute runtime are useful as a summary of performance whenstudying parallel visualization and analysis methods on computational platformsof increasing concurrency and complexity. We can obtain even more insights bymeasuring and examining more detailed measures from hardware performancecounters, such as the number of instructions executed by an algorithmimplemented in a particular way, the amount of data moved to/from memory,memory hierarchy utilization levels via cache hit/miss ratios, and so forth.This work focuses on performance analysis on modern multi-core platforms ofthree different visualization and analysis kernels that are implemented indifferent ways: one is "traditional", using combinations of C++ and VTK, andthe other uses a data-parallel approach using VTK-m. Our performance studyconsists of measurement and reporting of several different hardware performancecounters on two different multi-core CPU platforms. The results revealinteresting performance differences between these two different approaches forimplementing these kernels, results that would not be apparent using runtime asthe only metric.

A secure multi-party batch matrix multiplication problem (SMBMM) is considered, where the goal is to allow a master to efficiently compute the pairwise products of two batches of massive matrices, by distributing the computation across S servers. Any X colluding servers gain no information about the input, and the master gains no additional information about the input beyond the product. A solution called Generalized Cross Subspace Alignment codes with Noise Alignment (GCSA- NA) is proposed in this work, based on cross-subspace alignment codes. The state of art solution to SMBMM is a coding scheme called polynomial sharing (PS) that was proposed by Nodehi and Maddah-Ali. GCSA-NA outperforms PS codes in several key aspects - more efficient and secure inter-server communication, lower latency, flexible inter-server network topology, efficient batch processing, and tolerance to stragglers.

The volume of data moving through a network increases with new scientific experiments and simulations. Network bandwidth requirements also increase proportionally to deliver data within a certain time frame. We observe that a significant portion of the popular dataset is transferred multiple times to different users as well as to the same user for various reasons. In-network data caching for the shared data has shown to reduce the redundant data transfers and consequently save network traffic volume. In addition, overall application performance is expected to improve with in-network caching because access to the locally cached data results in lower latency. This paper shows how much data was shared over the study period, how much network traffic volume was consequently saved, and how much the temporary in-network caching increased the scientific application performance. It also analyzes data access patterns in applications and the impacts of caching nodes on the regional data repository. From the results, we observed that the network bandwidth demand was reduced by nearly a factor of 3 over the study period.

HipMCL is a high-performance distributed memory implementation of the popular Markov Cluster Algorithm (MCL) and can cluster large-scale networks within hours using a few thousand CPU-equipped nodes. It relies on sparse matrix computations and heavily makes use of the sparse matrix-sparse matrix multiplication kernel (SpGEMM). The existing parallel algorithms in HipMCL are not scalable to Exascale architectures, both due to their communication costs dominating the runtime at large concurrencies and also due to their inability to take advantage of accelerators that are increasingly popular.In this work, we systematically remove scalability and performance bottlenecks of HipMCL. We enable GPUs by performing the expensive expansion phase of the MCL algorithm on GPU. We propose a CPU-GPU joint distributed SpGEMM algorithm called pipelined Sparse SUMMA and integrate a probabilistic memory requirement estimator that is fast and accurate. We develop a new merging algorithm for the incremental processing of partial results produced by the GPUs, which improves the overlap efficiency and the peak memory usage. We also integrate a recent and faster algorithm for performing SpGEMM on CPUs. We validate our new algorithms and optimizations with extensive evaluations. With the enabling of the GPUs and integration of new algorithms, HipMCL is up to 12.4x faster, being able to cluster a network with 70 million proteins and 68 billion connections just under 15 minutes using 1024 nodes of ORNL's Summit supercomputer.

We present the design and optimization of a linear solver on General Purpose GPUs for the efficient and high-throughput evaluation of the marginalized graph kernel between pairs of labeled graphs. The solver implements a preconditioned conjugate gradient (PCG) method to compute the solution to a generalized Laplacian equation associated with the tensor product of two graphs. To cope with the gap between the instruction throughput and the memory bandwidth of current generation GPUs, our solver forms the tensor product linear system on-the-fly without storing it in memory when performing matrix-vector dot product operations in PCG. Such on-the-fly computation is accomplished by using threads in a warp to cooperatively stream the adjacency and edge label matrices of individual graphs by small square matrix blocks called tiles, which are then staged in registers and the shared memory for later reuse. Warps across a thread block can further share tiles via the shared memory to increase data reuse. We exploit the sparsity of the graphs hierarchically by storing only non-empty tiles using a coordinate format and nonzero elements within each tile using bitmaps. Besides, we propose a new partition-based reordering algorithm for aggregating nonzero elements of the graphs into fewer but denser tiles to improve the efficiency of the sparse format.We carry out extensive theoretical analyses on the graph tensor product primitives for tiles of various density and evaluate their performance on synthetic and real-world datasets. Our solver delivers three to four orders of magnitude speedup over existing CPU-based solvers such as GraKeL and GraphKernels. The capability of the solver enables kernel-based learning tasks at unprecedented scales.

Pairwise sequence alignment is one of the most computationally intensive kernels in genomic data analysis, accounting for more than 90% of the runtime for key bioinformatics applications. This method is particularly expensive for third-generation sequences due to the high computational cost of analyzing sequences of length between 1Kb and 1Mb. Given the quadratic overhead of exact pairwise algorithms for long alignments, the community primarily relies on approximate algorithms that search only for high-quality alignments and stop early when one is not found. In this work, we present the first GPU optimization of the popular X-drop alignment algorithm, that we named LOGAN. Results show that our high-performance multi-GPU implementation achieves up to 181.6 GCUPS and speed-ups up to 6.6× and 30.7× using 1 and 6 NVIDIA Tesla V100, respectively, over the state-of-the-art software running on two IBM Power9 processors using 168 CPU threads, with equivalent accuracy. We also demonstrate a 2.3× LOGAN speed-up versus ksw2, a state-of-art vectorized algorithm for sequence alignment implemented in minimap2, a long-read mapping software. To highlight the impact of our work on a real-world application, we couple LOGAN with a many-to-many long-read alignment software called BELLA, and demonstrate that our implementation improves the overall BELLA runtime by up to 10.6×. Finally, we adapt the Roofline model for LOGAN and demonstrate that our implementation is near optimal on the NVIDIA Tesla V100s.

Contact tracing has emerged as one of the main mitigation strategies toprevent the spread of pandemics such as COVID-19. Recently, several effortshave been initiated to track individuals, their movements, and interactionsusing technologies, e.g., Bluetooth beacons, cellular data records, andsmartphone applications. Such solutions are often intrusive, potentiallyviolating individual privacy rights and are often subject to regulations (e.g.,GDPR and CCPR) that mandate the need for opt-in policies to gather and usepersonal information. In this paper, we introduce Quest, a system that empowersorganizations to observe individuals and spaces to implement policies forsocial distancing and contact tracing using WiFi connectivity data in a passiveand privacy-preserving manner. The goal is to ensure the safety of employeesand occupants at an organization, while protecting the privacy of all parties.Quest incorporates computationally- and information-theoretically-secureprotocols that prevent adversaries from gaining knowledge of an individual'slocation history (based on WiFi data); it includes support for accuratelyidentifying users who were in the vicinity of a confirmed patient, and theninforming them via opt-in mechanisms. Quest supports a range of privacy-enabledapplications to ensure adherence to social distancing, monitor the flow ofpeople through spaces, identify potentially impacted regions, and raiseexposure alerts. We describe the architecture, design choices, andimplementation of the proposed security/privacy techniques in Quest. We, also,validate the practicality of Quest and evaluate it thoroughly via an actualcampus-scale deployment at UC Irvine over a very large dataset of over 50Mtuples.

HipMCL is a high-performance distributed memory implementation of the popular Markov Cluster Algorithm (MCL) and can cluster large-scale networks within hours using a few thousand CPU-equipped nodes. It relies on sparse matrix computations and heavily makes use of the sparse matrix-sparse matrix multiplication kernel (SpGEMM). The existing parallel algorithms in HipMCL are not scalable to Exascale architectures, both due to their communication costs dominating the runtime at large concurrencies and also due to their inability to take advantage of accelerators that are increasingly popular.In this work, we systematically remove scalability and performance bottlenecks of HipMCL. We enable GPUs by performing the expensive expansion phase of the MCL algorithm on GPU. We propose a CPU-GPU joint distributed SpGEMM algorithm called pipelined Sparse SUMMA and integrate a probabilistic memory requirement estimator that is fast and accurate. We develop a new merging algorithm for the incremental processing of partial results produced by the GPUs, which improves the overlap efficiency and the peak memory usage. We also integrate a recent and faster algorithm for performing SpGEMM on CPUs. We validate our new algorithms and optimizations with extensive evaluations. With the enabling of the GPUs and integration of new algorithms, HipMCL is up to 12.4x faster, being able to cluster a network with 70 million proteins and 68 billion connections just under 15 minutes using 1024 nodes of ORNL's Summit supercomputer.

Pairwise sequence alignment is one of the most computationally intensive kernels in genomic data analysis, accounting for more than 90% of the runtime for key bioinformatics applications. This method is particularly expensive for third-generation sequences due to the high computational cost of analyzing sequences of length between 1Kb and 1Mb. Given the quadratic overhead of exact pairwise algorithms for long alignments, the community primarily relies on approximate algorithms that search only for high-quality alignments and stop early when one is not found. In this work, we present the first GPU optimization of the popular X-drop alignment algorithm, that we named LOGAN. Results show that our high-performance multi-GPU implementation achieves up to 181.6 GCUPS and speed-ups up to 6.6× and 30.7× using 1 and 6 NVIDIA Tesla V100, respectively, over the state-of-the-art software running on two IBM Power9 processors using 168 CPU threads, with equivalent accuracy. We also demonstrate a 2.3× LOGAN speed-up versus ksw2, a state-of-art vectorized algorithm for sequence alignment implemented in minimap2, a long-read mapping software. To highlight the impact of our work on a real-world application, we couple LOGAN with a many-to-many long-read alignment software called BELLA, and demonstrate that our implementation improves the overall BELLA runtime by up to 10.6×. Finally, we adapt the Roofline model for LOGAN and demonstrate that our implementation is near optimal on the NVIDIA Tesla V100s.

We present the design and optimization of a linear solver on General Purpose GPUs for the efficient and high-throughput evaluation of the marginalized graph kernel between pairs of labeled graphs. The solver implements a preconditioned conjugate gradient (PCG) method to compute the solution to a generalized Laplacian equation associated with the tensor product of two graphs. To cope with the gap between the instruction throughput and the memory bandwidth of current generation GPUs, our solver forms the tensor product linear system on-the-fly without storing it in memory when performing matrix-vector dot product operations in PCG. Such on-the-fly computation is accomplished by using threads in a warp to cooperatively stream the adjacency and edge label matrices of individual graphs by small square matrix blocks called tiles, which are then staged in registers and the shared memory for later reuse. Warps across a thread block can further share tiles via the shared memory to increase data reuse. We exploit the sparsity of the graphs hierarchically by storing only non-empty tiles using a coordinate format and nonzero elements within each tile using bitmaps. Besides, we propose a new partition-based reordering algorithm for aggregating nonzero elements of the graphs into fewer but denser tiles to improve the efficiency of the sparse format.We carry out extensive theoretical analyses on the graph tensor product primitives for tiles of various density and evaluate their performance on synthetic and real-world datasets. Our solver delivers three to four orders of magnitude speedup over existing CPU-based solvers such as GraKeL and GraphKernels. The capability of the solver enables kernel-based learning tasks at unprecedented scales.

The growing deployment of Internet of Things (IoT) systems aims to ease thedaily life of end-users by providing several value-added services. However, IoTsystems may capture and store sensitive, personal data about individuals in thecloud, thereby jeopardizing user-privacy. Emerging legislation, such asCalifornia's CalOPPA and GDPR in Europe, support strong privacy laws to protectan individual's data in the cloud. One such law relates to strict enforcementof data retention policies. This paper proposes a framework, entitled IoTExpunge that allows sensor data providers to store the data in cloud platformsthat will ensure enforcement of retention policies. Additionally, the cloudprovider produces verifiable proofs of its adherence to the retention policies.Experimental results on a real-world smart building testbed show that IoTExpunge imposes minimal overheads to the user to verify the data against dataretention policies.

We present the software system developed to implement the Locus Algorithm, anovel algorithm designed to maximise the performance of differential photometrysystems by optimising the number and quality of reference stars in the Field ofView with the target. Firstly, we state the design requirements, constraintsand ambitions for the software system required to implement this algorithm.Then, a detailed software design is presented for the system in operation.Next, the data design including file structures used and the data environmentrequired for the system are defined. Finally, we conclude by illustrating thescaling requirements which mandate a high-performance computing implementationof this system, which is discussed in the other papers in this series.

This paper discusses the hardware and software components of the GridComputing system used to implement the Locus Algorithm to identify optimumpointings for differential photometry of 61,662,376 stars and 23,799 quasars.The scale of the data, together with initial operational assessments demanded aHigh Performance Computing (HPC) system to complete the data analysis. Gridcomputing was chosen as the HPC solution as the optimum choice available withinthis project. The physical and logical structure of the National Grid computingInfrastructure informed the approach that was taken. That approach was one oflayered separation of the different project components to enable maximumflexibility and extensibility.

Genomic datasets are growing dramatically as the cost of sequencing continues to decline and small sequencing devices become available. Enormous community databases store and share these data with the research community, but some of these genomic data analysis problems require large-scale computational platforms to meet both the memory and computational requirements. These applications differ from scientific simulations that dominate the workload on high-end parallel systems today and place different requirements on programming support, software libraries and parallel architectural design. For example, they involve irregular communication patterns such as asynchronous updates to shared data structures. We consider several problems in high-performance genomics analysis, including alignment, profiling, clustering and assembly for both single genomes and metagenomes. We identify some of the common computational patterns or 'motifs' that help inform parallelization strategies and compare our motifs to some of the established lists, arguing that at least two key patterns, sorting and hashing, are missing. This article is part of a discussion meeting issue 'Numerical algorithms for high-performance computational science'.

A central problem in analog wireless sensor networks is to design the gain or phase-shifts of the sensor nodes (i.e. the relaying configuration) in order to achieve an accurate estimation of some parameter of interest at a fusion center, or more generally, at each node by employing a distributed parameter estimation scheme. In this paper, by using an over-parametrization of the original design problem, we devise a cyclic optimization approach that can handle tuning both gains and phase-shifts of the sensor nodes, even in intricate scenarios involving sensor selection or discrete phase-shifts. Each iteration of the proposed design framework consists of a combination of the Gram-Schmidt process and power method-like iterations, and as a result, enjoys a low computational cost. Along with formulating the design problem for a fusion center, we further present a consensus-based framework for decentralized estimation of deterministic parameters in a distributed network, which results in a similar sensor gain design problem. The numerical results confirm the computational advantage of the suggested approach in comparison with the state-of-the-art methods-an advantage that becomes more pronounced when the sensor network grows large.

We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length 4 in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.

The rapid growth of big spatial data urged the research community to develop several big spatial data systems. Regardless of their architecture, one of the fundamental requirements of all these systems is to spatially partition the data efficiently across machines. The core challenges of big spatial partitioning are building high spatial quality partitions while simultaneously taking advantages of distributed processing models by providing load balanced partitions. Previous works on big spatial partitioning are to reuse existing index search trees as-is, e.g., the R-tree family, STR, Kd-tree, and Quad-tree, by building a temporary tree for a sample of the input and use its leaf nodes as partition boundaries. However, we show in this paper that none of those techniques has addressed the mentioned challenges completely. This paper proposes a novel partitioning method, termed R*-Grove, which can partition very large spatial datasets into high quality partitions with excellent load balance and block utilization. This appealing property allows R*-Grove to outperform existing techniques in spatial query processing. R*-Grove can be easily integrated into any big data platforms such as Apache Spark or Apache Hadoop. Our experiments show that R*-Grove outperforms the existing partitioning techniques for big spatial data systems. With all the proposed work publicly available as open source, we envision that R*-Grove will be adopted by the community to better serve big spatial data research.

Tomographic imaging has benefited from advances in X-ray sources, detectors and optics to enable novel observations in science, engineering and medicine. These advances have come with a dramatic increase of input data in the form of faster frame rates, larger fields of view or higher resolution, so high performance solutions are currently widely used for analysis. Tomographic instruments can vary significantly from one to another, including the hardware employed for reconstruction: from single CPU workstations to large scale hybrid CPU/GPU supercomputers. Flexibility on the software interfaces and reconstruction engines are also highly valued to allow for easy development and prototyping. This paper presents a novel software framework for tomographic analysis that tackles all aforementioned requirements. The proposed solution capitalizes on the increased performance of sparse matrix-vector multiplication and exploits multi-CPU and GPU reconstruction over MPI. The solution is implemented in Python and relies on CuPy for fast GPU operators and CUDA kernel integration, and on SciPy for CPU sparse matrix computation. As opposed to previous tomography solutions that are tailor-made for specific use cases or hardware, the proposed software is designed to provide flexible, portable and high-performance operators that can be used for continuous integration at different production environments, but also for prototyping new experimental settings or for algorithmic development. The experimental results demonstrate how our implementation can even outperform state-of-the-art software packages used at advanced X-ray sources worldwide.

The predominance of Kohn-Sham density functional theory (KS-DFT) for the theoretical treatment of large experimentally relevant systems in molecular chemistry and materials science relies primarily on the existence of efficient software implementations which are capable of leveraging the latest advances in modern high-performance computing (HPC). With recent trends in HPC leading toward increasing reliance on heterogeneous accelerator-based architectures such as graphics processing units (GPU), existing code bases must embrace these architectural advances to maintain the high levels of performance that have come to be expected for these methods. In this work, we purpose a three-level parallelism scheme for the distributed numerical integration of the exchange-correlation (XC) potential in the Gaussian basis set discretization of the Kohn-Sham equations on large computing clusters consisting of multiple GPUs per compute node. In addition, we purpose and demonstrate the efficacy of the use of batched kernels, including batched level-3 BLAS operations, in achieving high levels of performance on the GPU. We demonstrate the performance and scalability of the implementation of the purposed method in the NWChemEx software package by comparing to the existing scalable CPU XC integration in NWChem.

Tomographic imaging has benefited from advances in X-ray sources, detectors and optics to enable novel observations in science, engineering and medicine. These advances have come with a dramatic increase of input data in the form of faster frame rates, larger fields of view or higher resolution, so high performance solutions are currently widely used for analysis. Tomographic instruments can vary significantly from one to another, including the hardware employed for reconstruction: from single CPU workstations to large scale hybrid CPU/GPU supercomputers. Flexibility on the software interfaces and reconstruction engines are also highly valued to allow for easy development and prototyping. This paper presents a novel software framework for tomographic analysis that tackles all aforementioned requirements. The proposed solution capitalizes on the increased performance of sparse matrix-vector multiplication and exploits multi-CPU and GPU reconstruction over MPI. The solution is implemented in Python and relies on CuPy for fast GPU operators and CUDA kernel integration, and on SciPy for CPU sparse matrix computation. As opposed to previous tomography solutions that are tailor-made for specific use cases or hardware, the proposed software is designed to provide flexible, portable and high-performance operators that can be used for continuous integration at different production environments, but also for prototyping new experimental settings or for algorithmic development. The experimental results demonstrate how our implementation can even outperform state-of-the-art software packages used at advanced X-ray sources worldwide.

A central problem in analog wireless sensor networks is to design the gain or phase-shifts of the sensor nodes (i.e. the relaying configuration) in order to achieve an accurate estimation of some parameter of interest at a fusion center, or more generally, at each node by employing a distributed parameter estimation scheme. In this paper, by using an over-parametrization of the original design problem, we devise a cyclic optimization approach that can handle tuning both gains and phase-shifts of the sensor nodes, even in intricate scenarios involving sensor selection or discrete phase-shifts. Each iteration of the proposed design framework consists of a combination of the Gram-Schmidt process and power method-like iterations, and as a result, enjoys a low computational cost. Along with formulating the design problem for a fusion center, we further present a consensus-based framework for decentralized estimation of deterministic parameters in a distributed network, which results in a similar sensor gain design problem. The numerical results confirm the computational advantage of the suggested approach in comparison with the state-of-the-art methods-an advantage that becomes more pronounced when the sensor network grows large.

Serverless computing is increasingly popular because of the promise of lowercost and the convenience it provides to users who do not need to focus onserver management. This has resulted in the availability of a number ofproprietary and open-source serverless solutions. We seek to understand how theperformance of serverless computing depends on a number of design issues usingseveral popular open-source serverless platforms. We identify theidiosyncrasies affecting performance (throughput and latency) for differentopen-source serverless platforms. Further, we observe that just having eitherresource-based (CPU and memory) or workload-based (request per second (RPS) orconcurrent requests) auto-scaling is inadequate to address the needs of theserverless platforms.

Distributed data structures are key to implementing scalable applications for scientific simulations and data analysis. In this paper we look at two implementation styles for distributed data structures: remote direct memory access (RDMA) and remote procedure call (RPC). We focus on operations that require individual accesses to remote portions of a distributed data structure, e.g., accessing a hash table bucket or distributed queue, rather than global operations in which all processors collectively exchange information. We look at the trade-offs between the two styles through microbenchmarks and a performance model that approximates the cost of each. The RDMA operations have direct hardware support in the network and therefore lower latency and overhead, while the RPC operations are more expressive but higher cost and can suffer from lack of attentiveness from the remote side. We also run experiments to compare the real-world performance of RDMA- and RPC-based data structure operations with the predicted performance to evaluate the accuracy of our model, and show that while the model does not always precisely predict running time, it allows us to choose the best implementation in the examples shown. We believe this analysis will assist developers in designing data structures that will perform well on current network architectures, as well as network architects in providing better support for this class of distributed data structures.