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.

Given an edge-weighted graph and a set of known seed vertices, a network scientist often desires to understand the graph relationships to explain connections between the seed vertices. When the seed set is 3 or larger Steiner minimal tree - min-weight acyclic connected subgraph (of the input graph) that contains all the seed vertices - is an attractive generalization of shortest weighted paths. In general, computing a Steiner minimal tree is NP-hard, but several polynomial-time algorithms have been designed and proven to yield Steiner trees whose total weight is bounded within 2 times the Steiner minimal tree. In this paper, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of distance computation between all pairs of seed vertices, an expensive phase in many algorithms, our solution exploits Voronoi cell computation. Also, this approach has higher parallel efficiency than others that involve minimum spanning tree computation on the entire graph. Furthermore, our distributed design exploits asynchronous processing and a message prioritization scheme to accelerate convergence of distance computation, and harnesses both vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance of our solution using real-world graphs with up to 128 billion edges and 512 compute nodes (8K processes). We compare our solution with the state-of-the-art exact Steiner minimal tree solver, SCIP-Jack, and two serial algorithms. Our solution comfortably outperforms these related works on graphs with 10s million edges and offers decent strong scaling - up to 90% efficient. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.0527 times greater than the Steiner minimal tree - well within the theoretical bound of less than equal to 2., Comment: The 36th IEEE International Parallel and Distributed Processing Symposium (IEEE IPDPS 2022)

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.

Data analytics applications transform raw input data into analytics-specific data structures before performing analytics. Unfortunately, such data ingestion step is often more expensive than analytics. In addition, various types of NVRAM devices are already used in many HPC systems today. Such devices will be useful for storing and reusing data structures beyond a single process life cycle. We developed Metall, a persistent memory allocator built on top of the memory-mapped file mechanism. Metall enables applications to transparently allocate custom C++ data structures into various types of persistent memories. Metall incorporates a concise and high-performance memory management algorithm inspired by Supermalloc and the rich C++ interface developed by Boost.Interprocess library. On a dynamic graph construction workload, Metall achieved up to 11.7x and 48.3x performance improvements over Boost.Interprocess and memkind (PMEM kind), respectively. We also demonstrate Metall's high adaptability by integrating Metall into a graph processing framework, GraphBLAS Template Library. This study's outcomes indicate that Metall will be a strong tool for accelerating future large-scale data analytics by allowing applications to leverage persistent memory efficiently.

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

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.

Productivity from day one on supercomputers that leverage new technologies requires significant preparation. An institution that procures a novel system architecture often lacks sufficient institutional knowledge and skills to prepare for it. Thus, the "Center of Excellence" (CoE) concept has emerged to prepare for systems such as Summit and Sierra, currently the top two systems in the Top 500. This paper documents CoE experiences that prepared a workload of diverse applications and math libraries for a heterogeneous system. We describe our approach to this preparation, including our management and execution strategies, and detail our experiences with and reasons for using different programming approaches. Our early science and performance results show that the project enabled significant early seismic science with up to a l4X throughput increase over Cori. In addition to our successes, we discuss our challenges and failures so others may benefit from our experience.

Leadership supercomputers feature a diversity of storage, from node-local persistent memory and NVMe SSDs to network-interconnected flash memory and HDD. Memory mapping files on different tiers of storage provides a uniform in- terface in applications. However, system-wide services like mmap are optimized for generality and lack flexibility for enabling application-specific optimizations. In this work, we present UMap to enable user-space page management that can be easily adapted to access patterns in applications and storage characteristics. UMap uses the userfaultfd mechanism to handle page faults in multi-threaded applications efficiently. By providing a data object abstraction layer, UMap is extensible to support various backing stores. The design of UMap supports dynamic load balancing and I/O decoupling for scalable performance. UMap also uses application hints to improve the selection of caching, prefetching, and eviction policies. We evaluate UMap in five benchmarks and real applications on two systems. Our results show that leveraging application knowledge for page management could substantially improve performance. On average, UMap achieved 1.25 to 2.5 times improvement using the adapted configurations compared to the system service.

We present Metall, a persistent memory allocator designed to provide developers with an API to allocate custom C++ data structures in both block-storage and byte-addressable persistent memories (e.g., NVMe and Intel Optane DC Persistent Memory). Metall incorporates state-of-the-art allocation algorithms in Supermalloc with the rich C++ interface developed by Boost.Interprocess, and provides persistent memory snapshoting (versioning) capabilities. We demonstrate Metall processing large graphs in a variety of conditions and data-structure configurations, indicating a bright future for data-analytics leveraging emerging persistent memory technologies.

We update our prior 2017 Graph Challenge submission [7] on large scale triangle counting in distributed memory by demonstrating scaling and validation on trillion-edge scale-free graphs. We incorporate recent distributed communication optimizations developed for irregular communication workloads [1], and demonstrate scaling up to 1.5 million cores of IBM BG/Q Sequoia at LLNL. We validate our implementation using nonstochastic Kronecker graph generation where ground-truth local and global triangle counts are known, and model our Kronecker graph inputs after the Graph500 [5] R-MAT inputs. To our knowledge, our results are the largest triangle count experiments on synthetic scale-free graphs to date.

We describe a methodology for estimating edge-local triangle counts using cardinality approximation sketches. While the approach does not guarantee relative error bounds, we will show that it preserves triangle count heavy hitters - the edges incident upon the largest number of triangles - well in practice. Furthermore, we provide empirical evidence that the sum of edge-local estimations yield reasonable estimates of the global triangle count for free. In this paper we describe a two-pass algorithm for estimating edge-local triangle count heavy hitters. The algorithm requires time linear in the number of edges, memory almost linear in the number of vertices, and is easy to parallelize. We provide results on dozens of real-world and synthetic graphs.

We update our prior 2017 Graph Challenge submission [11] on large scale triangle counting in distributed memory by extending it to compute the full $k$ -truss decomposition [6] of large scale-free graphs. We build on heuristics to minimize ‘wedge checks', by operating on an ordered directed graph, and describe an algorithm to ‘unroll’ triangle counts when they are scheduled for pruning by the $k$ -truss decomposition. Our $k$ -truss algorithm is implemented using HavoqGT, an asynchronous vertex-centric graph analytics framework for distributed memory. We present a brief experimental evaluation on two large, real-world, scale-free graphs: a 128B edge web-graph and a 1.4B edge twitter follower graph. To our knowledge, the 128B edge web-graph is the largest real-world graph to have its $k$ -truss decomposition computed.

The eccentricity of a vertex is defined as the length of the longest shortest path to any other vertex. While eccentricity is an important measure of vertex centrality, directly computing exact eccentricity for all vertices on large-scale graphs is prohibitively costly. Takes and Kosters proposed an iterative algorithm that uses multiple runs of single-source shortest path (SSSP) to compute lower and upper bounds on eccentricity at every vertex. Their technique converges to exact eccentricity by performing SSSP from only a small percentage of vertices, when sources are efficiently selected. However, their source selection strategies do not always yield rapid convergence. We propose a pincer movement source selection algorithm that efficiently selects source vertices based on analysis of the lower and upper bounds produced by SSSP. We also leverage k-BFS, which runs breadth-first search (BFS) from multiple sources concurrently on HavoqGT, a high-performance vertex-centric message-passing graph processing framework, to achieve an additional significant performance improvement on distributed-memory systems. We demonstrate that our novel source vertex selection strategy has better performance on various real-world graph datasets compared with the previous strategy. In addition, we compute exact eccentricity for graphs with more than 1000X more edges (112B undirected edges) than graphs in the previous literature.

Researchers developing implementations of distributed graph analytic algorithms require graph generators that yield graphs sharing the challenging characteristics of real-world graphs (small-world, scale-free, heavy-tailed degree distribution) with efficiently calculable ground-truth solutions to the desired output. Reproducibility for current generators used in benchmarking are somewhat lacking in this respect due to their randomness: the output of a desired graph analytic can only be compared to expected values and not exact ground truth. Nonstochastic Kronecker product graphs meet these design criteria for several graph analytics. Here we show that many flavors of triangle participation can be cheaply calculated while generating a Kronecker product graph. Given two medium-sized scale-free graphs with adjacency matrices $A$ and $B$, their Kronecker product graph has adjacency matrix $C = A \otimes B$. Such graphs are highly compressible: $|{\cal E}|$ edges are represented in ${\cal O}(|{\cal E}|^{1/2})$ memory and can be built in a distributed setting from small data structures, making them easy to share in compressed form. Many interesting graph calculations have worst-case complexity bounds ${\cal O}(|{\cal E}|^p)$ and often these are reduced to ${\cal O}(|{\cal E}|^{p/2})$ for Kronecker product graphs, when a Kronecker formula can be derived yielding the sought calculation on $C$ in terms of related calculations on $A$ and $B$. We focus on deriving formulas for triangle participation at vertices, ${\bf t}_C$, a vector storing the number of triangles that every vertex is involved in, and triangle participation at edges, $\Delta_C$, a sparse matrix storing the number of triangles at every edge., Comment: 10 pages, 7 figures, IEEE IPDPS Graph Algorithms Building Blocks

Massive power-law graphs drive many fields: metagenomics, brain mapping, Internet-of-things, cybersecurity, and sparse machine learning. The development of novel algorithms and systems to process these data requires the design, generation, and validation of enormous graphs with exactly known properties. Such graphs accelerate the proper testing of new algorithms and systems and are a prerequisite for success on real applications. Many random graph generators currently exist that require realizing a graph in order to know its exact properties: number of vertices, number of edges, degree distribution, and number of triangles. Designing graphs using these random graph generators is a time-consuming trial-and-error process. This paper presents a novel approach that uses Kronecker products to allow the exact computation of graph properties prior to graph generation. In addition, when a real graph is desired, it can be generated quickly in memory on a parallel computer with no-interprocessor communication. To test this approach, graphs with $10^{12}$ edges are generated on a 40,000+ core supercomputer in 1 second and exactly agree with those predicted by the theory. In addition, to demonstrate the extensibility of this approach, decetta-scale graphs with up to $10^{30}$ edges are simulated in a few minutes on a laptop., Comment: 8 pages, 6 figures, IEEE IPDPS 2018 Graph Algorithm Building Blocks (GABB) workshop

On a GPU cluster, the ratio of high computing power to communication bandwidth makes scaling breadth-first search (BFS) on a scale-free graph extremely challenging. By separating high and low out-degree vertices, we present an implementation with scalable computation and a model for scalable communication for BFS and direction-optimized BFS. Our communication model uses global reduction for high-degree vertices, and point-to-point transmission for low-degree vertices. Leveraging the characteristics of degree separation, we reduce the graph size to one third of the conventional edge list representation. With several other optimizations, we observe linear weak scaling as we increase the number of GPUs, and achieve 259.8 GTEPS on a scale-33 Graph500 RMAT graph with 124 GPUs on the latest CORAL early access system., Comment: 12 pages, 13 figures. To appear at IPDPS 2018

We propose a new framework for parallelizing deep neural network training that maximize the amount of data that is ingested by the training algorithm. Our proposed framework called Livermore Tournament Fast Batch Learning (LTFB) targets large-scale data problems. The LTFB approach creates a set of Deep Neural Network (DNN) models and trains each instance of these models independently and in parallel. Periodically each model selects another model to pair with, exchanges models, and then run a local tournament against held-out tournament datasets. The winning model is will continue training on the local training datasets. This new approach maximizes computation and minimizes amount of synchronization required in training deep neural network, a major bottleneck in existing synchronous deep learning algorithms. We evaluate our proposed algorithm on two HPC machines at Lawrence Livermore National Laboratory including an early access IBM Power8+ with NVIDIA Tesla P100 GPUs machine. Experimental evaluations of the LTFB framework on two popular image classification benchmark: CIFAR10 [18] and ImageNet [19], show significant speed up compared to the sequential baseline.

Subgraph pattern matching is fundamental to graph analytics and has wide applications. Unfortunately, high computational complexity limits the robustness guarantees of existing algorithms: they do not scale for modern large graph datasets and/or they have limitations in terms of accuracy or in terms of the intricacy of the patterns supported. We present algorithms, theory, and empirical evidence that iteratively eliminating vertices that do not meet local constraints dramatically reduces the search space for pattern matching in real-world graphs, and demonstrate a scalable implementation of our algorithms. We additionally identify the characteristics of patterns for which every non-eliminated vertex participates in a match. These techniques are an essential step to enable scalable, practical solutions for robust pattern matching in large-scale labeled graphs.We demonstrate the advantages of the proposed approach through strong and weak scaling experiments on massive-scale real-world (up to 257 billion edges) and synthetic (up to 2.2 trillion edges) graphs and at scales (256 compute nodes with 6,144 processors) orders of magnitude larger than those used in the past for similar problems.

Triangle counting has long been a challenge problem for sparse graphs containing high-degree "hub" vertices that exist in many real-world scenarios. These high-degree vertices create a quadratic number of wedges, or 2-edge paths, which for brute force algorithms require closure checking or wedge checks. Our work-in-progress builds on existing heuristics for pruning the number of wedge checks by ordering based on degree and other simple metrics. Such heuristics can dramatically reduce the number of required wedge checks for exact triangle counting for both real and synthetic scale-free graphs. Our triangle counting algorithm is implemented using HavoqGT, an asynchronous vertex-centric graph analytics framework for distributed memory. We present a brief experimental evaluation on two large real scale-free graphs: a 128B edge web-graph and a 1.4B edge twitter follower graph, and a weak scaling study on synthetic Graph500 RMAT graphs up to 274.9 billion edges.

High-performance computing (HPC) systems are increasingly being used for data-intensive, or "Big Data", workloads. However, since traditional HPC workloads are compute-intensive, the HPC-Big Data convergence has created many challenges with optimizing data movement and processing on modern supercomputers. Our collaborative work addresses these challenges using a three-pronged approach: (i) measuring and modeling extreme-scale I/O workloads, (ii) designing a low-latency, scalable, on-demand burst-buffer solution, and (iii) optimizing graph algorithms for processing Big Data workloads. We describe the three areas of our collaboration and report on their respective developments.

We present DI-MMAP, a high-performance runtime that memory-maps large external data sets into an application's address space and shows significantly better performance than the Linux mmap system call. Our implementation is particularly effective when used with high performance locally attached Flash arrays on highly concurrent, latency-tolerant data-intensive HPC applications. We describe the kernel module and show performance results on a benchmark test suite, a new bioinformatics metagenomic classification application, and on a level-asynchronous Breadth-First Search (BFS) graph traversal algorithm. Using DI-MMAP, the metagenomics classification application performs up to 4× better than standard Linux mmap. A fully external memory configuration of BFS executes up to 7.44× faster than traditional mmap. Finally, we demonstrate that DI-MMAP shows scalable out-of-core performance for BFS traversal in main memory constrained scenarios. Such scalable memory constrained performance would allow a system with a fixed amount of memory to solve a larger problem as well as provide memory QoS guarantees for systems running multiple data-intensive applications.

In many graph applications, the structure of the graph changes dynamically over time and may require real time analysis. However, constructing a large graph is expensive, and most studies for large graphs have not focused on a dynamic graph data structure, but rather a static one. To address this issue, we propose DegAwareRHH, a high performance dynamic graph data store designed for scaling out to store large, scale-free graphs by leveraging compact hash tables with high data locality. We extend DegAwareRHH for multiple processes and distributed memory, and perform dynamic graph construction on large scale-free graphs using emerging 'Big Data HPC' systems such as the Catalyst cluster at LLNL. We demonstrate that DegAwareRHH processes a request stream 206.5x faster than a state-of-the-art shared-memory dynamic graph processing framework, when both implementations use 24 threads/processes to construct a graph with 1 billion edge insertion requests and 54 million edge deletion requests. DegAwareRHH also achieves a processing rate of over 2 billion edge insertion requests per second using 128 compute nodes to construct a large-scale web graph, containing 128 billion edges, the largest open-source real graph dataset to our knowledge.

Data-intensive problems challenge conventional computing architectures with demanding CPU, memory, and I/O requirements. Experiments with three benchmarks suggest that emerging hardware technologies can significantly boost performance of a wide range of applications by increasing compute cycles and bandwidth and reducing latency.

Recent successes of deep learning have been largely driven by the ability to train large models on vast amounts of data. We believe that High Performance Computing (HPC) will play an increasingly important role in helping deep learning achieve the next level of innovation fueled by neural network models that are orders of magnitude larger and trained on commensurately more training data. We are targeting the unique capabilities of both current and upcoming HPC systems to train massive neural networks and are developing the Livermore Big Artificial Neural Network (LBANN) toolkit to exploit both model and data parallelism optimized for large scale HPC resources. This paper presents our preliminary results in scaling the size of model that can be trained with the LBANN toolkit.

The publication of the Yahoo Flickr Creative Commons 100 Million dataset (YFCC100M)--to date the largest open-access collection of photos and videos--has provided a unique opportunity to stimulate new research in multimedia analysis and retrieval. To make the YFCC100M even more valuable, we have started working towards supplementing it with a comprehensive set of precomputed features and high-quality ground truth annotations. As part of our efforts, we are releasing the YLI feature corpus, as well as the YLI-GEO and YLI-MED annotation subsets. Under the Multimedia Commons Project (MMCP), we are currently laying the groundwork for a common platform and framework around the YFCC100M that (i) facilitates researchers in contributing additional features and annotations, (ii) supports experimentation on the dataset, and (iii) enables sharing of obtained results. This paper describes the YLI features and annotations released thus far, and sketches our vision for the MMCP.

The Placing Task is a yearly challenge offered by the MediaEval Multimedia Benchmarking Initiative that requires participants to develop algorithms that automatically predict the geo-location of social media videos and images. We introduce a recent development of a new standardized web-scale geo-tagged dataset for Placing Task 2014, which contains 5.5 million photos and 35,000 videos. This standardized benchmark with a large persistent dataset allows research community to easily evaluate new algorithms and to analyze their performance with respect to the state-of-the-art approaches. We discuss the characteristics of this year's Placing Task along with the description of the new dataset components and how they were collected.

At extreme scale, irregularities in the structure of scale-free graphs such as social network graphs limit our ability to analyze these important and growing datasets. A key challenge is the presence of high-degree vertices (hubs), that leads to parallel workload and storage imbalances. The imbalances occur because existing partitioning techniques are not able to effectively partition high-degree vertices. We present techniques to distribute storage, computation, and communication of hubs for extreme scale graphs in distributed memory supercomputers. To balance the hub processing workload, we distribute hub data structures and related computation among a set of delegates. The delegates coordinate using highly optimized, yet portable, asynchronous broadcast and reduction operations. We demonstrate scalability of our new algorithmic technique using Breadth-First Search (BFS), Single Source Shortest Path (SSSP), K-Core Decomposition, and Page-Rank on synthetically generated scale-free graphs. Our results show excellent scalability on large scale-free graphs up to 131K cores of the IBM BG/P, and outperform the best known Graph500 performance on BG/P Intrepid by 15%

Digitised version produced by the EUI Library and made available online in 2020.

Constant-amplitude, flexural-fatigue tests have been carried out over the frequency range 8–100 Hz and the temperature range 293–373°K on a commercial zinc-aluminium alloy of basically eutectoid composition. This alloy is highly superplastic at ∼530°K, when the strain-rate sensitivity of the flow stress index, m , ⋍0·5 . At 293°K some residual superplasticity exists and this manifests itself as a frequency effect in the fatigue behaviour. This effect is almost certainly the result of room-temperature, strainrate sensitivity; it is shown by the fact that when the superplastic microstructure is destroyed, the frequency effect disappears. Finally, it is shown that the model proposed by Morrow successfully predicts the fatigue life of this alloy.

The prediction of the yielding and flow behaviour of materials under complex stress systems from tensile test or other easily determined data has been the aim of engineers for many years. The yield criteria of Tresca and then Mises for isotropic metals are useful, but the realization that anisotropy is the rule rather than the exception, especially in sheet metals, led to the examination of Hill's anisotropic theory by various workers. In the present paper the stress-strain curves of various sheet metals are determined in uniaxial and balanced biaxial tension. As far as yielding behaviour is concerned, it is concluded that the theory is reasonably satisfactory for materials whose anisotropy is described with r > 1 , with certain anomalies for materials with r . As far as flow behaviour is concerned, the theory only applies for materials for r > 1 . Crossing of the uniaxial and biaxial curves is observed for certain metals at low strains and this is not predicted by the theory. More work is necessary on low -r materials to resolve these matters.

During the drawing of sheet metal between a die and a blankholder, compressive hoop stresses are developed which attempt to thicken or wrinkle the flange. Previous work on this behaviour has ignored any effects due to normal or planar plastic anisotropy. In this paper it is shown that the blankholder pressure necessary to suppress wrinkling increases with decreasing normal anisotropy ( r ) and increases with increasing planar anisotropy ( Δr ). The approximate plane strain conditions ( de z = 0 ) operating in the flange can be simulated by an edge-notched tensile specimen and this simulation demonstrates the effect of texture hardening and softening upon flange-wrinkling behaviour. The results obtained can be interpreted qualitatively by the use of anisotropic plasticity theory. The speed of drawing also affects wrinkling, in general, the number of wrinkles decreases with increasing drawing speed.

Measurements of the flow stress ( σ f ) and strain-rate sensitivity ( m ) over a wide range of strain rates (e) and at temperatures between 20°C and 300°C have been made on a range of SP alloys, basically the ZnAl eutectoid, (78 Zn-22 Al) but with additions of copper up to 1·0%, see Table 1. These additions do not significantly affect σ f or m above about 150°C. Again, the peak in the m vs. e curve is not displaced by these copper additions above about 150°C. The creep rate at room temperature decreases with increasing copper content and varies by a factor of about 140 between 0 and 1·0% copper. An empirical vacuum-forming test shows that copper at these concentrations has no effect on the vacuum-forming time at 250–260°C.

Previous work has shown that anisotropic plasticity theory does not hold for all metals. One of these metals was aluminium, and the purpose of the present work is to investigate this anomaly further by studying its behaviour in uniaxial and biaxial tension. The results of this investigation confirm the previous findings.

Sampling based motion planning methods have been highly successful in solving many high degree of freedom motion planning problems arising in diverse application domains such as traditional robotics, computer-aided design, and computational biology and chemistry. Recent work in metrics for sampling based planners provide tools to analyze the model building process at three levels of detail: sample level, region level, and global level. These tools are useful for comparing the evolution of sampling methods, and have shown promise to improve the process altogether [15], [17], [24]. Here, we introduce a filtering strategy for the Probabilistic Roadmap Methods (PRM) with the aim to improve roadmap construction performance by selecting only the samples that are likely to produce roadmap structure improvement. By measuring a new sample’s maximum potential structural improvement with respect to the current roadmap, we can choose to only accept samples that have an adequate potential for improvement. We show how this approach can improve the standard PRM framework in a variety of motion planning situations using popular sampling techniques.