nils-herrmann/clean_scirepeval huggingface dataset:
PLUM: Parallel Load Balancing for Adaptive Unstructured Meshes

Mesh adaption is a powerful tool for efficient unstructured-grid computations but causes load imbalance among processors on a parallel machine. We present a novel method called PLUM to dynamically balance the processor workloads with a global view. This paper describes the implementation and integration of all major components within our dynamic load balancing strategy for adaptive grid calculations. Mesh adaption, repartitioning, processor assignment, and remapping are critical components of the framework that must be accomplished rapidly and efficiently so as not to cause a significant overhead to the numerical simulation. A data redistribution model is also presented that predicts the remapping cost on the SP2. This model is required to determine whether the gain from a balanced workload distribution offsets the cost of data movement. Results presented in this paper demonstrate that PLUM is an effective dynamic load balancing strategy which remains viable on a large number of processors.
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 the sense 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 present a novel, general-purpose load balancer that utilizes symmetric broadcast networks (SBN) as the underlying communication topology. The experimental results on the IBM SP2 demonstrate that performance of the SBN-based load balancer is comparable to results achieved under PLUM, a global load balancing environment created to handle adaptive unstructured applications.
Adaptive load-balancing algorithms using symmetric broadcast networks: performance study on an IBM SP2

In a distributed-computing environment, it is important to ensure that the processor work loads are adequately balanced. Among numerous load-balancing algorithms, a unique approach due to Das and Prasad defines a symmetric broadcast network (SBN) that provides a robust communication pattern among the processors in a topology-independent manner. In this paper, we propose and analyze three SBN-based load-balancing algorithms, and implement them on an SP2. A thorough experimental study with Poisson-distributed synthetic loads demonstrates that these algorithms are very effective in balancing system load while minimizing processor idle time. They also compare favorably with several existing techniques.
New Computational Methods for the Prediction and Analysis of Helicopter Noise

This paper describes several new methods to predict and analyze rotorcraft noise. These methods are 1) a combined computational fluid dynamics and Kirchholt scheme for far-field noise predictions, 2) parallel computer implementation of the Kirchhoff integrations 3) audio and visual rendering of the computed acoustic predictions over large far-field regions, and 4) acoustic tracebacks to the Kirchhoff surface to pinpoint the sources of the rotor noise. The paper describes each method and presents sample results for three test cases. The first case consists of in-plane high-speed impulsive noise and the other two cases show idealized parallel and oblique blade-vortex interactions. The computed results show good agreement with available experimental data but convey much more information about the far-field noise propagation. When taken together, these new analysis methods exploit the power of new computer technologies and offer the potential to significantly improve our prediction and understanding of rotorcraft noise.
HARP: a fast spectral partitioner

Partitioningunstructuredgraphsis central to the parallel solution of computational science and engineering problems, Spectral partitioners, such recursive spectral bisection (RSB), have proven effective in generating high-quality partitions of realistically-sized meshes. The major problem which hindered their widespread use was their long execution times. This paper presents a new inertial spectral partitioned, called HARP. The main objective of the proposed approach is to quickly partition the meshes at runtime in a manner that works efficiently for real applications in the context of distributed-memory machines. The underlying principle of HARP is to find the eigenvectors of the unpartitioned vertices and then project them onto the eigenvectors of the originaJ mesh. Results for various meshes ranging in size from 1000 to 100,000 vertices indicate that HARP can indeed partition meshes rapidly at runtime, Experimental results show that our largest mesh can be partitioned sequentially in only a few seconds on an SP2 which is several times faster than other spectral partitioners while maintaining the solution quality of the proven RSB method. A parallel MPI version of HARP has also been implemented on IBM SP2 and Cray T3E. PrrralIel HARP, running on 64 processors SP2 and T3E, can partition a mesh containing more than 100,000 vertices into 64 subgrids in about half a second. These results indicate that graph partitioning can now be truly embedded in dynamically-changing real-world applications,
HARP: A Dynamic Inertial Spectral Partitioner

Horst D. SimonAndrew SohnRupak BiswasThe Research Institute of Advanced Computer Science is operated by Universities Space ResearchAssociation, The American City Building, Suite 212, Columbia, MD 21044, (410) 730-2656Work reported herein was supported by NASA via Contract NAS 2-96027 between NASA and the UniversitiesSpace Research Association (USRA). Work was performed at the Research Institute for Advanced ComputerScience (RIACS), NASA Ames Research Center, Moffett Field, CA 94035-1000.
Design of Novel Load-Balancing Algorithms with Implementations on an IBM SP1

In a distributed-computing environment, it is important to ensure that the processor workloads are adequately balanced. Among numerous load-balancing algorithms, a unique approach due to Das and Prasad defines a symmetric broadcast network (SBN) that provides a robust communication pattern among the processors in a topology-independent manner. In this paper, we propose and analyze three novel SBN-based load-balancing algorithms, and implement them on an SP2. A thorough experimental study with Poisson-distributed synthetic loads demonstrates that these algorithms are very effective in balancing system load while minimizing processor idle time. They also compare favorably with several other existing load-balancing techniques.
P-HARP: A parallel dynamic spectral partitioner

Partitioning unstructured graphs is central to the parallel solution of problems in computational science and engineering. The authors have introduced earlier the sequential version of an inertial spectral partitioner called HARP which maintains the quality of recursive spectral bisection (RSB) while forming the partitions an order of magnitude faster than RSB. The serial HARP is known to be the fastest spectral partitioner to date, three to four times faster than similar partitioners on a variety of meshes. This paper presents a parallel version of HARP, called P-HARP. Two types of parallelism have been exploited: loop level parallelism and recursive parallelism. P-HARP has been implemented in MPI on the SGI/Cray T3E and the IBM SP2. Experimental results demonstrate that P-HARP can partition a mesh of over 100,000 vertices into 256 partitions in 0.25 seconds on a 64-processor T3E. Experimental results further show that P-HARP can give nearly a 20-fold speedup on 64 processors. These results indicate that graph partitioning is no longer a major bottleneck that hinders the advancement of computational science and engineering for dynamically-changing real-world applications.
Studies of DMP and SMP Machines

Understanding the interplay between machines and problems is key to obtaining high performance on parallel machines. This paper investigates the interplay between programming paradigms and communication capabilities of parallel machines. In particular, we explicate the communication capabilities of the IBM SP-2 distributed-memory multiprocessor and the SGI PowerCHALLENGEarray symmetric multiprocessor. Two benchmark problems of bitonic sorting and Fast Fourier Translbrm are selected for experiments. Communication-efficient algorithms are developed to exploit the overlapping capabilities of the machines. Programs are written in Message-Passing Interface for portability and identical codes are used for both machines. Various data sizes and message sizes are used to test the machines' communication capabilities. Experimental results indicate that the communication performance of the multiprocessors are consistent with the size of messages. The SP-2 is sensitive to message size but yields a much higher communication overlapping because of the communication co-processor. The PowerCHALLENGEarray is not highly sensitive to message size and yields a low communication overlapping. Bitonic sorting yields lower performance compared to FFT due to a smaller computation-to-communication ratio.
Communication Studies of DMP and SMP Machines

Understanding the interplay between machines and problems is key to obtaining high performance on parallel machines. This paper investigates the interplay between programming paradigms and communication capabilities of parallel machines. In particular, we explicate the communication capabilities of the IBM SP-2 distributed-memory multiprocessor and the SGI PowerCHALLENGEarray symmetric multiprocessor. Two benchmark problems of bitonic sorting and Fast Fourier Transform are selected for experiments. Communication-efficient algorithms are developed to exploit the overlapping capabilities of the machines. Programs are written in Message-Passing Interface for portability and identical codes are used for both machines. Various data sizes and message sizes are used to test the machines' communication capabilities. Experimental results indicate that the communication performance of the multiprocessors are consistent with the size of messages. The SP-2 is sensitive to message size but yields a much higher communication overlapping because of the communication co-processor. The PowerCHALLENGEarray is not highly sensitive to message size and yields a low communication overlapping. Bitonic sorting yields lower performance compared to FFT due to a smaller computation-to-communication ratio.
Load balancing sequences of unstructured adaptive grids

Mesh adaption is a powerful tool for efficient unstructured grid computations but causes load imbalance on multiprocessor systems. To address this problem, we have developed PLUM, an automatic portable framework for performing adaptive large scale numerical computations in a message passing environment. The paper makes several important additions to our previous work. First, a new remapping cost model is presented and empirically validated on an SP2. Next, our load balancing strategy is applied to sequences of dynamically adapted unstructured grids. Results indicate that our framework is effective on many processors for both steady and unsteady problems with several levels of adaption. Additionally, we demonstrate that a coarse starting mesh produces high quality load balancing, at a fraction of the cost required for a fine initial mesh. Finally, we show that the data remapping overhead can be significantly reduced by applying our heuristic processor reassignment algorithm.
Load Balancing Unstructured Adaptive Grids for CFD Problems

Mesh adaption is a powerful tool for efficient unstructured-grid computations but causes load imbalance among processors on a parallel machine. A dynamic load balancing method is presented that balances the workload across all processors with a global view. After each parallel tetrahedral mesh adaption, the method first determines if the new mesh is sufficiently unbalanced to warrant a repartitioning. If so, the adapted mesh is repartitioned, with new partitions assigned to processors so that the redistribution cost is minimized. The new partitions are accepted only if the remapping cost is compensated by the improved load balance. Results indicate that this strategy is effective for large-scale scientific computations on distributed-memory multiprocessors.
An edge-based solution-adaptive method applied to the AIRPLANE code

ABSTRACTComputational methods to solve large-scale re-alistic problems in fluid flow can be made more effi-cient and cost effective by using them in conjunctionwith dynamic mesh adaption procedures that per-form simultaneous coarsening and refinement to cap-ture flow features of interest. This work couples thetetrahedral mesh adaption scheme, called 3D.TAG,with the AIRPLANE code to solve complete aircraftconfiguration problems in transonic and supersonicflow regimes. Results indicate that the near-fieldsonic boom pressure signature of a cone-cylinder isimproved, the oblique and normal shocks are bet-ter resolved on a transonic wing, and the bow shockahead of an unstarted inlet is better defined.INTRODUCTIONTraditional computational methods can bemade more efficient and cost effective by redistribut-ing the available mesh points to capture flowfieldphenomena of interest. Such adaptive proceduresevolve with the solution and provide a robust andreliable methodology. Highly localized regions ofmesh refinement are required in order to accuratelycapture shock waves, contact discontinuities, andshear layers. This provides the aerodynamicist withthe opportunity to obtain flow solutions on adaptedmeshes that are comparable to those obtained onglobally-fine grids.Two types of solution-adaptive grid strategiesare commonly used with unstructured-grid methods.
A dynamic mesh adaption procedure for unstructured hexahedral grids

Hexahedral elements can be subdivided anisotropically without mesh quality problems that are associated with tetrahedral meshes. Furthermore, hexahedral meshes yield more accurate solutions than their tetrahedral counterparts for the same number of edges. Our adaption procedure uses an edge data structure that facilitates efficient subdivision by allowing individual edges to be marked for refinement or coarsening. Pyramids and prisms are used as buffer elements between refined and unrefined hexahedra to eliminate hanging vertices. Preliminary results indicate that this new adaption procedure is a viable alternative to adaptive tetrahedral schemes.
Impact of load balancing on unstructured adaptive grid computations for distributed-memory multiprocessors

The computational requirements for an adaptive solution of unsteady problems change as the simulation progresses. This causes workload imbalance among processors on a parallel machine which, in turn, requires significant data movement at runtime. We present a new dynamic load-balancing framework, called JOVE, that balances the workload across all processors with a global view. Whenever the computational mesh is adapted, JOVE is activated to eliminate the load imbalance. JOVE has been implemented on an IBM SP2 distributed-memory machine in MPI for portability. Experimental results for two model meshes demonstrate that mesh adaption with load balancing gives more than a sixfold improvement over one without load balancing. We also show that JOVE gives a 24-fold speedup on 64 processors compared to sequential execution.
Efficient Helicopter Aerodynamic and Aeroacoustic Predictions on Parallel Computers

This paper presents parallel implementations of two codes used in a combined CFD/Kirchhoff methodology to predict the aerodynamics and aeroacoustics properties of helicopters. The rotorcraft Navier-Stokes code, TURNS, computes the aerodynamic flowfield near the helicopter blades and the Kirchhoff acoustics code computes the noise in the far field, using the TURNS solution as input. The overall parallel strategy adds MPI message passing calls to the existing serial codes to allow for communication between processors. As a result, the total code modifications required for parallel execution are relatively small. The biggest bottleneck in running the TURNS code in parallel comes from the LU-SGS algorithm that solves the implicit system of equations. We use a new hybrid domain decomposition implementation of LU-SGS to obtain good parallel performance on the SP-2. TURNS demonstrates excellent parallel speedups for quasi-steady and unsteady three-dimensional calculations of a helicopter blade in forward flight. The execution rate attained by the code on 114 processors is six times faster than the same cases run on one processor of the Cray C-90. The parallel Kirchhoff code also shows excellent parallel speedups and fast execution rates. As a performance demonstration, unsteady acoustic pressures are computed at 1886 far-field observer locations for a sample acoustics problem. The calculation requires over two hundred hours of CPU time on one C-90 processor but takes only a few hours on 80 processors of the SP2. The resultant far-field acoustic field is analyzed with state of-the-art audio and video rendering of the propagating acoustic signals.
Parallel Implementation of an Adaptive Scheme for

Leonid OlikerRupak BiswasRoger C. StrawnThe Research Institute of Advanced Computer Science is operated by Universities Space ResearchAssociation, The American City Building, Suite 212, Columbia, MD 21044, (410) 730-2656Work reported herein was supported by NASA via Contract NAS 2-13721 between NASA and the UniversitiesSpace Research Association (USRA). Work was performed at the Research Institute for Advanced ComputerScience (RIACS), NASA Ames Research Center, Moffett Field, CA 94035-1000.
A dynamic load balancing framework for unstructured adaptive computations on distributed-memory multiprocessors

The computational requirements for an adaptive solution of unsteady problems change as the simulation progresses. This causes workload imbalance among processors on a parallel machine which, in turn, requires significant data movement at runtime. We present a dynamic load-balancing framework, called JOVE, that balances the workload across all processors with a global view each time the computational mesh is adapted. JOVE has been implemented on an SP2 in MPI for portability. Experimental results for two model meshes demonstrate that mesh adaption with load balancing gives more than a sixfold improvement over one without load balancing. Furthermore, JOVE gives a 24-fold speedup on 64 processors compared to sequential execution.
Parallel Implementation of an Adaptive Scheme for 3D Unstructured Grids on the SP2

Dynamic mesh adaption on unstructured grids is a powerful tool for computing unsteady flows that require local grid modifications to efficiently resolve solution features. For this work, we consider an edge-based adaption scheme that has shown good single-processor performance on the C90. We report on our experience parallelizing this code for the SP2. Results show a 47.0X speedup on 64 processors when 10% of the mesh is randomly refined. Performance deteriorates to 7.7X when the same number of edges are refined in a highly-localized region. This is because almost all the mesh adaption is confined to a single processor. However, this problem can be remedied by repartitioning the mesh immediately after targeting edges for refinement but before the actual adaption takes place. With this change, the speedup improves dramatically to 43.6X.
Methods for the Prediction and Analysis of Helicopter Noise

Roger C. StrawnLeonid OlikerRupak BiswasThe Research Institute of Advanced Computer Science is operated by Universities Space ResearchAssociation, The American City Building, Suite 212, Columbia, MD 21044, (410) 730-2656Work reported herein was supported by NASA via Contract NAS 2-13721 between NASA and the UniversitiesSpace Research Association (USRA). Work was performed at the Research Institute for Advanced ComputerScience (RIACS), NASA Ames Research Center, Moffett Field, CA 94035-1000.
Global Load Balancing with Parallel Mesh Adaption on Distributed-Memory Systems

Dynamic mesh adaption on unstructured grids is a powerful tool for efficiently computing unsteady problems to resolve solution features of interest. Unfortunately, this causes load imbalance among processors on a parallel machine. This paper describes the parallel implementation of a tetrahedral mesh adaption scheme and a new global load balancing method. A heuristic remapping algorithm is presented that assigns partitions to processors such that the redistribution cost is minimized. Results indicate that the parallel performance of the mesh adaption code depends on the nature of the adaption region and show a 35.5X speedup on 64 processors of an SP2 when 35% of the mesh is randomly adapted. For large-scale scientific computations, our load balancing strategy gives almost a sixfold reduction in solver execution times over non-balanced loads. Furthermore, our heuristic remapper yields processor assignments that are less than 3% off the optimal solutions but requires only 1% of the computational time.
Satisfiability test with synchronous simulated annealing on the Fujitsu AP1000 massively-parallel multiprocessor

Solving the hard Satisfiability Problem is time consuming even for modest-sized problem instances. Solving the Random L-SAT Problem is especially difficult due to the ratio of clauses to variables. This report presents a parallel synchronous simulated annealing method for solving the Random L-SAT Problem on a large-scale distributed-memory multiprocessor. In particular, we use a parallel synchronous simulated annealing procedure, called Generalized Speculative Computation, which guarantees the same decision sequence as sequential simulated annealing. To demonstrate the performance of the parallel method, we have selected problem instances varying in size from 100-variables/425-clauses to 5000-variables/21,250-clauses. Experimental results on the AP1000 multiprocessor indicate that our approach can satisfy 99.9 percent of the clauses while giving almost a 70-fold speedup on 500 processors.
An Overset Grid Navier-Stokes/Kirchhoff-Surface Method for Rotorcraft Aeroacoustic Predictions

This paper describes a new method for computing the flowfield and acoustic signature of arbitrary rotors in forward flight. The overall scheme uses a finite-difference Navier-Stokes solver to compute the aerodynamic flowfield near the rotor blades. The equations are solved on a system of overset grids that allow for prescribed cyclic and flapping blade motions and capture the interactions between the rotor blades and wake. The far-field noise is computed with a Kirchhoff integration over a surface that completely encloses the rotor blades. FIowfield data are interpolated onto this Kirchhoff surface using the same overset-grid techniques that are used for the flowfield solution. As a demonstration of the overall prediction scheme, computed results for far-field noise are compared with experimental data for both high-speed impulsive (HSI) and blade-vortex interaction (BVI) cases. The HS! case showed good agreement with experimental data while a preliminary attempt at the BVI case did not. The computations clearly show that temporal accuracy, spatial accuracy and grid resolution in the Navier-Stokes solver play key roles in the overall accuracy of the predicted noise. These findings will be addressed more closely in future BVI computations.