Forgot your password?
typodupeerror
Programming Hardware

Building a 32-Bit, One-Instruction Computer 269

Posted by timothy
from the some-things-weren't-meant-for-post-its dept.
Hugh Pickens writes "The advantages of RISC are well known — simplifying the CPU core by reducing the complexity of the instruction set allows faster speeds, more registers, and pipelining to provide the appearance of single-cycle execution. Al Williams writes in Dr Dobbs about taking RISC to its logical conclusion by designing a functional computer called One-Der with only a single simple instruction — a 32-bit Transfer Triggered Architecture (TTA) CPU that operates at roughly 10 MIPS. 'When I tell this story in person, people are usually squirming with the inevitable question: What's the one instruction?' writes Williams. 'It turns out there's several ways to construct a single instruction CPU, but the method I had stumbled on does everything via a move instruction (hence the name, "Transfer Triggered Architecture").' The CPU is implemented on a Field Programmable Gate Array (FPGA) device and the prototype works on a 'Spartan 3 Starter Board' with an XS3C1000 device available from Digilent that has the equivalent of about 1,000,000 logic gates, costing between $100 and $200. 'Applications that can benefit from custom instruction in hardware — things like digital signal processing, for example — are ideal for One-Der since you can implement parts of your algorithm in hardware and then easily integrate those parts with the CPU.'"
This discussion has been archived. No new comments can be posted.

Building a 32-Bit, One-Instruction Computer

Comments Filter:
  • by 140Mandak262Jamuna (970587) on Thursday November 19, 2009 @02:16PM (#30161312) Journal
    -------------drum roll

    0x2A

    That is the ultimate instruction.

  • by mpoulton (689851) on Thursday November 19, 2009 @02:18PM (#30161362)
    It seems specious to say that One-Der is optimal for a task because it offers the flexibility of the underlying FPGA hardware. If you have the FPGA hardware present to run the One-Der implementation, then you could just configure a more optimally designed processor out of it for whatever task you are actually performing.
    • Re: (Score:3, Interesting)

      by Bakkster (1529253)

      But most FPGAs utilize a CPU core, which is often hard-wired and has ports to access the programable elements. Assuming the single-instruction MIPS runs faster than the common 'standard' CPUs such as PowerPC, then there would be a benefit. The CPU could be smaller (leaving more space for programmable elements) and more easily expanded upon (run additional functions by address rather than by OPCODE).

      That's a big 'if', but there's merit in exploring it. The biggest barrier I can think of right now is wit

    • by mattdm (1931)
      The sentence from the summary which you're replying to makes more sense in its full context in the article:

      Even so, One-Der is imminently usable as it is. Unlike many other FPGA CPU cores, this one is very simple to customize even if you aren't an expert on its internals. Applications that can benefit from custom instruction in hardware -- things like digital signal processing, for example -- are ideal for One-Der since you can implement parts of your algorithm in hardware and then easily integrate those pa

    • Re: (Score:3, Interesting)

      by SharpFang (651121)

      FPGA is usually the prototype phase.

      Actually, this could be implemented as a really small handful of transistors for the actual processor and a ton of various memory-mapped peripherials. Some of them being really simple old basic logic chips for ALU.

      It would mean a simple version for cheap microcontrollers would be really cheap to make, a family of compatible devices of different scale would be possible, and extending/upgrading existing instruction set would be easy too.

      The above is not a conflicting statem

  • nihilist (Score:5, Insightful)

    by Nadaka (224565) on Thursday November 19, 2009 @02:20PM (#30161388)

    vaguely reminds me of the nihilist language joke. A language that realizes that ultimately all things are futile and irrelevant, thus allowing all instructions to be reduced to a no-op.

  • Everyone attack him before he wins this round of Age of Empires. Quickly, he's probably low on resources right now.
  • Cheating? (Score:5, Insightful)

    by happy_place (632005) on Thursday November 19, 2009 @02:21PM (#30161416) Homepage
    So the one instuction is essentially a move command that has multiple modes... Ahem. Isn't that cheating? Isn't move considered two instructions already, a load and store? I guess this is really dependent upon how you define what is and isn't an instruction.
    • Re: (Score:2, Interesting)

      by Anonymous Coward

      Erm, no. The canonical single instruction machine uses "subtract and branch if negative" and that's not considered to be three instructions (subtract, test, branch) but one.
      Using memory-mapped facilities to perform operations like addition...now THAT is cheating.

      • Re: (Score:3, Informative)

        Using memory-mapped facilities to perform operations like addition...now THAT is cheating.

        Isn't that what it does?
        Strikes me that that is just complicating things, insofar as you still effectively have multiple instructions, there is just another semantic level tacked on to hide them.

        • Re:Cheating? (Score:5, Interesting)

          by maxwell demon (590494) on Thursday November 19, 2009 @04:08PM (#30163432) Journal

          I'd also consider it cheating. I can also invent a one-instruction computer, where the one instruction is a move immediate instruction. The move instruction moves a byte-sized value into a "command register" which does different things depending on the value of the byte you load into it and the current state of the machine. Indeed, since there's just one instruction, and it always has a single one-byte operand, I just don't encode the instruction itself, I just put all the operands into memory, one after another. And I define the state machine so that the actions are exactly the same as the actions of an x86 interpreting those bytes as separate instructions. Therefore I can avoid doing an implementation myself; I can just use a stock x86 processor as proof of concept.

    • Re: (Score:3, Informative)

      by Talennor (612270)

      So the one instuction is essentially a move command that has multiple modes... Ahem. Isn't that cheating?

      Yes, it is cheating. He basically took the instruction bits of the program and said, "Behold, for they are now address bits!" With the caveat that the address bits happen to address INSTRUCTIONS. It's all pretty brain-dead.

    • Re: (Score:3, Interesting)

      by Nazlfrag (1035012)

      I suppose it's cheating. I think it's useful though simply as a backbone for a custom processor, then patch in what you need. You might need an ALU and DSP for a complex project, and an accumulator & bit shifter for a simpler one. This lets you link them to a common bus architecture which could make for easy prototyping.

  • GOTO ... (Score:5, Funny)

    by gstoddart (321705) on Thursday November 19, 2009 @02:23PM (#30161464) Homepage

    I vote for GOTO as the only instruction.

    That would be hilarious.

    Cheers

    • by jfengel (409917)

      Actually, it sounds an awful lot like a COME FROM instruction.

      http://en.wikipedia.org/wiki/Come_from [wikipedia.org]

      • Re: (Score:3, Funny)

        by gstoddart (321705)

        Actually, it sounds an awful lot like a COME FROM instruction.

        Well, if we're going with joke operations, I'm changing my vote to HCF [wikipedia.org]. ;-)

        Cheers

        • by jfengel (409917)

          COME FROM is a joke, but it really does kind of model what they're doing here. The "one instruction" is a MOVE, but every time you move something to a particular location, some other part of the chip notices and performs operations on it.

          Move one number into location A and another into location B, and magically the CPU knows to multiply them and stick it in location C, like sticking a COME FROM at the instruction that stores into B. It's not exactly a COME FROM since control returns to your next instructi

    • by jeffmeden (135043)

      I think I was in a high school 'comp sci for dummies' class based on that principle. You would be surprised how much qBasic can do with generous use of GOTO.

      Well, at least, it seemed like an impressive program at the time. Good thing I don't write code for a living!

    • by nschubach (922175)

      goto:
      goto goto

      ?

    • NOOP would be funnier.
    • by deander2 (26173) *

      that would be the JMP instruction. =P

      • by gstoddart (321705)

        that would be the JMP instruction. =P

        Or B (branch), depending on your architecture.

        Cheers

    • The language of naughty schoolboys was goto-only. However, it never fulfilled on its promise of naked chicks if you turned to page 69. Some of the programs written in said language were, however, quite humerous and complex. You could implement loops in that language of course, and perhaps even keep an idiot busy for hours. I'm not sure if it was Turing complete though.

    • The only valid program is a single HALT instruction.

  • by nokiator (781573) on Thursday November 19, 2009 @02:23PM (#30161468) Journal
    I built a single instruction microprocessor at grad school. The only instruction was to move a 32-bit data from one address to another address. All the ALU and I/O functions were memory mapped. For example, you could have an adder where address A was operand #1, address B was operand #2 and address C was the result. Branches were handled through ALU units where the result of the operation changed the instruction pointer for some future instruction. It was very easy to implement and notoriously difficult to program.
    • by purpledinoz (573045) on Thursday November 19, 2009 @02:48PM (#30161942)
      For a few seconds there, I thought you said grade school. Made me feel very inferior :) Wouldn't the complexities of programming it be handled by a compiler? If someone managed to write one for a 1 instruction processor?
      • Wouldn't the complexities of programming it be handled by a compiler? If someone managed to write one

        What you say is true, but the most important part, which you leave out, is that managing to write a compiler is crazy difficult for some instructions sets. x86 is not around today because it's technically superior; it's with us because the compilers for better architectures are just too damn hard to write.

    • by Chris Burke (6130)

      So... how did you encode what operation the ALU should perform? And wouldn't that then be the ISA? Couldn't you then make a "one-instruction microprocessor" where the only instruction is "move bytes to x86 processor instruction cache"? ;)

      Or was each possible ALU operation a different memory-mapped address? Was writing the operands to the addresses what caused the operation, or did you have to write to a "do-it" ?

      Not that making such a processor isn't cool. Cus it's cool. Making just about any kind of

    • Re: (Score:3, Interesting)

      Interesting.

      First off, your one-instruction CPU, I guess you didn't need to express the instruction in machine code, just the arguments.

      Here's the funny question, why not develop an assembler with synthetic instructions, like SPARC v9? It would certainly make it easier to program.

    • by bigdavex (155746)

      It seems to me that the the distinction between the microprocessor and the ALU is arbitrary. How is this different than a CPU that comprises address load hardware and ALUs?

  • by mako1138 (837520) on Thursday November 19, 2009 @02:27PM (#30161530)

    It's XC3S1000, not XS3C1000. Been working with these parts too long...

  • So old it's new. (Score:5, Insightful)

    by LaminatorX (410794) <sabotage@praecantator . c om> on Thursday November 19, 2009 @02:31PM (#30161612) Homepage

    Sounds a hell of a lot like the read/write head of the Turing Machine to me.

  • by Chris Mattern (191822) on Thursday November 19, 2009 @02:32PM (#30161626)

    Why, DWIW (Do What I Want), of course.

  • One instruction... (Score:4, Insightful)

    by hey (83763) on Thursday November 19, 2009 @02:33PM (#30161652) Journal

    ... whose first operand is the task to perform. Followed by the necessary operands for that task.

    • by pz (113803) on Thursday November 19, 2009 @03:07PM (#30162256) Journal

      ... whose first operand is the task to perform. Followed by the necessary operands for that task.

      Exactly. It isn't a single instruction computer.

      And the idea isn't new.

      If a single instruction architecture is designed, then there is only one instruction (duh), and there's no reason to encode that instruction in the instructions themselves. All that will be left is encoding for operands. There's a tempting but brief foray into semantics where you can argue that the first handful of bits in TFA's instruction set are operands to the execution control unit, but that is, in fact, what most would consider defining a set of instructions where each distinct value in that first handful of bits describes more-or-less a distinct instruction. One quickly realizes, however, that there is a fundamental difference between data operands and instruction operands, and, by stating that it is a single instruction architecture, the implication is that there are no instruction operands. Therefore, TFA's architecture is not single instruction.

      It's well known that there are universal logic elements (like the two-input NOR gate), and, by extension, you can create single instruction architectures that compute the universal logic element operation on two arguments, writing the results to a third. Instructions in such architectures are just memory locations -- source A, source B and destination. While incredibly simple, such a machine is going to have a very, very low instruction set density. It's an interesting project for intellectual curiosity (like in an introductory graduate level machine architecture course) but hardly worthy of a Slashdot front page mention.

  • That would be the system with no instructions at all!

  • The instruction is "What is 7 times 9"

  • by systemeng (998953) on Thursday November 19, 2009 @02:36PM (#30161726)
    I remember hearing about building a one instruction computer back in engineering school. The one I heard about was based on Subtract and Branch if Not Equal. My roommate at the time figured it ought to be a way to get a very high clock rate. It seems like he found a proof in a hoary old book that such a computer was in fact Turing complete. I'm sure I'll get flamed for posting a vague recollection but. . . here it is.
  • AAA AA A A (Score:5, Funny)

    by tonique (1176513) on Thursday November 19, 2009 @02:37PM (#30161732)
    AA A AA  AAAA A  AAA AA   A A  AA  A A AAA    A A AAAA    AAA  AAAA
  • by Animats (122034) on Thursday November 19, 2009 @02:39PM (#30161782) Homepage

    That's an old idea. [wikipedia.org] The classic "one instruction" is "subtract, store, and branch if negative". This works, but the instructions are rather big, since each has both an operand address and a branch address.

    Once you have your one instruction, you need a macroassembler, because you're going to be generating long code sequences for simple operations like "call". Then you write the subroutine library, for shifting, multiplication, division, etc.

    It's a lose on performance. It's a lose on code density. And the guy needed a 1,000,000 gate FPGA to implement it, which is huge for what he's doing. Chuck Moore's original Forth chip, from 1985 [ultratechnology.com] had less than 4,000 gates, and delivered good performance, with one Forth word executed per clock.

  • RISC vs CISC - sigh (Score:2, Informative)

    by peter3125 (1117319)
    "The advantages of RISC are well known — simplifying the CPU core by reducing the complexity of the instruction set allows faster speeds, more registers, and pipelining to provide the appearance of single-cycle execution." I know this has been argued to death already - but it just isn't completely true that a RISC has advantages over a CISC. The gain in speed is usually negated by the lack of expressiveness and the number of registers would help a CISC just as much as a RISC. Why is this being drag
  • I think you can get it to compute anything - if you have enough of them.
    • by omnichad (1198475)

      That was exactly my first thought.

    • That's absolutely true. Anyone who has studied CPU logic knows that the CPU is made of NAND gates which can be arranged to make any other gate. A NAND instruction which takes 2 addresses of 2 different bits (has to be bitwise not bytewise) and stores the result can do anything.

      One thing i don't get is why it hasn't been done? The wikipedia article on the one instruction computer doesn't list a bitwise AND instruction as being one of the possible instructions for a one instruction computer.

      http://en.wiki [wikipedia.org]
  • "One-der" (Score:4, Insightful)

    by porges (58715) on Thursday November 19, 2009 @02:42PM (#30161846) Homepage

    The hyphen being so everyone doesn't call it "The O-need-er", as in That Thing You Do.

  • All the FPGA vendors have their own embedded CPU cores, such as the Xilinx Microblaze [wikipedia.org] and the Altera NIOS II [wikipedia.org] which are very small FPGA-embeddable CPU cores.

    You also have free options that aren't tied to specific FPGAs like the LEON sparc-compatible processors [wikipedia.org].

  • The idea of offloading software functions onto custom hardware built around a TTA is interesting - 5 years ago I used to work for Critical Blue [criticalblue.com] who were writing software to design and build those custom processors and optimise an ISA for them. Worth a look.
  • One command? (Score:3, Interesting)

    by HockeyPuck (141947) on Thursday November 19, 2009 @02:56PM (#30162090)

    Reminds me of this old saying,

    "Every program can be reduced by one instruction, and every program has at least one bug. Therefore, any program can be reduced to one instruction which doesn't work."

    I just wish I knew who came up with it.

  • by KiwiCanuck (1075767) on Thursday November 19, 2009 @02:58PM (#30162126)
    nop
  • by shoor (33382) on Thursday November 19, 2009 @03:05PM (#30162212)
    There can be different architectures for computers, but, nowadays, for many of us, I'd say there is one particular model of an architecture that is likely to be the only one we're really familiar with, and that automatically comes to mind when one speaks of a computer architecture. It's a rather compartmentalized architecture in which the CPU is the place where opcodes are executed and memory is just a big flat address space for data, including instructions. This "transfer triggered" architecture strikes me as being not so much a 1 instruction computer as one where instructions are implemented in a less compartmentalized fashion, spread out among special units activated by addresses, as opposed to the more plain architecture where bit patterns on the address bus simply activate individual generic memory cells along with a read/write signal. More than that may happen, cache memory comes into play with all it's complications for instance, but the 'model' for the programmer is that simple one.
    • There can be different architectures for computers, but, nowadays, for many of us, I'd say there is one particular model of an architecture that is likely to be the only one we're really familiar with, and that automatically comes to mind when one speaks of a computer architecture.

      Which just goes to show how shockingly ignorant 'many of us' are.

      Now if 'many of us' (brighter than the norm, or so the theory goes) can be so ignorant - why do we laugh at Joe Sixpack?

  • The point was supposed to be speed. So, he gets 10 MHz? That's not very impressive...
    • by Rockoon (1252108)
      No matter how you look at this type of computer, its just not going to compete in the general computing space because you can't design a memory cache that can cope with the forced random access to memory.
  • Isn't it cheating to have a CPU with one instruction that relies on custom hardware to do the rest of the instructions? You're just re-defining the CPU and adding more hardware to 'simplify' the CPU!
  • 2009: one million gates, one instruction, RISC, gnarly to program = 10 MIPS.

    1984: 200,000 gates, gobs of instructions, CISC, easy to program = 10 MIPS.

    We should have more to show for the last twenty-five years in microprocessor design.

  • I invented this and published it more than 30 years ago, during the early debate between CISC and RISC microprocessors. It was in the (now defunct) "Modern Data" magazine, in my column "Carol's Microcosm." It's an obvious solution for any computer programmer who understands hardware logic.
  • wonder how many addressing modes there are...

  • 1) "KILL ALL HUMANS!"

  • ... is it pronounced "O-knee-der" or "O-ned-der"?

    You know, every time it does that thing it does.

  • by straponego (521991) on Thursday November 19, 2009 @04:49PM (#30164284)
    ...if the one instruction is NOP. He could easily crack the petanop barrier.
  • by stonewolf (234392) on Thursday November 19, 2009 @05:27PM (#30164910) Homepage

    A cousin of mine (Howdy Rusty!) described this concept to me in the '70s while I was taking classes toward my CS degree.

    A little background: I went to the good old University of Utah which had a Boroughs 1700 with user writable microcode and so a lot of project centered around writing microcode and designing micro architectures. A friend was trying to code up a single instruction machine based on Curry Combinators. I thought he was nuts, but I liked the idea of a single instruction machine. So, I was talking to my cousin and he described an architecture that had one instruction that was a source and a destination address. Any address could be either memory or a register in a functional unit, an FU for short. No kidding, that is how he described it.

    The only trouble was trying to figure out how to do a conditional branch.

    A few years later while I was in gradual school I solved that problem and wrote paper about it. Being a gradual student I could not publish without permission from my adviser. Well, he got a good laugh out of the idea and told me not to show it to anyone. So, of course I sent it to everyone I knew. They all had a good laugh to. Said it was the funniest thing I had ever written. You see, I was into writing humorous stories at the time and people thought this was another one. Oh well, I have a print out of the thing around here somewhere.

    What I really liked about the architecture is that if you started modifying it to make it more economical, doing things like making the addresses have different lengths and adding a bit to tell you if the long address is the source or the destination, the move architecture starts looking more and more like a classic instruction set architecture. I thought that was very cool. When you look at micro coded architectures and think about a pure move based processor it really does look like all traditional architectures are attempts to make the one instruction machine make more economical use of instruction bits.

    So, how did I solve the conditional branch problem? Pretty much the way this fellow did. Every FU may, or may not, cause condition flags to be set. I added registers where you could read and write the condition bits and read and write the program counter. I also added a mask register that was anded with the condition register so you could enable and disable conditions. Then I just made the current instruction conditional on the values of the flags register anded with the mask register. If the result was non-zero the current instruction was skipped. Of course, the machine had to clear the condition register after each instruction was executed. (Hmm, it would make more sense to only make moves to the program counter conditional and it would make more sense to only clear the flags after a move to the instructions counter... Hey was a gradual student back then! :) That approach allowed you to select say the sign bit from one ALU, do an subtraction by moving values to two registers in the ALU, then jump if the sign bit is set. It also let you directly make any instruction conditional so you could implement something like the ABS() function without any jumps. Or, at least that was the idea.

    I called my one instruction: The Conditional Move From Here To There And Clear Flags, or TCMFHTTACF insturction. The assembly for it was really dull, it just always had the same op code down the left hand edge of the screen... Ok, really, I just never listed anything but addresses when I wrote code for it.

    Nice to see that someone actually built one of these. BTW, this kind of architecture makes it easy to add multiple execution units. With parallel execution and careful use of shared and private FUs and memories you can build a pretty damn powerful special purpose processor without a lot of hardware complexity.

    This just to damn cool... someone finally built it!

    Stonewolf

God may be subtle, but he isn't plain mean. -- Albert Einstein

Working...