nils-herrmann/clean_scirepeval huggingface dataset:
Evaluation of Cache-based Superscalar and Cacheless Vector Architectures for Scientific Computations

The growing gap between sustained and peak performance for s cientific applications is a well-known problem in high end computing. The recent development of par allel vector systems offers the potential to bridge this gap for many computational science codes and d eliver a substantial increase in computing capabilities. This paper examines the intranode perfor mance of the NEC SX-6 vector processor and the cache-based IBM Power3/4 superscalar architecture s ac oss a number of scientific computing areas. First, we present the performance of a microbenchmar k suite that examines low-level machine characteristics. Next, we study the behavior of the NAS Para llel Benchmarks. Finally, we evaluate the performance of several scientific computing codes. Results demonstrate that the SX-6 achieves high performance on a large fraction of our applications and ofte n significantly outperforms the cache-based architectures. However, certain applications are not easi ly menable to vectorization and would require extensive algorithm and implementation reengineering to u tilize the SX-6 effectively.
Tools and Techniques for Measuring and Improving Grid Performance

To better utilize its vast collection of heterogeneous resources that are geographically distributed across the United States, NASA is constructing a computational grid called the Information Power Grid (IPG). This paper describes various tools and techniques that we are developing to measure and improve the performance of a broad class of NASA applications when run on the IPG. In particular, we are investigating the areas of grid benchmarking, grid monitoring, user-level application scheduling, and decentralized system-level scheduling.
Parallel Computing Strategies for Irregular Algorithms

Author(s): Biswas, Rupak; Oliker, Leonid; Shan, Hongzhang |  Parallel computing promises several orders of magnitude increase in our ability to solve realistic computationally intensive problems, but relies on their efficient mapping and execution on large-scale multiprocessor architectures. Unfortunately, many important applications are irregular and dynamic in nature, making their effective parallel implementation a daunting task. Moreover, with the proliferation of parallel architectures and programming paradigms, the typical scientist is faced with a plethora of questions that must be answered in order to obtain an acceptable parallel implementation of the solution algorithm. In this paper, we consider three representative irregular applications: unstructured remeshing, sparse matrix computations, and N-body problems, and parallelize them using various popular programming paradigms on a wide spectrum of computing platforms ranging from state-of-the-art supercomputers to PC clusters. We present the underlying problems, the solution algorithms, and the parallel implementation strategies. Smart load-balancing, partitioning, and ordering techniques are used to enhance parallel performance. Overall results demonstrate the complexity of efficiently parallelizing irregular algorithms.
Memory-intensive benchmarks: IRAM vs. cache-based machines

The increasing gap between processor and memory performance has led to new architectural models for memory-intensive applications. In this paper, we use a set of memory-intensive benchmarks to evaluate a mixed logic and DRAM processor called VIRAM as a building block for scientific computing. For each benchmark, we explore the fundamental hardware requirements of the problem as well as alternative algorithms and data structures that can help expose fine-grained parallelism or simplify memory access patterns. Results indicate that VIRAM is significantly faster than conventional cache-based machines for problems that are truly limited by the memory system and that it has a significant power advantage across all the benchmarks.
Graph partitioning for parallel applications in heterogeneous Grid environments

The problem of partitioning irregular graphs for parallel computations on homogeneous systems has been extensively studied. However these solutions fail when the target system architecture exhibits heterogeneity in resource characteristics. With the emergence of technologies such as the Grid, it is imperative to study the partitioning problem in the context of distributed heterogeneous systems. In our Grid model, the system consists of processors with varying computational power that are connected via a non-uniform communication network. We present a novel multilevel partitioning algorithm, called MiniMax, for irregular graphs that takes into account issues pertinent to Grid computing environments. The proposed scheme generates and maps partitions onto a heterogeneous system with the objective of minimizing the maximum execution time of the parallel distributed application. Simulation results for both synthetic and real workloads demonstrate that MiniMax generates high quality partitions for various classes of applications targeted for parallel execution in a distributed heterogeneous environment.
MinEX: a latency-tolerant dynamic partitioner

The information power grid (IPG) being developed by NASA is designed to harness, the power of geographically distributed computers, databases, and human expertise, in order to solve large-scale realistic computational problems. This type of a metacomputing infrastructure is necessary to present a unified virtual machine to application developers that hides the intricacies of a highly heterogeneous environment and yet maintains adequate security. In this paper, we present a novel latency-tolerant partitioning scheme, called MinEX, that dynamically balances processor workloads while minimizing data movement and runtime communication, for applications that are executed in a parallel distributed fashion on the IPG. The number of IPG nodes, the number of processors per node, and the interconnect speeds are parameterized in a simulation experiment to derive conditions under which the IPG would be suitable for solving such applications. Experimental results demonstrate that MinEX is an effective load balancer for the IPG when the nodes are connected by a high-speed asynchronous interconnection network.
A de-centralized scheduling and load balancing algorithm for heterogeneous grid environments

In the past two decades, numerous scheduling and load balancing techniques have been proposed for locally distributed multiprocessor systems. However they all suffer from significant deficiencies when extended to a Grid environment: some use a centralized approach that renders the algorithm unscalable, while others assume the overhead involved in searching for appropriate resources to be negligible. Furthermore, classical scheduling algorithms do not consider a Grid node to be N-resource rich and merely work towards maximizing the utilization of one of the resources. In this paper, we propose a new scheduling and load balancing algorithm for a generalized Grid model of N-resource nodes that not only takes into account the node and network heterogeneity, but also considers the overhead involved in coordinating among the nodes. Our algorithm is decentralized, scalable, and overlaps the node coordination time with that of the actual processing of ready jobs, thus saving valuable clock cycles needed for making decisions. The proposed algorithm is studied by conducting simulations using the Message Passing Interface (MPI) paradigm.
A latency-tolerant partitioner for distributed computing on the information power grid

NASA's Information Power Grid (IPG) is an infrastructure designed to harness the power of geographically distributed computers, databases and human expertise, in order to solve large-scale realistic computational problems. This type of a metacomputing environment is necessary to present a unified virtual machine to application developers that hides the intricacies of a highly heterogeneous environment and yet maintains adequate security. In this paper, we present a novel partitioning scheme, called MinEX, that dynamically balances processor workloads while minimizing data movement and runtime communication, for applications that are executed in a parallel distributed fashion on the IPG. Experimental results show that MinEX is an effective load balancer in a distributed IPG environment.
High-performance Java codes for computational fluid dynamics

The computational science community is reluctant to write large-scale computationally-intensive applications in Java due to concerns over Java's poor performance, despite the claimed software engineering advantages of its object-oriented features. Naive Java implementations of numerical algorithms can perform poorly compared to corresponding Fortran or C implementations. To achieve high performance, Java applications must be designed with good performance as a primary goal. This paper presents the object-oriented design and implementation of two real-world applications from the field of Computational Fluid Dynamics (CFD): a finite-volume fluid flow solver (LAURA, from NASA Langley Research Center), and an unstructured mesh adaptation algorithm (2D_TAG, from NASA Ames Research Center). This work builds on our previous experience with the design of high-performance numerical libraries in Java. We examine the performance of the applications using the currently available Java infrastructure and show that the Java version of the flow solver LAURA performs almost within a factor of 2 of the original procedural version. Our Java version of the mesh adaptation algorithm 2D_TAG performs within a factor of 1.5 of its original procedural version on certain platforms. Our results demonstrate that object-oriented software design principles are not necessarily inimical to high performance.
Design Strategies for Irregularly Adapting Parallel Applications

Achieving scalable performance for dynamic irregular applications is eminently challenging. Traditional message-passing approaches have been making steady progress towards this goal; however, they suffer from complex implementation requirements. The use of a global address space greatly simplifies the programming task, but can degrade the performance of dynamically adapting computations. In this work, we examine two major classes of adaptive applications, under five competing programming methodologies and four leading parallel architectures. Results indicate that it is possible to achieve message-passing performance using shared-memory programming techniques by carefully following the same high level strategies. Adaptive applications have computational work loads and communication patterns which change unpredictably at runtime, requiring dynamic load balancing to achieve scalable performance on parallel machines. Efficient parallel implementations of such adaptive applications are therefore a challenging task. This work examines the implementation of two typical adaptive applications, Dynamic Remeshing and N-Body, across various programming paradigms and architectural platforms. We compare several critical factors of the parallel code development, including performance, programmability, scalability, algorithmic development, and portability.
Design of Unstructured Adaptive (UA) NAS Parallel Benchmark Featuring Irregular, Dynamic Memory Accesses

We describe the design of a new method for the measurement of the performance of modern computer systems when solving scientific problems featuring irregular, dynamic memory accesses. The method involves the solution of a stylized heat transfer problem on an unstructured, adaptive grid. A Spectral Element Method (SEM) with an adaptive, nonconforming mesh is selected to discretize the transport equation. The relatively high order of the SEM lowers the fraction of wall clock time spent on inter-processor communication, which eases the load balancing task and allows us to concentrate on the memory accesses. The benchmark is designed to be three-dimensional. Parallelization and load balance issues of a reference implementation will be described in detail in future reports.
Task assignment heuristics for distributed CFD applications

This paper proposes a task graph (TG) model to represent a single discrete step of a computational fluid dynamics (CFD) application. The TG model is then used to predict the performance of a set of task assignment heuristics developed based on the constraints inherent in the CFD problem. Two primitive assignments, the Largest Task First and the Minimum Task First, are systematically enhanced by the integration of the status of the processing units and communication costs. Evaluation is performed on a synthetic TG with tasks defined in terms of the number of gridpoints in predetermined grid zones. A realistic problem with eight million gridpoints is also used as a test case.
Message passing vs. shared address space on a cluster of SMPs

The emergence of scalable computer architectures using clusters of PCs (or PC-SMPs) with commodity networking has made them attractive platforms for high-end scientific computing. Currently, message passing (MP) and shared address space (SAS) are the two leading programming paradigms for these systems. MP has been standardized with MPI, and is the most common and mature parallel programming approach. However, MP code development can be extremely difficult, especially for irregularly structured computations. SAS offers substantial ease of programming, but may suffer from performance limitations due to poor spatial locality and high protocol overhead. In this paper, we compare the performance of and programming effort required for six applications under both programming models on a 32-CPU PC-SMP cluster. Our application suite consists of codes that typically do not exhibit scalable performance under shared-memory programming due to their high communication-to-computation ratios and complex communication patterns. Results indicate that SAS can achieve about half the parallel efficiency of MPI for most of our applications; however on certain classes of problems, SAS performance is competitive with MPI.
Parallel Processing of Adaptive Meshes with Load Balancing

Many scientific applications involve grids that lack a uniform underlying structure. These applications are often also dynamic in nature in that the grid structure significantly changes between successive phases of execution. In parallel computing environments, mesh adaptation of unstructured grids through selective refinement/coarsening has proven to be an effective approach. However, achieving load balance while minimizing interprocessor communication and redistribution costs is a difficult problem. Traditional dynamic load balancers are mostly inadequate because they lack a global view of system loads across processors. In this paper, we propose a novel and general-purpose load balancer that utilizes symmetric broadcast networks (SBN) as the underlying communication topology and compare its performance with a successful global load balancing environment, called PLUM, specifically created to handle adaptive unstructured applications. Our experimental results on an IBM SP2 demonstrate that the SBN-based load balancer achieves lower redistribution costs than that under PLUM by overlapping processing and data migration.
Latency hiding in dynamic partitioning and load balancing of grid computing applications

The Information Power Grid (IPG) concept developed by NASA is aimed to provide a metacomputing platform for large-scale distributed computations, by hiding the intricacies of a highly heterogeneous environment and yet maintaining adequate security. We propose a latency-tolerant partitioning scheme that dynamically balances processor workloads on the IPG, and minimizes data movement and runtime communication. By simulating an unsteady adaptive mesh application on a wide area network, we study the performance of our load balancer under the Globus environment. The number of IPG nodes, the number of processors per node, and the interconnect speeds are parameterized to derive conditions under which the IPG would be suitable for parallel distributed processing of such applications. Experimental results demonstrate that effective solutions are achieved when. The IPG nodes are connected by a high-speed asynchronous interconnection network.
Parallel Programming Strategies for Irregular Adaptive Applications

PARALLEL PROGRAMM ING STRATEGIES FORIRREGULAR ADAPTIVE APPLICATIONSR.  The use of a global addressspace greatly simplifies the programming task, but can degrade the performance for suchcomputations. In this work, we examine two typical irregular adaptive applications, DynamicRemeshing and N-Body, under competing programming methodologies and across variousparallel architectures . The Dynamic Remeshing application simulates flow over an airfoil,and retmes localized regions of the underlying unstructured mesh. The N-Body e×per_mentmodels two neighboring Plummer galaxies that are about to undergo a merger. Both problemsdemonstrate dramatic changes in processor workloads and interprocessor communication withtime; thus, dynamic load balancing is a required component.We investigate several critical factors of the parallel code development, including performance,programmability, scalability, algorithmic features, and portability. We compare the most popularimplementation strategy, message passing with MPI, against a number of alternate approaches.First, we evaluate the effectiveness of using the SHMEM communication library, which usessymmetric address spaces for individual processes, allowing one-sided communication. Next, weexamine an implementation using the OMP programming strategy, which uses shared-memoryalgorithms and OpenMP-style compiler directives on systems supporting global addressing. Thecache-coherent shared address space (CC-SAS) paradigm is tested next. It is similar to OMP butfocuses on spatial locality through methods such as data remapping and replication, which aretraditionally not considered in shared-memory programming. Experimental results using hybridprogramming are then reported. Here, two layers of parallelism are combined by implementingOpenMP codes within shared-memory multiprocessors (SMPs), while using message passingbetween the SMP nodes. Finally, we present results on the Cray MTA that uses multithreading tohide latency, rather than using data caches.Experiments were performed on several parallel systems: the distributed-memory Cray T3E, thehardware-supported CC-NUMA SGI Origin2000, the latest generation of IBM POWER3 8-waySP cluster, and the Cray MTA multithreaded computer. Results indicate that it is possible toachieve message-passing performance using shared-memory programming techniques bycarefully following the same high-level strategies, and that multithreaded systems offertremendous potential but are not well suited for all classes of applications.References[1] L. Oliker and R. B iswas, "Parallelization of a Dynamic Unstructured Algorithm Using ThreeLeading Programming Paradigms,"  2000.[2] H. Shah, J.P. Singh, L. Oliker, and R. Biswas, "'A Comparison of Three ProgrammingModels for Adaptive Applications on the Origin2000," CD_ROM Proceedings of SC2000Conference, Dallas, TX, 2000.
Ordering Sparse Matrices for Cache-Based Systems

The Conjugate Gradient (CG) algorithm is the oldest and best-known Krylov subspace method used to solve sparse linear systems. Most of the coating-point operations within each CG iteration is spent performing sparse matrix-vector multiplication (SPMV). We examine how various ordering and partitioning strategies affect the performance of CG and SPMV when different programming paradigms are used on current commercial cache-based computers. However, a multithreaded implementation on the cacheless Cray MTA demonstrates high efficiency and scalability without any special ordering or partitioning.
Parallel and Distributed Computational Fluid Dynamics: Experimental Results and Challenges

This paper describes several results of parallel and distributed computing using a production flow solver program. A coarse grained parallelization based on clustering of discretization grids, combined with partitioning of large grids, for load balancing is presented. An assessment is given of its performance on tightly-coupled distributed and distributed-shared memory platforms using large-scale scientific problems. An experiment with this solver, adapted to a Wide Area Network environment, is also presented.
Code IN Exhibits - Supercomputing 2000

The creation of parameter study suites has recently become a more challenging problem as the parameter studies have become multi-tiered and the computational environment has become a supercomputer grid. The parameter spaces are vast, the individual problem sizes are getting larger, and researchers are seeking to combine several successive stages of parameterization and computation. Simultaneously, grid-based computing offers immense resource opportunities but at the expense of great difficulty of use. We present ILab, an advanced graphical user interface approach to this problem. Our novel strategy stresses intuitive visual design tools for parameter study creation and complex process specification, and also offers programming-free access to grid-based supercomputer resources and process automation.
Ordering Unstructured Meshes for Sparse Matrix Computations on Leading Parallel Systems

Computer sim ulationsof realistic applications usually require solving a set of non-linear partial differential equations (PDEs) over a finite region. The process of obtaining numerical solutions to the governing PDEs involves solving large sparse linear or eigen systems over the unstructured meshes that model the underlying physical objects. These systems are often solved iterativ ely, where the sparse matrix-vector multiply (SPMV) is the most expensive operation within each iteration. In this paper, we focus on the efficiency of SPMV using various ordering/partitioning algorithms. We examine different implementations using three leading programming paradigms and architectures. Results show that ordering greatly improves performance, and that cache reuse can be more important than reducing communication. However, a multithreaded implementation indicates that ordering and partitioning are not required on the Tera MTA to obtain an efficient and scalable SPMV.
A Comparison of Three Programming Models for Adaptive Applications on the Origin2000

Adaptive applications have computational workloads and communication patterns which change unpredictably at runtime, requiring dynamic load balancing to achieve scalable performance on parallel machines. Efficient parallel implementations of such adaptive applications is therefore a challenging task. In this paper, we compare the performance of and the programming effort required for two major classes of adaptive applications under three leading parallel programming models on an SGI Origin2000 system, a machine which supports all three models efficiently. Results indicate that the three models deliver comparable performance; however, the implementations differ significantly beyond merely using explicit messages versus implicit loads/stores even though the basic parallel algorithms are similar. Compared with the message-passing (using MPI) and SHMEM programming models, the cache-coherent shared address space (CC-SAS) model provides substantial ease of programming at both the conceptual and program orchestration levels, often accompanied by performance gains. However, CC-SAS currently has portability limitations and may suffer from poor spatial locality of physically distributed shared data on large numbers of processors.