Search

Exascale workloads are expected to incorporate data-intensive processing in close coordination with traditional physics simulations. These emerging scientific, data-analytics and machine learning applications need to access a wide variety of datastores in flat files and structured databases. Programmer productivity is greatly enhanced by mapping datastores into the application process's virtual memory space to provide a unified “in-memory” interface. Currently, memory mapping is provided by system software primarily designed for generality and reliability. However, scalability at high concurrency is a formidable challenge on exascale systems. Also, there is a need for extensibility to support new datastores potentially requiring HPC data transfer services. In this article, we present UMap , a scalable and extensible userspace service for memory-mapping datastores. Through decoupled queue management, concurrency aware adaptation, and dynamic load balancing, UMap enables application performance to scale even at high concurrency. We evaluate UMap in data-intensive applications, including sorting, graph traversal, database operations, and metagenomic analytics. Our results show that UMap as a userspace service outperforms an optimized kernel-based service across a wide range of intra-node concurrency by 1.22-1.9 ${\times}$ × . We performed two case studies to demonstrate UMap 's extensibility. First, a new datastore residing in remote memory is incorporated into UMap as an application-specific plugin. Second, we present a persistent memory allocator Metall built atop UMap for unified storage/memory.

Pattern matching is a fundamental tool for answering complex graph queries. Unfortunately, existing solutions have limited capabilities: They do not scale to process large graphs and/or support only a restricted set of search templates or usage scenarios. Moreover, the algorithms at the core of the existing techniques are not suitable for today’s graph processing infrastructures relying on horizontal scalability and shared-nothing clusters, as most of these algorithms are inherently sequential and difficult to parallelize. We present an algorithmic pipeline that bases pattern matching on constraint checking . The key intuition is that each vertex and edge participating in a match has to meet a set of constraints implicitly specified by the search template. These constraints can be verified independently and typically are less expensive to compute than searching the full template. The pipeline we propose generates these constraints and iterates over them to eliminate all the vertices and edges that do not participate in any match, thus reducing the background graph to a subgraph that is the union of all template matches—the complete set of all vertices and edges that participate in at least one match. Additional analysis can be performed on this annotated, reduced graph, such as full match enumeration, match counting, or computing vertex/edge centrality. Furthermore, a vertex-centric formulation for constraint checking algorithms exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks. This technique (i) enables highly scalable pattern matching in metadata (labeled) graphs; (ii) supports arbitrary patterns with 100% precision; (iii) enables tradeoffs between precision and time-to-solution, while always selects all vertices and edges that participate in matches, thus offering 100% recall; and (iv) supports a set of popular data analytics scenarios. We implement our approach on top of HavoqGT, an open-source asynchronous graph processing framework, and demonstrate its advantages through strong and weak scaling experiments on massive scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) labeled graphs, respectively, and at scales (1,024 nodes / 36,864 cores), orders of magnitude larger than used in the past for similar problems. This article serves two purposes: First, it synthesises the knowledge accumulated during a long-term project [Reza et al. 2017, 2018; Tripoul et al. 2018]. Second, it presents new system features, usage scenarios, optimizations, and comparisons with related work that strengthen the confidence that pattern matching based on iterative pruning via constraint checking is an effective and scalable approach in practice. The new contributions include the following: (i) We demonstrate the ability of the constraint checking approach to efficiently support two additional search scenarios that often emerge in practice, interactive incremental search and exploratory search . (ii) We empirically compare our solution with two additional state-of-the-art systems, Arabsque [Teixeira et al. 2015] and TriAD [Gurajada et al. 2014]. (iii) We show the ability of our solution to accommodate a more diverse range of datasets with varying properties, e.g., scale, skewness, label distribution, and match frequency. (iv) We introduce or extend a number of system features (e.g., work aggregation, load balancing, and the ability to cap the generated traffic) and design optimizations and demonstrate their advantages with respect to improving performance and scalability. (v) We present bottleneck analysis and insights into artifacts that influence performance. (vi) We present a theoretical complexity argument that motivates the performance gains we observe.

Supplemental Digital Content is available in the text., With immunohistochemical (IHC) staining increasingly being used to guide clinical decisions, variability in staining quality and reproducibility are becoming essential factors in generating diagnoses using IHC tissue preparations. The current study tested a method to track and quantify the interrun, intrarun, and intersite variability of IHC staining intensity. Our hypothesis was that staining precision between laboratory sites, staining runs, and individual slides may be verified quantitatively, efficiently and effectively utilizing algorithm-based, automated image analysis. To investigate this premise, we tested the consistency of IHC staining in 40 routinely processed (formalin-fixed, paraffin-embedded) human tissues using 10 common antibiomarker antibodies on 2 Dako Omnis instruments at 2 locations (Carpinteria, CA: 30 m above sea level and Longmont, CO: 1500 m above sea level) programmed with identical, default settings and sample pretreatments. Digital images of IHC-labeled sections produced by a whole slide scanner were analyzed by a simple commercially available algorithm and compared with a board-certified veterinary pathologist’s semiquantitative scoring of staining intensity. The image analysis output correlated well with pathology scores but had increased sensitivity for discriminating subtle variations and providing reproducible digital quantification across sites as well as within and among staining runs at the same site. Taken together, our data indicate that digital image analysis offers an objective and quantifiable means of verifying IHC staining parameters as a part of laboratory quality assurance systems.

Understanding the higher-order interactions within network data is a key objective of network science. Surveys of metadata triangles (or patterned 3-cycles in metadata-enriched graphs) are often of interest in this pursuit. In this work, we develop TriPoll, a prototype distributed HPC system capable of surveying triangles in massive graphs containing metadata on their edges and vertices. We contrast our approach with much of the prior effort on triangle analysis, which often focuses on simple triangle counting, usually in simple graphs with no metadata. We assess the scalability of TriPoll when surveying triangles involving metadata on real and synthetic graphs with up to hundreds of billions of edges.We utilize communication-reducing optimizations to demonstrate a triangle counting task on a 224 billion edge web graph in approximately half of the time of competing approaches, while additionally supporting metadata-aware capabilities., Comment: 13 pages, 8 figures

Subgraph search in a massive background graph, i.e., pattern matching in graphs, is a challenging problem, particularly in an interactive usage scenario where fast response time is important. Our approach, Prune.Juice [1], is based on two intuitions: first, rather than directly searching for individual matches, it is cheaper to eliminate vertices and edges of the background graph that do not participate in any match. Second, to perform this pruning process, it is possible to decompose a search pattern into a set of constraints, and use each of these constraints to eliminate non-matching vertices and edges. This paper explores the feasibility of indexing the background graph to accelerate the checking of non-local constraints (e.g., cycles and paths), the most expensive phase of pruning. In particular, we demonstrate that indexing labeled triangle (i.e., a 3-Cycle) participation is a valuable acceleration technique. Additionally, we observe that labeled triangle counts at edges can be employed to detect 3-Paths that have terminal points with non-unique labels, at relatively little extra cost. Such paths and triangles are basic sub-constraints that can be used to rapidly prune non-matching vertices and edges. As proof of concept, we show that, using triangle information alone, indexing further accelerates expensive queries in Prune.Juice by up to $\mathbf{500}\times$ on billion-edge graphs.

Large-scale high-performance computing (HPC) systems consist of massive compute and memory resources tightly coupled in nodes. We perform a large-scale study of memory utilization on four production HPC clusters. Our results show that more than 90% of jobs utilize less than 15% of the node memory capacity, and for 90% of the time, memory utilization is less than 35%. Recently, disaggregated architecture is gaining traction because it can selectively scale up a resource and improve resource utilization. Based on these observations, we explore using disaggregated memory to support memory-intensive applications, while most jobs remain intact on HPC systems with reduced node memory. We designed and developed a user-space remote-memory paging library to enable applications exploring disaggregated memory on existing HPC clusters. We quantified the impact of access patterns and network connectivity in benchmarks. Our case studies of graph-processing and Monte-Carlo applications evaluated the impact of application characteristics and local memory capacity and highlighted the potential of throughput scaling on disaggregated memory.