Efficient, Scalable Architectures for Lattice-Gas Computations (Thesis)

Abstract:

The subject of this dissertation is finding an architecture for
two-dimensional cellular automata computations that is verifiably
correct, and the fastest and cheapest possible. The motivating
problems for this work are large-scale scientific computations; the
hardware context is that of application-specific processors attached to
general-purpose systems. While the conclusions are derived for a
specific class of two-dimensional cellular automata, the so-called
"lattice gasses," they are applicable to a wide range of similar
problems. By developing and applying solutions to discrete
isoperimetric problems to a pebbling game, upper bounds on throughput
for machines computing problems with data dependency graphs based on
the undirected graphs for the Hardy-de Pazzis-Pomeau (HPP) and
Frisch-Hasslacher-Pomeau (FHP) lattice-gasses are shown. A particular
architecture, the "Wide Serial Architecture" (WSA), is shown to be
within a factor of approximately 6 of the bound for the HPP-like
computations, and within a factor of about 4.5 of the bound for the
FHP-like computations. Besides the insight they provide into the
optimal computational strategy, the methods of solution of the
isoperimetric problems, such as the use of the Wulff Crystal, are of
interest in their own right. An analytic study of the least-cost
configuration for a multiple-pipeline WSA machine is undertaken. The
use of overlap-save method is described, and the efficiency of the WSA
architecture using this method is derived. A numerical search is used
to find the least cost machine configuration as the problem size is
scaled. A slightly super-linear speedup is shown over a moderate range
of problem sizes, and the least-cost machine parameters are described.
Finally, a data-embedded, specification-based testing technique for FHP
lattice gasses is introduced. The tests consist of limit cycles in the
cellular automaton, and their error detection coverage is shown
empirically to be good. Their use in software, hardware, and system
debugging is described, as well as their use as runtime simulation
error detectors. Machine design tradeoffs relating to testability are
discussed.