Here is our current list of DxT publications. The most recent papers are listed first. See the copyright notice.
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).
D. Batory. Teaching Modeling and Variability in Software Design and its Importance to Science . Keynote at Workshop on Modelling in Software Engineering (MiSE), Austin, Texas, May 2016 and at Workshop on Formal Methods in Software Engineering (FormaliSE), Austin, Texas, May 2016.
The goal of Automated Software Design (ASD) is to automate tasks of
program development and to identify the "laws" or algebraic
identities -- general or domain specific -- that software engineers
use implicitly in designs but may not realize it. I trace this
idea from material that I present in my classes to fundamental
results and recent advances in ASD research.
DxT, keynote, laws, relational query optimization, UML, refactorings
R. Goncalves, D. Batory, J. Sobral, and T. Riche. From Software Extensions to Product Lines of Dataflow Programs . Software and Systems Modeling (SoSym), 2015 .
Dataflow programs are widely used. Each program is a directed graph where nodes are computations and edges indicate the flow of data. In prior work, we reverse-engineered legacy dataflow programs by deriving their optimized implementations from a simple specification graph using graph transformations called refinements and optimizations. In MDE-speak, our derivations were PIM-to-PSM mappings. In this paper, we show how extensions complement refinements, optimizations, and PIM-to-PSM derivations to make the process of reverse engineering complex legacy dataflow programs tractable. We explain how optional functionality in transformations can be encoded, thereby enabling us to encode product lines of transformations as well as product lines of dataflow programs.We describe the implementation of extensions in the ReFlO tool and present two non-trivial case studies as evidence of our work’s generality. Keywords: MDE, PIM, PSM, model transformation, software extension, dataflow programs, software product line.
MDE, MDA, MDD, DxT, refinements, optimizations, extensions
D. Batory, B. Marker, and R. van de Geijn. Opportunities in Computational Science to Advance Software Engineering . Computational Science and Engineering Software Sustainability and Productivity Challenges (CSESSP), Oct. 2015 .
We describe the disparity between current-day Software Engineering (SE) research and that which is needed to advance Computational Science and Engineering (CSE) research. We explain how overcome the SE/CSE gap and explain our progress to date.
DSLs, DxT, DLA, MDE, MDA, MDD
R. Goncalves. Parallel Programming by Transformation. Ph.D. dissertation, 2015, The MAP-i Doctoral Program of the Universities of Minho, Aveiro and Porto, Portugal.
The development of effient software requires the selection of algorithms and
optimizations tailored for each target hardware platform. Alternatively, performance
portability may be obtained through the use of optimized libraries. However,
currently all the invaluable knowledge used to build optimized libraries
is lost during the development process, limiting its reuse by other developers
when implementing new operations or porting the software to a new hardware
platform.
To answer these challenges, we propose a model-driven approach and framework
to encode and systematize the domain knowledge used by experts when
building optimized libraries and program implementations. This knowledge is
encoded by relating the domain operations with their implementations, capturing
the fundamental equivalences of the domain, and defining how programs can be
transformed by refinement (adding more implementation details), optimization
(removing ineffiencies), and extension (adding features). These transformations
enable the incremental derivation of efficient and correct by construction
program implementations from abstract program specifications. Additionally,
we designed an interpretations mechanism to associate different kinds of behavior
to domain knowledge, allowing developers to animate programs and predict
their properties (such as performance costs) during their derivation. We developed
a tool to support the proposed framework, ReFlO, which we use to illustrate
how knowledge is encoded and used to incrementally|and mechanically|derive
effcient parallel program implementations in different application domains.
The proposed approach is an important step to make the process of developing
optimized software more systematic, and therefore more understandable and
reusable. The knowledge systematization is also the first step to enable the
automation of the development process.
DxT architectures dataflow categories higher-order transformations MDE student
B. Marker, D. Batory, F. Van Zee, R. van de Geijn. Making Scientific Computing Libraries Forward Compatible . Workshop on Working towards Sustainable Software for Science: Practice and Experiences (WSSSPE 2014)
NSF's Software Infrastructure for Sustained Innovation funds the development of community software in support of scientific computing innovation. A requirement is that the developed software be sustainable. Design-by-Transformation (DxT) is an approach to software development that views libraries not as instantiated in code, but as expert knowledge that is combined with knowledge about a target architecture by a tool (DxTer) that synthesizes the library implementation. We argue that this approach makes libraries to some degree forward compatible in that a (disruptive) new architectural advance can be accommodated by encoding knowledge about that architecture. This is particularly important when bugs are not correctness bugs, but instead performance bugs that affect how fast an answer is obtained and/or how much energy is consumed to compute the answer. DxT allows a human expert to focus on developing the primitives from which libraries are constructed and new insights as opposed to the rote application of known ideas to entire libraries. We summarize our success in the domain of dense linear algebra as evidence of DxT’s potential.
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 . 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 effort. 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. Riche, 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. Riche. 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. Riche, 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. Riche). 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
Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.