Engr 691-1: Special Topics in Engineering Science
Software Architecture
Spring Semester 2004
Lecture Notes


Pipes and Filters Architectural Pattern

Definition

"The Pipes and Filters architectural pattern provides a structure for systems that process a stream of data. Each processing step is encapsulated in a filter component. Data [are] passed through pipes between adjacent filters. Recombining filters allows you to build families of related filters." [Buschmann]

Context

The context consists of programs that must process streams of data.

Problem

Suppose we need to build a system to solve a problem:

The design of the components and their interconnections must consider the following forces [Buschmann]:

Solution

Structure

The filters are the processing units of the pipeline. A filter may enrich, refine, or transform its input data [Buschmann].

A filter may be active (the more common case) or passive.

The pipes are the connectors--between a data source and the first filter, between filters, and between the last filter and a data sink. As needed, a pipe synchronizes the active elements that it connects together.

A data source is an entity (e.g., a file or input device) that provides the input data to the system. It may either actively push data down the pipeline or passively supply data when requested, depending upon the situation.

A data sink is an entity that gathers data at the end of a pipeline. It may either actively pull data from the last filter element or it may passively respond when requested by the last filter element.

See the Class-Responsibility-Collaborator (CRC) cards for these elements on page 56 of the Buschmann book.

Implementation

Implementation of the pipes-and-filters architecture is usually not difficult. It often includes the following steps [Buschmann]:

  1. Divide the functionality of the problem into a sequence of processing steps.

    Each step should only depend upon the outputs of the previous step in the sequence. The steps will become the filters in the system.

    In dividing up the functionality, be sure to consider variations or later changes that might be needed--a reordering of the steps or substitution of one processing step for another.

  2. Define the type and format of the data to be passed along each pipe.

    For example, Unix pipes carry an unstructured sequence of bytes. However, many Unix filters read and write streams of ASCII characters that are structured into lines (with the newline character as the line terminator).

    Another important formatting issue is how the end of the input is marked. A filter might rely upon a system end-of-input condition or it may need to implement their own "sentinel" data value to mark the end.

  3. Determine how to implement each pipe connection.

    For example, a pipe connecting active filters might be implemented with operating system or programming language runtime facility such as a message queue, a Unix-style pipe, or a synchronized-access bounded buffer.

    A pipe connecting to a passive filter might be implemented as a direct call of the adjacent filter: a push connection as a call of the downstream filter as a procedure or a pull connection as a call of the upstream filter as a function.

  4. Design and implement the filters.

    The design of a filter is based on the nature of the task to be performed and the natures of the pipes to which it can be connected.

    The selection of the size of the buffer inside a pipe is an important performance tradeoff. Large buffers may use up much available memory but likely will involve less synchronization and context-switching overhead. Small buffers conserve memory at the cost of increased overhead.

    To make filters flexible and, hence, increase their potential reusability, they often will need different processing options that can be set when they are initiated. For example, Unix filters often take command line parameters, access environment variables, or read initialization files.

  5. Design for robust handling of errors.

    Error handling is difficult in a pipes-and-filters system since there is no global state and often multiple asynchronous threads of execution. At the least, a pipes-and-filters system needs mechanisms for detecting and reporting errors. An error should not result in incorrect output or other damage to the data.

    For example, a Unix program can use the stderr channel to report errors to its environment.

    More sophisticated pipes-and-filters systems should seek to recover from errors. For example, the system might discard bad input and resynchronize at some well-defined point later in the input data. Alternatively, the system might back up the input to some well-defined point and restart the processing, perhaps using a different processing method for the bad data.

  6. Configure the pipes-and-filters system and initiate the processing.

    One approach is to use a standardized main program to create, connect, and initiate the needed pipe and filter elements of the pipeline.

    Another approach is to use an end-user tool, such as a command shell or a visual pipeline editor, to create, connect, and initiate the needed pipe and filter elements of the pipeline.

Example

An example pipes-and-filter system might be a retargetable compiler for a programming language. The system might consist of a pipeline of processing elements similar to the following:

  1. A source element reads the program text (i.e., source code) from a file (or perhaps a sequence of files) as a stream of characters.

  2. A lexical analyzer converts the stream of characters into a stream of lexical tokens for the language--keywords, identifier symbols, operator symbols, etc.

  3. A parser recognizes a sequence of tokens that conforms to the language grammar and translates the sequence to an abstract syntax tree.

  4. A "semantic" analyzer reads the abstract syntax tree and writes an appropriately augmented abstract syntax tree.

    Note: This element handles context-sensitive syntactic issues such as type checking and type conversion in expressions.

  5. A global optimizer (usually optionally invoked) reads an augmented syntax tree and outputs one that is equivalent but corresponds to program that is more efficient in space and time resource usage.

    Note: A global optimizer may transform the program by operations such as factoring out common subexpressions and moving statements outside of loops.

  6. An intermediate code generator translates the augmented syntax tree to a sequence of instructions for a virtual machine.

  7. A local optimizer converts the sequence of intermediate code (i.e., virtual machine) instructions into a more efficient sequence.

    Note: A local optimizer may transform the program by removing unneeded loads and stores of data.

  8. A backend code generator translates the sequence of virtual machine instructions into a sequence of instructions for some real machine platform (i.e., for some particular hardware processor augmented by operating system calls and a runtime library).

  9. If the previous step generated symbolic assembly code, then an assembler is needed to translate the sequence of symbolic instructions into a relocatable binary module.

  10. If the previous steps of the pipeline generated a sequence of separate binary modules, then a linker might be needed to bind the separate modules with library modules to form a single executable (i.e., object code) module.

  11. A sink element outputs the resulting binary module into a file.

The pipeline can be reconfigured to support a number of different variations:

Of course, a pure active-filters system as described above for a compiler may not be very efficient or convenient.

Variants

So far we have focused on single-input single-output filters. A generalization of the pipes-and-filters pattern allows filters with multiple input and/or multiple output pipes to be connected in any directed graph structure.

In general, such dataflow systems are difficult to design so that they compute the desired result and terminate cleanly. However, if we restrict ourselves to directed acyclic graph structures, the problem is considerably simplified.

In the UNIX operating system shell, the tee filter provides a mechanism to split a stream into two streams, named pipes provide mechanisms for constructing network connections, and filters with multiple input files/streams provide mechanisms for joining two streams.

Consider the following UNIX shell commands. On a Solaris machine, this sequence sets up a pipe to build a sorted list of all words that occur more than once in a file:

        # create two named pipes
        mknod pipeA p
        mknod pipeB p
        # set up side chain computation (running in the background)
        cat pipeA >pipeB &
        # set up main pipeline computation
        cat filename | tr -cs "[:alpha:]" "[\n*256]" \
            | tr "[:upper:]" "[:lower:]" | sort | tee pipeA | uniq \
            | comm -13 - pipeB | uniq 

Consequences

Benefits

The pipes-and-filters architectural pattern has the following benefits [Buschmann]:

Liabilities

The pipes-and-filters architectural pattern has the following liabilities [Buschmann]:

References

The first version of these notes were written during the spring 1998 semester for the Special Topics in Software Architecture class (offered as ENGR 691).

These notes are based primarily on the "Pipes and Filters" section of Chapter 2 of the book:
Frank Buschmann, Regine Meunier, Hans Rohnert, Peter Sommerlad, and Michael Stal.
Pattern-Oriented Software Architecture: A System of Patterns,, Wiley, 1996.

It also draws on the "Pipes and Filters" section on Chapter 2 of the book:
Mary Shaw and David Garlan. Software Architecture: Perspectives on an Emerging Discipline,
Prentice-Hall, 1996.


UP to ENGR 691 Lecture Notes root document?


Copyright © 2004, H. Conrad Cunningham
Last modified: Thu Mar 18 2004