BACKGROUND: Transcriptomic profiling technologies have advanced the analysis of biological and toxicological responses. However, substantial differences in probe design, dynamic range, gene coverage, and preprocessing pipelines across platforms introduce artifacts that limit cross-study integration and hinder the reuse of historical datasets. We aim to develop computational methods for accurate cross-platform translation to maximize the value of legacy resources. RESULTS: We present TransPlatformer a deep learning framework for translating gene expression profiles across heterogeneous toxicogenomics platforms. TransPlatformer employs a novel attention-based architecture to map high-dimensional fold-change vectors from legacy microarray technologies to current platforms. Models are trained and evaluated using DrugMatrix, spanning three technological generations. We investigate mixed-tissue, single-tissue, and cross-tissue training paradigms and benchmark performance against multilayer perceptron and matrix-completion baselines. In mixed-tissue training, TransPlatformer achieves a greater than 50% reduction in mean absolute error (0.043 vs. 0.09) and nearly doubles Pearson correlation (≈ 0.71 vs. 0.37) relative to baseline methods. Importantly, TransPlatformer preserves rare but biologically meaningful over- and under-expressed signals, with mean absolute error below 0.22. Single-tissue models yield further improvements for well-represented organs, such as a 10% reduction in liver mean absolute error, while underscoring the need for data augmentation strategies in low-sample tissues.ra CONCLUSIONS: TransPlatformer provides an effective and scalable computational solution for cross-platform transcriptomic translation. By enabling biologically faithful harmonization of gene expression data, the proposed approach facilitates the reuse of legacy toxicogenomics datasets, enhances downstream biomarker discovery, and supports more reproducible predictive modeling in toxicology.

Graph neural networks have emerged as a specialized branch of deep learning, designed to address problems where pairwise relations between objects are crucial. Recent advancements utilize graph convolutional neural networks to extract features within graph structures. Despite promising results, these methods face challenges in real-world applications due to sparse features, resulting in inefficient resource utilization. Recent studies draw inspiration from the mammalian brain and employ spiking neural networks to model and learn graph structures. However, these approaches are limited to traditional Von Neumann-based computing systems, which still face hardware inefficiencies. In this study, we present a fully neuromorphic implementation of spiking graph neural networks designed for Loihi 2. We optimize network parameters using Lava Bayesian Optimization, a novel hyperparameter optimization system compatible with neuromorphic computing architectures. We showcase the performance benefits of combining neuromorphic Bayesian optimization with our approach for citation graph classification using fixed-precision spiking neurons. Our results demonstrate the capability of integer-precision, Loihi 2 compatible spiking neural networks in performing citation graph classification with comparable accuracy to existing floating point implementations.

Graph neural networks (GNNs) have emerged as one of the most effective ML techniques for drug effect prediction from drug molecular graphs. Despite having immense potential, GNN models lack performance when using datasets that contain high-dimensional, asymmetrically co-occurrent drug effects as targets with complex correlations between them. Training individual learning models for each drug effect and incorporating every prediction result for a wide spectrum of drug effects are impractical. Therefore, an opportunity exists to address this challenge as multitarget prediction problems and predict all drug effects at a time. We developed standard and hybrid GNNs to perform two separate tasks: multiregression for continuous values and multilabel classification for categorical values contained in our datasets. Because multilabel classification makes the target data even more sparse and introduces asymmetric label co-occurrence, learning these models becomes difficult and heavily impacts the GNN's performance. To address these challenges, we propose a new data oversampling technique to improve multilabel classification performances on all the given imbalanced molecular graph datasets. Using the technique, we improve the data imbalance ratio of the drug effects while protecting the datasets' integrity. Finally, we evaluate the multilabel classification performance of the best-performing hybrid GNN model on all the oversampled datasets obtained from the proposed oversampling technique. In all the evaluation metrics (i.e., precision, recall, and F1 score), this model significantly outperforms other ML models, including GNN models when they are trained on the original datasets or oversampled datasets with MLSMOTE, which is a well-known oversampling technique.

Large language models (LLMs) have garnered significant attention in both the AI community and beyond. Among these, the Generative Pre-trained Transformer (GPT) has emerged as the dominant architecture, spawning numerous variants. However, these variants have undergone pre-training under diverse conditions, including variations in input data, data preprocessing, and training methodologies, resulting in a lack of controlled comparative studies. Here we meticulously examine two prominent open-sourced GPT architectures, GPT-NeoX and LLaMA, leveraging the computational power of Frontier, the world’s first Exascale supercomputer. Employing the same materials science text corpus and a comprehensive end-to-end pipeline, we conduct a comparative analysis of their training and downstream performance. Our efforts culminate in achieving state-of-the-art performance on a challenging materials science benchmark. Furthermore, we investigate the computation and energy efficiency, and propose a computationally efficient method for architecture design. To our knowledge, these pre-trained models represent the largest available for materials science. Our findings provide practical guidance for building LLMs on HPC platforms.

In this paper, we propose a novel metric to characterize drug molecules based on their interaction with genes, to tackle dimensionality challenges with the DrugMatrix toxicogenomics dataset. We developed a graph neural network (GNN) that is able to accurately predict this metric and produce informative graph-level vector representations that represent relative similarity between drug molecules, by capturing both structural and functional information of drug molecules. The GNN’s resulting embedding vector representations achieve better performance than both traditional fingerprint representations and the functional property data, in clustering tasks. With its demonstrated efficacy, there is potential for further advancements in the field of toxicogenomics and future applications of GNNs in high-dimensional data analysis.

Graph convolutional networks leverage both graph structures and features on nodes and edges for improved learning performance in comparison with classical machine learning approaches. Spiking neuromorphic computers natively implement network-like computation and have been shown to be successful at implementing graph learning without features. Incorporating graph features brings the challenge of efficient feature representation and balancing the contribution of topology and features in learning. In this work, we present our design of a simulated network of spiking neurons to perform semi-supervised learning on graph data using both the graph structure and the node features. We explore various design choices, present preliminary results, and discuss the opportunities for using neuromorphic computers for this task in the future.

We are motivated by newly proposed methods for mining large-scale corpora of scholarly publications (e.g., full biomedical literature), which consists of tens of millions of papers spanning decades of research. In this setting, analysts seek to discover relationships among concepts. They construct graph representations from annotated text databases and then formulate the relationship-mining problem as an all-pairs shortest paths (APSP) and validate connective paths against curated biomedical knowledge graphs (e.g., Spoke). In this context, we present Coast (Exascale Communication-Optimized All-Pairs Shortest Path) and demonstrate 1.004 EF/s on 9,200 Frontier nodes (73,600 GCDs). We develop hyperbolic performance models (HYPERMOD), which guide optimizations and parametric tuning. The proposed Coast algorithm achieved the memory constant parallel efficiency of 99% in the single-precision tropical semiring. Looking forward, Coast will enable the integration of scholarly corpora like PubMed into the Spoke biomedical knowledge graph.

This study aims to effectively analyze and visualize the concept to concept network derived from the COVID-19 Open Research Dataset (CORD-19) dataset, where we have more than 48,000 concepts with more than 300,000 relationships between concepts. In analyzing networks, we focus on finding relationship patterns between the coronavirus disease 2019 (COVID-19) concepts and other concepts. Given the node and edge datasets, we construct directional graphs and calculate all pair shortest paths based on multiple edge weight schemes. However, statistical metrics are not sufficient to identify specific relationships represented in the network. Therefore, we also propose a visual analytics approach to effectively understand the knowledge graph. Our highly interactive visual analytics allows users to effectively analyze the evolving graphs and (COVID-19) concept nodes and other nodes related to the COVID-19 nodes. We envision that this study will pave the path to develop strategies to provide more accurate and scalable predictive analysis on knowledge graphs related to CORD19 and other biomedical knowledge graphs.

Distributed learning is now routinely conducted on cloud as well as dedicated clusters. Training with elastic resources brings new challenges and design choices. Prior studies focus on runtime performance and assume a static algorithmic behavior. In this work, by analyzing the impact of of resource scaling on convergence, we introduce schedules for synchronous stochastic gradient descent that proactively adapt the number of learners to reduce training time and improve convergence. Our approach no longer assumes a constant number of processors throughout training. In our experiment, distributed stochastic gradient descent with dynamic schedules and reduction momentum achieves better convergence and significant speedups over prior static ones. Numerous distributed training jobs running on cloud may benefit from our approach.

BACKGROUND: Drug discovery is a multi-stage process that comprises two costly major steps: pre-clinical research and clinical trials. Among its stages, lead optimization easily consumes more than half of the pre-clinical budget. We propose a combined machine learning and molecular modeling approach that partially automates lead optimization workflow in silico, providing suggestions for modification hot spots. RESULTS: The initial data collection is achieved with physics-based molecular dynamics simulation. Contact matrices are calculated as the preliminary features extracted from the simulations. To take advantage of the temporal information from the simulations, we enhanced contact matrices data with temporal dynamism representation, which are then modeled with unsupervised convolutional variational autoencoder (CVAE). Finally, conventional and CVAE-based clustering methods are compared with metrics to rank the submolecular structures and propose potential candidates for lead optimization. CONCLUSION: With no need for extensive structure-activity data, our method provides new hints for drug modification hotspots which can be used to improve drug potency and reduce the lead optimization time. It can potentially become a valuable tool for medicinal chemists.

Drug discovery is a costly process of searching for new candidate medications. Among its various stages, lead optimization easily consumes more than half of the pre-clinical budget. We propose an automated lead optimization workflow that uses data mining methods in components such as execution of molecular simulations, feature extraction, and clustering with convolutional variational autoencoder. The end-to-end execution produces protein-ligand binding affinity of atoms in the lead molecule which serves as metrics for identifying modifiable atoms. In contrast to known methods, our method provides new hints for drug modification hotspots which can be used to improve drug efficacy. Our workflow can potentially reduce the lead optimization turnaround time from months/years to several days compared with the conventional labor-intensive process and thus will become a valuable tool for medical researchers.

Training large, deep neural network acoustic models for speech recognition on large datasets takes a long time on a single GPU, motivating research on parallel training algorithms. We present an approach for training a bidirectional LSTM acoustic model on the 2000-hour Switchboard corpus. The model we train achieves state-of-the-art word error rate, 7.5% on the Hub5-2000 Switchboard test set and 13.1% on the Callhome test set, and scales to an unprecedented 96 learners while employing only 12 global reductions per epoch of training. As our implementation incurs far fewer reductions than prior work, it does not require aggressively optimized communication primitives to reach state-of-the-art performance in a short amount of time. With 48 NVIDIA V100 GPUs training takes 5 hours; with 96 GPUs, training takes around 3 hours.

Data loading can dominate deep neural network training time on large-scale systems. We present a comprehensive study on accelerating data loading performance in large-scale distributed training. We first identify performance and scalability issues in current data loading implementations. We then propose optimizations that utilize CPU resources to the data loader design. We use an analytical model to characterize the impact of data loading on the overall training time and establish the performance trend as we scale up distributed training. Our model suggests that I/O rate limits the scalability of distributed training, which inspires us to design a locality-aware data loading method. By utilizing software caches, our method can drastically reduce the data loading communication volume in comparison with the original data loading implementation. Finally, we evaluate the proposed optimizations with various experiments. We achieved more than 30x speedup in data loading using 256 nodes with 1,024 learners.

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.

Detecting actions in videos requires understanding the temporal relationships among frames. Typical action recognition approaches rely on optical flow estimation methods to convey temporal information to a CNN. Recent studies employ 3D convolutions in addition to optical flow to process the temporal information. While these models achieve slightly better results than two-stream 2D convolutional approaches, they are significantly more complex, requiring more data and time to be trained. We propose an efficient, adaptive batch size distributed training algorithm with customized optimizations for training the two 2D streams. We introduce a new 2D convolutional temporal stream that is trained end-to-end with a neural network. The flexibility to freeze some network layers from training in this temporal stream brings the possibility of ensemble learning with more than one temporal streams. Our architecture that combines three streams achieves the highest accuracies as we know of on UCF101 and HMDB51 by systems that do not pretrain on much larger datasets (e.g., Kinetics). We achieve these results while keeping our spatial and temporal streams 4.67x faster to train than the 3D convolution approaches.

We adopt and analyze a synchronous K-step averaging stochastic gradient descent algorithm which we call K-AVG for solving large scale machine learning problems. We establish the convergence results of K-AVG for nonconvex objectives. Our analysis of K-AVG applies to many existing variants of synchronous SGD. We explain why the K-step delay is necessary and leads to better performance than traditional parallel stochastic gradient descent which is equivalent to K-AVG with $K=1$. We also show that K-AVG scales better with the number of learners than asynchronous stochastic gradient descent (ASGD). Another advantage of K-AVG over ASGD is that it allows larger stepsizes and facilitates faster convergence. On a cluster of $128$ GPUs, K-AVG is faster than ASGD implementations and achieves better accuracies and faster convergence for training with the CIFAR-10 dataset.

Due to the additional temporal dimension, large-scale video action recognition is even more challenging than image recognition and typically takes days to train on modern GPUs even for modest-sized datasets. We propose algorithms and techniques to accelerate training of deep neural networks for action recognition on a cluster of GPUs. In terms of convergence and scaling, our distributed training algorithm with adaptive batch size is provably superior to popular asynchronous stochastic gradient descent algorithms. The convergence analysis of our algorithm shows it is possible to reduce communication cost and at the same time minimize the number of iterations needed for convergence. We customize the Adam optimizer for our distributed algorithm to improve efficiency. In addition, we employ transfer-learning to further reduce training time while improving validation accuracy. Compared with the base-line single-GPU stochastic gradient descent implementation of the two-stream training approach, our implementation achieves super-linear speedups on 16 GPUs while improving validation accuracy. For the UCF101 and HMDB51 datasets, the validation accuracies achieved are 93.1% and 67.9% respectively. As far as we know, these are the highest accuracies achieved with the two-stream approach that does not involve computationally expensive 3D convolutions or pretraining on much larger datasets.

The training data and models are becoming increasingly large in many deep-learning applications. Large-scale distributed processing is employed to accelerate training. Increasing the number of learners in synchronous and asynchronous stochastic gradient descent presents challenges to convergence and communication performance. We present our hierarchical, bulk-synchronous stochastic gradient algorithm that effectively balances execution time and accuracy for training in deep-learning applications on GPU clusters. It achieves much better convergence and execution time at scale in comparison to asynchronous stochastic gradient descent implementations. When deployed on a cluster of 128 GPUs, our implementation achieves up to 56 times speedups over the sequential stochastic gradient descent with similar test accuracy for our target application.

Parallel and distributed processing is employed to accelerate training for many deep-learning applications with large models and inputs. As it reduces synchronization and communication overhead by tolerating stale gradient updates, asynchronous stochastic gradient descent (ASGD), derived from stochastic gradient descent (SGD), is widely used. Recent theoretical analyses show ASGD converges with linear asymptotic speedup over SGD. Oftentimes glossed over in theoretical analysis are communication overhead and practical learning rates that are critical to the performance of ASGD. After analyzing the communication performance and convergence behavior of ASGD using the Downpour algorithm as an example, we demonstrate the challenges for ASGD to achieve good practical speedup over SGD. We propose a distributed, bulk-synchronous stochastic gradient descent algorithm that allows for sparse gradient aggregation from individual learners. The communication cost is amortized explicitly by a gradient aggregation interval, and global reductions are used instead of a parameter server for gradient aggregation. We prove its convergence and show that it has superior communication performance and convergence behavior over popular ASGD implementations such as Downpour and EAMSGD for deep-learning applications.

The Computational Science and Engineering (CSE) area has earned prominence through advances in electronic and integrated technologies. Advanced computing systems permeate our daily life and have an increasingly importance in many aspects and domains. CSE is shaping future research and development activities in academia and industry, ranging from engineering, science, finance, economics, healthcare, arts, and humanitarian fields. The IEEE International Conference on CSE has been providing a series of highly successful International Conferences on CSE. The 2015 edition of CSE, CSE2015 (http://www.fe.up.pt/cse2015), was held in Porto, Portugal on October 21–23, 2015. It brought together computer scientists, industrial engineers, and researchers to discuss and exchange experimental and theoretical results, work-in-progress, experiences, case studies, and trend-setting ideas, in the areas of advanced computing for solving problems in science and engineering applications. The six extended papers included have been selected from a preliminary set of 12 papers submitted to this special issue and are briefly described as follows. The article ‘Robust resource allocations through performance modeling with stochastic process algebra’ 1 presents a new resource allocation scheme that uses a stochastic process algebra for obtaining resource allocations. These allocations are robust with respect to unpredictable perturbations of the application or system characteristics during runtime. The key idea is to translate performance models into mathematical Markov chain descriptions that can be numerically evaluated without requiring the time consuming simulation process used in competing approaches. A comparison with previous studies shows that the proposed approach achieves competitive results. In addition, process algebras are easier to reproduce because they require neither the effort for learning a simulation framework nor setup or installation cost. Beyond that, the computational efficiency of the approach also allows for embedding the proposed process algebra model into the runtime systems of a model-based framework that re-evaluates the resource assignment whenever a system or application parameter changes at runtime. The article ‘Heterogeneous CPU + GPU Approaches for Mesh Refinement over Lattice-Boltzmann Simulations’ 2 investigates strategies for mapping Lattice-Boltzmann method (LBM) simulations to compute nodes with CPUs and GPUs. The particular challenge addressed is finding an efficient way so that adaptive mesh refinement strategies use both computing resources effectively. While parallelism is abundant in LBM simulations, the challenge is to structure the workload distribution and data access to perform well on both CPU and GPU, which inherently favor different granularities of parallelism. The authors propose two approaches, a multi-domain approach that uses a finer grid in domains where a higher resolution is required; and an irregular grid approach that uses a single Cartesian with non-uniform spacing. Both approaches (multi-domain and irregular grid) are implemented and evaluated for a system comprising a Xeon E5 CPU and an NVidia K20c GPU using either only the GPU or CPU + GPU for the LBM computation. The evaluation shows that the multi-domain approach allows for executing bigger simulations because it requires fewer lattice nodes. The irregular grid approach is easier to implement and delivers a higher throughput (million fluid lattice cell updates per second). For both methods, the CPU + GPU implementation outperforms the homogeneous GPU implementation by 10–30%. The article ‘Methods to Model and Simulate Super Carbon Nanotubes of Higher Order’ 3 presents a new, efficient approach based on graph algebra to simulate the mechanical behavior of super carbon nanotubes (SCNTs). Representing the SCNTs as directed graphs, the authors propose a new data structure that exploits the hierarchy of SCNTs for fast queries. In addition, they propose a novel, iterative solver using the conjugate gradient method. Exploiting the symmetry of SCNTs of order 0, the solver is able to drastically reduce the amount of required calculations and memory for small deformations. Further exploiting structural symmetry and adopting an improved proximity-aware Matrix–vector-Multiplication routine, the performance for SCNTs level 0 can be improved by an additional factor of 2. Up to 4.4 times speedup is achieved when running in parallel on a 16 core SMP system. The authors also explore optimizations for symmetry in SCNTs of order 1. Experimental results show that the new approach outperforms a compressed-row-storage-based reference solver, for SCNTs of order 0 and 1, regardless of deformation, and with much less memory consumption. Because in practice memory consumption is oftentimes the limiting factor for scaling, this approach can significantly expand the realm of feasible simulations for SCNTs. In the article, the readers can also find introductions to the basic mathematical formulations and algorithms for simulating SCNTs as well as a brief summary of previous results. The article ‘Combinatorial Optimization of DNA Sequence Analysis on Heterogeneous Systems’ 4 presents an experimental study of counting the occurrences of query patterns in DNA sequences in parallel. DNA sequence analysis has many important practical applications, and is both data and computation intensive. The authors parallelize the Aho Corasick pattern matching algorithm, and explore its execution on heterogeneous systems, such as Intel Xeon E5 with Xeon Phi as co-processor, for acceleration. To achieve maximal performance on heterogeneous systems, the authors employ simulated annealing to determine the number of threads, thread affinities, and data placement on the host and the accelerator as such configuration is critical to performance and system utilization. Using real-world DNA sequences, the authors evaluate the efficiency of their approach. They show that the average speedup achieved is 1.6 times compared against the host-only parallelization and 2 times against device-only parallelization. The article ‘Using Adaptive Runtime Filtering to Support an Event-based Performance Analysis’ 5 presents an approach to filter tracing data in the context of event-based monitoring for performance improvements. The approach is based on self-guided filters that automatically adapt to an application's runtime behavior and are able to reduce performance data to manageable sizes for large-scale parallel applications and long execution programs. The article presents four runtime filters, each one targeting a specific type of data redundancy. They evaluate their approach with five real-world applications from different scientific domains. Compared to the default settings, their filters achieve a data size reduction of two orders of magnitude while increasing execution time regarding the overhead of tracing by less than one percent on average. The article also examines the influence of filtering on the performance analysis and identifies its limitations and presents three schemes to help performance analysts to correctly interpret filtered traces or even reconstruct parts of a filtered trace. The article ‘Automatic source-to-source error compensation of floating-point programs: code synthesis to optimize accuracy and time’ 6 presents a source-to-source C compiler approach for automatically improving the numerical accuracy of floating-point programs without significantly increasing execution time. The approach is based on the automatic compensation of floating-point operations by applying error-free transformations, and on the synthesis of code for both accuracy and execution time criteria. The use of partial compensation is proposed in order to trade-off performance and accuracy. The article also presents a number of code transformations to increase accuracy and to tune the impact on execution time. In addition, the authors present a method to find the best transformation satisfying execution time or accuracy constraints. The approach presented is evaluated with a number of case studies using two target computing environments and is able to produce some compensated algorithms as accurate and efficient as the ones derived by hand. We would like to acknowledge the authors of the articles included in this special issue for the hard work on preparing high-quality papers, the work of the anonymous reviewers on providing very important insights and suggestions that undoubtedly helped authors to improve their papers, and the support of the CCPE editors, Geoffrey C. Fox and David W. Walker.

We present our study of solving large unit commitment problems in the California ISO planning model. The model calculates hourly day-ahead unit commitments, and all instances need to be solved close to optimality within an hour. It takes CPLEX, the current state-of-the-art solver, up to 5 and 10 hours to solve the deterministic instances and the 5-scenario stochastic instances, respectively. The 20-scenario instances are practically unsolvable as no feasible solutions are found after 24 hours.We consider improving solution times through distributed-memory parallelization. Prior techniques such as distributed branch- and-bound perform poorly for our problems. We propose coordinated concurrent search to solve the deterministic instances on a cluster. For stochastic instances, we propose parallelization strategy that combines scenario-based decomposition and asynchronous solves guided by intermediate results from progressive hedging. Our decomposition creates linear sub problems instead of quadratic ones that are oftentimes intractable. On a cluster of 16 IBM Power7 machines, our parallel implementation achieves on average 12.7 and 22 times speedup for the deterministic instances and the 5-scenario stochastic instances, respectively. All problems are solved within an hour to near optimality including the previously unsolvable 20-scenario stochastic instances.

Large-scale graph processing is an increasingly important workload in modern systems. Conventional systems are usually optimized for locality of memory references, using caches and parallelization techniques to cover long memory latencies. However since graphs are distributed over memory in unpredictable manner, their processing does not exhibit great locality. While graph algorithms have plenty of parallelism, they are not easily amenable for effective vectorization, as the memory references are scattered all over. What is needed is a paradigm to specify a number of parallel tasks, each of which performs a short computation near the memory and a mechanism to efficiently execute them. In this paper, we propose a novel computational model that is memory-centric: the computation is organized as a collection of functions, each of which operates on a specific piece of data and is executed close to the memory where it resides. Basic primitives are provided to orchestrate the flow, synchronization and execution of the functions at their respective data points to accomplish a global task. We propose a scalable architecture to execute this computational model. We simulate an implementation of this architecture to compare the performance of running some graph algorithms on it with observed performance when the same algorithms were run on conventional systems. Preliminary results for a few graph algorithms show our approach is very promising in improving the performance of graph algorithms.

The erratic memory access pattern of graph algorithms makes it hard to optimize on cache-based architectures. While multithreading hides memory latency, it is unclear how hardware threads combined with caches impact the performance of typical graph workload. As modern architectures strike different balances between caching and multithreading, it remains an open question whether the benefit of optimizing locality behavior outweighs the cost. We study parallel graph algorithms on two different multi-threaded, multi-core platforms, that is, IBM Power7 and Sun Niagara2. Our experiments first demonstrate their performance advantage over prior architectures. We find nonetheless the number of hardware threads in either platform is not sufficient to fully mask memory latency. Our cache-friendly scheduling of memory accesses improves performance by up to 2.6 times on Power7 and prior cache-based architectures, yet the same technique significantly degrades performance on Niagara2. Software prefetching and manipulating the storage of the input to improve spatial locality improve performance by up to 2.1 times and 1.3 times on both platforms. Our study reveals interesting interplay between architecture and algorithm.

Deploying an application onto a target platform for high performance oftentimes demands manual tuning by experts. As machine architecture gets increasingly complex, tuning becomes even more challenging and calls for systematic approaches. In our earlier work we presented a prototype that combines efficiently expert knowledge, static analysis, and runtime observation for bottleneck detection, and employs refactoring and compiler feedback for mitigation. In this study, we develop a software tool that facilitates \emph{fast} searching of bottlenecks and effective mitigation of problems from major dimensions of computing (e.g., computation, communication, and I/O). The impact of our approach is demonstrated by the tuning of the LBMHD code and a Poisson solver code, representing traditional scientific codes, and a graph analysis code in UPC, representing emerging programming paradigms. In the experiments, our framework detects with a single run of the application intricate bottlenecks of memory access, I/O, and communication. Moreover, the automated solution implementation yields significant overall performance improvement on the target platforms. The improvement for LBMHD is up to 45\%, and the speedup for the UPC code is up to 5. These results suggest that our approach is a concrete step towards systematic tuning of high performance computing applications.

Memory access latency is often a crucial performance limitation for high performance computing. Prefetching is one of the strategies used by system designers to bridge the processor-memory gap. This paper describes a new innovative list prefetching feature introduced in the IBM Blue Gene/Q supercomputer. The list prefetcher records the L1 cache miss addresses and prefetches them in the next iteration. The evaluation shows this list prefetching mechanism reduces data fetching time when L1 cache misses happen and improves the performance for high performance computing applications with repeating nonuniform memory access patterns. Its performance is compatible with classic stream prefetcher when properly configured.

High productivity is critical in harnessing the power of high-performance computing systems to solve science and engineering problems. It is a challenge to bridge the gap between the hardware complexity and the software limitations. Despite significant progress in programming language, compiler, and performance tools, tuning an application remains largely a manual task, and is done mostly by experts. In this paper, we propose a systematic approach toward automated performance analysis and tuning that we expect to improve the productivity of performance debugging significantly. Our approach seeks to build a framework that facilitates the combination of expert knowledge, compiler techniques, and performance research for performance diagnosis and solution discovery. With our framework, once a diagnosis and tuning strategy has been developed, it can be stored in an open and extensible database and thus be reused in the future. We demonstrate the effectiveness of our approach through the automated performance analysis and tuning of two scientific applications. We show that the tuning process is highly automated, and the performance improvement is significant.

The erratic memory access pattern makes it hard to implement fast large-scale graph analysis. Although algorithms of fine-grain parallelism seem to benefit from multithreading, it is unclear whether the long memory latency of such workload is fully masked on current systems, and if not, whether improving locality brings any performance benefit, especially when the cache is simple. We optimize several fundamental graph algorithms on a multi-threaded, multi-core platform, with simple caches. Although the naive implementation scales, we show nonetheless the number of hardware threads is insufficient to fully mask the memory latency for typical graph analysis workload and the processor is unlikely to be fully utilized. In optimizing for cache performance, we show that known cache-friendly designs that prove effective on traditional architectures do not perform well on this platform. We explore low-cost measures such as software prefetching and manipulating the storage of the input to improve performance. Our results show that compared with the original implementation speedups between 10% and 200% are achieved at different number of threads with our optimization.

Due to the memory intensive workload and the erratic access pattern, irregular graph algorithms are notoriously hard to implement and optimize for high performance on distributed-memory systems. Although the PGAS paradigm proposed recently improves ease of programming, no high performance PGAS implementation of large-scale graph analysis is known. We present the first fast PGAS implementation of graph algorithms for the connected components and minimum spanning tree problems. By improving memory access locality, compared with the naive implementation, our implementation exhibits much better communication efficiency and cache performance on a cluster of SMPs. With additional algorithmic and PGASspecific optimizations, our implementation achieves significant speedups over both the best sequential implementation and the best single-node SMP implementation for large, sparse graphs with more than a billion edges.

Abstract It is critical to understand the workload characteristics and resource usage patterns of available applications to guide the design and development of hardware and software stacks of future machines. In this article, we analyze the workload performance characteristics of three large‐scale DARPA HPCS benchmarks: Hybrid Coordinate Ocean Model, Parallel Ocean Program, and Lattice Boltzemann Magneto‐Hydrodynamics Code while executing on IBM Power5+ processor machines. Our analysis is focused on the CPU/memory performance using Cycles Per Instruction (CPI) model and multiprocess communication performance using MPI traces. For each benchmark, we provide a high‐level performance analysis followed by the hotspot analysis for selected input parameters. Then we present a detailed workload performance characterization using CPI model with data from a unique set of performance counters available on the Power5+ processor system. From communication performance analysis, we describe the sources of load imbalances in the applications and identify the potential impediments to the scalability of the applications under large processor counts. We identify several sources of performance problems that are potential bottlenecks and discuss methods to ameliorate them. We also present a comparative analysis of these benchmarks to summarize the similarities and differences in their performance characteristics. Copyright © 2009 John Wiley & Sons, Ltd.

As part of the DARPA sponsored high productivity computing systems (HPCS) program, IBM is building petaflop supercomputers that will be fast, power-efficient, and easy to program. In addition to high performance, high productivity to the end user is another prominent goal. The challenge is to develop technologies that bridge the productivity gap - the gap between the hardware complexity and the software limitations. In addition to language, compiler, and runtime research, powerful and user-friendly performance tools are critical in debugging performance problems and tuning for maximum performance. Traditional tools have either focused on specific performance aspects (e.g., communication problems) or provided limited diagnostic capabilities, and using them alone usually do not pinpoint accurately performance problems. Even fewer tools attempt to provide solutions for problems detected. In our study, we develop an open framework that unifies tools, compiler analysis, and expert knowledge to automatically analyze and tune the performance of an application. Preliminary results demonstrated the efficiency of our approach.

It is critical to understand the workload characteristics and resource usage patterns of available applications to guide the design and development of hardware and software stacks of the future machines. In this paper, we analyze the workload performance characteristics of three large-scale DARPA HPCS benchmarks: HYCOM, POP, and LBMHD while executing on IBM Power5+ processor machines. Our analysis is focused on CPU/memory performance using cycles per instruction (CPI) model and multiprocess communication performance using MPI traces. For each benchmark, we provide a high level performance analysis followed by the hot-spot analysis of codes for selected input parameters.Then we present a detailed workload performance characterization using CPI model with data from a unique set of performance counters available on the Power5+ processor system. For communication, we describe the sources of load imbalances in the applications and identify the potential impediments to scalability of the applications under large processor counts.We identify several sources of performance problems that are potential bottlenecks and discuss methods to ameliorate them.

Solving large, irregular graph problems efficiently is challenging. Current software systems and commodity multiprocessors do not support fine-grained, irregular parallelism well. We present XWS, the X10 Work Stealing framework, an open-source runtime for the parallel programming language X10 and a library to be used directly by application writers. XWS extends the Cilk work-stealing framework with several features necessary to efficiently implement graph algorithms, viz., support for improperly nested procedures, global termination detection, and phased computation. We also present a strategy to adaptively control the granularity of parallel tasks in the work-stealing scheme, depending on the instantaneous size of the work queue. We compare the performance of the XWS implementations of spanning tree algorithms with that of the hand-written C and Cilk implementations using various graph inputs. We show that XWS programs (written in Java) scale and exhibit comparable or better performance.

In this paper, we present the architecture design and implementation of a framework for automated performance bottleneck detection. The framework analyzes the time-spent distribution in the application and discovers the performance bottlenecks by using given bottleneck definitions. The user can query the application execution performance to identify performance problems. The design of the framework is flexible and extensible so it can be tailored based on the actual application execution environment and performance tuning requirement. To demonstrate the usefulness of the framework, we apply the framework on a practical DARPA application and show how it helps to identify performance bottlenecks. The framework helps to automate the performance tuning process and improve the user’s productivity.

Large-scale data science applications require manipulating large graphs distributed across multiple processors. In this paper we present our experimental study of an asynchronous, distributed spanning tree algorithm that handles the challenging random, sparse graphs with billions of vertices. With a constant number of barriers, our implementation scales to 1024 processors on a cluster of SMPs. Our algorithm sheds new light on the design and implementation of graph algorithms on distributed-memory machines.

We present some preliminary results of selective profiling in our efforts towards automatic performance tuning for scientific codes. Performance analysis and tuning are becoming very important with the increasing complexity and speed of high performance systems. Great efforts are necessary to tune applications for optimal performance on such systems. In our efforts to automate most, if not all, of the performance tuning process, we developed a flexible profiling tool that can quickly pinpoint the performance bottlenecks and further refine the problem area. This is an important first step in our open framework with a rule-based approach for our ongoing PERCS project.

Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent accesses to global data structures with low degrees of locality. The hierarchical memory systems of symmetric multiprocessor (SMP) clusters optimize for local, contiguous memory accesses, and so are inefficient platforms for such algorithms. Few parallel graph algorithms outperform their best sequential implementation on SMP clusters due to long memory latencies and high synchronization costs. In this paper, we consider the performance and scalability of two graph algorithms, list ranking and connected components, on two classes of shared-memory computers: symmetric multiprocessors such as the Sun Enterprise servers and multithreaded architectures (MTA) such as the Cray MTA-2. While previous studies have shown that parallel graph algorithms can speedup on SMPs, the systems' reliance on cache microprocessors limits performance. The MTA's latency tolerant processors and hardware support for fine-grain synchronization makes performance a function of parallelism. Since parallel graph algorithms have an abundance of parallelism, they perform and scale significantly better on the MTA. We describe and give a performance model for each architecture. We analyze the performance of the two algorithms and discuss how the features of each architecture affects algorithm development, ease of programming, performance, and scalability.

Many parallel algorithms for graph problems start with finding a spanning tree and rooting the tree to define some structural relationship on the vertices which can be used by following problem specific computations. The generic procedure is to find an unrooted spanning tree and then root the spanning tree using the Euler tour technique. With a randomized work-time optimal unrooted spanning tree algorithm and work-time optimal list ranking, finding rooted spanning trees can be done work-time optimally on EREW PRAM w.h.p. Yet the Euler tour technique assumes as "given" a circular adjacency list, it is not without implications though to construct the circular adjacency list for the spanning tree found on the fly by a spanning tree algorithm. In fact our experiments show that this "hidden" step of constructing a circular adjacency list could take as much time as both spanning tree and list ranking combined. We present new efficient algorithms that find rooted spanning trees without using the Euler tour technique and incur little or no overhead over the underlying spanning tree algorithms. We also present two new approaches that construct Euler tours efficiently when the circular adjacency list is not given. One is a deterministic PRAM algorithm and the other is a randomized algorithm in the symmetric multiprocessor (SMP) model. The randomized algorithm takes a novel approach for the problems of constructing the Euler tour and rooting a tree. It computes a rooted spanning tree first, then constructs an Euler tour directly for the tree using depth-first traversal. The tour constructed is cache-friendly with adjacent edges in the tour stored in consecutive locations of an array so that prefix-sum (scan) can be used for tree computations instead of the more expensive list-ranking.

Summary form only given. We focus on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the building block for many other parallel graph algorithms and also because it is representative of a large class of irregular combinatorial problems that have simple and efficient sequential implementations and fast PRAM algorithms, but often have no known efficient parallel implementations. Experimental studies have been conducted on related problems (minimum spanning tree and connected components) using parallel computers, but only achieved reasonable speedup on regular graph topologies that can be implicitly partitioned with good locality features or on very dense graphs with limited numbers of vertices. We present a new randomized algorithm and implementation with superior performance that for the first-time achieves parallel speedup on arbitrary graphs (both regular and irregular topologies) when compared with the best sequential implementation for finding a spanning tree. This new algorithm uses several techniques to give an expected running time that scales linearly with the number p of processors for suitably large inputs (n>p/sup 2/). As the spanning tree problem is notoriously hard for any parallel implementation to achieve reasonable speedup, our study may shed new light on implementing PRAM algorithms for shared-memory parallel computers. The source code for these algorithms is freely-available from our Web site hpc.ece.unm.edu. This work was supported in part by NSF Grants CAREER ACI-00-93039, ITR ACI-00-81404, DEB-99-10123, ITR EIA-01-21377, Biocomplexity DEB-01-20709, and ITR EF/BIO 03-31654.

Summary form only given. Minimum spanning tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Most of the previous attempts for improving the speed of MST using parallel computing are too complicated to implement or perform well only on special graphs with regular structure. We design and implement four parallel MST algorithms (three variations of Boruvka plus our new approach) for arbitrary sparse graphs that for the first time give speedup when compared with the best sequential algorithm. In fact, our algorithms also solve the minimum spanning forest problem. We provide an experimental study of our algorithms on symmetric multiprocessors such as IBM's p690/Regatta and Sun's Enterprise servers. Our new implementation achieves good speedups over a wide range of input graphs with regular and irregular structures, including the graphs used by previous parallel MST studies. For example, on an arbitrary random graph with IM vertices and 20M edges, our new approach achieves a speedup of 5 using 8 processors. The source code for these algorithms is freely-available from our Web site hpc.ece.unm.edu. This work was supported in part by NSF Grants CAREER ACI-00-93039, ITR ACI-00-81404, DEB-99-10123, ITR EIA-01-21377, Biocomplexity DEB-01-20709, and ITR EF/BIO 03-31654.