Re: 6502 illegal opcodes questions

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

Michael J. Mahon wrote:

> Video transcoding is an "embarrassingly parallel" application, yet
> I have not found a single popular software manufacturer that makes
> a parallel transcoder.  With all the multicore chips now, they are
> leaving factors of performance on the table.

Unfortunately the main uses for transcoding in the consumer space are
to convert DVD's or broadcast digital into more compact forms. Since
this is percieved as largely a piracy driven concern, you cannot obtain
a license for CSS to build such an application. If you go ahead and
build one anyway (it's not like the techniques are patented) you'll be
prosecuted  under the terms of the DMCA. *grumble*

> Apparently, the market for video encoders does not evaluate them
> on performance--astonishingly.  Some of the most popular perform
> terribly.

I would guess that there are some professional level solutions that do
a better job.

> The actual situation is a full continuum of bandwidths and latencies,
> and that hierarchy is very poorly supported.  Instead, we give designers
> the static choice between shared memory and message passing.  This is
> a bad match to a world in which the system interconnect continuum is
> neither very slow nor very fast, and is constantly moving.

Agreed. The moving target is one of the things that makes it difficult,
and a prime candidate for higher level abstractions, lest work done now
be less applicable to hardware available 2 years from now.

> The most important "tools" we are missing are the conceptual tools
> to guide systematic and quantitative decomposition of applications into
> concurrent "chunks" to be run on varying numbers of processors with
> varying amounts and latencies of shared memory and/or message passing.
>
> Until we can get our design heads on straight, it doesn't make much
> sense to codify a particular approach in a language design--though it
> will as we learn.

Interestingly the hardware world has learned a lot about out of order
execution in recent years, so perhaps a good deal of the techniques
have been better explored that first appears. I agree though, we need
the quantitative approach first through tools, then the better
languages can evolve from those discoveries.

> When races are involved, or rendezvous with non-determinate order of
> arrival, then actual nondeterminism enters the picture.  Sometimes this
> is planned, and enhances performance--as in the case of an evaluation
> tree that takes advantage of the distributive property of the rollup
> operation (like arithmetic addition or set addition).  Sometimes it is
> unplanned, as when an erroneous race condition exists that causes
> intermittent bugs or unreproducible results.

Yeah, and the planned nondeterministic methods are the case that has
the least exploration at this stage, and is the one that benefits most
as the size of clusters goes up.

> >>>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.
>
> Yes, that's my point.  The *hierarchy* needs to be the thing that is
> optimized for, not some ideal simplified case.
>
> The only way to get a uniform memory model is to slow down all the
> memory accesses so that the ones that could go faster run at the same
> speed as the ones that can't run any faster--clearly simpler, but *way*
> non-optimal!

I suspect that given the number of possible localities, etc. and the
likelihood of these changing quickly over time, that the most
successful way will be to design for the worst case interconnect, and
allow optimisation to occur per-architecture by some form of runtime.
Still, it doesn't solve the problem of appropriate partitioning of
algorithms in the first place.

> >>>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.
>
> There is no "ideal" way--there are only real ways, and none of them
> have simple behavior if they're any good!

:-) I meant "ideal" in terms of the ones that currently are 'better'
versus the 'worse' ones, in terms of processing units on the same
system board having closer locality for similar system cost.

> >>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.
>
> Agreed--and the tools for *optimizing* applications across even two
> processors are almost nonexistent.  A suboptimal data partitioning
> can cause a large factor of performance degradation, and designers
> have virtually no tools to understand and adjust this.

Indeed. There are plenty of cases where even non-parallel application
performance drops when moving to multiprocessor systems, simply because
of operating system design. A classic example, which is largely solved
now is the naive scheduler which shifts a running process to another
CPU, throwing out the cache on the one it was on in the process, and
worse, this happens while the process in question was waiting on I/O
:-)

> >>>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.
>
> Now you see what I mean.  OSs should automatically manage this
> "dynamic affinity" or "memory reference locality", with input and
> assistance from compile-time and run-time analysis.
>
> And the designer should be able to visualize the range of behaviors
> caused by various design choices relative to parallel execution.
>
> The absence of these tools is a major obstacle to the design and
> implementation of efficient parallel applications, and this is a
> *much* more fruitful area for investment than playing with language
> constructs.
>
> >>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.
>
> Sad but true.
>
> >>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 :-)
>
> Actually, that's one of the most important areas to do *much* better
> and more adaptively than is done in current OSs.

Yes. The current approach adds effectively a 'timeout' constant to a
process. The timeout represents the cost of shifting it to the next
nearest locality, and processes don't move until this time has expired
without the opportunity to shift them. Once the timeout has expired,
you look for a gap in the scheduling table on processors of this
locality, and if one exists, you slot it in. If not, you increase the
timeout to the cost of moving one level further out, and so on. Each
time a process gets scheduled to run, you reset the timeout to nearest
locality.

This approach works very well for avoiding unnecessary shifting of
single-thread processes on a multitasking system, and things tend to
settle into relative harmony as the system runs.

Of course, handling scheduling and moving of massively parallel
processes is another kettle of fish!

> The "distributed process allocation" problem in the OS is as fundamental
> as the "code selection" problem in a compiler, and will have much larger
> performance impact as the level of *system* concurrency continues to
> increase.
>
> I would even go so far as to say that the current *lack* of good
> solutions to this problem is a major reason for the limited utility
> of multicore systems.  In a couple of years, we could all have 8-way
> systems on our desktops, but if the fundamental enablers for parallel
> apps don't get done, they won't perform much better than single-core
> systems (as is true today for dual-core/single-core).

There's a real need to crawl before we walk here. One big problem that
needs be solved even on current systems is how to deal with many
concurrent independant processes all in kernel space at the same time.
Unless we move to microkernel systems, which I think eventally we will,
we have to solve the problem of how to effectively schedule multiple
concurrent threads of operating system code competing for resources as
well, effectively meaning the problem has to be solved twice. Most
current OS's have pretty ordinary granularity when it comes to
intra-kernel concurrency.

> >>>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.
>
> Exactly--which is why I say this is the real "frontier" today.
>
> > 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.
>
> It doesn't need to be a non-existent machine--most machines have timer
> interrupts that permit background profiling and dynamic code changes.
> All of these tricks can be (and have been) done on actual machine code.

Yes. I've often considered playing with this myself with Apple Pascal,
and profiling the bytecode interpreter as it runs. Then, use the output
of it to selectively native compile various procedures or functions and
relink the application. Should be a hoot :-)

> > 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.
>
> And not too difficult or intrusive if it is based on sampling
> information at interrupt time (which automatically bases sample
> density on performance impact).

Unfortunately on other operating systems, you don't have this level of
intrumentation, and the other systems are different enough in terms of
architecture, operating system design, etc. as to make many of the
performance tuning possibilities you uncover on Solaris not applicable
:-(

> >>>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.
>
> For systems with higher latency or lower bandwidth connections, the
> problem partitioning must allow for divisions that do not cut "strong"
> interactions.  Like Aristotle and reality, we must find ways to cut
> applications at their "joints", and ways to design applications that
> present numerous opportunities for cuts at various levels of
> connectivity.
>
> Thus a *conceptual* toolset is required plus a *measurement* toolset
> that can provide useful feedback to all levels, from high level design
> time, to low-level design time, to compile time, to link time, to load
> time, to execution time (and dynamically at execution time).
>
> > It works fine for compute-bound loads, but data bound loads need
> > different configurations, at least for currently available hardware.
>
> In many applications, there are relatively weak data dependencies
> connecting large segments of data, so the data can be divided up,
> processed, and then merged together--all very well suited to avoidance
> of excess communication.  (For example, video and audio transcoding
> and most image processing are such cases.)
>
> Note that many cases of multidimensonal data have the characteristic
> that the amount of computation grows as a power of the data volume,
> while the size of the interacting "boundaries" between data chunks
> grows as a lesser power, so that by adjusting "chunk" size, the
> ratio of processing to communication can be easily adjusted over a
> wide range--and *should* be so adjusted adaptively, based on run-time
> realities and available system resources.

Indeed. Video encoding can very easily be parallelised through time
division, across many more processors than we're likely to have in
consumer machines any time soon. This can be achieved through fairly
simple multithreading plus rendezvous techniques. Of course, if the
number of parallel slices becomes excessive, you introduce to many full
frames into your encoding, and require a multitiered approach, but it's
still relatively feasible to do using simple tools.

> > 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.
>
> And it is exactly this fundamental neglect of the most important
> dimension of future computing--parallelism--that I fault.  Language
> designers are fiddling with details while the main problem goes
> unaddressed.  Could it be because details are easy and the *real*
> problem is harder?  ;-)

:-)

> As I said at ASPLOS a decade ago to language designers, "Your long
> vacation is *over*!  It's time to get to work on parallelism."
>
> >>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 was exactly my point that the ratio of salt shakers to diners is
> an important, and easily managed, property of a solution.  And it can
> have *huge* performance effects if it is not properly balanced.  Either
> extreme case is almost certainly suboptimal.
>
> > 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.
>
> And this is a relatively low extra overhead in the rare cases when a
> local pool is exhausted.  (Proper dynamic pool balancing will make this
> case very unusual, unless local demand has a large time/space variance--
> which is yet another parametric input into the allocation problem.)
>
> > 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.
>
> If the resource consumers make a local "run" on resources faster than
> the anticipative/adaptive balancing algorithm can rebalance the pools,
> then there will always be trouble--extending at least as far as the
> offending locality.
>
> This is simply reality.  Everything in the real world exhibits the
> same issues, and the same kinds of costs for avoiding or remedying
> them.
>
> It's good to recognize when we have reached the limits of our ability
> to optimize a solution--like finding a "Second Law of Thermodynamics"
> that tells us we've done as much to cope with residual randomness as
> can be done.  Of course, we're generally nowhere near that kind of
> optimality today.

This is part of my point, and I believe certain language constructs are
an impediment to achieving this within the application programming
space.

> > 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.
>
> You are actually making an agrument for the relatively outmoded kind
> of concurrency called multiprogramming, where the concurrency of the
> load exceeds the concurrency of the system.  This is obsolete.

I'm not so sure it is - OS's still fail to exploit multiprocessor
systems for multiple execution threads efficiently, be they the same
process/program or not. This is a fundamental problem with any form of
parallelism.

> There are well known techniques for ensuring stability--analogous
> to servo system design.  (Programmers generally are not aware of
> the mass of work done on stability in control systems.)

Indeed.

> >>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.
>
> A few have made a start--none have approached the problem as the
> absolutely fundamental problem that it is.

It's beyond the understanding of most to approach the problem this way.
There's a degree of research going on in the quantum computing field,
but this is for algorithm design for theoretical machines. I'd imagine
though that a lot of the techniques apply to real parallel systems as
well.

> >>>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.
>
> Right--which is why I'm trying to emphasize that the truly *important*
> dimension of decomposition for concurrency has been sadly neglected,
> when it should be the real focus of our language work.

There is room, no, for multiple focus groups?

> We don't need language "lawyers", or even "mathematicians"; we need
> language "engineers" with their sights firmly focused on the needs of
> the future--and the exploitation of multi-leveled parallelism heads
> that list, both in terms of challenge and in terms of opportunity.

I agree with you, and with engineer hat firmly on, I maintain that
keeping applications agnostic of architecture-centric concerns is a
necessary step in this goal. Consider that massive scale parallelism is
going to be heterogeneous. There are techniques out there that support
this, and some embrace them. Others are content to blindly export
architectural dependancies into their code, when as you rightly point
out, there are far more pressing concerns awaiting us.

Matt