Re: 6502 illegal opcodes questions

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

Michael J. Mahon wrote:

> Actually, the problem of allocating computation across a hierarchy of
> memories and multiprocessors is quite old, and the topology has not
> varied from the "general case" in several decades--only more levels
> of hierarchy have been introduced.  It's still exactly the same
> problem, with exactly the same range of solutions.
>
> Put another way, there is nothing "special purpose" about the model
> that I propose we optimize for--it should apply to everything from
> atoms to stars (in fact, the universe already seems to have an
> allocation algorithm that works pretty well  ;-).
>
> Here's an outline of a possible (incomplete) conceptualization based,
> interestingly enough, on the dynamic stability of (most) stars.
>
> Given a population of processes, all working concurrently and
> 1) consuming resources, and 2) communicating, let us allocate
> processes to a single "processing node" until its resources are
> mostly used, then begin allocating processes to nearby nodes,
> until all processes have been "spread out" across nodes.  We will
> treat resource contention on a node as "pressure" which leads
> to "expansion" of the set of processes across more nodes.
>
> Now, as the processes communicate, we treat non-local communication
> as an attractive force between the communicating processes, which
> biases the allocation algorithm toward moving them closer together
> (in "communication cost" space).
>
> Now note that a dynamic equilibrium is possible in which the contractive
> "force" of communication is balanced by the expansive "force" of
> resource contention.  This is analogous to the equilibrium that exists
> in a stable star between gravitation attraction and internal pressure.
>
> Such models can form the basis, when melded with control system theory,
> for stable, quasi-optimal allocation of multiple communicating processes
> across a fabric of processor-memory nodes.  Generalizations to a
> hierarchy of connectivity latencies and bandwidths are possible and
> would be required except in the simplest cases.

Indeed this is the goal. Perhaps you should get involved in one of the
open source projects working on such fields. There seems to be a lot
more 'hardcore' computing going on in the open source community these
days than inside corporate walls.

> Actually, most of what is being practiced in the realm of hardware
> concurrency is quite well understood, and has been around for decades.
> What has changed is that transistors have become cheap enough that the
> techniques originally developed in limited form for supercomputers
> can now be implemented in more general forms on microprocessor chips.
>
> Buffering, speculation, scoreboarding, data flow, and associative memory
> are not new, but their affordability in desktop processors is.

Certainly techniques that are not applied in the software realm, which
is what I was pointing out.

> Bingo.
>
> BTW, it guarantees the loss of strict reproducibility of results if
> floating point arithmetic is used, because the order of operations is
> non-deterministic, and that is what determines roundoff error.  We'll
> just have to be content with "fuzzy" reproducibility!
>
> (Incidentally, the variance of results produced when a computation is
> evaluated nondeterministically several times is a lower bound on the
> roundoff error in the computation.)

Yes. The only practical solution is to use much larger floating point
representations such that the fuzziness is less of a concern, although
modern hardware can perform 256 bit fixed point arithmetic quite
quickly :-)

> > 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.
>
> Right.  And one must be able to adaptively change allocations to
> maintain efficiency as the computation evolves, since many computations
> have more than one "locality" behavior, depending on what's going on.

Hence my lack of faith in languages that bind us too tightly to
(hardware) architectural borders.

> >>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.
>
> Ah.  Well, that's just physics.  Unless the designers mess it up, things
> that are closer together can afford to be connected at a higher level of
> the hierarchy.
>
> Early multi-core designs were just sub-optimal "pasteup" jobs.

Many of them still on the market, being espoused as equivalent or
superior to competing solutions :-(

> >>>>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
> > :-)
>
> And you correctly identify this as an immature OS scheduler design--yet
> another example of how even OS designers are blissfully unaware of the
> concurrency trends barreling toward them like trucks!  (And they've
> been quite visibly coming for a decade, so no one can justly claim that
> they were surprised!)
>
> I've been amazed by how unaware OS designers are about the implications
> of memory hierarchy and multiprocessing on their algorithms.  And those
> who figured out how to "cope" with a 4-way system can't understand
> that they will need a completely different approach to deal efficiently
> with a 32- or 64-way system.  (Think about queueing theory, lock
> contention, resource pools, and error recovery.)

Absolutely, although there are designs out there the deal well with
machines of that size (Solaris is one example). PC based operating
systems have conventionally been optimised only for the hardware that
appears at the time, which considering the rate of improvement in that
field, has left a lot of stones unturned.

> >>>>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!
>
> Not if approached with the right abstractions.  ;-)

And ditching explicit pointer arithmetic in code is one of the
abstractions dammit ;-)

> >>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.
>
> True--and significant changes in the low levels of OSs is inevitable.
> But "crawl before walk" implies that we are facing this as a *new*
> problem, when, in fact, it has been coming toward us for a generation,
> but we have failed to acknowledge it in our designs.
>
> I hope using our nose for a wall detector won't cause us too much more
> pain in this process (though note that lack of application support for
> even low levels of parallelism is really slowing the PC market down).

Agreed. The crawling should have been done a decade ago, not starting
now while oodles of performance going begging. The process we have to
go through remains the same regardless of the timeline unfortunately.

> >>>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 :-)
>
> Sounds like great fun!
>
> Using a source of timer interrupts makes dynamic profiling a breeze.
> (Of course, this would also identify the parts of the *interpreter* that
> were hot.)

I'm awaiting a TimeMaster HO which has a rather nice programmable
interrupt controller. Much more flexible than relying on the 60Hz VBL I
use at the moment for experimentation.

It's good fun exploring these ideas on smaller environments that have
nice predictable behaviors, but you already know this :-)

> >>>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
> > :-(
>
> Users should pester OS designers to provide them with background
> profiling capabilities.  It's actually easy to do on any OS.
>
> Of course, if you can define interrupting timers, then you can do it
> yourself--with considerably more overhead.

One of the problems with the design of many operating systems is the
inability to expose interrupts to a user level process. This has
resulted in many awful design hacks in OS's over the years (The
embedding of the UI subsystem of Windows NT into the kernel from
version 4 onward being a good example)

> >>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.
>
> Now *there's* a degree of parallelism that I'd like to have access to!

When I've needed to do such things (being a linux man) I've simply
split the source file into two parts and ran two encoders at the same
time, then recombined. The fine granularity of tools offered by UNIX
style interface opens up a lot of flexibility with how you approach
problems.

I agree that it should be far simpler than this, though.

> >>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.
>
> I wouldn't say so.  Quantum computing is so radically different from
> state machine programming that there is almost no comparison.  I'd say
> it's at least as big a difference in paradigm as going from analog
> computing to digital computing.

I refer to the work done in selecting the correct computations from
many parallel ones, which should be applicable in some sense.

> What needs to be done is for trained people with an *engineering*
> mindset to sit down and squarely face the problem of multi-level
> concurrency.
>
> I expect the solutions will roll out in layers of successive refinement,
> but we haven't yet even chosen to directly address the problem.

It won't be long now. We can't wait much longer for companies to
engineer processors with massively faster sequential processing speeds
before realising that they can't :-)

> >>>>>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?
>
> Well, after spending 50 years on notation, how about starting in
> on parallelism?  ;-)
>
> I realize that there have been a few seminal approaches to supporting
> parallelism in languages--including the radically concurrent applicative
> languages--but none of the "rubber" was ever brought anywhere near the
> "road" of real systems, let alone ones with hierarchical connectivity.
>
> There are already dozens of designers focusing on notation.  I'm
> actually making a *plea* for more focus areas--and for one of
> them to be concurrency!

You're absolutely right, but there's a degree of dependency between the
two that needs to be addressed, and part of that is engineering out old
notational forms which inhibit the progress of parellel system design.

Matt