Rekursiv

Last updated

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

Contents

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. [1]

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. [1]

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. [1] 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. [2]

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. [3] Sometime after that the company was shut down. [lower-alpha 1]

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". [5]

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. [6] There was no default ISA, although Linn supplied one for running programs in the C programming language. [7]

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. [8] 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. [9]

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. [9]

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. [9] [lower-alpha 2]

Because the top two bits of the 40-bit pointer were used for status flags, Objekt could only identify 238 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. [9]

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. [10]

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. [10]

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. [10]

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. [10]

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. [10]

Notes

  1. ↑ According to one person that was working at the company at the time, the last straw was when a Linn truck damaged Harland's Porsche and he stopped coming to the office. [4]
  2. ↑ The 33rd bit is not mentioned in any of the sources and appears to be unused.

Related Research Articles

A control store is the part of a CPU's control unit that stores the CPU's microprogram. It is usually accessed by a microsequencer. A control store implementation whose contents are unalterable is known as a Read Only Memory (ROM) or Read Only Storage (ROS); one whose contents are alterable is known as a Writable Control Store (WCS).

A complex instruction set computer is a computer architecture in which single instructions can execute several low-level operations or are capable of multi-step operations or addressing modes within single instructions. The term was retroactively coined in contrast to reduced instruction set computer (RISC) and has therefore become something of an umbrella term for everything that is not RISC, where the typical differentiating characteristic is that most RISC designs use uniform instruction length for almost all instructions, and employ strictly separate load and store instructions.

<span class="mw-page-title-main">DEC Alpha</span> 64-bit RISC instruction set architecture

Alpha is a 64-bit reduced instruction set computer (RISC) instruction set architecture (ISA) developed by Digital Equipment Corporation (DEC). Alpha was designed to replace 32-bit VAX complex instruction set computers (CISC) and to be a highly competitive RISC processor for Unix workstations and similar markets.

In processor design, microcode serves as an intermediary layer situated between the central processing unit (CPU) hardware and the programmer-visible instruction set architecture of a computer. It consists of a set of hardware-level instructions that implement higher-level machine code instructions or control internal finite-state machine sequencing in many digital processing components. While microcode is utilized in general-purpose CPUs in contemporary desktops, it also functions as a fallback path for scenarios that the faster hardwired control unit is unable to manage.

<span class="mw-page-title-main">Machine code</span> Set of instructions executed by a computer

In computer programming, machine code is computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Although decimal computers were once common, the contemporary marketplace is dominated by binary computers; for those computers, machine code is "the binary representation of a computer program which is actually read and interpreted by the computer. A program in machine code consists of a sequence of machine instructions ."

<span class="mw-page-title-main">PDP-10</span> 36-bit computer by Digital (1966–1983)

Digital Equipment Corporation (DEC)'s PDP-10, later marketed as the DECsystem-10, is a mainframe computer family manufactured beginning in 1966 and discontinued in 1983. 1970s models and beyond were marketed under the DECsystem-10 name, especially as the TOPS-10 operating system became widely used.

<span class="mw-page-title-main">Reduced instruction set computer</span> Processor executing one instruction in minimal clock cycles

In computer science, a reduced instruction set computer (RISC) is a computer architecture designed to simplify the individual instructions given to the computer to accomplish tasks. Compared to the instructions given to a complex instruction set computer (CISC), a RISC computer might require more instructions in order to accomplish a task because the individual instructions are written in simpler code. The goal is to offset the need to process more instructions by increasing the speed of each instruction, in particular by implementing an instruction pipeline, which may be simpler to achieve given simpler instructions.

<span class="mw-page-title-main">VAX</span> Line of computers sold by Digital Equipment Corporation

VAX is a series of computers featuring a 32-bit instruction set architecture (ISA) and virtual memory that was developed and sold by Digital Equipment Corporation (DEC) in the late 20th century. The VAX-11/780, introduced October 25, 1977, was the first of a range of popular and influential computers implementing the VAX ISA. The VAX family was a huge success for DEC, with the last members arriving in the early 1990s. The VAX was succeeded by the DEC Alpha, which included several features from VAX machines to make porting from the VAX easier.

<span class="mw-page-title-main">Zilog Z80</span> 8-bit microprocessor

The Z80 is an 8-bit microprocessor introduced by Zilog as the startup company's first product. The Z80 was conceived by Federico Faggin in late 1974 and developed by him and his 11 employees starting in early 1975. The first working samples were delivered in March 1976, and it was officially introduced on the market in July 1976. With the revenue from the Z80, the company built its own chip factories and grew to over a thousand employees over the following two years.

The NS32000, sometimes known as the 32k, is a series of microprocessors produced by National Semiconductor. The first member of the family came to market in 1982, briefly known as the 16032 before becoming the 32016. It was the first general-purpose microprocessor on the market that used 32-bit data throughout: the Motorola 68000 used 32-bit data but had a 16-bit ALU and thus took twice as long perform many operations. However, the 32016 contained many bugs and often could not be run at its rated speed. These problems, and the presence of the otherwise similar 68000 which had been available since 1980, led to little use in the market.

In computer science, an instruction set architecture (ISA), also called computer architecture, is an abstract model of a computer. A device that executes instructions described by that ISA, such as a central processing unit (CPU), is called an implementation.

<span class="mw-page-title-main">IBM System/38</span> IBM midrange computer (1978–1988)

The System/38 is a discontinued minicomputer and midrange computer manufactured and sold by IBM. The system was announced in 1978. The System/38 has 48-bit addressing, which was unique for the time, and a novel integrated database system. It was oriented toward a multi-user system environment. At the time, the typical system handled from a dozen to several dozen terminals. Although the System/38 failed to displace the systems it was intended to replace, its architecture served as the basis of the much more successful IBM AS/400.

<span class="mw-page-title-main">Intel iAPX 432</span> Discontinued Intel microprocessor architecture

The iAPX 432 is a discontinued computer architecture introduced in 1981. It was Intel's first 32-bit processor design. The main processor of the architecture, the general data processor, is implemented as a set of two separate integrated circuits, due to technical limitations at the time. Although some early 8086, 80186 and 80286-based systems and manuals also used the iAPX prefix for marketing reasons, the iAPX 432 and the 8086 processor lines are completely separate designs with completely different instruction sets.

In computer science, computer engineering and programming language implementations, a stack machine is a computer processor or a virtual machine in which the primary interaction is moving short-lived temporary values to and from a push down stack. In the case of a hardware processor, a hardware stack is used. The use of a stack significantly reduces the required number of processor registers. Stack machines extend push-down automata with additional load/store operations or multiple stacks and hence are Turing-complete.

Addressing modes are an aspect of the instruction set architecture in most central processing unit (CPU) designs. The various addressing modes that are defined in a given instruction set architecture define how the machine language instructions in that architecture identify the operand(s) of each instruction. An addressing mode specifies how to calculate the effective memory address of an operand by using information held in registers and/or constants contained within a machine instruction or elsewhere.

In computer engineering, an orthogonal instruction set is an instruction set architecture where all instruction types can use all addressing modes. It is "orthogonal" in the sense that the instruction type and the addressing mode vary independently. An orthogonal instruction set does not impose a limitation that requires a certain instruction to use a specific register so there is little overlapping of instruction functionality.

Berkeley RISC is one of two seminal research projects into reduced instruction set computer (RISC) based microprocessor design taking place under the Defense Advanced Research Projects Agency VLSI Project. RISC was led by David Patterson at the University of California, Berkeley between 1980 and 1984. The other project took place a short distance away at Stanford University under their MIPS effort starting in 1981 and running until 1984.

<span class="mw-page-title-main">CVAX</span> Microprocessor chipset

The CVAX is a microprocessor chipset developed and fabricated by Digital Equipment Corporation (DEC) that implemented the VAX instruction set architecture (ISA). The chipset consisted of the CVAX 78034 CPU, CFPA floating-point accelerator, CVAX clock chip, and the associated support chips, the CVAX System Support Chip (CSSC), CVAX Memory Controller (CMCTL), and CVAX Q-Bus Interface Chip (CQBIC).

Joel McCormack is an American computer scientist who designed the NCR Corporation version of the p-code machine, which is a kind of stack machine popular in the 1970s as the preferred way to implement new computing architectures and languages such as Pascal and BCPL. The NCR design shares no common architecture with the Pascal MicroEngine designed by Western Digital but both were meant to execute the UCSD p-System.[1,2]

<span class="mw-page-title-main">DEC V-11</span>

The V-11, code-named "Scorpio", is a miniprocessor chip set implementation of the VAX instruction set architecture (ISA) developed and fabricated by Digital Equipment Corporation (DEC).

References

Citations

  1. 1 2 3 Pountain 1988, p. 341.
  2. ↑ Rose, Seb (19 April 2011). "Rekursiv". slideshare.net. Slideshare. Retrieved 27 February 2017.
  3. ↑ The Linn Rekursiv Story -REPOST
  4. ↑ Lothian 1993.
  5. ↑ Pountain 1988, p. 348.
  6. ↑ Pountain 1988, p. 342.
  7. ↑ Pountain 1988, pp. 348–349.
  8. ↑ Pountain 1988, p. 346.
  9. 1 2 3 4 Pountain 1988, p. 347.
  10. 1 2 3 4 5 Pountain 1988, p. 349.

Bibliography

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.