软件性能工程

这门课涵盖与软件性能工程相关的各种主题。

前置学习内容

• 软件构造基础
• 编程基础

课表

主题

• Lec 1 矩阵乘法

• Lec 2 Bentley Rule

• Lec 3 比特运算技巧

• Lec 4 汇编语言和计算机体系结构

• Lec 5 C 到 汇编（基于 LLVM）

• Lec 6 编译器能做什么和不能做什么

• Lec 7 多核编程

• Lec 8 竞态和并行

• Lec 9 多线程算法分析

• Lec 10 测量和计时

• Lec 11 存储分配

• Lec 12 并行存储分配

• Lec 13 Cilk 运行时系统

• Lec 14 缓存和高效缓存算法

• Lec 15 缓存参数无关算法

• Lec 16 不确定性并行编程

• Lec 17 无锁同步

• Lec 18 DSL 和自动调优

• Lec 19 西洋棋代码走读

• Lec 20 推测性并行

• Lec 21 TSP 问题

• Lec 22 图优化

• Lec 23 高性能动态语言——Julia

Lec 1 介绍&矩阵乘法

Lec 2 Bentley 程序优化的法则

本讲导览

• 数据结构层面
• 循环语句
• 逻辑语句
• 函数层面

lec2.md

Lec 3 比特运算技巧

Lec 4 汇编语言和计算机架构

如果你想写出更高效的代码，就必须了解计算机底层的工作原理。通过深入理解底层机制，你可以更好地利用计算机架构的优势。汇编语言提供了直接访问和控制计算机硬件的接口。掌握汇编语言不仅能让你编写出更高效的代码，还能帮助你理解高级语言在底层的实现方式，从而提升你的编程能力和效率。

本讲导览

• x86-64 ISA 基础
• 浮点数和矢量硬件
• 计算机架构总览

Lec4 入口

Lec 5 从 C 到汇编语言（基于 LLVM)

本节课我们将探讨如何 C 如何用 x86-64 的汇编实现的

本讲导览

• 复习

• LLVM 概述

• C 到 LLVM IR

  • 直线型 C 代码到 LLVM IR
  • C 函数到 LLVM IR
  • C 条件语句 到 LLVM IR
  • C 循环语句到 LLVM IR
  • LLVM IR 属性

• LLVM IR 到 汇编

  • Linux x86-64 调用约定

• 示例： Fib

lec5.md

Lec 6 编译器能做什么，不能做什么

在 Lec 5 我们介绍了从 C 语言如何经过 LLVM IR 生成汇编语言的，这节我们将探讨 LLVM IR 和汇编的

lec6.md

Lec 7 多核编程

本讲导览

• 共享内存硬件
• 并发平台
  • Pthread 库（和 WinAPI Thread）
  • 线程构建块
  • OpenMP
  • Cilk Plus

lec7.md

Lec 8 竞态和并行

本讲导览

• 确定性竞态条件
• 什么是并行？
• 扩展性分析：Cilkscale
• 调度理论
• Cilk 运行时系统

lec8.md

Lec 9 多线程算法分析

Schardl, Tao, William Moses, and Charles Leiserson. “Tapir: Embedding Fork-Join Parallelism into LLVM’s Intermediate Representation.” Proceedings of the 22nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (2017): 249–265.

本讲导览

• 分治法
  • 主定理
• Cilk 循环语句
• 矩阵乘法（TD）
• 归并排序（TD）

lec9.md

Lec 10 测量和计时

本节探讨如何可靠地测量软件的性能

本讲导览

• 静默系统（Quiescing System）
• 测量软件性能的工具
• 性能建模

lec10.md

Lec 11 存储分配

这节课关于内存的分配和释放。文献中就叫做 Storage Allocation

本讲导览

• 栈分配

• 堆分配

  • 固定大小分配
  • 变长分配

• 垃圾回收

  • 引用计数法
  • 标记-清除法
  • 停止-清除法

lec11.md

Lec 12 并行存储分配

本讲导览

• C 语言的内存分配
• 仙人掌栈

lec12.md

Lec 13 Cilk 运行时系统

本讲导览

• Cilk 回顾

• 功能分析

• 性能分析

• 双端工作队列的实现

• Spawning 计算

• Stealing 计算

• synchronizing 计算

lec13.md

Lec 14 缓存和高效缓存算法

深入缓存和介绍如何设计高效缓存的算法。

本讲导览

• 缓存硬件
• 理想的缓存模型
• 缓存感知算法
  • 分块矩阵乘法
• 缓存无关算法

lec14.md

Lec15 缓存无关算法

• Demaine, Erik. “Cache-Oblivious Algorithms and Data Structures” in Lecture Notes from the EEF Summer School on Massive Data Sets, BRICS (2002).
• Frigo, Matteo, Charles Leiserson, et al. “Cache-Oblivious Algorithms.” ACM Transactions on Algorithms (TALG) 8, no. 1 (2012): article no. 4.

本讲导览

• 热扩散模拟
• 缓存无关模型计算

lec15.md

Lec 16 不确定性并行编程

Leiserson, Charles. “A Simple Deterministic Algorithm for Guaranteeing the Forward Progress of Transactions.” Information Systems 57 (2016): 69–74.

不确定性并行编程非常恶心，相比并行编程而言（就是工作量和关键路径的把握）。不确定性就是因为多线程环境由于资源竞争，导致的数据争用，导致程序的不确定性。

本讲导览

• 确定性程序概念
• 互斥&原子性
• 锁的实现
• 锁的异常：死锁
• 事务性内存（TD）

lec16.md

Lec 17 无锁同步

阅读资料

• Leiserson, Charles. “A Simple Deterministic Algorithm for Guaranteeing the Forward Progress of Transactions.” Information Systems 57 (2016): 69–74.

本讲导览

• 顺序一致性

• 互斥的无锁实现

• 宽松内存一致性

  • 指令重排序

  • 硬件重排序

  • 重排序的影响

• 内存屏障

• CAS

• 无锁算法（LOCK-FREE ALGORITHMS）

• ABA 问题

lec17.md

Lec 18 DSL 和 自动调优

阅读资料

• GraphIt: A High-Performance Graph DSL, PACMPL'18'

• OpenTuner: An Extensible Framework for Program Autotuning, ICPAC'14

本讲导览

• DSL 介绍
• GraphIt
• Halide
• Opentuning

lec18.md

Lec 19 西洋棋代码走读

Lec 20 推测性并行 & 西洋棋

本讲导览

• 投机性并行
• 并行$\alpha-\beta$搜索
• Jamboree Search
• 西洋棋程序

Lec 21 旅行商问题

本讲导览

• Recursive Generaion 递归式生成
• The Traveling Salesperson Problem 旅行商问题
• A Sequence of TSP Algorithms TSP 算法的一种顺序
• Principles of Algorithm Engineering 算法工程原理

lec21.md

Lec 22 图优化

本讲导览

• 什么是图？
• 图的表示
• BFS 的实现
• 优化方法
  • 并行计算
  • 图的压缩和重排序

lec22.md

Lec 23 高性能动态语言——Julia

18.S096 | Matrix Calculus for Machine Learning and Beyond