Search

High performance computing system, which takes an interconnection network as its infrastructure topology, has been utilized in scientific computing, big data analysis as well as artificial intelligence. With the rapid growth of infrastructure topology (interconnection network) in high performance computing system, the probability of network element malfunction increases dramatically. Generally, the reliability of interconnection network is measured by the traditional (edge) connectivity, which is limited by the minimum degree of the network. In order to overcome the defect, the matroidal connectivity has been newly proposed to extend the edge connectivity. For the regular network G , let B k (G) = { B 1 , B 2 , ... , B k } be a fixed edge partition ordered sequence of G and χ k = (x 1 , x 2 , ... , x k) be a sequence of k integers. For any D ⊆ E (G) , if | D ∩ B i | ≤ x i (i ∈ [ k ]) and G − D is disconnected, then D is named matroidal cut set of G. The matroidal connectivity of G , denoted by λ (G , B k (G)) , is the minimum size of matroidal cut set of G. In this work, we characterize the matroidal connectivity of a class of n -dimensional regular networks G n. To be more specific, we show that λ (G n , B n (G n)) = (k − l + 1) f (l + j) , where f (n) is a function about n , and l , k , n are positive integers (l ≥ 1), j = n − k. As empirical analysis, we directly determine the matroidal connectivity of some well-known interconnection networks, such as hypercube Q n , star graph S T n and alternating group graph A G n. • High performance computing system, which takes interconnection network as its infrastructure topology, has been utilized in scientific computing, big data analysis as well as artificial intelligence. For the regular networks G , we use λ (G , B k (G)) to denote matroidal connectivity of G (where B k (G) = { B 1 , B 2 , ... , B k } is a fixed edge partition ordered sequence of G), which is the minimum size of edge cut set D ⊆ ∪ i = 1 k B i so that G − D is disconnected. In this work, we characterize the matroidal connectivity of a class of n -dimensional regular networks G n. That is, λ (G n , B k (G n)) = (k − l + 1) f (l + j) , where l , k , j (l ≤ k ≤ n) are integers. As empirical analysis, we determine the matroidal connectivity of some kinds of well-known interconnection networks, such as hypercubes (Q n), star graph (S T n) and alternating group graph (A G n). [ABSTRACT FROM AUTHOR]

• Propose the aligned storage formats ACSR and AELL. • Put forward a parallel SpMV algorithm based on ACSR and AELL formats. • Theoretically analyze the performance of SpMV on ARM processors. • Evaluate the performance of our optimization on Kunpeng 920 processors. Sparse matrix-vector multiplication (SpMV) has always been a hot topic of research for scientific computing and big data processing, but the sparsity and discontinuity of the nonzero elements in a sparse matrix lead to the memory bottleneck of SpMV. In this paper, we propose aligned CSR (ACSR) and aligned ELL (AELL) formats and a parallel SpMV algorithm to utilize NEON SIMD registers on ARM processors. We analyze the impact of SIMD instruction latency, cache access, and cache misses on SpMV with different formats. In the experiments, our SpMV algorithm based on ACSR achieves 1.18x and 1.56x speedup over SpMV based on CSR and SpMV in PETSc, respectively, and AELL achieves 1.21x speedup over ELL. The deviations between the theoretical results and experimental results in the instruction latency and cache access are 10.26% and 10.51% in ACSR and 5.68% and 2.91% in AELL, respectively. [ABSTRACT FROM AUTHOR]

There is a need for simple, fast, and memory-efficient multidimensional data structures for dense and sparse storage that arise with numerical methods and in software applications. The data structures must perform equally well across multiple computer architectures, including CPUs and GPUs. For this purpose, we developed MATAR, a C++ software library that allows for simple creation and use of intricate data structures that is also portable across disparate architectures using Kokkos. The performance aspect is achieved by forcing contiguous memory layout (or as close to contiguous as possible) for multidimensional and multi-size dense or sparse MAT rix and AR ray (hence, MATAR) types. Our results show that MATAR has the capability to improve memory utilization, performance, and programmer productivity in scientific computing. This is achieved by fitting more work into the available memory, minimizing memory loads required, and by loading memory in the most efficient order. This document describes the purpose of the work, the implementation of each of the data types, and the resulting performance both in some simple baseline test cases and in an application code. • Providing data structures that map problem data efficiently in memory. • Providing an easy to use interface for fast data access and modifier operators. • Creating data structures using Kokkos that run on multiple CPU and GPU architectures in a performant and portable manner. • Example use case of how to use Kokkos to encapsulate complex class hierarchies and virtual functions. [ABSTRACT FROM AUTHOR]

Rendezvous algorithms encode a communication pattern that is useful when processors sending data do not know who the receiving processors should be, or vice versa. The idea is to define an intermediate decomposition where datums from different sending processors can "rendezvous" to perform a computation, in a manner that both the senders and eventual receivers of the results can identify the appropriate rendezvous processor. Originally designed for interpolating between overlaid grids with independent parallel decompositions (Plimpton et al., 2004), we have recently found rendezvous algorithms useful for a variety of operations in particle- or grid-based simulation codes when running large problems on large numbers of processors. In particular, we show they can perform well when a load-balanced intermediate decomposition is randomized and not spatial, requiring all-to-all communication to move data between processors. In this case rendezvous algorithms leverage the large bisection communication bandwidths which parallel machines provide. We describe how rendezvous algorithms work in a scientific computing context and give specific examples for molecular dynamics and Direct Simulation Monte Carlo codes which result in dramatic performance improvements versus simpler algorithms which do not scale as well. We explain how a generic rendezvous algorithm can be implemented, and also point out similarities with the MapReduce paradigm popularized by Google and Hadoop. • This paper explains how parallel rendezvous algorithms work in the context of large-scale scientific modeling and simulation codes. • It gives several examples of such algorithms. • It presents performance gains of the new algorithms relative to previously used simpler algorithms which were less scalable. [ABSTRACT FROM AUTHOR]

We present the Julia package ToricAtiyahBott.jl, providing an easy way to perform the Atiyah–Bott formula on the moduli space of genus 0 stable maps M ‾ 0 , m (X , β) where X is any smooth projective toric variety, and β is any effective 1-cycle. The list of the supported cohomological cycles contains the most common ones, and it is extensible. We provide a detailed explanation of the algorithm together with many examples and applications. The toric variety X , as well as the cohomology class β , must be defined using the package Oscar.jl. [ABSTRACT FROM AUTHOR]

Lots of computational predictors have been developed for fast and large-scale analysis of biological data. However, many of them were developed long time ago when training datasets or sets of input features were rather small. Consequently, the utility of these predictors in much large datasets, which are very common in nowadays, need to be examined carefully. In addition, with the rapid development of scientific research, the expectation on the prediction accuracy of computational predictors is continuously uplifting. Therefore, developing novel strategies to improve the prediction accuracies of computational predictors becomes critical. In this study, the predictive results of existing individual miRNA target predictors were integrated into a decision-tree to make meta-prediction. When the multi-threshold sequential-voting technique was used, the prediction accuracy of the decision-tree was significantly improved by at least thirty percentage points compared to the individual predictors. [ABSTRACT FROM AUTHOR]

Computational science and engineering application programs are typically large, complex, and dynamic, and are often constrained by distribution limitations. As a means of making tractable rapid explorations of scientific and engineering application programs in the context of new, emerging, and future computing architectures, a suite of “miniapps” has been created to serve as proxies for full scale applications. Each miniapp is designed to represent a key performance characteristic that does or is expected to significantly impact the runtime performance of an application program. In this paper we introduce a methodology for assessing the ability of these miniapps to effectively represent these performance issues. We applied this methodology to three miniapps, examining the linkage between them and an application they are intended to represent. Herein we evaluate the fidelity of that linkage. This work represents the initial steps required to begin to answer the question, “Under what conditions does a miniapp represent a key performance characteristic in a full app?” [ABSTRACT FROM AUTHOR]

The design and implementation of high level tools for parallel programming is a major challenge as the complexity of modern architectures increases. Domain Specific Languages (or DSL) have been proposed as a solution to facilitate this design but few of those DSL s actually take full advantage of said parallel architectures. In this paper, we propose a library-based solution by designing a C++ DSL s using generative programming: NT 2 . By adapting generative programming idioms so that architecture specificities become mere parameters of the code generation process, we demonstrate that our library can deliver high performance while featuring a high level API and being easy to extend over new architectures. [ABSTRACT FROM AUTHOR]

Abstract: Parallelism has become mainstream, in the multicore chip, the GPU, and the internet datacenter running MapReduce. In my field, large-scale scientific computing, parallelism now reigns triumphant. It was no simple, direct route that led to this triumph. Along the way, we were confused by ideas that, in retrospect, turned out to be distractions and errors. The thinking behind them was reasonable, but wrong. One can learn from a dissection of mistakes, so I will retell part of the story here. [Copyright &y& Elsevier]

Abstract: Symbolic and logic computation systems ranging from computer algebra systems to theorem provers are finding their way into science, technology, mathematics and engineering. But such systems rely on explicitly or implicitly represented mathematical knowledge that needs to be managed to use such systems effectively. While mathematical knowledge management (MKM) “in the small” is well-studied, scaling up to large, highly interconnected corpora remains difficult. We hold that in order to realize MKM “in the large”, we need representation languages and software architectures that are designed systematically with large-scale processing in mind. Therefore, we have designed and implemented the Mmt language – a module system for mathematical theories. Mmt is designed as the simplest possible language that combines a module system, a foundationally uncommitted formal semantics, and web-scalable implementations. Due to a careful choice of representational primitives, Mmt allows us to integrate existing representation languages for formal mathematical knowledge in a simple, scalable formalism. In particular, Mmt abstracts from the underlying mathematical and logical foundations so that it can serve as a standardized representation format for a formal digital library. Moreover, Mmt systematically separates logic-dependent and logic-independent concerns so that it can serve as an interface layer between computation systems and MKM systems. [Copyright &y& Elsevier]

Abstract: The ability to support Quality of Service (QoS) constraints is an important requirement in some scientific applications. With the increasing use of Cloud computing infrastructures, where access to resources is shared, dynamic and provisioned on-demand, identifying how QoS constraints can be supported becomes an important challenge. However, access to dedicated resources is often not possible in existing Cloud deployments and limited QoS guarantees are provided by many commercial providers (often restricted to error rate and availability, rather than particular QoS metrics such as latency or access time). We propose a workflow system architecture which enforces QoS for the simultaneous execution of multiple scientific workflows over a shared infrastructure (such as a Cloud environment). Our approach involves multiple pipeline workflow instances, with each instance having its own QoS requirements. These workflows are composed of a number of stages, with each stage being mapped to one or more physical resources. A stage involves a combination of data access, computation and data transfer capability. A token bucket-based data throttling framework is embedded into the workflow system architecture. Each workflow instance stage regulates the amount of data that is injected into the shared resources, allowing for bursts of data to be injected while at the same time providing isolation of workflow streams. We demonstrate our approach by using the Montage workflow, and develop a Reference net model of the workflow. [Copyright &y& Elsevier]

Abstract: Numerical analysis of Markovian models is relevant for performance evaluation and probabilistic analysis of systems’ behavior from several fields in science and engineering. These models can be represented in a compact fashion using Kronecker algebra. The Vector-Descriptor Product (VDP) is the key operation to obtain stationary and transient solutions of models represented by Kronecker-based descriptors. VDP algorithms are usually CPU intensive, requiring alternatives such as data partitioning to produce results in less time. This paper introduces a set of parallel implementations of a hybrid algorithm for handling descriptors and a detailed performance analysis on four real Markovian models. The implementations are based on different scheduling strategies using OpenMP and existing techniques of static and dynamic load balancing, along with data partitioning presented in the literature. The performance evaluation study contains analysis of speed-up, synchronization and scheduling overheads, task mapping policies, and memory affinity. The results presented here provide insights into different implementation choices for an application on shared-memory systems and how this application benefited from this architecture. [Copyright &y& Elsevier]

Abstract: In parallel adaptive applications, the computational structure of the applications changes over time, leading to load imbalances even though the initial load distributions were balanced. To restore balance and to keep communication volume low in further iterations of the applications, dynamic load balancing (repartitioning) of the changed computational structure is required. Repartitioning differs from static load balancing (partitioning) due to the additional requirement of minimizing migration cost to move data from an existing partition to a new partition. In this paper, we present a novel repartitioning hypergraph model for dynamic load balancing that accounts for both communication volume in the application and migration cost to move data, in order to minimize the overall cost. The use of a hypergraph-based model allows us to accurately model communication costs rather than approximate them with graph-based models. We show that the new model can be realized using hypergraph partitioning with fixed vertices and describe our parallel multilevel implementation within the Zoltan load balancing toolkit. To the best of our knowledge, this is the first implementation for dynamic load balancing based on hypergraph partitioning. To demonstrate the effectiveness of our approach, we conducted experiments on a Linux cluster with 1024 processors. The results show that, in terms of reducing total cost, our new model compares favorably to the graph-based dynamic load balancing approaches, and multilevel approaches improve the repartitioning quality significantly. [Copyright &y& Elsevier]

Abstract: Particle-In-Cell (PIC) methods have been widely used for plasma physics simulations in the past three decades. To ensure an acceptable level of statistical accuracy relatively large numbers of particles are needed. State-of-the-art Graphics Processing Units (GPUs), with their high memory bandwidth, hundreds of SPMD processors, and half-a-teraflop performance potential, offer a viable alternative to distributed memory parallel computers for running medium-scale PIC plasma simulations on inexpensive commodity hardware. In this paper, we present an overview of a typical plasma PIC code and discuss its GPU implementation. In particular we focus on fast algorithms for the performance bottleneck operation of Particle-To-Grid interpolation. [Copyright &y& Elsevier]

Abstract: We present a scalable framework for parallelizing greedy graph coloring algorithms on distributed-memory computers. The framework unifies several existing algorithms and blends a variety of techniques for creating or facilitating concurrency. The latter techniques include exploiting features of the initial data distribution, the use of speculative coloring and randomization, and a BSP-style organization of computation and communication. We experimentally study the performance of several specialized algorithms designed using the framework and implemented using MPI. The experiments are conducted on two different platforms and the test cases include large-size synthetic graphs as well as real graphs drawn from various application areas. Computational results show that implementations that yield good speedup while at the same time using about the same number of colors as a sequential greedy algorithm can be achieved by setting parameters of the framework in accordance with the size and structure of the graph being colored. Our implementation is freely available as part of the Zoltan parallel data management and load-balancing library. [Copyright &y& Elsevier]

Abstract: We propose an architecture to harness the comparatively low computational power of geographically concentrated mobile devices (such as in a wireless ad hoc network, especially a sensor network) to build a wireless ad hoc lattice computer (WAdL). The primary contribution of the WAdL design is the ability to maintain, despite the mobility of the participating devices, a virtual lattice where the devices represent lattice points. WAdL is a cellular automaton-like architecture designed to carry out simulations of the unfolding of physical phenomena (e.g., fluid flow, system of moving, interacting objects, etc.) in the bounded region of Euclidean space represented by the underlying virtual lattice of WAdL. We present the design and algorithms of the WAdL architecture, and demonstrate its use with an example application (lift and drag on an airplane wing in flight) implemented on a simulated WAdL environment. We also discuss current issues and future directions of work on the WAdL architecture. [Copyright &y& Elsevier]

The exploitation of idle cycles on pervasive desktop PC systems offers the opportunity to increase the available computing power by orders of magnitude (10×–1000×). However, for desktop PC distributed computing to be widely accepted within the enterprise, the systems must achieve high levels of efficiency, robustness, security, scalability, manageability, unobtrusiveness, and openness/ease of application integration.We describe the Entropia distributed computing system as a case study, detailing its internal architecture and philosophy in attacking these key problems. Key aspects of the Entropia system include the use of: (1) binary sandboxing technology for security and unobtrusiveness, (2) a layered architecture for efficiency, robustness, scalability and manageability, and (3) an open integration model to allow applications from many sources to be incorporated.Typical applications for the Entropia System includes molecular docking, sequence analysis, chemical structure modeling, and risk management. The applications come from a diverse set of domains including virtual screening for drug discovery, genomics for drug targeting, material property prediction, and portfolio management. In all cases, these applications scale to many thousands of nodes and have no dependences between tasks. We present representative performance results from several applications that illustrate the high performance, linear scaling, and overall capability presented by the Entropia system. [Copyright &y& Elsevier]