EDIS |
Guide |
FAQ |
New |
Search |
Bibliography |
Index |
Feedback |
About |
![[EDIS Logo]](front.gif)
Encyclopedia of Delay-Insensitive Systems (EDIS)
Guide
The Encyclopedia of Delay-Insensitive Systems (EDIS)
presents each type of system in a single system document
comprising the following sections:
These sections are discussed in more detail below
(also see
EDIS Internal Naming and Structuring Conventions).
Preliminary Remarks
System types
A system type is a parameterized family of systems.
The terminal identifiers are always among the parameters,
though they are usually left implicit in the system name.
As an example consider the (type of all)
mxn-Decision-Waits.
It has as parameters:
two positive integers m and n,
m+n input terminals, and mn output terminals.
Substituting an appropriate value for each parameter yields a particular system,
also called an instance of the system type.
Partial substitution yields a subtype.
For example,
the mx2-Decision-Waits are a subtype of
the mxn-Desicion-Waits.
To obtain an instance of an mx2-Desicion-Wait,
one should also substitute a value for m
and indicate the terminal identifiers of the instance.
A statement such as `an mxn-Desicion-Wait is output deterministic'
applies to the whole type, that is, to all
mxn-Desicion-Wait instances.
System Names
Many systems are known by various names.
The names used in EDIS
were chosen with the following criteria in mind.
Names are (preferably)
- unique: `Sequencer' refers to one type of system only;
- descriptive:
`Join' rather than `C-Element';
- implementation-independent:
`Merge' rather than `XOR';
- short:
`Join' rather than `Rendezvous Element'
(though the latter is preferred historically);
- historically `correct': `Call' rather than `Non-Receptive Mixer';
- widely accepted: `Fork' rather than `Branch';
- consistent: `Call' and `Decision Call'
rather than `Call' and `Data Multiplexer'.
But usually one cannot have it all
(also see Miscellaneous).
In the document presenting system Foo,
all occurrences of the name Foo appear emphasized
(as illustrated in this sentence).
From other documents, references to Foo
are accompanied by a hyperlink to Foo's system document
(as illustrated in this sentence,
where the hyperlink points to the preceding sentence).
In a sense, the names used in EDIS are dummies,
since they could be systematically replaced without affecting
the global structure.
To be elaborated:
Names for generalizations;
incorporating parameters in names (as in mxn-Decision-Wait).
Specifications of systems are given in several ways for two reasons.
- For convenience:
You may be familiar with one language,
your neighbor (or tool) may know another.
Some specifications can even be copied and pasted directly into a tool,
without translation.
- To reinforce each other:
Ideally, each system document concerns a single type of system.
Nevertheless,
the various specifications that are given may differ slightly
in what they express due to limitions of the (in)formalism.
Currently,
the choice of formalisms is heavily influenced by this editor's preferences.
Also the order in which the formalisms appear is based on personal taste.
The connection diagram and state graph are shown first,
because they are visually oriented.
Informal
The informal specification describes
both the external structure and the observable behavior
of the system.
The terminology is chosen to be uniform and fairly precise,
without being pedantic.
It is intended to give a quick impression of the system.
For details you should turn to specifications expressed in
one of the formalisms below.
Input, output, terminal, signal, port, handshake, 2-phase, 4-phase...
The XDI Model appears first because it has some (though limited) way of
dealing with progress that is easily expressed in terms of state graphs
(we would like to keep the state graph near the beginning of the document).
Many systems have various pictorial representations.
Choosing a schematic diagram for a system raises similar problems
as choosing a name.
Here are some of the criteria we consider.
Diagrams are (preferably)
- unambiguous:
the roles of the input/output terminals are uniquely defined by
the diagram;
- easy to draw:
both by hand and by computer;
- implementation-independent:
we do not use the XOR symbol for a Merge.
- recognizable:
diagrams for frequently occurring systems
have readily recognizable shapes;
decorated rectangular boxes are used for all others;
Where possible, an alternate initial state is indicated by making use
of Initialized Wires rather than using
dots or blobs at the initialized component.
Example of schematic diagram and state graph:
The Zoom link brings up a picture
that is magnified by a factor two in both dimensions.
The Fig link brings up the xfig source of the picture.
The Specification in XDI model
link bring up the description
of the state graph in AND/IF format.
For specifications that also appear in the VERDECT library,
we have used the same name as in that library.
The given specifications can mostly be
offered directly to VERDECT (using copy and paste).
This may not be the case for some generalized specifications,
which must first be properly instantiated.
We have aimed at fully parameterized definitions.
That is, we write
define MERGE( a?, b?, c! ) =
pref *[ (a? | b?); c! ]
end
rather than
define MERGE = pref *[ (a? | b?); c! ] end
Currently,
VERDECT supports only parameterization over terminal identifiers.
A VERDECT specification is stored in a separate file. When shorter than
a certain limit it is also embedded in
the system page.
DI Algebra specifications are written in a format that is understood
by the DIGG
and Ludwig tools. DI Algebra, as it was originally proposed by Josephs and
Udding, has a drawback when it comes to specifying components with
separate environments. To overcome this, the notion of
channels or alternations is introduced. Both DIGG and
Ludwig accept a syntax that is extended with alternations.
A DI Algebra specification is stored in a separate file. When shorter than
a certain limit it is also embedded in
the system page.
We include both structural and behavioral properties.
Concerning structure there is the number of input/output terminals.
Behavioral properties include:
- number of states (transient, indifferent, demanding);
- automorphisms (symmetries) of the state graph,
with and without having the initial state as fixpoint;
- kinds of choice involved (nondeterminism);
- independent environments and ports;
- ...
The analysis report generated by the
XDI State Graph Tool is made available as xdi-report.html.
More detailed information on what is in the report and how to read
the report will appear here later.
DI Decompositions
Using Boolean Gates
Using Transistors
System type S is said to generalize system type T
when T can be obtained from S by partial instantiation,
that is, by substituting values for some of S's parameters.
Everything relevant that has no place elsewhere goes here. For instance,
alternative names and connection diagrams, including references to the
litarature. Historic footnotes. Controversies, difficulties, conjectures,
and open problems.
Keys to cited literature are collected here for quick reference.
Last modified at Tue Nov 10 12:49:26 1998
Encyclopedia of Delay-Insensitive Systems
Copyright © 1995-1998
Tom Verhoeff /
Tom.Verhoeff@acm.org
Disclaimer
