[cap-talk] Academic and patent disconnect - rant, taocp

[Jed Donnelley]

cap-talk,

OK, I admit up front this is a rant.

<rant>
Sometimes I find it difficult to believe just
how fragmented our IT profession can become.
Perhaps it's easier to see today when we have
so much more information at our fingertips
(literally), but still - consider these two
cases that I recently ran into:

A.  I did look up the "Thoth" operating system
work done under David Cheriton at the University
of Waterloo, e.g.:

http://delivery.acm.org/10.1145/360000/359074/p105-cheriton.pdf?key1=359074&key2=3819345021&coll=GUIDE&dl=GUIDE&CFID=20066187&CFTOKEN=48757567

(if you have access to the ACM archives)

Incidentally, there is no stretch of the imagination
that can make Thoth a "capability" system.

What outraged me was this statement in
the above paper from 1979:
__________
"Most previous work on software portability has focused
on problems of porting programs over different
operating systems as well as different hardware. To our
knowledge, this is the first time an entire system has
been designed for portability."
___________

By 1979 the LTSS system at LLNL had already been
running as a portable high level language system
for about 13-14 years.  It had been ported among
at least four very different architectures:

1.  the CDC 6600,

2.  the CDC 7600 (sound similar, but
the distinction with "large core" memory made
them quite distinct as did their I/O architectures)

3.  The Star-100 - a hugely different beast with
sophisticate virtual memory and a very rich vector
instruction set plus distinct I/O facilities

4.  The Cray-1 - again a very different beast.

The above not to mention that LTSS was used at
a number of sites within the Department Of Energy
and, renamed "CTSS" (Cray TimeSharing System, but
still supported mostly by LLNL) was being distributed
to more Cray sites.

At LLNL we though we might have been fairly early
adopters of portable OSs (1965), but we made no
claim to being first and certainly thought there
were others out there, including Unix by the
early 1970s - which of course was very widely
ported.

Might there be some other way to interpret
that statement from the Thoth paper?


B.  In the patent area, consider this one:

http://www.google.com/patents?id=yAgWAAAAEBAJ&dq=patent:6874027

Patent number: 6874027
Filing date: Jun 9, 2000
Issue date: Mar 29, 2005
Inventor: Robert M. English
Assignee: Network Appliance, Inc.

Abstract:
A method and system for providing the functionality of
dynamically-allocated threads in a multithreaded system,
in which the operating system provides only
statically-allocated threads. With this functionality,
a relatively large number of threads can be maintained
without a relatively large amount of overhead (either in
memory or processor time), and it remains possible to
produce program code without undue complexity. A plurality
of dynamically-allocated threads are simulated using a
single statically-allocated thread, but with state information
regarding each dynamically-allocated thread maintained within
the single statically-allocated thread. The single
statically-allocated thread includes, for each procedure
call that would otherwise introduce a new simulated thread,
a memory block including (1) a relatively small procedure call
stack for the new simulated thread, and (2) a relatively small
collection of local variables and other state information for
the new simulated thread.

Any questions or thoughts about what the description looks like?
Read on (above) if you have any.  I read through enough to convince
me it was the "obvious" thing.

We were using such a mechanism for running asynchronous threads
within processes by 1980 anyway, and I had no reason to believe
that it was original with us.  We adopted a "spaghetti" stack
mechanism (dynamically allocating new stack frame segments
as needed) along with tying stacks to threads and scheduling
them early in our NLTSS development as it was vital for our
support for multiple simultaneous requests, each of which
could block essentially on I/O (though also of course locks
on shared resources).

Again I wonder - could there be something I'm missing in
the description of the problem and solution??



What's the problem here?  Do we need another "Art of Computer
Programming"?  Come to think of it, I wonder if the above
scheme is in one of Knuth's books.  That's not so easy to
check, but it doesn't look likely (see below).

Hmmm.  There's a thought.  I wonder if it might be possible
to induce Dr. Knuth to release his book series to the Web
for all to read??  There is a situation where the financial
considerations clearly come to the fore.  I of course think
he should benefit from that monumental work, but I would hope
that he could do so in a way that makes it more readily available
to people on the Web...

Having looked just now at:

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

I think not.  Also I don't see anyplace in there that
looks likely for a mechanism to build asynchronous
threads as stack switching over context heavy parallel
processes.  More's the pity.

Hmmm.  Maybe it would be possible for some subscription
service - e.g. like the ACM - to buy his books for subscription
based publication on the Web?  Of course at that point algorithms
would quickly spread.  Mix?  Heh.

Does anybody really think he'll publish volumes 4 and 5?
Are bets being taken?  This quote may be relevant:
(from: http://www-cs-faculty.stanford.edu/~knuth/taocp.html )

"...but computer science has grown to the point where I
cannot hope to be an authority on all the material covered
in these books. Therefore I'll need feedback from readers
in order to prepare the official volumes later."

</rant>

--Jed  http://www.webstart.com/jed/