Design By Transformation Papers!

Here is our current list of DxT publications. The most recent papers are listed first. See the copyright notice.

Publications

Here are the publications of our research group listed in order of publication date. Each entry has a citation, an abstract, and a hypertext link to a PDF copy of the paper. See the copyright notice.

To search for multiple keywords separate each keyword by a comma: keyword , keyword

Keywords include:

architectures, analysis, aspects, categories, commuting diagrams, computational design, derivatives, Dense Linear Algebra (DLA),
Design by Transformation (DxT), design rules, Design Rule Checking (DRC), evolution, feature interactions, feature models, geodesic,
higher-order transformations, kubes, MDA, MDD, MDE, mixin layers, optimization, optional feature problem, origami, refactoring,
streaming, safe composition, semantics, testing, UML, verification, wizards, P3 (P1/P2/P3/DiSTiL data structure generator).

See all DxT publications

Total Publications: 15

B. Marker, D. Batory, R. van de Geijn. Understanding Performance Stairs: Elucidating Heuristics . Automated Software Engineering (ASE 2014)

How do experts navigate the huge space of implementations for a given specification to find an efficient choice with minimal searching? Answer: They use heuristics -- rules of thumb that are more street wisdom than scientific fact. We provide a scientific justification for Dense Linear Algebra (DLA) heuristics by showing that only a few decisions (out of many possible) are critical to performance; once these decisions are made, the die is cast and only relatively minor performance improvements are possible. The (implementation x performance) space of DLA is stair-stepped. Each stair is a set of implementations with very similar performance and (surprisingly) share key design decision(s). High-performance stairs align with heuristics that prescribe certain decisions in a particular context. Stairs also tell us how to tailor the search engine of a DLA code generator to reduce the time it needs to find implementations that are as good or better than those crafted by experts.

DxT DLA optimization

B. Marker Design by Transformation: From Domain Knowledge to Optimized Program Generation . Ph.D. dissertation, 2014, The Department of Computer Sciences, The University of Texas at Austin.

Expert design knowledge is essential to develop a library of high-performance software. This includes how to implement and parallelize domain operations, how to optimize implementations, and estimates of which implementation choices are best. An expert repeatedly applies his knowledge, often in a rote and tedious way, to develop all of the related functionality expected from a domain-specific library. Expert knowledge is hard to gain and is easily lost over time when an expert forgets or when a new engineer starts developing code. The domain of dense linear algebra (DLA) is a prime example with software that is so well designed that much of experts' important work has become tediously rote in many ways. In this dissertation, we demonstrate how one can encode design knowledge for DLA so it can be automatically applied to generate code as an expert would or to generate better code. Further, the knowledge is encoded for perpetuity, so it can be reused to make implementing functionality on new hardware easier or it can be used to teach how software is designed to a non-expert. We call this approach to software engineering (encoding expert knowledge and automatically applying it) Design by Transformation (DxT). We present our vision, the methodology, a prototype code generation system, and possibilities when applying DxT to the domain of dense linear algebra.

student DxT

R.C. Goncalves, D. Batory, J.L. Sobral ReFlO: An Interactive Tool for Pipe-And-Filter Domain Specification and Program Generation To appear, Software and Systems Modeling, 2014.

ReFlO is a framework and interactive tool to record and systematize domain knowledge used by experts to derive complex pipe-and-filter (PnF) applications. Domain knowledge is encoded as transformations that alter PnF graphs by refinement (adding more details), flattening (removing modular boundaries), and optimization (substituting inefficient PnF graphs with more efficient ones). All three kinds of transformations arise in reverse-engineering legacy PnF applications. We present the conceptual foundation and tool capabilities of ReFlO, illustrate how parallel PnF applications are designed and generated, and how domain-specific libraries of transformations are developed.

DxT, refinements, optimizations, Perry Substitition Principle, PSP

B. Marker, R. van de Geijn, and D. Batory Interfaces are Key . 1st Int. Workshop on Software Engineering for High Performance Computing in Computational Science and Engineering

Many dense linear algebra (DLA) operations are easy to understand at a high level and users get functional DLA code on new hardware relatively quickly. As a result, many people consider DLA to be a 'solved domain'. The truth is that DLA is not solved. DLA experts are rare because the 'tricks' and variety of algorithms they need to get high performance take time to learn. DLA implementations are only available on a new architecture when an expert with enough experience goes through a rote process to implement many related DLA operations. While so much of the manual work is rote, this hardly suggests the domain is 'solved'. We have not proven that we understand the field until we have automated the expert. Automate the expert for the entire field, and the field is closed. We view that goal as the equivalent of going to Mars. In practice, we will get to the moon automatically, and experts will then be freed up to worry about how to get from there to Mars.

DxT DLA

D. Batory, R. Goncalves, B. Marker, J. Siegmund. Dark Knowledge and Graph Grammars in Automated Software Design . Keynote at Conference on Software Language Engineering (SLE) 2013.

Mechanizing the development of hard-to-write and costly-to-maintain software is the core problem of automated software design. Encoding expert knowledge (a.k.a. dark knowledge) about a software domain is central to its solution. We assert that a solution can be cast in terms of the ideas of language design and engineering. Graph grammars can be a foundation for modern automated software development. The sentences of a grammar are designs of complex dataflow systems. We explain how graph grammars provide a framework to encode expert knowledge, produce correct-by-construction derivations of dataflow applications, enable the generation of high-performance code, and improve how software design of dataflow applications can be taught to undergraduates.

keynote, DxT, MDE, MDA, MDD

B. Marker, D. Batory, and R. van de Geijn. A Case Study in Mechanically Deriving Dense Linear Algebra Code . International Journal of High Performance Computing Applications.

Design by Transformation (DxT) is a top-down approach to mechanically derive high-performance algorithms for dense linear algebra. We use DxT to derive the implementation of a representative matrix operation, two- sided Trmm. We start with a knowledge base of transformations that were encoded for a simpler set of operations, the level-3 BLAS, and add only a few transformations to accommodate the more complex two-sided Trmm. These additions explode the search space of our prototype system, DxTer, requiring the novel techniques defined in this paper to eliminate large segments of the search space that contain suboptimal algorithms. Performance results for the mechanically optimized implementations on 8,192 cores of a BlueGene/P architecture are given.

DxT, DLA, MDE, MDA, MDD

B. Marker, D. Batory, R. van de Geijn. DSLs, DLA, DxT, and MDE in CSE . International Workshop on Software Engineering for Computational Science and Engineering (SECSE), May 2013.

We narrate insights from a collaboration between researchers in Software Engineering (SE) and in the domain of Dense Linear Algebra (DLA) libraries. We highlight our impressions of how software development for computational science has traditionally been different from the development of software in other domains. We observe that scientific software (at least DLA libraries) is often developed by domain experts rather than legions of programmers. For this reason, researchers in SE need to impact the productivity of experts rather than the productivity of the masses. We document this and other lessons learned.

DSLs, DxT, DLA, MDE, MDA, MDD

B. Marker, D. Batory, R. van de Geijn. Code Generation and Optimization of Distributed-Memory Dense Linear Algebra Kernels . International Workshop on Automatic Performance Tuning (IWAPT), June 2013.

Design by Transformation (DxT) is an approach to software development that encodes domain-specific programs as graphs and expert design knowledge as graph transformations. The goal of DxT is to mechanize the generation of highly-optimized code. This paper demonstrates how DxT can be used to transform sequential specifications of an important set of Dense Linear Algebra (DLA) kernels, the level-3 Basic Linear Algebra Subprograms (BLAS3), into high-performing library routines targeting distributed-memory (cluster) architectures. Getting good BLAS3 performance for such platforms requires deep domain knowledge, so their implementations are manually coded by experts. Unfortunately, there are few such experts and developing the full variety of BLAS3 implementations takes a lot of repetitive e ort. A prototype tool, DxTer, automates this tedious task. We explain how we build on previous work to represent loops and multiple loop-based algorithms in DxTer. Performance results on a BlueGene/P parallel supercomputer show that the generated code meets or beats implementations that are hand-coded by a human expert and outperforms the widely used ScaLAPACK library.

DxT, DLA, MDE, MDA, MDD, optimization, streaming

T. Riché, R. Goncalves, B. Marker, and D. Batory. Pushouts in Software Architecture Design . Generative Programming and Component Engineering (GPCE), September 2012.

A classical approach to program derivation is to progressively extend a simple specification and then incrementally refine it to an implementation. We claim this approach is hard or impractical when reverse engineering legacy software architectures. We present a case study that shows optimizations and pushouts -- in addition to refinements and extensions -- are essential for practical stepwise development of complex software architectures.

architectures, DxT, MDE, MDA, MDD, riche

B. Marker, J. Poulson, D. Batory, and R. van de Geign. Designing Linear Algebra Algorithms by Transformation: Mechanizing the Expert Developer . International Workshop on Automatic Performance Tuning (IWAPT), July 2012.

To implement dense linear algebra algorithms for distributed-memory computers, an expert applies knowledge of the domain, the target architecture, and how to parallelize common operations. This is often a rote process that becomes tedious for a large collection of algorithms. We have developed a way to encode this expert knowledge such that it can be applied by a system to generate mechanically the same (and sometimes better) highly-optimized code that an expert creates by hand. This paper illustrates how we have encoded a subset of this knowledge and how our system applies it and searches a space of generated implementations automatically.

architectures, DxT, MDE, MDA, MDD.

J. Feigenspan, D. Batory, and T. Riché. Is the Derivation of a Model Easier to Understand than the Model Itself? . International Conference on Program Comprehension (ICPC), June 2012.

Software architectures can be presented by graphs with components as nodes and connectors as edges. These graphs, or models, typically encode expert domain knowledge, which makes them difficult to understand. Hence, instead of presenting a complete complex model, we can derive it from a simple, easy-to-understand model by a set of easy-to-understand transformations. In two controlled experiments, we evaluate whether a derivation of a model is easier to understand than the model itself.

architectures, DxT, MDE, MDA, MDD, riche

B. Marker, A. Terrel, J. Poulson, R. van de Geijn, and D. Batory. Mechanizing the Expert Dense Linear Algebra Developer (Poster Paper) . Principles and Practice of Parallel Programming (PPoPP), February 2012.

The efforts of an expert to parallelize and optimize a dense linear algebra algorithm for distributed-memory targets are largely mechanical and repetitive. We demonstrate that these efforts can be encoded and automatically applied to obviate the manual implementation of many algorithms in high-performance code.

DxT, MDE, DLA, dense linear algebra

B. Marker, D. Batory, J. Poulson, and R. van de Geijn. How a Domain-Specific Language Enables the Automation of Optimized Code for Dense Linear Algebra (Extended Abstract) . International Workshop on Domain-Specific Languages and High-Level Frameworks for High Performance Computing (WOLFHPC), May 2011.

DxT, MDE, MDA, MDE, streaming architectures, DLA

T.L. Riché, H.M. Vin, and D. Batory. Transformation-Based Parallelization of Request-Processing Applications . Model Driven Engineering Languages and Systems (MODELS), October 2010.

Multicore, multithreaded processors are rapidly becoming the platform of choice for high-throughput request-processing applications (RPAs). We refer to this class of modern parallel platforms as multi-* systems. In this paper, we describe the design and implementation of Lagniappe, a translator that simplifies RPA development by transforming portable models of RPAs to highthroughput multi-* executables. We demonstrate Lagniappe’s effectiveness with a pair of stateful RPA case studies.

MDD riche MDE computational design award streaming architectures DxT

D. Batory (work with T. Riché). Refinement and Optimization of Streaming Architectures. Keynote at Software Engineering and Data Engineering (SEDE), Las Vegas, June 2009 and the Software Engineering and Databases (JISDB), San Sebastian, Spain, September 2009.

We present a Model Driven Engineering approach to explain, verify, build, and test dataflow or streaming software architectures that are to be parallelized for performance or availability. Componentconnector models are incrementally elaborated by transformations that refine or optimize architectural designs. We re-engineered two significant case studies to illustrate the generality of our work: (1) recoverable crash fault tolerant servers and (2) join parallelizations in database machines.

PDF of presentation

DxT, keynote, pipe-and-filter, architectural refinement, optimization, riche