JONY

红黑树

红黑树(Red-Black Tree)1972年德国学者R.Bayer提出平衡二叉B树，1978年Leo J. Guibas和Robert Sedgewick将其重新表述为更容易描述和实现的红黑树。红黑树基本是目前最流行的自平衡二叉树，很多程序语言的数据类型、操作系统的算法都是基于红黑树的。下面先定义松弛红黑树(relaxed red-black tree)，然后在松弛红黑树的基础上定义红黑树： 1) 松弛红黑树节点：额外包含一个布尔值的BST节点。为方便称其表示红或黑，对应的节点为红节点或黑节点； 2) 松弛红黑树：由松弛红黑树节点构成的BST，且满足如下性质： 2.1) 红节点如果有孩子，则孩子只能是黑节点； 2.2) 对于任意节点\(x\)，从\(x\)到\(x\)子树的所有叶节点的路径中，黑节点数必须相同； 3)… 阅读全文

INTEL酷睿i7管脚信号与DDR3内存总线操作

Intel酷睿i7处理器(第二代)第二代(Sandy Bridge)酷睿i7采用了32nm工艺，主频可达3.5GHz，是8086/8088后裔中比较年轻的一员。Intel为第二代酷睿i7提供了很好的向前兼容性，其具有和前辈80386、8048以及Pentium家族相同的指令系统层，包括相同的寄存器数目、指令集、浮点数标准等等。并且虽然它的性能与晶体管数远远超过了最前辈的8088处理器，但它还是向前兼容了8088，也就是说第二代酷睿i7可以不加修改的运行8088程序。当然第二代酷睿i7也包含了很多新的特性，比如新的加密指令等等。 第二代酷睿根据价位分为2-6核的版本，对于使用这种CPU的计算机，从计算机系统的角度应把它当成是多CPU的。程序员可利用多CPU优势编写多线程程序，通过真正的并行来提升速度。Intel在早期的Xeon服务器CPU中使用了超线程技术，超线程同样用在了第二代酷睿i7中，该技术可在1个物理CPU核心上创建2个硬件级的逻辑线程，简单来说就是在硬件层用1个物理CPU虚拟出多个CPU，所以带有超线程技术的CPU在操作系统的“硬件资源管理器”中会显示更多的CPU数。第二代酷睿i7有优秀的微体系结构层设计，支持同时执行4条指令，使之成为4发射超标量计算机。… 阅读全文

SPLAY树

SPLAY树(伸展树)1985年美国学者Daniel Sleator和Robert Tarjan提出Splay树，其能保证运算的摊还代价是\(O(\lg{n})\)，但不保证每次运算的实际代价都是\(O(\lg{n})\)，所以其并非严格意义上的自平衡二叉树，但这也使其有更简单的定义和运算步骤。这里直接给出Splay树的定义，首先其运算功能和前文的BST一致，且运算开始前只需保证二叉树是BST，但运算步骤是被具体规定的，它们都必须基于伸展运算\(splay(x)\)，其功能是通过多次单旋转使\(x\)成为树根。下面给出Splay树运算的步骤，其包括\(splay(x)\)的步骤： 1) \(splay(x)\)：开始迭代过程，每轮迭代的步骤如下： 1.1) \(x\)无父亲：退出迭代； 1.2) \(x\)有父亲无祖父：对\(x\)的父亲执行1次单旋转使\(x\)取代其父亲的位置(见上图第1张)。退出迭代；… 阅读全文

TREAP树

TREAP树(树堆)1980年Jean Vuillemin在解决范围搜索的问题时提出笛卡尔树，其特点是节点包含2个关键字。之后Edward McCreight提出一种基于笛卡尔树的结构并称之为Treap树，这是Tree和Heap的合成词，所以Treap也译为树堆。1989年Raimund Seidel和Cecilia R. Aragon利用带随机化策略的Treap树实现了BST的功能，在此之后Treap树一般用于指代这种结构。Treap树不是严格意义的自平衡二叉树，但其相比BST能在更一般的条件下保证二叉树的期望高度是\(O(\lg{n})\)。这里直接给出Treap树的定义，首先Treap节点相比前文的BST节点要额外存储一个堆关键字\(hkey\)，Treap树的运算功能和前文的BST一致，但每次运算开始前后除了要保证二叉树是BST还要保证任意节点的\(hkey\)都不大于其所有后代的\(hkey\)，最后规定Treap树的运算为如下的步骤：… 阅读全文

B树

B树(B-Tree)1970年德国学者R.Bayer提出B树，这是一种多路的自平衡树，其相比于红黑树等自平衡二叉树并没有更好的渐进代价，但在一些场景中其实际性能优于自平衡二叉树。B树包含一个称为最小度数(degree)的关键参数，该参数可以是大于1的任意整数，初始化B树时需同时给定该参数，之后该参数固定不变。最小度数为\(t\)的B树可通过如下几点来定义： 1) B树节点可包含多个关键字，非树根节点的关键字数目的取值范围是\([t-1,2t-1]\)，树根节点是\([0,2t-1]\)，树根节点的关键字数目等于0当且仅当B树中无关键字，关键字数目等于\(2t-1\)的节点被称为满节点。节点的关键字被非严格递增排序，任意节点\(x\)的第\(i\geq 0\)个关键字可计为\(x.keys[i]\)。需明确任何时刻都能得到任意节点\(x\)此时的关键字数目；… 阅读全文

计算机系统的分层

计算机系统的分层计算机系统(computer system)是计算机的硬件系统和软件系统构成的整体，这个概念跟操作系统(operating system)易混淆，因为平时较少使用到前者，后者其实是前者的一部分。在研究结构比较复杂的系统时，通常会先根据一些原则和思想将其划分成多个层(layer)，然后通过逐个的研究各个层来研究整个系统。现代计算机系统也是分层研究和实现的，一般认为其最底层位于数字电路(digital circuit)中靠顶层的位置，该位置实际并不太关心电路本身，而是关心如何用电路基本组件来构造可实现具体逻辑的组件，而该位置以下的部分则属于电子工程学(electronic engineering)等其他领域。需要明确这里的计算机指数字式电子计算机，而计算机系统本身并不限制实现方式，比如更早出现的机械计算机、模拟式电子计算机。… 阅读全文

计算机体系结构与计算机组成

计算机体系结构与计算机组成 之前的文章确立了研究对象并将其划为6个层，之后自然应当讨论各个层的设计与实现，这相当于在分层的视角下讨论计算机体系结构(computer architecture)。计算机体系结构研究的是“如何通过组件拆分的形式构造计算机系统”，其中有高观点的“设计方面的问题”，也有低观点的“如何实现给定的设计”，后一类问题被称为计算机组成(computer organization)。 实际上计算机体系结构和计算机组成的概念边界是不太清楚的，在英文维基百科中两者是上述的包含关系，计算机系统学者A.S. Tanenbaum认为这两者通常相同。历史上这两个概念的分裂可追溯至1960s，在这期间图灵奖得主、《人月神话》的作者Fred Brooks创造了计算机体系结构这个术语。当时他作为设计者在描述IBM… 阅读全文

现代计算机系统的硬件结构

现代计算机系统的硬件结构                  现代计算机系统中的主要硬件是CPU、内存、IO设备、总线(bus)，因为它们共同实现了冯·诺依曼结构的主要功能。需要明确这几种硬件不一定完全是物理上互相独立的实体，下面先简单描述它们的功能和结构： 1) 总线：用于在多个硬件之间或多个计算机系统之间实现标准化的连接与数据传输的系统。通常认为总线指硬件，但总线也可泛指相关的标准、协议、软件等。计算机系统中通常包含多种总线，同一种总线还可能有很多个(条)。上述其他硬件通过多种总线互连，它们内部的各个模块也可能通过多种总线互连，而不同总线之间可通过桥片(bridge)这种硬件互连； 2) 内存：配合内存控制器(memory controller)实现冯·诺依曼结构中的内存。内存具备存储能力，其通过内存总线直连内存控制器，再由内存控制器统一处理按内存地址读写的请求。通常将内存和内存控制器统称为内存系统(memory… 阅读全文

处理控制冒险的分支预测技术

分支预测分支预测技术是用于处理控制冒险的。这里借上图中的一段高级语言的IF-ELSE程序，及其对应的某种汇编语言来讨论分支预测，汇编包含1个条件跳转指令(BR)、1个无条件跳转指令(BNE)。 首先，上面的无条件跳转指令看起来似乎容易处理，因为其目的地址不会改变，似乎能直接让取值单元取目的地址的指令，但在很多计算机里并不能这样，这由流水线本身的特点决定。在这样的计算机里，当译码单元“发现”无条件转移指令时，取指单元已经在取其后面的指令了。换句话说，无条件跳转的下一条指令已经上了流水线。这时解决的办法是干脆让这条指令执行完，然后再去执行跳转到的指令。这种情况是很难让人接受的，因为完全不符合前后次序。不过有2种“通融”方式： 1) 默认把所有无条件转移指令的下一条指令“当作”其上一条指令来执行； 2) 让所有无条件转移指令的下一条指令都是NOP；… 阅读全文

处理数据冒险的乱序执行技术

顺序执行与数据冒险为讨论乱序执行技术，先引入一种超标量计算机，并先讨论其上的顺序执行，所谓顺序执行就是前面讨论的流水线的执行方式，即指令都按流水线的方向完成其各个步骤。 该机器包含R0~R7共8个指令层可见的寄存器，其所有算术指令都由3个寄存器完成(比如R0=R1+R2)。而超标量意味该机器的流水线是有“分支”的，2个分支能“同时”完成计算并写回公共的R0~R7寄存器，这种分支流水线通常是每个分支有自己独立的ALU等硬件。 该机器执行算术指令的时序是这样，如在第n周期译码，则在第n+1周期开始执行，加减在第n+2周期结束时把结果写入寄存器，乘法则要多占1个周期。比如第k周期发射2个加法指令，如寄存器不冲突，第k+2周期结束时，和就分别在2个寄存器里。译码器能在1个周期里译码和发射指令，也可之后发射。… 阅读全文
滚动至顶部