实验说明

实验一：Cache Miss 模拟

基本要求

• 实验目标：手动编写矩阵相乘的代码，模拟 cache miss 过程，要求：
  1. 两个矩阵分别放在两个文件中。
  2. 在不同大小的 cache line 情况下，尝试不同矩阵大小的情况，采用不同的矩阵乘法方式（不同顺序），并统计 cache miss 的发生情况。
  3. 将模拟出来的结果与理论分析结果进行对比分析。

具体要求

• 模拟 cache miss，关注数据访问模式与内存缓存的相互作用。
• 使用不同的矩阵乘法顺序，分析不同顺序对缓存的影响。
• 对比模拟结果与理论值，评估不同参数下的性能变化。

实验二：外部归并排序

基本要求

• 实验目标：实现一个外部归并排序算法，要求：
  1. 待排序的序列和排序后的序列都要存放在文件中，不能一次性读入或写出，模拟内存较小但待排序文件很大的情况。
  2. 生成顺串（可以使用任何内部排序算法，此时，单个顺串大小应该设置为内存可以放得下的），生成的顺串写入文件。
  3. 归并顺串（可以用最简单的两两归并）。

可探索内容

• 不同顺串大小、不同的归并路数（k）对排序速度的影响。
• 记录 I/O 次数，分析外部排序的效率瓶颈。

实验三：改进的外部归并排序

基本要求

• 实验目标：改进实验二的外部归并排序算法，使用 loser tree 来生成更大的顺串以提高排序效率。要求：
  1. 只使用三个缓冲区（一个与 loser tree 通信，另外两个分别用于读写）。
  2. 必须输出顺串的大小。
  3. 使用哈夫曼树来确定最佳的归并顺序，可以两两归并，也可以 k > 2。这个归并顺序也要输出。
  4. 对比实验二的排序效率。

可探索内容

• 顺串的个数（例如，平均个数、最差情况下顺串的个数）。
• 不同归并顺序对结果的影响，哈夫曼树是否一定是最快的。

实验四：进一步改进的外部归并排序

基本要求

• 实验目标：进一步改进实验三的外部归并排序算法，探索如何使用更大的 k 进行归并。要求：
  1. 使用一个尽可能大的 k 进行 k-way merge。
  2. 继续使用 loser tree 进行归并。
  3. 每个顺串分配一个缓冲区，并为 loser tree 提供数据。
  4. 额外一个输入缓冲区挂在最快被消耗完的那个顺串的缓冲区后面。
  5. 剩下的 k-1 个缓冲区放在 pool 里面，随用随调。

可探索内容

• 跟实验三进行对比，看看更大的 k 是否带来性能提升。
• 不同的 k 选择进行对比，看看 k 越大，效率是否越高。
• 是否有进一步的优化空间来提升速度。