% -*- Mode:Text -*- 
\chapter{Introduction}\sectlabel{intro}

\Step\ is an indefinitely scalable multiprocessor architecture optimized for
the fine-grained simulations of physical systems and other spatially-extended
systems.  From a functional viewpoint, the \step\ architecture can be thought
of as a spatially-extended, uniform, fine-grained medium of a rather general
and abstract nature.  Specific behavior is obtained by specifying the
medium's connectivity and dynamical properties, and assigning its initial
state.  In this sense, \step\ embodies the metaphor of ``programmable
matter.''

\medskip

This manual describes the software environment provided with the \step\
machine. At the moment, only rather low-level software resources are
available; however, they are sufficient to exercise and evaluate all of the
architecture's features. Thus, the present sofware should be viewed as an
``evaluation kit'' rather than a mature, comprehensive package.

It is hoped that higher-level software tools, both general-purpose
and application-specific, will arise out of the collaboration
between the architecture designers and a variety of users.

\medskip

The present \emph{Software Reference} is one of three companion
volumes. The scope of the three manuals is as follows.
 \begin{itemize}
	\item \emph{Architecture Reference:}\quad Describes
the \step\ architecture, stressing structural and methodological aspects.
	\item \emph{Software Reference:}\quad Presents and documents the
current \step\ software, primarily addressing the needs of the applications
programmer.
	\item \emph{Hardware Reference:}\quad Documents the
four levels of the \step\ hardware hierarchy, namely, \emph{machine},
\emph{box}, \emph{module}, and \emph{\chip}, specifying in detail
the physical interface between adjacent levels.
 \end{itemize}

All three manuals are undergoing continual revision and expansion.  Their
PostScript sources, as well as other documentation, are available via
anonymous \id|ftp|. The latest version number of each manual is listed in the
\id|README| file in the same \id|ftp| directory. Please compare this number
with the version number of your copy, written right under the title on the
cover page, to know whether your documentation is up-to-date.


\section{System overview}\sectlabel{system-overview}

The activity of the assembly of modules that make up a \tdf{\step\ machine}
is governed and monitored by a general-purpose computer called the
\tdf{host}. In the current release, the host is a \sun\ \sparcstation\
running under \unix; all references to the `host' in this manual will imply
such a configuration.

All exchanges between the host and the \step\ machine are mediated by the
\step\ \tdf{\ctrler} (\fig{two-buses}), which communicates with the host
directly via the \tdf{\sbus}---the \sparcstation's high-performance external
bus---and drives the modules via the \tdf{\bus}---a tree-like bus having the
\ctrler\ at its root and the individual modules at its leaves.  Physically,
the \ctrler\ consists of a small board plugged into one of the \sbus\ slots.

In what follows, the \step\ \ctrler\ and the \step\ machine will simply
be called `the \ctrler' and `the machine'.

\medskip

Physically, a \step\ machine consists of three-dimensional array of
\tdf{modules}. The array can have an arbitrary extension along each of the
dimensions. Typically, each dimension is wrapped around, yielding for the
module-array the topology of a three-dimensional torus. A module contains all
the resources (state variables and updating machinery) needed to simulate a
certain portion (a \tdf{sector}) of the system under study. The modules all
work in parallel and in lockstep, directly exchanging information only with
contiguous modules.

The system being modeled is represented by a collection of discrete
\tdf{cells} arranged in a regular \tdf{lattice}.  This lattice may have more
or fewer than three dimensions, it may have an arbitrary crystallographic
structure (in particular, it need not be a cubic lattice), and may or may not
be wrapped around (independently of whether the module array is wrapped
around).

An equal amount of data storage capacity is allocated to every lattice cell,
for representing in a distributed way the system's state variables, its
parameters, and other information useful for processing and analyzing the
system's state. Depending on the nature of the model, the appropriate cell
capacity may range from a few bits to thousands of bits.

Cells within each sector are updated serially: on each updating pass through
the sector a single processor is time-shared between the cells in such a way
as to simulate the parallel operation of an equivalent number of identical
virtual processors. A complete updating \tdf{step}, in which all cell state
components are appropriately updated, may require several \tdf{passes}.
Since the results of each pass are, in ordinary circumstances, independent of
the order in which the cells are scanned, the scanning order itself can be
chosen so as to accomodate particular display or analysis needs.  Moreover,
the updating algorithm may change from step to step, so as to implement a
\emph{time-dependent} dynamics.

Data communication between cells during each updating pass is not restricted
to the immediate neighbors in the lattice. Indeed, one of the features that
distinguish the \step{} architecture from more ``obvious'' cellular automata
architectures is that essentially instantaneous communication can be achieved
between cells that are hundreds or thousands of lattice sites apart. Thus,
short- and long-range interactions are efficiently handled at the same time
by the updating machinery.

Pipelining of address arithmetic, read, update, and write operations,
together with flash updating based on lookup tables, yield a high rate of
serial updating: for 16-bit cells, 25 Megacells/sec per module in the current
implementation.

\medskip

The basic building block of a \step{} machine is an assembly of
eight modules called a \tdf{box}.  Besides mechanical support, shielding, and
power distribution, the box provides signal buffering, clock distribution,
\bus\ routing and fan-out, a frame buffer, and a video interface. All of
these functions are handled by a board called the {\bf box interface} (a
motherboard with eight slots for the modules can be treated, for electrical
purpose, as part of the box interface). Boxes are physically stacked in a
three-dimensional array, and exchange information only with adjacent boxes.

The smallest viable \step{} machine consists of a single box populated by a
single module. Conceptually, there is no upper limit to machine size; in
practice, a limit is set by economic factors sooner than by engineering
constraints.  Installations consisting of hundreds or thousands of modules
are feasible and, in terms of useful modeling applications, desirable.

\medskip

Within each module, ordinary dynamic {\sc ram} chips (\dram) are used to
store cell data. The sytem's dynamics is defined by lookup tables, which are
stored in ordinary static {\sc ram} chips (\sram). The ``glue'' that turns
these generic commodities into a powerful and flexible modeling environment
is represented by a custom \vlsi{} chip---called the \tdf{\chip}---of which
there are a set of sixteeen in each module.  This set works as a tightly
integrated team, and is indeed called a \chip\ \tdf{\team}.

\medskip

A faithful and efficient software simulator for the \step{} architecture is
available. The current version runs on a \sparcstation, but is easily
portable to other platforms. For many applications, a viable approach is to
develop an experiment on the software simulator---on a lattice of only tens
of thousands of sites---and then run the \emph{identical} experiment on a
lattice of millions or billions of sites on a \step{} machine.


\section{\Step's machine language}\sectlabel{machine-language}

The \step{} architecture gives one great flexibility in specifying the
features of the conceptual model that is the object of the simulation.
Subject to a single quantitative constraint, i.e., the number of
\step{} modules available, the user has great latitude in choosing the
dimensionality of the lattice, its crystallographic group, and its
extension in each of the dimensions; the size and the internal
structure of the cells, as well as the interconnectivity of the cells
within the lattice; the sequencing of updating steps and the algorithmic
details of each step; and, finally, the strategies for real-time data
analysis and display and the related input/output tactics.

It must be understood that this great variety of high-level features are
synthesized from a basic set of low-level, native features of the
\step{} architecture---a simple, well-structured, highly orthogonal
set of machine primitives.

The main goal of this manual is to provide a ``programmer's model'' of
\step{} appropriate to this synthesis taks. That is, our chief concern will
be to introduce, explain, and document those aspects of the hardware that are
meant to be visible to the programmer.  In this respect, we shall deal with
primitive concepts such as \emph{sites} and \emph{layers}, \emph{kicks} and {\em
glue}, \emph{scans}, \emph{lookup tables} and \emph{events}. Common
\step-programming constructs such as \emph{lattice}, \emph{cells}, and {\em
steps} will be mentioned, but they properly belong to the
application-language level rather than machine-language level.

Ultimately, \step{} programming is reduced to writing to (and
occasionally reading from) a set of hardware registers. Only about a
dozen of these registers are of direct concern to the user, when
programming at the machine-language level. Even if programming is done
through a compiler, the user should be generally aware of the existence
and function of these registers. The other registers---used for setup,
interrupt control, and diagnostics---are handled by system calls and
are of concern only to systems programmers.


\section{Organization of this manual}\sectlabel{manual}

[to be written]

\medskip


\section{Conventions}\sectlabel{sect.conventions}

Here we list a number of general conventions followed throughout this
manual.

\subsection{Emphasis and quoting}

Italics are used for \emph{emphasis}, i.e., to stress a particular word or
phrase. Boldface indicates an \tdf{inline definition}, i.e., a term that is
formally being assigned a specific technical meaning by the surrounding text.
Double quotes are used, as customary, for quoting short pieces of text
inline. Double quotes are also used to indicate that an expression is
deliberately used in some informal, allegorical, or humorous way, as when one
says that ``the computer got confused''. We follow the continental style of
putting \emph{outside} the quotes punctuation that belongs to the main text
rather than the quoted text (such as the previous period). Finally, single
quotes are used for literally exhibiting a string, as when we say that `one
word' is \emph{two} words.

\subsection{Number representation}

Numerals in typewriter font are in base sixteen; thus \ttt{40}=64 and {\tt
ff}=255. The advantages of using base sixteen in many hardware and software
technical discussions need not be belabored.

\subsection{Data and variable ordering}

In listings, tables, and figures, we had to fight a hard struggle to
reconcile conflicting conventions concerning the ordering of items and
the orientation of axes.

There are two basic sources of conflict. One conflict is between the
``most significant first'' approach, typified by the way we write a
number such as `1992' starting with the thousands and ending with the
units, and the ``first causes first'' approach, typified by the way
the electronic engineer draws the stages of digital counter, starting
with the units stage on the left and making the carry propagate
left-to-right. The other conflict is between the way a mathematician
would write an $i,j$ array, with $j$ increasing left-to-rigth and $i$
top-to-bottom, in agreement with western-style writing, and the
way a physicist would draw an $x,y$ or an $x,t$ diagram on the page, with $x$
pointing rightwards but $y$ or $t$ pointing \emph{upwards}.
Note that the ``mathematician's'' approach is also the one used in
scanning an ordinary {\sc crt} monitor---left-to-right and then
top-to-bottom.

After much soul-searching, we took the responsibility to enforce a
consistent, universal convention: in any enumeration, the natural
ordering of the items (i.e., increasing values of the enumeration
index) will be reflected by the typographical ordering (left-to-right,
and, for a second index, top-to-bottom).

\medskip

Thus, an array indexed by $x$ and $y$ will be displayed with $x$
increasing from left to right and $y$ from top to bottom,
as in the following diagram
 $$
 \begin{picture}(232,96)(-24,-16)
	% (0,0) is at the front bottom corner
	\thicklines
	\multiput(0,0)(0,8){5}{\line(6,1){192}} % front 5 horizontal lines
	\multiput(0,0)(0,8){5}{\line(-1,1){16}} % side 5 horizontal lines
	\multiput(0,0)(48,8){5}{\line(0,1){32}} % front 5 vertical lines
	\multiput(0,0)(-4,4){5}{\line(0,1){32}} % side 5 vertical lines
	\multiput(0,32)(-4,4){5}{\line(6,1){192}} % top 5 lengthwise lines
	\multiput(0,32)(48,8){5}{\line(-1,1){16}} % top 5 across lines
	\thinlines
	\put(192,64){\line(6,1){16}}\put(208,66.67){\vector(4,1){0}}
		% unfortunately there are no vectors of slope 6:1
		\put(204,60){\makebox(0,0){$x$}}
	\put(0,32){\vector(0,-1){48}}\put(8,-12){\makebox(0,0){$y$}}
	\put(0,32){\vector(-1,1){24}}\put(-20,44){\makebox(0,0){$z$}}
 \end{picture}
 $$

\noindent Here, the diagram's third axis, $z$, is represented as
pointing \emph{into} the page).

Note that, with these conventions, the ``handedness'' of the ($x,y,z$)
frame is the same as that that results from the more conventional
ordering of axes, illustrated by the following diagram

 $$
 \begin{picture}(232,80)(-24,0)
	% (0,0) is on the same corner as in the above diagram
	\thicklines
	\multiput(0,0)(0,8){5}{\line(6,1){192}} % front 5 horizontal lines
	\multiput(0,0)(0,8){5}{\line(-1,1){16}} % side 5 horizontal lines
	\multiput(0,0)(48,8){5}{\line(0,1){32}} % front 5 vertical lines
	\multiput(0,0)(-4,4){5}{\line(0,1){32}} % side 5 vertical lines
	\multiput(0,32)(-4,4){5}{\line(6,1){192}} % top 5 lengthwise lines
	\multiput(0,32)(48,8){5}{\line(-1,1){16}} % top 5 across lines
	\thinlines
	\put(192,32){\line(6,1){16}}\put(208,34.67){\vector(4,1){0}}
		% unfortunately there are no vectors of slope 6:1
		\put(204,28){\makebox(0,0){$x$}}
	\put(0,0){\vector(0,1){64}}\put(8,60){\makebox(0,0){$z$}}
	\put(0,0){\vector(-1,1){24}}\put(-20,12){\makebox(0,0){$y$}}
 \end{picture}
 $$

\medskip

Similarly, a 16-bit computer register will invariably be represented as
follows
 $$
 \def\qq{$\phantom{\scriptstyle15}$}
 \setlength{\tabcolsep}{0.2em}
 \begin{tabular}{|c|*{16}{c|}}\hline
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq&
	\qq&\qq&\qq&\qq&\qq&\qq&\qq&\qq \\\hline
	\multicolumn{1}{c}{$\scriptstyle0$}&
	\multicolumn{1}{c}{$\scriptstyle1$}&
	\multicolumn{1}{c}{$\scriptstyle2$}&
	\multicolumn{1}{c}{$\scriptstyle3$}&
	\multicolumn{1}{c}{$\scriptstyle4$}&
	\multicolumn{1}{c}{$\scriptstyle5$}&
	\multicolumn{1}{c}{$\scriptstyle6$}&
	\multicolumn{1}{c}{$\scriptstyle7$}&
	\multicolumn{1}{c}{$\scriptstyle8$}&
	\multicolumn{1}{c}{$\scriptstyle9$}&
	\multicolumn{1}{c}{$\scriptstyle10$}&
	\multicolumn{1}{c}{$\scriptstyle11$}&
	\multicolumn{1}{c}{$\scriptstyle12$}&
	\multicolumn{1}{c}{$\scriptstyle13$}&
	\multicolumn{1}{c}{$\scriptstyle14$}&
	\multicolumn{1}{c}{$\scriptstyle15$}
\end{tabular}\quad
 $$

\noindent and a text description of this register will list individual
bits or fields in same order, as in the following example:
 $$
 \begin{tabular}{rl}
	0--6	& \ascii\ character\\
	7	& Parity bit\\
	8--15	& Not used
 \end{tabular}
 $$

\noindent When the contents of the register is interpreted as a
binary-encoded integer by the computer's arithmetic-logic unit or its
address-arithmetic unit, bit 0 will represent the least significant
binary digit (units), and in general bit $n$ will represent the
coefficient of $2^n$.

\medskip

The above ordering convention will be broken in \emph{only one circumstance}. In
deference to universally ingrained practice, ordinary numerals in the
text will be written as usual with the most significant digit first.
Thus, the number represented by the following register contents
 $$
 \setlength{\tabcolsep}{0.348em}
 \begin{tabular}{|c|*{16}{c|}}\hline
	1&0&0&0&1&1&1&1&0&0&0&0&0&0&0&0\\\hline
	\multicolumn{1}{c}{$\scriptstyle0$}&
	\multicolumn{14}{c}{}&
	\multicolumn{1}{c}{$\scriptstyle15$}
 \end{tabular}
 $$
	\noindent will be written, in text form, as hexadecimal \ttt{00f1}
or decimal 237.

