00:05:00 在本节中，演讲者讨论了计算性能工程的历史，以及从早期由于机器资源有限而导致的密集性能工程到芯片密度每两年翻一番的摩尔定律时代的转变让硬件赶上比优化软件更有利。然而，演讲者指出，通过降低功耗允许时钟速度变大的 Dennard 缩放在 2004 年结束，因此对性能工程的需求比以往任何时候都更加重要。演讲者引述了计算机科学家 Donald Knuth、Bill Wolfe 和 Michael Jackson 关于可读代码的重要性以及对过早优化的警告的引述。
00:25:00 在本节中，演讲者讨论了解释型语言（如 Python）、编译型语言（如 C）以及编译为字节码然后解释的语言（如 Java）之间的性能差异。像 Python 这样的解释器用途广泛但速度很慢，而像 C 这样的编译器则利用硬件和机器指令来优化性能。 JIT 编译器，与 Java 中使用的编译器一样，通过仅编译最常执行的代码片段来恢复一些性能。讲者指出，Python 的性能模型很难理解，这就是为什么他们在课程中会使用 C 来进行性能比较。但是，将有一个客座讲座，他们将讨论使用托管语言（如 Python）进行的性能工程。
00:30:00 在本节中，讨论了循环顺序对于矩阵乘法性能的重要性。循环的顺序影响缓存局部性，进而影响运行时间。矩阵在 C 中按行优先顺序排列在内存中，在 Fortran 中按列优先顺序排列。 ijk 阶的访问模式对 C 具有良好的空间局部性，但对 B 具有较差的空间局部性。工具“cachegrind”可用于确定代码的未命中率，调整编译器标志等简单更改也可以提高性能。
00:00:00 在本节中，讲师介绍了优化计算机程序工作的概念，并解释了减少程序工作如何提高其性能。他还谈到了优化工作的 Bentley 规则，该规则以 John Lewis Bentley 的名字命名，他写了一本关于编写高效程序的书。优化分为四类：数据结构、循环、逻辑和函数，讲师计划在整个课程的一系列小型讲座中涵盖所有 22 条规则。虽然减少程序的工作是改善其运行时间的一个很好的启发式方法，但计算机硬件的复杂性意味着它并不总是转化为运行时间的减少，因此讲师还将在稍后的章节中介绍特定于体系结构的优化课程。
00:05:00 在视频的这一部分，演讲者讨论了打包和编码数据结构的概念，以在机器字中存储多个数据值，并将数据值转换为需要更少位的表示形式。通过减少在内存中移动的东西的数量，它成为减少程序运行时间的一个很好的启发式方法。演讲者提供了一个编码日期的示例，以使用更少的位来存储它们，从而更容易获取特定日期的月、年或日。演讲者建议使用 C 中的位域功能来存储结构化数据，使其更易于访问。这种表示需要稍微多一点的位，但在访问结构中的特定数据值时效率更高。
00:15:00 在本节中，演讲者讨论了如何使用递归公式和 C 代码预先计算帕斯卡三角形。他们解释说递归公式涉及调用 choose 函数，以及如何在运行时使用循环预先计算表。此外，他们还讨论了如何通过将表值放入源代码来在编译时初始化表，从而节省程序执行时间。最后，他们提供了一个可在程序执行期间访问的最多为 10 的二项式系数的示例表。
00:20:00 在本节中，演讲者介绍了元编程的概念，作为一种避免在程序中手动输入大量常量值表的方法。通过编写生成必要代码的程序，可以自动完成繁琐的任务。演讲者提供了一个 Python 代码片段作为示例。还介绍了缓存主题，作为一种通过将最近访问的结果存储在缓存中来避免重复昂贵计算的技术。给出的示例是使用平方根运算符计算直角三角形的斜边，其中缓存预先存储以前的斜边以及 a 和 b 的值。 hypotenuse 函数首先检查输入值是否与缓存中的值匹配，如果匹配，则返回缓存值而无需重新计算平方根。
00:10:00 在本节中，视频讨论了可以在 C 中使用按位运算符实现的各种常见习语。一个示例是通过使用移位后跟 OR 或 NOT 和和，分别。另一个示例是通过在所需位的位置生成一个掩码，在其他地方为零，然后将掩码与 X 进行与运算，并右移提取的位，从而从字 X 中提取位域。该视频还提到，使用这些技巧在处理压缩或编码数据时特别有用。
00:15:00 在本节中，视频讨论了如何通过一些位技巧在不使用临时变量的情况下交换两个整数。该代码涉及设置 X 等于 X XOR Y，然后 Y 等于 X XOR Y，最后 X 等于 X XOR Y。这是有效的，因为 XOR 是它自己的逆，第一行生成一个掩码，其中 X 中的位和 Y 不同，然后用于翻转 Y 中与 X 不同的位。这允许在不使用临时变量的情况下进行交换。该视频还强调了在使用这些技巧时遮蔽以确保安全的重要性。
00:30:00 在本节中，视频讨论了编程中的可预测和不可预测分支，并介绍了无分支最小位技巧作为不可预测分支问题的解决方案。这个技巧涉及使用一个名为“comp”的变量来存储 a 和 b 的第一个元素之间的比较结果，并使用一个位技巧获得 a 和 b 的最小值。然后，最小值放在C中，A或B的值根据“comp”的值递增或递减。该视频指出，虽然该技巧在某些情况下可能不起作用，但它有助于了解编译器在做什么，而且许多针对单词的位黑客攻击可以扩展到向量的位和单词黑客攻击，因此了解这些技巧很有用。
00:35:00 在本节中，视频讨论了位黑客及其在编程中的实用性。给出的示例是模块化加法的一个小技巧，它允许在不使用除法的情况下进行更快的操作。通过将 Z 设置为 X 和 Y 的和，然后检查它是否小于或大于 N，程序可以返回 Z（如果它在范围内）或 Z 减去 N 的结果以将其带回范围内。该程序使用与 minimum 类似的逻辑，并且有一个不可预测的分支，可能导致分支预测错误。给出的另一个示例是一种使用位操作将值四舍五入到最接近的二的幂的方法，方法是递减 N，执行按位或操作，将 N 右移不同的值，然后在最后递增。
00:40:00 在视频的这一部分，演讲者讨论了两个位操作问题。第一个问题涉及找到大于给定值 n 的最小的 2 次幂。演讲者解释了如何通过使用位操作和递减 n（如果它已经是 2 的幂）来实现这一点，以确保设置 n 减去一位的对数。第二个问题涉及计算单词 X 中最低有效位的掩码，演讲者解释了如何通过将结果设置为 X 并使用带负数 X 的按位与运算来实现此目的。演讲者还提供了查找索引的代码通过将 X 乘以一个常数并在表中查找结果来计算该位。该部分以演讲者表演涉及位操作的数学魔术结束。
00:50:00 在本节中，我们了解 de Bruyne 序列及其与计算 2 的幂的对数底数 2 的相关性。de Bruyne 序列是一个循环位序列，其中长度为 K 的每个可能位串都恰好出现once 作为序列中的子字符串。使用转换表，我们可以将 de Bruyne 序列常数乘以 2 的幂并提取出现在序列开头的子字符串以计算 2 的幂的对数基数 2。通过左移序列然后查找向上转换表中子字符串的起始位置，我们可以确定我们开始的整数的对数基数 2，这解决了之前演示的卡片技巧。
00:55:00 在本节中，演讲者讨论了 de Bruijn 序列，这是一个二进制字母表的循环序列，其中包含每个可能的 n 位字符串恰好一次。该序列可用于解决诸如 N Queens 问题之类的问题，并且可以使用魔术生成。演讲者还解释了位技巧如何确定 de Bruijn 序列左移后子串的位置。这个位技巧的性能受到乘法和查表性能的限制，但现在有一个硬件指令来计算它。
01:00:00 在本节中，演讲者讨论了 N 皇后问题，该问题涉及将 N 个国际象棋皇后放在 NxN 棋盘上，以使两个皇后之间不会相互威胁。该问题通常使用回溯来实现，其中皇后逐行放置，当找不到有效位置时程序回溯。还讨论了棋盘的不同表示，最紧凑的是一组三位向量。下向量存储每列中皇后的存在，左对角向量存储每条左对角线上皇后的存在，右对角向量存储每条右对角线上皇后的存在。使用位向量可以更有效地实现算法。
01:05:00 在本节中，描述了使用位向量检查在 n 皇后问题中放置皇后的位置是否安全的过程。三项检查涉及检查是否已经有与该位置在同一行、同一列、同一对角线上的皇后。这种方法是有效的，并保证如果女王通过所有三项检查就可以安全放置。另一个讨论的问题是人口计数，它涉及计算一个字 X 中 1 位的数量。提出的方法重复消除 X 中的最低有效 1 位直到它变为零，所需的迭代次数与次数成正比X 中的 1 位。
00:05:00 在本节中，演讲者解释说汇编和机器代码在结构上非常相似，汇编中的 OP 代码对应于机器代码中的特定位模式。演讲者介绍了程序 ABS，它可以生成机器代码的反汇编，揭示助记的、人类可读的汇编代码。演讲者然后讨论了为什么有人可能想要查看汇编代码的几个原因，包括揭示编译器做了什么和没有做什么、调试编译器错误以及在无法访问其源代码的情况下对程序进行逆向工程。
00:10:00 在本节中，演讲者解释了对课程的期望，包括理解编译器如何使用 x86 指令实现语言结构，能够阅读 x86 汇编语言，以及理解常见汇编模式的性能影响。如有必要，学生还应该能够从头开始编写代码，并掌握到可行的水平。演讲者随后深入探讨了 x86 64 位指令集架构，包括寄存器、指令、数据类型和内存寻址模式。关键寄存器包括通用寄存器和标志寄存器，它跟踪算术运算和进位。指令指针通过汇编语言程序中的指令序列引导硬件。
在这部分视频中，讨论了理解 C 语言对汇编语言的重要性，以及如何使用编译器以汇编语言实现 C 代码。重点特别在于 LLVM IR 如何在 Linux x86 64 调用约定中转换为程序集。演示者解释了 LLVM IR 的基本组件以及 C 编程语言中的结构如何转换为 LLVM IR。该视频还涵盖了虚拟内存的布局、多个函数之间协调函数调用的问题，以及 Linux x86 64 调用约定使用两个指针（BP 和 SP）来管理所有堆栈帧。
该视频还解释了在 C 语言到汇编编程中维护寄存器状态的策略，例如将寄存器保存为调用者保存或被调用者保存，以及 x86 调用约定如何避免浪费工作。它涵盖了函数调用在 C 和汇编中的工作方式，讨论了将参数和局部变量保存到堆栈的过程，以及使用堆栈指针而不是基指针的常见优化。该视频还展示了将 LV miR 编译为汇编代码的过程，讨论了函数序言、保存寄存器、处理条件以及使用控制流图将 C 代码转换为汇编代码。最后，它讨论了用于在返回结果之前恢复寄存器的函数结语。
00:00:00 在这部分视频中，TB Shuttle 讨论了理解 C 语言对汇编语言的重要性。他指出，汇编语言提供了比 C 代码更高的精度，并且可以揭示 C 代码中不明显的程序细节。查看汇编还可以让开发人员确定编译器在优化程序时做了什么或没有做什么。此外，可能会出现错误，这些错误只会在特定级别优化代码时产生意外行为，从而难以发现这些错误。最后，了解汇编可以让开发人员手动修改汇编代码或对代码进行逆向工程。
00:05:00 在本节中，视频讨论了如何通过使用编译器以汇编语言实现 C 代码，编译器必须就使用哪些汇编指令、如何实现 C 条件和循环以及如何协调函数调用。为了解翻译过程，该视频介绍了 LVM IR，这是编译器用来推理程序的简化程序集。然后，该视频解释了 C 编程语言中的结构（例如函数、条件和循环）如何转换为 LVM IR。本节最后简要介绍了 LVM IR 属性。
00:10:00 在本节中，重点是 LLVM ir 如何转换为程序集的过程，特别是在 Linux x86 64 调用约定中。演示者简要介绍了 LLVM ir，解释了其函数、指令和寄存器的基本组成部分，类似于更简单版本的汇编。 LLVM ir寄存器类似于c变量，以名称区分，每个函数都有自己的本地寄存器名称。演示者在示例代码片段中突出显示了寄存器，并指出在引用 LLVM 中的不同基本块时，寄存器的语法被劫持了。演讲最后以一个案例研究结束，该案例研究介绍了此过程如何使用简单代码来计算斐波那契数列。
00:15:00 在本节中，演讲者解释了 LV Mir 指令的语法，其中包括寄存器名称、等号、操作码和操作数列表。虽然一些指令返回一个存储在本地寄存器中的值，但其他指令则不会。 LV Mir 指令集比 x86 的指令集小，因为它只包含少量用于数据移动、算术和逻辑运算以及控制流的指令。在 LV Mir 中，一切都作为类型公开，包括整数（具有定义的位数）、浮点类型、指针类型、向量类型和基本块的标签类型。演讲者还提到 LV Mir 向量运算看起来不像 SSE 或 AVX，而更像是对向量类型起作用的普通运算。
00:20:00 在本节中，视频讨论了如何将 C 代码中的操作序列转换为 LLVM IR，以及在 IR 中解释代码的经验法则。该摘录还解释了 LLVM IR 如何处理基本类型和聚合类型，例如数组和结构，并展示了访问数组中的元素如何涉及计算内存中地址的示例。此外，该视频还解释了如何将 C 函数转换为 LLVM IR，以及两种语言的相应返回语句。
00:25:00 在本节中，视频解释了 C 中的函数和参数如何转换为 LV Mir。 LV Mir 中的函数类似于 C 中的函数，但 C 参数在 LV Mir 中变成了参数列表。然而，读取 LV Mir 可能具有挑战性，因为寄存器名称不明确，因此难以破译。该视频还讨论了 LV Mir 中的基本块，这些块是根据控制流指令划分的代码块。基本块之间的连接基于分支指令引起的边。最后，该视频介绍了 LV Mir 中的条件语句，其中 if-then-else 语句成为条件分支指令，可引发基本块和控制流边缘。
00:30:00 在本节中，视频解释了条件操作和分支在 LLVM IR 中的工作原理。该过程从字面值与存储在寄存器中的值之间的比较开始，这将创建一位整数或布尔结果。然后将此结果连同两个基本块标签一起传递给条件分支操作，这两个标签指示如果谓词为真或假则去哪里。如果存在带一个操作数的无条件分支，则结果是直接跳转到特定的基本块。该视频还展示了如何在存在条件语句时在控制流图中创建菱形，并提供了一个用 C 代码编写的循环示例。
00:35:00 在本节中，视频讨论了 C 循环的组件，其中包括循环体和循环控制。循环体在每次迭代时执行，而循环控制管理循环的所有迭代。 AC 循环在控制流图中产生循环模式，进而在 LLVM ir 中创建循环结构。然后视频分析了循环控制的LLVM ir代码，其中有一个奇怪的fie指令，在处理循环时经常出现。 fie 指令试图解决代码的 LLVM 表示的问题，其中 I 由一大堆不同的寄存器表示，使我不清楚我实际去了哪里。
00:45:00 在视频的这一部分，重点是 LLVM IR，它类似于汇编，但在很多方面更简单，因为所有计算值都存储在寄存器中，就像普通的 C 变量一样。 LLVM IR 使用静态单一赋值范式，其中每个变量最多由一条指令写入。该视频介绍了如何将 C 代码转换为 LLVM IR，然后再转换为汇编，过程中还有一些额外的复杂性。编译器选择 LLVM IR 操作所需的实际汇编指令，决定使用哪些通用寄存器，并协调不同源文件和二进制库之间的函数调用。然后讨论转向 Linux x86 64 调用约定。
00:55:00 在视频的这一部分，演示者讨论了跨多个函数协调函数调用的问题，其中一些函数可能来自不同的文件或库。为了确保所有函数都能很好地协同工作，已经建立了所有函数都必须遵守的调用约定。 Linux x86 64 调用约定使用两个指针——BP 和 SP——来管理每个函数实例化的所有堆栈帧。执行call指令时，将IP的当前值作为返回地址压栈，call指令跳转到程序内存中某个函数的地址。返回指令撤消调用指令的操作，并将返回地址弹出堆栈以返回到调用者的执行。为了处理多个函数想要使用相同寄存器的问题，调用约定详细说明了每个函数可以使用哪些寄存器的规则，以及它们必须如何通过函数调用保留这些寄存器。
01:00:00 在本节中，视频讨论了在 C 到汇编编程中使用不同函数操作时维护寄存器状态的策略。它提到了可以使用的两种方法，一种是调用者在调用之前保存寄存器状态，另一种是被调用者保存所有寄存器状态。 x86 调用约定涉及两者，将一些寄存器指定为 callee-save，将其他寄存器指定为 caller-save 以避免浪费工作。该视频还探讨了堆栈内存的组织方式以及堆栈向下增长的方式。最后，它讨论了协调函数将如何使用堆栈内存的重叠部分。
01:05:00 在本节中，视频讨论了函数调用在 C 语言和汇编语言中的工作原理。在调用函数 C 之前，函数 B 将函数 C 的非寄存器参数放置到其局部变量下方其自己的堆栈内存中的保留链接块中。它将访问那些具有负偏移量的参数。当函数 C 启动时，它执行一个函数序言，它保存 B 的堆栈帧的基指针并将 BP 设置为 SP，因为它正在进入一个新帧。然后它在堆栈上为它自己的局部变量分配空间，以及 B 将用于它为其调用者或它所调用的事物创建的任何链接块的空间。该视频还提到了一个常见的优化，其中编译器可能会摆脱 BP 并根据堆栈指针 RSP 进行所有索引以获得更多的通用寄存器。
01:10:00 在本节中，讲师将带领观众完成将 LV miR 编译为汇编代码的过程。第一步涉及使用一些汇编程序指令（例如全局 fib 指令和对齐）将函数“fib”定义为全局可访问函数。然后，函数序言保存了一个 var BP 的推送队列和一个 RSP rbp 的 mob 队列。在将参数移至函数 RTI 之前，汇编代码还将几个寄存器压入堆栈，它们是 Kali 保存寄存器，并将其松鼠到 RBX 寄存器中。最后，评估一个比较指令以检查 N 的值是否小于二，如果是，则返回输入值。否则，它会通过一些直线代码来计算 n 减一的 fib 和 n 减二的 fib，将它们相加并返回结果。
00:20:00 计算 dag 中的顶点类型：初始链、延续链、函数调用链和最终链。 initial strand 包含要执行的第一条指令，final strand 包含程序中执行的最后一条指令。延续链代表生成操作的延续，而函数调用链代表函数调用的执行。重要的是要注意计算 dag 在执行期间动态展开并且不受处理器影响，这意味着运行时系统会弄清楚如何在运行时将任务映射到处理器。总之，计算 dag 是理解程序的并行性和并发性的强大工具。
00:25:00 在本节中，我们将了解计算 dag 以及如何使用它们来分析程序中的并行性。计算 dag 表示程序不同部分之间的依赖关系，具有不同类型的边，包括生成边、调用边、返回边和继续边。可以使用计算 dags 来分析程序中有多少并行度，我们使用 Amdahl 定律来量化并行度。在提供的示例中，需要顺序执行的节点少于七个，表明计算中存在一定程度的并行性。
00:30:00 在本节中，介绍了阿姆达尔定律的概念，作为确定并行处理中可能的最大加速比的一种方法。确定程序的串行部分为 3/18，导致最大加速比为 6。虽然 Amdahl 定律提供了并行度的上限，但在实际情况下往往过于宽松。引入了工作法则和跨度法则作为并行性的替代定义，其中工作法则表明 P 个处理器上的执行时间大于或等于程序的工作除以 P，而跨度法则表明执行时间P 个处理器上的执行时间至少是无限数量的处理器上的执行时间。在许多情况下，这些法则提供了比阿姆达尔法则更好的最大加速上限。
00:35:00 在本节中，演讲者讨论了如何组合不同计算的工作量和跨度量。他们解释说，当执行两个并行计算时，工作仍然是单个计算的工作总和，跨度是单个计算跨度的最大值。演讲者还定义了 P 处理器的加速，并讨论了次线性、线性和超线性加速。他们指出，最大可能的加速等于计算的并行度，即计算中每步的平均工作量。总的来说，本节提供了对计算的组成以及如何衡量它们的并行性的深入了解。
00:40:00 在本节中，演讲者使用计算 DAG 和并行快速排序算法等示例讨论如何分析计算的工作量和跨度以计算最大并行度。演讲者介绍了 Silk Scale 可扩展性分析器，它使用编译器工具来分析程序的串行执行并推导出程序并行加速的上限。演讲者还提到，手动分析大型计算的并行性可能很乏味，但 Silk Scale 可以帮助解决这个问题。
00:45:00 在本节中，视频讨论了运行并行计算并生成显示观察到的加速的图表的结果，以及跨度和工作定律的界限。该图显示最大加速比约为 5，表明程序中的并行度较低。分析表明，并行的瓶颈是按顺序执行分区函数，并行版本的快速排序的预期工作量和跨度为 n log n 量级。能达到的最大并行度是log log n的量级，不是很高。为了增加并行度，分区函数必须并行化。
00:50:00 在本节中，演讲者讨论了在分区和合并排序算法中实现并行性以实现显着加速的重要性。这些算法的并行版本具有 log 平方 n 的总跨度和 n 超过 log n 的高并行度。此外，还有许多其他实用的并行算法，它们具有高并行性和渐近等于相应顺序算法的工作界限。演讲者还介绍了调度理论的概念，解释了集中式调度器可以在运行时将计算 DAG 映射到可用的处理器上，而分布式调度器用于 Silk 编程。一个贪婪的调度器，它在计算的每一步都做尽可能多的事情，作为一个例子。
00:55:00 在本节中，引入了贪婪调度器的概念，它在当前时间步执行尽可能多的工作，而不考虑未来。定义了一个完整的步骤，其中至少 P 条链准备就绪，以及一个不完整的步骤，其中少于 P 条链准备就绪。 Ron Graham 于 1968 年首次展示的著名定理指出，贪婪调度程序实现的时间界限小于或等于 T1/P + T 无穷大，其中 T1 是工作，T 无穷大是跨度。提供了该定理的证明，并表明任何贪婪调度程序都可以在最佳运行时间的两倍内实现。
01:05:00 在本节中，演讲者讨论了处理器中的生成和并行性的概念。他们解释说，当处理器调用一个函数时，它会将函数的帧放在堆栈的底部，并可以在堆栈底部生成帧。多个进程可以并行发生，并且可以从生成和调用中返回。当工人没有工作可做时，他们会从另一个处理器的甲板上偷东西。著名的定理指出，工人很少偷窃，从而提供近乎线性的加速。演讲者还指出，Silk 支持 C 的指针规则，其中指向堆栈空间的指针可以从父级传递给子级，但不能从子级传递给父级。
01:10:00 在视频的这一部分，演讲者讨论了 Cactus 堆栈，这是 Silk 程序的祖先计算图中的任务可以看到的堆栈。这个栈允许并行的栈的多个视图，这使得并行函数调用成为可能。演讲者解释说，Silk 程序所需的堆栈空间可以通过将程序的串行执行所需的堆栈空间 (S sub 1) 乘以将使用的处理器数 (P) (S子 P ≤ P x S 子 1)。演讲者提供了这一概念的高级证明，并指出 P 处理器执行所需的堆栈空间上限通常比实际需要的数量要宽松得多，因为每个处理器可能不需要每次都沿着计算图向下移动它窃取工作的时间。
本视频讨论了分析分而治之递归的主要方法，并将其应用于多线程算法，方法是将 n 的对数基数 B 与 A 的对数基数 B 与 N 的 F 进行比较，以确定它们在 n 中的增长和所需的工作量。该视频展示了一个包含基本多线程算法解决方案的备忘单，涵盖了工作和跨度分析、工作效率以及通过粒度优化克服间接成本等主题。强调了在交流技术主题时同理心的重要性，并引入了 DAG 的概念作为平衡工作和跨度以增加并行性和减少运行时间的手段。
00:05:00 在本节中，演讲者解释了在评估多线程算法时如何确定 n 的增长和所需的工作量。关键是将 n 的对数 B 与 A 的对数 B 和 N 的 F 进行比较。演讲者涵盖了三种可能的情况，第一种是当对数 B n 远大于 n 的 F 时。在这种情况下，权重的常数部分在叶子中，导致答案为 n 到 A 的对数底数 B。第二种情况是当对数底数 B n 近似等于 n 的 F 时。为此，您添加了一个额外的日志，答案是 n 到日志的日志基数 B 到 n 的 k 加 1。最后，第三种情况是当对数基数 B 远小于 N 的 F 时，这意味着 F 必须满足正则性条件，他们将要查看的所有函数（如多项式和对数）都满足该条件。
00:15:00 在本节中，演讲者讨论了 Aqua Bazi 方法以及它如何比 master 方法更复杂，这足以分析大多数程序。然后，他们提供了一个并行循环示例，其中包含外部循环并行化的就地矩阵转置代码。演讲者强调了正确定义迭代空间和负载平衡对于高效并行处理的重要性。他们还解释了 open silk 编译器和运行时系统如何实现循环。
00:20:00 在本节中，演讲者描述了一个循环的递归程序，该循环利用分治法将循环分成两部分，并在每一侧递归调用自身，直到达到单元素迭代。这个计算的工作量是按照工作量和跨度来分析的，叶子的工作量是 n 次方的平方，上面的部分是 theta n，因为从叶子到根的每一层只有 n 个节点。 open silk 运行时系统没有循环原语，因此循环有效地转化为这种并行的分而治之方法。
00:25:00 在本节中，演讲者讨论了多线程算法的工作和跨度分析。他解释说，总功是 Θ(n²)，因为对完整二叉树的 n 个叶子中的每一个都进行了恒定的工作。循环控制的跨度是log(n)，这意味着无限多的处理器可以在对数时间内完成任务。但是，由于计算 (n) 中存在线性分量，因此总跨度为 Θ(n)。因此，并行度为 Θ(n)，这对于大多数实际系统来说是一个很好的数量。然后演讲者探讨了内循环也被并行化的场景，并讨论了由此产生的工作量。
00:35:00 在本节中，强调了在涉及技术主题时同理心在交流中的重要性。教授鼓励学生对课堂上可能不熟悉所涵盖材料的其他人要有耐心。继续对多线程算法进行分析，提出了向量加法的分而治之算法，发现并行度为 n over log n。讨论了并行度和处理器数量之间的关系，教授强调虽然更多的并行度看起来更好，但它只在特定阈值内有益。
00:40:00 在本节中，演讲者讨论了如何优化多线程算法中的一些开销，特别是子程序调用开销。他们引入了“粒度”的概念，这向编译器建议在分而治之过程的叶子上每个块最多有 G 个元素。这允许子例程开销在 G 迭代中分摊，而不是仅仅分摊一次，从而获得更好的性能。如果未指定粒度，系统会做出最佳猜测以最小化开销。演讲者分解变量 I、G 和 s 来分析此上下文中的工作，并将其与没有并行控制内容的原始代码中的工作进行比较。
00:50:00 在本节中，演讲者讨论了多线程算法的分析，特别是 DAG（有向无环图）的概念以及它如何影响算法的路径。他们强调 DAG 的不同子树之间需要独立，以允许并行处理。目标是平衡算法的工作量和跨度，因为这两个因素的作用方向相反。关键是让 G（并行量）比 I（算法的顺序部分）大得多，这样可以减少开销并加快处理速度。演讲者还提到了这个概念的实现，但指出它将在讲座系列的后面讨论。
00:55:00 在本节中，演讲者介绍了使用 for 循环将两个向量相加的多线程算法的实现。该循环使用一个称为 V add 的运算符来执行串行向量加法，并且该循环使用大小为 G 的向量在 G 组中产生加法。假设 G 等于 1，则循环的工作是 n 阶，跨度也是订单并行度是通过工作与跨度的比率来衡量的，即 n 除以 n，简化为 1。演讲者强调分析多线程算法的目标是增加并行度并减少跨度以最小化运行时间，并强调了技术称为条带挖掘，其中长度为 N 的循环被双嵌套循环取代以并行计算，作为改进多线程算法的一种方法。
01:05:00 在本节中，演讲者讨论了在多线程算法中使用分而治之策略，建议不要一个接一个地产生大量小任务，除非它们被分成几个任务，在这种情况下，开销很好。通常，应该采用分而治之的方法，其中分配给线程的任务数量足够大。演讲者警告要注意调度开销，并建议并行化外循环而不是内循环，后者有更多的开销。此处提供的示例代码显示了一个高效的代码，其中调度只发生一次，而一个糟糕的代码，其中开销发生 n 次。矩阵乘法用作多线程算法的示例，该算法使用分而治之策略将 n 乘以 n 矩阵，方法是对 n 乘以 2 x n 超过 2 个矩阵进行 8 次乘法，然后将两个 n 乘 n 矩阵相加。
01:10:00 在本节中，演讲者讨论了如何在二维编码和索引中表示子矩阵，尤其是 C 和 Fortran 等语言的行主顺序和列主顺序。其思想是，每个二维矩阵都可以作为一维矩阵进行索引，在处理子矩阵时，需要加上长矩阵的行数和长度，才能知道IJ元素在哪里。此外，在实施分而治之时，了解四个子矩阵中每一个的起始角是至关重要的。最后，演讲者强调在分治矩阵乘法代码中使用“restrict”来告诉编译器哪些元素可以或不可以别名。
01:15:00 在本节中，演讲者讨论了矩阵乘法的多线程算法。该算法基于将矩阵递归细分为更小的子矩阵，每个子矩阵递归相乘以获得最终结果。演讲者强调了一个快速确定 n 是否为 2 的幂的小技巧，并使用宏来简化矩阵的索引。该算法表现出高并行性，可以减少并行性以提高性能。还提到了其他类似的算法。
00:00:00 在本节中，演讲者讨论了他以前的一位学生所做的关于排序代码的研究。该代码使用 time.h 头文件来访问用于计时测量的时钟获取时间例程。排序例程是定时的，经过的时间被计算并打印出来。测得的运行时间图表显示，排序例程主要遵循 N log N 增长，但即使对于最大的数组，测得的时间也很慢。
00:35:00 在本节中，演讲者讨论了微小的变化如何对程序的性能产生巨大的影响。例如，插入一个字节可能会导致它之后的所有内容受到线性影响，并且更改点 o 文件在链接器命令行上出现的顺序可能比在 -OH- 和 -O3 之间移动产生更大的影响。为了解决这些问题，编译器正在识别问题并进行更多调整。 LLVM 有开关可以对齐一个函数中的所有函数和块，但是对齐会减慢程序的速度。此外，程序的名称会影响其速度，因为可执行文件的名称最终出现在最终出现在调用堆栈上的环境变量中。
00:40:00 在本节中，演讲者讨论了用于测量软件性能的各种工具和方法，包括使用 time 命令从外部测量程序，使用 clock get time 或其他方法将计时调用放入程序中，使用 gdb 中断程序确定哪个例程花费的时间最多，利用硬件和操作系统支持（例如 perf 工具集中使用的支持）或模拟程序以获得更深入的理解，但速度较慢。演讲者解释了使用 time 命令时经过的时间、用户时间和系统时间之间的差异，以及由于处理器分配的原因，它们加起来可能不等于总时间。
00:45:00 在本节中，演讲者讨论了不同类型的计时和测量，包括挂钟时间、处理器在用户模式下花费的时间以及在内核中花费的时间。推荐使用的计时调用是带有时钟单调选项的时钟获取时间，它保证永远不会向后运行。虽然它可能需要不确定的时间来运行，但它比 RTIDTSC 等其他计时器更可靠，后者可能会在不同的内核上给出不同的答案，并且可能会向后运行。演讲者警告不要使用 get time of day。
00:50:00 在本节中，演讲者讨论了在编程中测量和计时事件的各种方法，包括使用 clock_gettime 和使用 time 命令进行测量。他们警告说，随着时间的推移，技术可能会发生变化，工程师可能需要适应。演讲者还建议将随机中断代码作为一种简单的分析技术，并提到 Facebook 等大公司使用这种方法。此外，演讲者介绍了硬件计数器和库 livepFM4 的概念，它允许在每个进程的基础上访问这些计数器。他们强调，工程师可能并不总是需要外科手术般精确的工具，有时一个简单的工具就足以完成这项工作。
01:05:00 在本节中，讨论了各种类型的汇总统计数据，包括均值，它可以在不同情况下提供有用的绩效衡量标准。在评估 Web 服务器时，可以使用算术平均值来衡量 CPU 利用率和总任务完成时间，而挂钟时间和百分位行为可能与优化请求满意度更相关。然而，在总结比率时，例如比较程序 A 和 B 的性能，采用算术平均值并不是一种有效的方法，尽管它经常被误用。这是因为比率的平均值与比率本身不同，如视频中给出的示例所示。
01:15:00 在本节中，演讲者讨论了衡量和比较绩效的不同方法。一种方法是比较 10% 最便宜的选项并进行降噪以比较均值，尽管它可能无法提供确凿的证据。或者，可以在 A 和 B 之间进行面对面比较，看看哪一方获胜的频率更高。通过这个，可以检验原假设，并可以计算p值来判断偏差是否显着。这种方法常用于社会科学，在嘈杂的环境中也很有用。最后，演讲者简要介绍了拟合模型以得出统计数据的想法，并讨论了最小二乘近似的使用。
MIT 6.172 软件系统性能工程，2018 年秋季 - 1. 简介和矩阵乘法
一、简介与矩阵乘法
在这个名为“1. 介绍和矩阵乘法”的 YouTube 视频中，讲师讨论了性能工程的重要性以及它是如何随着时间的推移而演变的。演讲者以矩阵乘法为例，展示了编码技术和机器规格如何极大地影响性能。讨论涵盖循环顺序、高速缓存使用和并行编程等主题。演讲者还探讨了针对不同处理器和算术计算优化代码的方法。总的来说，该视频提供了对性能工程领域及其在现代计算系统中的实际应用的宝贵见解。
第 2 讲。Bentley 工作优化规则
2. 优化工作的 Bentley 规则
这段 YouTube 视频讨论了计算机程序的各种优化技术。介绍了用于优化工作的 Bentley 规则，并将优化分为数据结构、循环、逻辑和函数。讨论了编码值、数据结构扩充、预计算、缓存和利用稀疏矩阵等不同技术。演讲者还谈到了在图形程序中使用稀疏矩阵表示的好处、逻辑优化和碰撞检测优化。实施这些优化技术有助于减少程序的运行时间，从而提高它们的效率。
视频的第二部分涵盖了几类优化技术，包括循环提升、循环中哨兵的使用、循环展开和融合以及函数内联。演讲者反对过早优化，并强调保持正确性和使用回归测试的重要性。该视频还概述了 Bentley 工作优化规则，这是一个提高生产力和高效实现目标的六步指南。这些规则包括建立明确的目标、分解任务、计划和组织、确定任务的优先级、尽量减少干扰，以及定期审查和调整自己的方法。
第 3 讲 Bit Hacks
3. 位黑客
这个 YouTube 视频涵盖了各种位操作主题，包括二进制表示、二进制补码、按位运算符、不使用临时变量交换变量以及代码优化。该视频演示了各种位技巧，例如在不使用 if-else 语句的情况下找到两个整数中的最小值，以及如何在不使用临时变量的情况下交换两个整数。演讲者讨论了不可预测的分支，并介绍了可预测分支不可用时的无分支最小位技巧，并展示了位黑客如何通过用简单的按位运算代替除法等代价高昂的运算来优化代码。该视频还讨论了 de Bruijn 序列及其在解决 N Queens 问题等问题中的应用。
第二部分讨论使用位向量解决 N Queens 问题，并有效地计算二进制字中 1 的位数。回溯用于实现 N Queens 问题，位向量用于高效表示棋盘。描述了在 N Queens 问题中安全放置皇后的三个检查，并提出了一种通过递归消除最低有效 1 位来计算一个字中 1 位的数量的方法。此外，还讨论了使用查表和寄存器操作来计算 1 位的数量。视频以分治法的演示结束，该方法计算 1 位，其性能与字长的对数基数成正比。还提供进一步学习的资源。
第 4 讲 汇编语言与计算机体系结构
第 4 讲 汇编语言与计算机体系结构
该视频全面概述了汇编语言和计算机体系结构。汇编语言是优化代码性能的重要接口，了解计算机体系结构对于掌握汇编语言至关重要。演讲者讲解了x86 64 架构的历史和发展，它的关键寄存器、数据类型、内存寻址模式和指令集架构，包括堆栈、整数和二进制逻辑、布尔逻辑和子程序。他们还讨论了零和符号扩展等扩展以及汇编语言中的各种寻址模式。此外，该视频还讨论了浮点类型、向量和向量单元、传统指令和 SSE 指令，以及超标量处理、乱序执行和分支预测等计算机体系结构设计功能。
该视频还涵盖了与汇编语言和计算机体系结构相关的几个主题。其中一个中心主题是指令级并行性 (ILP) 和流水线停顿，它们是由数据依赖性等危害引起的。演讲者讨论了真实、反和输出数据相关性，以及超标量处理器如何利用硬件中的更多并行性来一次执行多条指令。然而，为了避免危险，架构师已经实施了重命名和重新排序等策略，以及推测执行来猜测分支的结果并预先执行它。演讲者鼓励听众了解这些方法，以更好地理解软件优化。
第 5 讲 C 到汇编
第 5 讲 C 到汇编
在这部分视频中，讨论了理解 C 语言对汇编语言的重要性，以及如何使用编译器以汇编语言实现 C 代码。重点特别在于 LLVM IR 如何在 Linux x86 64 调用约定中转换为程序集。演示者解释了 LLVM IR 的基本组件以及 C 编程语言中的结构如何转换为 LLVM IR。该视频还涵盖了虚拟内存的布局、多个函数之间协调函数调用的问题，以及 Linux x86 64 调用约定使用两个指针（BP 和 SP）来管理所有堆栈帧。
该视频还解释了在 C 语言到汇编编程中维护寄存器状态的策略，例如将寄存器保存为调用者保存或被调用者保存，以及 x86 调用约定如何避免浪费工作。它涵盖了函数调用在 C 和汇编中的工作方式，讨论了将参数和局部变量保存到堆栈的过程，以及使用堆栈指针而不是基指针的常见优化。该视频还展示了将 LV miR 编译为汇编代码的过程，讨论了函数序言、保存寄存器、处理条件以及使用控制流图将 C 代码转换为汇编代码。最后，它讨论了用于在返回结果之前恢复寄存器的函数结语。
第 6 讲 多核编程
第 6 讲 多核编程
本视频讲座讨论了多核编程以及由于摩尔定律和时钟频率缩放结束而出现的多核处理器。演讲者解释了处理器面临的功率密度问题，以及它如何导致在芯片中添加多个内核以跟上摩尔定律。本讲座还涵盖了共享内存硬件和并发平台（如 Pthreads、TBB、OpenMP 和 Silk 等为并行编程提供抽象的缓存一致性协议）的基础知识。每个平台的优点和缺点都通过实施斐波那契程序的示例进行了讨论和演示。该视频全面概述了多核编程以及程序员面临的挑战和解决方案。
该视频还涵盖了 Silk 的各个方面，Silk 是一种用于处理并行处理的抽象工具。演讲者讨论的主题包括嵌套 silk for 循环、生成汇编代码、使用缩减程序进行缩减、调度程序以及性能优化。他们还概述了 Silk 生态系统和相关工具，例如 silk sanitizer 和 silk scale，分别用于调试和分析可扩展性。主要收获是为多核处理器编写并行程序可能具有挑战性，但 Silk 通过高效处理复杂任务简化了流程，让程序员更好地控制代码的执行。
第 7 讲 种族和并行性
第 7 讲 种族和并行性
该视频涵盖了与 Silk 编程中的竞争、并行性和计算障碍相关的一系列主题。涵盖的一些关键概念包括用于并发执行的 spawn 和 sync 语句、避免竞争条件的重要性以及使用 Silk 的竞争检测器来识别它们。该视频还介绍了阿姆达尔定律、工作定律和跨度定律，作为量化程序中并行度的方法，以及分析工作和计算跨度的方法。还讨论了并行排序算法的潜在加速和并行性以及调度理论的概念，重点是贪婪调度定理。总体而言，该视频为了解和优化 Silk 编程中的程序性能提供了宝贵的见解。
该视频解释了贪婪调度器边界的推论，它本质上表明只要 T1/Tinfinity 大于或等于 P^2，任何贪婪调度器都能实现近乎完美的线性加速。 silk scheduler，采用work stealing scheduler，只要处理器数量远少于T1/Tinfinity，就可以实现近乎完美的线性加速。 Silk 运行时系统通过维护准备好的链的工作平台来工作，并像堆栈一样操纵平台的底部。该视频还讨论了 Cactus Stack，它允许并行查看堆栈的多个视图，并使并行函数调用成为可能。 P 处理器执行所需的堆栈空间上限通常比实际需要的数量要宽松得多，因为每个处理器可能不需要在每次窃取工作时都沿着计算图一路走下去。
第 8 讲 多线程算法分析
第 8 讲 多线程算法分析
本视频讨论了分析分而治之递归的主要方法，并将其应用于多线程算法，方法是将 n 的对数基数 B 与 A 的对数基数 B 与 N 的 F 进行比较，以确定它们在 n 中的增长和所需的工作量。该视频展示了一个包含基本多线程算法解决方案的备忘单，涵盖了工作和跨度分析、工作效率以及通过粒度优化克服间接成本等主题。强调了在交流技术主题时同理心的重要性，并引入了 DAG 的概念作为平衡工作和跨度以增加并行性和减少运行时间的手段。
该视频还讨论了多线程算法的分析，重点关注工作和跨度，以及如何在最小化跨度的同时最大化并行度以实现近乎完美的线性加速。演讲者建议对多线程算法采用分而治之的方法，其中分配给线程的任务数量足够大，并警告不要因调度开销而产生大量小任务。提供的示例代码包括一个有效的代码和一个糟糕的代码。演讲者还讨论了如何在二维编码和索引中表示子矩阵，并强调在分治矩阵乘法代码中使用“限制”来提高性能。
第 9 课 编译器能做什么和不能做什么
第 9 课 编译器能做什么和不能做什么
该视频讨论了编译器如何使用各种示例来优化代码。它解释了编译器如何消除不必要的存储和内存引用，以及它们如何优化循环以提高性能。
该视频还解释了编译器优化过程的概念，以及如何使用它们来提高代码性能。它还讨论了编译器的局限性，特别是在矢量化方面。如果编译器可以确定代码中的指针不会别名，则它们只能对代码进行矢量化。如果指针做别名，编译器将无法向量化代码。作为一名程序员，您可以通过注释您的指针来帮助编译器提供有关它们使用的更多信息。
第 10 讲 测量和定时
第 10 讲 测量和定时
在此视频中，演讲者讨论了计算中测量和计时的各个方面，包括可能影响准确性的外部因素。他们强调需要模型和对数据的清晰理解，减少方差以补偿错误，并使用适当的定时调用来确保可靠性。他们还讨论了准确测量软件性能的挑战，例如幂律和非确定性因素，同时重点介绍了性能建模、定时调用、硬件计数器和模拟器等工具。最后，他们告诫不要依赖单一工具，建议将三角测量和适应作为确保准确结果的技术。
演讲者解释了可靠的性能测量在性能软件工程中的重要性。他建议使用统计数据来准确衡量绩效，并讨论了各种类型的汇总统计数据，例如均值，它们可以在不同情况下提供有用的绩效衡量标准。他指出，取比率的算术平均值不是一种有效的方法，并建议改用几何平均值。演讲者强调了在比较程序时选择正确的数据聚合方式的重要性，并建议从多次运行中取低阶统计量，例如最小值或 10%，以更准确地比较性能。演讲者还讨论了衡量和比较性能的不同方法，包括直接比较和拟合模型以得出统计数据，但警告了建模中的过度拟合问题。总的来说，该视频强调了可靠的性能测量对于提高程序性能的重要性。