存档

文章标签 ‘Single Instruction Computer’

单指令计算机OISC(one instruction set computer)

2011年1月6日 sigma 10 条评论 9,624 views

前几天grapeot叫我帮他看一些体系结构的题,其中有一道题如下:

ISA Design:Describe an instruction set that is both minimal and can support any computation.

这道题的意思是设计一个计算机指令系统(Instruction Set Architecture, ISA),要求最少指令,并且要支持任何运算。

当时,由于我本人是做逻辑设计和验证的,凭直觉以及数理逻辑的知识,知道任何复杂的逻辑(包括计算机硬件系统)都是可以通过与非(NAND)或者 或非(NOR)堆出来的,而软件能够实现的运算,必然也可以通过硬件实现,因此,我觉得最简指令集就是一条 NAND指令 或者 NOR指令 。当然,这指令的操作数可以是三个。比如 NAND b,b,a,就是将b、a与非赋给a。

但是,我当时不太放心,而我这学期恰好学了可计算性(其实不算学,就去了一两节课)和计算复杂性。因此,我考虑了尝试用可计算理论来解决,根据我们学的可计算理论,任何可计算的问题都可以通过以下四条指令编程实现:

①自加指令:V=V+1

②自减指令:V=V-1

③空指令:   V=V

④条件跳转指令:if V ≠ 0,GOTO L

对于这个答案,我比较自信能够完成所有通用计算。我一直搞不明白的是为什么要加空指令(现在想可能是为了可计算理论里面证明来用的)。

昨天,和雨聊到自动机的话题,我又想到了这道题,当时我把我的想法说了,但貌似雨不太理解,并且说道如何实现除法操作,我自己都被搞晕了。只是我们都觉得也许从图灵机角度出发会比较好(图灵机其实就是一些状态机的跳转,这些状态机可以用四元组或者五元组构成)。今天恰好不想复习(哎,后面三门连续的考试怎么办啊怎么办),于是又想了下这个问题,但还是想不太明白。

只好放出最后一招,放狗搜,凭直觉,我觉得肯定有单指令的计算机,于是直接搜“single instruction computer”,搜到了wikipedia的词条OISC(one instruction set computer)。看了下,感觉比较靠谱,在这里分享下:

维基上把一条指令的计算机主要分成了四种:

①减并且小于等于0跳转(Subtract and branch if less than or equal to zero

②减并且为负数跳转(Subtract and branch if negative

Reverse subtract and skip if borrow(这个貌似翻译成起来很拗口,并且我也没看太懂,所以不翻译)

Move(不过看了下,貌似它需要有相当于一个ALU功能的ROM,其实这个ROM相当于图灵机里的状态转化的集合F)

在这里,我只解释下第一种,第二种与第一种类似,第三种没看懂,第四种,感觉就是个图灵机。

首先,解释下subleq(“SUbtract and Branch if Less than or EQual to zero”)的定义,其实它相当于两条指令:

subleq a, b, c   ; Mem[b] = Mem[b] – Mem[a]
                     ; if (Mem[b] ≤ 0) goto c

下面用subleq可以完成一些其他运算,通过部分示例来说明它是可以完成通用计算的:

  • 无条件跳转
        JMP c ==    subleq Z, Z, c   ; Z is a location previously set to contain 0
  • 加法操作
        ADD a, b == subleq a, Z
                    subleq Z, b
                    subleq Z, Z
  • MOVE操作
        MOV a, b == subleq b, b
                    subleq a, Z
                    subleq Z, b
                    subleq Z, Z

    从上面,我们几条指令的翻译,我们可以比较自信的下结论,subleq是比较靠谱的。

从上面几个指令集,很容易发现,貌似条件跳转是一个很核心的东西。

不过,我还是想,一个NAND指令还是可以实现单指令计算机的,其他算术和逻辑运算肯定是能用NAND完成的,现在只剩下一个条件跳转了。但凭我直接,条件跳转和硬件中的二选一很像,既然,二选一可以用NAND实现,条件跳转肯定也可以。

ps1:更多关于一条指令的计算机请看google上single instruction computer的搜索结果.

ps2:我上面说的东西肯定有很多错误,欢迎指正

无觅相关文章插件,快速提升流量