Design by Transformation:
Encoding Domain Knowledge to Derive
Optimized Program Architectures
Rui C. Gonçalve
Universidade do MinhsoUniversidad Jaume I, November 2012

Context and Motivatio• Complexity of hardware platforms is increasin• Burden of improving software has moved from hardware
manufacturers to developer• Development of ef cient software is a complex tas• Requires deep knowledge of the application domain andtarget hardware platfor• Tedious, time-consuming, and error-prone tas• Non-experts cannot reproduce, or even understand thedevelopment proceskgkn	smfis• Knowledge used to optimize programs is not reusableDesign by Transformation (DxT)• Encode domain knowledge as transformation• Transform models to map high-level speci cations to ef cientimplementation• Make domain knowledge reusabl• Enable automatio• Specify interfaces of domain operations and theirimplementation• Specify domain-speci c optimization• High-level representation of knowledge that makes it more
understandable by non-expert

fis

fissefinss• Requires regular and mature domains of application

ReFlO Tool
• MDE tool for modeling application domains and synthesize
ef cient program architecture• Modeling application domain• Specify interfaces, algorithms (pipe-and- lter implementations),primitives (code implementations• Specify interfaces, primitives and algorithms propagation functions(used to model properties propagation functions, preconditions• Synthesize ef cient program architecture• Re ne and optimize an initial high-level architecture, to obtain an
ef cient architectur• Obtain the properties of the architecture (e.g., cost) to evaluate its)

sfis)

sefi

fififiqualityModeling the Domain

Interfaces• To specify the interface for an operation, we create aninterface bo• Interface boxes hav• Name, input/output ports, and additional parameter• Ports have name and data typ• Additional parameters are inputs that are not shown asportseexs• Properties propagation functions

Algorithms• Specify how an interface can be implemente• Composes interfaces, using connectors to create a pipeand- lter grap

• Algorithm boxes havsdehfi• Name, input/output ports, and additional parameter• Properties propagation functions

Primitives• Specify the code implementations available for aninterfac• Primitive boxes havsee• Name, input/output ports, and additional parameter• Properties propagation functions

DxT Domain Model• Pairs interfaces with their implementations• An interface may be implemented by an algorithm or aprimitive• Pairs form rewrite rules, that define valid replacements forinterfaces (module preconditions)

DxT Domain Models• Rewrite rules also specify how to optimize inef cientfi

compositions of boxesAdditional Parameters• Some inputs represent data that ows through thediagram boxes (e.g. streams in databases, matricesin BLAS

• Called Essential Parameter• Other inputs are just constants, or copied from parentbox (e.g. attribute used as key when sorting a stream,transposition attributes in BLASfl)ss)• Called Additional Parameter• Not shown in graphical representations

Propagation Functions

Propagation Functions• Propagation Functions allow to associate behavior
with boxes, to later animate model• Extract info (or properties) from architecture• Example: associating to each box how it affects thedata sizes (a propagation function), we will be able tolater predict the data sizes of an architecture output• Similar ideas may be used to compute costs orsss

perform type checking, for example

Propagation Functions• Providing code for each box allows us to generate
code for any architecture and execute i• Providing properties propagation functions for eachbox allows us to animate an architecture and extract
properties from i• Several propagation functions may be executed insequenc• E.g.: to compute costs, we may rst have to compute datasizetfitefis• Speci ed in JavaPreconditions• Interfaces, primitives and algorithms haveprecondition• Preconditions restrict the architectures where a box
can be use• Boolean-valued function of properties of inputs andadditional parameter

fissd• Preconditions are de ned using propagation functions

Preconditions• do_nothing is a valid implementation for SORT when
the input stream is already sorted

Propagation Functions andPreconditions• SORT: output is always sorte
public void compute()
setOutputProperty("A", "IsSorted", true)}• SPLIT: outputs are sorted iff input is sorte
public void compute()
Boolean inA = getInputProperty("A", "IsSorted")
setOutputProperty("A1", "IsSorted", inA)
setOutputProperty("A2", "IsSorted", inA)}

• do_nothing (precondition): if input is not sorted throw an error

d;

;d;

;

;

;

{{{

public void compute()
Boolean inA = getInputProperty("A", "IsSorted")if(!inA) addError("Input is not sorted!")}Program Architecture
Transformation/Synthesis

Initial Architecture• Initial architecture is represented by an architecturebox (similar to an algorithm box), which speci es animplementation of the program to optimiz• To use properties, we must provide the properties ofprogram inputs/outputs, that ReFlO will propagat

efie• Properties may be just strings denoting variables

Re nements• Replace an interface with one of its implementation• Implementation preconditions (if any provided) aretested to build the list of possible implementation• Flatten transformation may then be used to removessfi

the algorithm boundaries

Project Sort ArchitectureProject Sort ArchitectureProject Sort ArchitectureProject Sort Architecture• The removal of the modular boundaries exposes
fiinef ciencies

Optimizing Abstractions• Aggregates a set of boxes, that are composed as analgorith• Preconditions are tested to ensure that architecture
remains correct after the transformatio• Operation Find Patterns automatically identi es thefinm

sets of boxes that can be abstracted

Project Sort ArchitectureProject Sort ArchitectureProject Sort ArchitectureProject Sort ArchitectureProject Sort ArchitectureRunning PropagationFunctions• At any point during the synthesis process, we can runpropagation function• Just select the architecture, and enter the propagation
functions to ru• Allows us to keep track of the evolution of costs (orsnother quality attributes) of the architectures

Other Features of ReFlO• Export DxT Domain Models to HTML documentatio• Requires the user to document the model elements(boxes, ports• Export DxT Domain Models to external tool (DxTer),that automates the search for the best implementatio• Some code needs to be manually provided as modelnn)annotations (e.g., preconditions)Summary• Approach/framework to encode (reusable) domain
knowledge using a pipe-and- lter notatio• Operations and their implementation• Optimization• Make domain knowledge accessible by non-expert• Transformation system for pipe-and- lter graphs tosynthesize program architecture• Incrementally build optimized architecture• Enable automatio

sns

fissfins• Animate architectures, and compute properties about them

Thank You!
• Some references• http://www.cs.utexas.edu/users/schwartz/DxT• Taylor Riché, Don Batory, Rui Gonçalves, Bryan Marker. Architecture
Design by Transformation. UT-CS Technical Report TR-10-39, 2010

• Taylor Riché, Rui Gonçalves, Bryan Marker, Don Batory. Pushouts in
Software Architecture Design. Generative Programming andComponent Engineering 2012

• Bryan Marker, Jack Poulson, Don Batory, and Robert van de Geign.

Designing Linear Algebra Algorithms by Transformation: Mechanizing
the Expert Developer. International Workshop on Automatic
Performance Tuning 2012.

/.

.

:

• Questions?