Buffered Banks in Multiprocessor Systems.
AbstractA memory design based on logical banks is analyzed for shared memory multiprocessor systems. In this design, each physical bank is replaced by a logical bank consisting of a fast register and subbanks of slower memory. The subbanks are buffered by input and output queues which substantially reduce the effective cycle time when the reference rate is below saturation. The principal contribution of this work is the development of a simple analytical model which leads to scaling relationships among the efficiency, the bank cycle time, the number of processors, the size of the buffers, and the granularity of the banks. These scaling relationships imply that if the interconnection network has sufficient bandwidth to support efficient access using high-speed memory, then lower-speed memory can be substituted with little additional interconnection cost. The scaling relationships are shown to hold for a full datapath vector simulation based on the Cray Y-MP architecture. The model is used to develop design criteria for a system which supports 192 independent reference streams, and the performance of this system is evaluated by simulation over a range of loading conditions.
Introduction
The gap between memory speed and processor
request rate is increasing rapidly in high
performance systems. This gap is due to a
decrease in processor cycle time, the use of
superscalar and other multiple issue mecha-
nisms, the increase in the number of processors
in shared memory systems, and the demands
of gigabit per second network commu-
nication. In addition, designers have sought
to replace expensive SRAM memories with
cheaper, slower DRAMS in order support dramatically
increased main memory sizes at a
reasonable cost.
In the face of these demands, several manufacturers
have introduced more complex circuitry
on their DRAM chips in order to reduce
the effective memory access time. Mit-
subishi, for example, has introduced a proprietary
cached DRAM. This chip has a small
SRAM which reduces the memory access time
if the reference is contained in the SRAM
[9]. Another cached DRAM has been developed
by Rambus [6]. Other approaches include
synchronous DRAM technology [14] and
enhanced DRAM technology [4]. Pipelined
memories have also been proposed
[11]. The effect of such memory hierarchies
in high-performance memory systems has not
been extensively studied.
In an ordinary interleaved memory, the
memory cycle time is the minimum time
required between successive references to a
memory module. The cycle time regulates
how quickly a processor can fill the memory
pipeline. Conflicts due to bad reference patterns
can cause the processor to block. The
latency is the time it takes for a read request
to navigate the memory pipeline and return a
value to the processor.
In hierarchical memory systems, such as
those which contain caches at the bank level,
the memory cycle time and the latency are
no longer constant. Caching can reduce both
the effective cycle time and the latency. This
paper explores buffering as an alternative or
as a supplement to caching at the chip level.
The proposed design is based on a buffering
scheme called logical bank buffering in which
physical banks are subdivided and buffered as
described in Section II. The principal contribution
of this paper is the development of a simple
model and the derivation of scaling relationships
among the efficiency, the bank cycle
time, the number of processors, the size of the
buffers, and the granularity of the banks. The
goal of the logical bank design is to provide
a mechanism for using large, slower memories
with a moderate number of high performance
processors while maintaining current operating
efficiency.
A second contribution of this work is the full
data-path simulation with register feedback
for a realistic interconnection network. High
performance machines, such as the Cray Y-
MP, have a separate interconnection network
for read return values. When simple memory
banks are replaced by a memory hierar-
chy, references arrive at the return network at
unpredictable times. Under moderate loading,
the resulting contention does not appear to be
a problem. Several approaches for equalizing
performance of reads and writes under heavy
loading are examined.
Buffering has been proposed by a number
of authors as a possible solution to the problem
of memory conflicts. A simulation study
by Briggs [2] showed that buffering at the processor
level in pipelined multiprocessors can
improve memory bandwidth provided that the
average request rate does not exceed the memory
service time. Smith and Taylor [20] explored
the effects of interconnection network
buffering in a realistic simulation model. The
simulations in this paper were based on a simi-
lar, but simpler interconnection network. The
buffering in this paper is at the memory modules
rather than within the interconnection
network, and the emphasis of the simulations
is on the verification of the scaling relationships

Other proposals to reduce memory conflicts
have been made. Skewing and related techniques
[7,8,12,13] have been shown to be effective
in reducing intraprocessor conflicts. A
recent simulation study by Sohi [21] explores
skewing and input and output buffering for
single reference streams consisting of vectors of
length 1024 with fixed strides. Skewing techniques
are not as effective for the situation considered
in this paper where conflicts between
processors are the main cause of performance
degradation. Skewing can be used in conjunction
with logical banks to reduce intraprocessor
contention.
This study uses memory efficiency and
throughput as its primary measures of memory
performance. The efficiency of a memory
system is defined as the ratio:
Total memory requests
The total number of memory requests includes
those requests which are denied because of a
conflict such as a bank conflict. It is assumed
that when such a conflict occurs, the processor
attempts the reference on the next cycle. This
memory efficiency is measured from the view-point
of the processor. It indicates the degree
to which processors will be able to successfully
issue memory references. The efficiency is essentially
PA , the probability of acceptance, as
calculated by Briggs and Davidson [3] in their
models of L-M memories without buffering.
Following Sohi [21], the throughput is defined
as the ratio:
vector references in a conflict-free system
Actual time for vector references
Sohi argues that this ratio is the appropriate
throughput measure when comparing memory
designs in a vector processing environment.
The throughput is the fraction of the optimal
rate at which entire vectors are delivered
through the system. The vector element read
latency is defined as the time between the first
attempt to access a vector element and the
availability of that element at the vector register

The efficiency depends on the number of
processors, the number of banks, the bank cycle
time, and the load. Unbuffered designs for
multiprocessor machines give a quadratic relationship
between memory speed and number
of banks for fixed performance [1]. If the memory
cycle time is doubled relative to the processor
speed, the interconnection costs must
be quadrupled to maintain the same memory
performance. The proposed design is a two-tier
system. The results show that if the inter-connection
network bandwidth is sufficient to
support the processors using high-speed mem-
ory, then lower-speed memory with buffers can
be substituted for little additional interconnection
cost or performance degradation.
Section II describes the logical bank design.
An analytical model for writes is developed in
Section III and is shown to be in reasonable
agreement with random reference simulations
in Section IV. The relationship between the
efficiency and system parameters such as the
bank cycle time, number of banks and number
of processors is then analyzed. Several design
criteria are developed which are applied
in later sections to vector systems.
Section V introduces a simulation model
which uses synthetically generated references
for a vector multiprocessor system similar to
the Cray Y-MP. The model incorporates a
full data-path simulation including return conflicts
and register feedback as recommended
in the simulation study by Smith and Taylor
[20]. The vector results are compared with
model predictions under moderate processor
loading in Section VI, and it is shown that
even a small number of buffer slots can result
in significant gains in performance. In Section
VII the design criteria are applied to a 64-
processor system (192 independent reference
streams) under heavy processor loading for a
range of stride distributions. Performance for
writes is excellent, but there is degradation for
reads. Several approaches for reducing this
degradation are examined including subbank
output buffering, additional lines, optimal ar-
bitration, port handshaking, port-line buffers,
and increased return bandwidth. It is found
that only the last alternative completely eliminates
the degradation. A final discussion and
conclusions are presented in Section VIII.
II. Logical Banks
A logical bank [16] consists of a fast register,
the logical bank register (LBR), and a number
of subbanks each with a queue of pending
requests as shown in Figure 1. The memory
within the logical bank is divided into equal
subbanks and addressed using the standard
interleaving techniques so that consecutive addresses
go to consecutive subbanks. A reference
to the logical bank can be gated into the
LBR in T la cycles if the register is free. T la is
the logical bank access time. If there is room
in the queue for the specified subbank, the reference
is then routed to the queue. Otherwise,
the LBR remains busy until a slot is available.
Only one reference to a logical bank can occur
during an interval T l . T l is called the logical
bank cycle time. It is the minimum time interval
between successful references to a logical
bank. The interval may be longer if the LBR
is waiting for a queue slot. If reference streams
attempt to access the same logical bank while
the LBR is busy, a logical bank conflict occurs
and all but one reference is delayed. In
the model and all of the simulations discussed
later, it is assumed that T la .
The parameters which define a multiprocessor
system with shared memory organized
into logical banks are shown in Table 1.
The default values are used in later simulations
except where otherwise indicated. For
single-port processors the number of reference
streams, n, is also equal to the number of pro-
cessors. In the vector simulations, the processors
are allowed to have multiple ports so
there can be more reference streams than pro-
cessors. Reference streams are assumed to be
either read or write. Read streams are more
difficult to handle because values must be returned
to the processor. The return fan-in net-work
for reads requires additional hardware for
arbitration because read values do not arrive
at the fan-in network at a predictable time.
The return values must include tag bits indicating
the destination. This hardware is also
required if cached DRAMs are used since the
effective access time is no longer constant in
that case either. In fact, cached DRAMS can
be used in conjunction with logical banks to reduce
the effective physical subbank cycle time,
little additional hardware.
Logical banks were introduced by Seznec
and Jegou to support the Data Synchronized
Pipeline Architecture (DSPA) [19]. Their design
includes a reordering unit so that data
flows out of the logical bank in chronological
order. In the scheme proposed in this paper,
a reordering unit is not required at the logical
bank, because reordering occurs at the processor

Buffering is distinct from caching in that
there is no miss penalty and no overhead for
cache management. The proposed circuitry
would take up a very small chip area if it
were incorporated on a chip. Alternatively, it
could be built as an interface between off-the-
shelf memory chips and the system interconnection
network. It is particularly appropriate
in situations in which average utilization
is below maximum capacity, but where there
are periods of maximal loading. In addition
to reducing average access time, logical banks
can smooth the type of bursty memory traffic
which is typical of highly vectorized programs
[17].
III. A Model for Random Writes
A model for the efficiency of logical bank
memories is now derived. In later sections the
throughput and latency are related to the ef-
ficiency. It is assumed that a reference stream
can initiate at most one reference per clock cycle
and that when a reference attempt fails, it
is retried by that reference stream on the following
cycle. As long as the LBR is available,
the processor sees a memory consisting of logical
banks with a cycle time of T l , the logical
bank cycle time. The efficiency in this case is
given by E l . This efficiency is determined by
the interreference stream conflicts at the logical
bank level. When the queues are full, the
memory behaves almost as though there were
no logical banks. The effective memory cycle
time in this case is T
T d is the minimum delay incurred in transferring
a reference from the queue to the subbank
and T c is the physical memory cycle time. The
efficiency in this case is denoted by E p .
A simple probabilistic argument shows that
if the probability of a successful reference is E,
the expected number of attempts per successful
reference is:X
E)
is the average number of cycles that it takes
a reference stream to initiate a reference from
the viewpoint of the processor. In contrast,
the average reference time from the viewpoint
of the physical memory is directly related to
the bank cycle time and other delays.
Let P be the probability that the logical
bank register (LBR) is available when a reference
is first initiated. A successful reference
will take 1
attempts with conditional
probability P and 1
attempts with probability
. The effective efficiency is then a
weighted average of the two cases depending
on the probability that there are slots available
in the appropriate subbank queue. The
average number of cycles for a successful reference
can then be estimated by:E
where E is the combined or effective efficiency.
This relationship can be written as:
This expression for the effective efficiency will
be called the logical bank model in the remainder
of the paper.
The probability, P , that the LBR is not full
can be estimated by considering each logical
bank as a system of k independent queues under
the M/D/1/B queuing discipline. This
queuing model has an exponential arrival rate,
deterministic service time, one server, and a finite
queue. For fixed queue size, the distribution
of the number of references in the queue
depends on the parameter ae = -T p where -
is the average arrival rate and T p is the effective
queue service time. - can be estimated as
where q is the probability that a free
stream initiates a reference, n is the number
of independent reference streams, and b is the
number of physical subbanks (kl). A simple
simulation is used to compute a table of probabilities
for a given value of ae and queue size
m.
Once the probabilities that the individual
queues are free have been determined, the
value of P for the entire logical bank can be
estimated as follows. If there are k subbanks
per logical bank, the LBR will be busy if any
of the k queues has m+1 slots filled, the extra
slot being from the LBR itself. Thus, if f is
the probability that a queue of size m + 1 is
not full, then the probability that the LBR is
This method is used to calculate P
for the graphs given later.
Estimates for E p and E l will now be de-
rived. The situation in which there are no logical
banks has been analyzed for random accesses
by Bailey [1] for systems with n single-port
processors and b memory banks. Let T
be the memory bank cycle time. Each processor
can be modeled as a Markov chain on
the state in which the processor is waiting for
a bank which will be busy for i more cycles
and s 0 denotes the state in which a processor
derived a steady
state expression for the efficiency in such as
system as:
Here q represents the probability that a free
processor will attempt a reference on the current
clock cycle. For relevant values of T , n,
and b, the efficiency is dominated by the expression
in the square root:
r
The efficiency is inversely proportional to T
and drops off fairly rapidly. If the bank cycle
time is doubled, the number of banks must be
increased by a factor of four to maintain the
same efficiency. The Bailey model can be used
to estimate E p by using T
the bank cycle time:
The logical bank efficiency, E l , can also be
estimated using the Bailey model as
l is the number of logical
banks in the system. T l , the logical bank cycle
time, is assumed to be one for much of the discussion
in this paper. Due to the assumptions
made in the derivation of the Bailey model, it
performs poorly when there are a small number
of processors or when the bank cycle time
is near one. Unfortunately the effective efficiency
is very sensitive to the value of E l when
P is close to one, so another model will be developed
This model will
be called the direct model and is derived below
using Markov chains in a manner similar
to that used by Bailey.
Assume that each reference stream is in one
of three states: the free state (1), a state in
which it is making a successful reference (2), or
the state in which it is attempting a reference
which is unsuccessful (3). Let:
probability that a given free stream
will attempt a reference
probability that the stream is in the
probability that the stream is making
a successful reference
probability that the stream is making
an unsuccessful reference
probability that a reference attempt
will be successful
The following probability conservation equation
holds:
The matrix, \Gamma, of state transition probabilities
is given in Table 2. \Gamma i;j , the entry in the i-th
row and the j-th column, represents the
conditional probability that the next state is i
given that the current state is j.
A reference attempt will be successful if no
higher priority stream is making a reference
to the same bank. On the average half of the
remaining streams will have a higher priority
than a given stream. Since only one higher
priority stream can make a successful reference
to a bank, the probability that one of the
streams is making a
successful reference to one of l banks may be
estimated as:
2l
and so ffi is given by:
where:
2l
be the vector of a priori
probabilities of the three states. The steady
state probabilities, which can be obtained by
the relationship -
are then given by:
These equations plus the conservation equation
can be used to obtain an expression for
The direct model is in better agreement with
the simulations when T will be
used to estimate E l for the remainder of the
paper.
IV. Predictions of the Model
Buffering can produce fairly dramatic improvements
in efficiency provided that the
memory system is not close to saturation.
In this section, the logical bank model is
compared with model simulations for random
references. The excellent agreement of this
comparison validates the model and suggests
relationships between the design parameters
which are necessary for achieving a particular
level of efficiency. In the following sections a
vector simulation model is compared with the
random-reference model, and the relationships
suggested by the analytical model are tested.
Consider a multiprocessor system which has
independent reference streams and a shared
memory consisting of 256 banks. (These parameters
represent an eight-processor Cray Y-MP
with three ports per processor and a maximal
memory configuration.) The performance
of this system is now compared with that of an
augmented system in which each physical bank
is replaced by a logical bank consisting of a single
subbank with a queue size of two. This case
corresponds to adding buffering at the physical
bank level without adding any additional logical
bank structure other than the buffers and
the LBR. The reference streams are assumed
to generate writes only and T
In

Figure

2 the efficiency for random reference
streams is plotted versus subbank cycle
time. Following Bailey [1] a reference rate
of is selected to give a base operating
efficiency in the unbuffered case of :67. The
logical bank model agrees well with results
from scalar simulations for operating efficiencies
above :6. A significant improvement in
performance is observed with buffering. When
the bank cycle time is 18, the simulation shows
an efficiency of :22 without buffering and an
efficiency of :66 with buffering. (The memory
efficiency of a real Cray Y-MP is higher than
the predicted :67, because selected buffering
mechanisms are incorporated at various stages
in the Cray Y-MP interconnection network as
described by Smith and Taylor [20].)
In

Figure

3 the efficiency is plotted versus
the number of reference streams. Again there
is excellent agreement between the model predictions
and those of random reference simula-
tions. The base efficiency of :67 can be maintained
with as many as 96 reference streams
when buffering is introduced at the bank level.
The logical bank model overestimates the efficiency
near saturation because the M/D/1/B
queuing model assumes that references are
thrown away when the queues are full. The
processor attempts to initiate a reference on
the next cycle with a certain probability q ! 1.
In the real system and in the simulation the
reference is retained and tried again on the
next cycle.
A simple analysis is now presented which
shows that queue sizes which are quite small
can give substantial improvements in performance

Table

3 shows the probability that the
number of items in the queue is less than the
queue size, m, for different values of m and
different system loadings. If ae = :5, the probability
that a queue will have fewer than three
slots (two queue slots plus the LBR) filled
is :9731. This value is indicative that small
queues will suffice. The estimate may not be
completely accurate near saturation, because
references which are not fulfilled are thrown
away in the model. Hence, the infinite queue
case is now considered.
In the infinite queue model, references are
never blocked, but are always queued. The
expected queue size for each subbank in the
infinite queue case is [10]:
Ex(Queue
For ae ! :5, the expected queue size is less
than :25 for each subbank. Table 4 shows that
the probability that a queue contains no more
than x items in the queue for the infinite queue
case. The probability that two or fewer slots
are filled is :947 for This probability is
on the borderline of reasonable performance.
The probability of having four or fewer elements
in the queue is :9957. A subbank input
queue size of four should be adequate to handle
most references (P - 1), and the effective
efficiency will be E l .
For fixed load q, E l is constant for constant:
2l
Furthermore,
is obtained by noting that E l is a decreasing
function of both q and ffl. The condition ffl !
:1 means there should be at least five times
as many logical banks as there are reference
streams for efficient performance.
The buffered and unbuffered cases can be
compared in the case where there is one sub-bank
per logical bank so that
the effect of buffering on efficiency when
held constant at :5 as the sub-bank
cycle time and the number of banks are
both increased. In this paper it is assumed
that will be decreasing
since ffl only depends on the number
of processors and the number of banks. When
the queue size is four, the probability of a logical
bank hit is :9957 so the efficiency is approximately
l . Since E l is independent of T c
and is an increasing function of l = b, the logical
bank model predicts that the efficiency will
actually increase slowly as the bank cycle time
and number of banks are increased with ae held
fixed at :5. Thus, for a fixed reference rate, q,
a doubling of T c , can be compensated for by
doubling the number of banks or by halving
the number of processors (reference streams).
This is in contrast to a system without logical
banks where T c
b must remain fixed to
maintain the same efficiency. In systems without
logical banks one would have to quadruple
the number of banks in order to compensate
for doubling the bank cycle time. When the
above argument is applied to the same system
with a queue size of two, the probability of a
logical bank hit is at least :947. The efficiency
is now a weighted average of the relatively constant
logical bank efficiency, E l , and the unbuffered
efficiency, E p . (The latter efficiency
drops off rapidly with bank cycle time.)
To confirm these relationships in the models
with and without logical banks, the load
q is fixed at :4, and the number of reference
streams is fixed at 24. In Figure 4 the efficiency
is plotted versus the subbank cycle time
when the number of banks is varied so that ae
is held constant at :5. The logical bank model
maintains an almost constant efficiency as the
bank cycle time is increased as predicted for
queue size of four. The system with queue
size two shows a slight fall-off. The efficiency
is initially lower than the asymptotic value because
when the bank cycle time is small and ae
is held at :5, there are so few banks that logical
bank conflicts become significant. When
the Bailey model is run for the same parameter
values, the efficiency drops dramatically as
predicted by the model. Similar scaling relationships
can be derived when the bank cycle
time is fixed and the number of banks and the
number of reference streams are varied.
One can use the relationship between ae and
E to determine design parameters required to
achieve a specified level of performance. The
Cray Y-MP has eight processors and three
ports per processor (24 independent reference
streams), a bank cycle time of five, and 256
physical banks. If a maximum reference rate
of
1+ffl . With a queue size of four, the probability
of a logical bank hit is nearly one. The
efficiency can be simply estimated from the
previous expression for ffl. When there are 256
logical banks (one subbank per logical bank),
:92. The logical bank model
predicts that buffering with four queue slots
will result in a high efficiency. The unbuffered
efficiency is predicted by the Bailey model for
these parameters to be :56. These model predictions
are tested in Section VII for a vector
simulation.
The results of the logical bank model can
be summarized as follows. For a fully loaded
system consisting of n reference
streams, l logical banks, a logical bank cycle
time of one, and subbank input queue size of
four, the efficiency is greater than :90 provided
ae -
and
For a queue size of two, ae should be chosen to
be less than :2.
Notice that the first relationship depends
on the total number of subbanks, b, while the
second relationship depends on the number of
logical banks, l. The per processor interconnection
costs depend on l. As long as there
are enough logical banks to adequately field
requests from the processors, an increase in
bank cycle time can be compensated for by
an increase in the number of subbanks without
a significant increase in the interconnection
costs. There is a point, however, at which
the data bus arbitration scheme will not be
able to handle read return traffic. This point
is discussed more fully in Section VII.
An increase of T l above one has the effect of
lowering the overall efficiency, but the curves
have the same shape. Design parameters can
be determined in this case by using the Bailey
model to estimate E l when
The efficiency now depends on the parameter
An efficiency of :90 can be
obtained provided that
V. Vector Simulation Model
In order to test the performance of the logical
bank organization and the predictions of
the logical bank model, a simulation study
based on the Cray Y-MP architecture inter-connection
network was developed. The Cray
Y-MP architecture was selected because its
highly pipelined interconnection network can
provide an effective T l = 1. This is accomplished
by having references issue immediately
to the interconnection network and block later
if conflicts should arise. A complete data path
simulation of this system with processor register
feedback was performed with reference
streams which were generated randomly under
realistic assumptions. The simulation includes
ports, lines, sections, and subsections
as described below.
The vector simulation model assumes there
are n p processors each with p ports. Each processor
can initiate up to p memory operations
on a cycle. These ports are assumed to generate
independent reference streams (n
Each port is designated either as a read stream
or a write stream.
The interconnection model is a simplified
version of the network described by Smith
and Taylor [20]. Each processor has four
lines which are direct connections to particular
sections of memory. The ports from a
particular processor access memory through
a crossbar connection to the processor's four
lines. The section number is determined by
the lowest two bits of the address, so consecutive
references are directed to different
sections of memory. Each section is divided
into eight subsections and the individual sub-sections
are further subdivided in banks. In
the case of the Cray Y-MP which has 256
banks, each subsection contains eight banks.
Following the notation of Smith and Taylor,
this interconnection network is denoted by:
8 processors !4 \Theta 4!8 \Theta 8 !1 \Theta 8 ! 256 memory banks.
In simulations of systems with n p processors
and l logical banks, the number of sub-sections
is fixed at eight and the number
of banks per subsection is increased. The
interconnection can then be described by:
np processors !4 \Theta 4!np \Theta 8!1 \Theta l=8!l memory banks.
In the Cray Y-MP, a processor can access
a particular subsection once every T c cycles
where T c is the physical bank cycle time. This
means that when a processor accesses a memory
bank, the processor is blocked from issuing
additional references to the entire subsection
containing this bank for the full bank cycle
time. Such a conflict is called a subsection conflict
and, like the section conflict, is strictly an
intraprocessor conflict. References from different
processors to the same subsection can proceed
without conflict provided that they are
addressed to banks which are not already in
use.
The simulation for the logical banks is based
on the conflict scheme described above. When
a particular memory location is referenced, the
line, subsection, logical bank, and subbank
numbers are calculated. If the line is free, it
is reserved for T r cycles and the subsection is
checked. If the subsection is free, it is reserved
for T s cycles, and the logical bank is checked.
If the logical bank register (LBR) is free, it is
reserved for T l cycles and the reference is initi-
ated. The reference generates a hold and fails
to issue if a conflict occurs at any level.
Once a reference has occupied the LBR for
l cycles, it can be moved to the appropriate
subbank queue if that queue is not full.
The reference must spend T d cycles in the
queue before it can be processed by the physical
memory. It is assumed that the reference
must occupy the subbank for at least T c cycles
before the subbank can accept another refer-
ence. If the operation is a write, the subbank
is free to accept another reference after T c cy-
cles. Reads are complicated by the return trip
to the processor as now described.
A vector read reference is not considered to
be completed until all of the element values
have arrived at the processor. Read data values
must be routed from the physical memory
bank to the appropriate processor vector reg-
ister. Additional conflicts may occur because
more than one value may become available on
a particular cycle. Each logical bank has a
single output latch. If the latch is free, the
value is moved from the subbank to the latch
and the subbank is freed. If the latch is busy,
the subbank must wait until the latch is free
before accepting another value. If an output
queue is included for each subbank as shown
in

Figure

1, the value is moved from the sub-bank
to the output queue and blocking of the
subbank due to return conflicts is less likely to
occur.
All of the data values latched for a particular
processor line compete for processing on
the return interconnection network. The real
system has separate forward and return inter-connection
networks. To simplify the simu-
lation, the return interconnection network is
modeled as a pipeline which can accept one
value per section per cycle. The pipeline
length is assumed to be ten which accounts
for the length of both the forward and return
pipelines. When the last value for a vector
read has emerged from the pipeline, the read
is considered to be complete.
The simulation also incorporates the feed-back
loop between the vector registers and
memory. Each processor has a certain number
of vector registers (eight was assumed for
the runs in this paper). When a vector operation
is initiated in the simulation, a free
processor vector register is randomly selected
and reserved for the duration of the operation.
If no register is available, the operation holds
until a register becomes available. The register
reserved for the operation is not freed until
all of the elements of the vector have arrived
at the processor. In contrast a vector write is
considered to be completed when the last element
operation has been issued. The vector
register is freed at that time although the actual
memory value may not be inserted until
sometime later because of buffering.
Priority in the simulation is rotated among
the processors in a circular fashion so that no
processor is favored. This scheme is similar
to the priority scheme used on the Cray X-
MP. The Cray Y-MP uses a fixed subsection
priority scheme which does not lend itself to
modification when the number of processors is
varied. The priority scheme should have little
effect on the results of the simulation.
The simulation generates a representative
reference stream for vectorized code as described
below. All memory operations are assumed
to be vector operations with an associated
stride and length. Gather/scatter operations
are not considered in this simulation.
The stride is a fixed interval between successive
references within a single vector opera-
tion. A stride of one is assumed to be the most
probable with other strides up to a maximum
stride being equally probable. A default probability
of stride one vectors of :75 is used unless
otherwise indicated. The effect of type of load
on performance is examined in Section VII.
The maximum length of the vector operations
is determined by the length of the vector
registers in the processor. When an operation
on a very long vector is required, the compiler
splits it into several vector operations,
all but one of which uses the maximum vector
register length. All possible vector lengths
are assumed to be equally probable, except the
maximumlength is assumed to occur more frequently

The system load is determined by the operation
initiation rate. When a port is free
there is a certain probability, p f , that on the
current cycle a memory operation will be initi-
ated. The value of p f may be different for read
and write ports and is a measure of the system
load. A relationship between p f and the
scalar reference rate q is now derived in order
to compare the vector case to the scalar case
already discussed. Let VL be the maximum allowed
vector length and p l be the probability
of a maximum length reference. The average
length of a vector reference is then:
and :0118. The value used by
Bailey [1] in his calculations of efficiency for
the unbuffered case. A study of interreference
times for vector references for the Perfect Club
Benchmarks run on a Cray Y-MP [18] shows
typical interreference times on the order of 10
to 200 cycles, so a value of appears
to be reasonable.
The parameters used in the simulation are
chosen to be close to the current Cray Y-MP
values and are summarized in Table 5.
The scalar simulations performed in Section
IV were performed by setting
In the unbuffered case, T l is the physical bank
cycle time as seen by the interconnection net-work

The vector data path simulator was written
in C and run on a network of SUN worksta-
tions. Most of the vector simulations done for
this paper were run for one hundred thousand
cycles, although some runs were as long as ten
million cycles. Each run was divided in blocks
of cycles and the statistics were computed over
each block in addition to over the entire run.
The statistics for the longer runs did not vary
significantly from those of the shorter runs.
This lack of variation is not unexpected since
each port on each processor can initiate a reference
on each cycle so there are a large number
of independent reference streams over which
the statistics are averaged.
VI. Results for Moderate Loading

Figure

5 shows a comparison of the efficiencies
as a function of bank cycle time for
the vector simulation and the logical bank
model when the system has eight processors
and three ports per processor. The number
of logical banks is fixed at 256 with one sub-bank
per logical bank and the queue size is four
slots per subbank. Buffering delays the drop in
performance with increasing bank cycle time.
For example, when all vectors have stride one
and the bank cycle time is 20, the efficiency
is :92 with logical bank buffering and
:22 without buffering. The agreement between
the simulation and the logical bank model is
good for subbank cycle times less than 10.
The agreement between model and simulation
is better for loads which have a random
component. The case where three fourths of
the strides are one and the remainder are randomly
distributed (p shown in

Figure

5. In this case, the efficiency is :68
for a subbank cycle time of 20. The over-all
efficiency is slightly below the model, but
the fall-off occurs in roughly the same place
as predicted by the model. The logical bank
model, which corresponds to random reference
streams, falls in between the simulations
for the two different stride distributions. The
agreement between the logical bank model and
the vector simulation is quite good considering
that the vector simulation includes lines, sub-
sections, and register feedback. The dip in efficiency
at bank cycle times which are integral
multiples of four is a real phenomenon which
is preserved over very long simulation runs.
In

Figure

6 the efficiency is plotted versus
the number of reference streams when the sub-bank
cycle time is five. The remaining parameters
are the same as in Figure 5. The
number of reference streams could be quadrupled
from 24 (eight processors) to 96 (32 pro-
cessors) while still maintaining an efficiency of
:67.
The analysis of Section IV for random references
predicts that the efficiency will be high
and will increase slightly as the number of
banks and the bank cycle time are increased
keeping n=b constant at a value - :5.
This scaling relationship holds in the case of
vector references as well. In Figure 7 the number
of reference streams is fixed at 24 (eight
processors) and the number of subbanks per
logical bank is one. The number of banks is
varied linearly with the bank cycle time in order
to keep ae constant at :5. The condition
satisfied when the number of logical
banks is greater than 120 which is the case
provided that T c ? 3 for ae held constant at :5.
For comparison, a simulation with the same
set of parameters was run without buffering
and the efficiency dropped dramatically when
the subbank cycle time was increased. The
runs are shown for two stride distributions (p s
The previous vector runs were performed
with no read ports. In an unbuffered memory
there is no difference in memory efficiency between
reads and writes. Because buffering introduces
unpredictable delays, more than one
result can become available on a particular cycle
for the interconnection network for a particular
section. When conflicts of this type
arise, some of the references are delayed which
in turn causes subbanks to block. Return
conflicts can thus cause an effective increase
in bank cycle time and a corresponding drop
in efficiency. The addition of a single output
queue slot at each subbank eliminates the
difference in performance between reads and
writes for moderate loading. However, as the
load is increased (either through increasing the
initiation rate or the percentage of stride one
vectors), the port return bandwidth may be
insufficient to handle the load. This problem
is addressed in the next section.
The analytical model derived in Section
III predicts the efficiency of memory writes.
Other possible indicators of performance include
throughput and latency. The through-put
defined in Section I is the fraction of the
optimal rate at which entire vectors are delivered
through the system [21]. The vector
element read latency is defined as the time between
the first attempt to access a vector element
and the availability of that element at
the vector register.

Figure

8 compares the efficiency, through-
put, and read latency when the load is varied.
A bank cycle time of 20 was chosen because
it is near the knee of the curves in Figure 5.
The parameters are the same as in that figure
except that the bank cycle time is fixed
and the initiation rate is varied. Probability
of OP (p f ) refers to the probability that
a vector operation will be initiated by a free
port. The value corresponds to the
value in Figure 5. The throughput is slightly
higher than the efficiency in the unbuffered
case and slightly lower than the efficiency in
the buffered case. The buffered throughput is
still considerably better than the unbuffered
throughput.
In the unbuffered case, the read latency is
just a constant plus the number of attempts
it takes to issue the request. As mentioned
in Section III, the number of attempts is just
the reciprocal of the efficiency. In fact, in the
unbuffered case the read latency curve in Figure
8 can be predicted to better than .3 percent
from the efficiency curve. When
the unbuffered read element latency is 36 and
the buffered read element latency is 51. If the
efficiency is at least moderately good, this indicates
that the last element of a vector read
is delayed about 15 cycles over what it would
be without buffering. With buffering, the read
latency is affected by return conflicts, and so
is dependent on the return scheme used. Different
return schemes are discussed in the next
section.
Since writes do not require a return path,
the write element latency is directly related to
the number of attempts to issue the element
operation. The write latency curves (not
shown) can be predicted from the efficiency
curve to within a few percent for both the
buffered and the unbuffered case.
VII. Results for Maximal Loading
The extreme case where each port attempts
a memory reference on each cycle is now con-
sidered. First an analysis is done for writes.
The logical bank model is used to pick design
parameters for a 64-processor system. The
performance for reads is then analyzed and improvements
in the return interconnection net-work
are considered to equalize the performance
of reads and writes.
The logical bank model can be used as a
guide in picking design parameters for a 64-
processor Cray Y-MP which minimizes the per
processor interconnection cost, while achieving
an efficiency of at least :90. Assuming a load
of 1:0, the condition ffl ! :1 gives
l ? 960. Assuming a bank cycle time of five,
the condition ae ! :5 gives b ? 1920. The number
of logical and subbanks should be powers
of two. Thus for 64 processors, the configuration
which operates with minimum per processor
interconnection cost and high efficiency
has 1024 logical banks and 2048 physical sub-
banks. If ae is approximately :5, a queue size
of four is required to have a :99 probability of
available in the queue according to

Table

4. If the queue size is two, four subbanks
per logical bank are required to bring ae down
to :3.

Figure

9 shows the performance of these designs
as a function of the percentage of stride
one vectors. The case of two subbanks per
logical bank with a queue size of four is indistinguishable
from the case of four subbanks
per logical bank with a queue size of two as
predicted by the logical bank model. The
case of 2048 banks with a queue size of two is
shown for comparison. The logical bank model
is based on the assumption of random references
and does not account for the presence of
bad strides. Buffering has been shown to reduce
the effect of bad strides under moderate
loading [7], and the designs here do not preclude
the use of address mapping to alleviate
intraprocessor conflicts [5,8]
Reads are more difficult to handle because
hot spots can develop on the return lines as
shown in Figure 10. The performance difference
between reads and writes as a function of
stride is quite dramatic. Even more surprising
is the fact that the performance for reads
actually drops as the percentage of stride one
vectors in the load is increased. The drop occurs
because the arbitration method used for
the return in the simulations is a simple round
robin priority scheme on the logical banks.
When a reference for a particular port is de-
layed, it causes all of the banks waiting for that
port to be delayed. When the system is operating
at a sustained maximal initiation rate,
the ports can never catch up.
Various solutions for solving the hotspot
problem have been examined including additional
output buffering at the physical sub-
banks, additional lines, optimal arbitration,
port handshaking, port-line queues, and additional
return ports. It was found that additional
lines alone do not solve the problem,
while queue depths of or more at each sub-bank
are required to make a significant difference
in efficiency.
In optimal arbitration, the logical banks are
examined in round robin succession, but if the
port to which a reference is made is already in
use, that reference does not block the line and
another reference can be issued. Port hand-shaking
is a control mechanism by which a particular
port is blocked from initiating a reference
if there was a return conflict for that port
on the previous cycle. Both methods improve
performance, but they do not bring read performance
up to write performance when most
of the vector strides are one.
Since the drop in read performance appeared
to be due to insufficient return port
bandwidth, two alternative approaches were
developed to increase the bandwidth. The first
approach involved adding port-line queues. In
this design modification, each port contains a
queue for each line so that each line can deposit
a result at a port on each cycle. The
port services one queue per cycle in round
robin succession. The second approach involved
doubling the number of return ports.
One possible design is to have a return port
for the odd-numbered vector elements and another
return port for the even-numbered vector
elements. An alternative design is to designate
one return port for each pair of return
lines. The second alternative would simplify
the port-line interconnection switches but
would complicate the vector register bus structure
internal to the processors.

Figure

11 compares the port-line buffering
to double-return ports for a variety of
strides at maximal loading. Output buffering
at the subbanks has been eliminated. Port-
line buffering improves efficiency but does not
increase the port bandwidth. The doubling
of the number of return ports brings the read
efficiency in line with the write efficiency.
VIII. Discussion
The main result of this paper can be summarized
as follows. If a shared memory system
has sufficient bandwidth to achieve high efficiency
with fast memory, the replacement of
the physical banks by logical banks will allow
the same efficiency to be achieved using considerably
slower memory without significantly
affecting the interconnection costs. This type
of buffering is particularly useful in vector
multiprocessors because vector memory operations
are naturally pipelined, and increases
in memory latency can be partially amortized
over an entire vector operation.
The logical bank model and the detailed
vector simulations given in this paper show
that the number of logical banks scales with
the number of processors and that the bank
cycle time scales with the number of physical
banks. Consequently slower memory can
be used if the logical banks are divided into
more subbanks. This is in contrast to the unbuffered
case where b=T 2
c n must be constant
for constant efficiency. The change from an
inverse quadratic to an inverse linear dependence
between bank cycle time and the number
of banks is particularly important.
A drawback of memory systems with variable
bank cycle time is that the values become
ready for return at unpredictable times. The
approach of Seznec and Jegou to reorder values
at the bank level does not solve the problem
of values arriving at the processor in the
order issued. The problem can be addressed
in the Cray Y-MP architecture by the addition
of a tag to each return value. The Cray
Y-MP architecture allows three independent
vector memory operations to proceed simulta-
neously. These vector memory operations can
be chained to the vector registers, and vector
registers can in turn be chained to functional
units. Chaining allows the results produced by
one vector operation to be used as input to a
succeeding operation before the first instruction
has completed. The component results
from the first instruction can be used by the
second instruction as they become available.
Pipeline setup can occur before any component
of the previous operation is available [15].
In the current architecture values arrive in order
so each vector register keeps track of the
last value to have arrived. When the values
arrive out of order each vector element must
have a bit indicating whether that value has
arrived. Some additional hardware can be incorporated
to chain forward when the next element
has arrived. The relative order among
different registers is assured by the existing
reservation and issue mechanisms.
It is well known [1] that the memory performance
of shared memory vector processors is
strongly dependent on the type of load which
is generated. Since the choice of load distribution
affects the results, it is desirable to
test the design against realistic loading con-
ditions. Address-trace collection methods [22]
are useful for generating statistical information
about the load, but the information collected
from these types of investigations is difficult
to use directly in testing new designs because
the efficiency depends not only on the
actual addresses, but on the exact time the
references were issued. Because of these diffi-
culties, the approach taken in this paper has
been to develop guidelines which are applicable
over a range of load distributions. The
larger the number of reference streams, the
less serious the impact of the details of one
reference stream on the overall efficiency.
Buffering greatly reduces the dependence
of memory efficiency on the type of load for
writes as illustrated by the runs in the two
previous sections. Most of the dependence on
load occurred because of return conflicts for
reads. A number of alternative designs were
evaluated in an effort to reduce the performance
degradation due to return conflicts. It
was found that doubling the number of return
ports eliminated the difference between reads
and writes over a range of loads.

Acknowledgment

This work was supported by Cray Research
Inc. Computational support was provided by
the University of Texas Center for High Performance
Computing and the National Science
Foundation ILI Program, Grant USE-0950407.



--R

"Vector computer memory bank contention,"
"Effects of buffered memory requests in multiprocessor systems,"
"Or- ganization of semiconductor memories for parallel-pipelined processors,"
"Enhanced dynamic RAM,"
"A simulation study of the Cray X-MP memory sys- tem,"
"A fast path to one memory,"
"Vec- tor access performance in parallel memories using a skewed storage scheme,"
"Address transformations to increase memory performance,"
"Dynamic RAM as secondary cache,"
The Art of Computer Systems Performance Analysis
"A 12-MHz data cycle 4-Mb DRAM with pipeline operation,"
"The prime memory system for array access,"
"Scrambled storage for parallel memory systems,"
"Synchronous dynamic RAM,"
The Cray X-MP/Model 24: A Case Study in Pipelined Architecture and Vector Pro- cessing
"Bus conflicts for logical memory banks on a Cray Y-MP type processor system,"
"Dynamic behavior of memory reference streams for the Perfect Club benchmarks,"
"Charac- terization of memory loads for vectorized programs."
"Optimizing memory throughput in a tightly coupled multiprocessor,"
"Accurate modeling of interconnection networks in vector supercomputers,"
"High-bandwidth interleaved memories for vector processors - a simulation study,"
"Address tracing for parallel ma- chines,"
--TR

--CTR
Hua Lin , Wayne Wolf, Co-design of interleaved memory systems, Proceedings of the eighth international workshop on Hardware/software codesign, p.46-50, May 2000, San Diego, California, United States
A. M. del Corral , J. M. Llaberia, Minimizing Conflicts Between Vector Streams in Interleaved Memory Systems, IEEE Transactions on Computers, v.48 n.4, p.449-456, April 1999
Toni Juan , Juan J. Navarro , Olivier Temam, Data caches for superscalar processors, Proceedings of the 11th international conference on Supercomputing, p.60-67, July 07-11, 1997, Vienna, Austria
Anna M. del Corral , Jose M. Llaberia, Increasing the effective bandwidth of complex memory systems in multivector processors, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.26-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
logical memory banks;buffered memories;vector processors;Cray Y-MP;memory conflicts