Re: 6502 illegal opcodes questions

["mdj" <mdj.mdj@gmail.com>]

Michael J. Mahon wrote:

> > 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 main 'commodity' area where large scale parallelism was going to be
useful was image processing, particularly video. A large degree of
parallelism actually exists today in this field, but rather than
traditional parallel approaches, CPU vendors added SIMD extensions, and
video card vendors built GPU's. Todays GPU's are basically parallel
computing machines done on a single chip. I'd imagine most
parallelisable tasks will utilise these extensions first, and resort to
generic approaches second, as the specialised environments are in
general, more efficient.

Of course, you're right that down the track there's a lot more domains
that can be vastly improved by parallisation, but much of those remain
unexplored.

> >>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.

The tradional UNIX multiprocessing model using fork(), pipe(),
semaphore() and friends has, and does, do exactly this for thirty
years. Originally this is approach was expensive, but modern MMU's mean
that the cost of cloning a process is not much higher than creating a
thread (which merely replicates the stack). It exists on single
machines, plus machine clusters that support such techniques as process
migration and other more esotetic parallel computing ideas - see
BeoWulf clusters.

Since System V, this model has also included a message passing
interface that can, and is extended across cluster nodes.

The reasons for adding the thread model as well are mainly due to
intra-process parallelism rather than inter-process. The tradional I/O
models are synchronous, but once you introduce asynchronous I/O models
you need threads to allow your program to do something useful instead
of waiting for I/O. In such scenarios, there's no reason at all to
introduce the overhead of IPC, as there simply isn't any IPC to be
done.

Additionally, the multiprocess model actually shares the very same
issues the thread model does - just because you've copied your data
into another address space doesn't alleviate the issue of data being
modified erroneously. The only real difference is that in the 'thread'
model, you have the opportunity to exploit far more efficient means of
synchronisation, which don't require marshalling data and copying it
across address spaces. It's better to think of it as the same, only
faster.

That said, the multiprocessing approach offers certain degrees of
robustness in the case of an errant child crashing the program. Of
course, these issues only really affect programs written in languages
that allow arbitrary pointer arithmetic.

The problem isn't really one of this model or that model being wrong,
and it's better to think of threads as just a way to exploit higher
efficiency in the case of closer locality.

Unfortunately, the other popular operating system only supports the
thread model, and it's unfortunately again, different in semantics to
the POSIX model.

What's really needed, is languages that support parallel processing
constructs. It's not really fair to blame a parallelisation techniques
particular quirks for the limitations of the tools we use.

> > 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.

I guess you mean determinism with regards to execution timing? This
isn't really useful on any modern architecture, you must use enforced
synchronisation and real-time scheduling to achieve this.

> > 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...

Some implementations support high speed transports of L1 cache data
both to on-die cores, and inter-package cores. There's still a lot of
variance in the available implementations.

> > 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.

That's right. I drew a distinction because at present not all multicore
systems are implemented in the ideal way. The current generation Intel
Xeon dual cores for instance only benefit you for power consumption,
and are actually of equivalent locality to different processor
packages. Eventually the idealised designs will surface though and
you'll have general localities of die, board, system, and network. For
the moment it's somewhat more complicated.

> 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.

A brand new PC these days will get you two cores. There are different
scales of systems. The big ones, for sure, will exhibit all 4 levels,
but there's plenty of work to be done just to handle the opportunities
that exist in a new laptop.

> > 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.

The thing to keep in mind is that there's two cores per memory
controller, so ideally, if you need to migrate a process, you'll
migrate it to it's 'twin' core first if it's available before moving it
to another memory controller. You stay on package in preference to
moving to another package. There's a lot of variables involved in
picking the next most appropriate locality for a process.

> 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.

Indeed. There are very few new ideas in Computing these days.

> 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.

Just be thankful you aren't the author of the process scheduler of a
current operating system :-)

> > 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.

It's very difficult to construct these tools when the languages we use
exploit parallelism in such low level ways. What's needed, is the
ability to abstract away the issues of locality, focus on the core
issues involved, and then instrument systems accordingly.

This is similar to the compiler you mentioned a while back that used
runtime instrumentation of it's p-code engine to determine critical
sections then tune them. Although modern VM's apply this technique
today, that's about as far as it's got.

One of the reasons I still like Solaris is that it's the only common OS
that supports the concept of 'microstate' accounting. This essentially
means that you can log the transitions of a process through various
known 'microstates' So rather than know just that a process is blocked
on a resource, you can find out what resources, why, how long, etc.
This is integrated back into the development toolchain all the way
through to the Java level profiler, so you can visualise exactly what
different threads are doing, spending time on, and easily spot
bottlenecks which in many cases can be tuned out at either the OS or
the VM. Very fancy stuff.

> > 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.

In truly partitioned systems, how do you propose to solve the issue of
providing access to the source data for all partitions? Shipping the
data via slower I/O trunks is generally less efficient than processing
it all on systems with greater locality.

It works fine for compute-bound loads, but data bound loads need
different configurations, at least for currently available hardware.

It's worth noting though that many modern languages have absolutely
awful parallelism management. Java in fact, is one of the worst in this
regard, requiring the developer to work around a very fundamental
design mistake in many cases. Luckily this issue is well understood.
Unfortunately there's not a lot of languages out there that are
markedly better.

Fortunately, there are a lot of very nice frameworks around that
mitigate both the known issues, plus provide excellent implementations
of known resource sharing idioms.

> 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.

It's worth noting though, that that having multiple resource pools
introduces it's own probems. From the diners perspective, it's most
efficient if they each are allocated a salt shaker. However, this
introduces the problem of managing all the salt shakers, imposing an
unreasonable burden on resurant staff :-) The challenge is to find the
balance between the two that provides adequate parallelism while
effectively managing shared resources. Hence we have a multitude of
approaches depending on the specifics of the problem domain.

It's probably also worth pointing out that more than once, I've visited
a nearby table to 'borrow' a condiment, as the one I my table was
exhausted. The resource sharing introduces a latency, which fortunately
was easily resolved by the locality of similar resources.

In a very busy place, you can easily find that even neighbouring tables
have exhausted their resources, resulting in a somewhat ad-hoc 'hunt'
for nearby sources, before resorting to approaching a waiter, or
counter in order to obtain more. If this continues too long you can end
up with a gridlock situation, with an already busy staff trying
desperately to fill many tiny bottles and then distribute them before
the system returns to any sense of order.

A parallel system is more like a resuraunt with a queue of people out
the front waiting.

In many cases, the partitioning of the problem isn't the hard part,
it's figuring out a strategy for keeping each of the partitions
ticking.

In conclusion, partitioning often isn't the hard part, it's formulating
strategies to keep each partition operating smoothly. Only then are
resources being consumed effectively.

> 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.

A technique that is always a lot harder to apply that it seems.

> 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.

Agreed - although don't overlook the fact that there are plenty of
systems out there that have faced a lot of these issues already.

> > 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.

Completely agree with this point. I'm continually surprised by the
number of people I encounter that do not understand the dining
philosophers problem, and that's perhaps the easiest one!

> 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.  ;-(

Almost, other than the additional abstraction and encapsulation being
required by both concepts.Current languages don't really provide
adequate abstractions for parallel computing primitives. Some of them
can be modelled effectively using OO techniques, some of them can't.

Matt