From: dinda@cae.wisc.edu (Dinda Peter)
Newsgroups: comp.arch
Subject: Summary: One Instruction Computers
Keywords: One Instruction
Date: 10 Oct 92 15:47:11 GMT
Organization: U of Wisconsin-Madison College of Engineering

This is an <attempted> summary of email and some news responses to my query:

> Prevoiusly someone had posted am message regarding one instruction
> computers - I believe a 3 operand conditional subtract instruction.
> I believe there was also a pointer to a paper that had been written
> on the subject.  Please email.


From: robbins@ringer.cs.utsa.edu (Steven Robbins): {
 One reference is "The ultimate RISC" by D.W. Jones in Computer Architecture
 News, Vol 16, No. 3, June 1988.
}


From: swm11@cl.cam.ac.uk (Simon Moore): {
 % in year order:

@conference{Lipovski76,
author="G J Lipovski",
title="Architecture of a Simple, Effective Control Processor",
booktitle="Second Symposium on Micro Architecture",
organisation="EUROMICRO",
pages="187-194",
year=1976}

@article{Azaria83,
author="H Azaria and D Tabak",
title="Design Consideration of a Single Instruction Microcomputer - A
Case Study",
journal="Microprocessing and Microprogramming",
volume=11,
pages="187-194",
year=1983}

@article{Jones88a,
author="D W Jones",
title="The Ultimate RISC",
journal="Computer Architecture News",
pages="48-55",
volume=16,
number=3,
year=1988}

@article{Jones88b,
author="D W Jones",
title="The Minimal CISC",
journal="Computer Architecture News",
volume=16,
number=3,
year=1988}

@article{Griffin88,
author="G W Griffin",
title="The Ultimate Ultimate RISC",
journal="Computer Architecture News",
volume=16,
number=3,
pages="26-32",
year=1988}

@conference{Moore91,
author="S W Moore and G Morgan",
title="The resursive {MOVE} machine: r-move",
booktitle="RISC architectures and applications",
organisation="IEE colloquium 1991/163",
year="1991"}

}

From: mfx@cs.tu-berlin.de (Markus Freericks): {

There is another way to build a one-instruction computer: Let the only
instruction be "move" and memory-map the ALUs. This is great if you
have ALUs that realize multi-cycle operations (e.g. trig FP, table
lookup). Also, code generation is somewhat easy :-)

There are some articles by Petr Kroha describing code generation for
such machines. I cannot find references at the moment, but the
forthcoming LNCS about code generation generators (collection of
papers presented at the Dagstuhl Workshop '91) should contain one.

}


From: mac@coos.dartmouth.edu (Milton A. Colvin): {

New England Digital Corp. sold the first digital music synthesizers in
the late 70s and was until recently still building computers for
digital audio processing.

The first NED processors were based on the Able minicomputer, notable
for it single instruction - MOVE. MOVE encodes an 8-bit source and an
8-bit destination.

As far as I know, this was the only commercial one-instruction
machine.  For its time it was quite fast. A number survive in
Synclaviers and as network routers at Dartmouth.


This summer NED ceased operation.
A summary of the Able instruction operands follows:
---

Machine Instruction Formats, Assembler Symbols, and Octal Codes

             SOURCES (low byte)

Instruction
Format       Use                               Assembler Symbol    Octal  Code
-----------  -------------------------------   ----------------    ---------------
Oxxxxxxx    Devices                             D0 -    D177        "0" - "177"
   
00000010    Priority Register                   D2                  "2"   (not model B)
00001000    Last Program Counter                D10                 "10"  (not model B)
   
losddddd    Immediate                           IM(expression)      "277" - "237" (-32=<expression=<31)
   
   
11OOrrrr    Register                            R0 - R17            "300" - "317"
110irrrr    Register then Increment             R0i - R17i          "320" - "337"
   
lllOrrrr    Memory Source                       MR0   MR17          "340" - "357"
llllrrrr    Memory Source then Increment        MR0i  MR17i         "360" - "377"
 
            DESTINATIONS (high byte)
          
0xxxxxxx    Devicess                            D0 -  D177          "@0" - "177"
0000010     Encode Priority                     D2                  "2"   (not model B)
0001000     Repeat                              D10                 "10"  (not model B)
 
100aaarr    Arithmetic                                              "200" - "237"
000              Load                           LOA0 - LOA3         "200" - "203"
001              And                   (&)      AND0 - AND3         "204" - "207"
010              Addition              (+)      ADD0 - ADD3         "210" - "213"
011              Subtract              (-)      SUB0 - SUB3         "214" - "217"
100              Exclusive Or          (XOR)    XOR0 - XOR3         "220" - "223"
101              Rotate Left           (ROL)    RTL0 - RTL3         "224" - "227"
110              OR                    (\)      OR0  - OR3          "230" - "233"
111              Load Compliment       (NOT)    LCMO - LCM3         "234" - "237"
 
1010ttrr    Test                                                    "240"  - "257-1
00               Load                           TLOA0 - TLOA3       "240" - "243"
01               And                            TAND0 - TAND3       "244" - "247"
10               Addition                       TADD0 - TADD3       "250" - "253"
11               Subtract                       TSUB0 - TSUB3       "254" - "257"
 
1011OOrr    Byte Swap with Or                   BSOR0 - BSOR3       "260" - "263"
10110irr    Shift Right with Add                SHRA0 - SHRA3       "264" - "267"
1011IOrr    Add with Carry                                          "270" - "273"
1011llrr    Subtract with Borrow                                    "274" - "277"
11OOrrrr    Register Destination                R0 - R17            "300" - "317"
 
1101occc    Conditional Transfer Absolute \                         "320" - "327"
11011ccc    Conditional Transfer Relative                           "330" - "337"
     000    Always                              ATRA / RTRA         "320" / "330"
     100    Never                               ATNV / RTNV         "324" / "334"
     001    Zero                                ATZE / RTZE  "321" / "331"
     101    Non-zero                            ATNZ / RTNZ  "325" / "335"
     010    Carry                               ATRC / RTRC  "322" / "332"
     110    Non-carry                           ATNC / RTNC  "326" / "336"
     011    Minus                               ATMI / RTMI  "323" / "333"
     lit    Non-minus                           ATPL / RTPL  "327" / "337"

 
111Orrrr   Memory Destination                   MR0 - MR17   "340" - "357"
1111rrrr   Memory Destination then Inc          MR0i-MR17i(ex.MR12)"360" - "377"  (ex."372")
1111101O   Memory Destination then Dec          MR12D        "372"

}

From: ivie@cc.usu.edu (CP/M lives!): {

In article <1992Oct2.192543.12309@dartvax.dartmouth.edu>, mac@coos.dartmouth.edu (Milton A. Colvin) writes:
> 
> [The NED processor, see above ]
>

DEUCE, a British machine ca. 1955, was also a MOVE-only machine. However,
it's instructions had three address: Source, Destination, and Next Instruction.

It was built by the English Electric Company, and I don't know who else
besides the Royal Aircraft Establishment bought one (the book that I got
the info from was written by someone from R.A.E.).

}



From: horst@techfak.uni-bielefeld.de: {

Petr Kroha
``An Extension of the single Instruction Machine Idea''
LITH-IDA-R-89-25, Research Report, PELAB
June 1989
Department of Computer Science
Link\"oping University
Sweden

May be there are more pointers in
  - LNCS 371 [Kroha:1988] or
  - LNCS 477 [Kroha:Fritzson:1990]

Last year his address was:

	Professor Petr Kroha
	University of Dortmund
	Fachbereich Informatik
	Postfach 500500
	W4600 Dortmund 50
	Germany

Have luck

[Thanks!]

Horst Hogenkamp

}

From: crowl@research.CS.ORST.EDU (Lawrence Crowl): {

There are two two-instruction computers that are also interesting.  They are

    increment
    decrement and branch on zero

and

    increment
    decrement and branch on non-zero

It turns out that one of these is much better than the other.  Which is better
is an exercise for the reader.  :-)


[My guess is that the second works much better for a loops]
}

From: Martin Leiser  <leiser@karlsruhe.gmd.de>: {


The instruction is:

  substract and jump if zero.

with 3 operand.

it appeared in Informatik Spektrum in an older issue (befoer 85?
I was unable to find it)

If my memory serves right the Author of the note was

Prof.Dr. J.Nievergelt, Informatik, ETH, CH-8092 Zuerich

}
   

From: Jim Frenzel <jff@k2.ee.uidaho.edu>: {

Don't know if this is the article to which you are refering:

Christopher Carroll, "A One Instruction Computer: Architecture, 
Implementation, and Experiments", Proceedings of the
1992 ASEE Conference, pp. 1683-1686.

It was primarily for instructional purposes, I believe.

}

From: Steve Loughran <slo@hplb.hpl.hp.com>: {

I did a 32 bit CPU based on the MOVE mem,mem instruction a few years
ago while still a student. Do you want a large latex report about that?

	-steve

[Thanks for the Report, Steve]

}

From: ttumlin@hubcap.clemson.edu (tim j ttumlin): {

I think it was in Comp Arch Review by a guy from Illinois. It was called SMAL I
think. I'm not at the office right now so I can't look.

If someone else doesn't tell, email me and I'll look for it.

Later,
TJ Tumlin ttumlin@cs.clemson.edu

}


From: Trevor Hopkins <trevor@computer-science.manchester.ac.uk>: {

Peter,

I understand you've been expressing an interest in One Instruction
Computers OICs).  The instruction is `Reverse Subtract, Skip if
Borrow' (RSSB), and the operand is given by a single memory address (a
one-address format).

Roughly, the operation says: `take the value from the memory at the address
given, subtract it from the accumulator, putting the result both in the
accumulator *and* back in the addressed location, and skip the next
instruction if a borrow took place.'

The code, of course, consists of a sequence of addresses, upon which to
perform the RSSB instruction.

This topic came up on USENET several years ago, and I was interested enough
to suggest a final year (undergraduate) project to actually construct such
a thing.  The student was called John Bown.

John started with the idea of a RSSB instruction, and implemented a
one-address form (read-modify-write) of OIC.  He used 16-bit words,
and his implementation used standard TTL parts, with a couple of small
PALs for timing generation.  His timing was quite complex, as he
implemented part of the memory using register chips (fast) and the
rest using (slow) static RAMs (32K 16-bit words).  All I/O was via a
couple of UARTs, which allowed a connection to a VDU (to drive the
`front-panel' monitor) and a host computer (microVAX).  The uVAX ran a
cross-assembler, with extensive macro facilities, and an `instruction'
simulator.  I've got the board which John built in front of me; it has
about 45 chips on it (all SSI/MSI, except for memory), and uses
`wire-wrap' construction.

The student also constructed a (macro) assembler, which took input in a
vaguely PDP11-style (16-bit instructions only) and generated a sequence of
RSSB instructions.  This compination managed to execute `PDP11' type
instructions at about 0.5 MIPS -- not too bad for a TTL single-board
computer.

A subsequent student started producing a Pascal compiler for the OIC, but
with less success (he was a less able student :-).

I could let you have a copy of John's report, if it would help (or at
least be interesting ;-).

Trevor.

}


From: dms!albaugh@netcom.com (Mike Albaugh): {

	We just got back "one the air" after massive changes to
our mail/news gateway, so I cought the tail end of this thread.
You two seemd to be the only ones _seeking_ information, rather
than offering it, so I have presumed to reply to you. Some time
ago I posted _my_ "Ultimate RISC", in th course of the previous
incarnation of this thread. I repeat it below, and will send my
"excerpts" of that thread incarnation if you are interested.

				Enjoy,
				Mike

--- repeat of my posting re: "Zero Instruction Computers" ---

	I wanted to point out that a machine with no opcode has not
zero, but one instruction(s). (2**0 = 1)

	As several people have noted, the idea of using addresses to
"cheat" (refer to function units) is well represented in the literature.
A recent article in ACM Computer Architecture News even has the audacity
to call this approach "The Ultimate RISC". I might be persuaded that it
is the "ultimate _useful_ RISC", but machines such as Van der Poel's
(article <3562@hubcap.UUCP>, by mark@hubcap.UUCP (Mark Smotherman) )
are arguably much more RISCy.

	A few years ago (Before I was personally on UseNet), I had a
friend email (Maybe post?) an earlier version of the following, In
which I present my own "ultimate" RISC. Since mine also has one (or two,
but not several) "magic" location, it may not be truly "ultimate". I
feel that it is closer than the various two and three address variations.
I originally intended to actually wire-wrap the first version, and may
yet build the current version, but kids and a house have changed my
priorities. I do have a C simulator, and some useful macros.

	An aside, the GRI-90 mentioned in <20743@apple.Apple.COM> by
baum@apple.com was manufactured by George Risk Industries, so it may
have been ahead of its time in nomenclature too :-)

And now, a re-run:

Random thoughts on the Ultimate Reduced Instruction Set Computer

	One possible implementation is a machine which has the instruction:
Reverse Subtract and skip on Borrow. That is, every instruction has no opcode
but does have an address. The accumulator is subtracted from that address and
the result left both there and in the accumulator. If the subtraction caused
a borrow (i.e. no carry out of the ALU), the subsequent instruction is skipped.
The only handwaving required is for the PC to live in a fixed location
(say 0, ala PDP-5). A very naive control unit which does one instruction per
6 clock cycles can be implemented, a slightly less naive one can do it in
5 (sometimes 4), and shadowing the PC can get it to 3 (sometimes 2).

	Some macros for the machine, to implement more common instructions are:

	macro CLR p1
	p1			; p1,acc <- p1-acc (may skip)
	p1			; p1,acc <- 0 (cannot skip)
	p1			; p1,acc <- 0 (cannot skip)
	ENDM
;	The third instruction is not redundant, since we have no way of knowing
; whether the first will skip.

	macro LOAD p1 p2
	CLR p2			; We need to provide a sacrificial location
	p1			; acc,p1 = p1-0 (cannot skip)
	ENDM

	macro STORE p1 z	; z must be a pre-zeroed location
	z			; acc,z = -acc (will skip unless acc=0)
	z			; acc,z = 0 (a nop in this case)
	CLR p1
	z			; acc = z (-acc from entry, cannot skip)
	p1			; acc,p1 = entry acc (will skip unless 0)
	z			; another NOP to fill the skip safely.
	ENDM

;	The necessity of providing a sacrificial location for LOAD and
; a guaranteed zero (which is destroyed) for STORE imply that the
; "one-address" machine is an inappropriate paradigm. The "two-address"
; machine yields a substantial improvement:

	macro MOV p1 p2 z
	CLR p2
	z
	z			; Also clears z, but shorter 'cuz we can't skip
	p1			; acc,p1 = p1
	z			; acc,z = -p1		(will skip unless 0)
	z			; in case p1 was 0
	p2			; acc,p2 = p1		(will skip unless 0)
	z			; in case p1 was 0
	ENDM

	macro SUB p1 p2 p3	; (p3=p1-p2), (p2=p2-p1)
	CLR p3
	p1			; acc,p1 = p1 (cannot skip)
	p2			; acc,p2 = p2-p1 (may skip)
	p3			; acc,p3 = p1-p2 (will skip unless p1=p2)
	p3			; acc,p3 = p1-p2 (cannot skip)
	ENDM

The analysis of that one is a bit tricky. If p2 is less than p1, the p2
instruction skips to the second p3, which cannot skip again, since 
(p2<p1) IFF (p1>p2). If p2 is greater than p1, the p2 will not skip, but the
first p3 will, by similar reasoning. If p2=p1, all instructions are executed
and p2 = p3 = 0.

	macro JMP l
	CLR	Z
	lit	next-l		;acc=(next-l)
next	0			;pc (which is in 0) = next-(next-l) = l
	ENDM

Actually, the value of the literal needs to be adjusted for the skip which
will occur if l is at a lower address than next, but I didn't want to clutter
the psuedo-macro with conditionals.

	macro ZAJMP l z		; if acc=0		if acc<>0
	z			; 0 (noskip)		-acc (must skip)
	lit	l-next		; l-next (noskip)	----
	z			; next-l (mustskip)	0 (noskip)
	z			; -----			0 (nop)
next	0			; JMP l			nop
	ENDM

	macro ZJMP t l z	;Jump to l if t=0
	LOAD	t z
	ZAJMP	l z
	ENDM

    The "lit" function is similar to the # (immediate) operator on such
machines as have an immediate mode. If you don't have such a mode (many
early machines didn't), you typically create a "literal pool", for all
the constants you are going to use. Such constants are shared by all the
instructions that need to refer to that particular bit pattern. Since a
careless use could alter the pattern, this can be a source of endless
"amusement" during debuging. The creation of a literal pool on a macro
assembler that doesn't have such a feature (such as DEC MACRO-11, because it
wouldn't use it in its "native tongue") is left as an exercise to the reader,
for now. I know how _I_ do it, but will leave it as an exercise to the
reader for any particular machine.

	Robert Murdoch (of Intel, Hi Doch :-)) suggested a refinement of 
Lyle Rains (of Atari Games, my boss's boss) idea that byte addressability
of memory would make character operations easier. Doch's idea was to go all
the way and make the memory bit-addressable. A whole word is still
referenced and modified in each cycle, but that word can start on any bit
boundary. Since the extra 4 bits would take a real bite out of the address
space of a 16-bit machine, this makes most sense with a 32 bit machine. The
complexities of the hardware get intense (if we want to go very fast), but
right shifts and field extraction become trivial.

	Interrupts can be handled by forcing references to 0 to go to "1"
instead. The quotes around "1" are because a bit addressable machine would
have its second word at address 16 (or 32). Anyway, just oring the interrupt
control flag with the appropriate address bit on a reference to 0 will do the
trick. The following software is needed to save and restore the "processor
status". accs and accs2 are two pre-zeroed locations, to recieve the contents
of the acc, whether or not the instruction before the interrupt caused a skip.
accr and accr2 pre-set by the IRQ routine, and the return is before the entry
so a simple delay on the reset of the IRQ flag accomplishes return
There are three possible input states to re-construct:
			 acc==0, !skip;	acc<>0, !skip;	acc<>0, skip

IRQRTN:	clr	IFRESET	; Flag hardware, action delayed 2 cycles past last ref.
	accr			0	0		-inacc
	accr2			0 	inacc 		0->inacc skip

; These get set up by:
INTEN:	accs		;	0	-inacc s	0
	accs2		;	0	---		-inacc s	
	accr		;	???	???		---
	accr		;	0	--?		???
	accr		;	0	0		--?
	accr		;	0	0		0
	accr2		;	???	???		???
	accr2		;	0	0		0
	accs		;	0	-inacc		0
	accr2		;	0	inacc s		0
	accs2		;	0	---		-innac
	accs		;	0	0		inacc s
	accr		;	0	0		---
	accr		;	0	0		-inacc s
	accs		;	0	0		---
	accs		;	0	0		0
	accs2		;	0	0		innac
	accs2		;	0	0		0
; At this point, accs and accs2 are pre-zeroed for next IRQ, accr and accr2
; are set up for return. Do body of IRQ routine...

	jmp	IRQRTN	; Jump up to return point

; for 28 cycles interrupt overhead...
; The clear of accs2 could be merged with the jump to IRQRTN to save two cycles


}


Thanks to all the contributers.  There is certainly a lot to think about 
here.  Hopefully it will be of use to others as well.


Peter A. Dinda
Newsgroups: comp.arch