Yuchen You

SRAM, DRAM, SSD SRAM 静态随机访问内存 由六个三极管组成 脆弱volatile：需要常量的电压来保存数据 快速: 1ns 左右的数据访问时间 空间占用率低: 只能在芯片上存储 MB 大小的数据 DRAM 动态随机访问内存 每一个 bit 用一个 三极管和一个电容组成 需要常量的电压来保存数据 缓慢: 大约 50 ns 的访问时间 便宜，可以提供 GB 单位的内存空间 现代硬件结构中这个往往被用作是主要内存硬盘 Disk 光盘 硬件将数据存储在 磁电,通过光盘的旋转来进行数据获取 数据获取非常缓慢，约 3ms 的访问时间 不脆弱：即使没有电压也可以保存数据 固态硬盘 solid-state disk, SSD 相比光盘，访问时间快很多，大约 0.1 ms 的时间 十分便宜 总结 reg, cache, memory 的速度和内存大小的关系如下图: 缓存 Caches 功能 缓存存储了我们认为最有可能会被使用的数据, 从时间和空间维度，共有两种可能： 空间(spatial locality)：最近被调用的数据的附近更有可能会被调用 时间(temp ...

NP-hard 定义 一个语言 LLL 是 NP-hard 若对任意 NP 中的语言 X 存在关系 X≤pLX\le_p LX≤p​L 定义这个关系为：at least as hard as 并不要求 NP-hard 问题属于 NP NP-complete 定义语言 LLL 是 NP-complete 的如果 1. L∈L\inL∈ NP 且 2. L∈L\inL∈ NP-hard 从简单上来认识这个 class，可以理解为这是最难解决的 NP 问题 NP-hard 的复杂度性质 如果对于任何一个 NP-hard 的问题，存在一个 多项式复杂度的解 那么任何 NP 问题都可以在 P 时间内解决 因此有两种可能性: NP-complete 问题全部都属于 P NP-complete 问题全部需要超过 多项式时间复杂度的求解难度 NP-hard reduction 定义符号 ≤p\le_p≤p​ 使得 A≤pB⇔A\le_p B \LeftrightarrowA≤p​B⇔ ∃f\exists f∃f 多项式函数 s.t. x∈A⇔f(x)∈Bx\in A \Leftrightarrow ...

P 类 多项式可解类 定义 P class:= 所有的 decidable 的 problem 中可以在多项式中决定的集合 即若有 L∈PL\in PL∈P, 那么就会存在图灵机 MMM decides LLL, 且 MMM 的时间复杂度是 O(nk)O(n^k)O(nk) 难以解决的问题-例: traveling salesperson problem (TSP) 旅行商问题 在一个图中，是否存在一条路径经过每个点一次且路径权值和小于常数 b ? 这个问题的求解步骤或许非常麻烦，但是当我们提出一种解之后，我们很容易就可以根据定义来进行验证其真伪，我们称这类容易验证的问题为 efficiently verifiable 其他难解决易证明问题 走迷宫问题、数独求解问题 证明属于 P 类 证明属于 decidable 问题 (用伪代码定义图灵机的存在, 需要证明 correctness) 证明过程可以在 O(nk)O(n^k)O(nk) 时间内停止，这里 nnn 表示 input size NP 类 多项式可验证类 定义 NP class := 所有的能在多项式时间内验证一个问题的真 ...

目的 可以压缩执行时间，从单循环的长周期短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 为了方便浮点数的运算，我们需要将小数点的位置规整化，类似于科学计数法，我们只将位数 ...