首页 > 技术相关, 随感 > 单指令计算机OISC(one instruction set computer)

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

2011年1月6日 sigma 发表评论 阅读评论

前几天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:我上面说的东西肯定有很多错误,欢迎指正

本文作者: Sigma    在新浪微博关注SigmaSigmaWeibo    RSS订阅本博客
本文链接: http://www.sigma.me/2011/01/06/one_instruction_set_computer.html
本博客采用知识共享署名—非商业性-禁止演绎使用3.0协议进行许可,转载请保留作者和原文链接。

  1. 2011年1月9日12:24 | #1

    One Instruction Set Computer(OISC) – HU, Pili – Blog …
    […] Pickup: http://www.sigma.me/2011/01/6/one_instruction_set_computer.h … […]…

  2. 2011年1月6日17:15 | #2

    @grapeot

    那就是你健忘了。。。

    看来我要把这回复框做小一点,和上面的大小一致

  3. 2011年1月6日17:01 | #3

    换行害死人啊

    那单指令我记得最早是我说有,然后你不信 <– 这是前半段

  4. 2011年1月6日16:22 | #4

    @grapeot

    哪前半段,我真不记得了。。。

  5. 2011年1月6日16:14 | #5

    去你丫的,我怎么不记得前半段了,就是哥的教诲。

    哇靠,那(雨)是个自动机小超人,你跟她搞必然要被搞晕的~

  6. 2011年1月7日07:38 | #6

    @grapeot

    其实你想说你才是这个世界的真谛,你很重要

    哎,何必这么隐晦呢

  7. 2011年1月6日15:34 | #7

    雨是谁?嗯?

    哎,后面三门连续的考试怎么办啊怎么办 — 哈哈哈哈哈,你什么时候考?

    那个单指令计算机当时上组成原理还是体系结构的时候就跟你说过的。所以你那不是直觉,是哥的教诲。

    可计算理论。。好高深。。

  8. 2011年1月6日17:00 | #8

    那单指令我记得最早是我说有,然后你不信,但是某一天你说你看到有个sb真造出了这样的计算机

    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    这个是前半段

  9. 2011年1月7日06:58 | #9

    为什么单指令计算机前三个缩写都带个SB。。。SB才是世界的真谛啊

  10. 2011年1月6日16:04 | #10

    @grapeot

    雨是谁你还不知道

    我下周一,周三,周四都有考试。。。

    那单指令我记得最早是我说有,然后你不信,但是某一天你说你看到有个sb真造出了这样的计算机

    可计算理论其实很sb的,就是什么问题是可以通过图灵机计算的,有些问题是不可以通过图灵机计算,比如说什么停机问题

  1. 本文目前尚无任何 trackbacks 和 pingbacks.

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