misc edits

[pec.git] / physical-evolutionary-computation.tex

\documentclass{sig-alternate}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{listings}
\input{tikz-setup.tex}

% in 2010 there was 8-page maximum
\begin{document}
\conferenceinfo{GECCO'11,} {July 12--16, 2011, Dublin, Ireland.}
\CopyrightYear{2011}
\crdata{978-1-4503-0072-8/10/07}
\clubpenalty=10000
\widowpenalty = 10000

\title{Physical Evolutionary Computation}

\numberofauthors{2}
\author{
% \alignauthor
% Eric Schulte\\
%   \affaddr{University of New Mexico}\\
%   \email{eschulte@cs.unm.edu}
% \alignauthor
% David H. Ackley\\
%   \affaddr{University of New Mexico}\\
%   \email{ackley@cs.unm.edu}
}

\maketitle
\newcommand{\Comment}[1]{}
\begin{abstract}
  \noindent
  Although evolutionary computation (EC) is an ``embarrassingly
  parallel'' process, it is often deployed on essentially serial
  machines, and even its parallel implementations typically retain the
  globally synchronized and regimented style typical of serial
  computation.  We explore a radical `physical evolutionary
  computation' (PEC) hardware/software framework that is based on real
  time and real space rather than an abstract sequence of events---for
  example, the mutation rate is specified in Hertz.  PEC supports
  massive and reconfigurable parallelism, using a prototype hardware
  `tile' that begins evolutionary computation within three seconds of
  applying power.  Although each tile is a simple computer by today's
  standards, tiles can be plugged together into a wide variety of size
  and shape computing grids---even while the computation is running.

  We present our initial explorations with this framework, defining
  mechanisms for representing and sharing problems, and mapping
  between computational spaces and physical ones.  We discuss
  advantages of PEC---such as extremely robust operation---as well as
  its challenges, and touch on some unexpected, and potentially
  useful, level-crossing interactions that can be explored when the
  embedding of the computational within the physical is made real.
%  levels, such as observing that an \emph{increased} hardware failure
%  rate can benefically affect the explore/exploit balance of an
%  evolutionary computation.

\Comment{
  In contrast to conventional, highly abstract, computational models,
  the \emph{physical computation} framework embraces the concrete
  properties of space and time.  Computational space contains multiple
  processor/memory elements arranged in some geometry, with sizes,
  relative positions, and local communications; and computational
  times---frequencies and intervals, delays and deadlines---are
  measured in hertz and seconds or milliseconds, rather than steps or
  generations or simulated days.

  Within such a framework, \emph{evolutionary computation} (EC) is one
  natural computational strategy.  Though often implemented on a
  serial computer, ECs such as genetic programming (GP) are fundamentally
  `embarrassingly parallel' computational strategies, and thus
  apparently well-suited to such distributed and parallel hardware.

  In this paper, we introduce and demonstrate a combined hardware and
  software implementation of \emph{physical evolutionary computation}
  (PEC), based on small pluggable computers programmed with firmware
  that performs genetic programming in the physical computation style,
  and exchanges both problem specifications and evolved individual
  programs with whatever neighbors may exist.  Our `evolution
  processing tiles' typically begin evaluating individuals less than
  two seconds after power on;
  %assuming the 'one shot red boot' technique is in use..
  in effect, they cannot \emph{not} evolve.

  We explore the abilities and limitations of systems of such
  `non-stop evolution' components, which possess rather different
  properties than serial GP.  Some traditionally difficult or ignored
  problems become easy, such as: Robust operation in the face of
  software and hardware failures, dynamic utilization of changing
  hardware resources, and the aligning spatial dimensions of the
  physical hardware with dimensions of the problem space.  On the
  other hand, some operations that are traditionally trivial or free
  become more difficult or expensive, such as: Halting computations,
  repeating a computation exactly, coordinating global goals, and
  `forgetting' prior solutions.
}
\end{abstract}

% A category with the (minimum) three required fields
\category{1.2.11}{Computing Methodologies}{Distributed Artificial Intelligence}
\category{C.3}{Computer Systems Organization}{Special-Purpose and Application-Based Systems}
\category{B.8}{Hardware}{Performance and Reliability}

\terms{Reliability}
\keywords{Evolutionary Computation, Robustness, Physical Computation}

\section{Scalable abstractions}
\label{sec:introduction}

\Comment{
\subsection{Scaling abstractions}
\label{sec:abstraction}

The ability to abstract is critical to our cognitive abilities, with
incredibly deep and productive abstractions such as mathematics and
the structures of science and engineering ultimately powering much of
our success as a species.  That said, it is important to remember that
many different abstractions can be drawn from any given situation or
events, each with its own biases and limitations as well as emphases
and strengths.}

\noindent 
Abstract computational models simplify the natural world to help us
understand it, and also serve as outlines for the engineering
of---preferably ever-more-powerful---computing machines.  Researchers
have explored computing models inspired by everything from mathematics
and philosophy to the natural and social sciences, but abstractions
based \emph{algorithmic software on reliable serial hardware} have
dominated computer science and engineering, accruing volumes of
widely-understood tools and techniques.  The basic \emph{von Neumann
  machine} `CPU+memory' model abstracts physics into deterministic
boolean algebra, and abstracts time into a total ordering of discrete
steps from a beginning to an end.  Even more aggressively, it
eliminates the distances and dimensions of physical space entirely,
declaring all memory equally cheap to access by the CPU.  Where that
assumption is invalid, the von Neumann machine is simply a poor
descriptive model.  On the other hand, when used for machine design,
that assumption has held simply because engineering was commanded to
make it so, which it has done spectacularly for decades, scaling clock
speed and memory capacity over many orders of magnitude.

\Comment{
 that isn't and can't be true in general plays
out in two aspects: Descriptively where it isn't true -- as far as
trying to apply it to some observations of actual reality -- this
model just doesn't apply and offically has specific to say.  And on
the other hand prescriptively, where the abstraction is being used as
an architecture of or scaffolding for the \emph{design of a machine};
in that case the engineer's job is to \emph{make} what the abstraction
holds be true, and it was VN that introduced the mathematical study of
reliable computing from unreliable organisms, showing how mass
quantities of extremely cheap and noisy amplifiers could be engineered
to represent and manipulate digital information extremely reliably.


he structure of thought and
computation, as well as 
}

Of course, many different abstractions can be imposed on any situation,
and the continued dominance of serial algorithmic computing is 
now uncertain as its scalability dwindles
%ERIC: NEED MORE THAN THAT?  TRYING TO SAVE A PARAGRAPH LINE..
% -- this looks good to me
and it yields ground to alternate models such as cache-coherent
multicores \cite{free-lunch}, which offer a degree of parallelism
while preserving many of the computational and spatiotemporal
abstractions of the classic framework.

This paper explores the \emph{physical evolutionary computation} (PEC)
framework (Figure \ref{fig:pec}), which abstracts reality quite
differently than the classical approach.  It retains explicit units of
space and time, and it marginalizes brittle, finite, serial algorithms in
favor of robust, open-ended, parallel computational processes, capable
of filling whatever volume of computational space-time one's hardware,
energy, and patience can supply.

\Comment{
is in some significant ways ``closer to
reality''---for example, it is a spatial
computing~\cite{DAGSTUHLSPATIAL} model explicitly aware of spatial and
temporal distances and relationships.  

---at the level of  For example, although PEC abstracts the
details of local computations in a largely von Neumann style, but
programmed as an open-ended, event-based computation

, developing
an abstraction that emphasizes robust operation and indefinite
scalability~\cite{HOTOS11}---

 a framework
we call \emph{physical evolutionary computing}

.  We 

  spatiotemporal 
emphasizes \emph{robust indefinite scalability}\cite{HOTOS11}, and
retains notions of real time and spatial dimensions and
distances to do it.

Indefinite scalability, (2)
Robust design, and (3) P naturally suited to evolutionary computation,
and that has the potential to scale vastly beyond any serial machine.

, and 
introduce a new computational abstraction organizational paradigm for physical
evolutionary computation which embeds every computational event in
real space time.  
}

By anchoring evolutionary computation firmly in space and time---with
many `evolution tiles' spatially interconnected in some geometry, and
genetic operations occurring not in a global algorithmic lockstep, but
independently triggered by hardware timers and arriving local
stimuli---we obtain a naturally distributed system that is extremely
scalable, without any \emph{a priori} edges or `privileged points',
and so inherently robust that, basically, the system can't \emph{not}
evolve.

\begin{figure*}[htb!]
  \centering
  \includegraphics[width=\textwidth]{figures/overview.pdf}
  \caption{Physical Evolutionary Computation.  Prototype overview:
    Hardware and software in physical space, mapped to sample fitness
    function in problem space.  See text for details.}
  \label{fig:pec}
\end{figure*}

This paper presents our initial experiences with a prototype PEC
system.  Section \ref{sec:pec} motivates and presents the design we
have developed.  Six sample tasks illustrate the system behavior in
Section \ref{sec:pec-demos}.  Section \ref{sec:data} provides results
and analysis of the performance of the system, and a few anecdotes of
some ways in which this system surprised our assumptions drawn from
traditional computation.  Finally we discuss the application of our
findings to alternate hardware systems and problem domains, and review
the implications of this model of computation in section
\ref{sec:discussion}.

\section{Physical Evolutionary\\ Computation}
\label{sec:pec}

\subsection{Parallel Evolutionary Computation}
\label{sec:ec}

\noindent
\emph{Evolutionary Computation} (EC) is a domain independent
stochastic search technique modeled after the biological process of
evolution.  EC is \emph{scalable} in the population size and number of
generations, and famously \emph{embarrassingly parallel}
\cite{parallel-gp} in that multiple individuals can generally be
evaluated simultaneously on multiple processors, and many researchers
have explored such approaches~\cite[e.g.]{subpop,beowulf,stender}.

However, perhaps due to their derivations from serial designs, even
parallel EC's are typically organized so that their aggregate
computation is fully equivalent to a single serial execution path.
Such rigid global control can provide the cardinal benefit of
repeatability, but it is of course uncharacteristic of real
biological systems (and non-trivial real-world systems generally), and
it limits the ultimate system scalability by requiring global
synchronization points, typically at least once per generation.

In the PEC framework, we prioritize the goal of \emph{robust
  indefinite scalability} over the goal of maintaining a
serial-equivalent computational path, so we adopt a design goal of
eliminating as far as possible all `privileged points' in space (e.g.,
root nodes, dependence on edges or corners) and time (e.g., sequential
phases, synchronization points, global clocks).  Here we describe our
prototype PEC system including hardware evolutionary tiles and the PEC
process they support. 

\subsection{Evolutionary Tiles}
\label{sec:ixm}

\noindent
The hardware layer of a PEC system is composed of a fungible
collection of interconnected \emph{evolutionary tiles}, whose quantity
and configuration may change during the course of a computation.  A
group of connected tiles is shown in Figure \ref{fig:ixm}.

\begin{figure}[h]
  \centering
  \includegraphics[width=0.4\textwidth]{figures/group-crop.png}
  \caption{37 Evolutionary Tiles.  \normalfont With external
    power connections \emph{left} and an external data connection \emph{top}.}
  \label{fig:ixm}
\end{figure}

As part of a research effort in Robust Physical Computation, hardware
and support software has been developed for a prototype tilable
computer that has been brought to market under the name
\emph{Illuminato X Machina} (IXM) \cite{LIQUIDWARE}.  The IXM is a
self-contained traditional Von Neumann machine with a single
processor, a modicum of RAM and persistent memory, and additional
hardware such as timers that can be used to trigger computation at
specific intervals (details in Figure \ref{fig:pec}).  Each of the
tile's four edges holds a connector capable of sharing both
power and/or information with either a traditional computer or power
supply, or more frequently, with a neighboring tile.  The support
software defines several basic abstractions including a simple but
powerful packet format, as well as managing the hardware to perform
interrupt-based asynchronous communications via all four tile edges
simultaneously.  Although the PEC process is certainly not limited to
specifically this hardware, all the demonstrations shown in this paper
were run on groups of IXM tiles.

\Comment{ % save for later
\subsection{Computational Space-Time}
\label{sec:space-time}

\noindent
A connected \emph{group} of tiles defines a discrete 2-dimensional
space.  Each tile in this space performs calculations initiated by
hardware timers, resulting in a discrete 3 dimensional grid of
computational space-time.

Every event in this computational space will fill a 1 dimensional
rectangle with one of two possible orientations.  Either the event is
extended in time on a single tile, or the event extends between two
adjacent tiles in a single instant.  These two orientations
correspond to on-tile calculation and to intertile communication
events respectively.
% The above relies on the two simplifying
% assumptions that clocks are synchronized between tiles, and that
% communication between tiles is instantaneous.

\Comment{ % some of this can be used below, but not here
\begin{description}
\item[Spatial Localization] Each tile in the grid houses a subset of
  the total population.  In all variations discussed herein the
  population size is kept constant and each tile holds an equal
  fraction of the total population however neither of these need
  necessarily be the case.  On-tile sub-populations are altered
  through local evolutionary events, and through communication with
  immediately neighboring tiles -- \emph{Action at a distance} is not
  allowed.  Each tile is aware of its relative position in the grid,
  this information may influence the portion of the problem domain
  tackled by the tile.  In this way it is possible for the physical
  dimensions of the 2 dimensional tile arrangement to be leveraged in
  structuring EC.
\item[Temporal Localization] Temporal localization of computation is
  achieved through the use of hardware timers.  Each IXM tile is
  equipped with sixteen hardware timers.  Each timer can be associated
  with some arbitrary computation, and then scheduled to trigger some
  number of ms in the future.  The time of execution as determined by
  the local on-tile timer is passed to the associated computation as
  a parameter.  After execution has completed, control is passed back
  to the CPU.  It is customary to implement reoccurring actions at set
  frequencies by having the final act of the computation associated
  with some timer to be the re-scheduling of the timer.
\end{description}
}

Unlike in traditional algorithmic models of computation, no continuous
series of event may span the entire group of tiles or the entire
time-span of computation.  Rather global computation emerges
% scared `emerge' may carry too much baggage, but is seems appropriate
from the \emph{communication} between many individually initiated
local \emph{calculations}, the nature and relative frequencies of
which may be controlled while the exact ordering of which is not
specifiable.

\subsubsection{Calculation}

\noindent
All computational operations take place at specific points in
space-time.  The tile on which an operation occurs determines the
spatial coordinates in the 2 dimensional grid of the \emph{group}.
The temporal location of a calculation is determined by the
cause of the calculation.  There are four possible causes of a
calculation.

On \emph{powerup} a tile will run a series of one-time actions.
These may be used to initiate hardware times, configure reflexes, and
situate the tile with its neighbors.  Once this routine completes the
tile drops into an infinite \emph{maintenance loop}, similar to the
loop of an operating system.  This loop is used exclusively for
performing regular hardware maintenance tasks and is not used by the
PEC process.

The majority of calculations occur as \emph{timed operations} or as
\emph{reflexive} responses to external stimuli.  Using hardware timers,
calculations may be initiated at precise frequencies specified in
milliseconds.  These calculations are short lived and will generally
result in a communication event.  \emph{Reflexive} calculations
respond to these events and, like timed calculations, reflexive
calculations effect group wide computation through the initiation of
further communication events.

\subsubsection{Communication}

\noindent
All communication of information in a group is either spatial or
temporal.  \emph{Spatial} communication between tiles takes the form
of lines of text up to 250 bytes long.  The receiving tile dispatches
on the first byte of such a message, initiating the associated reflex.
The message string is passed to the reflex as an argument.
\emph{Temporal} communications are transferred through on-tile memory.
Assuming discrete units of time, and instantaneous message passing,
the entire state of a group between any two moments is exactly the
state of the tiles comprising the group.
}

\subsection{The PEC Processing Mechanism}
\label{sec:ea}

\noindent
We present the PEC process in three sections: the processing local to
a single hardware tiles and its immediate neighbors, the mechanisms
for handling `global' events such as changing the fitness function,
and finally housekeeping details.  In many cases it will be obvious
that other evolutionary computation mechanisms could be substituted
for the ones we used without significantly distorting the overall
processing structure, but here we discuss only the specific mechanisms
we have implemented and tested.

\subsubsection{Local Genetic Operators}
\label{sec:subpopulation}

\noindent
Each tile in a PEC system houses a single subpopulation of candidate
solutions, so an overall group of tiles evolves using the
`island' approach to genetic algorithm
parallelism~\cite{demes}.  On \emph{power up} the tile
subpopulation is initialized with 64 randomly generated individuals,
and this subpopulation size is then held constant by all further
evolutionary actions.

The population serves as both a source and repository for candidate
solutions which are accessed and stored through \emph{tournaments} and
\emph{incorporation} respectively.

\emph{Tournaments} perform selection in the PEC system.  In a
tournament three individuals are chosen from the population at
random, these individuals are then evaluated, their resulting finesses
are compared, and the individual with the best fitness is
selected.  Individuals are only evaluated at the time of selection and
their fitness is not stored, so it is possible that a
single individual may be evaluated multiple times or not at all.  In
the presence of a changing problem space the individual's fitness is
expected to be valid only at the time of selection.
% In the above, could mention that multi-objective EC could be
% implemented simply through selecting with different fitness
% functions at different frequencies, which seems both practical and
% natural -- maybe this is better for the discussion...

When new individuals are generated through tournaments and local
reproduction, or are received from neighboring tiles, they are
\emph{incorporated} into the local population.  To maintain a constant
population size during such an incorporation, a randomly chosen
existing individual is evicted from the population.  Incorporation is
the only means by which individuals are added to or removed from the
population.
% Because individuals are randomly selected for removal from the
% population it is common for the best individual to be removed from the
% population.

Subpopulations evolve locally through \emph{mutation} \emph{crossover}
and \emph{sharing}, each of which is triggered at a fixed frequency by
the hardware clock---although processing pile-ups can cause small
delays.

The \emph{mutation} operation, occurring twenty times a second ($f_m = 20Hz$)
in our experiments, begins by tournament-selecting an individual to
copy from the population.  Random points along the individual's
genotype are chosen---one point per 16 symbols of genotype length, but
no less than one point---and then each point is either: Replaced with
a randomly chosen value from the underlying symbol set, with a 50\%
chance; deleted from the individual, with a 25\% chance; or has a
randomly chosen symbol inserted into the individual immediately
preceding the point, with a 25\% chance.  The resulting individual is
then incorporated into the population.

In a \emph{crossover} operation, which occurs ten times a second ($f_m =
10Hz$), two individuals are selected via independent tournaments and
copied from the population.  A random point is chosen independently
along each genotype, and single point crossover is used to create a
new individual, which is then incorporated into the population.

Finally, individuals are also \emph{shared} between tiles, at a rate
of once every ten seconds ($f_s = 0.1Hz$).  When sharing, an
individual is tournament-selected and copied into messages sent to
every adjacent tile.  Upon arrival at a neighboring tile, a sharing
message triggers a reflex action that incorporates the shared
individual into the recipient's subpopulation.  Sharing propagates
individual solutions between tiles (see section~\ref{sec:spread},
below, for more); note that each successful act of sharing also
amounts to up to a fourfold reproduction within the aggregate global
population---and that individuals and subpopulations housed in more
densely-connected tiles have an advantage in that regard.

\subsubsection{Global Coordination}
\label{sec:global-coordination}

% These include the relative
% coordinates assigned to each tile in the group, the EC parameters in
% use by the group, as well as the problem space and the scheme by which
% it is mapped into the computational space.

\noindent
Some aspects of a PEC computation, inevitably, need to be coordinated
globally across an entire group of tiles, and various \emph{control
  messages} are defined for this purpose, containing information such as
the problem specification (Section \ref{sec:problem-sets}), the scheme
for mapping between problem space and computational space (Section
\ref{sec:schemes}), and the frequencies of the PEC genetic operators
discussed above.  Parameter-setting messages may be global in
intent---in which case they are propagated throughout the group---or
may be sent from one tile to an immediate neighbor in response to a
direct request, which occurs when a tile has just rebooted or been
added to the group.

For purposes of problem space mapping and data collection, each tile
in the group also maintains a 2D coordinate specifying its position in
the two dimensional spatial configuration of the group, with the
origin specified---in our experiments so far---by the location of the
external data connection.  These coordinates are calculated and
maintained using control messages.  A reflex action triggered by
coordinate message arrival updates the local state to reflect the new
coordinates, and forwards appropriately-transformed coordinates to
each of its neighbors, using a message serial number to avoid looping.

\subsubsection{Housekeeping and Maintenance}
\label{sec:housekeeping-and-maintenance}

\noindent
In addition to the evolutionary operations described previously, there
are several maintenance tasks proceeding concurrently, which we touch
on briefly here for completeness and intuition.

\begin{description}
\item[Serial port management] The low-level software frequently sends
  ``Are you (still) there?'' messages out all serial ports, to allow
  prompt detection of tile connections and disconnections.
\item[Problem data update] If a (partially or completely) new problem
  data matrix is injected into the group, it propagates from tile to
  tile incrementally and automatically as a background process.
  Evolution continues during this process except during
  erasure of flash sectors which requires a tile reboot.
\item[System software update] If a new version of the PEC software
  itself is made available to the group, it will propagate tile
  to tile until the whole group is updated, again while evolution
  continues on the group as a whole.
\end{description}

This completes the high-level description of the PEC process, though
there are a number of details yet to present, such as the mechanism
whereby subpopulations determine what portion of a function space they
will optimize; these mechanisms are explained in the next section
where their application is demonstrated.

\section{PEC Demonstrations}
\label{sec:pec-demos}

\noindent
The application of the PEC process is explored through a number of
demonstrations.  Various fitness functions are satisfied using a variety of
group geometries and problem space to computational space
mapping schemes.

Though PEC scales to any number of tiles, all demonstrations here are performed on a group of 16 tiles
connected to a external power supply, and to an external computer
(connection shown in Figure \ref{fig:group-shapes}).  The external
machine is used to collect data from the group, and to send periodic
control messages to the group to assert the desired problem and
settings of the PEC parameters.
% coordinating the execution of multiple
%runs covering various combinations of problem set, geometry and
%mapping scheme.

\subsection{Setup}
\subsubsection{Fitness Functions}
\label{sec:problem-sets}

\noindent
Experiments are run against six fitness functions, consisting of
matching a set
of points in three dimensions.  Evolved individual candidate solutions
take the form of algebraic expressions over two variables represented
as character strings in reverse polish notation (RPN).  Individuals
are assigned a fitness based on their ability to match 
the surface of the fitness function.  Two of the dimensions of the
fitness function are aligned with the two spatial
dimensions in which the group of tiles are configured.

\begin{figure}[htb]
  \centering
  \subfigure[$\frac{(x-y)}{1}$]
  {\includegraphics{figures/poly0.pdf}\label{fig:poly0}}
  \subfigure[$\frac{(x-y) \times (x+y)}{2}$]
  {\includegraphics{figures/poly1.pdf}\label{fig:poly1}}
  \subfigure[$\frac{(x-y) \times (x+y) \times (x-y)}{3}$]
  {\includegraphics{figures/poly2.pdf}\label{fig:poly2}}
  \subfigure[$\frac{(x-y) \times (x+y) \times (x-y) \times (x+y)}{4}$]
  {\includegraphics{figures/poly3.pdf}\label{fig:poly3}}
  \subfigure[$10\times\sin{x}+10\times\sin{y}$]
  {\includegraphics{figures/poly4.pdf}\label{fig:poly4}}
  \subfigure[Montana gravity data]
  {\includegraphics{figures/gravity.pdf}\label{fig:grav}}
  \caption{Problem sets}
  \label{fig:problems}
\end{figure}

The six target sets are show in figure \ref{fig:problems}.  Four
are polynomial equations of increasing degree and
complexity which can be exactly matched by RPN individuals.  The fifth
is a trigonometric equation which can not be exactly matched by the
RPN individuals, and the final consists of gravity anomaly data
collected from the state of Montana \cite{montata-grav}.

\subsubsection{Geometric Configurations}
\label{sec:configurations}

\noindent
Tiles are assembled into groups using the geometric configurations
shown in Figure \ref{fig:group-shapes}.  The geometry can affect both
the portion of the problem space that is sampled by a group, as well
as the communication pattern between the group tiles---which has been
shown to impact the performance of distributed genetic
algorithms~\cite{stender}.  For example, due to its extension the line
configuration (Figure \ref{fig:line}) will sample more extreme values
of the problem space (under most mappings, see
section~\ref{sec:schemes} below), and, because each tile has at most
two neighbors, it will have more restricted intertile communication
which may be beneficial in some circumstances.

\begin{figure}[htb]
  \centering
  \subfigure[Grid]{
    \includegraphics[width=0.1\textwidth]{figures/grid.pdf}
    \label{fig:grid}}
  \subfigure[Bone]{
    \includegraphics[width=0.2\textwidth]{figures/bone.pdf}
    \label{fig:bone}}\\
  \subfigure[Line]{
    \includegraphics[width=0.4\textwidth]{figures/line.pdf}
    \label{fig:line}}
  \caption{Group Configurations}
  \label{fig:group-shapes}
\end{figure}

\subsubsection{Mapping Schemes}
\label{sec:schemes}

\noindent
The PEC practitioner decides how to align the dimensions of the
hardware and problem spaces.  This work demonstrates the mapping
schemes shown in Figure \ref{fig:mapping}.

\begin{figure}[htb]
  \centering
  \subfigure[Global Same]{
    \includegraphics[width=0.2\textwidth]{figures/global-same.pdf}
    \label{fig:global-same}
  }
  \subfigure[Local Disjoint]{
    \includegraphics[width=0.2\textwidth]{figures/local-disjoint.pdf}
    \label{fig:local-disjoint}
  }\\
  \subfigure[Global Offset]{
    \includegraphics[width=0.2\textwidth]{figures/global-offset.pdf}
    \label{fig:global-offset}
  }
  \subfigure[Local Overlap]{
    \includegraphics[width=0.2\textwidth]{figures/local-overlap.pdf}
    \label{fig:local-overlap}
  }\\
  \subfigure[Adaptive]{
    \includegraphics[width=0.2\textwidth]{figures/adaptive.pdf}
    \label{fig:adaptive}
  }
  \caption{Schemes \normalfont mapping hardware to problem space.
    Shown assuming the `Bone' configuration from
    figure~\ref{fig:group-shapes}.}

  \label{fig:mapping}
\end{figure}

\emph{Global Same} (Figure \ref{fig:global-same}) maps each tile to
the same portion of the problem space.  This scheme is what many
non-spatialized parallel ECs use; it is also one natural choice when
there is no obvious match between problem and hardware dimensionality.
\emph{Local Disjoint} (Figure \ref{fig:local-disjoint}) maps each tile
into a non-overlapping equal-sized portion of the problem space,
preserving the neighborhood relationships of the computational space.
\emph{Global Offset} (Figure \ref{fig:global-offset}) is similar to
global same; however the domain of each tile is slightly offset based
upon the tile's position in the computational space.  \emph{Local
  Overlap} (Figure \ref{fig:local-overlap}) is like local disjoint,
except the domain of each tile is slightly increased causing overlap
in the problem space.  Finally, the \emph{Adaptive} (Figure
\ref{fig:adaptive}) scheme begins with the same mapping as local
disjoint.  During the course of an adaptive run, tiles share their
mean fitness, and based on their comparative
performance, tiles increase or decrease the size of their domain in
the problem space, such that the better-performing tiles take on
larger portions of the problem space.

\subsection{Data}
\label{sec:data}

\Comment{ %% Not needed -- just a rehashing of the reification stuff
\subsection{Metrics}
\label{sec:metrics}

Both the data learned by the evolutionary algorithm and the space time
in which the physical hardware embeds the computation composing the
evolutionary algorithm can be related using real units.  In terms of
kilometers between points of latitude and longitude, centimeters
between on-tile CPUs and ms between computational events.  This
allows the assignment of units and real values to metrics of algorithm
performance.

For all experiments run we will report.
\begin{description}
\item[scale] Each tile maps directly from a subset of the hardware
  space measured in centimeters to a subset of the data space measured
  in kilometers resulting in a direct scale factor.
\item[innovation velocity] The velocity in $\frac{cm}{ms}$ with
  which candidate solutions move through the physical computational space
  as well as the velocity in $\frac{kilometers}{ms}$ with which
  candidate solutions move through data space.
\item[error] At every point in time the error can be measures as the
  integral of error over some subset of the problem domain.  The
  change of error over time will be a useful comparative measure
  between schemes and physical layouts.
\end{description}
}

\subsubsection{Group-wide error by scheme}
\label{sec:group-wide-error-by-scheme}

\noindent
Using the grid configuration, 10 runs were performed for each
combination of the first 5 problem sets, and the 5 mapping schemes.
The results are shown in Figure \ref{fig:poly-err-over-time}.

\begin{figure*}[htb]
  \centering
  \subfigure[$x - y$]
  {\includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-0.pdf}
  \label{fig:err-prob0}}
  \subfigure[$\frac{(x - y) \times (x + y)}{2}$]
  {\includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-1.pdf}}
  \subfigure[$\frac{(x-y) \times (x+y) \times (x-y)}{3}$]
  {\includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-2.pdf}}\\
  \subfigure[$\frac{(x - y)^{2} \times (x + y)^{2}}{4}$]
  {\includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-3.pdf}}
  \subfigure{
    \includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-key.pdf}}
  \subfigure[$10\sin{x} + 10\sin{y}$]
  {\includegraphics[width=0.325\textwidth]{figures/error-over-time-goal-4.pdf}
  \label{fig:err-prob4}}
  \caption{Error by mapping scheme over polynomial fitness functions}
  \Comment{
The average of 10 runs is shown for each combination of goal and
scheme.  Runs were terminated when either the perfect solution is
found and propagates to all tiles, or after 1 hour of run time.  For
each second of each run, the best guess of each tile is collected and
parsed into a function, these are combined into a single piecewise
function representing the entire group's ``best guess'' at that point
in time.  The integral of the difference between the ``best guess''
and the goal function is then calculated to find the total error on
the grid at that second.  For each total second of run time the
average total error over 10 runs is shown with completed runs averaged
in as 0
  }
  \label{fig:poly-err-over-time}
\end{figure*}

Performance by scheme is consistent across all five problem sets with
the three `local' schemes (\emph{local disjoint}, \emph{local overlap}
and \emph{adaptive}) resulting in less error than the two `global'
schemes (\emph{global same} and \emph{global offset}).  Against all
but the simplest problem set (Figure \ref{fig:err-prob0}) the
\emph{local overlap} scheme outperforms all others, showing consistent
improvement over the course of the run even against the most difficult
problem set (Figure \ref{fig:err-prob4}) in which many schemes show no
improvement after the first one thousand seconds of run time.

\Comment{
\subsubsection{Time to solution}
\label{sec:time-to-solution}

In addition to the total error over time, we can look at the time
taken to find the optimal solution.  While the \emph{local} schemes
perform better in terms of group-wide error it seems that the
\emph{global} scheme perform better in terms of likelihood of finding
the global optimal solution as shown in Table
\ref{tab:chance-by-scheme}, however when a solution was found the
local schemes generally found their solution in less time than the
global schemes as shown in Table \ref{tab:speed-by-scheme}.

\begin{table}[htb]
  \centering
  \subtable[Chance by scheme]{
    \centering
    \begin{tabular}{l|l}
      global same     &     70\% \\
      local disjoint  &  13.33\% \\
      global offset   &     30\% \\
      local overlap   &  13.33\% \\
      adaptive        &     20\% \\
    \end{tabular}
    \label{tab:chance-by-scheme}
  }
  \subtable[Time by scheme]{
    \centering
    \begin{tabular}{l|l}
      global same     &  1466.7142 \\
      local disjoint  &    2363.75 \\
      global offset   &  1565.5555 \\
      local overlap   &    2680.25 \\
      adaptive        &  2131.6667 \\
    \end{tabular}
    \label{tab:speed-by-scheme}
  }\\
  \subtable[Chance by shape]{
    \centering
    \hspace{0.25cm}
    \begin{tabular}{l|l}
      grid  & 83.33\% \\
      line  & 16.67\% \\
      bone  & 46.67\% \\
    \end{tabular}
    \hspace{0.25cm}
    \label{tab:chance-by-shape}
  }
  \subtable[Time by shape]{
    \centering
    \hspace{0.25cm}
    \begin{tabular}{l|l}
      grid  &    1861.48 \\
      line  &     1535.6 \\
      bone  &  1688.7142 \\
    \end{tabular}
    \hspace{0.25cm}
    \label{tab:speed-by-shape}
  }
  \caption{Exact matching of the first two goals.
    \normalfont The percent chance of finding the exact solution and the
    average time required to find a solution when found in seconds are
    give broken out by group shape and by scheme.}
  \label{fig:exact-solution}
\end{table}

It is also possible to break out the percent chance of finding the
optimal solution, and the speed with which such solutions are found as
a function of the shape of the group as shown in Tables
\ref{tab:chance-by-shape} and \ref{tab:speed-by-shape}.  Comparisons
between different shapes are less clear given that the shape of the
group partially determines the problem.
}

\subsubsection{Group wide error by robustness}
\label{sec:group-error-by-robustness}

\noindent
To explore the robustness of PEC in the face of unreliable hardware,
we simulated hardware errors by programming the tiles to reboot
probabilistically with an experimenter-specified mean time to failure
per tile ($MTTF_{tile}$).  We evaluated several levels of hardware
instability ranging from ${MTTF}_{tile} = 1000\mathrm{~sec}$ to
${MTTF}_{tile} = 50\mathrm{~sec}$, which---on the 16 tile grid in
which these experiments were run---results in a failure somewhere in
the grid ranging from about once per a minute, to about once every
three seconds.  We found that all trials with ${MTTF}_{tile} <
5\mathrm{~sec}$ failed in the sense that the group lost its programmed
PEC parameters and reverted to default settings (as described in
Section \ref{sec:lord-of-the-flies}).  The results are shown in Figure
\ref{fig:error-by-robust}.

\begin{figure}[htb]
  \centering
  \subfigure[Best Performers by Robustness]{
    \includegraphics[width=0.45\textwidth]{figures/gravity-robust-bins.pdf}
}\\
  \subfigure[Error by Robustness]{
    \includegraphics[width=0.45\textwidth]{figures/robustness-over-gravity.pdf}}
  \caption{Error by robustness over gravity data}
  \label{fig:error-by-robust}
\end{figure}

As shown, more robust hardware is not generally preferable to unstable
hardware.  In the first 50 seconds the best performing reboot rate is
once every 50 seconds per tile, from 50 seconds to 100 seconds the
best performing hardware reboots every 100 seconds per tile, from 100
to 250 seconds a rate of once every 500 seconds is preferable, and in
the final 1000 seconds the perfectly stable hardware was the most
consistently successful performer.

To the PEC practitioner, hardware robustness becomes just another knob which may
be tuned with other PEC parameters to adjust the exploration vs. exploitation
trade off of the evolutionary computation.  This is understandable given
that on reboot the local subpopulation is re-populated with randomly
generated individuals.  Also, while individuals are lost on reboots, it
is likely that fit individuals will spread to multiple tiles
increasing their resilience to such loss.

\subsubsection{Spread of solutions through the group}
\label{sec:spread}

\noindent
Figure \ref{fig:grid-secs} shows six snapshots of a successful run
against the second problem \label{fig:poly1} using the \emph{local disjoint}
scheme \ref{fig:local-disjoint}.  The exact solution first appears
roughly 1900 seconds into the run \ref{fig:grid-1900-sec}, this
solution is then immediately lost \ref{fig:grid-1910-sec}, and then
quickly recovered \ref{fig:grid-2000-sec} after which it overtakes the
entire group \ref{fig:grid-2055-sec}.

\begin{figure}[htb]
  \centering
  \subfigure[1 second]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-1.pdf}
   \label{fig:grid-1-sec}}
  \subfigure[900 seconds]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-900.pdf}
   \label{fig:grid-900-sec}}\\
  \subfigure[1900 seconds]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-1900.pdf}
   \label{fig:grid-1900-sec}}
  \subfigure[1910 seconds]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-1910.pdf}
   \label{fig:grid-1910-sec}}\\
  % \subfigure[1950 seconds]
  % {\includegraphics[width=0.225\textwidth]{figures/grid-sec-1950.pdf}
  %  \label{fig:grid-1950-sec}}\\
  \subfigure[2000 seconds]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-2000.pdf}
   \label{fig:grid-2000-sec}}
  \subfigure[2055 seconds]
  {\includegraphics[width=0.225\textwidth]{figures/grid-sec-2055.pdf}
   \label{fig:grid-2055-sec}}
  \caption{Spread of the exact solution \normalfont video of this run
    is available at \texttt{--anonymized--}}
  % http://cs.unm.edu/~eschulte/research/pec/runs/grid.1.1.4.mp4
  \label{fig:grid-secs}
\end{figure}

%\subsection{PEC in Practice: Life on the run}
%\subsection{PEC in Practice: Evolution in action}
\subsection{Life with PEC}
\label{sec:anecdotes}

\noindent
With their go-go operation and wild-and-woolly parallelism, PEC
systems are much like natural systems, and for just that reason they
violate typical assumptions of how a computer ``should work.''  Here
we offer two brief tales of mistakes we made during development,
illustrating some of the perils of carrying serial and synchronous
assumptions uncritically into this new context.

\subsubsection{Instant Winners}
\label{sec:leaking-solutions}

\noindent
All the data we have presented is gathered over repeated runs in each
experimental condition, and performing those separate runs was
accomplished using a controlling script running on the external
computer, which sent periodic control messages to the connected tile
group to begin and end runs and to change PEC parameters.

Since it is not possible to communicate with all tiles
instantaneously, messages intended for global distribution pass
through a group of tiles somewhat like ripples spreading on a pond,
and during that process such messages race against all other messages
moving in the system.  For example, when a `global reset message wave'
reaches some tile and causes it to reset, there might still be an
in-flight sharing message inbound to that tile from a `downwave'
neighbor, which can recreate an evolved individual and the PEC
parameters that the global reset was attempting to erase.

During early data collection we found that sometimes fit individuals
were surviving the `official' end of one experiment and then
immediately dominating the next experiment, looking like
\emph{extremely rapid} evolution!  Now, however, the experiment driver script
on the external machine is designed to recheck the state of tiles
after a parameter change and to repeatedly ``flood'' the group until
all tiles are on board---but without global privileged points in
computational space-time there is simply no 100\% reliable hook by
which a PEC practitioner may take hold of computation.

A robust solution more in the PEC spirit, if one cared more about
results than statistical independence, would be to abandon any
pretense of dividing time into discrete `experiments' and instead just
periodically redrive the currently desired problem and parameters into
the grid, whether it has changed or not.  Or on the other hand, if
independence is \emph{really} critical, then falling back to the
`physically privileged point' in PEC---i.e., power-cycling the entire
grid, with all the delays and inconvenience that implies---is the way
to go.

%% In the above example there is no obvious way to
%% synchronize the expulsion of previously learned solutions. More
%% generally enforcing consensus between the tiles on items like the
%% current problem to be solved or the current scheme by which to
%% organize evolution requires great care.

\subsubsection{Lord of the Flies}
\label{sec:lord-of-the-flies}

\noindent
When a tile joins a working group, either due to it rebooting or being
a hardware addition, it must learn the goal
and parameters of the group.  Immediately upon powering up a tile reads its
own ``inherent parameters'' from persistent memory and begins evolving
using those default settings.  It then attempts to acquire the
``cultural knowledge'' of the goal and scheme in use by its neighbors
in the group

Early versions of our PEC software failed to distinguish
`read from persistent memory' vs `learned from neighbors' parameter
sets.  As a result, it could happen that a pair of  
adjacent tiles might both reboot in a narrow window of time, then
share their inherent parameters with each other---each convincing the
other that their inherent `state of nature' settings were actually the
`culturally sanctioned' settings of the group as a whole.  Small
subgroups formed in this way proved persistent, and, in some cases,
grew to overtake an entire group.

We addressed this by adding a \emph{provenance bit} that tracks the
source of a parameter set and allows a tile to ensure it does not
falsely advertise its inherent parameters as cultural.  Still,
however, we observed that in sparsely connected groups
(e.g. configuration \ref{fig:line}), when combined with a high
frequency of hardware reboots, it is possible for isolated subgroups
to lose the sanctioned parameters of the group and to revert to
evolving under their inherent parameters.  Similarly, as tiles reboot,
for whatever reason, they temporarily ``drop out'' of the group and
stop passing messages, which can cause the network communication graph
to become temporarily disconnected, exacerbating the global
coordination issues mentioned earlier.

\section{Discussion}
\label{sec:discussion}

\noindent
PEC's inherent scalability stands in stark contrast to the ultimate
unscalability of serial EC strategies.  On the other hand, however,
tasks like pausing, restarting, or exactly repeating a
computation---trivial in serial models---are decidedly non-trivial, or
even impossible, with PEC.  PEC tiles generate new solutions
spontaneously and steadily, a process that is necessarily destructive
as well as creative;
lacking a synchronous global clock it isn't even easy to
\emph{define}, let alone capture, a consistent global snapshot of an
entire group.  Any communications must propagate through the group, at
some finite velocity, while the group as a whole continues to evolve.
Similarly it is impossible to write a complete state to a group of
tiles as the state will change as it is being written.

On the other hand, a potential benefit of the focus on robust
indefinite scalability is that, lacking any requirements for rigid
global control, PEC carries far fewer design commitments than many
parallel EC approaches, making it easier for PEC to `play nice' within
a larger computational system.  Give a PEC grid power and a task, and
it gets right to work without a lot of fuss; if the solutions coming
back aren't good enough fast enough, it is easy to try plugging in more
grid: robust indefinite scalability means the new hardware will
automatically be recruited by the group and increase its computational
power.

Indeed, so far our sense has been that those items which proved most
difficult with PEC were often tasks of coordination and measurement
desirable for researching \emph{PEC itself}, while PEC's comparative
strengths---such as non-stop and real-time operation and extreme
robustness---are more likely to benefit `embedded PEC practitioners'
deploying evolutionary computation within a larger system design.

\subsection{Computational Space-Time}
\label{sec:platforms}

\noindent
The prototype hardware layer used in this effort continues a long
history of implementing EC on distributed hardware systems
\cite{beowulf, poli:1999:22par, langdon:2005:metas}.  This particular
hardware system is unique in the composability of hardware tiles,
which by the nature of their physical connections ensure both a
spatial location of each calculation, and a locality of each
communication.

The discrete 2 dimensional space created by a group of tiles,
augmented with the temporal dimension defined by tile's hardware
timers, results in a discrete 3 dimensional grid of computational
space-time.  Every event in this space-time will fill a 1 dimensional
rectangle with one of two possible orientations.  Either the event is
extended in time on a single tile, or the event extends between two
adjacent tiles in a single instant.

Developing software for such computational environments is a difficult
task to which classical algorithmic techniques are not well suited.
However, as computer engineers pack hardware into successively smaller
pockets of space and time it becomes necessarily for computer
scientists to make concessions to the basic rules of the physical
world---spatial orientation, local causality and decreased
reliability.  As this work indicates, EC is well suited to such
constraints and may even benefit from the imposed structure.

\subsection{Reification}
\label{sec:reification}

\noindent
The rigid mapping between hardware elements and points in
computational space allow for novel computational metrics.  Extensions
in the 3 dimensional grid of computational space-time may be measured
in \emph{real} units.  Each tile measures 4.75 centimeters on a side,
and hardware timers are scheduled with millisecond granularity.  Due
to this reification of computational metrics, real ratios exist
between measurements in the computational and problem spaces---like
the legend on a map, each centimeter of computational space will
represent a real distance in the problem space.  Consequently, real
valued computational metrics such as the maximum rate of spread of a
fit individual through a group (or \emph{innovation velocity}) may be
translated directly into real velocities in e.g., kilometers per hour
in the problem space.

\subsection{Conclusion: Abstract different}
\label{sec:conclusion}

\noindent
In its treatment of space and time, PEC is most aggressively concrete
just where traditional models of computation are most aggressively
abstract.  But for all that, PEC still \emph{is} an abstraction,
smoothing over everything from the details of the fitness function and
the specific genome representation and its interpretation, to the size
and geometry of the tile group performing the computation, to the
hardware details of the tile itself.  It is just a \emph{different}
abstraction, and, by representing space-as-space and time-as-time, it
is an abstraction that allows studying couplings between the
computational and the physical in a rather direct, and we think rather
refreshing, way.

The separation of levels---such as the disinction between hardware and
software---is at once one of the greatest successes of computer
science, engineering, and the industry, and also a cause of many of
its difficulties.

The Microsoft doesn't know, and doesn't want to know, what the Intel
is doing.

So everybody just agreed to keep making, and using, ever bigger VNs.

But that's ending now, and even if it wasn't, there's increasing
recognition that maybe its possible for a VN to be too big.  Like if
biology had scaled the way the von Neumann machine has, something the
size of a person would be one gigantic amoeba.

With the technical knowledge, manufacturing prowess, and cost
reduction gained from decades of VN development combined with
multimillion unit blockbusters such as the cellphone, an new
opportunity is emerging for researchers to investigate substantially
novel computational architectures---reslicing across the traditional
lines of hardware and software, using masses of cheap VN's as a
flexible computational `clay', rather than a scalable goal in itself.
In the evolutionary computing community, as PEC illustrates, we can
push our methods down closer to the hardware, and look towards full
systems with embedded adaptive components, rather than continuing to
strand EC in the isolated environments of the standalone research
tool.

\Comment{
As engineers squeeze computation into ever smaller pockets of space
and time % through further embedding into the physical world
it is
necessary for computational space to make concessions to the basic
rules of the physical world---spatial orientations, local causality
and decreased reliability.  As this work indicates, EC is well suited
to such constraints and may even benefit from the imposed structure.
It is our hope to encourage EC practitioners to embrace such
\emph{physical} computational spaces as a viable and inevitable
alternative to traditional \emph{abstract} models of computation.
}

\bibliographystyle{apalike}
\bibliography{physical-evolutionary-computation}

\end{document}