LLVM frontends like Clang preserve source-level type information in the intermediate representation (IR) primarily through debug metadata. Although intended for debuggers, this metadata benefits compiler tools like sanitizers, which need type information of stack, heap and global allocations for tasks such as verifying memory safety. We present llvm-dimeta, a library that extracts type information for memory allocations directly from LLVM IR via debug metadata. It handles the necessary IR analysis internally, enabling frontend-independent type queries. As a case study, we integrate llvm-dimeta into a type correctness checker for MPI-parallelized HPC applications. Using llvm-dimeta, the checker achieves 98% accuracy on an MPI correctness benchmark, up from 76% when relying solely on LLVM IR’s more limited type system. Code is available at https://github.com/ahueck/llvm-dimeta

This study focuses on gaining insights into the usage of the Message-Passing Interface (MPI) in a large set of High-Performance Computing (HPC) codes by analyzing MPI function calls and their argument usage patterns. Previous work has focused on analyzing MPI feature usage by statically matching function calls. However, this approach does not reveal common argument-specific call patterns or cross-interactions between MPI functions. In particular, MPI exposes its internal data structures using handles, and users pass these handles to MPI constructor functions, e.g., to create custom communicators. Tracking the relevant MPI arguments of these constructors and cross-referencing them with other MPI calls in a target code can reveal common user interactions. These insights can be used to optimize, e.g., datatype construction at a library level or to extend MPI correctness debugging tools to verify correct construction of these data structures. To that end, we statically analyze codes to extract MPI function calls and their arguments, cross-reference them with other MPI calls, and provide statistics on common argument patterns and cross-use of MPI functions. We believe that these insights can guide further development within the MPI community to ultimately benefit users.

High-performance computing codes often combine the Message-Passing Interface (MPI) with a shared-memory programming model, e.g., OpenMP, for efficient computations. These so-called hybrid models may issue MPI calls concurrently from different threads at the highest level of MPI thread support. The correct use of either MPI or OpenMP can be complex and error-prone. The hybrid model increases this complexity even further. While correctness analysis tools exist for both programming paradigms, for hybrid models, a new set of potential errors exist, whose detection requires combining knowledge of MPI and OpenMP primitives. Unfortunately, correctness tools do not fully support the hybrid model yet, and their current capabilities are also hard to assess. In previous work, to enable structured comparisons of correctness tools and improve their coverage, we proposed the MPI-CorrBench test suite for MPI. Likewise, others proposed the DataRaceBench test suite for OpenMP. However, for the particular error classes of the hybrid model, no such test suite exists. Hence, we propose a hybrid MPI-OpenMP test suite to (1) facilitate the correctness tool development in this area and, subsequently, (2) further encourage the use of the hybrid model at the highest level of MPI thread support. To that end, we discuss issues with this hybrid model and the knowledge correctness tools need to combine w.r.t. MPI and OpenMP to detect these. In our evaluation of two state-of-the-art correctness tools, we see that for most cases of concurrent and conflicting MPI operations, these tools can cope with the added complexity of OpenMP. However, more intricate errors, where user code interferes with MPI, e.g., a data race on a buffer, still evade tool analysis.

Abstract In this article, we present the novel features of the recent version of SimAnMo, the Simulated Annealing Modeler. The tool creates models that correlate the size of one input parameter of an application to the corresponding runtime and thus SimAnMo allows predictions for larger input sizes. A focus lies on applications whose runtime grows exponentially in the input parameter size. Such programs are, for example, of high interest for cryptanalysis to analyze practical security of traditional and post‐quantum secure schemes. However, SimAnMo also generates reliable models for the widespread case of polynomial runtime behavior and also for the important case of factorial runtime increase. SimAnMo's model generation is based on a parallelized simulated annealing procedure and heuristically minimizes the costs of a model. Those may rely on different quality metrics. Insights into SimAnMo's software design and its usage are provided. We demonstrate the quality of SimAnMo's models for different algorithms from various application fields. We show that our approach also works well on ARM architectures.

The Message Passing Interface (MPI) is the de-facto standard for distributed memory computing in high-performance computing (HPC). To aid developers write correct MPI programs, different tools have been proposed, e.g., Intel Trace Analyzer and Collector (ITAC), MUST, Parcoach and MPI-Checker. Unfortunately, the effectiveness of these tools is hard to compare, as they have not been evaluated on a common set of applications. More importantly, well-known and widespread benchmarks, which tend to be well-tested and error free, were used for their evaluation. To enable a structured comparison and improve the coverage and reliability of available MPI correctness tools, we propose MPI-CorrBench as a common test harness. MPI-CorrBench enables a structured comparison of the different tools available w.r.t. various types of errors. In our evaluation, we use MPI-CorrBench to provide a well-defined set of error-cases to MUST, ITAC, Parcoach and MPI-Checker. In particular, we find that ITAC and MUST complement each other in many cases. In general, MUST works better for detecting type errors while ITAC is better in detecting errors in non-blocking operations. Although the most-used functions of MPI are well supported, MPI-CorrBench shows that for one sided communication, the error detection capability of all evaluated tools needs improvement. Moreover, our experiments reveal a MPI standard violation in the MPICH test suite as well as several cases of discouraged use of MPI functionality.

The size and complexity of high-performance computing applications present a serious challenge to manual reasoning about program behavior. The vastness and diversity of code bases often break automatic analysis tools, which could otherwise be used. As a consequence, developers resort to mini-apps, i.e., trimmed-down proxies of the original programs that retain key performance characteristics. Unfortunately, their construction is difficult and time consuming and prevents their mass production. In this paper, we propose a systematic and tool-supported approach to extract mini-apps from large-scale applications that reduces the manual effort needed to create them. Our approach covers the stages kernel identification, data capture, code extraction and representativeness validation. We demonstrate it using an astrophysics simulation with ≈ 8.5 million lines of code and extract a mini-app with only ≈ 1, 100 lines of code. For the mini-app, we evaluate the reduction of code complexity and execution similarity, and show how it enables the tool-supported discovery of unexploited parallelization opportunities, reducing the simulation’s runtime significantly.

In this paper, we propose a parallel implementation of LDSieve, a recently published sieving algorithm for the SVP, which achieves the best theoretical complexity to this day, on parallel shared-memory systems. In particular, we propose a scalable parallel variant of LDSieve that is probabilistically lock-free and relaxes the properties of the algorithm to favour parallelism. We use our parallel variant of LDSieve to answer a number of important questions pertaining to the algorithm. In particular, we show that LDSieve scales fairly well on shared-memory systems and uses much less memory than HashSieve on random lattices, for the same or even less execution time.

Summary Super carbon nanotubes (SCNTs) are of interest in material design because of their strength and weight characteristics. In this paper, we present a graph algebra‐based approach to model and construct SCNTs of arbitrary order. The SCNTs are represented by directed graphs with Y junctions as basic modeling element. A new data structure to store these graphs is proposed that capitalizes on the hierarchy within SCNTs and allows efficient queries for nodes and edges. Symmetry considerations for SCNTs are conducted and related to the graph algebra‐based modeling. We present an extended and improved algorithm for simulating the mechanical behavior of SCNTs. Compared with our previous work on level 0 SCNTs, the performance is improved by a factor higher than 2 when running in serial and a factor up to 4.4 when running in parallel on a 16‐core symmetric multiprocessing system. A new pre‐processing step exploiting structural symmetry and an improved proximity‐aware matrix‐vector‐multiplication routine make this performance improvement possible while only consuming little additional memory. We also now consider SCNTs of order 1 and 2. Experimental results show that our new solver is up to 1.4 times faster than a compressed‐row‐storage based reference solver, on order 0, 1, and 2 SCNTs, with and without deformations, while requiring only half the memory. Because memory is the limiting factor for the feasibility of such simulations, our new approach significantly expands the realm of feasibility for such simulations. Copyright © 2016 John Wiley & Sons, Ltd.

The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.

The Shortest Vector Problem (SVP) is a key problem in lattice-based cryptography and cryptanalysis. While the cryptography community has accumulated a vast knowledge of SVP-solvers from a theoretical standpoint, the practical performance of these algorithms is commonly not well understood. This gap in knowledge poses many challenges to cryptographers, who are oftentimes confronted with algorithms that perform worse in practice then expected from theory. This is a problem because the asymptotic complexity of the best algorithms plays a key role in the construction of cryptosystems, but only practically appealing, validated algorithms are accounted for in this process. Thus, if one cannot extract the full potential of theoretically strong algorithms in practice, efficient algorithms might be ruled out and wrong assumptions are made when constructing cryptosystems. In this paper, we take a step forward to fill this gap, by providing a computational analysis of HashSieve, the most practical sieving SVP-solver to date, and showing how its performance can be enhanced in practice. To this end, we revisit the parallel generation of random numbers, memory allocation and memory access patterns. Employing scalable random sampling, object memory pools, scalable memory allocators and aggressive memory prefetching, we were able to improve the best current implementation of HashSieve by factors of 3x and 4x, depending on the lattice dimension, and set new records for the HashSieve algorithm, thereby shrinking the gap between its theoretical complexity and its performance in practice.

Improving the memory access behavior of parallel applications is one of the most important challenges in high-performance computing. Non-Uniform Memory Access (NUMA) architectures pose particular challenges in this context: they contain multiple memory controllers and the selection of a controller to serve a page request influences the overall locality and balance of memory accesses, which in turn affect performance. In this paper, we analyze and improve the memory access pattern and overall memory usage of large-scale irregular applications on NUMA machines. We selected HashSieve, a very important algorithm in the context of lattice-based cryptography, as a representative example, due to (1) its extremely irregular memory pattern, (2) large memory requirements and (3) unsuitability to other computer architectures, such as GPUs. We optimize HashSieve with a variety of techniques, focusing both on the algorithm itself as well as the mapping of memory pages to NUMA nodes, achieving a speedup of over 2x.

In this paper, we assess the practicability of Hash Sieve, a recently proposed sieving algorithm for the Shortest Vector Problem (SVP) on lattices, on multi-core shared memory systems. To this end, we devised a parallel implementation that scales well, and is based on a probable lock-free system to handle concurrency. The probable lock-free system, implemented with spin-locks, in turn implemented with CAS operations, becomes likely a lock-free mechanism, since threads block only when strictly required and chances are that they are not required to block. With our implementation, we were able to solve the SVP on an arbitrary lattice in dimension 96, in less than 17.5 hours, using 16 physical cores. The least squares fit of the execution times of our implementation, in seconds, lies between 2(0.32n -- 15) or 2(0.33n -- 16). These results are of paramount importance for the selection of parameters in lattice-based cryptography, as they indicate that sieving algorithms are way more practical for solving the SVP than previously believed.

Operator overloading allows the semantic extension of existing code without the need for sweeping code changes. For example, automatic differentiation tools in C++ commonly use this feature to enhance the code with additional derivative computation. To this end, a floating point data type is changed to a complex user-defined type. While conceptually straightforward, this type change often leads to compilation errors that can be tedious to decipher and resolve. This is due to the fact that the built-in floating point types in C++ are treated differently than user-defined types, and code constructs that are legal for floating point types can be a violation of the C++ standard for complex user-defined types. We identify and classify such problematic code constructs and suggest how the code can be changed to avoid these errors, while still allowing the use of operator overloading. To automatically flag such occurrences, we developed a Clang-based tool for the static analysis of C++ code based on our assessment of constructs problematic in operator overloading for numeric types. It automatically finds instances of problematic code locations and prints Lint-like warning messages. To showcase the relevance of this topic and the usefulness of our tool, we consider the basic routines of the OpenFOAM CFD software package, consisting of 1,476 C++ source and header files, for a total of over 150,000 lines of code. Altogether, we found 74 distinct occurrences of problematic code constructs in 21 files. As some of these files are included in over 400 different locations in the OpenFOAM base, errors in these files create a torrent of error messages that often are difficult to comprehend. In summary, the classification of problematic instances aids developers in writing numerical code that is fit for operator overloading and the tool helps programmers that augment legacy code in spotting problematic code constructs.

Summary The reverse mode of automatic differentiation executes the adjoint statements induced by each statement in the original program in the reverse order of the original program flow. This program flow reversal commonly requires storage of information on the control flow of the original program. In addition, intermediate values of variables that are overwritten have to be recorded, as these values may later be needed to compute the partial derivatives of the corresponding statement. The stored information will be accessed in reverse order of being written. This runs contrary to many assumptions made in standard implementations of file systems, operating systems, and input/output (I/O) libraries. A common buffering strategy aimed at speeding up future read requests is to employ read‐ahead. This strategy is useful for accesses in forward direction but is considered to be harmful to the performance of the reverse mode. To increase the performance of the reverse mode, it is also advantageous to interleave computations with the data storage and retrieval operations, which can be achieved using multithreading. To this end, we design and implement a novel software called reverse‐mode I/O stream (RIOS) that is adapted to these particular requirements of the reverse mode. We show the advantages of RIOS in two empirical case studies, an artificially constructed example of a typical I/O pattern in the reverse mode and a real‐world example arising from fluid mechanics, which is studied in Fortran90 and in Matlab where the reverse mode is generated via the automatic differentiation tools Tapenade and ADiMat, respectively. Copyright © 2014 John Wiley & Sons, Ltd.

Lattice-based cryptography became a hot-topic in the past years because it seems to be quantum immune, i.e., resistant to attacks operated with quantum computers. The security of lattice-based cryptosystems is determined by the hardness of certain lattice problems, such as the Shortest Vector Problem (SVP). Thus, it is of prime importance to study how efficiently SVP-solvers can be implemented. This paper presents a parallel shared-memory implementation of the GaussSieve algorithm, a well known SVP-solver. Our implementation achieves almost linear and linear speedups with up to 64 cores, depending on the tested scenario, and delivers better sequential performance than any other disclosed GaussSieve implementation. In this paper, we show that it is possible to implement a highly scalable version of GaussSieve on multi-core CPU-chips. The key features of our implementation are a lock-free singly linked list, and hand-tuned, vectorized code. Additionally, we propose an algorithmic optimization that leads to faster convergence.

The novel ScaleMP vSMP architecture employs commodity x86-based servers with an InfiniBand network to assemble a large shared memory system at an attractive price point. We examine this combined hardware- and software-approach of a DSM system using both system-level kernel benchmarks as well as real-world application codes. We compare this architecture with traditional shared memory machines and elaborate on strategies to tune application codes parallelized with OpenMP on multiple levels. Finally we summarize the necessary conditions which a scalable application has to fulfill in order to profit from the full potential of the ScaleMP approach.

Ventricular Assist Devices (VADs) support the heart in its vital task of maintaining circulation in the human body when the heart alone is not able to maintain a sufficient flow rate due to illness or degenerative diseases. However, the engineering of these devices is a highly demanding task. Advanced modeling methods and computer simulations allow the investigation of the fluid flow inside such a device and in particular of potential blood damage. In this paper we present a set of visualization methods which have been designed to specifically support the analysis of a tensor-based blood damage prediction model. This model is based on the tracing of particles through the VAD, for each of which the cumulative blood damage can be computed. The model's tensor output approximates a single blood cell's deformation in the flow field. The tensor and derived scalar data are subsequently visualized using techniques based on icons, particle visualization, and function plotting. All these techniques are accessible through a Virtual Reality-based user interface, which features not only stereoscopic rendering but also natural interaction with the complex three-dimensional data. To illustrate the effectiveness of these visualization methods, we present the results of an analysis session that was performed by domain experts for a specific data set for the MicroMed DeBakey VAD.

Extraction of complex data structures like vector field topologies in large-scale, unsteady flow field datasets for the interactive exploration in virtual environments cannot be carried out without parallelization strategies. We present an approach based on Nested OpenMP to find critical points, which are the essential parts of velocity field topologies. We evaluate our parallelization scheme on several multi-block datasets, and present the results for various thread counts and loop schedules on all parallelization levels. Our experience suggests that upcoming massively multi-threaded processor architectures can be very advantageously for large-scale feature extractions.

Nasal airway obstruction is a serious and common problem within the field of rhinology. This paper introduces VRhino II, a virtual-reality-based application for the analysis of the airflow through the human nasal cavity. This tool is currently developed within a research project striving to gain better insight into the flow conditions during respiration. The paper's focus lies on a general description of the application's design. Additionally, technical details about the main system components are given.

One recommended strategy for the analysis of CFD-data is the interactive exploration within virtual environments. Common visualization systems are unable to process large data sets while carrying out real-time interaction and visualization at the same time. The obvious idea is to decouple flow feature extraction from visualization. This paper covers the functionality of the parallel CFD post-processing toolkit Viracocha. Two aspects are discussed in more detail. The first approach covers strategies to reduce the loading time. Data caching and prefetching are employed to reduce access time. The second aspect concerns an approach called streaming that minimizes the time a user has to wait for first results. Viracocha already sends coarse intermediate data back to the virtual environment before the final result is available. Different streaming and data handling strategies are described. In order to emphasize the benefit of our implementation efforts, some strategies are applied to multi-block CFD data sets.

Automatic differentiation is a semantic transformation that applies the rules of differential calculus to source code. It thus transforms a computer program that computes a mathematical function into a program that computes the function and its derivatives. Derivatives play an important role in a wide variety of scientific computing applications, including optimization, solution of nonlinear equations, sensitivity analysis, and nonlinear inverse problems. We describe a simple component architecture for developing tools for automatic differentiation and other mathematically oriented semantic transformations of scientific software. This architecture consists of a compiler-based, language-specific front-end for source transformation, loosely coupled with one or more language-independent "plug-in" transformation modules. The coupling mechanism between the front-end and transformation modules is provided by the XML Abstract Interface Form (XAIF). XAIF provides an abstract, language-independent representation of language constructs common in imperative languages, such as C and Fortran. We describe the use of this architecture in constructing tools for automatic differentiation of Fortran 77 and ANSI C, and we discuss how access to compiler optimization techniques can enable more efficient derivative augmentation.

Derivatives of almost arbitrary functions can be evaluated efficiently by automatic differentiation whenever the functions are given in the form of computer programs in a high-level programming language such as Fortran, C, or C++. Furthermore, in contrast to numerical differentiation where derivatives are approximated, automatic differentiation generates derivatives that are accurate up to machine precision. The so-called forward mode of automatic differentiation computes derivatives by carrying forward a gradient associated with each intermediate variable simultaneously with the evaluation of the function itself. It is shown how software tools implementing the technology of automatic differentiation can benefit from simple concepts of shared memory programming to parallelize the gradient operations. The feasibility of our approach is demonstrated by numerical experiments. They were performed with a code that was generated automatically by the Adifor system and augmented with OpenMP directives.

We develop an algorithmic framework for reducing the bandwidth of symmetric matrices via orthogonal similarity transformations. This framework includes the reduction of full matrices to banded or tridiagonal form and the reduction of banded matrices to narrower banded or tridiagonal form, possibly in multiple steps. Our framework leads to algorithms that require fewer floating-point operations than do standard algorithms, if only the eigenvalues are required. In addition, it allows for space-time tradeoffs and enables or increases the use of blocked transformations.

We present a software toolbox for symmetric band reduction via orthogonal transformations, together with a testing and timing program. The toolbox contains drivers and computational routines for the reduction of full symmetric matrices to banded form and the reduction of banded matrices to narrower banded or tridiagonal form, with optional accumulation of the orthogonal transformations, as well as repacking routines for storage rearrangement. The functionality and the calling sequences of the routines are described, with a detailed discussion of the “control” parameters that allow adaptation of the codes to particular machine and matrix characteristics. We also briefly describe the testing and timing program included in the toolbox.

We develop algorithms and implementations for computing rank-revealing QR (RRQR) factorizations of dense matrices. First, we develop an efficient block algorithm for approximating an RRQR factorization, employing a windowed version of the commonly used Golub pivoting strategy, aided by incremental condition estimation. Second, we develop efficiently implementable variants of guaranteed reliable RRQR algorithms for triangular matrices originally suggested by Chandrasekaran and Ipsen and by Pan and Tang. We suggest algorithmic improvements with respect to condition estimation, termination criteria, and Givens updating. By combining the block algorithm with one of the triangular postprocessing steps, we arrive at an efficient and reliable algorithm for computing an RRQR factorization of a dense matrix. Experimental results on IBM RS/6000 SGI R8000 platforms show that this approach performs up to three times faster that the less reliable QR factorization with column pivoting as it is currently implemented in LAPACK, and comes within 15% of the performance of the LAPACK block algorithm for computing a QR factorization without any column exchanges. Thus, we expect this routine to be useful in may circumstances where numerical rank deficiency cannot be ruled out, but currently has been ignored because of the computational cost of dealing with it.

This article describes a suite of codes as well as associated testing and timing drivers for computing rank-revealing QR (RRQR) factorizations of dense matrices. The main contribution is an efficient block algorithm for approximating an RRQR factorization, employing a windowed version of the commonly used Golub pivoting strategy and improved versions of the RRQR algorithms for triangular matrices orginally suggersted by Chandrasekaran and Ipsen and by Pan and Tang, respectively, We highlight usage and features of these codes.

This article describes approaches to computing second-order derivatives with automatic differentiation (AD) based on the forward mode and the propagation of univariate Taylor series. Performance results are given that show the speedup possible with these techniques relative to existing approaches. We also describe a new source transformation AD module for computing second-order derivatives of C and Fortran codes and the underlying infrastructure used to create a language-independent translation tool. 1 Introduction Automatic differentiation (AD) provides an efficient and accurate method to obtain derivatives for use in sensitivity analysis, parameter identification and optimization. Current tools are targeted primarily at computing first-order derivatives, namely gradients and Jacobians. Prior to AD, derivative values were obtained through divided difference methods, symbolic manipulation or hand-coding, all of which have drawbacks when compared with AD (see [4] for a dis- This wo...

The accurate and efficient computation of gradients for partially separable functions is central to the solution of large-scale optimization problems, because these functions are ubiquitous in large-scale problems. We describe two approaches for computing gradients of partially separable functions via automatic differentiation. In our experiments we employ the ADIFOR (automatic differentiation of Fortran) tool and the SparsLinC (sparse linear combination) library. We use applications from the MINPACK-2 test problem collection to compare the numerical reliability and computational efficiency of these approaches with hand-coded derivatives and approximations based on differences of function values. Our conclusion is that automatic differentiation is the method of choice, providing code for the efficient computation of the gradient without the need for tedious hand-coding.

In scientific computing, we often require the derivatives ∂f/∂x of a function f expressed as a program with respect to some input parameter(s) x, say. Automatic Differentiation (AD) techniques augment the program with derivative computation by applying the chain rule of calculus to elementary operations in an automated fashion. This article introduces ADIC (Automatic Differentiation of C), a new AD tool for ANSI-C programs. ADIC is currently the only tool for ANSI-C that employs a source-to-source program transformation approach; that is, it takes a C code and produces a new C code that computes the original results as well as the derivatives. We first present ADIC ‘by example’ to illustrate the functionality and ease of use of ADIC and then describe in detail the architecture of ADIC. ADIC incorporates a modular design that provides a foundation for both rapid prototyping of better AD algorithms and their sharing across AD tools for different languages. A component architecture called AIF (Automatic Differentiation Intermediate Form) separates core AD concepts from their language-specific implementation and allows the development of generic AD modules that can be reused directly in other AIF-based AD tools. The language-specific ADIC front-end and back-end canonicalize C programs to make them fit for semantic augmentation and manage, for example, the association of a program variable with its derivative object. We also report on applications of ADIC to a semiconductor device simulator, 3-D CFD grid generator, vehicle simulator, and neural network code. © 1997 John Wiley & Sons, Ltd.

The numerical methods employed in the solu-

. The numerical methods employed in the solution of many scientific computing problems require the computation of first- or second-order derivatives of a function f : R n !R m . We present an approach that, given a serial C program for the computation of f(x), derives a parallel execution schedule for the computation of f and its derivatives in a completely automatic fashion. This is achieved by overloading the computation of f(x) in C++ to obtain a trace of the computations to be performed and then transforming this trace into a data flow graph for the computation of f(x). In addition to the computation of f(x), this graph also allows us to exactly and inexpensively compute derivates of f by the repeated use of the chain rule. Parallelism is exploited in two ways: rows or columns of derivative matrices can be computed by independent passes through the computational graph, and parallelism within the processing of this computational graph can be exploited by processing independent...

The goal of the LAPACK project is to design and implement a portable linear algebra library for efficient use on a variety of high-performance computers. The library is based on the widely used LINPACK and EISPACK packages for solving linear equations, eigenvalue problems, and linear least-squares problems, but extends their functionality in a number of ways. The major methodology for making the algorithms run faster is to restructure them to perform block matrix operations (e.g., matrix-matrix multiplication) in their inner loops. These block operations may be optimized to exploit the memory hierarchy of a specific architecture. The LAPACK project is also working on new algorithms that yield higher relative accuracy for a variety of linear algebra problems.>

This paper presents a new algorithm for computing the QR factorization of a rank-deficient matrix on high-performance machines. The algorithm is based on the Householder QR factorization algorithm with column pivoting. The traditional pivoting strategy is not well suited for machines with a memory hierarchy since it precludes the use of matrix-matrix operations. However, matrix-matrix operations perform better on those machines than matrix-vector or vector-vector operations since they involve significantly less data movement per floating point operation. We suggest a restricted pivoting strategy which allows us to formulate a block QR factorization algorithm where the bulk of the work is in matrix-matrix operations. Incremental condition estimation is used to ensure the reliability of the restricted pivoting scheme. Implementation results on the Cray 2, Cray X-MP and Cray Y-MP show that the new algorithm performs significantly better than the traditional scheme and can more than halve the cost of computing the QR factorization.

A parallel version of the Householder algorithm with column pivoting is introduced for computing the QR factorization of a matrix. Local pivoting allows efficient implementation of the algorithm on a parallel machine; in particular, it is implemented on one with a distributed architecture. An inexpensive but reliable incremental condition estimator is used to control the selection of pivot columns by obtaining cheap estimates for the smallest singular value of the currently created upper triangular matrix R. Numerical experiments show that the local pivoting strategy behaves about as well as the traditional global pivoting strategy. They also show the advantages of incorporating the controlled pivoting strategy into the traditional QR algorithm to guard against the known pathological cases.>