[MUSIC PLAYING]
The Cray T3D system is the first of a new generation
of supercomputers from Cray Research based
on the principles of massively parallel processor design.
This lecture will describe architectural and hardware
implementation aspects of the Cray T3D.
A second tape in this series will
describe the system software and application software
environments.
This new family of supercomputers
complements the highly successful line
of Cray parallel-vector processing systems.
Those products, the most recent of which
is the Cray C90 and its dependents,
have roots tracing back to the original Cray-1.
The Cray-1, a universally accepted guidepost
for the industry, was designed by Seymour Cray
and introduced in the marketplace in 1976.
Significant changes have occurred since those early days
at Cray Research.
Most compelling are the great advances
in the integrated circuit density and speed.
These advances have spawned multiple generations
of microprocessors and inexpensive semiconductor
memory.
In fact, the latest microprocessors
now challenge the performance claims of the original Cray-1,
but at a small fraction of the cost.
By combining this microprocessor technology with advanced Cray
proprietary integrated circuit, packaging,
and cooling technology, the Cray T3D has been designed to solve
highly parallel, vary-compute, and I/O-intensive problems.
The Cray T3D is a multiprocessor system,
scalable up to configurations of 2,048 processors.
It operates in a heterogeneous parallel-vector
and massively parallel environment.
The Cray T3D supports a globally addressable, physically
distributed memory subsystem.
I/O is also scalable via I/O gateways, which
support high-bandwidth proprietary channels connected
to Cray parallel-vector systems and dedicated I/O processors.
The configuration supports a high degree
of concurrency to achieve high efficiencies
from the computational and data motion resources.
Scaling options allow varying subsystem configurations
across a wide range.
These options allow parallel-vector production
environments to explore the potential of MPP systems.
Others who have optimized MPP applications in hand
will configure their systems with the majority
of the resources on the MPP side.
Closely coupling the MPP with proven parallel-vector
technology serves several purposes.
Moving MPP technology into the production environment
requires a host of operating system services.
In the parallel-vector environment,
Cray has more than a 10-year development investment
in our supercomputer variant of Unix, which we call UNICOS.
By adding microkernel technology on the MPP side of it,
it has been possible to maximize MPP OS
functionality and stability and minimize time to market.
It is well-known that moving applications onto MPP platforms
can be a daunting task.
The heterogeneous configuration allows an environment
in which an application programmer
can manage the work in a staged, incremental way.
Finally, the closely coupled connection
between the parallel-vector system and the Cray T3D
allows new opportunities for high-performance computing.
There have been recent reports of applications
which have portions of code that map best on the MPP,
while other portions of the code do better
on the parallel-vector platform.
The end result can be performance which outpaces
either component working alone.
The Cray environment will support
efficient heterogeneous computing
using the Parallel Virtual Machine software technology.
PVM was originally developed through
a three-way collaborative effort of researchers
at Oak Ridge National Laboratory,
the University of Tennessee, and Emory University.
The Cray T3D compute and I/O nodes
are interconnected with a three-dimensional toroidal
switch.
The switch is designed for very high bandwidth and extremely
low latencies, setting a new standard
for massively parallel switch design.
The switch supports independent bidirectional paths
to nearest neighbors in each of the six directions, which
can be thought of as up, down, north, south, east, and west.
A seventh pair of paths provides connectivity
to the compute resources associated with the node.
The switch manages a peak input flux and, of course,
an equal output flux of 16.8 gigabits
or 2.1 gigabytes per second.
Unidirectional switch and wire latency
for a two-byte-wide packet fit for physical unit
is typically 13.3 nanoseconds.
When routing requires a corner turn,
there's only an additional 6.7 to 13.3 nanoseconds of delay.
What kinds of problems have the potential
to capitalize on the computing power delivered
by large numbers of processors numbering
in the hundreds or even thousands?
While we are interested in delivering
a high degree of sustained as opposed to peak
performance for real-world applications,
the most important objective must
be in reducing the time to solution.
The problem and selected algorithm
must, of course, be highly parallel.
As is well-known, Amdahl's law observes that for practical
problems, the total execution time will consist of a parallel
portion parceled out to a collection of processors,
plus a serial portion which cannot be performed
in a parallel manner.
If large numbers of processors are frequently
forced to wait for the computation of data coming
from a single processor in the system plus the additional time
required to distribute that data,
the actual benefit of the large numbers of processors
will be reduced.
At some point, adding more processors
is no longer cost-effective in reducing the time to solution.
Even for a problem which is 95% parallel,
one cannot expect speedups beyond 20,
even with an arbitrarily large number of processors.
Massively parallel or MPP systems
of hundreds of processors require problems that
are more than 99% parallel.
The problem design should not only be highly parallel,
but it should exhibit high algorithmic efficiency.
Each calculation should be effectively moving the problem
toward the solution.
A high sustained floating-point operation rate
is diminished in value if the algorithm demands
many more intermediate results than a competing
algorithmic choice.
Third, it must be possible to efficiently move dependent data
to requesting processors.
This communication overhead can have
the same effect as the serial portion of the computation.
Here, we are interested in algorithms
which require only modest amounts of interprocessor
communication or which allow mechanisms in design
to effectively make the latency transparent.
This is accomplished by hardware and software prefetching
techniques.
The importance of each of these criteria--
algorithmic efficiency, a high level
of parallelism, and moderate or transparent processor
communications--
can be mitigated by selecting ever-higher-performing
processors and communication networks.
But in the real world, users are also
concerned about price performance.
It would be terrific if we could design a system consisting
of 1,000 processors each with gigaflops of performance,
an interprocessor network that delivers tens of gigabytes
per second of data flux for each processor,
and interprocessor latencies below 100 nanoseconds.
The problem today is that such a system, if it could be built,
would be outrageously expensive.
This will no doubt be less true tomorrow.
Today, however, we are faced with a series
of important architectural and technology trade-offs.
Properly made, there is vast potential
for improving the price performance
of challenging and grand challenging problems
having the characteristics just described.
The rest of the story then will take you
through the series of architectural and technology
choices and trade-offs made by the designers of the Cray T3D.
Three distinct kinds of parallel programming models
and the accompanying high-level language
constructs to support them have evolved.
These models are data-parallel, message passing,
and work sharing.
Data-parallel models use a limited, often single control
flow within a system to control a very large data set.
Data communication is usually specified implicitly
in the high-level language using, for example, naming,
which references entire arrays of data.
Interaction among individual data elements
is masked by high-level operators,
such as matrix multiply, transpose, or inversion.
Message-passing models recognize distinct data
domains which may represent real domains in the problem space
or which may just be artifacts of the organization
of the computer system itself.
In any case, explicit communication sequences are
specified-- indeed, required--
which serve to move data and also provide
a low-level synchronization function.
The third model is work sharing.
The emphasis here is on implicit data motion requests
automatically invoked by the use of variables
representing a fine degree of granularity.
The naming can effectively specify and use
arrays, array elements, and scalars.
Multiple control flows are supported through a rich set
of synchronization primitives.
The objective here is to keep a high percentage
of the processing cycles actively performing real work.
Without applications, particularly
third-party applications, no supercomputing system
can be broadly successful in the marketplace.
Although application development remains in an immature state,
the variety of applications which do exist
and which must be supported for market success
use all three models, data-parallel, message passing,
and the emerging work-sharing model.
The Cray T3D was designed to efficiently support all three.
Let's turn our attention to the variety
of architectural and implementation
choices for massively parallel processor design.
It is expected that for highly parallel problems,
significant performance gains will
come from large numbers of processors working together.
But there are two distinct ways this cooperation
might be enforced.
The collection of processors could
follow the Single Instruction, Multiple Data or SIMD model
or the Multiple Instruction, Multiple Data
model, the MIMD model.
In the first case, each processor
operates in lockstep with all other processors
in the partition, but with different parallel data sets.
In the second case, MIMD, each processor
follows its own control flow, executing from a distinctly
different instruction stream.
SIMD designs are a good match for data-parallel models
and can be somewhat simpler to program.
On the other hand, they suffer from inefficiencies
when, for example, sparse matrix data
is being manipulated in rather naive ways
with lots of multiplications or additions of 0 operands.
Although the operation count may be high,
the algorithmic efficiency for this example is low.
MIMD systems provide many more degrees of freedom,
with-- conceptually-- each processor
operating from distinctly different optimized control
stores.
In practice, however, the computation
would probably be broken up into a handful
of computational domains.
There may, for example, be separate code
to simulate a physical structure's
interior and, separately, its boundary regions,
whereas synchronization is implicit for the SIMD model,
with all parallel calculations occurring simultaneously.
It is necessary for the MIMD case
to manage more explicitly the limited interaction
among processors.
This adds to complexity at the application programmer
or at least the compiler designer level.
Nevertheless, the opportunity for high real performance
has caused almost every MPP vendor
to concentrate on MIMD designs.
And the Cray approach is no different.
The Cray T3D is a multiple instruction, multiple data
design.
The next important choice involves
the way in which memory and, ultimately, data
is shared among processors.
Parallel-vector systems from Cray Research and others
use a uniform access physically shared memory implementation.
With this approach, the processors and the memory
subsystem form two distinct and physically separated
resource pools.
All processors compete more or less equally for access
to each location in the memory subsystem.
The latency each processor sees is also
approximately equivalent.
Although not fundamental to the physically shared design,
the communication paths between the processor partition
and the memory partition are often highly optimized
for high bandwidth and low latency,
adding significantly to the supercomputer system cost.
Unfortunately, such system organizations
do not scale well to large numbers of processors,
because the required number of independent data paths
grows exponentially.
The non-uniform physically distributed memory model
provides a much more scalable solution,
with each processor located physically nearby a set
of memory devices.
The processors can then have preferential access
that is lower-latency and/or higher-bandwidth
to the nearby memory.
The non-uniform memory access model
can provide a much more cost-effective solution
for parallel algorithms that emphasize
a high degree of local computation
and only moderate amounts of global data movement,
whereas the high degree of connectivity
in the uniform access memory system
may be underutilized a significant part of the time.
The Cray T3D utilizes the non-uniform physically
distributed memory model in its construction.
However, through its memory addressing mechanism,
it, in a logical sense, preserves the concept
of memory sharing, allowing the Cray T3D to operate
as a true multiprocessor.
Many MPP systems to date have been
designed as multi-computers, not multiprocessors.
Interprocessor communication must depend upon explicit
I/O-based requests.
Data moving from one processor to another
must pass through the I/O ports of the processors.
This usually requires the use of processor interrupt mechanisms
and even intervention by the operating system.
The target processor must decode or interpret
via software techniques the address tag
and the purpose of the message to determine the exact source
or destination for the payload.
This results in significant increases
in latency for the interprocessor communication
process.
A multiprocessor, on the other hand,
provides direct paths to each memory location
within the entire processor pool partition.
Addressing is managed through a single global address space.
On the target end of the transfer,
the data communication mechanism does not
interrupt the processor, but proceeds directly
via hardware support to that processor's local memory.
Because network communication within less efficient
multi-computers lacks a unique global addressing mechanism
and also requires processor intervention
on each side of the transfer, the programming models
on these systems are dependent upon the message-passing model.
For a multiprocessor system, however,
a true work-sharing model can be implemented.
The specification of data using a high-level language,
whether local or global, can be consistent.
Memory references local or global at the hardware level
are direct, with very low overhead.
It is very important, however, for the Cray T3D to effectively
support message passing.
And it does.
Explicit message-passing send and receive
requests are translated to allow at the lower hardware
level actual data movement to progress
through the multiprocessor memory protocols.
Let's concentrate now on the interprocessor data
communication network to provide motivation for the network
topology and switch characteristics selected
by the Cray T3D designers.
Access by processors to the local memory
on the same node results in preferential treatment,
with higher bandwidth and lower latency,
than access to memory locations residing in neighboring nodes.
When making trade-offs among resources
spent on local versus global traffic,
support for locality of data has priority.
We have seen that the Cray T3D is a true multiprocessor.
Although processors own local memory resources,
that memory appears logically as part
of a larger globally addressed physically distributed
shared memory subsystem.
Although the objective in programming for a distributed
memory system should always be to maximize
the occurrence of local calculations
and thereby minimize global traffic,
it is nevertheless helpful to minimize,
within reason, global latency.
We give this priority because a certain amount
of global communication for real-world problems
is unavoidable.
But we want more than low latency.
We also want to include mechanisms
which allow the system to hide latency
whenever possible through invocation
of prefetch mechanisms.
Network paths should obviously be
high-bandwidth within the constraints of system cost
trade-offs.
The Cray T3D achieves both low latency and high bandwidth
by using true supercomputer technology.
Microprocessor shell and network switch logic
are clocked by a single synchronous 150-megahertz clock
distribution network.
Market requirements for massively parallel systems
dictate support for a wide range of system sizes
with incremental pricing structures.
The network must be scalable, with a fairly linear increase
in cost to match linear increases
in the number of processors.
Fault-tolerant features must be considered when designing
the switching network.
Reconfiguration can allow masking of hardware faults
until scheduled maintenance, increasing system availability.
Finally, the system architect should
be aware of the technology choices which
will be available to those who implement the hardware design.
Advanced packaging to support high-clock-rate designs
have been a trademark of Cray Research designs
through the years.
With time-to-market always an important consideration,
it is wise to exploit but not overextend the technology
reach of each new product.
Good judgment therefore requires a good technology fit
with the design and manufacturing processes
of the organization.
And now, Steve Oberlin will discuss
the details of the interprocessor communication
network.
Thanks, Steve.
As previously mentioned, Cray T3D Processing Elements or PEs
communicate over a high-speed network
configured in a three-dimensional torus
topology.
What's that?
Well, to illustrate, let's start with networks having
less than three dimensions.
This is a diagram of a simple single-dimension torus
network connecting eight nodes.
The links between them carry data packets
at some maximum rate we're not concerned with for now.
There are a few things worth noting about this network.
First, what's the latency of the network going to be?
Topologically speaking, there are no ends to the network.
During random global communications,
a packet can choose to travel whichever
direction around the network is the shortest
path to its destination.
The worst-case distance then is to a node halfway
around the network.
If we measured latency in hops, the maximum for this network
would be four hops.
If you look at all possible communications between PEs,
the average latency is about two hops.
Second, what is the bandwidth of this network?
The ability of the network to carry global traffic
is measured by counting the number of wires
that would be cut if you snipped the network in two
at the center.
This is called "bisecting" the network.
When you multiply the result by the speed data
moves on each wire, you get a metric called the "bisection
bandwidth."
And for this simple 1D example, the bisection
is two times the channel rate.
In this diagram, it looks as though the link connecting
the ends to form a torus must be a pretty long wire.
In reality, it's possible to fold a torus so that all wires
are about the same length.
This diagram is also a torus.
And it's topologically equivalent
to the previous diagram.
Only the wires go from node to node in an interleaved pattern.
In T3D, two of the three dimensions
are folded in this fashion.
There's one other characteristic of the torus
that's worth mentioning.
It's naturally fault-tolerant.
Suppose one of the links broke for some reason.
The torus provides a second path between nodes--
the long way around the network--
so that the system can continue running.
The more processors in a system, the more important fault
tolerance becomes, because the failure of a single PE or link
represents a correspondingly smaller fraction
of the machine.
Who wants to give up their machine for repair if a failure
only costs 1,000th of its capability?
Let's look at a more complex network, an eight-node 2D
torus.
Now, our nodes are connected to their neighbors
in two dimensions.
By adding a second dimension, we double the bandwidth
to four over the 1D Taurus.
Maximum latency is now three and the average is less than two.
These effects are magnified the more nodes you have.
For instance, a 64-node torus has
eight times the global bandwidth of a 1D torus
and a maximum latency of eight, instead of 32.
You can see where this is going by now.
By stacking planes of 2D tori and connecting
nodes in the third dimension into a torus, as well,
we can construct a 3D torus, which
is the T3D's network topology.
We've again doubled the bisection bandwidth to eight.
And maximum latency is now two and the average
barely over one.
Again, the biggest advantages of adding a dimension
come with the larger sizes.
At 64 nodes, a 3D torus has 16 times the bandwidth
of a 1D torus and a maximum latency of six, instead of 32.
For comparison, the largest-size T3D
has a torus with 1,024 nodes in an eight
by 16 by eight configuration.
Data packets route through the T3D network in dimension order.
This means that a packet injected into the network
routes in the x-dimension first, then the y-dimension,
then z, until it reaches the destination node, where
it's ejected from the network.
So what does a T3D network node look like?
This block diagram shows the communication paths associated
with a network switch.
Each network node in T3D is shared by two independent PEs.
The PEs are logically separate and only share
the bandwidth of a network switch and a data mover
called the "Block Transfer Engine,"
which I'll talk about later.
There are high-speed channels radiating from the network
switch in seven directions.
Six of those directions are for the 3D torus connections.
The seventh direction is the channel to the PEs.
Each channel is actually two unidirection channels
that operate independently.
In other words, it's possible to have data streaming
through the switch from east to west at the same time
other data is moving from west to east.
Packet steering is controlled by a routing tag
in the header of a data packet that
specifies the number of hops a package should
travel in each direction.
In T3D, routing tags are stored in a high-speed lookup
table at each node.
When a data link fails, the routing directions
in the lookup tables are simply changed to avoid the bad link.
T3D also provide some extra compute nodes
as spares in the event of a PE or node failure for increased
fault tolerance.
There are eight redundant PEs for every 512 PEs.
Redundant nodes can be electronically switched
in place of a failed compute node
by rewriting the lookup table to substitute the redundant node
for the failed node.
The network switch or router is actually
implemented on three chips.
Each chip handles one dimension.
We call this a "dimension-sliced router."
Its functioning is fairly straightforward.
Packets enter the x-dimension switch from a PE
and route from x-switch to x-switch, then
turn the corner by crossing to the y-switch chip
to travel in the y-dimension, then
cross to the z-switch chip for z-dimension routing,
then finally emerge at the destination PE.
Latency of the switch is very low.
Essentially, it takes one clock period, 6.7 nanoseconds
at 150 megahertz, for a packet entering a chip
to decide which way it's going and leave again.
At these clock speeds, the time spent on the wires
isn't negligible and must also be included
in latency calculations.
In T3D, all wires are either one or one and a half clocks long.
Each hop in the network then takes one clock
for the switch plus one to one and a half clocks for the wire.
Turning the corner is similar to routing within a dimension.
It takes one clock inside the first chip,
one clock for the connection between chips,
and one clock for the second chip.
And you're on the wires in the next dimension.
Notice this diagram has all the same arrows
as the earlier node diagram.
Each arrow represents a channel that
is 16 bits wide that is clocked at 150
megahertz for a raw bandwidth of 300 megabytes per second.
Earlier, we talked about the bisection bandwidth
of a network.
The bisection bandwidth of a 1K processor T3D,
which has 512 network nodes in an eight
by eight by eight torus, is easy to calculate.
The number of channels cut when we bisect the torus is 8 times
8, one plane of the torus, times 2
for the connected ends of the torus times 2
for the channels in each direction times
300 megabytes per second, giving a total of 76
gigabytes per second.
Data packets carry data in two payload sizes, one or four
64-bit words.
Packets are broken up into 16-bit chunks
called "phits" for physical units
and sent over the network in a string of successive parcels.
The routing tag is always in the first phit.
And it opens a path through the switches
for the following control and data phits.
The head of a packet can easily be many switches ahead
of the tail in the network.
In scientific literature, this is commonly called "wormhole
routing."
Deadlock is a phenomenon like gridlock
in Manhattan at rush hour that can
happen when packets in a network are not guaranteed to have room
to make forward progress.
Deadlock is impossible in T3D because
of the use of layers of buffering
called "virtual channels."
By separating the buffering for requests and responses
and providing an additional set of buffers for packets that
have passed a certain point in a torus ring called the "date
line," we guarantee network packets
can't be blocked indefinitely.
T3D thus has four sets of virtual channel buffers,
two for requests and responses before the date line
and two for requests and responses after the date line.
Cray chose the 3D torus topology after
an extensive investigation ending
in a final shootout between a couple of champion networks
in a detailed simulation using real
and synthetic communication patterns.
When evaluated within the constraints
of real-world packaging limits and wiring capabilities,
the 3D torus provided the highest global bandwidth
and lowest global latency for the number
of processors we expected to have
in T3D, hundreds to thousands.
Several additional important characteristics
include good physical scalability, fault tolerance,
ability to exploit locality for reduced latency and improved
bandwidth, and a good fit with our technology--
that is, short wires in a regular wiring pattern,
resulting in a high clock speed.
There's also significant headroom
in the technology that will be used
to provide even better network performance in future machines.
Let's define and differentiate two levels of the Cray T3D
architecture.
These are the macro-architecture level
and the micro-architecture level.
The macro architecture represents the high-level view
of the system seen by the MPP programmer.
This includes the globally addressed
physically distributed memory characteristics,
in a general sense, the topology, which
defines relationships among compute nodes,
and the synchronization features to the degree
they are exposed in high-level language constructs.
It is important to present a consistent,
although probably slowly evolving view to the user.
This allows generation-to-generation source
compatibility.
The balance among computational, memory bandwidth,
and interconnect support will be also fairly consistent.
Application-level optimizations that work
well on one generation system should also
work well on the next.
If a system is successful in the marketplace,
this steadiness of purpose will also
work to support the development of standards in the MPP world.
The micro-architecture roadmap, on the other hand,
must be much more agile.
Micro architecture refers to the CPU and the lower-level logic
shell, which maps the CPU into the system overall.
When beginning an MPP design, one of the first decisions
to be made is whether to design a new proprietary
microprocessor or to select from a variety of emerging commodity
devices.
The primary argument for a proprietary design
is that it gives an opportunity to specifically and efficiently
tailor the micro-architectural design
within the context of the overall macro-architectural
goals.
But there is a problem.
With commodity microprocessor development cycles
lasting only two years, there is opportunity
for rapid improvement, which also can mean rapid change.
To be competitive with current state-of-the-art microprocessor
designs, which by some counts are already as a class
in the middle of the fourth or fifth generation,
demand significant design and integrated circuit process
development resources.
The human resources must be applied
in a widely parallel fashion to minimize time to market.
There is always an unfolding next generation coming
from large competing design groups.
For these reasons, even the largest
of computer corporations have seen fit to build and support
consortia to provide sufficient market presence to pay back
the design effort.
And of course, these devices benefit from high volume,
which allows lower pricing.
This counterargument to embrace an emerging commodity
micro-architectural implementation
was most persuasive for the Cray T3D project team.
The processor selected was from the Alpha Microprocessor family
from Digital Equipment Corporation.
This device was selected primarily
because it best met our objectives of providing
high performance and high precision
for both floating-point and integer data types.
We present only a short list of some
of the more important characteristics of this device,
but would refer you to the other videos
in the UVC series featuring lectures by Digital Equipment
Corporation engineers.
These tapes cover Alpha architecture and implementation
in detail.
The DEC chip 21064 represents a 0.75-micron CMOS implementation
of a full 64-bit reduced instruction set computer.
It has a peak floating-point performance
of 150 million floating-point operations per second,
utilizing a 150-megahertz clock frequency.
Up to two instructions can be issued
per clock period or 300 MIPS.
The internal register set consists
of 32 integer and 32 floating-point registers.
There are two internal caches, 8K bytes of instruction cache
and 8K bytes of data cache.
All candidate commodity microprocessors,
including the Alpha Microprocessor,
were designed primarily to satisfy the requirements
of workstations containing single or, at most,
a handful of CPU devices.
This design focus, while appropriate for the workstation
market, results in certain weaknesses
when it is inserted into a scalable massively parallel
processing system.
This is particularly true when the system design
has an objective of supporting very large numbers
of processors sharing a very large global address space.
Fortunately, there are ways in which the microprocessor
can be enhanced with appropriate supporting shell logic.
A globally addressed memory subsystem designed
with the objective of scaling to more than 1,000 processors
requires a very large physical address.
Even a large workstation memory by today's standards
is small compared to that of a fully configured Cray T3D
system.
When data cannot be found in the local data cache,
the cache miss invokes an external memory reference.
Typical microprocessors can support
only a very limited number of outstanding memory loads,
often only one.
But in a distributed memory MPP, any global reference,
even nearest neighbor, which stalls the processor
will seriously affect computational efficiency.
Logic must be added to support and mask
many outstanding references, thereby hiding latency.
This provides capability to fully exploit
modern compilers that are able to accurately judge when
to prefetch streams of data.
Interprocessor synchronization must be fast and scalable.
Typical RISC microprocessor designs
anticipate only very moderate numbers
of processors working together within a workstation.
Techniques used are often bus-based,
such as the popular bus snooping protocol.
Due to very real physical constraints,
these schemes do not scale well beyond about a dozen
processors.
Software and I/O-based synchronization protocols used
in workstation cluster organizations may scale
to large numbers, but fall far short of our goal for providing
single microsecond or less global synchronization latency.
The T3D's macro architecture can be
described by the characteristics that
are visible to the programmer.
These include the physically distributed memory,
which probably represents both the largest challenge
and the greatest performance opportunity
for a programmer, the global address space, which
provides the ability to communicate
in a fine-grained manner, fast barrier
synchronization, especially useful for data-parallel
programming, fast memory locks and support for dynamic loop
distribution, especially useful for work sharing,
and hardware messaging support, especially
useful for the message-passing programming model.
Also visible to the programmer due to their effect
on performance are the 3D torus interconnect network,
where a programmer may wish to optimize communication patterns
or data locality, the block transfer engine,
which can help hide remote latency,
and the local processor's cache memory,
which a programmer may need to be
aware of for best performance.
Let's take a look at how the PE micro architecture implements
the macro architecture in T3D.
At the heart of the processing element
is the Alpha Microprocessor.
Around the Alpha, we've added a shell of external circuits
to implement the MPP functions we need.
These fall into the three categories
Steve mentioned earlier, address extension, latency hiding,
and synchronization.
The Alpha has a 43-bit virtual address space that is
translated in the on-chip DTB--
that's Data Translation lookaside Buffer--
to a 34-bit physical byte address.
T3D has up to 64 megabytes of local memory
and up to 2K processors, which would require
at least 37 bits of address.
In reality, this isn't even close.
Several additional address bits are also
needed to control caching and to facilitate control
of the memory map mechanisms that implement the external MPP
shell.
So an external address extension mechanism of some sort
is required.
In T3D, this takes the form of a 32-entry register
set called the "DTB annex."
The way memory is distributed in T3D,
addresses have two parts, a PE number part
that says essentially which bank of memory
and an offset part that says which
memory location within the bank.
When the Alpha initiates a load or store,
the offset portion of the address
is taken from the physical address bits
that are translated on-chip.
And the PE number portion is taken from the DTB annex.
The choice of which of the 32 annex
registers to read for the PE number
is made by a five-bit field above the offset.
The DTB annex is readable and writable by user code.
The value read from the annex is a virtual PE number,
which is translated by a shell mechanism
into a logical PE number and checked for validity prior
to applying it to the routing tag lookup table
to make a remote reference.
The virtuological PE translation mechanism
is used to create user partitions
within the physical torus and provides
a good deal of flexibility concerning size
and shape of the partition.
Shell circuitry always checks the virtual PE number
and, if it matches the local PE, performs a local memory
reference, instead of a remote reference.
What about latency hiding?
The Alpha, like most microprocessors,
has a very limited external pipeline capability.
When it performs a load, it places the address
on its address bus and waits for the data
to be delivered before it will move on to the next reference.
This may be OK for a desktop system
with a single processor, when the memory is only inches away.
But it's unacceptable in an MPP when
the data is at a remote node.
We can't have the processor stalled
waiting for remote references.
So in T3D, we've extended the memory pipeline externally
by adding a latency hiding mechanism called
the "prefetch queue."
The prefetch queue is a first in, first out memory
16 64-bit-words deep that is used
as the temporary destination of remote loads.
Prefetches are initiated by executing a FETCH instruction,
which is an Alpha op code meant to be used as a prefetch hint
to a board-level secondary cache.
In T3D, a fetch causes a single-word load
to be initiated from memory, possibly remote.
But since the destination is not the processor,
the fetch can be acknowledged as soon
as we've latched the address.
And the processor can continue with other work.
When the load response returns, it's
placed in a slot in the prefetch queue that
was reserved for it at the time the fetch issued.
Sometime later, the processor can come back and pop the data
from the memory-mapped head of the prefetch queue,
thereby hiding the latency of the load.
If the processor tries to pop the data from the queue
before it's returned, the processor
will stall until the data arrives.
Using the prefetch queue, up to 16 loads
can be outstanding at any time.
The prefetch queue is turning out
to be a very powerful mechanism easily used by the compiler.
Alpha stores to memory do not need to wait for a response.
So a large number can naturally be outstanding at any time.
This is a good communication mechanism
if the producer knows who the next consumer will be,
because the Alpha has write buffers on board that
try to accumulate a cache line, four words, of data
prior to performing the actual remote store.
This increases the payload size and effective bandwidth.
A counter in the shell circuitry is incremented each time
a store is issued by Alpha and decremented
each time a write completes.
This counter can be read by the processor at any time
to determine when all of the writes
have completed for synchronization purposes.
The third major latency-hiding mechanism
is an asynchronous memory-to-memory data
mover called the block transfer engine or BLT.
There's one BLT per node-- no sense having two,
since it can saturate the network interface by itself.
Once started, it functions independent of the PE,
transferring data between remote memory
and the local memory in either direction.
The BLT can move up to 256K words of memory
with a single invocation.
The local data that is the source on a write block
transfer or the destination on a read block transfer
can be addressed with any constant stride.
Remote addresses can be any constant stride
or can be indirect, meaning the address is
from a separate stream previously stored
in local memory.
Indirect operations are commonly called
"scatter/gather operations" because they can reference data
in completely arbitrary ways.
The BLT also has a unique mechanism
for interpreting the remote address.
This mechanism, called the "Centrifuge,"
is used to support and control the distribution of data
among the PEs that is so critical to attaining
good performance on a distributed memory computer.
We previously said that memory addresses have two parts,
an offset and a PE number.
A remote address generated by the BLT
must somehow have its bits interpreted
to determine which PE to send the reference to
and what offset to use once the reference arrives.
I've got a couple of examples to show you how this works
and why it's so powerful.
In a conventional computer with an interleaved memory,
an address is usually interpreted
as having the memory bank number in the low-order bits,
with the offset in the high-order bits.
If we increment this address repetitively by one,
we see that the resulting address pattern visits the same
offset on each bank once.
Then the carry increments the offset field,
and all the banks are visited again.
In a distributed memory computer,
sometimes the offset is interpreted
as lying in the low-order bits of the address,
while the bank or PE number is in the high-order bits.
If we increment this address repetitively by one,
we see that the resulting address pattern traverses
all of the memory within the first bank
before finally incrementing the bank address to the next bank,
where all of its memory is traversed before incrementing
the bank again, et cetera.
In our MPP, we'd like to have it both ways.
Indeed, we want even more.
We'd like to be able to control exactly
which bits of the address are interpreted as PE
and which are offset.
This would allow us to, for example, slide the PE number up
by, say, four bits so that it had offset bits on either side.
If we start incrementing this address by one,
we see that the address pattern touches
a block of 16 addresses on one PE
before incrementing to the next PE to touch 16 more and so on.
We call this a "block distribution."
The Centrifuge in T3D is controlled
by a mask that indicates which bits are PE number.
Any place a one is set in the mask,
the address is interpreted to be a PE number.
Any place a zero is in the mask, the address
is interpreted as an offset.
The output of the Centrifuge is a separated PE number
and offset that is used to make a memory reference.
Note that bits in the mask do not even need to be contiguous.
This permits precise control of the distribution
of individual dimensions of multidimensional data arrays.
All remote addresses generated by the block transfer engine
are centrifuged prior to use.
The BLT naturally has a larger start-up overhead
than direct processor stores or the prefetch queue.
So it's most useful when moving larger blocks of data.
Now, let's talk about synchronization.
The PE shell circuitry implements
four major synchronization mechanisms, barriers,
fetch and increment, atomic swap, and messaging.
A barrier is a point in a program beyond which
no processor should advance before all processors have
arrived.
Barriers are often used to delineate
between parallel sections of code
when data produced by the first section
is to be consumed during the second section.
It is a block form of synchronization
that is latency-sensitive, since there is usually
little to do while waiting for the knowledge
that the last processor has arrived at a barrier
to be propagated to all processors
so that they can proceed.
T3D has specialized barrier hardware
in the form of 16 parallel logical AND trees
that permit multiple barriers to be pipelined
and the resource to be partitioned.
The barrier resource appears to a PE
as a memory-mapped register.
When a PE arrives at a barrier, it
sets a designated bit in its barrier register to a one
and waits for it to switch to a zero.
When all PEs in a partition have reached the barrier
and set the same bit to a one, the AND function is satisfied.
And the barrier bits are cleared by hardware,
signaling the processors that they may proceed.
As an alternative to repetitively
testing a set barrier bit to see if it switched to a zero,
the processor can enable and interrupt
and perform unrelated work until the barrier is satisfied.
The barrier has a second mode called
Eureka mode that supports search-type operations.
A Eureka is simply a logical OR instead of an AND.
A Eureka's satisfied by any one processor.
A Eureka may be used during, say, a database search,
where all processors would enable their interrupt
on Eureka and proceed with a search
until any processor succeeds and terminates the search
by satisfying the Eureka.
The barrier mechanism in T3D is extremely fast.
Even in the largest configuration,
it's less than 50 clock periods, about 330 nanoseconds,
which is about the latency of a local memory read.
A second synchronization mechanism
that supports work distribution well
is the fetch-and-increment registers.
This set of registers is globally accessible by the PEs.
There's one per PE.
A store to a fetch-and-increment register acts normally,
but a load from one causes the contents to auto-increment.
This is very useful for distributing array indices,
for example, while strip mining a loop.
Each time the fetch-and-increment register
is read, it delivers a value one greater than the last.
To hide the latency of accesses to the fetch-and-increment
registers, they can be fetched to the prefetch queue.
Another fine-grained synchronization mechanism,
atomic swap, permits construction of locks in memory
or the emulation of full empty bits
on individual words of data.
The swap is simply an atomic read/write
of a global memory location.
The value that is stored in the memory location
comes from a local memory-mapped register
called the "swaperand."
The value that was originally in the memory location
is returned to the PE.
The return destination, like any load,
can be the prefetch queue in order to hide the latency.
Full empty bits in memory are emulated
by designating a token value--
say, an undefined IEEE floating-point Not A Number
or NAN--
to mean "empty."
When a processor wants to load and lock
a memory location in order to, for instance,
perform an atomic add to that location,
it simply swaps the empty token into the memory location.
If the return value is also an empty token,
then the location was already locked by another PE
and the swap must be retried.
If the value it returned is a valid number,
then the PE has successfully locked the location
and may perform its atomic operation.
To unlock the location, the PE simply stores the valid data
back to memory, overwriting the empty token.
Message passing is directly supported by T3D hardware
in the form of low-level primitives
that permit cache-line-size messages to be sent directly
from user space.
These short messages are initiated
by performing stores through special memory-mapped space
to the target PE.
The message data is stored in a hardware-managed message
queue in the local memory of the target PE.
And that PE is interrupted.
Hardware automatically allocates space
from the sender's message queue in case
the destination queue is full and the message rejected.
Rejected messages land in the sender's queue
and interrupt the sending processor for a retry.
Messages carry 32 bytes of payload
and are stored in the target message queue,
with the routing tag and packet control
information bringing the total to 64 bytes per message.
The message queue area in local DRAM
is 256K bytes, permitting up to 4K messages to he received.
The messaging facility is also key to the network
error-handling mechanism.
All network packets have parity on each phit
of control information.
Data is protected by sec-det. If a parity error or a packet
miswrote is detected when a packet arrives at a node,
the entire packet, header and all,
is deposited in the apparent destination PE's message queue
and an error interrupt issued.
That pretty much wraps up our overview
of the T3D micro architecture.
Let's step back a minute to discuss
the design of T3D's I/O.
System I/O is performed via multiple Cray
high-speed channels that connect T3D to a host YMP
or to standard Cray I/O subsystems
that contain interfaces to a wide array
of peripheral devices and networks.
A single Cray high-speed channel consists
of two unidirectional channels, one input and one output,
each capable of 200 megabytes per second, coupled
with a low-speed control channel that
allows the passing of supervisory information.
Each high-speed channel pair connects to a specialized node
within T3D called a "gateway."
There are eight gateways for every 512 processors in a T3D
system.
Aggregate I/O bandwidth for 512 processors
is 3.2 gigabytes per second.
Each gateway itself is actually a pair
of nodes, each handling one direction
of the high-speed channel.
The two nodes within a gateway share the low-speed control
channel.
Each of the two gateway nodes has its own CPU for control,
separate local memory, and a dedicated block transfer
engine that can move data between memory
and the high-speed channel.
A gateway node network switch is connected
into the network in the x- and z-dimensions
only, that being all that's necessary to allow
complete communication.
Gateways are placed on the diagonal of the 3D torus
network in order to distribute the I/O bandwidth
and minimize I/O traffic contention with compute traffic
in the network.
This Cray T3D processor element module
holds eight microprocessors, four on this side
and four on the back side.
Each pair of microprocessors within the compute node
is supported by 21 proprietary integrated circuits.
These circuits implement high-performance bipolar
emitter-coupled logic.
Small dotter boards support wide-word dynamic random access
memory components.
These dotter boards can be easily replaced locally
by field service personnel.
Each long edge of the motherboard
is configured with a dense array of zero-insertion-force
connectors.
These connectors provide the high degree
of interconnectivity required for the interprocessor
channels.
The module is liquid-cooled by attaching the circuit
boards and integrated circuits to an anodized aluminum
cold plate.
An inert cooling fluid flows into, through,
and then out of the module via hoses
connected to a cooling manifold in the chassis.
A single Cray T3D chassis can support up
to 512 compute processors, eight I/O gateways,
and additional redundant processors for fault tolerance.
The zero-insertion-force connector
is activated and deactivated by inserting a cam
down each edge of the module after it has been
inserted in the module slot.
The cam works to move small sliding contacts one by one
out of the chassis-mounted connector
half of the mated pair into the half mounted on the module.
Bundles of high-performance Teflon wires attached
to the chassis connectors provide
the toroidal communication paths.
The arrangement of the wire bundles
can be changed to support the future addition of modules
into chassis which were initially
configured to smaller sizes.
Switching power supplies, each supplying up to 1,800 amperes,
provide module power.
Standard configurations provide for one extra power supply
for each required voltage, allowing additional fault
coverage for the system.
Steve and I have tried to convey our excitement
about this design.
We believe the Cray T3D to be a powerful and flexible
supercomputing tool.
I hope you've enjoyed our presentation.
Thank you.
[MUSIC PLAYING]