00:05:00 在这一节中，讲师讲了两种存储方式：栈和堆。栈是一种固定大小的存储，效率高但不能用于所有事情，而堆更通用但难以高效组织和使用。对于堆分配，可以使用 malloc 和 free C 函数，但由于 C 和 C++ 不提供垃圾收集器，程序员必须自己管理内存，这会导致内存泄漏、悬垂指针和双重释放。讲师建议使用地址清理器和 Valgrind 等内存检查器来减少程序中的内存错误数量。
00:15:00 在本节中，介绍了外部碎片的概念，当使用的内存块散布在所有内存空间时，就会发生这种情况。这会导致更大的页表，从而导致磁盘抖动并降低查找翻译的效率。为了减轻外部碎片，可以使用每个磁盘页面的空闲列表或位图，并且可以从最满的页面进行分配、释放故事块和调出空页面。固定大小的堆分配也可用于减少外部碎片。最后，可变大小的堆分配可以与 bin 空闲列表一起使用，它针对不同大小的已分配内存利用空闲列表的效率。
00:20:00 在本节中，介绍了一种在内存分配系统中存储不同大小的内存块的方案。该方案涉及根据块的大小将块分成 bin，每个 bin 包含指定大小的块，这些块是 2 的幂。分配内存时，根据请求的大小选择合适的bin，如果为空，则将较大的非空bin拆分成较小的块以获得所需的大小。但是，这种方案会导致内存内部碎片化，造成浪费，因此限制使用的bin数量，将小块分组到页中以减少开销。如果需要，操作系统可用于提供更多内存，并且有系统调用可用于此目的。
00:30:00 在本节中，讨论了虚拟内存的碎片问题，如果内存分散，它可能导致外部碎片、页表性能下降、磁盘抖动和 TLB 命中率低。存储分配的目标是使用尽可能少的虚拟内存，同时保持已使用的内存部分紧凑。分析了 bin free list 分配方案，有一个定理表明堆存储消耗的虚拟内存量上限为 M log M。将较小的块合并为较大的块可以改进 bin free list 方案，但开销根据 Charles Leiserson 的一篇论文，与标准 bin free list 算法相比，这种方法可能比最佳分配器差一个常数因子。
00:50:00 在本节中，视频介绍了处理碎片的“停止和复制”垃圾收集程序。此过程类似于标记和清除算法，但采用不同的方法来确保活动对象在内存中是连续的。该过程使用两个独立的内存空间——from 空间和 to 空间——并从 from 空间分配和释放对象，直到它变满。然后运行垃圾回收算法，将二次空间作为队列进行广度优先搜索，识别存活对象，在二次空间内存中连续放置。但是，使用此算法可能会导致正确性问题，即指向源空间中对象的指针可能不再正确。为了解决这个问题，该过程在源空间中的相应对象中存储一个转发指针，并在广度优先搜索中从队列中删除对象时，根据这些转发指针更新所有指针。
00:55:00 在本节中，演讲者讨论了停止和复制垃圾收集算法、其时间复杂度以及它如何处理外部碎片。停止和复制算法涉及将对象从 from 空间复制到 to 空间，然后更新 to 空间中这些对象的指针。这种算法在时间和空间上是线性的，这使得它成为一种更高效和有效的垃圾收集方式。当from空间变满时，用户可以请求一个新的堆空间并将from空间的大小加倍。该方案所需的虚拟内存空间为常数倍最优，该算法消除了外部碎片。
该视频讨论了各种内存分配策略及其权衡。解释了 malloc 和对齐分配的使用，以及使用 free 正确释放内存的重要性。还介绍了使用 Mmap 进行虚拟内存分配，以及外部碎片和性能低下的问题。探讨了 C 和 C++ 编程中堆栈的概念，重点放在用于分配堆栈帧的基于堆的仙人掌堆栈方法上，这可以带来更好的空间限制证明和上限。还讨论了线性堆栈池的使用，以及优化小块以最小化碎片的重要性。该视频最后讨论了全局和局部堆方法及其潜在问题，以及用于解决这些问题的 bin 空闲列表和定期内存重新平衡等方法。
该视频还讨论了并行存储分配的解决方案，并介绍了 Hoard 分配器作为解决方案。 Hoard 分配器结合使用本地和全局堆以及可以在堆之间移动的大型超级块，以减少错误共享、提高可伸缩性并减少外部碎片。全局堆中分配的最大存储最多是本地堆中分配的最大存储，占用空间上限为用户占用空间加上本地堆中已分配但未使用的存储空间。该视频还简要讨论了其他分配器，例如 Je malloc 和 Super malloc，基准测试结果表明 Super malloc 的性能优于 Je malloc 和 Hoard。讨论最后引用了有关垃圾收集详细信息的在线幻灯片。
00:15:00 在本节中，演讲者讨论了地址转换在现代机器中的工作原理，并深入探讨了 C 和 C++ 编程中堆栈的概念。堆栈用于跟踪函数调用和局部变量并遵循线性顺序。演讲者强调了传统线性堆栈中指针的一个规则：父级可以将指向其堆栈变量的指针向下传递给其子级，但不能反过来，以避免覆盖变量。演讲者还建议了一些选项，例如在堆上或在父级堆栈上分配内存，以便将内存从子函数传回父级。
00:25:00 在本节中，视频讨论了使用基于堆的仙人掌堆栈方法来分配堆栈帧，而不对最大深度设置上限。然而，当尝试将传统的线性堆栈代码与这个基于堆的仙人掌堆栈一起使用时，互操作性是一个问题。这可以使用一种称为线程局部内存映射的方法来解决，但这种方法需要更改操作系统。尽管如此，基于堆的仙人掌堆栈方法在实践中仍然很好，可以用来证明使用它的 Silk 程序的空间限制。这个空间限制表明，使用基于堆的仙人掌堆栈的 P worker 执行的堆栈空间上限为 P 乘以 s1，其中 s1 是串行执行 Silk 程序所需的堆栈空间。这是基于堆的仙人掌堆栈方法的一个很好的特性。
00:30:00 在本节中，分析了分治矩阵乘法代码，以了解如何将其应用于时空权衡定理。该代码进行了八次递归调用，每次调用的大小为 N/2，并且在每次调用之前，它执行 malloc 以获得大小为 N 平方的临时空间，然后在函数返回之前释放该空间。由于分配遵循堆栈规则，即使在堆外分配时，上一张幻灯片中的空间限制也可用于限制 P 工作空间。工作是 N 的立方，跨度是对数平方 N 的阶数。空间的递归是 N/2 的 s + N 平方的 theta，求解为 N 平方。因此，空间边界的忙叶性质和定理表明，在 P 个处理器上，空间的边界为 P 乘以 N 的平方。
00:35:00 在本节中，演讲者向听众介绍了如何为上一节中讨论的算法证明更强的空间界限。通过分析算法的结构并着重于在递归树顶部附近尽可能多地分支，演讲者能够证明 P 的空间界限为 N 平方的三分之一，这比之前的上限要好.演讲者指出，与简单地应用一般定理相比，分析算法的结构可以产生更强的空间限制证明。本节最后讨论并行函数如何无法与遗留和第三方串行二进制文件互操作。
00:45:00 在视频的这一部分，演讲者讨论了如何使分配的足迹尽可能接近用户足迹，以最大限度地减少两者的比率。一种解决方案是使用称为 M advise 的东西，它告诉操作系统不再需要某个内存页，但应将其保留在虚拟内存中。演讲者还提到了上一讲的定理，即 bin free lists 的碎片是 U 的 order log base 2，其中 U 是分配的内存总量，并解释了空间开销、内部碎片和外部碎片之间的区别。最后，演讲者指出，现代 64 位处理器提供大约 2 到 48 字节的虚拟地址空间，这对于大多数程序来说已经足够，但仍然超过典型机器上的物理内存。
00:50:00 在本节中，视频探讨了使用具有互斥保护的全局堆的并行堆分配策略，这是默认 C++ 分配器的工作方式。这种策略的缺点之一是，与串行分配器相比，它不需要额外的空间。然而，这种方法的潜在问题是性能下降，因为每次分配和释放都获取锁很慢，并且随着处理器的增加而变得更糟。锁争用是可扩展性差的主要原因，由于更高的请求率，这对于小分配来说问题更大，而大块分配需要更多的工作。
00:55:00 在本节中，视频讨论了使用本地堆方法的潜在问题，即它可能导致内存漂移和无限爆炸。本质上，如果您在一个线程中分配所有内存但在另一个线程中释放它，则系统中可能存在未使用的内存，分配器不够智能，无法重用。因此，在多个处理器上运行的程序最终可能会耗尽内存，但如果它仅在单个内核上运行，则不会发生这种情况。该视频建议使用 bin free list 方法来解决此问题，这涉及在 bin free list 数据结构中设置指针，以便释放的块可以出现在其中一个链表中。另一种策略是定期重新平衡内存，但也讨论了一种更简单的方法。
01:10:00 在本节中，演讲者解释了 Horde 分配器如何通过从最满的非满超级块中分配一个空闲对象来密集超级块的移动来减少外部碎片。如果在本地堆中找不到该对象，它会检查全局堆，如果全局堆为空，它会从操作系统调用一个新的超级块。 Horde 分配器维护一个不变量，其中堆最多使用了一半，如果它检测到堆未被充分利用，它会将半空的超级块移动到全局堆。然后演讲者提出一个引理，指出全局堆中分配的最大存储最多是本地堆中分配的最大存储。最后，演讲者证明了 Horde 分配器的占用空间上限为 u 加 SP 的定理，其中 u 是程序的用户占用空间，SP 是本地堆中已分配但未使用的存储空间。然后将放大计算为一阶 SP 除以 u。
01:15:00 在本节中，演讲者讨论了不同的分配器，包括 Je malloc 和 Super malloc。 Je malloc 对不同的分配大小有单独的全局锁，并使用 em advice 释放空页，这使得它对不同的分配跟踪具有鲁棒性。另一方面，Super malloc 代码行数极少，发展速度非常快。演讲者分享了基准测试结果，其中 Super malloc 的性能优于 J malloc，J malloc 的性能优于 Horde，而默认分配器的性能较差。讨论还扩展到垃圾收集，但是，演讲者将其细节推迟到在线幻灯片。
Cilk 运行时系统使用设置跳转和跳远协议来处理从受害进程的执行平台窃取计算。 Cactus Stack 抽象允许窃贼进程拥有自己的调用堆栈，以防止损坏受害者的堆栈。系统的同步协议使用计算树和 Cactus Stack 来确保同步仅发生在函数内的嵌套计算之间。 Full Frame Tree 维护计算与未完成子计算之间的父子关系，以简化同步过程。此外，运行时系统优化了当前函数没有未完成的子计算并且所有工作进程都忙的常见情况。支持的其他功能包括 C++ 异常、reducer 超对象和谱系。
00:20:00 在本节中，演讲者讨论了 Cilk 运行时系统所需的功能，其中包括串行执行、窃贼跳入运行函数的中间、同步以嵌套细粒度方式进行同步、仙人掌栈用于所有工作人员都可以看到，并处理生成帧和被调用帧的混合，这些帧在窃取计算时可能可用。然后该部分继续讨论系统的性能，我们需要足够的并行性，T1 over T infinity 应该比 P 大很多，并且我们希望在增加运行程序的处理器数量时线性加速。本节还介绍了 TCP 在 P 个处理器上的预期运行时间，它与计算工作量除以处理器数量再加上计算跨度的数量级成正比。
00:25:00 在本节中，我们将了解 Cilk Runtime System 及其在具有足够并行性的程序中保持高工作效率的目标。 Silk Runtime System 通过优化程序的串行执行来遵守工作至上的原则，即使以钢材的一些额外成本为代价。运行时系统库处理并行执行的问题，并在出现故障时处理较慢的执行路径。 worker 维护一个单独的 deck 数据结构，其中包含指向堆栈帧的指针并使用头指针和尾指针。可被窃取的帧有一个额外的本地结构，其中包含必要的信息，以便在 deck 位于调用堆栈外部时发生窃取。
00:45:00 在本节中，演讲者讨论缓存和缓存高效算法。他们分析了矩阵乘法的两种情况，其中 n 大于 B 上的 M 和 n 小于 C 乘以 M 上的 B。他们使用 LRU 替换策略并计算访问矩阵 B 时发生的缓存未命中数。在第一个在这种情况下，他们发现他们需要 n 个立方缓存未命中的 theta，导致算法中的局部性没有任何好处。在第二种情况下，他们可以利用空间局部性并将缓存未命中数减少 B 倍，从而使 n 的立方比 B 缓存未命中数的 theta 更高效。
00:50:00 在视频的这一部分，演讲者讨论了缓存和缓存高效算法。他们首先分析了整个矩阵适合缓存的情况，导致缓存未命中总数为 n 的平方 B。然后他们通过交换内部两个循环的顺序来讨论优化，以受益于空间局部性和将缓存未命中的总数减少到 n 的三次方 B。但是，他们指出，可以通过使用称为平铺的优化来做得更好，其中六个 for 循环用于循环平铺并为每个子完成计算-矩阵，然后再继续下一个。然后对大小为 s × s 的子矩阵的工作进行 s 立方。
01:05:00 在本节中，演讲者讨论了缓存和缓存高效算法，并使用矩阵乘法的示例来解释分析工作和缓存未命中之间的区别。演讲者画了一个递归树来可视化大小问题和分支子问题，并注意到直到叶子的层数是 n 的以 2 为底的对数。叶子的数量计算为 n 的以 2 为底的对数 8，这与 n 的立方相同。工作量只是 theta n 的立方，使用不同的基本情况分析缓存未命中，其中子矩阵适合缓存，并使用缓存未命中的 N 平方的 theta。演讲者强调，级别的数量不仅仅是 n 的以 2 为底的对数，还取决于缓存的大小，从而导致不同的叶子数量，即 n 的立方 m 的 theta 的三等分。
视频的第二部分讨论了用于排序和合并的无缓存算法。具体来说，视频涵盖了归并排序的缓存复杂度，介绍了多路归并的概念，讲解了多路归并算法的缓存复杂度。该视频还讨论了漏斗排序算法，这是一种缓存不经意的排序算法，可以合并 K 个平方元素和 K 个排序列表。漏斗排序算法是最优的，用 K 个漏斗的平方根递归构造。该视频解释了还有许多其他无需缓存的算法和数据结构，例如 B 树、有序文件维护和优先级队列。总的来说，该视频为那些有兴趣进一步了解该主题的人提供了缓存遗忘算法的介绍。
00:05:00 在本节中，演讲者将介绍如何为允许使用模板方法进行有限差分近似的仿真方程编写代码。该方程使用 U 相对于 T 和 X 的偏导数，演讲者展示了如何使用近似方法获得这些偏导数。二维空间使用矩阵表示，X 和 T 值分别在水平和垂直方向表示。演讲者解释了矩阵的边界并使用等式计算 U。
00:10:00 在本节中，演示者解释了模板计算，这是一种在科学计算中广泛用于各种目的的方法。在此方法中，数组中的每个点都使用称为模板的固定模式进行更新。计算取决于其他三个值，这被称为三点立场。尽管模板计算可用于较大的 X 值，但性能可能会因缓存而受到影响，从而导致缓存未命中。此外，通过仅存储两行（当前行和先前行）来更新点值，可以减少存储数据所需的存储空间。
00:15:00 有效：在每个时间步长中，我们仅使用前一行的值更新特定行的 X 值。因此，我们可以交替更新哪一行和将哪一行用作前一行，并且只需要保留大约一行额外的值。然而，这段代码的缓存效率不是很高，我们可以使用平铺或缓存无关算法来提高效率。理想的缓存模型假设一个完全关联的缓存具有最优或 LRU 替换策略，并捕获容量未命中但不是串行执行中的冲突未命中。尽管如此，它对于设计利用时间和空间局部性的高效算法仍然很有用。
00:20:00 在本节中，演讲者解释了如何使用缓存遗忘算法来计算 2D 矩阵中梯形空间内的点，而无需查看外部。计算涉及一个内核函数，该函数将指向 UT mod 的指针取为 X，并返回 W 的 0 加上 alpha 乘以负 1 的 W 减去 2 乘以 W 的 0 加上 W 的 1。假设 LRU 替换策略分析了缓存行为，并且高速缓存未命中数是每行 B 上 NT 的 Theta。然而，演讲者指出，通过平铺可以实现更好的性能，但他们继续讨论无缓存版本。梯形在 T1 处有一个顶底，在 T0 处有一个底底。该算法使用涉及 T、t0、t1、X、x0、x1、DX0、DX1 的不等式条件计算梯形内的所有点，其中 DX0 和 DX1 为 -1、0 或 1，表示斜率。
00:30:00 在本节中，演讲者讨论了缓存无关算法的缓存复杂性。他们分析了递归树方法，发现该算法在每个级别将自身分为两个子问题，直到达到基本情况，它表示 HW 点的 theta，其中 H 是 W 的 Theta。每个叶子的缓存未命中数是 theta W在 B 上，叶子的数量是 NT 在 HW 上的 Theta。内部节点对高速缓存的复杂性没有实质性贡献。缓存复杂度泛化为多维，如果 d 为一，则导致 NT 超过 MB。
00:35:00 在本节中，演讲者解释了循环代码和梯形代码之间的区别，梯形代码通过节省 M 因子（其中 M 是缓存行数）具有更好的缓存复杂度。仿真表明，与循环代码相比，梯形代码会导致更少的缓存未命中，从而更快地完成计算。但是，演讲者指出此模拟仅适用于一维，并继续演示二维中发生的情况。
00:45:00 在本节中，演讲者讨论了缓存和并行性之间的相互作用。他们解释了一个定理，即在串行执行中最小化高速缓存未命中可以在假设低跨度算法的情况下在并行执行中最小化它们。然后，他们演示了梯形算法如何使用 V 形切割并行工作，其中两个独立的梯形并行执行，灰色梯形随后执行。他们还提到用于倒梯形的倒置 V 形切割。
01:00:00 在本节中，演讲者通过首先分析合并两个已排序输入数组的复杂性来讨论分析合并排序的缓存复杂性。执行此操作的时间与输入数组大小的总和成正比。合并 n 个元素时发生的缓存未命中数是 B 上的 theta n，其中 B 是缓存行中的字节数。合并排序对一半大小的输入进行两次递归调用，并合并其递归调用的排序输出。归并排序的整体工作是theta of n log n，使用递归树的方法进行分析。还讨论了归并排序的缓存复杂度，表明缓存未命中数与存储数据所需的缓存块数成正比，即 theta n over B log M，其中 M 是最大尺寸 a子块可以有。
01:05:00 在本节中，演讲者解释了归并排序缓存复杂性的重现。基本情况发生在问题大小适合缓存时，导致 Θ(n/B) 缓存未命中。否则，该算法有两个大小为 n/2 和 Θ(n/B) 缓存未命中的递归调用来合并结果。分析涉及递归树的层数，即n/CM的以2为底的对数，其中CM为常数。每片叶子的缓存未命中数是 Θ(M/B * n/CM)，给出了 Θ(n/B * log (n/CM)) 的缓存未命中总数，在第一项中节省了 B 因子.然而，对于较大的问题规模，与工作量相比，我们只节省了 B 的一个因子，而对于较小的问题规模，我们节省了 B log n 的一个因子。演讲者询问是否有更好的解决方案，答案总是肯定的。
01:15:00 在本节中，演讲者讨论了多路归并排序算法的缓存复杂度，并将其与二进制归并排序算法进行了比较。多路合并排序算法涉及将问题划分为大小为 n/R 的子问题，并支付 n/B 缓存未命中以合并它们。递归树的层数为n/cm的对数底R，叶子大小为cm。 speaker 将 R 设置为等于 M/B 的 theta，使其尽可能大，并分析了缓存复杂度，结果是 thetan n log n 除以 B log M。与二进制归并排序算法相比，多-way 合并排序算法在缓存未命中中节省了 log M 的一个因子。然而，该算法不是缓存无关的，并且需要针对特定机器调整 R 的值，如果其他作业正在运行竞争缓存，这可能会成为问题。
01:20:00 在本节中，演讲者讨论了漏斗排序算法，这是一种缓存遗忘排序算法，可以合并 K 个平方元素和 K 个排序列表。此合并的成本显示与多路合并排序算法的成本相同，但漏斗排序算法是缓存无关的，其边界是最优的。演讲者展示了 K 漏斗的图片，并解释了该算法是使用 K 漏斗的平方根递归构建的，它将元素提供给缓冲区，缓冲区又将元素提供给 K 漏斗的最终输出平方根，从而产生K 漏斗的输出。演讲者还提到还有许多其他缓存无关算法和数据结构，例如 b 树、有序文件维护和优先级队列，并邀请观众在线了解更多信息。
视频的第二部分讨论了使用内存栅栏和同步指令来防止并行程序中的错误。演讲者探讨了以隐式或显式方式实现内存栅栏的不同方法，以及在处理处理器不同方面的不同团队之间进行精心设计和协调的重要性。此外，讲师讨论了使用CAS指令作为C11语言标准中无锁算法的一部分，仅使用常量空间来实现n线程无死锁互斥算法的互斥量。 Charles Leiserson 解释了在多线程系统中使用锁的问题以及改用 CAS 的解决方案，因为长时间持有锁的线程可能会阻塞等待访问同一资源的其他线程。此外，该视频强调了比较和交换的 ABA 问题的潜在问题，并鼓励对该主题感兴趣的人了解更多有关无锁算法的信息。
00:15:00 在本节中，Charles Leiserson 解释了 Peterson 的算法，该算法仅使用加载和存储操作在并发程序中实现互斥。该算法允许两个并发进程 Alice 和 Bob 通过使用一组变量和轮流机制在互不干扰的情况下执行代码。该代码确保一次只有一个进程可以进入临界区并修改共享资源。与锁不同的是，Peterson 的算法不依赖于获取或释放锁，而是使用加载和存储来实现互斥。
00:20:00 在本节中，演讲者讨论了 Peterson 在不使用锁的情况下实现临界区互斥的算法。他解释说，一次只有一个人可以进入临界区，算法确保想要进入临界区的人可以进入，如果他们是唯一想进入的人的话。然后演讲者给出了该算法的证明，其中包括假设 Alice 和 Bob 发现自己一起处于临界区并推导出矛盾。证明依赖于“先于发生”关系和执行指令的程序顺序。
00:25:00 在本节中，演讲者解释了无锁同步的过程。他们建立指令链并确保它们以正确的顺序出现以避免同步错误。他们使用 Bob 和 Alice 想要访问共享资源的示例作为演示。他们解释说，在同步时，工程师需要小心并审查“发生在事情之前”以确保它们以正确的顺序发生。
01:05:00 在本节中，讲师讨论了C11 语言标准中的无锁同步。该标准定义了一个弱内存模型，它允许将事物声明为原子的，需要使用昂贵的操作，如内存栅栏或用于无死锁互斥算法的原子比较和交换。在这里，CAS 指令（比较和交换）作为无锁算法的一部分进行了探索。该指令检查内存中的值是否与旧值相同，然后再将其交换为新值，所有操作均以原子方式完成。 CAS 的使用允许仅使用常量空间来实现 n 线程无死锁互斥算法的互斥量。一个锁指令，它旋转直到它得到值 true，用于交换 true 说明有人持有锁。
01:10:00 在本节中，Charles Leiserson 教授解释了如何使用比较和交换 (CAS) 来解决同步问题。他演示了如何使用 CAS 作为锁并修复了学生提交的代码中的错误。然后，他提供了一个用于计算数组中值总和的错误代码，这导致了竞争条件。他介绍了互斥锁作为典型的解决方案，并解释了一个线程在获取锁后被换出的潜在问题，导致其他线程等待锁，从而阻碍了进展。
01:15:00 在这一节中，Charles Leiserson 解释了在多线程系统中使用锁的问题以及使用 CAS 代替的解决方案。有了锁，一个线程可能会持有锁很长时间，阻塞等待访问同一资源的其他线程。但是，对于 CAS，在计算温度之后加载 x 之后是存储 x，同时还使用变量 old 和 new 来存储旧结果并将临时结果添加到该旧值以产生一个新值，该新值可以是如果旧值未更改，则换入。 Charles 还提到了比较和交换的 ABA 问题，并鼓励对该主题感兴趣的人学习更多关于无锁算法的知识。
00:55:00 在本节中，演讲者讨论了 Leiserchess 项目中的 eval.c 文件，以及由于其大小和复杂性，乍一看似乎让人不知所措。然而，随着用户越来越熟悉它，他们将获得处理一段合适大小的代码的信心。 eval.c 文件包含启发式算法，例如 p between、p central、k face 和 k aggressive，它们根据棋子的类型及其颜色评估棋盘上的每个方块。 p between heuristic 决定兵是否在两个国王之间，而 p central 根据兵离棋盘中心的距离给予奖励。 k face 和 k aggressive heuristics 根据国王的方向及其与对手和棋盘边缘的距离给予奖励。
00:05:00 在本节中，演讲者讨论了如何缓解在并行操作时向内循环添加过多内容的问题。他们解释说，条带挖掘可用于将 n 次迭代的循环替换为 n 次超过四次迭代的循环和四次迭代的内部循环，同时还检查是否每四次迭代都超过阈值以最小化成本支票。为了并行化一个短路循环，演讲者在代码中添加了一个中止标志，并递归地使用它来检查总和是否大于限制并且在将标志设置为真之前没有被中止。通过在设置之前检查标志，他们避免了确定性竞赛并防止了真正的共享竞赛。
00:25:00 在这一部分，演讲者谈到了一个程序，该程序几乎赢得了 1999 年世界计算机象棋锦标赛的冠军。他们提出了一个大家都同意的规则更改，但后来他们输给了著名的 IBM 计算机深蓝。他们在桑迪亚国家实验室的 1824 节点超级计算机上运行，他们唯一的损失是深蓝。他们决定让他们的程序中的转置表存在竞争，但不包括访问表的锁，因为这会减慢程序的速度。他们计算出，一场比赛影响他们选择的价值并最终影响锦标赛结果的几率很低。
00:30:00 在视频的这一部分，演讲者讨论了三种对国际象棋 AI 决策很重要的数据结构。第一个是“杀手级”启发式算法，它跟踪给定代码深度的最佳移动，并且在本质上倾向于重复。第二个是“最佳着法”表，它根据统计数据对所有顺序较低的着法进行排序。两种数据结构都是共享的，在并行化代码时需要妥善管理。最终的数据结构是开局书，它在游戏开始时预先计算出最佳着法。然而，演讲者表示，悬而未决的结果比开场白要少，而且从统计数据来看，大多数游戏的持续时间都不足以让开场白发挥作用。
00:35:00 在本节中，演讲者讨论了在 Leiserchess 中构建开局书籍的策略，Leiserchess 是一款团队尝试创建最强的国际象棋机器人的游戏。演讲者指出，一些团队通过创建强大的开局书取得了成功，这使他们能够通过出色的开局取胜。他们还建议，为每一方保留单独的开篇书比双方都使用一本更有效。此外，演讲者建议为代码添加轻微的随机性以避免可预测性，但警告说在 beta one 期间没有必要为此进行优化。最后，他们提出了迭代加深的策略，该策略涉及在不同深度执行搜索，直到时间控制到期。演讲者指出，这是一个很好的策略，因为每个深度的工作量呈指数增长，但重要信息是在前几个深度积累的。
01:20:00 在本节中，视频讨论了重构代码并对其进行适当测试以确保在不破坏代码的情况下正确进行更改的重要性。演讲者建议在修改函数调用之前重构板对函数调用的访问，以便在不进行大量重构的情况下更轻松地更改板表示。适当的测试对于确保更改是正确的并且不会破坏代码也是必不可少的，并且使代码具有确定性以避免不可预测性也很重要。演讲者还提到了 John Bentley 即将举行的讲座，这是一次结识名人和了解该领域更多信息的宝贵机会。
第 11 讲。存储分配
第 11 讲。存储分配
讲师在此视频中讨论了存储分配，包括内存分配和释放。解决了不同类型的存储，包括堆栈和堆，以及固定和可变大小的分配方案。还讨论了由内存块分散引起的外部碎片，以及每个磁盘页面的空闲列表或位图等解决方案。还介绍了垃圾收集的概念，包括引用计数和该算法的局限性。还解释了“标记和清除”和“停止和复制”垃圾收集过程，重点是后者如何解决碎片和指针更新可能产生的正确性问题。该视频以关于停止和复制算法的时间和空间复杂度及其消除外部碎片的注释结束。
该视频涵盖了与动态存储分配相关的各种主题，包括 Buddy 系统、标记和清除程序、优化、分代和实时垃圾收集、多线程存储分配和并行垃圾收集。讲师解释说，分代垃圾收集基于更频繁地扫描年轻对象的想法，而实时垃圾收集在程序执行期间在后台运行，但如果对象和指针图不断变化，可能会导致正确性问题。最后，讲座总结了不同类型的存储分配，包括堆栈和堆，以及不同的垃圾收集方法，例如引用计数、标记清除和停止复制。讲师提到学生将在即将到来的家庭作业中尝试其中的一些方法。
第 12 讲。并行存储分配
第 12 讲。并行存储分配
该视频讨论了各种内存分配策略及其权衡。解释了 malloc 和对齐分配的使用，以及使用 free 正确释放内存的重要性。还介绍了使用 Mmap 进行虚拟内存分配，以及外部碎片和性能低下的问题。探讨了 C 和 C++ 编程中堆栈的概念，重点放在用于分配堆栈帧的基于堆的仙人掌堆栈方法上，这可以带来更好的空间限制证明和上限。还讨论了线性堆栈池的使用，以及优化小块以最小化碎片的重要性。该视频最后讨论了全局和局部堆方法及其潜在问题，以及用于解决这些问题的 bin 空闲列表和定期内存重新平衡等方法。
该视频还讨论了并行存储分配的解决方案，并介绍了 Hoard 分配器作为解决方案。 Hoard 分配器结合使用本地和全局堆以及可以在堆之间移动的大型超级块，以减少错误共享、提高可伸缩性并减少外部碎片。全局堆中分配的最大存储最多是本地堆中分配的最大存储，占用空间上限为用户占用空间加上本地堆中已分配但未使用的存储空间。该视频还简要讨论了其他分配器，例如 Je malloc 和 Super malloc，基准测试结果表明 Super malloc 的性能优于 Je malloc 和 Hoard。讨论最后引用了有关垃圾收集详细信息的在线幻灯片。
第 13 讲 Cilk 运行时系统
第 13 讲 Cilk 运行时系统
Cilk 运行时系统负责并行处理器上的调度和负载平衡计算，使用随机工作窃取调度程序在运行时将计算映射到处理器。该系统旨在优化程序的串行执行，即使以窃取额外成本为代价。 worker 维护一个单独的 deck 数据结构，其中包含指向堆栈帧的指针并使用头指针和尾指针。可被窃取的帧有一个额外的本地结构，其中包含必要的信息，以便在 deck 位于调用堆栈外部时发生窃取。该部分解释了系统如何使处理器能够从正在运行的函数的中间开始执行，以及当到达无法执行超出该点的同步语句时处理器之间的同步如何变得复杂，因为特定处理器仍在等待计算完成。此外，演讲者还介绍了系统的性能、设计考虑和数据结构，以及系统如何使用 THC 协议优化执行，涉及两组协议，一组用于执行工作的工人，另一组用于小偷。
Cilk 运行时系统使用设置跳转和跳远协议来处理从受害进程的执行平台窃取计算。 Cactus Stack 抽象允许窃贼进程拥有自己的调用堆栈，以防止损坏受害者的堆栈。系统的同步协议使用计算树和 Cactus Stack 来确保同步仅发生在函数内的嵌套计算之间。 Full Frame Tree 维护计算与未完成子计算之间的父子关系，以简化同步过程。此外，运行时系统优化了当前函数没有未完成的子计算并且所有工作进程都忙的常见情况。支持的其他功能包括 C++ 异常、reducer 超对象和谱系。
第 14 讲 缓存和缓存高效算法
第 14 讲 缓存和缓存高效算法
在关于缓存和缓存高效算法的视频中，讲师解释了现代机器的缓存层次结构、完全关联缓存和直接映射缓存之间的区别，以及集合关联缓存的优缺点。该视频还介绍了理想的缓存模型和缓存高效算法的概念。演讲者讨论了缓存未命中引理、高缓存假设和子矩阵缓存引理。他们还分析读取子矩阵和矩阵乘法期间发生的缓存未命中。该视频最后介绍了分块矩阵乘法的概念以及它如何显着提高性能，但也指出它不可移植，并且针对多级缓存进行优化可能代价高昂。
本讲座以递归矩阵乘法为例，介绍了缓存和缓存高效算法。演讲者强调了分别分析工作和缓存未命中的重要性，并指出由于缓存大小不同，缓存感知算法可能并非对所有机器都是最佳的。演讲者还讨论了针对任何缓存大小自动调整的缓存无关算法，并提到了并行缓存无关代码的开发。最后，目标是设计缓存感知或缓存无关的算法，关于缓存无关算法设计的讨论将在下一讲中继续。
第 15 讲缓存无关算法
第 15 讲缓存无关算法
该视频讨论了缓存无关算法，可以自动调整机器上的缓存大小，实现良好的缓存效率，并且不需要知道机器的缓存参数。该视频展示了如何使用模板方法在二维矩阵上通过微分方程编写代码来模拟热扩散。该代码同时具有循环和梯形版本，由于循环代码访问模式的可预测性，后者的缓存效率更高，但在 2D 模拟中速度并不明显。该视频还讨论了缓存和并行之间的相互作用以及潜在并行加速瓶颈的诊断。最后，演讲者解释了模板计算以及数组中的每个点如何使用称为模板的固定模式进行更新，模板可能会遭受缓存未命中，并且可以使用利用时间和空间局部性的高效算法来减少存储需求。
视频的第二部分讨论了用于排序和合并的无缓存算法。具体来说，视频涵盖了归并排序的缓存复杂度，介绍了多路归并的概念，讲解了多路归并算法的缓存复杂度。该视频还讨论了漏斗排序算法，这是一种缓存不经意的排序算法，可以合并 K 个平方元素和 K 个排序列表。漏斗排序算法是最优的，用 K 个漏斗的平方根递归构造。该视频解释了还有许多其他无需缓存的算法和数据结构，例如 B 树、有序文件维护和优先级队列。总的来说，该视频为那些有兴趣进一步了解该主题的人提供了缓存遗忘算法的介绍。
第 16 讲。非确定性并行编程
第 16 讲。非确定性并行编程
该视频讨论了与确定性和非确定性并行编程相关的各种概念。演讲者强调了避免非确定性的重要性，因为它会导致异常行为和调试困难。管理非确定性的策略包括使用固定值、记录回放、分析工具、封装和单元测试。详细探讨了互斥体的使用，包括自旋与屈服、可重入与不可重入以及公平与不公平。演讲者还谈到了上下文切换的概念和并行编程上下文中的“滑雪租赁问题”。该部分最后讨论了多核处理器中性能工程的基本原理。
视频的第二部分介绍了并行编程中的死锁问题并提供了避免死锁的解决方案，例如保证没有等待循环的互斥锁的线性排序。此外，演讲者还介绍了事务内存的概念，它通过将关键区域表示为一次提交所有更新的事务来确保原子性。然后，该视频介绍了一种算法，该算法使用基于锁的方法以及有限所有权数组和释放排序 require 方法来防止死锁和饥饿，而无需全局锁。最后解释了release sort and reacquire算法，避免了多个锁同时尝试获取一个锁，避免了性能问题。
第 17 讲 无锁同步
第 17 讲 无锁同步
Charles Leiserson 在 YouTube 视频中探讨了无锁同步的概念。他提供了一个示例，说明需要全局线性指令顺序来确保顺序执行，并讨论如何通过顺序一致性实现互斥，避免使用锁的困难和潜在问题。 Leiserson 介绍了 Peterson 的算法作为一种解决方案，该解决方案仅使用加载和存储操作来访问关键部分而不受并发进程的干扰。该视频还涵盖了由于硬件重新排序而导致的通过内存同步的挑战，以及与其他指令保持相对顺序的内存栅栏的概念。 Leiserson 认为，支持并行机器的顺序一致性是有益的，但对硬件设计者来说很难实现。
视频的第二部分讨论了使用内存栅栏和同步指令来防止并行程序中的错误。演讲者探讨了以隐式或显式方式实现内存栅栏的不同方法，以及在处理处理器不同方面的不同团队之间进行精心设计和协调的重要性。此外，讲师讨论了使用CAS指令作为C11语言标准中无锁算法的一部分，仅使用常量空间来实现n线程无死锁互斥算法的互斥量。 Charles Leiserson 解释了在多线程系统中使用锁的问题以及改用 CAS 的解决方案，因为长时间持有锁的线程可能会阻塞等待访问同一资源的其他线程。此外，该视频强调了比较和交换的 ABA 问题的潜在问题，并鼓励对该主题感兴趣的人了解更多有关无锁算法的信息。
第 18 讲。领域特定语言和自动调整
第 18 讲。领域特定语言和自动调整
在此视频中，麻省理工学院 EECS 系的 Saman Amarasignhe 教授讨论了在性能工程中使用领域特定语言 (DSL) 和自动调整的好处。他强调了 DSL 的重要性，DSL 捕获难以用通用语言描述的特定领域，允许程序员利用领域专家的知识来获得更好的性能。 Singh 讨论了使用 DSL 优化图形过程，包括图形分区和图形形状在计算中的重要性。他介绍了用于图像处理的 DSL Halide，它可以实现快速代码优化和跨机器的可移植性。他讨论了 Halide 在 Google 和 Adobe 等各个行业中的使用。最后，他强调了在优化代码时尝试不同方法的重要性，同时关注并行性、局部性和冗余工作。
该视频还讨论了性能工程的挑战，以及为程序高效运行寻找最佳参数的挑战。演讲者建议自动调整可以通过自动搜索大参数空间来找到最优值来解决这个问题。他指出，穷举搜索可能不切实际，基于启发式的解决方案可能不是最优的。自动调整定义了可接受值的空间并根据性能结果进行迭代，可以加快寻找最佳解决方案的过程。演讲者还讨论了自动调整在为 Try 生成调度时的应用，它能够比穷举搜索更有效地生成调度。
第 19 讲 Leiserchess Codewalk
第 19 讲 Leiserchess Codewalk
在这个名为“19. Leiserchess Codewalk”的 YouTube 视频中，Helen Xu 解释了 Lesierchess 的规则，Lesierchess 是一种由两支球队进行的游戏，目标是射击对方的王或射中你的王。该游戏有两种类型的动作，基本动作和重击动作，以及一个 Ko 规则，如果它撤消了对手最近的动作，则该动作是非法的。 Xu 深入探讨了玩游戏的各个方面，包括 Fisher 时间控制方法、Forsythe-Edwards 符号、云自动测试器和项目组织，使用 Elo 评级、移动生成、静态评估和搜索算法（如 alpha-beta）评估和比较机器人，原理变化、子树修剪和转置表。她还讨论了测试基础架构对于优化程序和 eval.c 文件的重要性，该文件包含根据棋子类型及其颜色评估棋盘上每个方块的试探法。
演讲者还深入探讨了游戏的激光覆盖方面，解释了使用 while-true 语句根据玩家的颜色为一个位置生成所有可能移动的复杂系统。他们还解释了代码正确性的重要性以及如何对其进行测试，建议在性能优化之前转换表示以确保正确性。演讲者还讨论了 Leiserchess UCI 界面提供的极大灵活性，它允许用户根据自己的喜好编辑表格和命令，并向观众保证死代码将被清理，并且应报告任何其他错误以进行修复。
第 20 讲 思辨平行论和 Leiserchess
20. 推测平行论和 Leiserchess
在这个名为“20. Speculative Parallelism & Leiserchess”的 YouTube 视频中，讲师介绍了推测并行性的概念，它本质上是先发制人地猜测某些任务可以并行执行并且可以产生更快的代码。但是，演讲者警告说此代码是不确定的，只应在必要时使用，同时还警告不要在可以使用更好的串行代码的情况下使用它。视频的很大一部分围绕着讨论并行 alpha-beta 搜索，其中涉及修剪游戏树以优化搜索时间，还讨论了搜索算法评估过程中使用的不同数据结构和启发式方法，特别是避免循环和静止搜索。该视频还谈到了迭代加深的好处以及它如何为搜索带来更好的移动排序，同时还讨论了 Zobrist 哈希，这是一种用于搜索算法的优化技术，涉及棋盘上具有相同棋子的每个位置的唯一哈希值。
该视频还讨论了国际象棋引擎的各种优化技术，例如换位表、后期移动减少以及使用位板生成移动。演讲者还谈到了“推测性并行性和 Leiserchess”的主题，他建议程序员评估移动是否影响激光的路径并追求“激光覆盖”。演讲者建议在代码中保留旧的表示，并使用程序来测试更改。他们还开发了一种启发式方法，用于测量激光与 Leiserchess 中的国王有多近。更多优化建议包括寻找更好的方法来评估对手与玩家激光的接近程度以及优化动作排序。最后，讨论了正确重构和测试代码的重要性。