Rekursiv

Rekursiv was a computer processor designed by David M. Harland in the mid-1980s at a division of hi-fi manufacturer Linn Products. It was one of the few computer architectures intended to implement object-oriented concepts directly in hardware, a form of high-level language computer architecture. The Rekursiv operated directly on objects rather than bits, nibbles, bytes and words. Virtual memory was used as a persistent object store and unusually, the processor instruction set supported recursion (hence the name).

By the time the project had delivered its first implementation, new processors like the Sun SPARC and Intel 486 had surpassed its performance, and development was abandoned in 1988.

History

The Rekursiv project started as an effort to improve the assembly line controls in Linn's factories in Glasgow, Scotland. Their lines were automated using a suite of VAX-11 systems, but these were slow and very difficult to program with the flexibility that Linn's founder, Ivor Tiefenbrun, desired. By the early 1980s, Tiefenbrun had become convinced that object-oriented programming would offer solutions to these problems.

In 1981, Tiefenbrun hired a number of programmers to write a version of the Smalltalk language for the VAX systems, borrowing some syntax from ALGOL. Known as LINGO, the system worked but ran very slowly on the VAX platform. Tiefenbrun concluded the solution to the performance issue was not to improve the language on the VAX but instead produce an entirely new CPU dedicated specifically to running object programs.

In 1984, Tiefenbrun formed the wholly owned subsidiary Linn Smart Computing under the direction of University of Strathclyde professor David Harland and the Rekursiv project was born. The first version of the system emerged in 1988. A small number of prototype VMEbus boards, called Hades, comprising these four chips plus 80 MB of RAM were produced. These were intended for installation in a host system such as a Sun-3 workstation. Although the Rekursiv was never fully developed and was not a commercial success, several Hades boards were used in academic research projects in the UK. The last known copy of a Rekursiv computer ended up at the bottom of the Forth and Clyde canal in Glasgow.

According to a post by a researcher at the University of Strathclyde, while the Rekursiv system was being developed, a new version of the LINGO language was written for the Sun SPARC system which emerged at about this time. It ran twice as fast as the Rekursiv hardware, rendering the effort pointless. Sometime after that the company was shut down.

Description

Basic concepts

The underlying concept of the Rekursiv platform was to provide a hardware-assisted persistent object store, constantly and invisibly writing the memory state to disk without intervention from the operating system or the user's program. One reviewer described it as "an object-database engine for creating and managing persistent objects".

To make such a system work with reasonable performance while running complex programs, Rekursiv was designed to allow the programmer to write their own instruction set architecture (ISA) dedicated to the language they were using. The microcode instruction set was stored in static RAM. There was no default ISA, although Linn supplied one for running programs in the C programming language.

Memory handling

The system did not provide the analog of a memory address to the programs running on it, instead, objects were given a 40-bit identifier which the Objekt chip hashed and used as a pointer to physical memory. Objekt also handled the mapping of the object memory to hard disk for permanent storage, implementing a virtual memory system. To handle garbage collection, Objekt divided the provided dynamic RAM (main memory) into two halves, using one for new object creation and leaving the other unused. When a new object would require more memory than was free in the used portion, Objekt paused the system, copied any object with a valid pointer to it to the unused half of memory, and then switched to make the formerly unused half the active portion. In extremely memory-limited cases, Objekt would first attempt to spool some objects to disk, and if that failed to free up enough room, would use both halves of memory.

Objects are composite structures with multiple values within them, which in most systems are implemented as a series of pointers to the memory locations holding the values. In Rekursiv, the addresses are replaced by 40-bit object IDs pointing to a section of memory allocated by Objekt. The most significant bit (MSB) of the 40-bit pointer was set to 1 if the value was an object identifier, or 0 if it was an untyped binary value. The later was used to store large unformatted data, like the data for a digital image, and could only be used within objects.

In the case of a full object, a further simplification was available to store short fields as values within the pointer itself. This was indicated by setting the second MSB to 0 as well. In this case, the following five bits indicated a type, defined by the program's ISA, which might be "integer" or "string fragment". The actual value of this "compact object" was placed in the lower 32-bits of the pointer. This allowed such simple values to be immediately presented to the processor without the need to follow a pointer to the physical location, which saved memory and improved performance.

Because the top two bits of the 40-bit pointer were used for status flags, Objekt could only identify 2³⁸ objects in total. Since the objects were constantly being garbage collected, many of these values might point to non-existent objects, meaning the system could run out of identifiers in practical use. To address this, the entire system image was periodically written to disk, during which time all of the pointers were re-numbered to be consecutive.

Microcode

The processor's instruction set was stored in a dedicated area of static RAM known as the "control store". It was accessed via a dedicated 16-bit bus, organized as 16,384 words of 128-bits each. A separate "control store map" section of SRAM holds a numbered table of entry points into the microcoded routines, mapping a 10-bit opcode onto one of 2,048 entities. In a conventional processor, the map would normally be implemented in hardwired logic in the opcode decoder.

Opcodes could be parts of objects and stored in the same way that any other data would be using Objekt. For performance reasons, a separate memory bank known as NAM (and NAMARG) reserved 524,288 40-bit words storing 10-bit opcodes and 30-bit arguments. NAM connected directly to the processor via its own bus, making it act more like a cache in modern architectures.

In practice, the developer of a programming language would first outline the assembler language they desired, which would be the underlying syntax of the language with up to 2,048 instructions. Commonly used routines, like those found in stdlib in C, would then be coded using that assembler language and written to the NAM. Simulations suggested that Lisp routines written using this style operated about 20 times faster than a Symbolics Lisp machine. The company also produced similar microcode systems for Smalltalk and Prolog, the later reducing Prolog's complex unification operation to a single opcode.

Physical packaging

The Rekursiv processor consisted of four gate-array chips named Numerik (32-bit ALU), Logik (instruction sequencer), Objekt (object-oriented memory management unit) and Klock (processor clock and support logic). The original versions were clocked at 10 MHz.

Linn intended to sell the Rekursiv chip set to vendors, as well as produce their own workstation using it. Initially, the only product was "HADES", the "Hardware Accelerator for Dynamic Expert Systems", which consisted of a VMEbus card that could be plugged into a Sun-3 or Sun-4 workstation. HADES included the four main chips, 2 MB of 45 nanosecond (22 MHz) SRAM and 5 MB of 100 ns (10 MHz) DRAM. Disk access was handled by a program running on the underlying Sun system, which significantly hampered performance.

References

Bibliography

• Pountain, Dick (November 1988). "Rekursiv: an object-oriented CPU" (PDF). BYTE. 13 (12): 341–349.
• Lothian, James (15 March 1993). "Re: Rekursiv chip (pretty long)". Newsgroup: comp.arch. Usenet: 33000@castle.ed.ac.uk.

Further reading

• The Jim Austin Computer Museum Rekursiv page
• The CPU Shack: Weird and Innovative Chips

• Harland, David M. (August 1988). Rekursiv: Object-Oriented Computer Architecture (Ellis Horwood Series in Computers and Their Applications). Ellis Horwood Ltd. ISBN 0-13-771965-5.
• Baines, Rupert (March 1990). "Taking RISCs". Personal Computer World. 13 (3): 136–140.
• Harland, David M.; Gunn, Hamish I. E.; Pringle, Ian A.; Beloff, Bruno (September 1986). "The Rekursiv: An Architecture for Artificial Intelligence". Proc. AI Europa.
• Harland, David M.; Beloff, Bruno (December 1986). "Microcoding an Object-Oriented Instruction Set". ACM SIGARCH Computer Architecture News. 14 (5). Association for Computing Machinery: 3. doi:10.1145/18981.18982. S2CID 17125054.
• Harland, David M.; Beloff, Bruno (April 1987). "Objekt: A Persistent Object Store with an Integrated Garbage Collector". ACM SIGPLAN Notices. 22 (4). Association for Computing Machinery: 70. doi:10.1145/24714.24723. S2CID 14704178.
• Rose, Seb. "Rekursiv".
• Harland, David M. "Object-Oriented Computer Architecture: - Concepts and Issues - The REKURSIV Object-Oriented Computer Architecture" (PDF).