Yuchen You

目的 可以压缩执行时间，从单循环的长周期短cpi和多循环的短周期长cpi结合得到 短周期 + 短 cpi (等于 多循环的cpi) 特点 在 multi-cycle 的电路基础上，添加一个 对应每个 stage 的寄存器, 一共四个 最大同时执行指令的次数: 5 (即 if, id, ex, mem, wb 各一个同时进行) 总 cycle 数 instr 数 + pipeline_stage 数 - 1 pipeline 问题 data hazard data dependency: 指令依赖于前面某个指令的结果 data hazard: 一个指令如果不进行额外处理就会遇到错误情况 解决方案 代码主动避免 avoid 检测与贮存 (处理器主动等待) detect and stall 自动修复为标准值 detect and forward 1. 代码主动避免 加入 noop 轮空 cycle 问题 硬件版本不同需要的 noop 数量不同 (新的硬件可能 pipeline 更长，需要的noop会变) 程序体变大很多 执行速度变慢 2. 检测与贮存 Detect and Sta ...

选择器 mux 在逻辑电路中，我们经常会需要选择使用哪个数据源(这里其实是比较 compare 逻辑)，所以我们会用到 mux 来完成, 其符号如下: 原理 这个逻辑可以用 与门 来完成 加法器 adder 已经在基本逻辑电路中解释过了，大致原理就是接收 进位位 Carrier, 输入位 a,b 通过逻辑演算得到 本位值以及进位位值 解码器 decoder 简单理解，就是将每一个输入根据其digit转为第n根线出high

常用的不可定中间语言 BARBER LBARBER={⟨M⟩:Mdoes not accept ⟨M⟩}L_{BARBER} = \{ \langle M \rangle : M \text{does not accept } \langle M \rangle \}LBARBER​={⟨M⟩:Mdoes not accept ⟨M⟩} HALT LHALT={(⟨M⟩,x):M halts on w}L_{HALT} = \{ (\langle M\rangle, x) : M \text{ halts on } w \}LHALT​={(⟨M⟩,x):M halts on w} ACC LACC={⟨M⟩:M accepts L(M)}L_{ACC} = \{ \langle M \rangle : M \text{ accepts } L(M) \}LACC​={⟨M⟩:M accepts L(M)} 单string停机问题 虽然不能解决通用停机问题，但是我们是否可以解决单string停机问题？即对于给定的一个string，判断一个特定的图灵机是否能停机。从简单的角度考虑，我 ...

罗素悖论 - 理发师悖论 Barber Paradox 一个小镇上的理发师，只给那些不给自己理头发的人理发 那么就会出现一个问题，如果这个理发师给自己理发（假设物理上做得到）那么他就违反了他的 slogan，因为他自己是理头发的人，他不能给理头发的人理头发 如果这个理发师不给自己理头发，那么他也违反了自己的slogan，他不给自己理头发但是他理应给自己理头发 图灵机的循环 由于我们知道图灵机能表述为一个 string (即用其的7元组进行各部分编码得)，那么我们是不是可以用另一个图灵机来处理这个图灵机？ 再根据理发师悖论，我们就有了一个很叛逆的图灵机： 图灵机 TM 只接受任意不接受任意自己描述的字符串的 TM1TM_1TM1​ 那么，这个特殊的 TM 可以接受其自身的描述字符串吗？ 很遗憾根据悖论，这里是不行的 可决定集合 假设我们有一个语言 LAccL_{Acc}LAcc​ 包含了所有的 tuple (⟨M⟩,x)(\langle M\rangle, x)(⟨M⟩,x), 其中 MMM 是一个 TM, xxx 是一个 string, 且 MMM 接受 xxx 这在生活中很常见：我们 ...

排序的分类 一般我们将排序能不能根据输入数组后能否优化处理的特性将排序算法分为两类 Non-Adaptive Sort: 不会根据输入数据的特性进行优化处理 Adaptive Sort: 会根据输入数据的特性进行优化处理 冒泡排序 bubble sort 用两个指针，逐个将相邻的两个节点大小进行比较，每次把最极端的值放到数组的某一边，然后下一层循环减小空间 时间复杂度 O(n2)O(n^2)O(n2) 空间复杂度 O(1)O(1)O(1) Adaptive 策略 如果在一次遍历中没有发生任何元素的交换，说明数组已经有序，可以提前结束排序 选择排序 selection Sort 每次遍历一个数组，找到最极端的值然后和边界值进行互换，再在剩下的空间完成剩余的排序 时间复杂度 O(n2)O(n^2)O(n2) 空间复杂度 O(1)O(1)O(1) Adaptive 策略 在极端值的时候，如果index和交换目标相同，那么就不交换 (这里其实基本上没有优化) 插入排序 insertion sort 对于一个正在构建的数组(数据流)，每到来一个元素我们都会需要将新变量插入到本来已经有 ...

对分查找 binary search 这个查找的前提是建立在数组有序的基础上，我们可以通过对分的位置判断分区，从而快速找到目标节点 一般只能返回是否找到目标节点，而不能返回其位置，我们应该使用 标准迭代器 lower_bound(), upper_bound() 进行坐标确定，其中 lower_bouund 能从右侧逼近最靠近目标元素的位置； upper_bound 能从最左侧逼近最靠近目标元素的位置 什么样的集合是方便查找的？ 从对分查找的经验里面我们可以知道，如果集合是有序的是很利于其查找的 但是很多时候我们会对一个集合进行操作，如何保持集合的有序性是一个很重要的问题 最直接的想法，是将两个数组用两个迭代器分别指向，然后比较将较小的值填充进新数组中。 但是，如果数组的同异集合性并不能通过数值来进行表示呢？ 例如，在生物图谱中，我们如何知道人类和鱼类是否有相近的基因？假设生物学已经构建了以人为中心和以鱼类为中心的两个集合图，然后假设某一天有科学家证明了这两个集合图中的某对元素(a∈a\ina∈ 人, b∈b\inb∈ 鱼) 存在近亲关系，那么我们就可以将这两个集合合并到一起了，但是， ...

单精度浮点数 float 浮点数在内存中的存储格式是 127 基偏差 方式 (base biased 127 encoding) 即将 -127 = 0x00000000 那么: 1 = 0x10000000 128 = 0x11111111 0 = 0x01111111 小数点的前后 对于十进制小数 10.625, 我们可以将整数部分分解为二进制: 1010 但是小数部分如何用二进制表示？ 类比十进制，小数点后一位是 10−110^{-1}10−1, 二进制小数点后一位是 2−12^{-1}2−1, 二进制小数点后二位是 2−22^{-2}2−2, 以此类推。 那么 .625 就可以理解为 0.5+0.125=2−1+2−3=0b0.1010.5 + 0.125 = 2^{-1} + 2^{-3} = 0b0.1010.5+0.125=2−1+2−3=0b0.101 因此整个小数就是 0b1010.1010b1010.1010b1010.101 = 10.625 正规化 normalization 为了方便浮点数的运算，我们需要将小数点的位置规整化，类似于科学计数法，我们只将位数 ...

背景 在编译 C 或者 C++ 文件的时候，我们都会用到链接这一步骤，即 预处理 - 编译 - 汇编 - 链接 四个步骤 我们已经学过了汇编了，那么接下来就该了解一下什么是 linking 了 什么是链接 在汇编中，我们一般是每一个 c/cpp 文件生成一个 汇编代码文件 (obj file, 扩展名 .o)，那么，如果存在跨文件的变量，汇编怎么知道这个变量是来自哪里的呢？ 首先我们联想在编译的时候 (compile time) 我们会在项目编译的内存空间中创建一个格式为 text - data - heap - stack 的空间结构(这里说的不恰当，应该说 compile time 分配的 text - data 空间)，那么类似的，对于每个源文件生成的汇编码，我们都要用一个表来记录全局变量的引用 cross−refcross-refcross−ref 以及外来方法 (即函数) 的对应引用 obj 文件的内容 上述两个表格会在编译的过程中存储在 .o 文件中，因此 obj 文件的格式会表现为: Header - Text - Data - Symbol Table - Reloc ...

排课问题 假设开学季的某一个下午多个社团都想要占用霍体开设招新活动，每个活动的时间长度各不相同且开始和结束的时间都各不相同，那么，学校方希望能尽可能多的开设活动，而并不考虑总活动时长的影响因素 最早结束时间算法 Earliest Ending Time EET 将这些活动按照时间结束的早晚进行排序，然后选中最前面那个，然后去除所有重叠的活动，然后递归选取下一个 选择的可靠性 (safe) 我们需要证明我们选择的这个活动确实是能带来最多活动数量的，或者用数学术语来说，存在最优解集 IOPTI_{OPT}IOPT​, 我们要证明 我们选择的 first ends I∈IOPTI \in I_{OPT}I∈IOPT​ 由于根据定义，结束时间 end(I)≤end(IOPT)end(I) \le end(I_{OPT})end(I)≤end(IOPT​) 那么由于 IOPTI_{OPT}IOPT​ 的下一个元素开始时间一定晚于当前的结束时间，所以 end(I)<start(IOPT,next)end(I) < start(I_{OPT, next})end(I)<start( ...

堆 我们将一棵树变得更加特别，即限制其必须为完整的，即每一个树的层级都是满的，除了最后一层。 然后，我们联想生活中的常见的堆型结构：稻草堆，其特征是上小下大，那么，我们就可以定义数据结构中堆的特性：具有一定的偏序关系(优先级)，且根节点的值总是该偏序关系的一端。 堆的节点关系 堆在内存中存储为一个 array 的形式，假设当前节点的 index 为 i (假设根节点 id = 1): 父节点 i / 2 左子节点 2i 右子节点 2i + 1 是否为叶节点 return (2 * i > n) 大顶堆的实现 fixUp() 当我们向一个堆进行插入元素操作，那么我们需要保证堆的特性，即根节点的值总是最大的。我们可以通过将新插入的元素与其父节点进行比较，如果新插入的元素大于其父节点，那么我们就将新插入的元素与其父节点进行交换，直到新插入的元素不再大于其父节点。 这个操作的结果是 将新的堆变成符合 父节点大于子节点的属性，且根节点一定是顺序最高的 fixDown() 当我们删除堆顶的元素的时候，我们需要将下面的元素逐个选择大的向上填充，那么我们就需要进行 fixDown() 操作， ...