

\documentstyle{article}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-0.3in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.8in}
\setlength{\parindent}{0in}
\setlength{\parskip}{0.2in}

\begin{document}

\title{\bf On Decentralized Task Allocation and Scalable Cache Coherency\rm}

\author{Norman Matloff \\
Division of Computer Science \\
University of California at Davis \\
Davis, CA  95616 \\
matloff@heather.cs.ucdavis.edu \\
(916) 752-1953, (916) 752-7004}
\maketitle

\begin{abstract}
Recently there has been considerable interest in
cache coherency protocols in shared-memory multiprocessor systems,
particularly in protocols which are scalable, i.e. suitable for very 
large systems.  However, cache coherency scalability (CCS) entails heavy
performance overhead and system cost, so a critical examination of
the assumptions underlying the quest for CCS is undertaken here.
The focus is on monitor variables, which comprise the majority
of cache invalidations.  Evidence is presented here that in most
applications, these invalidations can be greatly reduced, using a 
very simple technique.  The findings provide theoretical and
empirical justification for some types of CCS hardware, while
indicating that other types of such hardware should be eliminated.
An architecture which provides only ``locally, but not globally,
coherent" hardware support is also proposed.
\end{abstract}

\maketitle

\section{Introduction}

     In the last few years, scalability of cache coherency protocols
has been one of the most active topics of research in shared-memory
multiprocessor systems.  A nice survey of this area, with a good
list of references, was presented in [Stenstrom], and new papers have 
continued to appear since then.  However, cache coherency scalability 
(CCS) requires complex hardware, which carries significant overhead,
inhibiting system performance, both in absolute terms and also with
respect to performance/price ratios.  It is thus worthwhile to examine 
the fundamental question of whether CCS is a sufficiently desirable 
property to warrant the heroic efforts which are being made to 
achieve it.  This question is addressed here, and evidence toward an
at least partially negative answer to it is presented.  

     The key point involves the type and extent of hardware which
should be devoted to support for coherent access to globally shared
data, i.e. data which are at least potentially shared by all processors
in the system.  It is found here that a large portion of accesses to such 
data can be replaced, in a very simple manner, by data shared only by a
fixed number of processors, with that fixed number being independent of overall 
system size.  This
obviates much of the need for scalability.  The findings here provide 
theoretical and empirical justification for some types of CCS hardware, 
while indicating that other types of such hardware should be eliminated.
An architecture which provides only ``locally, but not globally,
coherent" hardware support is also proposed.

     The concept of CCS may be summarized as follows:  A central 
problem in the design of shared-memory processors is contention for 
both memory and the processor-memory interconnect.  Installing cache 
memories at the processors reduces this contention, but if shared 
variables may be cached, the problem arises of consistency among 
several copies of such variables.  Clever protocols for insuring 
consistency have been developed, but these protocols add significant 
overhead, negatively impacting system performance.  This overhead is 
particularly problematic in systems with large numbers of processors, 
i.e. there is a {\it scalability} problem. 

     At the heart of the matter is atomic access to monitor variables 
(MVs), i.e. temporarily exclusive access of one processor to a lock
variable or equivalent.  Empirical work has shown that the 
majority of coherency transactions involve such variables [Agarwal89].
For this reason, the major focus of this paper is on MVs.

     For reasons which will emerge below, let us roughly divide the 
class of MVs into those which are frequently accessed (FAMVs), and the 
rarely-accessed ones (RAMVs).  A typical example of an FAMV is a lock 
variable that is guarding access to a task-allocation data structure.
If task time and the access time of the data structure itself are small, 
the lock variable will be an FAMV. 

     RAMVs often occur as {\it barrier} variables [Boyle].  For example,
such a variable may be used at the end of a parallel program, to determine
when all processors have finally finished their last tasks.  In such a
setting, this variable is accessed only at the very end of execution,
and is thus an RAMV.  (On the other hand, some barrier variables are
FAMVs, as an example in Section 5 shows.)

     Another example of RAMVs is the ``column-ready" variable type in the 
LU matrix decomposition application used in [Gupta].  Let us denote such a
variable for column i by $C_i$.  For each column, sequentially from 
left to right, a ``phase-A" process is done, followed by an associated 
``phase-B" process of all columns to the right of the current one.  
When column i's phase A is finished, $C_i$ will change value so as 
to give a Proceed signal to the other processors, so that they may perform 
phase B for columns j, j $>$ i.  The scalability context here would 
concern the effect on $C_i$ as matrix size increases, which will be 
that $C_i$ will become more and more an RAMV as the matrix size 
increases.

     Atomic access to an MV can be implemented either in hardware, for
example in cache coherency protocols and related support mechanisms
such as test-and-set instructions, or indirectly in software.  Clearly, 
hardware support is justified only for FAMVs, not for RAMVs.  Accordingly, 
FAMVs form a major underlying motivation in the quest for CCS. 

     As mentioned earlier, CCS schemes carry very substantial overhead, 
which slows system speed.  The slowdown stems from the fact that when a 
cached MV changes value, that event must be made known to other caches 
which contain copies of the MV.  These invalidation messages take time, 
especially in larger systems.

     For example, consider the Scalable Coherent Interface (SCI) standard 
[James], a directory-based cache-coherency protocol.  SCI features the 
ability to create very long linked lists of processors which share an MV.  
SCI manages these lists very efficiently.  However, even with the highest 
efficiency, the propagation delay for a cache update message along such 
a list is quite substantial, with an attendant slowdown in system speed.
Improvements have been suggested, e.g. adding redundant links so that a
message can be sent to several caches simultaneously, but the point still
is that as the system grows, the mean time to propagate an invalidation 
message will grow as well.

     The same difficulty occurs in all cache-coherency schemes for large 
systems:  When a processor writes to a cache line, the cache must send
cache-invalidation messages to all other caches currently sharing that
block.  This is the root of the scalability problem, because the larger
the system, the larger the potential number of caches which may share a
block, and thus the more problematic the sending of invalidation messages
becomes. 

     Again, FAMVs are common in current implementations of parallel 
processing algorithms, usually in support of mechanisms to allocate tasks 
to the various processors.  When a processor finishes a task, it will then 
seek a new task to perform.  However, since processors must contend with 
each other for access to the task-allocation data structure,
a large number of cache invalidations may be generated.

     One possible solution to this problem would be to replace this
centralized task allocation by decentralized task allocation:  Processors
would be divided into groups, and instead of having one task-allocation
data structure, there would be several, one for each processor group.
A processor would then contend only with other processors in its group.
The significance of this is that the number of invalidation messages
generated for any given write is limited to the group size.  {\it In other
words, the number of invalidation messages for a given write does
\underline{not}
grow as the system size grows, and thus there is no scalability problem
in task-allocation actions.}  This will form the central topic of
this paper.

     In Section 2, the implementation of decentralized task allocation 
will be outlined for several different types of applications.  This is
done to clarify the subsequent discussion, to demonstrate that it entails
virtually no additional effort on the part of the programmer, and to 
emphasize that it is architecture-independent, a general programming
technique for use on {\it any} shared-memory multiprocessor, i.e. any
multiprocessor with a single, completely shared address space.

     In Section 3, a mathematical model for these ideas is presented 
which demonstrates that decentralized task allocation is efficient.
This is then supplemented by simulation results for specific application 
types; it is here that we see that decentralized task allocation is not 
only as good as the centralized kind, but is actually {\it superior}, 
once we account for the overhead involved in accessing a task list.

     Section 4 then discusses the architectural implications of these
findings.  First, it is pointed out that these results provide some
justification for the clustering in DASH [Lenoski], and for the 
limited-hardware features of the LimitLESS protocol [Chaiken91] of
ALEWIFE.  On the other hand, the results here are shown to suggest
that some features of these machines, such as DASH's lock queues,
should be eliminated or at least modified.  It is also indicated
that modifications to SCI, such as the redundant pointers mentioned
earlier, may be of lesser importance than previously thought.
Also, a new class of machines, called LCSMA (locally coherent
shared-memory architectures) is proposed, with the main feature
being that hardware is devoted only to within-group cache coherence,
not between-group coherence; in other words, in this proposed
architecture, CCS has been eliminated entirely as a design criterion.

     Section 5 then presents some discussion.


\section{Implementing Decentralized Task Allocation}

     This section will outline the implementation of decentralized task 
allocation for several different types of applications.  Before beginning, 
it should again be noted that this is an {\it architecture-independent}
programming technique,\footnote{
The term architecture-independent is used here in the sense of [Boyle],
meaning from the point of view of the applications programmer (in the
rest of this paper, this latter term will be abbreviated to ``programmer").
Machine dependencies, such as test-and-set instructions, are made
transparent to the programmer, by making available a set of system
calls, as in [Boyle].  The analogy here is that of Unix, say 4.3 BSD,
which provides an architecture-independent interface to programmers
on many different machines.}
described in [Ni] for {\it general} shared-memory multiprocessors.

     In the decentralized version of any application, at the beginning
of the program there would be a system call:

\begin{verbatim}
   GN = GetGroupNumber();
\end{verbatim}

which will place into GN the group number of this processor, analogous
to the Unix getpid() and getpgrp() calls.  The group number will range
between 0 and $g-1$, where g is the number of groups.

     The first example is a simpler one, called MATMULT, involving the
multiplication of a single column vector by a large, square matrix. 
In the centralized version, the task-allocation 
data structure consists simply of a single global variable, called 
Next\_Row, which contains the number of the next row available to be 
multiplied.  When a processor finishes the multiplication of a row, 
it performs

\begin{verbatim}
   R = Next\_Row++;
\end{verbatim}
 
and then does the multiplication of row number R.  

     In the decentralized version, the direct analogy of Next\_Row is
a g-element array Local\_Next\_Row.\footnote{Actually, there should be 
more than g elements, with much padding of 0s,
to prevent cache-block aliasing (i.e. to prevent having two nonzero
elements of Local\_Next\_Row in the same cache block) when applied to 
Section 4 and the CCS question.  This would again be done via a system 
call, GetPaddingSize(), so that the programmer would not have to worry
about the underlying architecture.  But for convenience of notation,
this will be ignored here.}
There is also a variable Glob\_Next\_Row 
and another g-element array Local\_Last\_Row, which are used indirectly,
as will now be seen.  When a processor finishes the multiplication of a 
row, it performs

\begin{verbatim}
   R = Local\_Next\_Row[GN]++;
   if (Local\_Next\_Row[GN] > Local\_Last\_Row[GN])  {
      Local\_Next\_Row[GN] = Glob\_Next\_Row;
      LR = Glob\_Next\_Row += K;
      Local\_Last\_Row[GN] = LR - 1;
   }
\end{verbatim}

What is happening here is the following:  Initially each group is
allocated a set of K consecutive rows of the matrix, K being a design
parameter.  The processors in that group process these rows one-by-one,
just as in the centralized case, with Local\_Next\_Row[GN] playing the
role corresponding to Next\_Row in the centralized version.  When one
of the processors discovers that these K rows have all been processed,
it goes to Glob\_Next\_Row to get K more rows for its group.  (Compare
to [Kruskal], in which each {\it processor}, rather than each group, 
is assigned K tasks at a time.  By assigning batches of K tasks to 
groups rather than processors, work is distributed more evenly, and 
thus overall completion time is reduced.)  

     In the centralized version, the programmer must signal to the
compiler or OS that NextRow is to accessed atomically, e.g. with a
test-and-set instruction.  In the decentralized version, this must
be done for Glob\_Next\_Row and the two arrays.

     Except for these few lines, the remainder of the code would be
line-for-line identical in the centralized and decentralized versions.  
The point is that the programmer does \underline{not}
assign processes to processors, etc.

     Note that though the entire arrays Local\_Next\_Row and Local\_Last\_Row 
are global variables visible to all processors, the code is written so
that a processor in one group will never access the array element
intended for another group.  In the code above, for instance, the only 
array index used is GN.  

     Another well-known application is that of ``the heat equation" (HEAT).
Here one has, say, a two-dimensional grid of points, and an iterative 
computation.  The iteration n value at any given point is computed as 
the average of the iteration (n-1) values at the four neighboring points.  
In order to minimize processor idle time, an asynchronous setup will be 
assumed here, so that different processors might be working on different 
iterations at the same time.

   In the centralized version, there might be a linked list, ReadyList, 
showing which points are currently eligible for another 
iteration.\footnote{Actually, it is more common to have a processor work on a 
{\it set} of
points in one iteration, say a vertical strip of points, but the
discussion here will be simpler if we think of a processor as being
assigned to one point at a time.}
When a processor finishes a point, it would simply delete the head of
this list, and start work on the point specified by the deleted list item.
The decentralized case would be very similar, with the grid now being
divided into g regions, and the i-th processor group being assigned to 
the i-th region.  ReadyList would now be an array of linked lists, with 
ReadyList[GN] being the list for group GN.  (This arrangement for HEAT,
and that of QUAD below, could be made more dynamic, by setting up a
variable analogous to Glob\_Next\_Row in MATMULT above; however, the setup 
here is quite sufficient in these two applications.)  

     The next application, QUAD, involves quadrature, i.e. numerical
integration [Boyle].  The region of integration is successively bisected
into an increasing number of subintervals.  A task consists of bisecting 
the given subinterval, applying the trapezoidal rule to each of the two 
parts, and comparing the area so obtained with the area determined for 
the original subinterval.  If the difference is within a specified 
tolerance level, no further bisection is done; if not, one of the parts
is then processed again by the current processor, and the other is added 
to the task list.  

     In the centralized version, there is one global task list.  In
the decentralized version, the region of integration is divided
into g subregions, with the i-th processor group working only on 
intervals within the i-th subregion.

     Two applications similar to those above are described here 
briefly.  First, consider the LU matrix decomposition mentioned earlier.  
It is similar
to the MATMULT example described above, with columns being analogous
to rows.  In the straightforward implementation described here (more
aggressive approaches can be used), after the phase-A operation for 
column i, the centralized version would set Next\_Column to i+1, and
the processors would acquire tasks using this variable, as they did
with Next\_Row in MATMULT.   The decentralized version would again be
analogous to that of MATMULT, with for example the variable
Global\_Next\_Column being set to i+1, and incremented by K whenever 
a processor acquires a set of K columns on behalf of its group.

     Another problem to consider is that in which one is given a set 
of letters, say o, n and w, and finds all words in a given dictionary 
that can be formed from these letters (no duplication allowed).  
Suppose a depth-first tree search is used, as shown in Figure 1.  
Calling the root level 0, we see that potential 1-letter words are 
considered in level 1, 2-letter words in level 2 and 3-letter words 
in level 3.  Each potential word is checked against the given 
dictionary.  Potential words found to be actual words are flagged 
with `*', while nodes found to be ``dead ends"---i.e. for which not 
only the current combination of letters is a nonword, but also no 
word in the dictionary begins with that sequence of letters---are marked
with `\&'.  A processor at a given node will first generate all possible
one-letter extensions of the ``word" at that node.  It will add
all but one of them to the task list, and process the remaining
one itself.  Clearly the centralized and decentralized versions
of this algorithm can be handled in analogy to QUAD above.

     The vast majority of applications can be partitioned in
manners similar to those indicated here.


\section{Algorithmic Efficiency of Decentralized Task Allocation}

     As mentioned in Section 1, MVs account for the majority of cache 
invalidation messages in systems with
shared-block caches.  Decentralized task allocation can help solve this
problem, since the number of messages needed for a given invalidation 
is limited to the group size.  If the group size is kept fixed while
the number of processors grows, i.e. in the scalability context, then
CCS becomes less of an issue.

     Decentralized task allocation eliminates most systemwide FAMVs, 
but the question then arises as to whether this can be done efficiently.  
Clearly, there will be {\it some} nonzero loss of efficiency, since a 
processor in one group might lie idle while there is work waiting to be 
assigned in another group.  The question then becomes one concerning the 
{\it degree} of this loss.  This question is investigated in this section, 
in which it is found that the degree of loss is actually quite small.

     The investigation here is two-pronged.  First, in Section 3.1,
a mathematical analysis is described, which shows that decentralized
task allocation can indeed be done efficiently with a fixed group
size, even with arbitrarily large overall system size.  Moreover, we
find that a ``universal" group size exists, information which then
can be incorporated into hardware design.  Then in Section 3.2, this 
efficiency is illustrated concretely by simulating three specific 
applications.  Even more significantly, the simulations can in
addition account for the overhead a processor spends in actually
acquiring a task from a task allocator, and it is found that when
such time is included in the analysis, decentralized allocation is
actually \underline{superior} to centralized allocation.


\subsection{M/M/p Analysis}

     Related questions prompted the investigation in [Ni] (in a
non-CCS context), which modeled a p-processor system as an M/M/p queue.  
In this model, each new task joins a central queue, with tasks from 
the queue being assigned on a first-available-processor basis.  
The main quantity computed, called DLI (``degree of load imbalance"), 
was the probability of having at least one idle processor in some group, 
simultaneously with at least one queued task in some other group.  This 
was appropriate for the fixed number of processors considered in that
paper, but not for our scalability context here, which examines what 
occurs as the number of processors increases.  If the per-processor 
utilization and group size are held constant while the number of 
processors increases (i.e. overall workload increases proportionally 
to the number of processors), DLI will increase to 1.0.  Thus DLI 
is not a useful criterion in our context.

     Instead of DLI, the analysis here uses another criterion, 
mean queuing time (MQT), i.e. the mean time a task waits before it is
started by some processor.\footnote{Actually, this was considered 
somewhat in [Ni] too, but again not from
the point of view taken here.}
Ideally, we would like MQT to be zero.  That is of course unattainable,
but it can be shown that MQT can be kept close to zero without making 
the group size increase with p.  Specifically, let MPT denote the mean
processor time needed for a given task.  Then the analysis yields the 
following:

{\bf Theorem:}

Fix positive values $\epsilon$ and $\delta$.  Then there exists a group 
size $\gamma$ such that if work is allocated on the group level rather
than on the system level, all applications having per-processor utilization 
$\leq  1 - \epsilon$ will have $MQT/MPT < \delta$, no matter how large p is.

     The significance of this is as follows:  We can choose $\epsilon$ small
enough so that most applications are included, and choose $\delta$ small 
enough so that queuing time is an acceptably small proportion of processor 
time per task.  These parameters then give us a ``universal" group size, 
${\gamma}_{univ}$, for which all applications in the given range will run 
efficiently, with decentralization inducing only a negligible increase
in task wait time.
     
     It is a key point that the group size ${\gamma}_{univ}$ is applicable 
no matter how large p is, i.e. no matter how many processors the system 
has.  Partitioning the system into groups of size ${\gamma}_{univ}$ will 
be efficient for any system size.  

     The Theorem is proved in Appendix 1.


\subsection{Simulation Analysis of Some Specific Application Classes}

     The M/M/p queueing model studied in Section 3.1 provides valuable
insight.  However, it does not capture some facets of the behavior 
of some applications, such as the following:
 
\begin{itemize}
\item[(a)]
First, the M/M/p environment is an {\it infinite-horizon} problem, in 
which there is an infinite stream of tasks to process.  This differs 
significantly from {\it finite-horizon} problems, in which a finite 
number of tasks is specified at the outset, because in finite-horizon 
problems, the number of idle processors increases as we near the end of an 
application.  

\item[(b)]
In the M/M/p environment new tasks arrive from outside the system, 
with no relation between tasks.  Yet in many applications there are
dependencies between tasks.  For instance, in the HEAT example in Section 
2, the tasks to be allocated are generated in a feedback-loop manner, 
with the completion of one task typically triggering the readiness of 
another.  

\item[(c)]
The M/M/p analysis does not take into account the overhead involved in
a processor's accessing a task-allocation list.

\item[(d)]
In an M/M/p system, the standard deviation of the task time necessarily
equals the mean.  Thus M/M/p analysis does not allow investigation of
the effect of changing the standard deviation with other factors being
held constant.
\end{itemize}

     For these reasons, three specific application classes, MATMULT,
HEAT and QUAD from Section 2, were simulated, to verify that the 
qualitative implications of Section 3.1---namely, that one can avoid 
having systemwide, i.e. nongrouped, FAMVs without any real performance 
penalty---hold in these settings.  

     Each of the applications was simulated, with task times---the time 
to do one row multiplication, the time to do one quadrature computation 
and comparison, and the time to do one grid iteration---normalized
to have mean 1.  The task time distribution was taken to be Gaussian
(truncated at 0), with standard deviation $\sigma$.  In the first
experiments described here, $\sigma$ was taken to be 0.3, but by varying 
$\sigma$, item (d) listed above could be investigated, as will be seen 
below.  This is also the reason for using the term {\it application class}.  
For example, it allows not only simulation of matrix-multiplication problems,
but also other problems which have similar structure to matrix-multiplication
but which have much different standard deviations.  

     The simulation tool used was {\small CSIM}
a process-oriented simulation environment for use with the C language
[Schwetman].  Each processor was represented by one {\small CSIM} 
process.  For each setting, 1000 replications were run, e.g. 1000
matrix multiplications for each combination of parameter values
considered.

     The results of these simulations are presented in Tables 1-9.
Note that the cases in which $\gamma$ = p represent centralized task
allocation, while the others are decentralized.  The parameter r
represents the problem size:  the number of rows in MATMULT, the
number of grid points in HEAT, and the number of initial subintervals
in QUAD.

     The simulations did confirm the findings of Section 3.2.  For example, 
consider the instance of MATMULT shown in Table 1.  The performance penalty 
was almost zero for $\gamma$ = 16, and was only about 2\% for the very small 
group size $\gamma$ = 8.\footnote{In the MATMULT simulations presented here, 
the parameter K was taken to be equal to $\gamma$.}

     Similarly, the experiments with QUAD yielded the results shown in
Table 2.  Again we see only a minor loss of efficiency due to using 
decentralized task allocation, even with very small group sizes.  The 
results for HEAT, in Table 3, were again similar.

     Table 4 shows the results from running MATMULT again, on a larger
system.  Again, a group size of 16 seems quite sufficient.

     Thus the simulations, dealing with real applications, do confirm
the findings of Section 2.  Much more significantly, the simulations
allow us to introduce another element of realism which was missing in
Section 2, concerning $\omega$, the time cost involved when a processor 
accesses a task list.  This time is manifested not only in the direct 
cost to the processor, but also indirectly in that a processor may need 
to spend time queuing behind other processors which are accessing the 
task list.

     To investigate this, the simulations were rerun, with $\omega$ equal
to 0.02 (recall that the mean task time is 1.00).  Tables 1-4 then become 
Tables 5-8.  Note that the effect of nonzero $\omega$ for large systems 
is especially prominent (Table 8).  Using centralized task allocation 
results in an increase in completion time by a factor of approximately 
5, a severe penalty.  The effect is larger in this case because of the
smaller coefficient of variation (see below), since the processors
will tend to finish tasks at bunched-together times and thus contend
with each other more when accessing task lists.

     In other words, decentralized task allocation is not only {\it as
efficient as} centralized allocation in terms of processor utilization,
but is actually {\it better than} centralized allocation, since it greatly 
reduces the overhead due to processor queuing for task lists.  

     As mentioned in item (d) at the beginning of this section,
the effect of varying $\sigma$ was also investigated.  Recall that the
results presented above had $\sigma$ = 0.3.  This actually was a rather
large value, for typical applications (see Appendix 2).
In other words, the value $\sigma$ = 0.3 used in the simulations
above is actually rather conservative, since typical values of $\sigma$
are smaller than this.  The term ``conservative" here stems from the
fact that the results are even stronger for smaller values of $\sigma$,
which produce smaller oscillations and thus a lower probability that
a processor in one group will lie idle while work is waiting in another
group.  For example, the analog of Table 1 for $\sigma$ = 0.05 is Table
9, which shows there is no penalty at all (to two significant figures) 
for using decentralized task allocation.


\section{Architectural Implications}

     The results of Section 3 indicate that applications of shared-memory
multiprocessors generally do not need systemwide FAMVs, because such 
variables can usually be eliminated through the use of decentralized task
allocation.  This section will discuss implications of this finding for 
CCS (an implication to a non-CCS issue arising in shared-memory
multiprocessor systems is outlined in Appendix 3). 
Some comments on previously-proposed systems will be made, and a new
type of architecture will be proposed as well.


\subsection{Implications for CCS Architectures}

     In this section, some implications of the results in Section 3
will be given for three specific CCS systems, those in DASH [Lenoski]
[Gupta], ALEWIFE [Chaiken91] and SCI [James].  The discussion here of
these systems is intended to only be illustrative, not comprehensive; 
it is believed that the results of Section 3 have relevance to them 
in a variety of other ways in addition to those given as examples here.  

     In general, the theme here is that due to the findings in Section 3 
concerning task-allocation variables---variables which, it should be 
emphasized again, account for the majority of invalidation messages---the 
need for attaining good CCS is much less than had been thought
previously.  This then translates into reduced hardware requirements, 
possible changes in hardware, and in different software approaches.

     First, the findings here, indicating that task allocation can be 
done efficiently on a \underline{group}
rather than a centralized basis, may be viewed as providing theoretical 
and empirical justification for the version of DASH described in 
[Lenoski], which has hardware support for processor clusters.  

     Similarly, these findings provide a new justification for various 
limited-directory schemes such as LimitLESS in ALEWIFE.  These schemes 
have up to now been justified by data which indicate that, during
the course of execution of a given application, the number of
processors contending for a given MV will usually be small.  The
point of view which has been taken is that although there will 
occasionally be exceptional cases, in which rather substantial
time penalties will be incurred, this will hopefully occur rarely
enough so that those penalties do not greatly affect overall
performance.  By contrast, the results of Section 3 show that instead
of just {\it hoping} that such occurrences will be rare, we can actually
{\it guarantee} it in the case of task-allocation MVs.

     For SCI, it was mentioned in Section 1 that the slow propagation
of an invalidation message along a linear linked list---a delay which
tends to become worse as the system size scales upward---has motivated
SCI developers to consider more complex, treelike linking structures, 
employing redundant pointers to send several copies of an invalidation 
message in parallel.  But again, using decentralized task allocation as 
shown here, we can limit the length of the SCI linked lists to a fixed 
constant, independent of the system size p.  For this limited length,
a linear linked list 
may be sufficiently efficient after all, and the addition of redundant 
pointers could be avoided, thus avoiding a substantial increase in 
hardware complexity.

     Similarly, in both DASH and ALEWIFE, one concern is that many cache 
invalidation messages may have to travel to remote portions of the 
network.  In DASH, for example, an invalidation transaction may involve 
three different portions of the network, the original {\it local cluster}, 
the {\it home cluster} and the {\it remote cluster}.  But the results of 
Section 3 show that this is much less of a concern than originally 
thought, since one can guarantee that invalidation messages involving 
task-allocation MVs can be confined to small 
groups of processors, with group size independent of overall system 
size p.  {\it In other words, as the system size grows, the network distance 
traveled by the majority of the invalidation messages can be kept bounded 
by a fixed constant, independent of p, so CCS is much less of an issue.}  
A related implication of this is that network topology in such systems 
might be designed to optimize intragroup communication (possibly as in
[Lenoski]), even at the expense of some deterioration of intergroup 
communication performance.

     Another possibility is the elimination of the lock queues in DASH.
Again, most lock variables can be handled on the group level, thus
confining traffic involving them to a small region of the network---not
only small, but again also of a fixed size, not growing with p.  Thus the
lock queues may be of limited usefulness for CCS, and thus might be
eliminated, with a substantial savings in hardware complexity.


\section{A New Class of Shared-Memory Multiprocessor Architecture}

     One can take this last idea, i.e. the possible elimination of
DASH's lock queues mentioned at the end of Section 4.1, one step further:
One might consider eliminating \underline{all}
hardware devoted to CCS.  In DASH, for example, there is a large
amount of such hardware; the directories, for example, have complexity
O($p ^ 2$).  In this regard, consider a concept of
{\it locally coherent shared-memory architectures} (LCSMA), which we 
define to mean shared-memory multiprocessor systems which provide 
hardware support for cache coherency within groups of processors, but 
provide no hardware support for systemwide cache coherency.\footnote{Note 
that ALEWIFE is not an LCSMA machine, since it too has hardware
which is indirectly used for systemwide cache coherency.  The cache 
directory must include logic to detect overflow and to relinquish 
cache control to the processor; the directory and the processor must 
be designed so that the processor can actively access the directory; 
the processor must be designed so as to have very fast trap-handling 
capability; etc.}  

     Under LCSMA the software must, where possible, avoid creation of 
systemwide MVs.  Section 2 indicated a general approach by which this 
can be done, creating group task-allocation variables.  Atomic access
to these variables, and the problem of contention for them, are handled
via hardware, i.e. cache coherency for the latter and mechanisms such
as test-and-set instructions for the former.  Any MVs which remain, e.g. 
those involved in barrier variables, are handled in software.  Some
details are given in Appendix 4.

     The motivation for LCSMA is that while on the one hand hardware is 
needed for efficient access of FAMVs, on the other hand FAMVs can be
limited to groups of processors, and therefore it makes sense to limit
hardware support for cache coherency to intragroup coherency.  The
question of CCS then becomes moot.  This would result in a machine
which is low-cost in terms of hardware, and yet efficient in terms
of task allocation.

     As shown in Section 2, the burden on the applications programmer 
to set up decentralized task allocation is quite minimal.  Only a 
few lines of code need to be changed, and the programmer would not need
to be aware of the underlying architecure; a single, shared address
space standard to shared-memory machines is all that is assumed, and
the caches are transparent to the programmer.

     Another point concerns non-MV shared variables (NMVSVs), e.g. 
the matrix itself in the LU application in Section 2.  A variety of 
approaches are possible.  The simplest solution is to just mark all 
NMVSVs as noncacheable (i.e., mark only group task-allocation structures
as cacheable).  This would not be the most aggressive approach in terms 
of performance, but it would be easiest, and again due to the fact that 
FAMVs form the primary bottleneck on current systems, good performance 
should be attainable.  Alternatively, caching of NMVSVs in an LCSMA 
system could be done automatically by the compiler [Cheong] [Adve].

     LCSMA denotes a broad class of architectures, with many possible 
implementations.  For example, an interconnect structure such as that 
of Figure 2 could be used.  (For the purposes of readability, this figure 
depicts a very small system, with an unrealistically small value of 4 
for ${\gamma}_{univ}$.)  Here processors are connected to memory modules 
via the familiar delta network [Almasi] [Hwang].  What is different is 
that processors are partitioned into groups, and processors within any 
given group are connected via snooping caches [Goodman] and a local bus.
These provide hardware support for local MVs, i.e. variables which are 
shared only by processors within a given group.  Let us introduce one final 
acronym, using LSSMA (``locally-snooping shared-memory architecture") 
to refer to the approach proposed in Figure 1.\footnote{In this sense 
it has some commonality with [Lenoski], but again it
should be noted that the latter is not LSSMA; it is not even an LCSMA 
machine.  A cache invalidation in the machine in [Lenoski] can, and 
often does, result in invalidation messages being sent to processors 
outside the cluster where the invalidation occurred.  In other words,
the hardware does enforce systemwide cache coherency, which is a
fundamental point of departure for LCSMA.}

     The results of Section 3 indicate that a group size of perhaps 
16 will be effective (see Section 5).  This would be nice, since bus 
snooping has been found to work well in this range.  On the other hand, 
even if a larger value of ${\gamma}_{univ}$ turns out to be necessary, 
many other implementations of LCSMA are possible, including adapting
some recently proposed architectures to the LCSMA philosophy.  For
example, a very good implementation may be an LCSMA version of the 
DASH project, with the interconnection network topology again placing
extra interconnection bandwidth within groups of ${\gamma}_{univ}$ 
nodes, but all hardware support for systemwide coherency eliminated.
Another possible implementation of LCSMA would be to adapt SCI, 
making the size of its linked lists limited to ${\gamma}_{univ}$, 
and either retaining the linear structure (see Section 4.1), or
optimizing a tree-based mechanism for the fixed-length lists.
In any case, the main point is that once ${\gamma}_{univ}$ is 
determined, we avoid having to implement cache coherency on an 
ever-widening scale as p increases.


\section{Discussion}

     Although the work here has presented evidence that a reasonable 
value of ${\gamma}_{univ}$ can be chosen, it has not specifically 
identified such a value.  We could use the results of Section 3.1 
to help choose the value, but since Equation (5) in Appendix 1
was derived from 
inequalities, the value obtained would be too conservative.  The 
results in Section 3.2 are more valuable in this regard, and as 
mentioned earlier, indicate that a group size of perhaps 16 will 
be effective.  This should be verified by investigating other 
applications, but it is anticipated that this value will continue 
to hold up well in them, given the ``universality" nature of the 
findings of Section 3.1, the close similarity of the three sets of 
results in Section 3.2, and the remark at the end of Section 2
concerning the similarity of most applications to one of the ones
considered here.

     There are of course {\it some} applications in which systemwide,
i.e. nongrouped, FAMVs arise, such as synchronous algorithms with 
very short times between successive synchronizations.  For instance, 
considering a root-finding problem.  Suppose it is known that the 
function f has a root in the interval (a,b), where f(a) < 0, f(b) > 0 
and f is monotonic increasing.  A parallel-processing attack on this 
problem might be as follows:  At the i-th iteration, we consider the
interval $( a_i , b_i )$, where $a_0 = a$ and  $b_0 = b$.
Within the interval, p evenly spaced points are defined, and the p processors
evaluate f at these points.  Then $a_{i+1}$ and $b_{i+1}$ are defined
to be the largest of these points at which f is negative and the smallest
at which f is positive, respectively.  

     In this setting the processors must synchronize at the end of each
iteration i, at which time they wait for the announcement of $a_{i+1}$
and $b_{i+1}$.  The latter two values (and the barrier variable used
to set them) are then associated with systemwide MVs.  Furthermore, if 
the evaluation of function f is not time-consuming,\footnote{It 
\underline{would} be time-consuming if, say, f were the value
of an integral which itself must be evaluated numerically.}
these MVs are then FAMVs, and it would be nice to have hardware support 
to aid in their access.  

     However, it is clear that cached-based approaches are not good solutions
to this problem either.  The overhead due to relaying of cache update 
messages throughout an entire large system would be too heavy.  Thus other 
mechanisms would be needed if this type of application were to be targeted, 
say adding a separate broadcast channel to Figure 2 for announcing 
$a_{i+1}$ and $b_{i+1}$.  The point here is that this and similar examples do 
not counter this paper's theme concerning a reduced role for CCS as an 
architectural design criterion shared-memory multiprocessors. 

     In any case, the goal here has not been to propose machines which
are optimal for all applications, which is impossible.  Instead, the 
point has been that {\it most} applications of shared-memory multiprocessors 
can be done efficiently without systemwide FAMVs, and that this has
strong implications, positive and negative, for the various CCS schemes
which have been proposed.  

\bigskip

{\bf Bibliography}

S. Adve, V. Adve, M. Hill, M. Vernon.  ``Comparison of Hardware and
Software Cache Coherency Schemes,"
{\it Proceedings of the 18th Annual International Symposium on Computer
Architecture}, 1991, 298-308.

A. Agarwal and M. Cherian.  ``Adaptive Backoff Synchronization
Techniques,"
{\it Proceedings of the 16th Annual International Symposium on Computer
Architecture}, 1989, 396-406.

G. Almasi and A. Gottlieb.  {\it Highly Parallel Computing}, Benjamin
Cummings, 1989.

J. Boyle, R. Butler, T. Disz, B. Glickfield, E. Lusk, R. Overbeek,
J. Patterson and R. Stevens.  {\it Portable Programs for Parallel
Processors}, 1987, Holt, Rinehart \& Winston.

D. Chaiken, J. Kubiatowicz and A. Agarwal.  ``LimitLESS Directories:
A Scalable Cache Coherence Scheme," {\it Proceedings of the Fourth
International ASPLOS Conference}, 1991, 224-234.

H. Cheong and A. Veidenbaum.  ``Compiler-Directed Cache Management
in Multiprocessors," 
{\it Computer}, June 1990, 39-48.

G. Gonnet.  {\it Handbook of Algorithms and Data Structures}, Addison-Wesley,
1984.

J. Goodman.  ``Using Cache Memory to Reduce Processor-Memory Traffic,"
{\it Proceedings of the 10th Annual Symposium on Computer Architecture},
1983, 124-131.

A. Gupta, J. Hennessy, K. Gharachorloo and T. Mowry.  ``Comparative
Evaluation of Latency Reducing and Tolerating Techniques,"
{\it Proceedings of the 18th Annual International Symposium on Computer
Architecture}, 1991, 254-263.

K. Hwang and F. Briggs.  {\it Computer Architecture and Parallel
Processing}, 1984.

Intel.  {\it Microprocessor and Peripheral Handbook}, 1988.

D. James, A. Laundrie, S. Gjessing and G. Sohi.  ``Scalable
Coherent Interface," {\it Computer}, June 1990, 74-77.

C. Kruskal and A. Weiss.  ``Allocating Independent Subtasks
on Parallel Processors," {\it IEEE Transactions on Software
Engineering}, SE-11 (10), 1001-1016, 1985.

D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta and J. Hennessy.
``The Directory-Based Cache Coherence Protocol for the DASH
Multiprocessor," 
{\it Proceedings of the 17th Annual International Symposium on Computer
Architecture}, 1990, 148-158.

L. Ni and C.-F. Wu.  ``Design Tradeoffs for Process Scheduling
in Shared Memory Multiprocessor Systems," {\it IEEE Transactions
on Software Engineering}, 15, 1989, 327-334.

G. Pfister and V.A. Norton.  ``Hot Spot Contention and Combining
in Multistage Interconnection Networks," {\it IEEE Transactions on
Computers}, C-34, 1985, 943-948.

H. Schwetman.  {\it CSIM Reference Manual}, Microelectronics and 
Computer Technology, Technical Report ACA-ST-257-87 Rev. 14, 1990.

P. Stenstrom.  ``A Survey of Cache Coherency Schemes for Multiprocessors,"
{\it Computer}, June 1990, 12-24.

K. Trivedi.  {\it Probability \& Statistics, With Reliability,
Queuing and Computer Science Applications}, Prentice-Hall, 1982.

P.-C. Yew, N.-F. Tzeng and D. Lawrie.  ``Distributing Hot-Spot
Addressing in Large-Scale Multiprocessors," {\it IEEE Transactions
on Computers}, C-36, 1987, 388-395.


\newpage
\appendix

\section{Derivation of the Theorem}

     To derive the Theorem in Section 3.1, consider multiprocessor 
systems 1 and 2, which use centralized and decentralized task allocation, 
respectively.  Each has Poisson task arrivals with rate $\lambda$, 
whose service times are exponentially distributed with mean 1/$\mu$.  
Each system consists of p = $q \gamma$ processors.  However, the two 
systems differ in the manner in which processors acquire tasks:  System 
1 has one global queue; when a processor finishes a task, it gets its 
new task from the head of this queue.  In system 2, an arriving task 
is randomly assigned to one of q queues, each of which serves a group 
of $\gamma$ processors; processors in a group take tasks only from the 
queue for that group.  

     Consider the classical M/M/k queue [Trivedi], in which there are:  
Poisson arrivals with rate $alpha$; exponential service times with mean 
1/$\beta$; and k servers.  System 1 above is such a queue, with $alpha$ = 
$\lambda$, $\beta$ = $\mu$ and k = $q \gamma$, while each individual 
{\it group}
in system 2 is such a queue, with $alpha$ = $\lambda$/$q$, $\beta$ = $\mu$
and k = $\gamma$.  The mean time spent by tasks waiting in this M/M/k 
queue, not including the service time, is 
\begin{equation}
E(Q) = p_0 \frac{{(uk)}^{k-1} u} {k! \beta {(1-u)} ^ 2} ,
\end{equation}
where the per-server utilization is u = $\alpha$/(k $\beta$) and the 
probability that the system is empty is
\begin{equation}
p_0 = \frac{1}
{\sum_{i=0}^{k-1} \frac{{(uk)}^i}{i!} +
\frac{{(ku)}^k}{k! (1-u)} }
\end{equation}

     Let us consider the scalability question in this context, by 
comparing systems 1 and 2.  First note that the value of u is the 
same for the two systems.  The effect on E(Q) as k increases will
be investigated, while holding u fixed.  In other words, as k increases, 
the overall workload is also increased proportionally, with the result 
being that the demand on each processor remains constant.

     Note that for large k, the value of (2) is approximately 
$e^{-ku}$.  An approximate value is obtained for (1) using
Stirling's approximation for factorials,
\[ n! \approx \sqrt{2 \pi} e^{-n} n ^ {n + \frac{1}{2}} . \]
From all this, (1) has the approximate value
\begin{equation}
e^{-ku}
\frac
{k^{k-1}u ^ k} 
{ \beta \sqrt{2 \pi} e^{-k}k ^ {k + \frac{1}{2}}  {(1-u)} ^ 2} 
=
\frac{1}{\beta }
\frac
{ {( u e^{1-u})} ^ k } 
{ \sqrt {2 \pi} k ^ {\frac{3}{2}} {(1-u)} ^ 2 }
\end{equation}

     Since $0 \leq u \leq 1$, the maximum value of 
${( u e^{1-u})} ^ k$ is 1.  Thus an approximate upper bound 
for E(Q) is
\begin{equation}
\frac{1}{\beta}
\frac{1}{\sqrt{2\pi} k^{\frac{3}{2}}  {(1-u)} ^ 2 } .
\end{equation}
Moreover, since the mean service time is $1 / \beta$, we see that an 
approximate upper bound for E(Q) as a proportion of mean service time is
\begin{equation}
\frac{1}{\sqrt{2\pi} k^{\frac{3}{2}} {(1-u)} ^ 2 } .
\end{equation}
For fixed u, the expression (5) converges to 0 as $k \rightarrow \infty$.

     Thus, in both systems 1 and 2, as the group size---$q \gamma$ for 
system 1, $\gamma$ for system 2---goes to infinity, the mean queue wait 
goes to zero.  In other words, for large group size, both systems 1 
and 2 approach full efficiency, and thus the efficiency lost by using 
system 2 instead of system 1 is small.  As long as the group size $\gamma$
in system 2 is sufficiently large, there is essentially no penalty for 
using system 2 instead of system 1.

     Even more importantly, note that in (5), if u bounded away from 1, 
i.e. for all u in the range $0 \leq u \leq U$ for any fixed $U < 1$, the
convergence to 0 is uniform in u.  In other words, in order to have (5) 
get below a certain desired value, say 0.05, the same value of $\gamma$, 
say $\gamma$, will work for all values of u in the range $0 \leq u \leq U$.  
Since it is rare for an application to achieve a value of u above, 
say 0.9, we can choose the group size $\gamma$ accordingly.  Then system 
2---i.e. decentralized task allocation with fixed group size $\gamma$---will 
work well for the vast majority of applications, even on systems of
arbitrarily large size.


\section{Effect of $\sigma$}

     In Section 3.2 it was mentioned that the value $\sigma$ = 0.3 used
in most of the simulations there was actually rather large, for typical
applications.  This point is discussed in this Appendix.

     For example, consider MATMULT.
The multiplication of one r x 1 row involves r multiply/add operations.
The time taken by each such operation is a random variable, with mean $Nu$ 
and standard deviation $rho$.  Their sum has mean $r Nu$, and, making the 
reasonable assumption that the r variables are statistically independent, 
the standard deviation would be $sqrt r rho$.  The coefficient of variation, 
i.e. the ratio of the standard deviation to the mean, for one row 
multiplication would then be O($\frac{1}{\sqrt{r}}$), and thus would
be very small for large r.

     Taking for instance the 80387 mathematics coprocessor, the number 
of clock cycles for a floating-point multiply is in the range 27-35, 
while for a floating-point add the figure is 24-32 [Intel].  Thus a 
multiply/add will take between 51 and 67 cycles, which would imply
a value for $rho$ of at most 8.  Suppose the mean $Nu$ is the midpoint
of this range, 59, and r is, say, 500.  Then the coefficient of variation
for a row multiplication would be at most 0.006.  Recalling that in the 
simulations the mean was scaled to 1.0, that would correspond to a value 
for $\sigma$ of 0.006, orders of magnitude smaller than the value 
$\sigma$ = 0.3 used earlier.

     A similar analysis can be made for many other applications.  For
example, consider Heapsort, for sorting r items.  Many parallel sort
algorithms are based on parceling out subarrays to the individual
processors, with each processor then performing a sequential sort,
e.g. a Heapsort, on its subarray.  The mean running time of Heapsort
is O(r log r), while the standard deviation is O($\sqrt r$) [Gonnet].
Again, the larger the problem, the smaller the coefficient of variation,
in this case O($\frac{1}{\sqrt{r}log r}$).


\section{Application to the Hot Spot Problem}

     Though not the subject of this paper, it should be mentioned that 
the findings of Section 3 also have implications to other issues in 
shared-memory multiprocessor design, such as the problem of {\it tree 
saturation} [Pfister] (though this is one of the motivations for
the CCS question, it is of broader importance than this).  Here, a 
number of processors might be simultaneously trying to enter a critical 
section guarded by an MV, in which case the MV, and the memory module 
in which it resides, become a {\it hot spot}.  The resulting backup 
can affect the entire network, including paths leading to other modules.  
A hardware-intensive method to handle tree saturation has been proposed,
in the form of combining networks [Almasi], but decentralized task 
allocation can reduce this bottleneck without requiring special hardware.

     Just as LCSMA obviates the need for CCS by placing a system
size-independent bound on the number of messages stemming from a given
block invalidation, decentralized task allocation can be used to solve 
the hot-spot problem in a manner independent of system size.  In the
analysis in [Pfister], the maximum memory bandwidth per processor is
given by
\begin{equation}
\frac{1}{1 + h(p-1)} ,
\end{equation}
for a system with p processors, p memory modules, assuming traffic
which is uniform across modules, except that the module containing
the MV has a proportion h of extra traffic.  This expression goes to
zero as p goes to $inf$, a real scalability problem.

     By contrast, with decentralized task allocation, the MV would be 
replaced by a separate MV for each group, giving a maximum bandwidth of
\begin{equation}
\frac{1}{1 + h( {\gamma}_{univ} - 1 )} ,
\end{equation}
which is independent of p.


\section{Software Alternatives}

     As stated in Section 4, LCSMA defines a class of architectures,
rather than a specific architecture, and thus can potentially be
realized in many different implementations.  This Appendix presents 
a brief outline of two implementations of the software-based atomic 
access to systemwide MVs referred to in Section 4. 

     One possibility is to employ the methods in [Yew], which use
software to combine the atomic-access requests of several processors 
to a given MV, in a tree-like manner.  The root nodes of such trees
consist of the memory modules.  There is atomic-access hardware in
the latter, but in a completely scalable manner, since the amount
of such hardware in any particular module remains constant as the
number of processors (and/or memory modules) grows.

     Another possibility, involving no special hardware at all, 
is the following.  Say we have a critical section C, which would in a 
conventional system be protected via hardware by some lock variable L.  
We could accomplish this in software in LCSMA by replacing this scalar 
L by an array, with L[i] being associated with processor Pi.  One of 
the processors, say P0, would be dedicated to periodically scanning 
the L array.  When Pi reaches C and wishes to enter C, Pi sets L[i] 
to 1.  Suppose at that time processor Pr is occupying C.  When Pr 
exits C, it will set L[r] to 0.  P0, upon seeing that action, will 
scan the L array, looking for a processor whose component of L is 
equal to 1.  P0 will handle all such processors in turn; when Pi's 
turn comes, P0 will then set L[i] to 2, indicating that Pi can now 
enter C.  Meanwhile, Pi has been watching for this, and will then go 
ahead and enter C.

     Both of these implementations are simple ones.  There are a number
of refinements that could be made to improve their efficiency, but since
they would primarily be used on RAMVs, refinements would be of only
secondary importance.

     A number of system calls should be developed to make these
operations easy for the programmer.  The calls GetGroupNumber() and
GetPaddingSize() have already been mentioned.  There should also be
calls like AcquireLock(), in two forms:  The first controls hardware,
e.g. includes something like a test-and-set instruction, while the
second implements a software lock-acquire operation, as outlined
above.

\newpage
\twocolumn

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
128 & 32 & 32 & 4.81 \\ \hline
128 & 32 & 16 & 4.85 \\ \hline
128 & 32 & 8 & 4.91 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 1

\vspace{0.5in}
 

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
64 & 64 & 64 & 5.09 \\ \hline
64 & 64 & 32 & 5.15 \\ \hline
64 & 64 & 16 & 5.11 \\ \hline
64 & 64 & 8 & 5.13 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 2

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
128 & 64 & 64 & 11.19 \\ \hline
128 & 64 & 32 & 11.12 \\ \hline
128 & 64 & 16 & 11.18 \\ \hline
128 & 64 & 8 & 11.26 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 3

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
1024 & 512 & 512 & 3.11 \\ \hline
1024 & 512 & 256 & 3.10 \\ \hline
1024 & 512 & 128 & 3.09 \\ \hline
1024 & 512 & 64 & 3.10 \\ \hline
1024 & 512 & 32 & 3.11 \\ \hline
1024 & 512 & 16 & 3.13 \\ \hline
1024 & 512 & 8 & 3.18 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 4

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
128 & 32 & 32 & 7.44 \\ \hline
128 & 32 & 16 & 5.48 \\ \hline
128 & 32 & 8 & 5.34 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 5

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
64 & 64 & 64 & 5.87 \\ \hline
64 & 64 & 32 & 5.48 \\ \hline
64 & 64 & 16 & 5.32 \\ \hline
64 & 64 & 8 & 5.22 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 6

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
128 & 64 & 64 & 14.70 \\ \hline
128 & 64 & 32 & 11.84 \\ \hline
128 & 64 & 16 & 11.61 \\ \hline
128 & 64 & 8 & 11.61 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 7

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
1024 & 512 & 512 & 21.91 \\ \hline
1024 & 512 & 256 & 11.33 \\ \hline
1024 & 512 & 128 & 6.19 \\ \hline
1024 & 512 & 64 & 3.78 \\ \hline
1024 & 512 & 32 & 3.48 \\ \hline
1024 & 512 & 16 & 3.70 \\ \hline
1024 & 512 & 8 & 4.43 \\ \hline
\end{tabular}

\bigskip

\hspace{0.5in} Table 8

\vspace{0.5in}

\begin{tabular}{| l | l | l | l |} \hline
r & p & $\gamma$ & mean time \\ \hline
128 & 32 & 32 & 4.22 \\ \hline
128 & 32 & 16 & 4.22 \\ \hline
128 & 32 & 8 & 4.22 \\ \hline
\end{tabular}


\hspace{0.5in} Table 9

\bigskip

\onecolumn


% Figure 1 starts here:
\expandafter\ifx\csname graph\endcsname\relax \csname newbox\endcsname\graph\fi
\expandafter\ifx\csname graphtemp\endcsname\relax \csname newdimen\endcsname\graphtemp\fi
\setbox\graph=\vtop{\vskip 0pt\hbox{%
    \special{pn 8}%
    \special{pa 2550 350}%
    \special{pa 3000 350}%
    \special{pa 3000 0}%
    \special{pa 2550 0}%
    \special{pa 2550 350}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.175in
    \rlap{\kern 2.775in\lower\graphtemp\hbox to 0pt{\hss root\hss}}%
    \special{pa 400 1250}%
    \special{pa 850 1250}%
    \special{pa 850 900}%
    \special{pa 400 900}%
    \special{pa 400 1250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.075in
    \rlap{\kern 0.625in\lower\graphtemp\hbox to 0pt{\hss o\hss}}%
    \special{pa 2550 1250}%
    \special{pa 3000 1250}%
    \special{pa 3000 900}%
    \special{pa 2550 900}%
    \special{pa 2550 1250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.075in
    \rlap{\kern 2.775in\lower\graphtemp\hbox to 0pt{\hss n\hss}}%
    \special{pa 4700 1250}%
    \special{pa 5150 1250}%
    \special{pa 5150 900}%
    \special{pa 4700 900}%
    \special{pa 4700 1250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.075in
    \rlap{\kern 4.925in\lower\graphtemp\hbox to 0pt{\hss w\hss}}%
    \special{pa 0 2150}%
    \special{pa 450 2150}%
    \special{pa 450 1800}%
    \special{pa 0 1800}%
    \special{pa 0 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 0.225in\lower\graphtemp\hbox to 0pt{\hss on*\hss}}%
    \special{pa 800 2150}%
    \special{pa 1250 2150}%
    \special{pa 1250 1800}%
    \special{pa 800 1800}%
    \special{pa 800 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 1.025in\lower\graphtemp\hbox to 0pt{\hss ow\hss}}%
    \special{pa 2150 2150}%
    \special{pa 2600 2150}%
    \special{pa 2600 1800}%
    \special{pa 2150 1800}%
    \special{pa 2150 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 2.375in\lower\graphtemp\hbox to 0pt{\hss no*\hss}}%
    \special{pa 2950 2150}%
    \special{pa 3400 2150}%
    \special{pa 3400 1800}%
    \special{pa 2950 1800}%
    \special{pa 2950 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 3.175in\lower\graphtemp\hbox to 0pt{\hss nw\&\hss}}%
    \special{pa 4300 2150}%
    \special{pa 4750 2150}%
    \special{pa 4750 1800}%
    \special{pa 4300 1800}%
    \special{pa 4300 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 4.525in\lower\graphtemp\hbox to 0pt{\hss wo\hss}}%
    \special{pa 5100 2150}%
    \special{pa 5550 2150}%
    \special{pa 5550 1800}%
    \special{pa 5100 1800}%
    \special{pa 5100 2150}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 1.975in
    \rlap{\kern 5.325in\lower\graphtemp\hbox to 0pt{\hss wn\&\hss}}%
    \special{pa 0 3050}%
    \special{pa 450 3050}%
    \special{pa 450 2700}%
    \special{pa 0 2700}%
    \special{pa 0 3050}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.875in
    \rlap{\kern 0.225in\lower\graphtemp\hbox to 0pt{\hss onw\hss}}%
    \special{pa 800 3050}%
    \special{pa 1250 3050}%
    \special{pa 1250 2700}%
    \special{pa 800 2700}%
    \special{pa 800 3050}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.875in
    \rlap{\kern 1.025in\lower\graphtemp\hbox to 0pt{\hss own*\hss}}%
    \special{pa 2150 3050}%
    \special{pa 2600 3050}%
    \special{pa 2600 2700}%
    \special{pa 2150 2700}%
    \special{pa 2150 3050}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.875in
    \rlap{\kern 2.375in\lower\graphtemp\hbox to 0pt{\hss now\hss}}%
    \special{pa 4300 3050}%
    \special{pa 4750 3050}%
    \special{pa 4750 2700}%
    \special{pa 4300 2700}%
    \special{pa 4300 3050}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.875in
    \rlap{\kern 4.525in\lower\graphtemp\hbox to 0pt{\hss won*\hss}}%
    \special{pa 2775 350}%
    \special{pa 625 900}%
    \special{fp}%
    \special{pa 2775 350}%
    \special{pa 2775 900}%
    \special{fp}%
    \special{pa 2775 350}%
    \special{pa 4925 900}%
    \special{fp}%
    \special{pa 625 1250}%
    \special{pa 225 1800}%
    \special{fp}%
    \special{pa 625 1250}%
    \special{pa 1025 1800}%
    \special{fp}%
    \special{pa 2775 1250}%
    \special{pa 2375 1800}%
    \special{fp}%
    \special{pa 2775 1250}%
    \special{pa 3175 1800}%
    \special{fp}%
    \special{pa 4925 1250}%
    \special{pa 4525 1800}%
    \special{fp}%
    \special{pa 4925 1250}%
    \special{pa 5325 1800}%
    \special{fp}%
    \special{pa 225 2150}%
    \special{pa 225 2700}%
    \special{fp}%
    \special{pa 1025 2150}%
    \special{pa 1025 2700}%
    \special{fp}%
    \special{pa 2375 2150}%
    \special{pa 2375 2700}%
    \special{fp}%
    \special{pa 4525 2150}%
    \special{pa 4525 2700}%
    \special{fp}%
    \hbox{\vrule depth3.050in width0pt height 0pt}%
    \kern 5.550in
  }%
}%
\centerline{\box\graph}

\hspace{2.5in} Figure 1


% Figure 2 starts here:
\expandafter\ifx\csname graph\endcsname\relax \csname newbox\endcsname\graph\fi
\expandafter\ifx\csname graphtemp\endcsname\relax \csname newdimen\endcsname\graphtemp\fi
\setbox\graph=\vtop{\vskip 0pt\hbox{%
    \special{pn 8}%
    \special{pa 0 2250}%
    \special{pa 250 2250}%
    \special{pa 250 2000}%
    \special{pa 0 2000}%
    \special{pa 0 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 0.125in\lower\graphtemp\hbox to 0pt{\hss C0\hss}}%
    \special{pa 700 2250}%
    \special{pa 950 2250}%
    \special{pa 950 2000}%
    \special{pa 700 2000}%
    \special{pa 700 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 0.825in\lower\graphtemp\hbox to 0pt{\hss C1\hss}}%
    \special{pa 1400 2250}%
    \special{pa 1650 2250}%
    \special{pa 1650 2000}%
    \special{pa 1400 2000}%
    \special{pa 1400 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 1.525in\lower\graphtemp\hbox to 0pt{\hss C2\hss}}%
    \special{pa 2100 2250}%
    \special{pa 2350 2250}%
    \special{pa 2350 2000}%
    \special{pa 2100 2000}%
    \special{pa 2100 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 2.225in\lower\graphtemp\hbox to 0pt{\hss C3\hss}}%
    \special{pa 2800 2250}%
    \special{pa 3050 2250}%
    \special{pa 3050 2000}%
    \special{pa 2800 2000}%
    \special{pa 2800 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 2.925in\lower\graphtemp\hbox to 0pt{\hss C4\hss}}%
    \special{pa 3500 2250}%
    \special{pa 3750 2250}%
    \special{pa 3750 2000}%
    \special{pa 3500 2000}%
    \special{pa 3500 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 3.625in\lower\graphtemp\hbox to 0pt{\hss C5\hss}}%
    \special{pa 4200 2250}%
    \special{pa 4450 2250}%
    \special{pa 4450 2000}%
    \special{pa 4200 2000}%
    \special{pa 4200 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 4.325in\lower\graphtemp\hbox to 0pt{\hss C6\hss}}%
    \special{pa 4900 2250}%
    \special{pa 5150 2250}%
    \special{pa 5150 2000}%
    \special{pa 4900 2000}%
    \special{pa 4900 2250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.125in
    \rlap{\kern 5.025in\lower\graphtemp\hbox to 0pt{\hss C7\hss}}%
    \special{pa 350 1750}%
    \special{pa 600 1750}%
    \special{pa 600 1500}%
    \special{pa 350 1500}%
    \special{pa 350 1750}%
    \special{fp}%
    \special{pa 1750 1750}%
    \special{pa 2000 1750}%
    \special{pa 2000 1500}%
    \special{pa 1750 1500}%
    \special{pa 1750 1750}%
    \special{fp}%
    \special{pa 3150 1750}%
    \special{pa 3400 1750}%
    \special{pa 3400 1500}%
    \special{pa 3150 1500}%
    \special{pa 3150 1750}%
    \special{fp}%
    \special{pa 4550 1750}%
    \special{pa 4800 1750}%
    \special{pa 4800 1500}%
    \special{pa 4550 1500}%
    \special{pa 4550 1750}%
    \special{fp}%
    \special{pa 350 1250}%
    \special{pa 600 1250}%
    \special{pa 600 1000}%
    \special{pa 350 1000}%
    \special{pa 350 1250}%
    \special{fp}%
    \special{pa 1750 1250}%
    \special{pa 2000 1250}%
    \special{pa 2000 1000}%
    \special{pa 1750 1000}%
    \special{pa 1750 1250}%
    \special{fp}%
    \special{pa 3150 1250}%
    \special{pa 3400 1250}%
    \special{pa 3400 1000}%
    \special{pa 3150 1000}%
    \special{pa 3150 1250}%
    \special{fp}%
    \special{pa 4550 1250}%
    \special{pa 4800 1250}%
    \special{pa 4800 1000}%
    \special{pa 4550 1000}%
    \special{pa 4550 1250}%
    \special{fp}%
    \special{pa 350 750}%
    \special{pa 600 750}%
    \special{pa 600 500}%
    \special{pa 350 500}%
    \special{pa 350 750}%
    \special{fp}%
    \special{pa 1750 750}%
    \special{pa 2000 750}%
    \special{pa 2000 500}%
    \special{pa 1750 500}%
    \special{pa 1750 750}%
    \special{fp}%
    \special{pa 3150 750}%
    \special{pa 3400 750}%
    \special{pa 3400 500}%
    \special{pa 3150 500}%
    \special{pa 3150 750}%
    \special{fp}%
    \special{pa 4550 750}%
    \special{pa 4800 750}%
    \special{pa 4800 500}%
    \special{pa 4550 500}%
    \special{pa 4550 750}%
    \special{fp}%
    \special{pa 0 250}%
    \special{pa 250 250}%
    \special{pa 250 0}%
    \special{pa 0 0}%
    \special{pa 0 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 0.125in\lower\graphtemp\hbox to 0pt{\hss M0\hss}}%
    \special{pa 700 250}%
    \special{pa 950 250}%
    \special{pa 950 0}%
    \special{pa 700 0}%
    \special{pa 700 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 0.825in\lower\graphtemp\hbox to 0pt{\hss M1\hss}}%
    \special{pa 1400 250}%
    \special{pa 1650 250}%
    \special{pa 1650 0}%
    \special{pa 1400 0}%
    \special{pa 1400 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 1.525in\lower\graphtemp\hbox to 0pt{\hss M2\hss}}%
    \special{pa 2100 250}%
    \special{pa 2350 250}%
    \special{pa 2350 0}%
    \special{pa 2100 0}%
    \special{pa 2100 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 2.225in\lower\graphtemp\hbox to 0pt{\hss M3\hss}}%
    \special{pa 2800 250}%
    \special{pa 3050 250}%
    \special{pa 3050 0}%
    \special{pa 2800 0}%
    \special{pa 2800 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 2.925in\lower\graphtemp\hbox to 0pt{\hss M4\hss}}%
    \special{pa 3500 250}%
    \special{pa 3750 250}%
    \special{pa 3750 0}%
    \special{pa 3500 0}%
    \special{pa 3500 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 3.625in\lower\graphtemp\hbox to 0pt{\hss M5\hss}}%
    \special{pa 4200 250}%
    \special{pa 4450 250}%
    \special{pa 4450 0}%
    \special{pa 4200 0}%
    \special{pa 4200 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 4.325in\lower\graphtemp\hbox to 0pt{\hss M6\hss}}%
    \special{pa 4900 250}%
    \special{pa 5150 250}%
    \special{pa 5150 0}%
    \special{pa 4900 0}%
    \special{pa 4900 250}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 0.125in
    \rlap{\kern 5.025in\lower\graphtemp\hbox to 0pt{\hss M7\hss}}%
    \special{pa 0 2850}%
    \special{pa 250 2850}%
    \special{pa 250 2600}%
    \special{pa 0 2600}%
    \special{pa 0 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 0.125in\lower\graphtemp\hbox to 0pt{\hss P0\hss}}%
    \special{pa 700 2850}%
    \special{pa 950 2850}%
    \special{pa 950 2600}%
    \special{pa 700 2600}%
    \special{pa 700 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 0.825in\lower\graphtemp\hbox to 0pt{\hss P1\hss}}%
    \special{pa 1400 2850}%
    \special{pa 1650 2850}%
    \special{pa 1650 2600}%
    \special{pa 1400 2600}%
    \special{pa 1400 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 1.525in\lower\graphtemp\hbox to 0pt{\hss P2\hss}}%
    \special{pa 2100 2850}%
    \special{pa 2350 2850}%
    \special{pa 2350 2600}%
    \special{pa 2100 2600}%
    \special{pa 2100 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 2.225in\lower\graphtemp\hbox to 0pt{\hss P3\hss}}%
    \special{pa 2800 2850}%
    \special{pa 3050 2850}%
    \special{pa 3050 2600}%
    \special{pa 2800 2600}%
    \special{pa 2800 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 2.925in\lower\graphtemp\hbox to 0pt{\hss P4\hss}}%
    \special{pa 3500 2850}%
    \special{pa 3750 2850}%
    \special{pa 3750 2600}%
    \special{pa 3500 2600}%
    \special{pa 3500 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 3.625in\lower\graphtemp\hbox to 0pt{\hss P5\hss}}%
    \special{pa 4200 2850}%
    \special{pa 4450 2850}%
    \special{pa 4450 2600}%
    \special{pa 4200 2600}%
    \special{pa 4200 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 4.325in\lower\graphtemp\hbox to 0pt{\hss P6\hss}}%
    \special{pa 4900 2850}%
    \special{pa 5150 2850}%
    \special{pa 5150 2600}%
    \special{pa 4900 2600}%
    \special{pa 4900 2850}%
    \special{fp}%
    \graphtemp=.5ex\advance\graphtemp by 2.725in
    \rlap{\kern 5.025in\lower\graphtemp\hbox to 0pt{\hss P7\hss}}%
    \special{pa 125 2600}%
    \special{pa 125 2250}%
    \special{fp}%
    \special{pa 825 2600}%
    \special{pa 825 2250}%
    \special{fp}%
    \special{pa 1525 2600}%
    \special{pa 1525 2250}%
    \special{fp}%
    \special{pa 2225 2600}%
    \special{pa 2225 2250}%
    \special{fp}%
    \special{pa 2925 2600}%
    \special{pa 2925 2250}%
    \special{fp}%
    \special{pa 3625 2600}%
    \special{pa 3625 2250}%
    \special{fp}%
    \special{pa 4325 2600}%
    \special{pa 4325 2250}%
    \special{fp}%
    \special{pa 5025 2600}%
    \special{pa 5025 2250}%
    \special{fp}%
    \special{pa 0 3250}%
    \special{pa 2350 3250}%
    \special{fp}%
    \special{pa 2800 3250}%
    \special{pa 5150 3250}%
    \special{fp}%
    \special{pa 250 2125}%
    \special{pa 350 2125}%
    \special{fp}%
    \special{pa 350 2125}%
    \special{pa 350 3250}%
    \special{fp}%
    \special{pa 700 2125}%
    \special{pa 600 2125}%
    \special{fp}%
    \special{pa 600 2125}%
    \special{pa 600 3250}%
    \special{fp}%
    \special{pa 1650 2125}%
    \special{pa 1750 2125}%
    \special{fp}%
    \special{pa 1750 2125}%
    \special{pa 1750 3250}%
    \special{fp}%
    \special{pa 2100 2125}%
    \special{pa 2000 2125}%
    \special{fp}%
    \special{pa 2000 2125}%
    \special{pa 2000 3250}%
    \special{fp}%
    \special{pa 3050 2125}%
    \special{pa 3150 2125}%
    \special{fp}%
    \special{pa 3150 2125}%
    \special{pa 3150 3250}%
    \special{fp}%
    \special{pa 3500 2125}%
    \special{pa 3400 2125}%
    \special{fp}%
    \special{pa 3400 2125}%
    \special{pa 3400 3250}%
    \special{fp}%
    \special{pa 4450 2125}%
    \special{pa 4550 2125}%
    \special{fp}%
    \special{pa 4550 2125}%
    \special{pa 4550 3250}%
    \special{fp}%
    \special{pa 4900 2125}%
    \special{pa 4800 2125}%
    \special{fp}%
    \special{pa 4800 2125}%
    \special{pa 4800 3250}%
    \special{fp}%
    \special{pa 125 2000}%
    \special{pa 350 1750}%
    \special{fp}%
    \special{pa 825 2000}%
    \special{pa 600 1750}%
    \special{fp}%
    \special{pa 1525 2000}%
    \special{pa 1750 1750}%
    \special{fp}%
    \special{pa 2225 2000}%
    \special{pa 2000 1750}%
    \special{fp}%
    \special{pa 2925 2000}%
    \special{pa 3150 1750}%
    \special{fp}%
    \special{pa 3625 2000}%
    \special{pa 3400 1750}%
    \special{fp}%
    \special{pa 4325 2000}%
    \special{pa 4550 1750}%
    \special{fp}%
    \special{pa 5025 2000}%
    \special{pa 4800 1750}%
    \special{fp}%
    \special{pa 125 250}%
    \special{pa 350 500}%
    \special{fp}%
    \special{pa 825 250}%
    \special{pa 600 500}%
    \special{fp}%
    \special{pa 1525 250}%
    \special{pa 1750 500}%
    \special{fp}%
    \special{pa 2225 250}%
    \special{pa 2000 500}%
    \special{fp}%
    \special{pa 2925 250}%
    \special{pa 3150 500}%
    \special{fp}%
    \special{pa 3625 250}%
    \special{pa 3400 500}%
    \special{fp}%
    \special{pa 4325 250}%
    \special{pa 4550 500}%
    \special{fp}%
    \special{pa 5025 250}%
    \special{pa 4800 500}%
    \special{fp}%
    \special{pa 350 1500}%
    \special{pa 350 1250}%
    \special{fp}%
    \special{pa 600 1500}%
    \special{pa 1750 1250}%
    \special{fp}%
    \special{pa 1750 1500}%
    \special{pa 3150 1250}%
    \special{fp}%
    \special{pa 2000 1500}%
    \special{pa 4550 1250}%
    \special{fp}%
    \special{pa 3150 1500}%
    \special{pa 600 1250}%
    \special{fp}%
    \special{pa 3400 1500}%
    \special{pa 2000 1250}%
    \special{fp}%
    \special{pa 4550 1500}%
    \special{pa 3400 1250}%
    \special{fp}%
    \special{pa 4800 1500}%
    \special{pa 4800 1250}%
    \special{fp}%
    \special{pa 350 1000}%
    \special{pa 350 750}%
    \special{fp}%
    \special{pa 600 1000}%
    \special{pa 1750 750}%
    \special{fp}%
    \special{pa 1750 1000}%
    \special{pa 3150 750}%
    \special{fp}%
    \special{pa 2000 1000}%
    \special{pa 4550 750}%
    \special{fp}%
    \special{pa 3150 1000}%
    \special{pa 600 750}%
    \special{fp}%
    \special{pa 3400 1000}%
    \special{pa 2000 750}%
    \special{fp}%
    \special{pa 4550 1000}%
    \special{pa 3400 750}%
    \special{fp}%
    \special{pa 4800 1000}%
    \special{pa 4800 750}%
    \special{fp}%
    \hbox{\vrule depth3.250in width0pt height 0pt}%
    \kern 5.150in
  }%
}%
\centerline{\box\graph}

\hspace{2.5in} Figure 2


\end{document}



