Towards dense linear algebra for hybrid GPU accelerated manycore systems

We highlight the trends leading to the increased appeal of using hybrid multicore + GPU systems for high performance computing. We present a set of techniques that can be used to develop efficient dense linear algebra algorithms for these systems. We illustrate the main ideas with the development of a hybrid LU factorization algorithm where we split the computation over a multicore and a graphics processor, and use particular techniques to reduce the amount of pivoting and communication between the hybrid components. This results in an efficient algorithm with balanced use of a multicore processor and a graphics processor.     

An initial algebra approach to term rewriting systems with variable binders

We present an extension of first-order term rewriting systems. It involves variable binding in the term language. We develop systems called binding term rewriting systems (BTRSs) in a stepwise manner. First we present the term language, then formulate equational logic. Finally, we define rewriting systems. This development is novel because we follow the initial algebra approach in an extended notion of Σ-algebras in various functor categories. These are based on Fiore-Plotkin-Turi’s presheaf semantics of variable binding and Lüth-Ghani’s monadic semantics of term rewriting systems. We characterise the terms, equational logic and rewrite systems for BTRSs as initial algebras in suitable categories. Then, we show an important rewriting property of BTRSs: orthogonal BTRSs are confluent. Moreover, by using the initial algebra semantics, we give a complete characterisation of termination of BTRSs. Finally, we discuss our design choice of BTRSs from a semantic perspective. An erlier version appeared in Proc. Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP2003).     

A scalable approach to solving dense linear algebra problems on hybrid CPU‐GPU systems

Aiming to fully exploit the computing power of all CPUs and all graphics processing units (GPUs) on hybrid CPU‐GPU systems to solve dense linear algebra problems, we design a class of heterogeneous tile algorithms to maximize the degree of parallelism, to minimize the communication volume, and to accommodate the heterogeneity between CPUs and GPUs. The new heterogeneous tile algorithms are executed upon our decentralized dynamic scheduling runtime system, which schedules a task graph dynamically and transfers data between compute nodes automatically. The runtime system uses a new distributed task assignment protocol to solve data dependencies between tasks without any coordination between processing units. By overlapping computation and communication through dynamic scheduling, we are able to attain scalable performance for the double‐precision Cholesky factorization and QR factorization. Our approach demonstrates a performance comparable to Intel MKL on shared‐memory multicore systems and better performance than both vendor (e.g., Intel MKL) and open source libraries (e.g., StarPU) in the following three environments: heterogeneous clusters with GPUs, conventional clusters without GPUs, and shared‐memory systems with multiple GPUs. Copyright © 2014 John Wiley & Sons, Ltd.     

Tensor computations in computer algebra systems

This paper considers three types of tensor computations. On their basis, we attempt to formulate criteria that must be satisfied by a computer algebra system dealing with tensors. We briefly overview the current state of tensor computations in different computer algebra systems. The tensor computations are illustrated with appropriate examples implemented in specific systems: Cadabra and Maxima.     

An algebra of product families

Experience from recent years has shown that it is often advantageous not to build a single product but rather a family of similar products that share at least one common functionality while having well-identified variabilities. Such product families are built from elementary features that reach from hardware parts to software artefacts such as requirements, architectural elements or patterns, components, middleware, or code. We use the well established mathematical structure of idempotent semirings as the basis for a product family algebra that allows a formal treatment of the above notions. A particular application of the algebra concerns the multi-view reconciliation problem that arises when complex systems are modelled. We use algebraic integration constraints linking features in one view to features in the same or a different view and show in several examples the suitability of this approach for a wide class of integration constraint formulations. Our approach is illustrated with a Haskell prototype implementation of one particular model of product family algebra.     

An algebra of mixed computation

Algebraic tools for mixed computation are presented. Some axioms for informational objects, program functions, inputs and outputs are introduced. These axioms are sufficient for the correct mixed computation of some basic program composition forms.     

An algebra of temporal faults

Faults modelling is essential to anticipate failures in critical systems. Traditionally, Static Fault Trees are employed to this end, but Temporal and Dynamic Fault Trees are gaining evidence due to their enriched power to model and detect intricate propagation of faults that lead to a failure. In previous work, we showed a strategy based on the process algebra CSP and Simulink models to obtain fault traces that lead to a failure. Although that work used Static Fault Trees, it could be used with Temporal or Dynamic Fault Trees. In the present work we define an algebra of temporal faults (with a notion of fault propagation) and prove that it is indeed a Boolean algebra. This allows us to inherit Boolean algebra’s properties, laws and existing reduction techniques, which are very beneficial for faults modelling and analysis. We illustrate our work on a simple but real case study supplied by our industrial partner EMBRAER.     

An algebra for commitment protocols

Protocols enable unambiguous, smooth interactions among agents. Commitments among agents are a powerful means of developing protocols. Commitments enable flexible execution of protocols and help agents reason about protocols and plan their actions accordingly, while at the same time providing a basis for compliance checking. Multiagent systems based on commitments can conveniently and effectively model business interactions because the autonomy and heterogeneity of agents mirrors real-world businesses. Such modeling, however, requires multiagent systems to host a rich variety of protocols that can capture the needs of different applications. We show how a commitment-based semantics provides a basis for refining and aggregating protocols. We propose an approach for designing commitment protocols wherein traditional software engineering notions such as refinement and aggregation are extended to apply to protocols. We present an algebra of protocols that can be used to compose protocols by refining and merging existing ones, and does this at a level of abstraction high enough to be useful for real-world applications. We thank Amit Chopra, Nirmit Desai, and anonymous referees for valuable comments. This research was supported partially by the NSF under grant DST-0139037, and partially by DARPA under contract F30603-00-C-0178.     

An algebra for probabilistic databases

An algebra is presented for a simple probabilistic data model that may be regarded as an extension of the standard relational model. The probabilistic algebra is developed in such a way that (restricted to α-acyclic database schemes) the relational algebra is a homomorphic image of it. Strictly probabilistic results are emphasized. Variations on the basic probabilistic data model are discussed. The algebra is used to explicate a commonly used statistical smoothing procedure and is shown to be potentially very useful for decision support with uncertain information     

An algebra for process creation

In this paper, we study the issue of process creation from an algebraic perspective. The key to our approach, which is inspired by work of America and De Bakker, consists of giving a new interpretation to the operator symbol · (sequential composition) in the axiom system BPA of Bergstra and Klop. We present a number of other models for BPA and show how the new interpretation of · naturally generalises the usual interpretation in ACP. We give an operational semantics based on Plotkin style inductive rules for a simple language with process creation and communication, and give a complete finite axiomatisation of the associated bisimulation model. Note: Partial support received from the European Communities under ESPRIT contract 432, An Integrated Formal Approach to Industrial Software Development (METEOR), and RACE contract 1046, Specification and Programming Environment for Communication Software (SPECS).     

Image algebra: An overview

This paper is the first in a sequence of papers describing an algebraic structure for image processing that has become known as the AFATL Standard Image Algebra. This algebra provides a common mathematical environment for image processing algorithm development and methodologies for algorithm optimization, comparison, and performance evaluation. In addition, the image algebra provides a powerful algebraic language for image processing which, if properly embedded into a high level programming language, will greatly increase a programmer's productivity as programming tasks are greatly simplified due to replacement of large blocks of code by short algebraic statements. The purpose of this paper is to familiarize the reader with the basic concepts of the algebra and to provide a general overview of its methodology.     

Using computer algebra systems in mathematical classrooms

Abstract This paper describes a research whose main focus is the use of Computer Algebra Systems (CAS) in mathematical classrooms and the didactical possibilities linked with its use. The possibilities of integrating Self-Regulated Learning (SRL) within the CAS environment are brought into focus. Forty-three Israeli students (mean age 13.3) were assigned to two learning algebraic groups. The first group received explicit meta-cognitive SRL with CAS (CAS + SRL); the second group was exposed to CAS without SRL (CAS). Empirical results from the experimental and case study designs revealed that (CAS + SRL) students outperformed (CAS) students on algebraic thinking and that (CAS + SRL) students regulated their learning more effectively.     

Dynamics of serial chain systems using dual algebra

Multibody System Dynamics - Dynamic modelling of a multibody system is critical to analyse its behaviour under different circumstances. This paper proposes the dynamic modelling of a rigid...