Re: 6502 illegal opcodes questions

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

Michael J. Mahon wrote:

> > 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.
>
> Corporate R&D budgets have been systematically slashed to make
> the next quarter look good.  ;-(

There's an unfortunate reality that as corporations grow, more and more
of the resources get allocated to maintaining their current size.

> >>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.
>
> Software folks are always pushing their own flavor of complexity, so
> they don't take time to learn from what's been going on in the real
> world very much.

Aint that the truth.

> >
> > Hence my lack of faith in languages that bind us too tightly to
> > (hardware) architectural borders.
>
> But the solution to this kind of varability is run-time adaptation,
> not anything linguistic (= static).  Language has pretty much done its
> thing by the time it has allowed local variables to be grouped.

That's right, but it's important that we actually *use* languages that
allow this kind of runtime adaptation.

> > Many of them still on the market, being espoused as equivalent or
> > superior to competing solutions :-(
>
> I know, but Darwin will have his way with them...  ;-)
>
> The only way to be successful and persistently stupid is if everyone
> else is also persistently stupid--fortunately, an unstable proposition.

It'd be better if Darwin would prune the tree from both ends though
wouldn't it :-)

> >>>>>>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.
>
> Of course.  HP-UX was managing large numbers of processors with
> excellent performance early in the game.
>
> I was trying to get some very real stones turned before they became
> prevalent.
>
> >>>>>>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 ;-)
>
> Well, I'll grant that operating as if there is only one contiguous
> space holding all data is a problem.  Now, treating data as if it were
> "segmented" (which everyone hates) may prove to be quite useful...   ;-)

The solution is to treat data such that you're unconcerned by it's
physical organisation, this making it possible (via instrumentation) to
observe the partitioning scheme that's most appropriate for that
particular application. I'm glad you see this as a problem holding us
back, and note that it affects my concerns (portability, security) as
much as it affects yours.

> >>>>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.
>
> Such is the nature of learning.  And such is the inefficacy of prophecy.
> ;-)

Only when the congregation is worshiping at the feet of false prophets
;-)

> >>>>>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.
>
> Actually, 60Hz is plenty fast enough to find almost anything of
> real interest on a slow machine.  And it is infrequent enough that
> you can actually execute some code without it being intrusive.

True. Actually I've found 60Hz to be a good slicing interval on the
Apple II, perhaps moreso when the machine accelerated than not. I'm
looking forward though to having a programmable timer source in the
machine - something I've been missing for a long time.

> > It's good fun exploring these ideas on smaller environments that have
> > nice predictable behaviors, but you already know this :-)
>
> ...and I *love* it!  Of course, I love it even more when I fail to
> predict a behavior.  ;-)

And it's very enlightening just how frequently this occurs, even on
machines that are very humble. There is so much to be learned.

> Yes, I always provided a way for processes to handle interrupts
> directed to them.  (Most language designers hated the idea.)

It's hard enough getting OS designers to acknowledge the issue :-(

Most language designers are fundamentally opposed to concurrency
concerns entering the language. This is a folly, and a real impediment
to having modern system provide realtime scheduling :-(

> That is the very simple approach which I believe the encoders themselves
> should do after taking a "census" of the system they are running on.

Yeah - it's simple enough to get a poor mans version through a simple
wrapper script, but you're right encoders need to do this. Bring on
parallelism support in languages says I !

> Quantum computing evaluates all possible computations simultaneously,
> so the "selection" of the answer tends to be done at the end.  ;-)
>
> NP-complete problems become solvable because a huge combinatoric
> space of possible solutions is explored "in superposition" in the
> time required to explore a single solution.  Then you have to "read
> out" the final state(s) to discover the solution(s).

Parallelism provides a reduction in time required to compute many
combinatorial problems too.

> I'm reminded of "the answer to the ultimate question".  At some point,
> you realize that you really want the ultimate question, too.  ;-)

Indeed! The answer is arbitrary without the question :-)

> >>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 :-)
>
> Yes, I think that has dawned on them as they whip their design teams
> harder while watching their stock stagnate and then fall...

I think it has dawned on them the stock price is falling, but beyond
that, the actual measures of such failure tend to evade being
addressed. :-(

> > 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.
>
> Again, I would say that very little of the current linguistic goals have
> more than incidental relevance to parallelism.  It's a plain case of
> "looking where there's light instead of where they lost it".

Indeed the things I'd like to change are fairly little things too, yet
the degree of defiance that ones faces when suggesting it is staggering
:-)

> If an alien intelligence is watching, a little box on page 11,325 of
> their weekly report must be devoted to a betting pool on how long it
> will take us to figure out that we were working on the wrong problem.
> (Just in *this* area--there are lots of boxes on other pages!  ;-)

And the one who wins the pool probably made his guess based on looking
at their own history ;-)