Performance Prediction and Evaluation of Parallel Processing on a NUMA Multiprocessor.
The efficiency of the basic operations of a NUMA (nonuniform memory access) multiprocessor determines the parallel processing performance on a NUMA multiprocessor. The authors present several analytical models for predicting and evaluating the overhead of interprocessor communication, process scheduling, process synchronization, and remote memory access, where network contention and memory contention are considered. Performance measurements to support the models and analyses through several numerical examples have been done on the BBN GP1000, a NUMA shared-memory multiprocessor. Analytical and experimental results give a comprehensive understanding of the various effects, which are important for the effective use of NUMA shared-memory multiprocessor. The results presented can be used to determine optimal strategies in developing an efficient programming environment for a NUMA system.
a distributed memory multicomputer environment in which data sharing and communication are
conducted by message-passing through the network. The bus-based shared memory multiproces-
sors, such as the Encore Multimax and Sequent Symmetry always make an uniform memory access
(UMA) to the shared data because of the exclusive use of the bus per data access. The simple bus
structure limits the size of the UMA multiprocessor to a small scale, for example up to
cessors. In a NUMA architecture, the shared memory environment is built through a distributed
architecture - each processor has its local memory and is also able to access to all other memory
models through a switching network. Therefore, a NUMA architecture can scale large number
of processors in shared memory multiprocessor design. Examples of current NUMA architectures
include BBN Butterfly family (see e.g. [3]-[5], [16], [23]), Cedar at the University of Illinois (see
e.g. [14], [26]), the IBM RP3 (see e.g. [21]), Cm* and PLUS at Carnegie-Mellon University (see
e.g. [9], [17], [22]), Hector (see [25]) and Paradigm (see [11]), in which the BBN butterfly machines
are the only systems commercially available, and the rest are research model architectures.
1.1 Programming models on a NUMA architectures
Programming models on a NUMA architecture can be classified into three types: distributed mem-
partially shared memory and fully shared memory. Under the distributed programming model,
each node is viewed as a complete computer supported by a processor, a local memory and some
I/O facilities physically on one board which connects to all other nodes in the system. An important
factor in the efficiency of the distributed memory model is the effectiveness with which data can
be exchanged among its many nodes. The partially shared memory programming model provides
noncached access to shared memory, with program code and private data stored in local memory.
Programming requires partitioning the application across all the nodes in load time which explores
the processor locality best but provides no dynamic process scheduling in run time. The shared
memory synchronization primitives such as a barrier are supported for synchronizing processors at
the end of a group of parallel tasks. The fully shared memory programming model implies that
any processor can access any memory module at any time except with one exception: no single
memory module can be accessed by more than one processor simultaneously. From a user's point
of view, all processors share a single pool of memory in different memory access time. A scheduling
mechanism is supported to schedule the processes dynamically among the processors in run time.
Several related studies have been conducted to understand and improve the parallel processing
performance on a NUMA multiprocessor. LaRowe and Ellis (see [19]) take an experimental approach
to compare a wide-range of memory management policies on a target NUMA system, the
BBN GP1000. Their system experiments conclude that the placement and movement of code and
data are crucial to NUMA performance. The performance of a general multistage interconnection
network, such as the Omega network has been evaluated analytically (see e.g. [6], [7], [15]). The
analysis work is independent on the NUMA architecture although the multistage interconnection
network is commonly used for a NUMA system. The performance factors of NUMA multiprocessors
(for example, the BBN GP1000), such as the data access time, scheduling overhead and others have
been measured through various application programs (see e.g. [10], [30]). As memory architectures
and interconnection networks become more complex, the performance prediction and evaluation
of a NUMA architecture become more difficult. This paper studies the three types of programming
models supported in a NUMA multiprocessor architecture, and presents several analytical
models and measurements to predict and evaluate the overhead of interprocessor communication,
process synchronization, process scheduling and remote memory access where network contention
and memory contention are considered. Performance measurement to support the models and
analyses through different measurements has been done on the BBN GP1000, a NUMA shared
memory multiprocessor. It is our goal to provide reasonably accurate NUMA performance models
to incorporate both interconnection network effects and NUMA system effects by the analyses and
experiments.
1.2 Performance models
Our performance analyses start with Amdahl's law [1] which is in its simplest form of execution
time versus number of processors p
This model can be viewed as separating a program into a perfectly parallelized time section t p
and strictly sequential time section t s
and running on a p node multiprocessor, where t s
Amdahl's law is an incomplete model for evaluating parallel processing performance in practice.
The model ignores several significant effects such as communication, synchronization, memory
management, memory and network contention and others. Amdahl's model may be modified by
adding an overhead function term T o (p) to include the practical effects
The modified Amdahl's model has been used for evaluating parallel processing performance on
different architectures, such as the vector supercomputers (see e.g. [18]), distributed memory multicomputer
hypercube (see e.g. [13]), and UMA shared memory multiprocessors (see e.g. [28]). The
overhead function T o (p) can be affected by the structure of the application which influences the
necessity for communication, task dispatching algorithm used to control assignment of processes
to processors as well as the hardware and software mechanisms for communication and synchro-
nization. Similar to other distributed memory multicomputers, communication delay is the major
overhead when distributed programming model is applied in a NUMA architecture. The computing
bottleneck in partially shared memory programming model is the barrier synchronization set at the
end of a group of parallel tasks. A typical parallel computation process under the shared memory
programming model on a NUMA architecture is described in following steps. The system spends
some amount of time to generate the parallel tasks and place them in shared memory visible to all
processors through an interconnection network. Then each processor, in turn, enters the critical
region to select or to be assigned a task for itself. At the end of computation there will be some time
expended waiting for the last processor to finish its parallel task. The another important source
of runtime overhead on a NUMA multiprocessor under both shared memory models comes from
remote memory access, i.e. a processor access (read or write) the memory models which are not
local to itself. Therefore, in the distributed memory programming model, the overhead function is
mainly contributed by the communication cost
barrier synchronization and remote memory access in the partially shared memory model,
and process scheduling in shared memory programming models,
respectively.

Figure

1: A two-level interconnection network connecting 16 processors and 16 memory modules.
1.3 The BBN GP1000
The GP1000 (see [3]-[5]), based on the original Butterfly architecture is a MIMD system, and
incorporates up to 256 Motorola 68020 processor nodes connected via a multistage interconnection
switching network. An example of a 16 processor GP1000 system is described in Figure 1. The
network is composed of 4 2 4 switches to form a plog 4 p switching interconnection, where p is the
number of processors connected. The bandwidth of each path of a switch is
Each processor node has a 68851 paged memory management unit for virtual memory processing.
The memory of the machine is shared among all processors in this way - each processor node
includes 4 MBytes of memory that can be accessed from any processor in the system via the network.
Each memory location is physically local to its host processor, although globally accessible by any
processor in the system. A memory access from a processor to its own memory through the direct
path is called local access, and a memory access from a processor to other memory models through
the network is called remote access. The time ratio between a local access and a remote access with
no other processors active on the GP1000 is up to 1:15 depending on the types of the access (see
e.g. [10]).
The GP1000 provides a parallel programming environment called the Uniform System (see [5])
where the parallel tasks may be distributed and processed without regard to the physical location
of the data associated with the tasks. The Uniform System is an UMA (Uniform Memory Access
where all processors have uniform memory access time for all data) shared memory programming
model implemented on a NUMA architecture, the GP1000. Thus, the Uniform System uses shared
memory data structures, called task generators to specify the parallel operations. This approach
to processor management is implemented by treating processors as equivalent workers. When a
processor working on a task finishes its current task, it looks for the next task, which performs the
best possible load balancing dynamically, but totally ignores the processor locality. The memory
management mechanisms in the Uniform System makes the globally shared data visible to all
processes, allows programs to control where data is allocated and provides means for copying
blocks of data from one memory to another.
We evaluate and measure the NUMA performance based on the four major overhead sources:
communication, barrier synchronization, process scheduling and remote memory access, and provide
several timing models and experimental results. Section 2 presents some performance evaluation
for the distributed memory model. Communication overhead in message passing is measured on
the GP1000 multiprocessor. Section 3 gives two models for evaluating static and dynamic task
scheduling performance and the synchronization overhead under the partially and fully shared
memory programming models. The synchronization cost and dynamic scheduling overhead are also
measured on the GP1000 multiprocessor through several numerical examples. The remote access
delay is studied in section 4 along with analytical models and experimental measurements. Finally,
a summary is given in section 5.
communication overhead
In a NUMA multiprocessor system, the memory modules are distributed and an interconnection
network is used to connect a processor and its local memory with all other processors and their memory
modules. This type of architecture, such as the BBN GP1000, can also support a distributed
memory multicomputer environment in which data sharing and communication are conducted by
message-passing through the interconnection network. When a message passes between a pair of
nodes in the system, it is routed through a number of switches of the network. If no contentions in
the switches are considered, and a multi-level connection network is used (see Figure 1), the over-
ff fi
GP1000 1812 2.40
Topology 1000 215

Table

1: Alpha and Beta for interprocessor communication on GP1000 comparing with other five
types of distributed memory multicomputers
head of a message passing between any pair of nodes is identical. Thus, the basic communication
timing test for distributed memory model is to measure the time required to transmit a message
packet from one node to a another node through the network. This test is also called echo test: A
test node sends a message to an echo node which is directly connected to the test node. The echo
node receives the message and sends it back to the test node. The interprocessor communication
time required to transmit a message between two directly connected nodes may be approximately
expressed as
where K is the number of bytes contained in the message, ff is the overhead or the startup time for
sending a packet in -s and fi is the bandwidth of the communication channel (-s/byte). We conducted
echo tests for measuring the interprocessor communication overhead on the BBN GP1000.
The communication primitive in the machine is supported by a set of Mach 1000 system calls. We
used Different sizes of message packets, from 1 byte to 8K bytes, in our experiment, and used a
least square fit to approximate ff and fi. Table 1 gives the ff and fi of the GP1000 comparing with
other five types of distributed memory multicomputers (see e.g. [29]).
Our experimental results show that the message-passing on the GP1000 is not very efficient.
The bandwidth of the communication channel fi is same as the one of Intel iPSC/1, a representative
of the first generation hypercube multicomputer. The startup time ff for sending a packet, is about
4 times longer than the one of the iPSC/1. This is because a connection between a processor
and a remote memory module for remote memory access is established through two level switches.
Therefore, the distributed programming model on the BBN GP1000 is not preferred unless very
large data sets need to be exchanged occasionally. (see [24]).
3 Process scheduling models and synchronization overhead
There are two major process scheduling models available on a NUMA multiprocessor, pre-scheduling
for the partially shared memory programming model and self-scheduling for the fully shared memory
programming model. We evaluate the overhead from these two schedulings respectively and give
quantitative comparisons between the two models through different numerical examples in this
section.
3.1 Pre-scheduling and barrier
In pre-scheduling, the tasks are pre-scheduled to be assigned to some processors at load time.
All processes must wait at a synchronization point called barrier until the slowest finishes. A
synchronization barrier defines a logical point in the control flow at which all processes must arrive
before any are allowed to proceed further. It is most often used to synchronize processors at the end
of processing a group of parallel tasks, such as the pre-scheduling model. Thus, the consequences
of fluctuations in the execution time or the imbalanced task load are maximized. By choosing the
task load from a normal probability distribution, we derive a simple analytical timing model which
predicts the effect of imbalanced task load caused from pre-scheduling scheme. The model assumes
that there are p processors that begin the work section simultaneously; the time each takes has
mean - and standard deviation oe. Assuming mutual independence, the instant at which the last
processor completes the work section, t w , is given by
Thus, keeping the task load balanced among the independent processes (reducing oe), and reducing
number of barriers will decrease the potentially large performance penalties caused by the pre-scheduling
process.
The advantage of pre-scheduling is that no dynamic load scheduling is performed. If the task
distribution decision can be made deterministically so that the tasks can be processed efficiently
among the processors, and the degree of the imbalanced task load is minimized, pre-scheduling is
preferred.
A simple algorithm of the barrier to synchronize the pre-scheduling is the accumulating counter
barrier (see e.g. [2]), which is implemented on the BBN GP1000. This consists of two locks and a
shared counter. The first lock controls access to the shared counter, which records the number of
processes that have arrived at the barrier. This counter must be globally shared and all access to
it serialized.
The shared counter is allocated to the local memory of one processor. When the process in the
processor with the shared counter arrives at the barrier point, it simply does an atomic operation
to the counter in the local memory. The atomic operation includes a "busy-wait" type of lock, and
an unlock immediately after an update to the counter. The rest of the processors have to busy-wait
and access the counter using remote memory accesses through the interconnection network when
the processes arrive at the barrier. The worst case situation can occur in which all processors arrive
at the barrier at the same time and the shared counter is updated in a sequential order. The barrier
synchronization delay in time units on a NUMA shared memory architecture may be described as
where p is number of processors used, t atom is the time spent on the atomic operation to lock,
update and unlock the counter, t i for is the remote memory access conducted by the
processors respectively. On the GP1000, t i is a constant, in other words, the remote memory
access is equally distant among the processors. If we use t r to represent the identical remote access
delay, (3.2) becomes
The linear function (3.3) can be simplified as
where fl represents the critical section delay protecting the update of the shared counter in the
local memory, and ffi is the overhead caused by a remote update to the shared counter through the
interconnection network.
We computed a matrix dot-product, A is a n 2 n matrix, b is a vector
with n elements on the GP1000. The n rows of the matrix A are distributed in blocks on the
processors, and each processor holds a copy of the b vector. In order to measure the overhead
only associated with the barrier implementation, we minimize the fluctuations in the execution
time of the multiplication, which is the oe described in (3.1) by evenly pre-scheduling the tasks
among the processors in our experiment. We run the program on different number of processors,
from 1 to 12 in our experiment, and used a least square fit to approximate fl and ffi. Ideally, the
barrier synchronization overhead is independent of the sizes of the evenly distributed dot-product
problems. We computed the dot-product for the problems of different sizes: 120, 240, 480 and
1200 variables. The differences of the approximated fl's and ffi's by using the least square fit from
different size problems are trivial. We get the average fl and ffi from these experiments and obtain
the synchronization overhead for the GP1000
Imbalanced load and the computing cycles consumed by the barrier are the two major sources
of a complete synchronization overhead in pre-scheduling, which may be expressed as the sum of
the second term of (3.1) and (3.3)
More efficient barrier algorithms are proposed on the NUMA shared memory architectures. Interested
readers may refer to [20] and [8].
3.2 Self-scheduling and shared memory programming
In order to balance the processing load, the tasks are dynamically scheduled or self-scheduled to
processors at runtime. The self-scheduling algorithm consists of each processor fetching a task one
at a time by requiring mutually exclusive access to a shared variable, and reading or modifying
appropriate data in some memory modules. In an UMA architecture, such as the bus-based shared
memory multiprocessors, each processor requires exclusive access to the shared bus to reach the
shared memory. In a NUMA architecture, such as the GP1000, access to the shared memory is
performed through the interconnection network with or without network contention problems. The
multistage interconnection switching network provides a unique path between any source processor
and destination memory module pair. However, the paths for different pairs are not disjoint and,
therefore, conflicts may occur when simultaneous communication is established between several
source-destination pairs, which may degrade parallel performance.
Consider a computing job which may be divided into n tasks, each requiring an average t comp
units of time to execute on a single processor. This computing job is executed on p processors.
The self-scheduling routines create and initialize the task data structures and place them in shared
memory visible to all processors but with different distances to each processor on a NUMA archi-
tecture. This process spends t init time units for initializing each task. Each processor requires extra
time units t i to access the data of the scheduled task which may also be denoted
as as a constant, t r for the identical remote access delay, such as the one in GP1000. In addition,
each processor requires an overhead of t arri units in synchronizing at the barrier at the end of
the computation, where t arri units are spent to notify other processors of its arrival. Finally, it
will be the first scheduled processor to process a task, and the last to terminate on program exit.
Thus, this special processor needs t chek units to check that all other processors have arrived. We
assume that n is an integral multiple of p, the parallel execution time on a NUMA shared memory
multiprocessor may be described as
The first term of (3.7) is the time purely spent on computing and the rest of terms are the overhead
of the scheduling

Figure

2 gives a time line of the self-scheduling with
3.3 Comparisons of the two scheduling models
Pre-scheduling and self-scheduling provide static and dynamic load balancing schemes. Comparing
(3.6) with (3.8), the overhead caused from pre-scheduling and the overhead from self-scheduling
are quantitatively equal if
oe =p 2log(p)
the overhead from the pre-scheduling is quantitatively larger than the one from the self-scheduling
if
oe ?p
and the overhead from the pre-scheduling is quantitatively less than the one from the self-scheduling
if
oe !p

Figure

2: A Self-scheduling example: 8 tasks are scheduled to run on 4 processors
where oe is the standard deviation for the time each task used on one processor, representing the
degree of the imbalanced task load.
Based on above analysis, if variance in distributed task processing is expected to be not large,
and to have no dynamic changes during the execution, then there is no advantage in using self-scheduling
according to (3.11). Self-scheduling will decrease the arrival time variance at the cost
of the scheduling overhead. When (3.10) exists, self-scheduling will gain more.
3.4 Numerical experiments in pre-scheduling and self-scheduling
The numerical experiment we conducted to compare the two scheduling models is a group of complex
nonlinear circuit simulations. The objective of circuit simulation is to determine accurately the
voltage and current waveforms of a circuit over a period of time specified by the user given the
topology and electric elements of the circuit. When the simulation is conducted on a multiprocessor,
one method is to partition the circuit so that each processor simulates one or a set of subcircuits
concurrently. The result of the circuit partitioning leads us to solve a special class of nonlinear
systems of equations in block bordered structure by using Newton's method
n. For detailed mathematical analyses
of the nonlinear block bordered equations, reader may refer to [27].
The circuit equations usually are highly nonlinear so that a Newton step easily may result in
an increase in the function norm. In addition, many block bordered equations result in nearly
singular or singular Jacobians in the iteration process. Thus, the Newton step needs to be modified
dynamically to converge to a solution. The modifications on some of the subsystems, such as a
line search and matrix perturbations (see e.g. [12]) require extra computing time that cannot be
predicted statically before running the program.
The testing circuit problem we simulated was the 741 op-amp from [27], where Using
the pre-scheduling model, the block bordered equations
of the 741 op-amp circuit were distributed among 1, 2, and 4 nodes of the GP1000 respectively.
In addition, the function f q+1 was assigned to another node which plays the control role. The
computation load among different nodes was reasonably balanced statically obtained from the
circuit partitioning. In the runtime of the simulation, each subsystem was perturbed only once.
The independent computation time in each node is only slightly different.
Using the self-scheduling model, the sub-circuit systems were scheduled in the run-time by
the system. The sub-circuit system data structures were placed in shared memory visible to all
processors but in different distances to each processor on the GP1000. Again, we used 1, 3, and
processors respectively for the computation. The computing performance under both scheduling
models are given in Figure 3. Our experiments showed that the computing performance under
the self-scheduling model is poor comparing with the one under the pre-scheduling model. This
is because the partitioned systems were well balanced before the runtime, therefore the dynamic
scheduling became a real overhead in the multiprocessing.
We also simulated an analog filter connected by 3 blocks of 741 op-amp circuit (see [27]) on

Figure

3: Pre-scheduling and self-scheduling of the op-amp 741 simulation.
the GP1000 where 12 sub-circuit systems are generated. The 12 block equations of the analog
filter were distributed among 1, 3, 6, and 12 nodes of the GP1000 respectively. This nonlinear
system is harder to compute than the single 741-op-amp system because it is an unbalanced block
bordered system due to the singularity of some subsystems in the runtime. Some of the subsystems
were perturbed quite often during the Newton iteration. We applied both pre-scheduling and
self-scheduling models to the unbalanced systems. Figure 4 gives the computational curves of
both. Since the pre-scheduling is not able to handle dynamic load scheduling in runtime, the
self-scheduling did show its effectiveness for solving this system.
4 Remote memory access delay
4.1 Background
As memory architectures become more complex and the interconnection network introduces the
non-uniform memory access, the remote memory access prediction and evaluation of a NUMA
system under dynamic environment become more difficult. Some remote memory access delay has
been measured on the BBN butterfly systems between a processor and a memory module pair
without considering the memory and network contentions at all or without considering the random
contentions. (see e.g. [3], [10]). However, in real parallel processing on a NUMA system, the remote
memory access delay is more complicated because of the memory and network contentions. We
give an analytical model to predict the average remote memory access delay with considerations of
different network and memory architecture effects of NUMA systems.

Figure

4: Pre-scheduling and self-scheduling of an analog filter connected by 3 op-amp 741 simulation

The multistage switching interconnection network is commonly and effectively used in NUMA
systems, such as the BBN Butterfly systems and the IBM RP3 multiprocessors. Figure 1 shows a
two-stage switching network connecting 16 processors and 16 memory modules, where each switch
has 4 inputs and 4 outputs. The network contention is defined as a conflict where two messages
need to access the same portion of a path at the same time. The network can be designed either
in blocking form or nonblocking form. In the blocking-network, a protocol organizes a message
queue while all the conflicting traffic comes to a standstill (each of the other conflicting messages
sits and holds its path). When the path is cleared, the next selected message proceeds. Problem
of the blocking network is the so called cascade effect - when each new message tends to run into
other blocked messages, and so gets blocked itself. This ties up more resources in the switch, and
increases the chance that subsequent messages will also block. The non-blocking network greatly
reduces the traffic conflicts in practice (see e.g. [23]): when conflicts happen, the switch has all but
the "first" message retreat back to its source and free up their path. It then selects an alternative
route, and after a random delay, tries again. Our model is based on the nonblocking-network
architecture, which is used for most NUMA systems.
4.2 A model of remote memory access
Gelenbe [15] describes the behavior of a remote memory access in a nonblocking multi-stage interconnection
network by a state transition diagram called drop approach (see Figure 5). Here a
processor makes a remote memory access by formulating requests for access to the set of switches

Figure

5: State transition diagram for remote memory access through an n-stage interconnection
network.
along that path. If it cannot obtain a switch, it abandons its request at that point and will try
again at some later time. In Figure 2, state 0 represents some processor in quiescent state, while
represents an ongoing successful access. State b represents the processor when it has
dropped its request because of the switch contention.
To make an analytical model tractable certain approximation assumptions are necessary. We
assume that in multiprocessor system each processor is identical and has an uniform reference
model, which is different from the UMA concept. The URM (Uniform Reference Model) implies
that, when a processor makes a memory request to the global memory, the request will be directed to
any memory modules with the same probability, that is the destination address of a memory request
is uniformly distributed among all the memory modules. This symmetric property significantly
simplifies the modeling. The average remote memory access delay is estimated by making use of a
semi-Markov model.
The length of a path is n, and a request will be in some state i (1 - i - n), if it has successfully
obtained the first i switches on its path. From state i it will go to b if its (i 1)-th request is
not successful, otherwise it will go to state (i + 1). This process continues until the state n + 1 is
reached if all of the switch requests are granted. Finally, it goes from state n + 1 to state 0 after
the processor access the memory module, and releases the path then.
Assume - 0 is the rate (number of the requests per time unit) at which a quiescent processor
makes a remote memory access, and 1=- 0 is the average time spent by the processor in the state
before making the access. When a processor is in the state i, (1 - i - n), we assume it requests
the next switch after an average time T i , with a probability of success q i . Following notation for
are used for later mathematical work:
In practice, all the switches in a network are the same. Therefore, all the T i 's for
are identical, and . The average duration of an access is denoted as 1=OE s , after which a
processor will return to state 0. Similarly we use 1=OE b to denote the average time spent in state b,
after a conflict is detected before the processor returns to the quiescent state.
Based on the Kirchhoff Current Law (KCL) of flow balance and above assumptions, the steady-state
probabilities associated with the states of the model may be obtained from the following
equations:
and
is the steady-state probabilities at state i. There are n
above, of which the last equation can be derived from the previous n+ 2 ones. To solve the system
of equations, one additional equation based on the sum of the success and fail probability:
The success probability at i-th state q i will depend on the traffic conditions, and can be expressed
based on the steady-state probabilities and the input/output size of each switch in the network
is the steady-state probabilities at state i, k is the input/output size of multistage inter-connection
network use.
By substituting q i into - i we get n new equations with
?From the above system of equations we are able to solve each - get each q i for
The probability that a memory reference request may fail at i-th stage network is
Then the average delay of unsuccessful memory access (caused either by network contention or by
memory contention) is
and the successful one is
The average delay for each remote access is then
(4.
s is the probability of success of remote access
Then the average delay caused by m remote access in one computation is
4.3 An experiment for remote memory access
It is very difficult to use a limited number of experiments to cover all the cases interpreted by (4.14)
because of the random contentions and various structures of application programs. However, the
remote memory access delay, in practice is determined by the two important factors: (1) the delay
of establishing a connecting path between a processor and the remote memory module through
network switches, and (2) the network contention. The connection delay is a constant in time
units without considering any network contention, which is architecture dependent. For example,
GP1000 spends about 0.5 -s to establish a remote memory access connection through the 2-level
switches. After the connection is established, the read or write operations are performed by data
communication in the rate of 0.125 -s for every 4-bits. (see e.g. [3]). The network contention is
basically determined by the remote access rate, defined as the number of remote access per time
unit, which is denoted as - in (4.1).
We constructed two programs for measuring and comparing the remote memory access effects
on the GP1000. One is a matrix multiplication, A = C2B, and the other one is a matrix addition,
are all n 2 n square matrices. The structures of the
programs are designed in such a way that each single operation, the multiplication or the addition
on a pair of data needs two remote memory access. Therefore, the number of remote access for the
matrix multiplication and addition are 2 2 n 3 and 2 2 n 2 respectively, where n is the size of the
matrices in the computations. In order to compare the remote memory access effects between the
computations, we made the number of remote memory access in two problems identical by chosing
the size of the matrices in the addition, n a = nm
nm , where n a is matrix size of the addition, and
nm is the size in the multiplication.

Figure

6 gives the remote access times of the two computations on different number of processors.
The size of the matrix multiplication is 80, and 716 for the matrix addition. Both computations

Figure

Remote access time for both matrix addition and matrix multiplication on the GP1000.
performed a total of approximate 1024210 3 times remote memory access on the GP1000. However,
the time spent on remote access for computing the matrix addition is almost twice as much as that
for computing the matrix multiplication. A total of times of multiplication operations
are performed in the matrix multiplication program, while approximately same number of additions
are performed in the matrix addition program. The computing time ratio between a multiplication
operation and an addition operation by each of the MC68020 processors in the GP1000 is about
1.7. Thus, the remote memory access rate in the matrix addition program is about 1.7 times higher
than the one in the matrix multiplication. This gives the difference of overall remote access times
in a similar factor between the two programs runing on the GP1000 plotted in Figure 6. The higher
the remote memory access rate is, the higher chances the network contention will occur. Therefore,
the remote memory access rate can be simply used to predict the remote memory access delay.
5 Summaries
We have examined the effects of scheduling, synchronization and remote memory access to parallel
processing performance on a NUMA shared memory multiprocessor. Analytical models based on
a generic NUMA machine were developed, and tested and verified on the GP1000 multiprocessor
through several numerical examples. The analytical and experimental results in this paper may be
used as advice to determine an optimal parallel processing strategy for effective use of a NUMA
shared memory multiprocessor in developing efficient parallel programming environment and running
application programs. Current work includes the development of a graphical tool to monitor
and tune the performance of a NUMA multiprocessor based on the analysis models presented in
this paper.

Acknowledgement

: The authors wish to thank P. Srinivasan, W. Wu from the University of
Texas at San Antonio, and J. Zhou from the University of Ohio for some multiprocessor tesing and
technical discussions.



--R

"Validity of the single-processor approach to achieving large scale computing capabilities"
"Effects of Synchronization barriers on multiprocessor performance"
BBN Advanced Computer Inc.
BBN Advanced Computer Inc.
BBN Advanced Computer Inc.
"Design and performance of generalized interconnection network"
"Performance of multiprocessor interconnection network"
"A simple mechanism for efficient barrier synchronization in MIMD machines"

"Performance evaluation and prediction for parallel algorithms on the BBN GP1000"
"Paradigm: a highly scalable shared-memory multicomputer architecture"

"Performance of parallel processors"
"Cedar - a large scale multiprocessor"
John Wiley and Sons
"An overview of the Butterfly GP1000: a large-scale parallel Unix computer"
"Software management of Cm* - a distributed multiprocessor"
"Measuring parallel processor performance"
"Experimental comparison of memory Management policies for NUMA multiprocessors"
"Barrier synchronization over multistage interconnection networks"
"The IBM research parallel processor prototype (RP3): Introduction and architec- ture"
"Cm* - a modular, multi-microprocessor"
"Behavior of the Butterfly parallel processor in the presence of memory hot spots"
Experimental Studies on Different Programming Models on the BBN GP1000
"Hector: a hierarchically structured shared memory multiprocessor"
"Architecture of the Cedar parallel supercomputer"
"Parallel partition and simulation for large-scale circuits on a local memory mul- ticomputer"
"Performance measurement and modeling to evaluate various effects on a shared memory multiprocessor"
"System effects of interprocessor communication latency in multicomputers"
"Distributed task processing performance on a NUMA shared memory multiprocessor"
--TR
Effects of synchronization barriers on multiprocessor performance
Design and performance of generalized interconnection networks
Performance of Multiprocessor Interconnection Networks
Multiprocessor performance
Measuring parallel processor performance
Paradigm
Hector
Performance Measurement and Modeling to Evaluate Various Effects on a Shared memory Multiprocessor
Performance evaluation and prediction for parallel algorithms on the BBN GP1000
PLUS
System Effects of Interprocessor Communication Latency in Multicomputers
Experimental Comparison of Memory Management Policies for NUMA Multiprocessors

--CTR
Xiaodong Zhang , Robert Castaeda , Elisa W. Chan, Spin-Lock Synchronization on the Butterfly and KSR1, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.1, p.51-63, March 1994
L. Boyd , John-David Wellman , Santosh G. Abraham , Edward S. Davidson, Evaluating the communication performance of MPPs using synthetic sparse matrix multiplication workloads, Proceedings of the 7th international conference on Supercomputing, p.240-250, July 19-23, 1993, Tokyo, Japan
Xiaodong Zhang , Robert Castaeda , Elisa W. Chan, Spin-Lock Synchronization on the Butterfly and KSR1, IEEE Parallel & Distributed Technology: Systems & Technology, v.2 n.1, p.51-63, March 1994
Xiaodong Zhang , Yong Yan , Robert Castaeda, Comparative Performance Evaluation of Hot Spot Contention Between MIN-Based and Ring-Based Shared-Memory Architectures, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.872-886, August 1995
K. Harzallah , K. C. Sevcik, Hot spot analysis in large scale shared memory multiprocessors, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.895-905, December 1993, Portland, Oregon, United States
Yongsheng Song , Wei-Ming Lin, Performance prediction based loop scheduling for heterogeneous computing environment, Proceedings of the 1997 ACM symposium on Applied computing, p.413-421, April 1997, San Jose, California, United States
analytical models;programming environment;process synchronization;BBN GP1000;parallel processing performance;nonuniform memory access;multiprocessing systems;performance evaluation;process scheduling;network contention;parallel processing;scheduling;NUMA shared-memory multiprocessor;interprocessor communication;remote memory access;memory contention;optimal strategies