NonTrivialMIPS - 十级双发射顺序MIPS32处理器

前一段时间我和几个同学参加了名为“龙芯杯”的比赛,这个比赛是自己设计一个CPU,在其上设计SoC,运行操作系统等… 是一个系统类的比赛。我主要负责写CPU除Cache外的部分,我们最终设计了一个有十级流水的双发射顺序执行的MIPS32处理器。在龙芯的实验板上达到了123MHz的主频,同时还具有较高的IPC。代码现在已经在 github 上开源:https://github.com/trivialmips/nontrivial-mips

我来说说这个流水线的设计,除去各种数据旁路,流水线的架构大约如下图NonTrivialMIPS CPU

这十级流水基本上是从标准的五级流水扩展而来,其中有3级的取指,2级的发射,3级的访存。其实我们最开始计划的是双发射乱序处理器,并且之前在组成原理课上有一部分顺序双发射的经验,当时有一个很麻烦的地方就是取指阶段,这里需要根据到底发射一条指令还是两条指令控制PC的增加,但是在决定下一个PC值时所需要的指令还没有取到,这就需要一部分预测和旁路,导致取指阶段很复杂并且容易写错。具体可以参考我当时的计原报告

  Report of TrivialMIPS (588.0 KiB, 705 hits)

这次我基本上重写了整个CPU,在取指阶段增加了一个FIFO,把取到的指令放入FIFO。之后在发射的时候从FIFO读取指令。这样一定程度上将取指和之后的执行等阶段进行了解耦。取指有3级流水基本上是由于指令Cache的需要。由于分支要在较后才能解析,CPU必然需要一个分支预测器,我实现的是2bit的分支预测。假设分支预测完全正确的情况下,可以保证放入FIFO的指令流就是执行所需要的指令流(当然这里也处理了延迟槽)。同时,为了支持双发射,我们的指令Cache一次可以取出8字节的数据,如果其后的8字节仍然在同一个Cache行内,也会一并取出。这是为了在预测到分支指令的之后能够尽早将延迟槽放入FIFO而不需要进行一次多余的取指。也就是,我们的FIFO在一个周期最多可以放入3条指令。

在之后发射阶段,为了频率的提高,我们将读操作数单独作为一个流水段。虽然这样会造成分支预测失败的损失增大进而减小IPC,但是和频率的提升相比这部分的损失还是比较小的。双发射基本上是对称的,只要不存在数据冲突和结构冲突(例如两条除法指令或者两条访存指令)都可以同时发射。当然,为了设计简便,我额外增加了一个限制,也就是分支指令和延迟槽必须一起发射。发射之后的读操作数和执行就没有太多技术含量,和通常的五级流水线相同。我们的异常处理和CP0的读写都是在执行之后的一个阶段,也就是访存的第一个阶段进行的。

在这里有一个很严重的问题就是,由于数据Cache的流水太常,导致访存相关(即访存后立即使用数据)的暂停很高,这极大影响了性能。为了缓解这个问题,我们允许部分指令的读操作数和执行延迟到访存阶段进行。这样就可以很大地减小访存暂停。当然不是所有指令都能做到这件事,首先这需要满足一些条件。其一就是这类指令不能是访存指令,其二是这类指令不能在执行阶段出现异常(取指的TLB miss还是可以的,这在它执行前就可以判断)。当然,这两个条件其实不是很严格,很大一部分程序访存后基本上是跟着一些ALU指令或者分支指令。在增加这个优化之后,整个处理器的IPC大约有了15%的提升,同时频率仍然保持。其实我们或许还可以进一步优化,对于非分支指令还可以将其延迟到访存的第二个阶段读操作数,这样就完全不会有访存相关。至于分支指令,我们必须要能够在分支预测失败时撤销其后的指令,流水线上能够影响处理器状态的第一个阶段就是访存的第一个阶段,因此分支指令最迟必须要在访存第二个阶段执行完成。不过我并没有实现这个优化。另外还有一个较小的优化,对于存储指令的数据,可以在执行阶段再读取。

除了执行操作系统所需要的指令以外,我们还做了一定的扩展,例如实现了一个32位的FPU以及一个硬件AES加速单元同时移植到OpenSSL上。MIPS32在早期版本对单精度浮点的规范非常奇怪,有两条指令叫做ldc1和sdc1,它允许同时两个FPU寄存器和内存交换数据,也就是一次访存的数据宽度是64位。我实现的方法是在发射阶段将其拆开成为两条32位的访存指令,同时不允许中断打断这两条指令。至于AES加速,实际上是在CP2上实现的。只用到了mfc2和mtc2两条指令,AES单元具有自己的寄存器,通过这两条指令和CPU的寄存器进行数据的交互以及控制。

至于操作系统和SoC的内容,这就不是我负责的范围了,具体可以看看我们最后的报告 https://github.com/trivialmips/nontrivial-mips/tree/master/report.

其实实现的过程中还有一个乱序的版本,不过最后因为频率没法提升最终没有使用。

TrivialDB - 一个简单的SQL引擎

TrivialDB是一个简单的数据库管理系统,我们实现了大部分常见的SQL语句和类型。同时支持多表连接、复杂表达式运算、多主键约束、外键约束、CHECK约束、UNIQUE和DEFAULT约束、聚集查询、利用B+树索引的查询优化,同时,我们支持任意长度的VARCHAR类型。

项目地址是 https://github.com/miskcoo/TrivialDB,这是这学期一门课程的大作业。

编译及运行

你需要有支持C++11特性的编译器,以及Bison和Flex两个库。本项目通过CMake来构建,在根目录运行

进行编译选项的设置,之后运行

进行项目的编译,编译后的可执行程序在build/trivial_db目录下。

编译后可以选择在testcase目录下运行python3 run_test.py运行测试程序。

系统功能

数据类型

数据库支持的基本类型有:

  • 整型(INT)
  • 浮点型(FLOAT)
  • 字符串型(VARCHAR)
  • 日期型(DATE),日期格式YYYY-MM-dd

日期类型的字面值和字符串相同,在实现中如果必要可以转换为字符串。

SQL语句

我们支持的SQL语句一共有如下几种

  • 插入语句:INSERT INTO ... VALUES ...
  • 删除语句:DELETE FROM ... WHERE ...
  • 查询语句:SELECT ... FROM ... WHERE ...
  • 更新语句:UPDATE ... SET ... WHERE ...
  • 创建数据库:CREATE DATABASE ...
  • 删除数据库:DROP DATABASE ...
  • 切换数据库:USE ...
  • 显示数据库信息:SHOW DATABASE ...
  • 创建表:CREATE TABLE ...
  • 删除表:DROP TABLE ...
  • 显示表信息:SHOW TABLE ...
  • 创建索引:CREATE INDEX ...
  • 删除索引:DROP INDEX ...

复杂表达式处理

表达式大致可以分为两种:算术表达式和条件表达式。由于采用Bison进行解析,可以支持任意深度嵌套的复杂表达式。我们所支持的基本运算主要如下

  • 四则运算,针对整数和浮点数进行。
  • 比较运算符,即<=, <, =, >, >=, <>。
  • 模糊匹配运算符,即LIKE,其实现采用C++11的正则表达式库。
  • 范围匹配运算符,即IN,可以在表的CHECK约束中以及WHERE子句中使用。
  • 空值判定运算符,即IS NULL和IS NOT NULL两种。
  • 逻辑运算,包含NOT、AND和OR三种。

以下是一些复杂表达式运算的例子

聚集查询

我们实现了五种聚集查询函数COUNT、SUM、AVG、MIN和MAX。其中COUNT不支持DISTINCT关键字。例如

属性完整性约束

我们支持多种属性完整性约束,分别是

  • 主键约束。一个表可以有多个列联合起来作为主键,只有在所有主键都相同时才认为两条记录有冲突,即这种情况下主键是一个元组。
  • 外键约束,每个域都可以有外键约束,引用另外一个表的主键。
  • UNIQUE约束,该约束限制某一列的值不能重复。
  • NOT NULL约束,该约束限制某一列不能有空值。
  • DEFAULT约束,该约束可以在INSERT语句不指定值是给某列赋予一个默认值。
  • CHECK约束,该约束可以对表中元素的值添加条件表达式的检查。

下面是一个简单的例子,注意如果在多个列都指定了PRIMARY KEY,那么就认为主键是一个元组,而不是有多个主键。例如Infos表的主键为(PersonID, InfoID)。

多表连接查询

在SELECT语句中,我们支持任意多表的连接操作,例如

并且,对于多个表的连接中形如A.Col1 = B.Col2的条件,那么如果这两个列的某一个拥有索引,会利用索引进行查询优化。例如如下查询就可以优化

具体的优化方法以及何种查询可以优化见文档中"查询优化"部分。

表别名

我们在多表连接查询时支持通过别名(alias)的方式对一个表进行连接,例如

FPGA Console——硬件实现的VT220兼容终端

这是和@HarryChen在这学期数字逻辑课上做的项目。主要是利用FPGA模拟一个终端。项目放在https://github.com/miskcoo/fpga-virtual-console上。

现在大部分的操作系统都是内置有虚拟终端,就像Linux下的xterm、gnome-terminal。但是,在最初控制台和计算机是相互独立的。控制台一般是由键盘和屏幕组成,键盘将用户输入传入计算机,计算机将输出发送显示给用户。这整个通信的过程是有一套标准来规定的,例如VT100就是一个早期的标准,更进一步有VT220、xterm-256color等。由于计算机回显的数据并不是单纯地整个屏幕的像素数据,而是更高层次的类似控制命令的内容,例如表示光标移动到某个位置,在某个位置插入某个字符,删除某一行的字符等。这些标准主要是定义了计算机发送回的这些控制命令的行为,和键盘发送给计算机的控制命令的行为。

我们做的这个项目就是一个物理上的终端!通过FPGA接受键盘的输入,将输入转化为控制命令通过串口输出给计算机。同时也通过串口接受计算机传回的控制命令名且解析、执行,修改对应位置的字符,再将字符进行渲染通过VGA输出到屏幕。

主要支持的标准是VT220,以及xterm-256color下大部分影响最终显示效果的指令,对于大部分linux下的程序的输出都可以正确地解析。同时串口速度提升到了3M可以支持以大约170fps的帧率播放黑白字符视屏,和约30fps的帧率播放彩色字符视屏。简单来说,就是正常终端可以做的事情这个物理终端都可以做到。

比如下面就是一个调用笔记本上摄像头的例子(我真的不是直接把VGA连到电脑上了),这时候串口速度还没那么快所以看起来有点卡……

fpga-camera

具体的细节我就不打算说了,文档里都写得非常明白。

https://github.com/miskcoo/fpga-virtual-console/raw/v1.0/doc/report.pdf

程序设计训练 - 数独、国际跳棋、人物信息检索系统

这次程序设计训练小学期一共有三个大作业,分别是数独、在线国际跳棋和人物信息检索系统。这里是简单的一些介绍,代码放在 https://github.com/miskcoo/programming-training

Week 1: Sudoku Game

简介

Sudoku 是一款利用 Qt 实现的数独游戏,提供了多达 10 个难度的关卡选择,同时还有丰富的功能来帮助玩家更加高效地求解数独问题,例如候选数、高亮相同数字、高亮选中的行列、撤销当前操作以及提示等功能。玩家还可以手动输入数独题目利用 Sudoku 帮助求解。

除了传统 9x9 的数独游戏以外,还提供了更高难度的 16x16 的数独游戏。

基本功能

Sudoku提供了多个方便的按钮:

  • 新游戏:玩家可以开始一局新的游戏。
  • 重玩:玩家可以重新开始本局游戏。
  • 暂停:玩家可以暂停该局游戏(即暂停计时)。
  • 提示:如果当前已经确定的数都是正确的,玩家将会得到一个未填空格的正确数字;如果当前已经确定的数和答案矛盾,导致整个数独无解,那么所有与答案矛盾的数字将会被粗体标出。
  • 清除:清除当前选中格子的所有数字。
  • 撤销:撤销前一步的操作,以及取消撤销(最多可支持 50 步撤销)。

同时可以通过菜单来实现多达 10 种难度的游戏选择,可以求解任意用户输入的数独问题。

玩家在空格中填入的数字分为确定数(采用正常大小的字体表示)以及候选数(采用小号字体表示)。确定数只能存在一个,候选数可以存在多个,并且确定数和候选数不能同时存在。

玩家可以通过多种方式进行格子的选择:

  • 鼠标直接点击格子进行选中。
  • 键盘方向键来进行当前选中格子的切换。
  • Tab键快速切换到下一个格子。

玩家可以用鼠标右键点击格子来对其进行标记。

玩家在选中一个格子之后,如果该格子的数字已经确定,那么所有与该数相同的数将会被加粗显示,以方便确认是否满足数独的条件。同时,所有与该格在相同行或列的格子都会被高亮显示。此外,无论该格子数字确定与否,右侧数字列表中该格子的所有数都会被加粗。

玩家可以通过多种方式在空格中填入数字:

  • 键盘直接输入数字将填入对应的确定数,如果 Ctrl 键被按下,那么填入的将会是候选数。
  • 鼠标点击右侧数字列表填入。使用鼠标左键点击将会填入确定数,右键点击则会填入候选数。

玩家也可以通过多种方式在空格中填入数字:

  • 键盘删除键删除格子中的一个数字。
  • 鼠标点击右侧数字列表已经选中的数进行删除。
  • “清除”功能键来清除该格子所有的数字。

Read More

较短步数复原魔方的算法

这其实是我们上学期徐 BOSS 程设课的一个大作业,我本来很早就想把它记录下来了,可是实在太懒了加上拖延症严重于是就拖到了这个学期。本来作业是要求复原魔方就好了,但是后来发现没有图形界面的话似乎调试很困难,就顺便写了一个 UI,刚好还学了一下 OpenGL。最开始我是写了能够找到最优解的 Krof 算法,但是估计是我写得比较丑再加上状态空间实在太大了(大约在搜索到第 15 步还是 16 步的时候状态数就到百亿级别了,而我 8 个线程一秒只能搜几千万个状态好像),根本没有办法在可以接受的时间内得到解。于是退而求其次,改为去搜索一个比较优的解,最后基本上一秒以内就可以得到解了。

整个工程的代码我放在了我的 Github 上:https://github.com/miskcoo/rubik-cube

魔方的表示

如何表示一个魔方呢?一个很直接的方法就是用六个面一共 54 个色块来表示它,我在最开始写的时候就是用这种方法来表示一个魔方的,但是这样存在着很多的冗余。事实上,我们可以按照魔方的各个棱块和角块的位置和方向来存储。对于魔方的一个角块来说,我们只需要存储这个块在 8 个角的哪一个地方以及它的方向如何(关于方向接下来会进行规定)。对于棱块来说也是相同的,只需要位置和方向就可以决定了。

角块方向的表示

首先对于一个角块来说它可能会有 3 个不同的方向(如下图,暂不考虑这个魔方是否合法,仅关注角块)

corner-0corner-2

想象一下,从左到右相当于单独把面对我们的这个角块(按照从魔方中心指向该角块顶点的向量)旋转了两次。我们可以按照这样来规定角块的方向:首先将对应角块像上图中一样面对我们,并且以绿色或蓝色作为顶面。现在以绿色或蓝色作为参照色(因为一个角块有且仅有这两种颜色之一)。现在来规定角块的方向:

  • 如果参照色位置在如同第一张图一样的位置,就规定方向为 0
  • 如果参照色位置在如同第二张图一样的位置,就规定方向为 1
  • 否则就规定方向为 2

棱块方向的表示

对于棱块方向的规定就稍微有些复杂了,因为没有办法像角块这样找到对立的两个面使得每个棱都包含这两种颜色之一。那么对于棱块的参照色我们规定:如果一个棱存在蓝色或绿色,则该颜色为参照色,否则白色或者黄色为参照色。规定了参照色之后就可以规定棱块的方向了:

  • 如果棱块位于顶层或者底层(也就是绿色或者蓝色面所在的层),那么当参照色在这两个面中的一个时方向为 0,否则为 1
  • 如果棱块位于中间层,那么当参照色在白色或者黄色面时方向为 0,否则为 1

edge-0edge-1

在第一张图中,两个棱块的方向都是 0。这是因为对于红白色棱块,白色为参照色并且其位于顶层绿色面;对于绿白色棱块,绿色为参照色并且位于中层白色面。

在第二张图中,两个棱块的方向都是 1。原因与之前的刚好相反。

Kociemba 算法

首先我们规定一种魔方的中间状态:仅仅通过 U、D、L2、R2、F2、B2 这几种旋转就可以将魔方复原的状态。也就是不允许 90^\circ 地旋转魔方的前后左右这四个面。这种状态有什么特点呢?

首先很明显可以观察到按照我们刚刚规定的方向,旋转顶面和底面都是不会改变棱块和角块的方向的,并且仅按照 180^\circ 来旋转周围四个面也是不会改变棱块和角块的方向。那也就是说,在这种中间状态下,魔方的棱块和角块的方向应该都是 0,这是因为目标状态的魔方如此。除此之外,魔方中间层的四个棱块必然也在中间层。

可以简单地计算出这种中间状态一共只有 8! \times 8! \times 4! = 3.9 \times 10^{10} 种可能,事实证明,在不超过 18 步以内就可以从这种状态复原魔方。我们用 IDA* 来进行搜索,当我们设计启发函数的时候分别针对角块(一共 8! 种可能)、顶层和底层的棱块(一共 8! 种可能)、中间层的棱块(一共 4! 种可能)计算复原它们所需要的最少步数(这可以直接进行搜索),之后的启发函数就是这三者的最大值。

剩下的问题就是如何将魔方旋转到中间状态,我们同样采用 IDA* 来进行搜索。对于启发函数,分别针对角块的方向(一共 3^8 种可能)、棱块的方向(一共 2^8 种可能)、中间层棱块的位置及方向(一共 A^4_{12}\times 2^4 种可能)计算复原它们所需要的最少步数。经过计算,不超过 12 步就可以将一个魔方旋转到中间状态。这样总共在不超过 30 步的情况下就可以复原一个魔方了!

刚刚的状态表示方式在这个算法里显示出了很大的优势,在进行 Hash 的时候可以直接使用这个状态表示,而不必从其它表示方法(例如存储 54 个面的方法)计算出棱和角的方向。事实证明,在通常情况下,这个算法很快就能够复原一个魔方。

Krof 算法

这个算法就是我前面说的搜索最优解的算法,思路和 Kociemba 算法几乎一样,不过 Krof 算法没有划分阶段,启发函数是分别对于角块的方向和位置(一共 8!\times3^7 种可能)、两组每组 6 个梭块的位置和方向(每组都是 A^6_{12}\times2^6 种可能)计算复原它们所需要的最少步数。由于这个启发函数的计算也是十分耗时的,所以可以先计算一次之后记录下来之后直接读取就可以了,而前面 Kociemba 算法的启发函数可以现场计算。

上帝的指纹——Mandelbrot集合的绘制

322px-mandel_zoom_00_mandelbrot_set

曼德博集合(Mandelbrot Set)是一个在复平面上的点集。有人认为 Mandelbrot 集合是“人类有史以来做出的最奇异、最瑰丽的几何图形”,曾被称为“上帝的指纹”。

Mandelbrot 集合是一个分形(fractal),将它无限放大都能够有精妙的细节在内,而这瑰丽的图案仅仅由一个简单的公式生成。

Mandelbrot 集合的定义是由法国数学家 Adrien Douady 做出的,而它的命名则是为了纪念被称为“分形学之父”的 Benoit Mandelbrot。

在计算机出现后,对于分形的绘制成为了可能。在这篇文章中,我会介绍如何用 C++ 以及高精度库 MPFR 绘制 Mandelbrot 集合,以及对图像色彩渲染的一些方法。

具体代码可以参考 https://github.com/miskcoo/mandelbrot-render

Read More

列表、字符串及字典——Python基本数据结构

Python 的强大之处就在于它有丰富的库以及各种方便的特性。这篇文章将会介绍 Python 中的几个内置类型——列表、元组、字符串及字典。

我是按照 Python3 来介绍,如果和 Python2 有不同的地方会特别指出的。并且,文中的代码如果有输出的部分,都是按照 Python3 语法进行。另外,如果代码中是以 >>> 开头的,就说明这段代码是我直接在交互模式下运行的,并且包含了输出。

List——列表类型

首先,我们来介绍列表类型。什么是列表呢?你可以认为列表是多个变量的集合,并且这个集合是有序的。你在以前遇到的类型可能都只是涉及单个元素,比如说 intfloat 之类的,这都只涉及了一个数字。但是列表不同,它可以用一个变量存储多个元素,如果你了解过其它语言,列表和数组是十分类似的。

一个列表是用一个方括号包围的,列表中的元素使用逗号分隔,例如下面这几个变量都是一个列表:

值得注意的是,一个列表可以不包含任何元素,就像变量 c 存储的列表一样,这样的列表叫做空列表

另外,一个列表内的元素不一定要有相同的类型,甚至列表本身也可以作为元素存储在一个列表中:

比如说上面第一个列表,它存储着三个不同类型的元素,一个是整数,一个是浮点数,另外一个是字符串。

至于第二个列表,它包含四个元素,第一个元素是一个整数 233 ,第二个元素是先前的列表 x ,第三个元素是一个空列表 [] ,最后一个元素是另外一个仅包含一个字符串作为元素的列表。

Read More

BZOJ-3695. 滑行

这是 2014 年福建省省队训练的时候首长出的一道题,然后听完讲评后整个人就不好了,题目大概是这样的

首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题

现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的区域内部有一个不同的速度上限

小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)

地面上有 N 层区域,每层区域都是矩形,现在给你一个序列 \{H_i\} 表示每层区域的高度,覆盖的地面横坐标范围是 0~X,第i个区域的限速是 v_i

注: Y=\sum_{i=1}^nH_i,其它的地方小滑块不允许进入

现在我们要设计一个路线使得小滑块滑到目标点的用时最小

如果你知道两个物理学的定理(光的最速原理、折射定律),那么这题就可以很快解出来了

Read More

NOI2012. 迷失游乐园

放假了,小Z觉得呆在家里特别无聊,于是决定一个人去游乐园玩

进入游乐园后,小Z看了看游乐园的地图,发现可以将游乐园抽象成有n个景点、m条道路的无向连通图,且该图中至多有一个环(即 m 只可能等于 n 或者 n-1,并且环上节点个数不超过 25 个)。小Z现在所在的大门也正好是一个景点

小Z不知道什么好玩,于是他决定,从当前位置出发,每次随机去一个和当前景点有道路相连的景点,并且同一个景点不去两次(包括起始景点)。贪玩的小Z会一直游玩,直到当前景点的相邻景点都已经访问过为止。小Z所有经过的景点按顺序构成一条非重复路径,他想知道这条路径的期望长度是多少?

小Z把游乐园的抽象地图画下来带回了家,可是忘了标哪个点是大门,他只好假设每个景点都可能是大门(即每个景点作为起始点的概率是一样的)

同时,他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点

Read More