Task System and Item Architecture (TSIA)
- Practical Graph Reduction

For a computer application, a transparent execution is one not visible to the application.
Instead, the execution is managed by a system external to the application.
Graph reduction (also known as dataflow) long has been a model for transparent application
execution. Given graph reduction, a system for transparent parallelism, reliability or other
execution can be implemented. Unfortunately, graph reduction itself has not had a practical
implementation.

The Task System and Item Architecture (TSIA) is a recent practical model of graph reduction.
Close ancestors are ALICE and the early versions of Cilk.

I came to TSIA via a large production system called Funnel, whose implementation I led.
Since 1992, Funnel has served about 1000 CPU-years to the ZEUS experient at DESY
and the L3 experiment at CERN. Funnel is one example of many systems which transparently
serve a bag-of-tasks application. A popular system is SETI@home. Other real-world systems
transparently provide a bag-of-tasks application with a transparent reliable, distributed,
heterogeneous, adaptive, dynamic, real-time, parallel, secure or other execution.
Such a system for a bag-of-task application is a practical implementation of graph reduction,
albeit for a very simple application.
By combining previous work on graph reduction with the above real-world experience,
I arrived at TSIA - practical graph reduction for a large variety of applications.

I have given invited presentations on TSIA at IBM, Caltech and elsewhere.

About me: Curriculum Vitae, Publications, References.
I'm also the author of cfortran.h, a popular interface between C or C++ and Fortran.

Titles and abstracts of papers on TSIA follow in reverse chronological order.
Additional papers should be available here soon.


Graph Reduction for Partial Evaluation

Partial evaluation is an automatic optimization of the execution of an application. For some
of the components of partial evaluation, graph reduction long has promised practical
implementations. The promises have not been fulfilled, since graph reduction itself lacked
a practical implementation.
Practical graph reduction recently has been achieved. It may satisfy some of the promises
of graph reduction for partial evaluation. This presentation demonstrates practical
implementations of the following components of partial evaluation: partial execution,
inlining routines, algebraic simplification, as well as support for input/output and other
global effects.

The paper is submitted for publication.
A draft is available here as graph.ps.gz (136,824 bytes) or graph.pdf.gz (159,509 bytes).
The C code of all the demonstrations in the paper is here pex_examples.tar.gz (9,060 bytes).
As is usual, the following will unpack the code into the directory pex_examples/.
The program zcat is the GNU version or compatible.
unix> zcat pex_examples.tar.gz | tar xf -


Task Frames

Forty years ago Dijkstra introduced the current conventional execution of routines.
It places activation frames onto a stack. Each frame is the internal state of an executing
routine. The resulting application execution is not easily helped by an external system.
This presentation proposes an alternative execution of routines. It places task frames
onto the stack. A task frame is the call of a routine to be executed. The feasibility
of the alternative execution is demonstrated by a crude implementation. As described
elsewhere, an application which executes in terms of tasks can be provided by an external
system with a transparent reliable, distributed, heterogeneous, adaptive, dynamic,
real-time, parallel, secure or other execution. By extending the crude implementation,
this presentation outlines a simple transparent parallel execution.

The paper is submitted for publication.
A draft is available here as stack.ps.gz (98,393 bytes) or stack.pdf.gz (94,863 bytes).


TSIA: A Dataflow Model

The Task System and Item Architecture (TSIA) is a model for transparent application execution.
In many real-world projects, a TSIA provides a simple application with a transparent reliable,
distributed, heterogeneous, adaptive, dynamic, real-time, parallel, secure or other execution.
TSIA is suitable for many applications, not just for the simple applications served to date.
This presentation shows that TSIA is a dataflow model - a long-standing model for transparent
parallel execution. The advances to the dataflow model include a simple semantics,
as well as support for input/output, for modifiable items and for other such effects.

The paper is submitted for publication.
A draft is available here as df.ps.gz (57,966 bytes) or df.pdf.gz (46,128 bytes).


Partial Execution - An Easy Partial Evaluation

Partial evaluation, also known as automatic specialization, is a particular collection of techniques
for improving the performance of an application. With clear benefits, but unclear implementation
up until now, partial evaluation is little used in current computing practice. This soon will change.
Presented here is partial execution, an alternative to symbolic evaluation - the technique driving
previous implementations of partial evaluation. In contrast to symbolic evaluation, partial execution
is simply a part of the usual application execution. Partial execution thus avoids many of the problems
introduced by symbolic evaluation. Partial execution is one of many execution features provided
by the Task System and Item Architecture (TSIA) - a project in its early stages.

The paper is largely superceded by the above paper "Graph Reduction for Partial Evaluation".
A draft is available here as pe.ps.gz (69,668 bytes) or pe.pdf.gz (69,456 bytes).


Dividing the Application Definition from the Execution

Current computing practice requires great effort to produce an application with a reliable,
distributed, heterogeneous, adaptive, dynamic, real-time, parallel, secure or other execution.
An exception is a bag-of-tasks application. Examples of such a type of application include
the simulation of independent trials, the processing of independent media frames and the evaluation
of independent candidate solutions. In many real-world projects, an external system provides such
an application with a transparent execution. This division of the application definition from the
application execution greatly reduces the effort to produce the application.
This presentation has several aims. Most specifically, this presentation helps produce a bag-of-tasks
application with less effort. Most generally, this presentation points out that many other applications
can be treated like a bag-of-tasks application and thus can be produced with less effort.

The above is from the draft. The final paper is in
IEEE Computing in Science & Engineering, Vol. 2, No. 3, May/June 2000, pp. 70-75.
A draft is available here as cse.ps.gz (43,137 bytes) or cse.pdf.gz (45,135 bytes).


An Alternative Implementation of Routines

In the current conventional implementation of a routine, a parent receives the outcome of its child.
A parent may be coded such that it does not use the outcome of its children, thus allowing delegation -
an alternative implementation of the routine. As part of its execution, such a parent can replace itself by
its children. The parent thus delegates the responsibility for its outcome to its children. In turn, a child
may delegate the responsibility to its descendants. Due to such delegation, a routine previously
dependent on the outcome of the parent thus becomes dependent on the parent's children or on other
descendants.
Delegation is a variation on continuation - a part of the Scheme programming language and of other
functional computing. Delegation allows for a simple implementation of proper tail calls, non-strict
evaluation, conditional items, streams and of other features of functional computing.

Presented at Implementation of Functional Languages 11th International Workshop (IFL'99).
The paper is available here as ifl.ps.gz (54,675 bytes) or ifl.pdf.gz (41,929 bytes).


After Compilers and Operating Systems :
The Third Advance in Application Support

After compilers and operating systems, TSIAs are the third advance in application support.
A compiler supports a high level application definition in a programming language.
An operating system supports a high level interface to the resources used by an application execution.
A Task System and Item Architecture (TSIA) provides an application with a transparent reliable,
distributed, heterogeneous, adaptive, dynamic, real-time, interactive, parallel, secure or other execution.
In addition to supporting the application execution, a TSIA also supports the application definition.
This run-time support for the definition is complementary to the compile-time support of a compiler.
For example, this allows a language similar to Fortran or C to deliver features promised by functional
computing.
While many TSIAs exist, they previously have not been recognized as such and have served only a
particular type of application. Existing TSIAs and other projects demonstrate that TSIAs are feasible for
most applications.
As the next paradigm for application support, the TSIA simplifies and unifies existing computing
practice and research. By solving many outstanding problems, the TSIA opens many, many new
opportunities for computing.

This is an early rough draft paper introducing TSIA.
It is available here as paper.ps.gz (64,358 bytes) or paper.pdf.gz (66,835 bytes).


DRAFT : Task System and Item Architecture (TSIA)

During its execution, a task is independent of all other tasks. For an application which executes in terms
of tasks, the application definition can be free of the details of the execution. Many projects have
demonstrated that a task system (TS) can provide such an application with a parallel, distributed,
heterogeneous, adaptive, dynamic, real-time, interactive, reliable, secure or other execution. A task
consists of items and thus the application is defined in terms of items. An item architecture (IA) can
support arrays, routines and other structures of items, thus allowing for a structured application
definition. Taking properties from many projects, the support can extend through to currying,
application defined types, conditional items, streams and other definition elements. A task system
and item architecture (TSIA) thus promises unprecedented levels of support for application execution
and definition.

This is a draft book introducing TSIA.
It is available here as tsia.ps.gz (578,827 bytes) or tsia.pdf.gz (700,786 bytes).

The draft also has been released as preprint DESY 99-066 by the Deutsches Elektronen-Synchrotron
(DESY), the national particle physics lab. in Hamburg, Germany.
It also is available at the Los Alamos preprint server http://xxx.lanl.gov/abs/cs.PL/9905002.
The draft has vii+244 pages, including 126 illustrations and program code examples.


Funnel: Towards Comfortable Event Processing

Presented in the plenary session `F. Systems and Facilities',
Computing in High Energy Physics (CHEP'95), Rio de Janeiro, Brazil, Sept. 1995,
editors R. Shellard and T.Nguyen, World Scientific, pp. 59-63.
The paper is available here as pfunnel.ps.gz (36,836 bytes) or pfunnel.pdf.gz (52,569 bytes).


Burkhard D. Steinmacher-Burow, Postfach 1163, 73241 Wernau, Germany.
burow@desy.de
http://www-zeus.desy.de/~funnel/TSIA/index.htm
[Mirrored at http:://www.tsia.org since I'm curious about free web-hosting in exchange for advertising.]