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

\Step1 (or simply \step{} in this manual) is an indefinitely scalable
multiprocessor architecture optimized for the fine-grained simulations
of physical 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 discusses those functional and structural aspects of
\step's hardware that are of interest to the programmer and the
sophisticated user.  It does not address issues of modeling
methodology. Issues of digital design or electronic engineering are
dealt with only insofar as they clarify the reasons for certain design
choices, and thus have tutorial or mnemonic value.


\section{System overview}\label{sect.system-overview}

Functionally, a \step{} machine consists of a three-dimensional array
of {\em modules}. The number of modules along each dimension is finite
(though it can be arbitrarily large), with each dimension wrapping
around on itself; thus, the module-array topology is that of a
three-dimensional torus. A module contains all the resources (state
variables and updating machinery) needed to simulate a certain portion
(a {\em 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
{\em unit cells} arranged in a regular {\em lattice}.  This lattice
may have more or fewer than three dimensions, it may have an arbitrary
crystallographic structure\footnote
	{Cf.\ Neil {\sc Ashcroft} and David {\sc Mermin}, {\sl Solid
State Physics}, Saunders College (1976).}
	(in particular, it need not be a cubic lattice), and may or
may not be 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
system, 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
{\em step}, in which all cell state components are appropriately
updated, may require several 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 {\em 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 positions 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.

The \step{} machine is controlled by a {\em host} computer through a
{\em controller} board that sits on the host's bus. The
controller communicates with the array of modules via a special
tree-shaped bus, called the {\em \bus}, which distributes commands and
data to the modules and collects status reports and data from them.

\medskip

Physically, the basic building block of a \step{} machine is an
assembly of eight modules called a {\em box}.  Besides mechanical
support, shielding, and power distribution, the box provides signal
buffering, clock distribution, \bus\ routing and fan-out, a video
interface, and a frame buffer. All of these functions are handled by a
board called the {\em box interface} (a motherboard with eight slots
for the modules can be treated, for electrical purpose, as an
part of the 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 {\em \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 {\em \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 it is a viable approach to develop an experiment on the
software simulator, on a lattice of tens of thousands of sites, and
then run the {\em identical} experiment on a lattice of millions or
billions of sites on a \step{} machine.


\section{\Step's 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 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 visible to the programmer.  The approach
will be ``bottom-up.'' We shall start with low-level concepts such as
{\em sites} and {\em layers}, {\em kicks} and {\em glue}, {\em lookup
tables} and {\em events}. Higher-level concepts such as {\em lattice},
{\em cells}, and {\em steps} will not be mentioned again for a while,
but will emerge in due course.

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}

Part I presents \step's overall theory of operation. The last chapter
of Part I is a detailed description of all the \chip{} registers:
these registers constitute the functional link between software and
hardware.

The \step{} design naturally falls into four hierarchical levels, namely
{\em machine}, {\em box}, {\em module}, and {\em \chip}.  Part II
describes each level of this hierarchy in terms of its interface to
the rest of the system, and sketches how each level is built up from
the lower one. For sake of reference, a systematic listing of all
input and output signals (``pinout''), accompanied by a brief
description of each signal, is given for each level, using a
consistent system-wide nomenclature.


\section{Conventions}

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

\subsection{Number representation}

Numerals in typewriter font are in base sixteen;
thus {\tt 40}=64 and {\tt FF}=255.

\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 {\em 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 {\em 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 {\em 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 {\tt 00F1}
or decimal 237.

\subsection{Signal polarity}

Signal names, typeset in sans-serif face, are chosen so as to have
appropriate mnemonic value. For instance, the \bus{} {\sym Reset}
signal has a value of 1 (logical {\sc true}) when the \step{} machine
is being reset, and 0 (logical {\sc false} otherwise. 

Physically, on the the \bus\ wires, this signal travels in
complemented form, indicated by {\sym Reset*}.  However, we shall
usually mention the signal in its native form, saying, for instance,
that ``in certain conditions {\sym Reset} is asserted;'' this implies
that, in those conditions, the physical signal {\sym Reset*} is
negated.

The complemented form, {\sym Reset*}, would be used only when
tabulating the pinout of a chip or connector, to make it clear that
the physical signal present on that pin is the complement of {\sym
Reset}.

\endinput

\bib{ashcroft} {\sc Ashcroft}, Neil, and David {\sc Mermin}, {\sl Solid
State Physics}, Saunders College (1976).
