\section{\label{performance}Multiprocessor Performance}

Given the three mapping plans proposed above, let us consider
their use in code construction for multiprocessor computers.
First we introduce the two processor architectures we use as
contrasting targets for parallel computing. Then we discuss
the machine code structures appropriate to implementing
continuous processing applcations such as the optical surveillance
computation. We discuss the performance differences among the
three plans and point out the tradeoffs possible among
throughput, memory, and latency of output data.


\subsection{Architectures}

We consider two contrasting multiprocessor architectures.
One uses processing elements of conventional architecture with
features intended to support efficient multiprocessor computation. We
designate this the CVA (ConVentional Architecture) machine.
A commercial example of such a processing element is the
Texas Instruments TMS320C3x digital signal processor. This machine has
high single-thread performance, but makes only modest concessions to
supporting fine-grain synchronization and communication
for efficient parallel computing. In this architecture, a thread
is created by a {\tt fork} command or a parallel function call
interpreted by run-time software, and may terminate at a {\tt join}
command or by execution of a {\tt quit} command. A thread may
be suspended to wait for some event to occur, and it may be
preempted to allow the processor to handle interrupt events or
to schedule a thread having a higher priority.

The second architecture uses a
hypothetical processing element having an interleaved multithreading
architecture, as proposed in \cite{DennisGao94, Dennis89}.
We designate this
one the MTA (MultiThreaded Architecture) machine. In
this processor there may be four active threads that share
resources (functional units, registers, and access to local
memory). Threads are non-preemptible, so execution of
a ready thread is delayed until one of the four pipeline slots
is released by termination of an active thread. A thread becomes
ready for execution when it is signaled from other threads, or
when a message arrives from another processor. A thread uses a small
number of registers to pass results from one instruction to a
later instruction of the thread; registers are undefined
when a thread becomes active and are not saved at thread termination.
A typical thread will either send signals to activate other threads,
or send an interprocessor message just before terminating by
executing a {\tt quit} instruction. In the MTA a thread is a
sequence of instructions fixed at compile time and is
short enough that other threads may be executed soon enough to
meet performance requirements.

Other multithreaded architectures have supported eight active
threads to allow tolerance of long memory accesses. For the
present discussion we assume that multiplexing four threads
in the computation pipeline is sufficient to tolerate the
latency of accesses to local memory and to fill pipeline
gaps due to intra-thread dependences.

To compare the two architectures for our example,
we will assume that both are able to achieve the same
total instruction processing rate. This means that one
thread on the MTA will run one fourth as fast as a single
thread on the CVA. (This is unfair to the MTA because the CVA
will be slowed more by pipeline hazards.)

With respect to implementing the mapping plans for the
optical surveillance problem, the differences 
that affect the code structure needed to get best
performance are the following:

\begin{enumerate}

\item
A CVA processor can be fully utilized by a single thread.
For the proposed MTA machine, four threads are
needed to fully utilize the processor.

\item
Switching between threads is more expensive for the CVA, so long
threads are favored. The fast switching of the MTA processor allows
short threads to be used, permitting more parallelism to be
exploited.

\item
Sending and receiving overhead is very low in the
MTA machine, so very short messages may be handled efficiently.

\end{enumerate}


\subsection{Machine Code Structure}

In the MTA the low cost of threads allows the machine-level
program structure to reflect the concurrency structure of the
algorithm being implemented. In the case of the CVA, it will
be advantageous for high throughput to
unroll loops to obtain long threads, and to block data into
long messages to amortize message-passing overhead.

For both architectures, it better to run long threads because
starting and terminating threads has a non-zero cost in both
processors. Since we are assuming that local memory accesses
do not cause pipeline gaps, the only events that benefit from
thread switching are synchronizations with data arriving in
messages from other processors, and to provide sufficient
multiplexing of module operation to meet latency and
throughput requirements of the application.


\subsection{The Example}

First we determine the number of processors needed to perform the
computation at the desired rate. To do this we estimate the number
of instructions needed to perform one compute cycle, multiply by the
desired rate and divide by the performance of the processing element.

From Table~\ref{load-table} we see that 139,138 operations per compute cycle are
needed. Allowing an equal number of data movement and miscellaneous
instructions, and allowing and additional 25 percent for overhead
of scheduling and communication, we find that the total instructions
per cycle will be about\footnote{These are estimates made without
careful analysis. We plan
to carry out a more detailed evaluation.}.
\[I_{cycle} = 139138 \times 2 \times 1.25 = 347,845\]
using the desired rate of 2.5 kHz., we find that
the total instruction rate must be at least
\[R_{instr} = 869\ MIPS\]
This rate could be met by 18 processors at 50 MIPS each, so
to be generous, let us assume a machine with 20 processors.

Of the proposed mapping plans, Plan C has the greatest
communication load because communication is needed to
pass the entire data stream between each of two pairs of
program modules (as well as a small amount of intra-module
communication). The communication rate required will be
$2w = 512$ words per compute cycle, or $1.28$ million words
per second. This is less than $0.2$ percent of the required
instruction rate and is far below the capacity of typical
interconnection networks. This is indeed an embarrassingly
parallel computation, and is compute bound
for all three mapping plans.

There is one more issue to discuss before we consider the
mapping plans separately. A major challenge for this
computation is handling the large number of high volume
input data streams. In each case we assume
that input data from the sensors is
made available to the multiprocessor in blocks of eight
values for each ``channel'' of data processing. This means
processing one interrupt by the CVA or one synchronization event
for the MTA for each channel on every minor cycle of operation.
Similarly, the results of processing are delivered to the user
as blocks of 16 16-bit words containing the (Boolean) peak data
for one cycle of processing. Handling the output stream is a
very minor problem, but the rate of input data stream events is
\[R_{inp} = 4 \times w \times 2.5 = 2.56\ MHz\]
or 128,000 input event per second for each processing element.
If each input event is handled in the CVA machine by processing
and interrupt and scheduling a thread, the overhead cost will
be high. In the MTA machine, the corresponding cost is that
of synchronizing thread initiation with an input event, which
amounts to just a few processor cycles.


\subsubsection*{Plan A:} Under Plan A, computation by
each of the five program modules is
distributed over all 20 processing elements. If each processor
performs the work associated with $256/20 = 13$ channels of data, the only
interprocessor communication will be to support the boundary references
in the {\tt TwoDimFilter} and {\tt PeakDetect} modules. As we have
already noted, this communication load is very small.

In the CVA machine, a single high-priority thread may perform the 32
executions of {\tt BaseRemove}, four executions of {\tt  SpikeAdapt},
and one execution of {\tt NyquistFilter} for each data stream in
each compute cycle. There will be a substantial cost associated
with synchronizing the start of this thread with the arrival
of $4 \times 13 = 52$
blocks of sensor data for each compute cycle. Separate
lower priority threads may be used
to perform the {\tt TwoDimFilter} and {\tt PeakDetect} computations
when signaled by arrival of messages containing boundary data.

In the MTA machine, many threads may be employed without thread
switching overhead becoming significant. One attractive structure
is to use a separate thread to perform the work of the three
front-end modules for each data channel. Each of these threads
would contain 351 operations, which is sufficiently short
that responsiveness of processing will not be affected.
One thread apiece will serve to perform the {\tt TwoDimFilter} and
{\tt PeakDetect} computations after synchronizing with
interprocessor messages.

The {\em latency} of processing is the time interval between
arrival of input data and the availability of output data
that depends on it. Some of the processing steps of the optical
surveillance example have a built-in delay of from one to three
operation cycles. Additional latency is introduced in the machine
program by overhead costs and because once operations are performed
additional work is done before the consumer of results is scheduled
or signaled to begin operation. In this respect, the MTA machine
has the advantage because its finer granularity of processing
allows successor threads to be signaled sooner than is feasible
to schedule them in the CVA machine. This is partially
compensated by the property that threads execute four times
faster in the CVA.


\subsubsection*{Plan B:} In Plan B a two processors would perform all
computation for {\tt TwoDimFilter} and {\tt PeakDetect}. Because there
would be only two sections of the data stream, message traffic
for intra-module communication would be smaller. Instead, the entire
data stream passing from Nyquist to TwoDimFilter would have
to be carried in interprocessor messages. Handling this
data stream on a word by word basis would involve a large
overhead for the CVA machine (more cycles than needed to
execute the {\tt TwoDimFilter} algorithm), but would be a relatively
minor amount for the MTA (ten percent or less). Although the
higher communication load for this plan would not overload
a typical network, there is no compensating saving because
the intra-module communication need is so low, and the plan
has the disadvantage of introducing unbalanced use of
parts of the network. Under this mapping plan, there would be
good opportunity to improve performance of the CVA by
passing data in large blocks between stages of the computation,
however this would increase the latency of results and require
large data buffers.

\subsubsection*{Plan C:} Plan C takes the further step
of executing {\tt TwoDimFilter} and
{\tt PeakDetect} algorithms on separate groups of processors, further
increasing the communication load without compensating benefits.


\subsection{Discussion}

The principal difference between the two architectures is
in the cost of synchronization, which also reflects a
difference in the handling of global memory access. (One
may regard the communication performed to implement access
to boundary values of the data array in TwoDimFilter and
PeakDetect as instances of a general mechanism for
global memory access.) The effect is greater in computations
that can benefit from short threads.

The impact of this cost on performance of the CVA may be
mitigated by several standard techniques, namely breaking
the data stream up into blocks of sufficient length that
the start-up cost for sending and receiving messages is
acceptably small. The penalty is longer latency of results
and increased amounts of memory needed to buffer blocks
of data between processing stages.

In the calculation of performance it is also necessary to
check that the performance is actually achievable, that is,
that there is sufficient parallelism that no processing element is ever starved for
work. This may be done using Petri nets to represent the dynamic
behavior of the scheduling of threads, but is beyond the scope of
this paper.
