[TUHS] Early multiprocessor Unix

[TUHS] Early multiprocessor Unix

[Paul Ruizendaal]

The discussion about the 3B2 triggered another question in my head: what were the earliest multi-processor versions of Unix and how did they relate?

My current understanding is that the earliest one is a dual-CPU VAX system with a modified 4BSD done at Purdue. This would have been late 1981, early 1982. I think one CPU was acting as master and had exclusive kernel access, the other CPU would only run user mode code.

Then I understand that Keith Kelleman spent a lot of effort to make Unix run on the 3B2 in a SMP setup, essentially going through the source and finding all critical sections and surrounding those with spinlocks. This would be around 1983, and became part of SVr3. I suppose that the “spl()” calls only protected critical sections that were shared between the main thread and interrupt sequences, so that a manual review was necessary to consider each kernel data structure for parallel access issues in the case of 2 CPU’s.

Any other notable work in this area prior to 1985?

How was the SMP implementation in SVr3 judged back in its day?

Paul

[TUHS] Re: Early multiprocessor Unix

[Larry Stewart]

[-- Attachment #1: Type: text/plain, Size: 1329 bytes --]

There's a 1975 paper about an MP Unix at the Naval Postgraduate School by Hawley and Meyer.

https://calhoun.nps.edu/handle/10945/20959


> On Nov 28, 2022, at 8:28 AM, Paul Ruizendaal <pnr@planet.nl> wrote:
> 
> The discussion about the 3B2 triggered another question in my head: what were the earliest multi-processor versions of Unix and how did they relate?
> 
> My current understanding is that the earliest one is a dual-CPU VAX system with a modified 4BSD done at Purdue. This would have been late 1981, early 1982. I think one CPU was acting as master and had exclusive kernel access, the other CPU would only run user mode code.
> 
> Then I understand that Keith Kelleman spent a lot of effort to make Unix run on the 3B2 in a SMP setup, essentially going through the source and finding all critical sections and surrounding those with spinlocks. This would be around 1983, and became part of SVr3. I suppose that the “spl()” calls only protected critical sections that were shared between the main thread and interrupt sequences, so that a manual review was necessary to consider each kernel data structure for parallel access issues in the case of 2 CPU’s.
> 
> Any other notable work in this area prior to 1985?
> 
> How was the SMP implementation in SVr3 judged back in its day?
> 
> Paul

[-- Attachment #2: Type: text/html, Size: 1871 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 2627 bytes --]

As far as I know, the first non-commercial work was done at the Naval Post
Grad school with V6.  I have never seen the code for it, only a paper, so I
don't know too much about it to comment.

A few years later (1980), Goble's work became the Purdue Vax [
https://en.wikipedia.org/wiki/George_H._Goble] - which used a master-slave
configuration. He spliced a second 780 CPU onto the SMB and, with some
interesting work, allowed the second CPU to run user code.  This was
extremely effective for their usage case -- timesharing of students.  If we
don't have the code on TUHS, we should probably dig it up, as it was widely
distributed. The other thing he did was splice an 11/40 onto the UBA of the
same system for debugging - which was a pretty cool hack.  He found a
couple of interesting BSD kernel issues, including a famous CVE using his
real-time monitor -- there is a USENIX paper on that tool that is work
checking out.

The first commercial MP Unix was the Masscomp MC500/MP, which was
originally developed as Goble-style Master/Slave and released in RTU 2.0.
A year later, with RTU 3.0 and the release of the MC5000 family, it was
fully SMP.

After that, several SMP UNIX started to appear.   Each uses its own lock
scheme.   If you are interested, I recommend getting a copy of Schimmel's
book: 'Unix on Modern Processors' which discusses many (most) of the
challenges.


ᐧ

On Mon, Nov 28, 2022 at 8:25 AM Paul Ruizendaal <pnr@planet.nl> wrote:

> The discussion about the 3B2 triggered another question in my head: what
> were the earliest multi-processor versions of Unix and how did they relate?
>
> My current understanding is that the earliest one is a dual-CPU VAX system
> with a modified 4BSD done at Purdue. This would have been late 1981, early
> 1982. I think one CPU was acting as master and had exclusive kernel access,
> the other CPU would only run user mode code.
>
> Then I understand that Keith Kelleman spent a lot of effort to make Unix
> run on the 3B2 in a SMP setup, essentially going through the source and
> finding all critical sections and surrounding those with spinlocks. This
> would be around 1983, and became part of SVr3. I suppose that the “spl()”
> calls only protected critical sections that were shared between the main
> thread and interrupt sequences, so that a manual review was necessary to
> consider each kernel data structure for parallel access issues in the case
> of 2 CPU’s.
>
> Any other notable work in this area prior to 1985?
>
> How was the SMP implementation in SVr3 judged back in its day?
>
> Paul

[-- Attachment #2: Type: text/html, Size: 3981 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 3200 bytes --]

Paul, the other thing I should point out -- ghg's work was
widely distributed amount the BSD licenses. I somewhat wonder why the Naval
Post Grad school's work was not.   My guess is that USENIX was still in its
formative stages when the latter did their work, whereas, by the time of
George's hack, BSD/Vaxen was being used for teaching as University
timesharing systems so his 'upgrade' was a cheap solution.
ᐧ

On Mon, Nov 28, 2022 at 9:05 AM Clem Cole <clemc@ccc.com> wrote:

> As far as I know, the first non-commercial work was done at the Naval Post
> Grad school with V6.  I have never seen the code for it, only a paper, so I
> don't know too much about it to comment.
>
> A few years later (1980), Goble's work became the Purdue Vax [
> https://en.wikipedia.org/wiki/George_H._Goble] - which used a
> master-slave configuration. He spliced a second 780 CPU onto the SMB and,
> with some interesting work, allowed the second CPU to run user code.  This
> was extremely effective for their usage case -- timesharing of students.
> If we don't have the code on TUHS, we should probably dig it up, as it was
> widely distributed. The other thing he did was splice an 11/40 onto the UBA
> of the same system for debugging - which was a pretty cool hack.  He found
> a couple of interesting BSD kernel issues, including a famous CVE using his
> real-time monitor -- there is a USENIX paper on that tool that is work
> checking out.
>
> The first commercial MP Unix was the Masscomp MC500/MP, which was
> originally developed as Goble-style Master/Slave and released in RTU 2.0.
> A year later, with RTU 3.0 and the release of the MC5000 family, it was
> fully SMP.
>
> After that, several SMP UNIX started to appear.   Each uses its own lock
> scheme.   If you are interested, I recommend getting a copy of Schimmel's
> book: 'Unix on Modern Processors' which discusses many (most) of the
> challenges.
>
>
> ᐧ
>
> On Mon, Nov 28, 2022 at 8:25 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>
>> The discussion about the 3B2 triggered another question in my head: what
>> were the earliest multi-processor versions of Unix and how did they relate?
>>
>> My current understanding is that the earliest one is a dual-CPU VAX
>> system with a modified 4BSD done at Purdue. This would have been late 1981,
>> early 1982. I think one CPU was acting as master and had exclusive kernel
>> access, the other CPU would only run user mode code.
>>
>> Then I understand that Keith Kelleman spent a lot of effort to make Unix
>> run on the 3B2 in a SMP setup, essentially going through the source and
>> finding all critical sections and surrounding those with spinlocks. This
>> would be around 1983, and became part of SVr3. I suppose that the “spl()”
>> calls only protected critical sections that were shared between the main
>> thread and interrupt sequences, so that a manual review was necessary to
>> consider each kernel data structure for parallel access issues in the case
>> of 2 CPU’s.
>>
>> Any other notable work in this area prior to 1985?
>>
>> How was the SMP implementation in SVr3 judged back in its day?
>>
>> Paul
>
>

[-- Attachment #2: Type: text/html, Size: 5172 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 2973 bytes --]

On Mon, Nov 28, 2022, 7:07 AM Clem Cole <clemc@ccc.com> wrote:

> As far as I know, the first non-commercial work was done at the Naval Post
> Grad school with V6.  I have never seen the code for it, only a paper, so I
> don't know too much about it to comment.
>

I tried to find the code a couple of years ago, but no joy. And the timing
suggested he may have started with/used V5, since the paper is dated June
75 and V6 was released in May 75.

Warner

A few years later (1980), Goble's work became the Purdue Vax [
> https://en.wikipedia.org/wiki/George_H._Goble] - which used a
> master-slave configuration. He spliced a second 780 CPU onto the SMB and,
> with some interesting work, allowed the second CPU to run user code.  This
> was extremely effective for their usage case -- timesharing of students.
> If we don't have the code on TUHS, we should probably dig it up, as it was
> widely distributed. The other thing he did was splice an 11/40 onto the UBA
> of the same system for debugging - which was a pretty cool hack.  He found
> a couple of interesting BSD kernel issues, including a famous CVE using his
> real-time monitor -- there is a USENIX paper on that tool that is work
> checking out.
>
> The first commercial MP Unix was the Masscomp MC500/MP, which was
> originally developed as Goble-style Master/Slave and released in RTU 2.0.
> A year later, with RTU 3.0 and the release of the MC5000 family, it was
> fully SMP.
>
> After that, several SMP UNIX started to appear.   Each uses its own lock
> scheme.   If you are interested, I recommend getting a copy of Schimmel's
> book: 'Unix on Modern Processors' which discusses many (most) of the
> challenges.
>
>
> ᐧ
>
> On Mon, Nov 28, 2022 at 8:25 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>
>> The discussion about the 3B2 triggered another question in my head: what
>> were the earliest multi-processor versions of Unix and how did they relate?
>>
>> My current understanding is that the earliest one is a dual-CPU VAX
>> system with a modified 4BSD done at Purdue. This would have been late 1981,
>> early 1982. I think one CPU was acting as master and had exclusive kernel
>> access, the other CPU would only run user mode code.
>>
>> Then I understand that Keith Kelleman spent a lot of effort to make Unix
>> run on the 3B2 in a SMP setup, essentially going through the source and
>> finding all critical sections and surrounding those with spinlocks. This
>> would be around 1983, and became part of SVr3. I suppose that the “spl()”
>> calls only protected critical sections that were shared between the main
>> thread and interrupt sequences, so that a manual review was necessary to
>> consider each kernel data structure for parallel access issues in the case
>> of 2 CPU’s.
>>
>> Any other notable work in this area prior to 1985?
>>
>> How was the SMP implementation in SVr3 judged back in its day?
>>
>> Paul
>
>

[-- Attachment #2: Type: text/html, Size: 4853 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 3416 bytes --]

On Mon, Nov 28, 2022, 7:15 AM Clem Cole <clemc@ccc.com> wrote:

> Paul, the other thing I should point out -- ghg's work was
> widely distributed amount the BSD licenses. I somewhat wonder why the Naval
> Post Grad school's work was not.   My guess is that USENIX was still in its
> formative stages when the latter did their work, whereas, by the time of
> George's hack, BSD/Vaxen was being used for teaching as University
> timesharing systems so his 'upgrade' was a cheap solution.
> ᐧ
>


I know the Perdue work on Kirk's DVD collection....

Warner

Warner

On Mon, Nov 28, 2022 at 9:05 AM Clem Cole <clemc@ccc.com> wrote:
>
>> As far as I know, the first non-commercial work was done at the Naval
>> Post Grad school with V6.  I have never seen the code for it, only a paper,
>> so I don't know too much about it to comment.
>>
>> A few years later (1980), Goble's work became the Purdue Vax [
>> https://en.wikipedia.org/wiki/George_H._Goble] - which used a
>> master-slave configuration. He spliced a second 780 CPU onto the SMB and,
>> with some interesting work, allowed the second CPU to run user code.  This
>> was extremely effective for their usage case -- timesharing of students.
>> If we don't have the code on TUHS, we should probably dig it up, as it was
>> widely distributed. The other thing he did was splice an 11/40 onto the UBA
>> of the same system for debugging - which was a pretty cool hack.  He found
>> a couple of interesting BSD kernel issues, including a famous CVE using his
>> real-time monitor -- there is a USENIX paper on that tool that is work
>> checking out.
>>
>> The first commercial MP Unix was the Masscomp MC500/MP, which was
>> originally developed as Goble-style Master/Slave and released in RTU 2.0.
>> A year later, with RTU 3.0 and the release of the MC5000 family, it was
>> fully SMP.
>>
>> After that, several SMP UNIX started to appear.   Each uses its own lock
>> scheme.   If you are interested, I recommend getting a copy of Schimmel's
>> book: 'Unix on Modern Processors' which discusses many (most) of the
>> challenges.
>>
>>
>> ᐧ
>>
>> On Mon, Nov 28, 2022 at 8:25 AM Paul Ruizendaal <pnr@planet.nl> wrote:
>>
>>> The discussion about the 3B2 triggered another question in my head: what
>>> were the earliest multi-processor versions of Unix and how did they relate?
>>>
>>> My current understanding is that the earliest one is a dual-CPU VAX
>>> system with a modified 4BSD done at Purdue. This would have been late 1981,
>>> early 1982. I think one CPU was acting as master and had exclusive kernel
>>> access, the other CPU would only run user mode code.
>>>
>>> Then I understand that Keith Kelleman spent a lot of effort to make Unix
>>> run on the 3B2 in a SMP setup, essentially going through the source and
>>> finding all critical sections and surrounding those with spinlocks. This
>>> would be around 1983, and became part of SVr3. I suppose that the “spl()”
>>> calls only protected critical sections that were shared between the main
>>> thread and interrupt sequences, so that a manual review was necessary to
>>> consider each kernel data structure for parallel access issues in the case
>>> of 2 CPU’s.
>>>
>>> Any other notable work in this area prior to 1985?
>>>
>>> How was the SMP implementation in SVr3 judged back in its day?
>>>
>>> Paul
>>
>>

[-- Attachment #2: Type: text/html, Size: 5996 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 859 bytes --]

On Mon, Nov 28, 2022 at 9:16 AM Warner Losh <imp@bsdimp.com> wrote:

>
>
> On Mon, Nov 28, 2022, 7:07 AM Clem Cole <clemc@ccc.com> wrote:
>
>> As far as I know, the first non-commercial work was done at the Naval
>> Post Grad school with V6.  I have never seen the code for it, only a paper,
>> so I don't know too much about it to comment.
>>
>
> I tried to find the code a couple of years ago, but no joy. And the timing
> suggested he may have started with/used V5, since the paper is dated June
> 75 and V6 was released in May 75.
>
Thanks - that makes sense.   As I said, I never saw the code, and again, it
agrees with my observation that this was 'pre-USENIX,' particularly since I
believe that those folks are in CA and the original USENIX people were in
NYC and Boston folks, so they would have been less likely to be a part.
ᐧ

[-- Attachment #2: Type: text/html, Size: 2042 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Paul Winalski]

On 11/28/22, Clem Cole <clemc@ccc.com> wrote:
>
> A few years later (1980), Goble's work became the Purdue Vax [
> https://en.wikipedia.org/wiki/George_H._Goble] - which used a master-slave
> configuration. He spliced a second 780 CPU onto the SMB

SBI (Synchronous Backplane Interconnect), the data bus for the 11/780.
The KA780 CPU plugged into it, as did the memory controller, the UBA
(UNIBUS adapter), the MBA (MASSBUS adapter), and the CI (Computer
Interconnect, the high-speed network used for VAXcluster
communication).

> and, with some
> interesting work, allowed the second CPU to run user code.  This was
> extremely effective for their usage case -- timesharing of students.

Normally only one KA780 CPU was attached to the SBI, but there was
nothing physical or electronic to prevent plugging in a second one.
IIRC there were a couple of places in the 11/780 microcode that
assumed there was only one CPU on the SBI, but that was easily
tweaked.  DEC productized the two-processor asymmetric multiprocessor
configuration as the VAX-11/782.  The software development tools group
that I worked in was one of the two beta test sites for the 782 (the
other was MIT).  I was the system manager for that machine.  Ours ran
VMS, of course, not Unix, but with the same idea that only user mode
code was scheduled to run on the second processor.  All I/O and kernel
mode code was done on the primary.  It scaled pretty well for
compute-intensive loads.  It actually ran slower than a single
processor under high I/O loads, though, and it gave no advantage to
real-time workloads.

I don't know if Ultrix ever supported the 11/782.  The product had a
rather short lifetime, as it was soon superseded by VAX models that
were designed for symmetric multiprocessing from the ground up, and
full SMP support had been implemented in VMS and Ultrix.

-Paul W.

[TUHS] Re: Early multiprocessor Unix

[Clem Cole]

[-- Attachment #1: Type: text/plain, Size: 369 bytes --]

On Mon, Nov 28, 2022 at 11:30 AM Paul Winalski <paul.winalski@gmail.com>
wrote:

> > configuration. He spliced a second 780 CPU onto the SMB
>
> SBI (Synchronous Backplane Interconnect),
>
right SBI -- thanks, Paul -- too many TLAs - bad cache refill.


>
> I don't know if Ultrix ever supported the 11/782.
>
no - the Ultrix group never bothered.

ᐧ

[-- Attachment #2: Type: text/html, Size: 1569 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Jonathan Gray]

On Mon, Nov 28, 2022 at 02:24:52PM +0100, Paul Ruizendaal wrote:
> The discussion about the 3B2 triggered another question in my head: what were the earliest multi-processor versions of Unix and how did they relate?
> 
> My current understanding is that the earliest one is a dual-CPU VAX system with a modified 4BSD done at Purdue. This would have been late 1981, early 1982. I think one CPU was acting as master and had exclusive kernel access, the other CPU would only run user mode code.
> 
> Then I understand that Keith Kelleman spent a lot of effort to make Unix run on the 3B2 in a SMP setup, essentially going through the source and finding all critical sections and surrounding those with spinlocks. This would be around 1983, and became part of SVr3. I suppose that the “spl()” calls only protected critical sections that were shared between the main thread and interrupt sequences, so that a manual review was necessary to consider each kernel data structure for parallel access issues in the case of 2 CPU’s.
> 
> Any other notable work in this area prior to 1985?

HP-UX on FOCUS/series 500?
https://www.openpa.net/systems/hp-9000_520.html

https://www.tuhs.org/Archive/Documentation/AUUGN/AUUGN-V05.3.pdf
Jeff Lindberg
A Layered Implementation of the UNIX Kernel on the HP9000 Series 500
Computer

"The HP9000 Series 500 computers are based on a proprietary 32 bit
microprocessor chip set with stack architecture. It has user-transparent
multi-CPU support, for which they included semaphores and a very
carefully worked out scheduler.

HP-UX is based on top of an operating system called SUN (no relation to
Sun Microsystems Inc.). The SUN operating system was intended to be a
modern operating system to support HP's desktop BASIC system. As
designed, though, it turns out to be language independent, and had
several other features that made it attractive as a base upon which to
build a UNIX implementation."

https://archive.org/details/1983-proceedings-unicom-san-diego/page/119/mode/2up
Frederick W. Clegg
Hewlett-Packard’s Entry into the UNIX Community

"Several motivations prompted this somewhat unconventional
implementation of the HP-UX kernel on the HP 9000. It should be
understood that much of the low- level, machine-dependent software for
the HP 9000 was complete before a final commitment was made to offer
UNIX on this product line. Thus reinvention of device and interface
drivers, low-level memory management routines, power-up code, and
architecturally-dependent utility routines was avoided by this approach.
Additionally, this approach permitted leverage of software developed to
support graphics and database management from the BASIC environment.

Additionally, SUN has a number of features which are not present in AT&T
UNIX. These provide opportunities for HP-UX to make a contribution above
and beyond other UNIX implementations. Such features include real-time
performance in the area of interrupt response time and process
switching, support for multiple processors, and reliability in the face
of system errors."

some more details in
https://www.hpl.hp.com/hpjournal/pdfs/IssuePDFs/1984-03.pdf
HP Journal, March 1984, Volume 35, Number 3

[TUHS] Re: Early multiprocessor Unix

[Jonathan Gray]

On Mon, Nov 28, 2022 at 02:24:52PM +0100, Paul Ruizendaal wrote:
> The discussion about the 3B2 triggered another question in my head: what were the earliest multi-processor versions of Unix and how did they relate?
> 
> My current understanding is that the earliest one is a dual-CPU VAX system with a modified 4BSD done at Purdue. This would have been late 1981, early 1982. I think one CPU was acting as master and had exclusive kernel access, the other CPU would only run user mode code.
> 
> Then I understand that Keith Kelleman spent a lot of effort to make Unix run on the 3B2 in a SMP setup, essentially going through the source and finding all critical sections and surrounding those with spinlocks. This would be around 1983, and became part of SVr3. I suppose that the “spl()” calls only protected critical sections that were shared between the main thread and interrupt sequences, so that a manual review was necessary to consider each kernel data structure for parallel access issues in the case of 2 CPU’s.
> 
> Any other notable work in this area prior to 1985?

Sequent Balance 8000 from 1984 had up to 12 National NS32000 processors
and ran the 4.2BSD derived DYNIX.

Bob Beck, Bob Kasten
VLSI Assist in Building a Multiprocessor UNIX System
USENIX 1985 Summer Conference Proceedings
https://archive.org/details/1985-proceedings-summer-portland/page/254/mode/2up

National had their own 4.1BSD derived GENIX.  I can't find any
references to it running on multiprocessor machines.

Gould PowerNode 9080, a dual processor machine was announced in 1984 and
ran a 4.2BSD derived UTX/32.
https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1659257

Pyramid Technology, 90Mx dual processor early 1985, 98x late 1985
https://archive.org/details/sim_systems-software_1985-02_4_2/page/n37/mode/2up
Systems & Software  1985-02: Vol 4 Iss 2
"The new 90Mx, the first dual-processor machine from Pyramid, can
support up to 256 users.  It has a maximum of 32 megabytes of main
memory, and comes in one single-cabinet and three dual-cabinet
configurations.  The 90x, first shipped in October 1983, is limited
to 128 users and 16 megabyte of main memory as a single processor
machine.  Like the 90x, the 90Mx uses the reduced instruction set
computer architecture (RISC)."
"OSx is Pyramid's dual-port, multi-processor implementation of
Unix System V from AT&T and 4.2BSD from the University of California,
Berkeley."

https://archive.org/details/Unix_Review_1985_Aug.pdf/page/n9/mode/2up
Unix Review Magazine Aug 1985
"One of the more impressive machines making its debut at the National
Computer Conference in Chicago July 16 was Pyramid Technology Corp’s
98x, a super minicomputer built with the idea of equal opportunity for
equal microprocessors. Pyramid calls the 98x an "isoprocessor" system;
there are two 32-bit RISC (reduced instruction set computer) processors
working as equal partners."
"The idea behind isoprocessing comes from Purdue’s dual processor
implementation, Krahling said. CPU balance is achieved through the use
of a proprietary semaphore system that protects critical sequences of
code and controls simultaneous access to kernel data structures."
"90Mx has a master-slave multiprocessor environment."

[TUHS] First supercomputer UNIX: The Denelcor HEP (was Early multiprocessor Unix)

[Ron Natalie]

In 1982, I returned to BRL (having spent a year working for Martin 
Marietta on  project involving a dual process RSX-11M system.    I did 
spend some time setting up the PWB UNIX tools with the QA guys while 
there).

BRL had commissioned the Denver Electronics Corporation (i.e., Denelcor) 
to build a MIMD system called the HEP, ostensibly to do fluid dynamics 
problems.   It was looking like the manufacturer wasn’t going to have a 
useful OS for it so Mike Muss did his usual thing and suggested he could 
put UNIX on it (he had done this twice previously with orphaned 
machines:  some 11/34 graphics stations that were supposed to be 
connected to the CDC7600 and converting the University of Illinois 
Arpanet Terminal Server (ANTS) to a host that could support long 
leaders.

I was part of Mike’s team.   We split up various aspects of the project. 
   Mike ported PCC.   I ported ld, and F77 (as we figured the 
“scientists” would probably want that).    Mike did the core of the 
kernel.  I handled all the I/O system because I was the “device driver” 
guy at JHU and continued on with this at BRL.     Our initial work was 
done by traveling out to Denelcor’s facility where our machine was 
assembled on their floor.   They had started their operating system work 
(not UNIX), so we took the machine after hours.   Amusingly, at BRL in 
the room the HEP was going in, the cabinet layout was taped out on the 
floor around a central pillar.   The tape marked with the component that 
went there.   Out in the Denver machine room, the equipment was there 
but there was a square taped out that said “BRL post” so they knew not 
to put/route anything there.

The software being ported was 4BSD.    I believe we started with the 
George Gobels mods of the dual VAX (BRL already had built one of these). 
   In working on that I found there was a rather serious portability 
problem.    The kernel did what I refer to as “conversion by union” 
where they stuck a pointer of one type into one element of the union and 
retrieved it by a different pointer type union element.   Well, such is 
all well and good on the VAX, but the HEP encoded the partial word size 
into the low order bits of the pointer.   This meant that you ended up 
with pointers that would access the wrong size operand.    I spent a few 
days chasing down all these things and fixing them.

The HEP had an 11/34 as a control processor that allowed you to 
configure the switch system that interconnected the memory in the 
processors.    It did this via a special feature called (aptly) “The Low 
Speed Bus” (more on that later).   But once running, everything was self 
contained on the HEP hardware itself.    Other amusing things about the 
HEP is it had a lot of registers.   It also had this stuff called “table 
memory” which essentially were read-only registers.  You could but a 
variety of constants there (we had all the integers from 0-255 and then 
powers of two after that).    The rest of the memory had an extra bit 
per 64-bit word called the “full empty” bit.   While the thing was 
capable of running the equivalent of 32 UNIX processes simultaneously, 
it also had the ability within each of those to hardware schedule 
threads.  Many instructions had features that used the extra bit like 
“WAIT FULL, READ, SET EMPTY” or “WRITE, SET FULL”.

The whole thing was built out of Motorola 10800 ECL.   All hand 
assembled.   Quite impressive.

After we got the system up, and Mike tried to port his ray tracing 
software to it, we found the I/O system was beastly slow.  The I/O 
system was a cute device.  It had a bunch traditional memory (no 
full/empty bits) connected to the main memory via the switch but also to 
32 individual UNIBUSes.   The only problem was that in order to whack 
the registers on the UNIBUS you had to do it through the “Low Speed 
Bus.”    This was the performance bottleneck.    The original designer 
of this thing, Burton Smith and I sat down at the Golden Corral 
Steakhouse in Aberdeen and worked on a new plan.   The key was to allow 
the kernel tasks to talk directly to the UNIBUS registers via the 
regular memory switch.    Fortunately, we had an extra switch node in 
spare parts.    We did however need software and another PDP-11 to 
control the thing.   Fortunately, I had spares from my building of the 
early internet router: BRL-GATEWAY.   I also used the little OS on it 
(LOS) to write the control software.   In a couple of days, we had 
rebuilt the I/O system out of essentially spare parts and it flew.

Amusingly, this was the first of two UNIX ports I worked on that didn’t 
use the standard ISR thing that most of the kernels those days did.    
After the device driver on the HEP had started the IO up, that thread 
just ended.    When the UNIBUS interrupt came in, a new thread was 
created to service it.    I later did a similar strategy with the 
message passing coprocessor on the Multibus II.

This was a fun waste of about a year.    By the time we got this ready 
for prime time, the Army had decided they didn’t have any supercomputers 
(other than HEP) and immediately used defense priority to snag the next 
Cray X/MP off the assembly line (which had been slated for Apple).    
Mike got one run of his raytracer to make a movie:  The artillery 
shell’s view of collision with a tank.   The HEP could generate the 
frames about 60:1 (took a minute to make one second of movie time) 
faster than anything else we had in the day.    Of course, it pales 
compared to your modern video games.   After that, the HEP was 
dismantled (Denelcor had gone out of business) to make room for the 
Cray.   I recently just found pictures of us all sitting on the “seats” 
of the Cray and one of me peering out from the core of the machine.

The Army went on for plans for multiple Cray 2 purchases.   After a lot 
of amusing “systems engineering” work that originally slated for all of 
them to go in Oak Ridge Tennessee, and then all of them to go at BRL, 
they decided to spread them around the country (what I told them they 
should do in the first place).    My last months at BRL, I signed my 
name to the $25 million dollar Cray 2 procurement, but it got delivered 
after I left (I visited it a few years later).

Somewhere I still have the name plates for the Denelcor HEP H1000.   
They, in fact, were never actually installed on the machine,

[TUHS] Re: First supercomputer UNIX: The Denelcor HEP (was Early multiprocessor Unix)

[Jon Steinhart]

Ron Natalie writes:
>
> BRL had commissioned the Denver Electronics Corporation (i.e., Denelcor) 
> to build a MIMD system called the HEP, ostensibly to do fluid dynamics 

I remember the presentation on this at Usenix.  My thought at the time was
that the HEP was a lot like what I saw when people started selling their
expensive California homes and moving to Oregon to spend that money on
mini-mansions.  Well, in California I could only afford two columns, one
dormer, and a one-car garage but now I can have 8 columns, 6 dormers, a
10 car garage, and so on.  I remember thinking at the time that the HEP
seemed like every piece of available hardware at the time glommed together.
I'm sure that more thought went in to it than that, but that was my
impression at the time.

Jon

[TUHS] Re: First supercomputer UNIX: The Denelcor HEP (was Early multiprocessor Unix)

[steve jenkin]

Bitsavers has some files on the HEP, if anyone is interested.

The research papers are a collection of undated, probably published pieces.

<http://www.bitsavers.org/pdf/denelcor/>

> On 30 Nov 2022, at 02:54, Ron Natalie <ron@ronnatalie.com> wrote:
> 
> BRL had commissioned the Denver Electronics Corporation (i.e., Denelcor) to build a MIMD system called the HEP, ostensibly to do fluid dynamics problems.   It was looking like the manufacturer wasn’t going to have a useful OS for it so Mike Muss did his usual thing and suggested he could put UNIX on it (he had done this twice previously with orphaned machines:  some 11/34 graphics stations that were supposed to be connected to the CDC7600 and converting the University of Illinois Arpanet Terminal Server (ANTS) to a host that could support long leaders.

--
Steve Jenkin, IT Systems and Design 
0412 786 915 (+61 412 786 915)
PO Box 38, Kippax ACT 2615, AUSTRALIA

mailto:sjenkin@canb.auug.org.au http://members.tip.net.au/~sjenkin

[TUHS] Re: Early multiprocessor Unix

[scj]

When I left Bell Labs in 1986, I joined Ardent Computer in California.  
We built a multiprocessor Unix system with up to four processors based 
on ECL technology (faster than the computer chips of the time).  The CPU 
had a standard set of registers, and there were four vector registers 
that would hold 1000 floating-point numbers and vector instructions to 
do arithmetic.
So that meant that we had compiler work to do.  Luckily, Randy Allen had 
just graduated and signed on to do the parallelism.  I took on the job 
of doing the assembler, loader, parallelizing C and FORTRAN compilers, 
and I did the lower-level stuff: assembler, loader,
designed the a.out format, and even wrote a bug tracking system.  
Randy's compiler was excellent, but there were other problems.  The Sun 
workstations had some quirks: from time to time they would page in a 
page of all zeros due to a timing problem.  Unhappily, the zero was the 
halt operation!  We addressed that by adding code to the Kernel the 
verify that no code page was all 0's before executing.   AT&T and Sun 
and MIPS and all the hardware makers have problems like this with early 
chips.  One thing I had told the team from the beginning was that we 
were going to have to patch hardware problems in the early versions.

The most serious early hardware bug in our machine was that when the 
MIPS chip had a page fault, the CPU started executing the new page 
before it was all present.  It only missed the first two or three 
instructions.  We settled on a strategy to generate the a.out file so 
that the first 4 instructions were all No-Ops.  This solved the MIPS 
problem.

Now we faced the problem of how do we take a standard a.out format and 
redo it so that the first four instructions in each code page are NOPs.  
We built an "editor" for a.out files that would read the file in, 
respond to a series of requests, relocate the instructions correctly, 
and then branch to the line of code that it had been about to execute.  
One good thing about this was that when the chip got fixed we would not 
have to change any code -- it would just work.

And then we got creative.  We could use the "editor" to find the basic 
blocks in the code, introduce counting instructions at the head of each 
block, and produce a profiler by recompiling.  We probably found about 
20 things we could do with this mechanism, including optimization after 
loading, timing the code without having to recompile everything, 
collecting parallelism statistics, etc.


---


On 2022-11-28 05:24, Paul Ruizendaal wrote:
> The discussion about the 3B2 triggered another question in my head:
> what were the earliest multi-processor versions of Unix and how did
> they relate?
> 
> My current understanding is that the earliest one is a dual-CPU VAX
> system with a modified 4BSD done at Purdue. This would have been late
> 1981, early 1982. I think one CPU was acting as master and had
> exclusive kernel access, the other CPU would only run user mode code.
> 
> Then I understand that Keith Kelleman spent a lot of effort to make
> Unix run on the 3B2 in a SMP setup, essentially going through the
> source and finding all critical sections and surrounding those with
> spinlocks. This would be around 1983, and became part of SVr3. I
> suppose that the “spl()” calls only protected critical sections that
> were shared between the main thread and interrupt sequences, so that a
> manual review was necessary to consider each kernel data structure for
> parallel access issues in the case of 2 CPU’s.
> 
> Any other notable work in this area prior to 1985?
> 
> How was the SMP implementation in SVr3 judged back in its day?
> 
> Paul

[TUHS] Re: Early multiprocessor Unix

[Larry McVoy]

On Sat, Aug 05, 2023 at 04:00:55PM -0700, scj@yaccman.com wrote:
> The Sun workstations
> had some quirks: from time to time they would page in a page of all zeros
> due to a timing problem.  

Was this over NFS?  Because that was a thing.  Paging in from disc I've
never heard of this.

BTW, scj, loving your walk through history.  I'd love to read drafts of
your management book.  My entire career I waited to meet a person that 
got as much joy out of managing as I got out of engineering.  

Still waiting.

[TUHS] Re: Early multiprocessor Unix

[Paul Ruizendaal]

Thank you for sharing, very interesting context info!

It would seem to me that there was only limited work on multi-processor Unix prior to 1985, with the work by Bach/Buroff/Kelleman around 1983 being the defining effort.

When I was doing my thesis with Prof. Van de Goor (who had earlier worked at DEC with the PDP-8 and PDP-11 design teams), another student down the corridor was working on multi-processor Unix ca. 1984-1985. There is a short paper about that work here https://dl.acm.org/doi/pdf/10.1145/6592.6598

From today’s perspective the paper’s conclusions seem odd. It describes going through the source code end-to-end as a huge job, but the core SysIII kernel is only some 7,000 sloc, with maybe two dozen shared data structures. On the other hand, with the tooling of the early 1980’s debugging this stuff must have been very hard. In contrast, on my porting projects today it is very easy to generate a kernel trace for millions of instructions in a few seconds. Even billions is do-able. The edit/compile/test cycle for a kernel with some debug test code compiled in is similarly a matter of seconds. A single test must have taken an hour or more back in the day, assuming that one had exclusive access to the machine.

Also its observation that the Unix kernel is “not highly structured” seems unfair. I find the 1980-era Unix kernel rather well structured, with the exception of the memory management code which is indeed spread out over multiple files making it not so easy to fully grasp. Maybe this was what my fellow student was referring to in his MSc thesis. Also note that a Dutch MSc thesis only took 6-12 months.


> On 6 Aug 2023, at 06:00, scj@yaccman.com wrote:
> 
> When I left Bell Labs in 1986, I joined Ardent Computer in California.  We built a multiprocessor Unix system with up to four processors based on ECL technology (faster than the computer chips of the time).  The CPU had a standard set of registers, and there were four vector registers that would hold 1000 floating-point numbers and vector instructions to do arithmetic.
> So that meant that we had compiler work to do.  Luckily, Randy Allen had just graduated and signed on to do the parallelism.  I took on the job of doing the assembler, loader, parallelizing C and FORTRAN compilers, and I did the lower-level stuff: assembler, loader,
> designed the a.out format, and even wrote a bug tracking system.  Randy's compiler was excellent, but there were other problems.  The Sun workstations had some quirks: from time to time they would page in a page of all zeros due to a timing problem.  Unhappily, the zero was the halt operation!  We addressed that by adding code to the Kernel the verify that no code page was all 0's before executing.   AT&T and Sun and MIPS and all the hardware makers have problems like this with early chips.  One thing I had told the team from the beginning was that we were going to have to patch hardware problems in the early versions.
> 
> The most serious early hardware bug in our machine was that when the MIPS chip had a page fault, the CPU started executing the new page before it was all present.  It only missed the first two or three instructions.  We settled on a strategy to generate the a.out file so that the first 4 instructions were all No-Ops.  This solved the MIPS problem.
> 
> Now we faced the problem of how do we take a standard a.out format and redo it so that the first four instructions in each code page are NOPs.  We built an "editor" for a.out files that would read the file in, respond to a series of requests, relocate the instructions correctly, and then branch to the line of code that it had been about to execute.  One good thing about this was that when the chip got fixed we would not have to change any code -- it would just work.
> 
> And then we got creative.  We could use the "editor" to find the basic blocks in the code, introduce counting instructions at the head of each block, and produce a profiler by recompiling.  We probably found about 20 things we could do with this mechanism, including optimization after loading, timing the code without having to recompile everything, collecting parallelism statistics, etc.
> 
> 
> ---
> 
> 
> On 2022-11-28 05:24, Paul Ruizendaal wrote:
>> The discussion about the 3B2 triggered another question in my head:
>> what were the earliest multi-processor versions of Unix and how did
>> they relate?
>> My current understanding is that the earliest one is a dual-CPU VAX
>> system with a modified 4BSD done at Purdue. This would have been late
>> 1981, early 1982. I think one CPU was acting as master and had
>> exclusive kernel access, the other CPU would only run user mode code.
>> Then I understand that Keith Kelleman spent a lot of effort to make
>> Unix run on the 3B2 in a SMP setup, essentially going through the
>> source and finding all critical sections and surrounding those with
>> spinlocks. This would be around 1983, and became part of SVr3. I
>> suppose that the “spl()” calls only protected critical sections that
>> were shared between the main thread and interrupt sequences, so that a
>> manual review was necessary to consider each kernel data structure for
>> parallel access issues in the case of 2 CPU’s.
>> Any other notable work in this area prior to 1985?
>> How was the SMP implementation in SVr3 judged back in its day?
>> Paul

[TUHS] Re: Early multiprocessor Unix

[Ronald Natalie]

The first foray into multiprocessor UNIX for us was to build one of the 
Purdue University dual vaxes (where they took the SBI terminator out, 
built some special cables to flipped around, and to stick a second CPU 
in that location.    Not too much later we got a multiprocessor Gould 
SEL machine (also with Purdue’s hack to BSD as the OS).

BRL had contracted to buy a Denelcor HEP, which was a MIMD machine 
capable of running 32 or so parallel tasks.    Each one could be divided 
into multiple processes (what we would call a thread the days).   The 
regular memory had a semaphore per word (called a full-empty bit) that 
allowed you to create a bunch of threads and let the hardware itself 
schedule them.    There were four Process Execution Modules (each with 8 
processors) that were interconnected by a fast memory switch, alll 10800 
ECL.

The thing was booted up from a PDP-11/34 front end through an interface 
aptly named the “low speed bus”.    Mike Muuss suggested we could put 
UNIX on the thing and nobody could come up with a reason why not, so we 
ported the same 4 BSD kernel that the dual vaxes were using.   Oddly, 
there were some bad things in the BSD kernel that needed to be fixed 
(notably “conversion by union” that wouldn’t work on this architecture). 
     After the initial boot up, we found that the thing couldn’t run 
I/O’s very quickly as they I/Os were routed through the “low speed bus.” 
     The hardware designer (Burton Smith) and me literally designed a new 
I/O interface on napkins at the local steakhouse, the Golden Corral, and 
built the thing out of spare parts.     I donated another PDP-11/34 to 
the task.

The I/O system was a fun system, the thing had 32 Unibuses connected to 
a memory cache for the main processor.    You could hit the CSRs on the 
Unibuses virtually through mapped memory addresses.    Interrupts 
weren’t the traditional sense but rather a new kernel task was spawned 
to handle it.

-Ron

[TUHS] Re: Early multiprocessor Unix

[Ralph Corderoy]

Hi Steve,

> We built an "editor" for a.out files that would read the file in,
> respond to a series of requests, relocate the instructions correctly,
> and then branch to the line of code that it had been about to execute.  

What level of granuality were these requests?  Could you give a rough
example or two.  Was it sed like, with labels and testing branches?  Did
the requests operate on matched instructions instead of lines?

-- 
Cheers, Ralph.

[TUHS] Re: Early multiprocessor Unix

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 521 bytes --]

On Mon, Nov 28, 2022 at 7:07 AM Clem Cole <clemc@ccc.com> wrote:

> As far as I know, the first non-commercial work was done at the Naval Post
> Grad school with V6.  I have never seen the code for it, only a paper, so I
> don't know too much about it to comment.
>

The data of the paper suggests a V5 base since the paper is 1 month after
the V6 release. I couple of us tried to track down the author and/or
advisors and found one retired who said that code is long gone and he
couldn't help me.

Warner

[-- Attachment #2: Type: text/html, Size: 957 bytes --]

[TUHS] Re: Early multiprocessor Unix

[Warner Losh]

[-- Attachment #1: Type: text/plain, Size: 951 bytes --]

On Mon, Nov 28, 2022 at 7:15 AM Clem Cole <clemc@ccc.com> wrote:

> Paul, the other thing I should point out -- ghg's work was
> widely distributed amount the BSD licenses. I somewhat wonder why the Naval
> Post Grad school's work was not.   My guess is that USENIX was still in its
> formative stages when the latter did their work, whereas, by the time of
> George's hack, BSD/Vaxen was being used for teaching as University
> timesharing systems so his 'upgrade' was a cheap solution.
> ᐧ
>

Also the Naval Post Grad work was on a fairly specialized MP pdp-11/50
system that wasn't super easy to build... plus the paper was declassified,
but it's not clear that the code ever was, or even submitted for
declassification. It was super early still in the unix sharing culture
evolution and wide-spread distribution didn't catch on. Plus, it was for a
funky odd custom thing, which limited people wanting to ask for it.

Warner

[-- Attachment #2: Type: text/html, Size: 1699 bytes --]