[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: 6502 illegal opcodes questions

mdj wrote:

Michael J. Mahon wrote:



The big "open door" opportunity is multiprocessor parallelism, but
we have invested so little in learning to apply parallelism that it
remains esoteric.  (But AppleCrate makes it easy to experiment with! ;-)



Parallelism is the big door, but I think the approaches that need to be
explored cover a wider gamut than multiprocess parallelism, which as
you point of has considerable latency issues.


And I would say that tools to help with the decomposition of algorithms
into parallel parts, while minimizing the effects of latency and limited
bandwidth, are the most important "tool frontier" today.


The popular "thread" model, in which all of memory is conceptually
shared by all threads, is a disaster for real multiprocessors, since
they will *always* have latency and bandwidth issues to move data
between them, and a "single, coherent memory image" is both slow
and wasteful.



It is however an extremely efficient form of multiprocessing for
applications with modest horizontal scaling potential.


And it offers unprecedented potential for data races an
nondeterministic behavior!  ;-)

The thread model should have fundamentally segregated memory, so
that inter-thread references require special coordination commensurate
with their special risks and costs.


There's essentially 3 basic models for parallelism that must be
exploited:

Multithread - in which one processor core can execute multiple threads
simultaneously


This is the only case that can even approximate "uniform memory", since
at least most of the cache hierarchy will be common to all threads.


Uniform Memory Multiprocessor - in which many processsor cores share
the same physical memory subsystem. Note that this is further divided
into multiple cores in the same package, plus other cores in different
packages, which have very different latency properties.


Even within one package, only lower cache levels will be common, so
this is not fundamentally different from your next case...


Non Uniform Memory Multiprocessor - In this case the latency can vary
wildly depending on the system configuration.

Modern multiprocessor servers employ all three approaches, both on the
same system board, plus via high speed interconnects that join multiple
system boards together. OS's must weight the 'distance' to another CPU
when considering a potential execution unit for a process.


All of your cases are actually the same, differing only in the level
of memory hierarchy (and its corresponding latency and bandwidth) that
is shared.

Any practical system will consist of all levels of connectivity, with
sharing at virtually all the different levels of the memory hierarchy.
And I would add another set of levels, in which there is no "memory
consistency" model, but message passing is the sharing mechanism.
This extends the multiprocessing model across networks.


What's slow and wasteful depends a great deal on the task at hand.
Multithreading used to be just as expensive as multiprocessing. But
consider a current generation CPU designed for low power, high
concurrency, the UltraSPARC T1.

These units have execution cores cable of running 4 concurrent threads.
In the highest end configuration, there are 8 of these execution cores
per physical processor. The cores have a 3.2GB/s interconnect. Each
physical processor has 4 independant memory controllers, so you have
non-uniform memory access on the one die.


Exactly.  The general case is becoming the common case.

And multi-threaded processors are actually a very old idea.  The
Honeywell 800 supported 8 "threads" (not called that, of course),
by executing instructions in "rotation", skipping slots that were
waiting for I/O to complete.  At the time, it was considered to be
a hardware implementation of multiprogramming.

Today, multithreaded processors do much the same, but the "I/O wait"
has been replaced by the "cache miss".

The peripheral processor of the CDC 6600 was another salient example
of multi-threading.  It was implemented in the same fast logic as
the central processor, but presented the appearance of 10 separate
PPs, each executing instructions at 10th the rate of the central
processor.  This had the effect of matching its instruction rate to
the latency of memory, and provided 10-fold concurrency for managing
I/O and memory transfers.


Peak power consumption for this part is 79W at 1Ghz. Considering you
can in theory run 32 threads simulaneously, that's pretty impressive.
How well you can exploit it depends on your application. An 'old
school' web server for instance, can only get 8 way parallelism on this
chip. A new school web server written in Java, can get 32 way, assuming
at any given time there is at least 32 concurrent requests for the same
dynamic page, or 32 static requests.

It's getting to the stage where the power consumed by driving I/O over
a pin on an IC package is significant, so expect to see systems like
this grow in popularity.


This was always an inevitable result of higher levels of integration.
As soon as a significant amount of cache can be shared on the chip,
it becomes advantageous to adorn it with multiple processors.


Interesting, you can download a VHDL description of this part from Sun,
and synthesise it on one of the higer end FPGA's. Oh how I wish I had
access to hardware like that!

A top of the range Sun server uses parts that have 4 execution threads
per core, four cores per board, each with it's own memory
controller+memory, and up to 18 boards per system (coupled together by
an 9GB/s crossbar switch). Exploiting all the resources in this system
and doing it efficiently is *hard*, as it employs every different style
of parallelism I mentioned before within the same 'machine'.

And I haven't even considered computing clusters!


Exactly.  And the full hierarchy of latency and bandwidth needs to be
addressed by both measurement tools and by behavioral models for code
partitioning and optimization.  *This* is the tools frontier that I see,
with huge potential payoffs.


The way it's panning out is that real multiprocessors are a disaster
for parallelism. The problem is that essentially any task that can be
parallelised needs to process the same data that it does in serial
form. Because of this, you can utilise the same buses, I/O subsystems,
and take advantage of 'nearness' to allow some pretty incredible IPC
speeds.


No, that problem corresponds to a *very poor* partitioning of the
problem onto parallel processors--ironically, one that is encouraged
by current languages' simplistic "thread" models of parallel computing.

Let me give a little example.

Maximum efficiency of resource utilization is obtained by "pooling"
all of a particular resource together so that all requestors obtain
it by withdrawing from one pool.  Then, you're not "out" of that
resource until you are *really* out of it.

But this creates a huge point of serial contention, since all
requestors must lock the pool, allocate some resource, then unlock
the pool.  It is as if a large cafeteria put one giant salt shaker
in the middle of the room for all to share.

An alternative resource allocation scheme which is well adapted to
multiple concurrent users and a hierarchy of latencies is to provide
multiple local pools, shared by a small number of users at essentially
the same level of connection latency.  This is like the more common
case of putting a small salt shaker within arms reach of each small
group of diners.

Of course, there is still the issue of resource balancing (when the
resource is really uniform--not like memory), and this can be done
by periodically re-balancing the amounts of resource in the local
pools, and across hierarchical levels if necessary.

This is the kind of thinking that must go into the next generation
of systems, and it is very different from the thinking that has
inspired the systems and tools of today.


Multithreading approaches are very important on these systems. In fact,
multithreading is important even on systems with single execution
units. The gap between I/O throughput and processing throughput means
you get a certain degree of 'parallelism' even though you can only run
one thread at a time. Free performance improvement if you employ
parallel design techniques.

Of course, there are certain heavily compute-bound applications where
the degree of IPC is very low, and massive parallelism is possible
regardless of the interconnect used, as IPC constitutes a relatively
small part of the workload. For the rest of the cases though where lots
of data is being consumed, systems that allow low-overhead IPC through
multithreading are the way to go.


And a tiny fraction of todays tools and designers are even out of
kindergarten on issues of partitioning and locality.

Object orientation is almost totally orthogonal, if not antithetical,
to the *real* problems of highly parallel computing, which is the
platform of the future.  I expect we'll figure this out sometime
in the next decade.  ;-(

-michael

Parallel computing for 8-bit Apple II's!
Home page:  http://members.aol.com/MJMahon/

"The wastebasket is our most important design
tool--and it is seriously underused."