One of the most interesting talks at WISTP so far was David Naccache's talk who, as an invited speaker, used the time to talk about some projects he's currently working on with students and fellow researchers and one of those topics was subleq machines. I've heard about RISC and CISC machines, Turing machines, single- and multicore processors, reconfigureable processors, general-purpose and dedicated co-processors and a lot of other architectures before but a subleq machine was completely new to me. It's not about Complex Instruction Set Computing nor Reduced ISC but about Single Instruction Computing. Now this might initially sound stupid if not impossible but quite to the contrary: Not only is it possible to compute any instruction using sequences of the subleq instruction (a bit like NAND-logic where you build arbitrary gates from NAND gates) but there's also some sense to limiting yourself to just one instruction. But let me explain the subleq machine a bit more, first.
A
subleq a b c
instruction computes the same as the following C pseudo code:
*b = *b - *a;
if (*b <= 0) { goto c; }
With this,
subleq a, a, $+1
is the same as
clear a
just to give an example of the construction of other instructions and David Naccache showed some more. Also, subleq isn't the only instruction which could be used for a SI(S)C machine but among all the instructions investigated so far, subleq was their favourite.
So why would you want to build such a subleq machine? One thing is, that it is a very simple machine and thus easy to analyze on the hardware level if you need to prove resilience to power analysis attacks and fault injection. It also fills the gap between theoretical fault injection ("I have this equation and if there's a fault in this value then...") and practical fault injection ("I have this device and point my laser at that position and something happens...") as a subleq machine is simple enough to be used within formal frameworks of theoretic computer science. Using the tools of theoretic computer science one may thus hope to prove for a specific subleq program that it is resilient for up to n faulty instructions.
Subleq is not the simplest OISC. There are bit manipulating machines, which are much simpler yet still universal and with comparable power as arithmetic based OISCs.
ReplyDeleteYes, but neither David Naccache nor I claimed that subleq is the simplest machine possible. My perception of David's talk was that his goal isn't aiming at finding the simplest machine, but at finding a machine which is simple enough to fit it into theoretical frameworks, easily testable in an evaluation process and yet provides reasonable performance. Considering that it is work in progress, subleq seems to be the best trade off that David and his group have found so far.
ReplyDelete