10.8

#diary #2025/10

重拾笔墨

鸽了好久好久的日记，这是继 10.2 以来的第一篇日记。

步伐不会停止

自开学以来，坚持每日 3km （以及坚持按时下楼三餐）可以说是保持得最好的生活习惯了，十分出人意料。

从另一个意义上来说，CSAPP 的 lab 部分基本完结。前天花了 8h 写完了 cache lab，今天花了 4h 写完了 shell lab，和其他贵物相比，shell lab 属实是路边一条了。只剩下 malloc lab 和 19 年新加的 proxy lab：proxy lab 和 Web Server 有关可以等到学完计算机网络再来写；malloc lab 的任务是完成一个 allocator，实现 C 的 malloc/realloc/free 三个功能，追求最大化空间利用率和时间效率。鉴于该部分属于内存性能优化的一个专题，不具备 cache lab 中缓存分析对于程序性能提升或者 shell lab 那样对 shell 作为常用工具的理解提升的普遍性，所以可以一定程度上推延。（某种程度上为自己的懒惰找了一个看起来相当花里胡哨的理由）所以这意味着可以开启新的课题的学习了！学习的铁蹄将踏向数理逻辑。

Cache Lab

接下来对 cache lab 做简要评价。cache lab 的目标是

• 实现一个 cache simulator。只涉及单层缓存的逻辑。只涉及加载的逻辑，不涉及写入 write-back/write-through 的逻辑。conflict replacement strategy 是 Least-Rencently-Used，而现代缓存的 conflict replacement strategy 一般是伪 LRU
• 在 s = 5, E = 1, b = 5 的 cache 下优化 $32\times 32,64\times 64,61\times 67$ 的 int 矩阵的转置，要求最小化 cache miss 次数。注意到 E = 1 意味着 Direct-Mapped Cache，所以存在一定局限性。另外 cache miss 次数并不完全等价于运行性能，在 $64\times 64$ 的处理中采取了用两倍的指令数来换取 cache miss 的减少，在实际问题中需要权衡。

简述解法

• $32\times 32$：分析缓存行的大小，采用 $8\times 8$ 的 tiling 使得对于单个矩阵来说 tile 内恰好不发生 cache conflict；在复制元素时，先将 A 一行的元素全部取到 register 中再复制到 B 可以减少对角线上的 A B 之间的 cache confict。
• $64\times 64$：要使 tile 内恰好不发生 cache conflict 需要 $4\times 4$ tiling，但是这样 A 的单个缓存行的数据利用率从 100% 降低到 50%。维持 $8\times 8$ 保证 A 的缓存行 100% 利用率，此时在 A 复制第 1-4 行 5-8 列时需要加载的 B 第 5-8 行与 B 第 1-4 行冲突，考虑先将需要复制到 B 第 5-8 行 1-4 列的数据暂时储存在位于缓存内 B 的第 1-4 行 5-8 列，当 A 复制第 5-8 行时，依次取出暂存的元素然后丢弃 B 的第 i 行而加载 i + 4 行。本质是充分利用了缓存行中无需读取/写入的部分作为额外的 cache 来加速数据访问，这要求被利用的缓存行的丢弃时间晚于额外数据访问需求的结束时间。
• $61\times 67$：十分抽象，尝试理性分析了一波没有从混沌的元素排列得出任何有意义的结论。直接看答案发现答案也很离谱，思路是暴力分块，枚举分块大小选择性能最好的一个。性能最好的分块大小为 17/16 是无法理解的。

Shell Lab

需要补全的机制包括

• 基本的循环，某一时刻可以有若干个 background job 运行/停止，foreground 要么等待用户输入 command 然后 parse, evaluate，要么在与运行的 foreground job 交互（waitfg）。
• jobs 机制：built-in command fg/bg 对 bg job 发送 SIGCONT 并分别移入 foreground/background
• Ctrl-C Ctrl-Z 对 foreground job 传递信号 SIGINT/SIGTSTP
• Reap Child：正常 terminated、被未捕获的 signal terminated 的 process 删除 job 并打印相关信息；被 stop 的 process 将 job 的状态置为 stopped（注意如果是 foreground job 则会停止 shell 的交互并移入 bg）

不支持

• 丰富的 built-in command
• 工作目录
• 环境变量操作
• pipe
• IO redirection
• sub shell
• command history/auto completion/alias
• conditional/loop/function
• glob/arithmetic operation/command substitution/string operation
• config

解构数理逻辑的第一步

数理逻辑分为五个子版块：基础逻辑、证明论、公理集合论、模型论、递归论

这两天胡乱地看了几本涉及数理逻辑教材

• 石纯一 数理逻辑与集合论。这本书就是史，解释极少（初学者不优化），牵强的应用，看似什么都有实际上有深度的部分都一笔掠过（比如命题逻辑的公理化）。
• Kenneth H. Rosen Discrete Math and its Application，通俗易懂，不过太浅了。
• Enderton H. B. A Mathematical Introdution to Logic，神书。

前两本书并没有很好地满足我期望的学习效果，只粗略地看完了命题逻辑和谓词逻辑。现在转到了第三本书

Mathematical Introdution to Logic 第一章将 Sentential Logic（Propositional Logic） 视为一种语言，首先从字符串出发先从形式上构建了 Well-Formed Formula，此时 wff 还没有赋予意义，接着通过 Induction/Recursion 从一组 Truth Assignment 出发为所有 Well-Formed Formula 都赋予了含义，接着又从 Well-Formed Formula 建立了到 Boolean Function 的一一映射，为研究 wff 被赋予的含义的性质提供了有力的工具。最后证明了紧致性定理并不严谨地分析了有效性，不过紧致性定理的意义暂时不明朗。

由于学习路线尚不明朗，只能制定初步的计划：花费一周的时间，学到哥德尔不完备性定理。

部落冲突突突突突

时间都去哪了？部落冲突最近更新匹配赛制分为常规赛和排位赛制，这使得常规赛的体验较之前而言大幅提升。常规赛几乎能把把三星，打起来十分令人满足，即使资源打满了还想打，另外还有 8 次排位的进攻机会，部落联赛，夜世界打资源（终于速到 10 本了），消耗了不少时间。本来打算今晚写 malloc lab 的，结果玩累了之后直接睡到 11 点，跑完步回来之后没忍住又玩了一会，真是一个美好的夜晚~。另外，正值月初刚冲月卡，为了达到效益最大化，需要花费一些额外的精力。

研究了一下雷龙的连锁机制、大守护者的跟随机制，新摆了一个防雷龙的阵。

为什么这篇日记写了一个多小时？？？