Multi-dimensional arrays are among the most fundamental and most useful data structures of all. In C++, excellent template libraries exist for arrays whose dimension is fixed at runtime. Arrays whose dimension can change at runtime have been implemented in C. However, a generic object-oriented C++ implementation of runtime-flexible arrays has so far been missing. In this article, we discuss our new implementation called Marray, a package of class templates that fills this gap. Marray is based on views as an underlying concept. This concept brings some of the flexibility known from script languages such as R and MATLAB to C++. Marray is free both for commercial and non-commercial use and is publicly available from www.andres.sc marray
summarizes the mathematics of runtime-flexible multi-dimensional views and arrays. It is a concise compilation of existing ideas from excellent research articles @cite_6 @cite_17 and text books, e.g. @cite_9 . deals with the C++ implementation of the mathamtical concepts and provides some examples that show how the classes can be used in practice. Readers who prefer a practical introduction are encouraged to read first. discusses already implemented extensions based on the C++0x standard proposal @cite_2 . Section concludes the article.
@cite_9 @cite_2 @cite_6 @cite_17
2058033966 2112482891 2154032363 2154968583
This paper presents a new approach for automatically deriving worst-case resource bounds for C programs. The described technique combines ideas from amortized analysis and abstract interpretation in a unified framework to address four challenges for state-of-the-art techniques: compositionality, user interaction, generation of proof certificates, and scalability. Compositionality is achieved by incorporating the potential method of amortized analysis. It enables the derivation of global whole-program bounds with local derivation rules by naturally tracking size changes of variables in sequenced loops and function calls. The resource consumption of functions is described abstractly and a function call can be analyzed without access to the function body. User interaction is supported with a new mechanism that clearly separates qualitative and quantitative verification. A user can guide the analysis to derive complex non-linear bounds by using auxiliary variables and assertions. The assertions are separately proved using established qualitative techniques such as abstract interpretation or Hoare logic. Proof certificates are automatically generated from the local derivation rules. A soundness proof of the derivation system with respect to a formal cost semantics guarantees the validity of the certificates. Scalability is attained by an efficient reduction of bound inference to a linear optimization problem that can be solved by off-the-shelf LP solvers. The analysis framework is implemented in the publicly-available tool C4B. An experimental evaluation demonstrates the advantages of the new technique with a comparison of C4B with existing tools on challenging micro benchmarks and the analysis of more than 2900 lines of C code from the cBench benchmark suite. 1. High Performance Systems. An Example Program: Matrix Multiplication. Structure of a Compiler. 2. Programming Language Features. Languages for High Performance. Sequential and Parallel Loops. Roundoff Error. 3. Basic Graph Concepts. Sets, Tuples, Logic. Graphs. Control Dependence. 4. Review of Linear Algebra. Real Vectors and Matrices. Integer Matrices and Lattices. Linear System of Equations. System of Integer Equations. Systems of Linear Inequalities. Systems of Integer Linear Inequalities. Extreme Values of Affine Functions. 5. Data Dependence. Data Dependence in Loops. Data Dependence in Conditionals. Data Dependence in Parallel Loops. Program Dependence Graph. 6. Scalar Analysis with Factored Use-Def Chains. Constructing Factored Use-Def Chains. FUD Chains for Arrays. Finding All Reaching Definitions. Implicit References in FUD Chains. InductionVariables Using FUD Chains. Constant Propagation with FUD Chains. Data Dependence for Scalars. 7. Data Dependence Analysis for Arrays. Building the Dependence System. Dependence System Solvers. General Solver. Summary of Solvers. Complications. Run-time Dependence Testing. 8. Other Dependence Problems. Array Region Analysis. Pointer Analysis. I O Dependence. Procedure Calls. Interprocedural Analysis. 9. Loop Restructuring. Simpile Transformations. Loop Fusion. Loop Fission. Loop Reversal. Loop Interchanging. Loop Skewing. Linear Loop Transformations. Strip-Mining. Loop Tiling. Other Loop Transformations. Interprocedural Transformations. 10. Optimizing for Locality. Single Reference to Each Array. Multiple References. General Tiling. Fission and Fusion for Locality. 11. Concurrency Analysis. Code for Concurrent Loops. Concurrency from Sequential Loops. Concurrency from Parallel Loops. Nested Loops. Roundoff Error. Exceptions and Debuggers. 12. Vector Analysis. Vector Code. Vector Code from Sequential Loops. Vector Code from Forall Loops. Nested Loops. Roundoff Error, Exceptions, and Debuggers. Multivector Computers. 13. Message-Passing Machines. SIMD Machines. MIMD Machines. Data Layout. Parallel Code for Array Assignment. Remote Data Access. Automatic Data Layout. Multiple Array Assignments. Other Topics. 14. Scalable Shared-Memory Machines. Global Cache Coherence. Local Cache Coherence. Latency Tolerant Machines. Glossary. References. Author Index. Index. 0805327304T04062001 The theory of arrays, introduced by McCarthy in his seminal paper "Towards a mathematical science of computation," is central to Computer Science. Unfortunately, the theory alone is not sufficient for many important verification applications such as program analysis. Motivated by this observation, we study extensions of the theory of arrays whose satisfiability problem (i.e., checking the satisfiability of conjunctions of ground literals) is decidable. In particular, we consider extensions where the indexes of arrays have the algebraic structure of Presburger arithmetic and the theory of arrays is augmented with axioms characterizing additional symbols such as dimension, sortedness, or the domain of definition of arrays. We provide methods for integrating available decision procedures for the theory of arrays and Presburger arithmetic with automatic instantiation strategies which allow us to reduce the satisfiability problem for the extension of the theory of arrays to that of the theories decided by the available procedures. Our approach aims to re-use as much as possible existing techniques so as to ease the implementation of the proposed methods. To this end, we show how to use model-theoretic, rewriting-based theorem proving (i.e., superposition), and techniques developed in the Satisfiability Modulo Theories communities to implement the decision procedures for the various extensions. Heterogeneous computers with processors and accelerators are becoming widespread in scientific computing. However, it is difficult to program hybrid architectures and there is no commonly accepted programming model. Ideally, applications should be written in a way that is portable to many platforms, but providing this portability for general programs is a hard problem. By restricting the class of programs considered, we can make this portability feasible. We present Liszt, a domain-specific language for constructing mesh-based PDE solvers. We introduce language statements for interacting with an unstructured mesh, and storing data at its elements. Program analysis of these statements enables our compiler to expose the parallelism, locality, and synchronization of Liszt programs. Using this analysis, we generate applications for multiple platforms: a cluster, an SMP, and a GPU. This approach allows Liszt applications to perform within 12 of hand-written C++, scale to large clusters, and experience order-of-magnitude speedups on GPUs.