open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  1. MIT - 6.001 - SICP

寄存器机器

在本课之前,我们基于 Scheme 环境建立抽象程度更高的 Scheme* Evaluator,已经对利用抽象级别低的工具构建抽象级别高的工具有了概念;从本课开始,我们从另一个方向出发,从构建一个 CPU (central processing unit) 开始,看一看 Scheme 环境的底层。

设计一个 CPU

接下来,我们利用以下工具来构建一个机器语言是 Scheme 的 CPU:

  • 电线 (wires)

  • 逻辑电路 (logics)

  • 寄存器 (registers)

  • 序列控制器 (control sequencer)

本节的目标:

  • 在硬件中实现迭代算法

  • 在硬件中实现递归算法

最终目标:

在硬件中支持机器语言 Scheme。举例如下:

![](/assets/Screen Shot 2018-04-20 at 11.12.09 AM.jpg)

最终我们可以利用这个 CPU 构建一个终极机器,它可以接受任意一个procedure,如求最大公约数 (GCD),然后调整自己内部的状态使之与 GCD 的逻辑相同,同样的输入产生同样的输出。这正是二十课中提到过的通用机,只不过它的抽象级别很低,直接利用的是 CPU 的机器语言。

GCD

GCD in Scheme

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

GCD circuit diagram

![](/assets/Screen Shot 2018-04-20 at 11.14.55 AM.jpg)

上图是 GCD 的逻辑电路,也代表了数据通路 (datapath)。以下是逻辑电路中的各元素说明:

  • Button (图中的圈圈叉叉): 当 Button 被按下后,输入线 (input wire) 上的值流过输出线 (output wire)

  • Register:

    • 当有新的值从输入线上进入时,改变内部存储的值

    • 不断输出当前内部存储的值

  • Operation: 接收输入线进入的数值,经过某个固定的函数,由输出线输出

  • Test:

    • 输出是 true or false 的操作,将结果输出到 condition register

GCD instructions in register machine

(controller
test-b
  (test (op =) (reg b) (const 0))
  (branch (label gcd-done))
  (assign t (op rem) (reg a) (reg b))
  (assign a (reg b))
  (assign b (reg t))
  (goto (label test-b))
gcd-done)

Connect instructions with circuit diagram

![](/assets/Screen Shot 2018-04-20 at 10.20.55 AM.jpg)

仅仅有逻辑电路并不是一个完整的 register machine,我们还需要别的组件来控制命令的执行,这个东西就是图中的 sequencer。sequencer 接受 condition register 的输入,来决定下一个要执行 instruction,这个 instruction 的地址总是被存在 sequencer 内部的 program counter register 中。图中的 instructions 则与逻辑电路图中的 Button 一一对应。

结合 GCD 的 register machine instructions:

  • controller 就是刚才提到的 sequencer,控制程序的执行过程

  • test-b、gcd-done 是一个 label,指向其下的命令地址,用于 branch 命令

  • test 命令用于判断某个条件是否成立,成立则把 True 放入 condition register,不成立则把 False 放入 condition register

  • branch 命令用于有条件跳转,当 consition register 中是 True 时,则程序跳转至 label 指向的地址,否则继续顺序执行

  • goto 命令是无条件跳转,直接跳转到 label 指向的地址

Less-abstract GCD instructions

在前面的 GCD instructions 中,我们用到了 rem instruction,这种抽象程度较高的 instruction,被称为 abstract instruction,它可以被进一步拆分成更小的,更基本的 instruction。以下是一个更具体的 GCD instructions:

(controller
test-b
  (test (op =) (reg b) (const 0))
  (branch (label gcd-done))
  (assign t (reg a))
rem-loop
  (test (op <) (reg t) (reg b))
  (branch (label rem-done))
  (assign t (op -) (reg t) (reg b))
  (goto (label rem-loop))
rem-done
  (assign a (reg b))
  (assign b (reg t))
  (goto (label test-b))
gcd-done)

这里把 rem 展开成了更基本的 instructions。

参考

Previous通用机Next子程序、栈与递归

Last updated 6 years ago

Youtube: SICP-2004-Lecture-21