Re: multi/tasking/processing

[Eugen Leitl <ui22204@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, 17 Aug 1995, Francois-Rene Rideau wrote:

[ stuff you all already saw snipped ]

>    Again, all speed-efficient messages should be (dynamically) inlined.
> E.g. integer "+" should be inlined to proper assembly instructions.

But how do you know that the message sent at some time will be "+"? 
You can't know this at compile time, unless you severly restrict 
programming degrees of freedom. Either I can't dig what you say, or 
you use an utterly unusual programming style/language.

> > Call it OS, call it whatever. Certain methods, I choose to assotiate
> > with the "OS" object (node13.OS.flush_1(objectID)) wind up called
> > lots of time.
>
>    Then why dispatch call to them through a kernel ? (Dynamically) link
> your code so it calls the right routine.

Again, I have a simulation. Objects come & go around the network to level
the load, get swapped in/out, die & get born. Objects produce & consume
message streams. I can't predict all this, can I? If I could: why am I
running this thing at all, then? I could predict the result, as well.
 
> > Microkernels are too big, nanokernel is the thing.
>    Nano- or Micro-, they are the same. The principle of a kernel itself
> is deeply broken. What is a kernel ? Just some overhead to dispatch
> routines at run-time. It just has no point. Code should be bound whenever
> the binding is known, not before (not possible!), not after (and at least,
> just once, not once per call).

I mean you have to have a basic functionality in a node to be able to
run applications at all. Of course it may vary from node to node
what exact set of methods you need. I didn't mean that these methods
occupy a contigous memory block (though it would be wise if we want
to hardware r/w protect them). But some (varying) fraction of resources, 
memory/MIPS/network has to be allocated to these set of methods in 
each node. Unless you propose some hardware providing this functionality,
which is certainly the very opposite of MISC, we _need_ an "OS".
(Is this a good definition?)

Essentially, I would like to have this functionality provided via a VM
threaded code, the code located at certain fixed addresses in
on-chip SRAM to enable future chips decoding certain opcodes directly,
for the sake of efficiency (not MISC this, agreed. But every 
architecture grows encumbring mussels on its hull with time).

[ hardware SEND ]

>    No ! Certainly not ! OO-in-hardware was tried at the beginning of
> the eighties (see intel i832), and led to bloated chips that were
> big and slow. Just *the opposite of MISC*. I've thought about it a lot

I think this needs not to be. A simple transparent way of sending 
messages to both node-local and off-node objects is sufficient.
Especially, if network processor/router interface is really good.

I mean, you have an object ID. How the objectID encodes object
position in node should be of no interest to you (in fact, some
objects should even _be prevented_ from learning this). You rely
on the OS benchmarking message traffic in the background and
constantly re-positioning the object to minimize net load. So
you push your message on stack (verbatim or reference msg) and
say SEND. It invokes some unspecified (hardware/software) machinery
which either direct-lookups or hash-lookups the according object,
etc. etc.

What's wrong with this scheme?

> back in time, and when I evaluated the cost, I understood it was
> not feasible. Of course, like you, I regretted the security such
> design would have brought, until I discovered formal methods for
> programming, which allow you to compile *secure* code in a
> strongly specifiable language into *fast* code for efficient
> machines.

I mean there is a reason why C++ is a kludge. Have you discovered
a panacea? With compile-time checks only? I dunno.

> > Object's data is private. Some object methods are private, some
> > public. (Verbatim and threaded methods). I can't know to which
> > objects I will be talking to at compile time. How can I compile
> > direct method calls without runtime checks?
>    Recent studies showed that in a strongly typed language with
> bounds checking, most (>95%) run-time checks could be removed
> using simple optimization techniques.

I think this is a valuable technique. However, there is a reason
why one can't compile LISP code entirely without run-time checks,
either by software or hardware. You gain speed, you lose flexibility.
And vice versa. 
 
> > There are many shared methods. Kill, flush, retrieve, relocate, etc.
> > which each object must understand. Instead of having stupid redundant
> > local jump tables and a dispatcher, the message gets diverted to the 
> > according OS methods by a central (preferably hardware) dispatcher, 
> > only then branching to local dispatcher. 
> >
> > Why not?
> Because it wastes lots of resource for a job that is best done at
> compile-time, or at bind-time in a dynamically partially evaluating
> system.

I am not convinced. I wish I could have a look at some of your code/problems.

[ basic OS methods ]

>    Then, what method should be "bare-bone" is a completely subjective
> matter. People doing lots of graphics or programming a GUI will
> require lots of graphics primitives in here; end-users will want
> a full-fledge UI included; people in embedded systems will want the least
> possible included, etc. There is *no reason* why some people should be
> priviledged to the great demise of everyone else, or why the OS should
> grow to monstruous sizes in trying to satisfy everybody. Actually,
> there are lots of reasons why not, and nobody is satisfied in the end.
> Instead, the OS should scale to the user's need.

Of course. At no point did I talk about monolithic OSses. Their
time is gone. Of course one needs monstrous amounts of code
to provide monstrous amounts of functionality, just look at Linux/GNU
(_not_ the kernel. The entire package).
There is no distinct boundary between application and OS. But still:
there is no rule why all this code should be in main store and in 
each node at the same time, even if it is not used. Of course.

(But: you can't have functionality without code. Albeit a high-density/
low redundancy one).

[ snip ]
>    Why should applications have no idea ? On the contrary, the more we
> know, the better we can "optimize" code. Well, of course, there are cases

The more you know about a particular installation, the less portable
your code. (Old Chinese proverb).

> when you don't know, and you need dynamic evaluation. But why re-link
> at each call ? You just need link once per binding.

Alas, I am not convinced.

[ bugs & Co ]

>    You will _always_ have *buggy* software. My point is you can have
> *crash-proof* software, which is quite another thing. So you _don't_

I say you can't have absolutely crash-proof software without a minimum of
hardware protection.

> need MMU, user/kernel protection and suches, which are but a lot
> of hardware overhead that won't ever buy you crashproofing, but will
> waste a lot of resources. Instead (assuming you need crashproof software),

I can assure you, network code need be crashproof. Even more, you'd
need massive cryptography to make really sure the code to be
crashproof. At the very least you need a (temporary) restrictive means
to localize bombing code even in a single multi-node box.

> you need high-level programmation tools, with programmable code
> transformation tools to obtain *fast* secure programs.

There is no power without the price.

[ snip ]
>    Yes you can (but you need a lot of investment over existing software).
> That's called formal methods for programming and correctness proofs.

You can't use this even in purely functional Lisp code. The power
of proof machinery is limited. If you can prove that the certain
piece of code is bugless, then it is not doing anything useful.
And vice versa.

> It works only when you have a mathematically expressible specification
> of what you want your program to do or not to do, and you need to prove
> things about your program (and to because it's too hard to get from an
> existing program, you need program in a language that makes proofs easy,
> and code proofs and programs together).

I think this is not a mere lingo problem, though there are languages
facilitating formal proofs. I think the methodology is fundamentally
flawed.

> >> tools, like strongly typed languages, and correction proof software.
> > Proofs are worth nothing in the real world.
>    They sure are worth as much as run-time checking, and much more than
> MMU-based protection, and they apply in much more cases.

Again, I am not convinced. Prove your point with code.
 
> >> I'm sure this is the only possible long-term future for the software
> >> industry, in the same way as I'm sure MISC is the only possible
> >> long-term future for the hardware industry.
> > These methods will come, but I essentially think nonalgorithmic
> > systems are the only robust ones.
> What are you calling "nonalgorithmic systems" ???
> AFAIK, all digital computers run algorithms. Are you suggesting going
> back to analog computers ?

Of course not. I refered to brittleness of current systems vs. robust
natural information processing systems. These work nonalgorithmically.
One can simulate the latter on a digital machine, but not emulate them.
Special hardware will be needed, and maspar MISC clusters is a point
in the right direction. (I am refering to AN/CA systems).

[ ... ]
>    Have you ever heard about compilers ? And again, bug-free *is* possible

Either: a) you run your code on a hardware interpreter without any
means of protection, but real fast, or b) you use a slow but safe software
interpreter mimicking the same hardware.

b) is possible only in the debugging stage (remember UCSD?)

Is there a third, fundamentally different possibility I do not see
yet?

> if only you have a bug free specification. And if the crash-free part
> of the specification is ok, at least you can have crash-free code.
> Compiling can select the few right checks to do instead of the many wrong
> ones you're doing with hardware protection.

Convince me. So far, you have not been able. Show code.

-- Eugene

> 
> --    ,        	                                ,           _ v    ~  ^  --
> -- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
> --                                      '                   / .          --
> Join the TUNES project for a computing system based on computing freedom !
> 		   TUNES is a Useful, Not Expedient System
> WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/";
>