Pipe-and-filter (PnF) architectures are a fundamental class of software designs. Complex parallel PnF architectures can be derived by transformations that codify design knowledge used by domain experts. Starting with a simple sequential PnF architecture, we apply transformations to refine (reveal hierarchical detail), optimize (break modular boundaries to achieve efficiency or availability), and extend (incrementally expose more architecture functionality) to derive a parallel architecture. More information is obtained by following the hyperlinks below.
| Basics | Case Studies | Tools | Research Support | Publications |
A pipe-and-filter architecture is a directed multi-graph of boxes and connectors that defines the implementation of a system. A box is a component with input and output ports. A connector is a communication path for messages pointing in the direction of dataflow from an output port to one or more input ports.
A filter architecture is an example (Fig. (a)). It consists of a single box FILTER that takes a stream of photographs P as input, examines each photograph p in P, and outputs p only if some criteria is satisfied. A shorter stream Q is produced. FILTER may have other parameters, such as a photograph type and filtering criteria. We elide these details without loss of generality.
An architectural transformation is a mapping (a multi-graph rewrite) of an input architecture to an output architecture an elementary architecture into a complex, sophisticated architecture. There are at least 3 basic transformations that we consider:
Refinement is the rewrite of replacing an interface with an implementation. A refinement replaces the FILTER box of Fig (a) with the FILTERb box resulting in Fig (b). Another refinement replaces the FILTER box of Fig (a) with its map-reduce counterpart in Fig (c), showing that an input stream can be split into substreams, where each substream is filtered in parallel, and the output substreams are merged.
Optimization is the rewrite of an inefficient composition of boxes (multi-graph) with a functionally equivalent and more efficient multi-graph. Normally, optimizations break encapsulation boundaries. Fig (a) below is an example. Modular boundaries are indicated by dashed lines. The LEFT box processes stream H by box F. The RIGHT box immediately processes its input by box F^-1, the inverse of F. Fig (b) dissolves these boundaries, exposes the inefficiency, and reveals the IDENTITY abstraction of which (F followed by F^-1) is an implementation. Fig (c) is the optimized architecture.
Extension is the rewrite that adds functionality to an architecture, much like adding a new feature (as in software product lines) to a program. Extension is related to subclassing, where a subclass extends the functionality of its superclass. Fig (a) below shows an architecture α with a Sort and WebServer box. The WebServer takes sorted tuples and creates a webpage of sorted results. Fig (b) shows an extended architecture b that permits sort keys to be altered at run time. Sort and WebServer are extended with new ports (Sort ESort and WebServer EWebServer) and a feedback connector labeled newKey is added. A newKey message changes the key that ESort uses to sort incoming tuples (e.g. switching from last names to ID numbers in a patient database or artists to album titles in a music player).
DxT can be used as a principled way to re-engineer legacy applications or to forward engineer new applications. (The former is used for domains containing a single application, whereas the latter is used when transformations describe a combinatorial number of derivable applications). Our primary application is to forward engineer dense linear algebra applications using the Flame methodology and Elemental library. Our goal is to express the design knowledge of Elemental as transformations, and to generate Elemental libraries for new architectures, rather than hand-deriving such libraries. Doing so will be a significant accomplishment -- both in software engineering in general, and dense linear algebra in particular. To date, our case studies include DxT designs of
Asynchronous crash fault tolerant servers
Parallel implementations of database hash joins
Efficient and parallel implementations of Dense Linear Algebra (DLA) applications
ReFlO -- this is a general-purpose graphical tool for defining and applying rewrite rules in the DxT manner.
DxTer -- using DxT rewrite rules, DxTer is a general "program transformation engine" that will explore the space of possible implementations and select the most efficient implementation automatically.
DxT work is supported by:
NSF's Science of Design Grant #CCF-0724979
Portuguese Science Foundation (FCT) grant SFRH/BD/47800/2008.
Portuguese Science Foundation (FCT) project UTAustin/CA/0056/2008.
NSF’s Computer Systems Research Grant CNS 0509338
NSF Graduate Research Fellowship DGE-11100007