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

Re: 6502 illegal opcodes questions

mdj wrote:

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.


Corporate R&D budgets have been systematically slashed to make
the next quarter look good.  ;-(


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.


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 :-)


You and Kahan agree--double-precision is the amateur's best friend.


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.


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.


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 :-(


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.


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 "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.
;-)


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.


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


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)


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


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.


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.


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.


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

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


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


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.


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

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!  ;-)

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