JONY – 第 2 页 – JONY'S WORDPRESS

分治法与主定理

分治法分治法是种经典的算法设计策略，这种策略简单来说就是先把原问题分成规模更小的子问题，再把子问题划分成更小的子问题…一直划分到子问题十分容易解决，然后就能倒过来解决原问题。数学中数列项的递推式就能看做是基于分治策略的算法，数学中的递推式很多时候都比通项式更容易找到和理解，分治算法相对于一些其他的算法很多时候也是这样。虽然分治策略本身不限定算法的物理实现形式，但通常默认分治算法是递归函数程序。由于分支策略只是一个大的设计框架，所以不同问题的分治算法间的区别可以很大，且同一问题也可能有多种分治算法。但所有分治算法都是遵循如下3大步骤的(或者说能按这几大步骤设计)： 1) 分解子问题：需要拆分出几个子问题，这些子问题的输入应该怎么求得； 2) 解决子问题：解决上述这些子问题，并得到子问题的解；… 阅读全文

数字逻辑层概述

数字逻辑层概述由最底层提供给数字逻辑层的基本电路单元包括5种门(gate)。数字逻辑层主要讨论如何用各种门搭建能实现具体功能的门电路，它们被作为功能单元提供给微体系结构层。事实上很难做到仅讨论上面所规定的内容，首先必须明确更高层提供给该层的数据表示什么，否则无法设计相关的门电路，所以之后将这部分内容称为机器级数据表示，并在该层额外讨论。另外由于这里主要关注CPU的设计，所以之后不会完整讨论一些硬件的门电路实现，但为理解计算机系统的整体运转机制，仍需明确这些硬件与外界的通信规则，所以之后将这部分内容称为接口技术，并在该层额外进行讨论。门通常在数字逻辑层无需关心这5种门的内部构造，但这里还是说明一种用NPN三极管的电子开关特性构造5种门的方法。在上图第一行最左边的电路中，称对地电势0~0.5V为低电平，1~1.5V为高电平，规定\(V_{cc}\)恒为1.5V，将电势\(V_{in},V_{out}\)分别作为该电路的输入和输出。通常NPN三极管元件的导通压降在0.7V左右，当输入为低电平时，射极和集极相当于开路，\(V_{out}=V_{cc}\)，所以输出为高电平，当输入为高电平时，射极和集极相当于短路，\(V_{out}=0\)，所以输出为低电平。这种输入低电平输出高电平，输入高电平输出低电平的电路称为非门。通过串并联NPN三极管可得上图第一行的另外2个电路，它们都有\(V_1,V_2\)两个输入和\(V_{out}\)一个输出，分别称为与非门和或非门。最后将与非门的输出接入非门可得与门，将或非门的输出接入非门可得或门。… 阅读全文

树与二叉树

树的定义树(Tree)默认指有根树(Rooted Tree)，无根树(Unrooted Tree)之后会在图结构(Graph)中讨论。树是种非线性结构，树中的元素一般称为树节点(Tree Node)，线性表元素的前驱后继是空或唯一的，一个树节点可以有不止一个“后继节点”，“前驱节点”是空或唯一的。给出树\(T\)的递归定义如下，递归定义法在算法中经常使用到： 1) \(T\)是由\(n\geq 0\)个节点(Node)组成的有限集合； 2) 当\(n=0\)时，\(T\)是空集称为空树； 3) 当\(n\geq 1\)时，\(T\)有且仅有1个节点被指定为\(T\)的树根(Root)； 4) 当\(n\geq 2\)时，\(T\)除树根外的所有节点被划入\(m\geq 1\)个不相交有限集合\(T_1,T_2…T_m\)(即它们的并集是\(T\)除树根外的所有节点，它们中任意2个的交集为空集)，并要求\(T_1,T_2…T_m\)都递归的满足树的定义，它们被称为\(T\)的子树(Subtree)；… 阅读全文

组合逻辑单元

组合逻辑电路(combinational logic circuit) 组合逻辑电路是指在任何时刻，输出状态只决定于该时刻各输入状态的组合，与其他时间的状态无关的电路。组合逻辑电路的功能可以用逻辑函数或真值表描述。接下来会讨论一些计算机内部经常用到的组合逻辑电路单元。多路选择器(multiplexers)上图就是1个多路选择器，其输入分为两部分，\(D_0\)～\(D_1\)是8个“待选择”的输入，而\(ABC\)则是提供“如何选择”的信息的。其功能是根据\(ABC\)状态的共\(2^3\)种组合，表示将8个“待选择”的输入中的哪一个送入后面的或门。当\(ABC\)的组合表示要选择某个\(D\)时，该\(D\)对应的与门收到的所有其他输入都是真，也就是该与门的输出会与其对应的输入\(D\)保持一致。而其他与门的输入将至少有1个为假。… 阅读全文

指令系统层概述

MIC-1的数据通路与微指令

IJVM与MIC-1 微体系结构层夹在数字逻辑层和指令系统层之间。设计CPU时通常先大致确定指令系统，然后设计微体系结构实现它，或是两者是并行设计的。通常RISC(精简指令集)的很多指令可在单个时钟周期完成。而Intel酷睿的x86指令集属于CISC(复杂指令集)，一条指令可能需要多个时钟周期，会被分为多个操作步骤，其控制方式和简单的指令系统有较大区别。微体系结构层没有太多一般性原理，很多都是特例。所以在学习微体系结构层时，需要预先引入一种具体的指令系统，然后再考虑怎么构建微体系结构层实现指令系统。这里将要引入的指令系统是JVM的一种子集IJVM，其仅包含部分整数指令，并且不包含面向对象特性。IJVM指令通常只有1-2个字段，第1个字段都是操作码(opcode)，用于标识指令，有的包含操作数(operand)字段，用于提供额外信息。… 阅读全文

完整的MIC-1微体系结构

MIC-1的组成完整的MIC-1微体系结构如上图所示，其由数据通路和控制部分组成。这里需要说明一下控制部分所引入的部件，以及之前没讨论到的一部分数据通路上的信号： 1) 控制存储器：计做CS，图中512*36位的只读存储器，是控制部分最重要的电路，其固化了用于实现ISA指令的所有微指令，其至多能存储512条微指令，其功能和只读内存相似，其中的每条微指令都有自己的地址，微指令的地址也叫微地址。该CS接受的输入是微地址，输出是微指令。由于实现指令系统类似于在CS中写程序(填微指令)，所以也把整个CS中的微地址和微指令统一称为微程序； 2) 微程序计数器：图中MPC，功能类似MAR，是微地址的寄存器； 3) 微指令寄存器：图中MIR，存储将要执行的微指令。上图MIR画的很像微指令； 4) N与Z连接的方框：两个1位触发器，其数据写入时机和“内存写入寄存器”、“C总线写入寄存器”一样，也是时钟上升沿的边沿触发；… 阅读全文

IJVM的内存模型与指令集

栈内存模型通常编程语言支持过程(procedure)和方法(method)。过程就像编程里的函数调用，有自己的局部变量，中间结果等。过程在返回后，其局部变量消失。这意味着需要对局部变量有效的管理，容易想到给每个局部变量固定地址，但这是不行的，因为过程支持自己调用自己(递归)，这将导致地址冲突。这里引入基于栈的局部变量管理，简单来说就是划分内存区域放局部变量，用数据结构栈的形式管理。上图给出了一种编程语言执行算术表达式a1=a2+a3的栈内存的活动情况。在执行表达式前通常会声明a1,a2,a3变量，所以栈底的3个元素为a1,a2,a3。在执行算术计算时，第一步是前后将a2,a3入栈，然后通过算数指令弹出栈顶两个元素，得到其和，然后把和入栈，最后把和赋值给a1(图d在原来a1的位置写了a2+a3，目的是表示a1被赋值)。… 阅读全文

用MIC-1微指令实现IJVM

MIC-1的寄存器功能之前陆陆续续讨论过大部分寄存器的作用，这里统一的明确和汇总一下： 1) MAR：32位内存地址寄存器。为read/write内存操作提供内存字地址。用于IJVM方法区以外的区域的内存地址，这些地址对应的数据都是1个字的长度； 2) MDR：32位内存数据寄存器。存放read从内存取回的32位数据、write要写入内存的32位数据； 3) PC：32位程序计数器。为fetch内存操作提供内存字节地址。通常每次fetch取的是IJVM方法区的IJVM指令的1个字节，并且通常是顺序读取的，即下次fetch的地址是PC+1； 4) MBR：8位内存缓冲寄存器。存放fetch操作从内存取回的8位数据。其作为输出时必然会按符号扩展或无符号扩展中的一种方式，把32位数据送上B总线； 5) SP：32位寄存器，指向IJVM栈的栈顶的内存地址；… 阅读全文

二叉树的性质

二叉树的高度如上图所示，可直观的把二叉树节点分层，也可以递归定义节点所在的层(Level)为“树根在第1层，其他节点的层数等于其父亲节点的层数加1”。树中层数最大的节点的层数称为树的深度(高度)。层数满足如下性质： a1) 二叉树在第\(k\)层的最大节点数为\(2^{k-1}\)； a2) 设二叉树的节点数为\(n\)，深度为\(m\)，则\(n\leq 2^m – 1\)；有些教材会从0开始计层(level)或将单节点二叉树的高度计为0，所以之后文章里的高度可能和这里不同。二叉树的形态直观上如果两个二叉树画出来后“重合”就称它们相似或形态相同，考虑将这种直观概念转化成严格定义，先用\(S(T_1,T_2)\)表示二叉树\(T_1,T_2\)是否相似，直观上如果两个二叉树的树根、左子树、右子树都分别“重合”，那么两个二叉树“重合”，基于这点可严格给出\(S(T_1,T_2)\)的递归定义为“若\(T_1,T_2\)的树根都为空则返回真，若\(T_1,T_2\)的树根只有1个为空则返回假，若\(T_1,T_2\)的树根都非空则返回\(S(L_1,L_2)\)且\(S(R_1,R_2)\)。其中\(L_1,L_2\)分别是\(T_1,T_2\)的左子树，\(R_1,R_2\)分别是\(T_1,T_2\)的右子树”。… 阅读全文