OSTEP-第十九章 · Auceptin's Blog

本次作业要测算一下 TLB 的容量和访问 TLB 的开销。这个想法参考了 Saavedra-Barrera 的工作[SB92]，他设计了一个简单而漂亮的用户级程序，来测算缓存层级结构的方方面面。更多细节请阅读他的论文。

基本原理就是访问一个跨多个内存页的大尺寸数据结构（例如数组），然后统计访问时间。例如，假设一个机器的 TLB 大小为 4（这很小，但对这个讨论有用）。如果写一个程序访问 4 个或更少的页，每次访问都会命中 TLB，因此相对较快。但是，如果在一个循环里反复访问 5 个或者更多的页，每次访问的开销就会突然跃升，因为发生 TLB 未命中。

问题：

为了计时，可能需要一个计时器，例如gettimeofday()提供的。这种计时器的精度如何？操作要花多少时间，才能让你对它精确计时？

写一个程序，命名为tlb.c，大体测算一下每个页的平均访问时间。程序的输入参数有：页的数目和尝试的次数

用你喜欢的脚本语言写一段脚本来运行这个程序，当访问量从1增长到几千，也许每次迭代都乘2。在不同的机器上运行这段脚本，同时收集相应的数据。需要试多少次才能获得可信的测量结果？

接下来将结果绘图

要注意编译器优化带来的影响。编译器做各种聪明的事情，包括优化掉循环，如果循环中增加的变量后续没有使用，如何确保编译器不优化掉你写的TLB大小测算程序的主循环

还有一个需要注意的地方，今天的计算机系统大多有多个CPU，每个CPU当然有自己的TLB结构。为了得到准确的测量数据，我们只需要在一个CPU上运行程序，避免调度器把进程从一个CPU调度到另一个去运行。如何做到？（提示，在Google上搜索“pinning a thread”相关的信息）如果没有这样做，代码从一个CPU移到了另一个，会发生什么情况？

另一个可能发生的问题与初始化相关。如果在访问数组a之前没有初始化，第一次访问将非常耗时，由于初始访问开销，比如要求置0。这会影响你的代码及其计时吗？如何抵消这些潜在的开销？

先考虑一下可能遇到的这些问题：对于计时，第六章的作业已经接触过，可以用rdtsc系统调用。脚本语言自然是我最熟悉的lua了，对于计时，也许可以继续使用C的系统调用，绘图有些麻烦，可能不像py那样方便。编译器的优化问题，可以在编译时指定-O0，查看汇编代码是否有不必要的优化。CPU调度的话，pin指令已经不陌生了。初始化问题，如果没有初始化，因为很多操作都是lazy的，访问时才分配物理内存，建立映射，就增加了额外的延迟

#include<stdio.h>
#include <x86intrin.h>
#define N 1000
#define PAGES 1000
#define MAX 17

int a[PAGES * (1<<MAX) + 1]; // +1好习惯
int main(){
  for(int i = 0; i < PAGES * (1<<MAX) + 1; i++){ //初始化
    a[i] = 0;
  }
    for (int i = 0; i < MAX; i++){    //改变步长
      unsigned long long start = __rdtsc();
      for (int j = 0; j < N; j++){    //重复多次以取平均值
        for (size_t k = 0; k < (PAGES * (1 << i)); k+=(1<<i)){
            a[k] += 1;
        }
      }
      unsigned long long end = __rdtsc();
      double time = (end - start) / N;
      printf("步长为%d,测量%d次取平均值，访问%d次平均用时为%lf时钟周期\n",1 << i , N ,PAGES, time);
    }
}

gcc tlb.c -O0 -o tlbO0保证没被优化掉
wsl里的运行结果：

步长为1,测量1000次取平均值，访问1000次平均用时为4257.000000时钟周期
步长为2,测量1000次取平均值，访问1000次平均用时为4290.000000时钟周期
步长为4,测量1000次取平均值，访问1000次平均用时为4398.000000时钟周期
步长为8,测量1000次取平均值，访问1000次平均用时为4429.000000时钟周期
步长为16,测量1000次取平均值，访问1000次平均用时为5063.000000时钟周期
步长为32,测量1000次取平均值，访问1000次平均用时为4432.000000时钟周期
步长为64,测量1000次取平均值，访问1000次平均用时为4508.000000时钟周期
步长为128,测量1000次取平均值，访问1000次平均用时为4375.000000时钟周期
步长为256,测量1000次取平均值，访问1000次平均用时为4537.000000时钟周期
步长为512,测量1000次取平均值，访问1000次平均用时为20244.000000时钟周期
步长为1024,测量1000次取平均值，访问1000次平均用时为26971.000000时钟周期
步长为2048,测量1000次取平均值，访问1000次平均用时为18894.000000时钟周期
步长为4096,测量1000次取平均值，访问1000次平均用时为20321.000000时钟周期
步长为8192,测量1000次取平均值，访问1000次平均用时为21044.000000时钟周期
步长为16384,测量1000次取平均值，访问1000次平均用时为26365.000000时钟周期
步长为32768,测量1000次取平均值，访问1000次平均用时为42513.000000时钟周期
步长为65536,测量1000次取平均值，访问1000次平均用时为86202.000000时钟周期

在512的位置有明显的时钟周期增长，而后趋于稳定，过大时继续明显增长

taskset -c 0 ./tlb绑定CPU0

步长为1,测量1000次取平均值，访问1000次平均用时为4352.000000时钟周期
步长为2,测量1000次取平均值，访问1000次平均用时为4282.000000时钟周期
步长为4,测量1000次取平均值，访问1000次平均用时为4426.000000时钟周期
步长为8,测量1000次取平均值，访问1000次平均用时为4200.000000时钟周期
步长为16,测量1000次取平均值，访问1000次平均用时为4399.000000时钟周期
步长为32,测量1000次取平均值，访问1000次平均用时为4457.000000时钟周期
步长为64,测量1000次取平均值，访问1000次平均用时为4636.000000时钟周期
步长为128,测量1000次取平均值，访问1000次平均用时为4521.000000时钟周期
步长为256,测量1000次取平均值，访问1000次平均用时为4580.000000时钟周期
步长为512,测量1000次取平均值，访问1000次平均用时为18783.000000时钟周期
步长为1024,测量1000次取平均值，访问1000次平均用时为28484.000000时钟周期
步长为2048,测量1000次取平均值，访问1000次平均用时为41077.000000时钟周期
步长为4096,测量1000次取平均值，访问1000次平均用时为37400.000000时钟周期
步长为8192,测量1000次取平均值，访问1000次平均用时为35532.000000时钟周期
步长为16384,测量1000次取平均值，访问1000次平均用时为28906.000000时钟周期
步长为32768,测量1000次取平均值，访问1000次平均用时为28843.000000时钟周期
步长为65536,测量1000次取平均值，访问1000次平均用时为27293.000000时钟周期

接下来是用lua控制，也就是说我需要把C的版本改成可以接受参数的，再把数组放在堆上，输出也改成平均每次访问的时钟周期

int main(int argc, char * argv[]) {
  int N = atoi(argv[1]);
  int PAGES = atoi(argv[2]);
  int *a = (int *)malloc(PAGES * (1 << MAX) * sizeof(int));
  ……
  double time = (end - start) / (N * PAGES);
      printf("步长为%d,测量%d次取平均值，访问%d次平均每次用时为%lf时钟周期\n",1 << i , N ,PAGES, time);

然后用lua控制，每次改变的是访问的数组次数

local N = 16
local result = {}

for i = 0, N do
    local times = 1 << i
    local cmd = string.format("taskset -c 0 ./tlb %d %d", 1000,times)
    local handle = io.popen(cmd)
    local output = handle:read("*a")
    print(output)  -- 打印输出
    handle:close()  -- 关闭文件句柄
end

结果：

步长为1,测量1000次取平均值，访问1次平均每次用时为5.000000时钟周期
步长为2,测量1000次取平均值，访问1次平均每次用时为5.000000时钟周期
步长为4,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为8,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为16,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为32,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为64,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为128,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为256,测量1000次取平均值，访问1次平均每次用时为5.000000时钟周期
步长为512,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为1024,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为2048,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为4096,测量1000次取平均值，访问1次平均每次用时为5.000000时钟周期
步长为8192,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为16384,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为32768,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
步长为65536,测量1000次取平均值，访问1次平均每次用时为4.000000时钟周期
……
步长为1,测量1000次取平均值，访问128次平均每次用时为4.000000时钟周期
步长为2,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为4,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为8,测量1000次取平均值，访问128次平均每次用时为4.000000时钟周期
步长为16,测量1000次取平均值，访问128次平均每次用时为4.000000时钟周期
步长为32,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为64,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为128,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为256,测量1000次取平均值，访问128次平均每次用时为5.000000时钟周期
步长为512,测量1000次取平均值，访问128次平均每次用时为13.000000时钟周期
步长为1024,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
步长为2048,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
步长为4096,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
步长为8192,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
步长为16384,测量1000次取平均值，访问128次平均每次用时为14.000000时钟周期
步长为32768,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
步长为65536,测量1000次取平均值，访问128次平均每次用时为15.000000时钟周期
……
步长为1,测量1000次取平均值，访问8192次平均每次用时为4.000000时钟周期
步长为2,测量1000次取平均值，访问8192次平均每次用时为5.000000时钟周期
步长为4,测量1000次取平均值，访问8192次平均每次用时为4.000000时钟周期
步长为8,测量1000次取平均值，访问8192次平均每次用时为5.000000时钟周期
步长为16,测量1000次取平均值，访问8192次平均每次用时为5.000000时钟周期
步长为32,测量1000次取平均值，访问8192次平均每次用时为5.000000时钟周期
步长为64,测量1000次取平均值，访问8192次平均每次用时为6.000000时钟周期
步长为128,测量1000次取平均值，访问8192次平均每次用时为19.000000时钟周期
步长为256,测量1000次取平均值，访问8192次平均每次用时为17.000000时钟周期
步长为512,测量1000次取平均值，访问8192次平均每次用时为24.000000时钟周期
步长为1024,测量1000次取平均值，访问8192次平均每次用时为38.000000时钟周期
步长为2048,测量1000次取平均值，访问8192次平均每次用时为44.000000时钟周期
步长为4096,测量1000次取平均值，访问8192次平均每次用时为40.000000时钟周期
步长为8192,测量1000次取平均值，访问8192次平均每次用时为47.000000时钟周期
步长为16384,测量1000次取平均值，访问8192次平均每次用时为54.000000时钟周期
步长为32768,测量1000次取平均值，访问8192次平均每次用时为66.000000时钟周期
步长为65536,测量1000次取平均值，访问8192次平均每次用时为85.000000时钟周期

分析结果的话，只访问一次也无所谓局部性了，128次在512步长处出现了明显的增长，8192次责是从128开始，后续增长也很明显

在不同的设备上运行：
Ubuntu

……
步长为1,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为2,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为4,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为8,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为16,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为32,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为64,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为128,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为256,测量1000次取平均值，访问64次平均每次用时为6.000000时钟周期
步长为512,测量1000次取平均值，访问64次平均每次用时为8.000000时钟周期
步长为1024,测量1000次取平均值，访问64次平均每次用时为22.000000时钟周期
步长为2048,测量1000次取平均值，访问64次平均每次用时为23.000000时钟周期
步长为4096,测量1000次取平均值，访问64次平均每次用时为23.000000时钟周期
步长为8192,测量1000次取平均值，访问64次平均每次用时为22.000000时钟周期
步长为16384,测量1000次取平均值，访问64次平均每次用时为22.000000时钟周期
步长为32768,测量1000次取平均值，访问64次平均每次用时为22.000000时钟周期
步长为65536,测量1000次取平均值，访问64次平均每次用时为22.000000时钟周期
……
步长为1,测量1000次取平均值，访问2048次平均每次用时为11.000000时钟周期
步长为2,测量1000次取平均值，访问2048次平均每次用时为7.000000时钟周期
步长为4,测量1000次取平均值，访问2048次平均每次用时为7.000000时钟周期
步长为8,测量1000次取平均值，访问2048次平均每次用时为6.000000时钟周期
步长为16,测量1000次取平均值，访问2048次平均每次用时为7.000000时钟周期
步长为32,测量1000次取平均值，访问2048次平均每次用时为7.000000时钟周期
步长为64,测量1000次取平均值，访问2048次平均每次用时为7.000000时钟周期
步长为128,测量1000次取平均值，访问2048次平均每次用时为11.000000时钟周期
步长为256,测量1000次取平均值，访问2048次平均每次用时为15.000000时钟周期
步长为512,测量1000次取平均值，访问2048次平均每次用时为15.000000时钟周期
步长为1024,测量1000次取平均值，访问2048次平均每次用时为21.000000时钟周期
步长为2048,测量1000次取平均值，访问2048次平均每次用时为22.000000时钟周期
步长为4096,测量1000次取平均值，访问2048次平均每次用时为22.000000时钟周期
步长为8192,测量1000次取平均值，访问2048次平均每次用时为23.000000时钟周期
步长为16384,测量1000次取平均值，访问2048次平均每次用时为25.000000时钟周期
步长为32768,测量1000次取平均值，访问2048次平均每次用时为27.000000时钟周期
步长为65536,测量1000次取平均值，访问2048次平均每次用时为37.000000时钟周期

Killed

Segmentation fault (core dumped)

最后出现了段错误，没有那么多堆上空间分给此程序

然后是可视化，在本机做的,让o3用python写一个：

#!/usr/bin/env python3
"""
visualize_tlb.py
----------------
运行 `./tlb` 不同参数组合的测试并将结果可视化。

使用方法：
    python3 visualize_tlb.py        # 直接运行脚本即可

脚本会：
1. 按照 tlb.lua 中的逻辑，对 pages = 2**i, i = 0..13 依次调用
   `taskset -c 0 ./tlb 1000 <pages>`。
2. 解析每次调用产生的输出（中文），提取步长(step_size) 和
   平均时钟周期(time)。
3. 使用 matplotlib 绘制“步长 vs 平均时钟周期”的折线图，
   不同 pages 值对应不同曲线，并自动添加图例。

注意事项：
- 需要预先安装 matplotlib: `pip install matplotlib`。
- 建议在 Linux/WSL 环境下运行；若在 Windows 原生环境运行请移除
  `taskset -c 0` 前缀或者改为相应的绑核命令。
"""

import subprocess
import re
import sys
from collections import defaultdict

try:
    import matplotlib.pyplot as plt
except ImportError:
    sys.stderr.write("[错误] 未找到 matplotlib，请先执行: pip install matplotlib\n")
    sys.exit(1)

# 与 tlb.c 输出格式匹配的正则
LINE_RE = re.compile(r"步长为(\d+).*平均每次用时为([0-9\.]+)时钟周期")

N_MEASURE = 1000  # 与 tlb.lua 中保持一致
MAX_POW   = 13    # pages = 2**i, i in [0, 13]


def run_tlb(pages: int) -> str:
    """运行一次 tlb 并返回标准输出。"""
    cmd = ["taskset", "-c", "0", "./tlb", str(N_MEASURE), str(pages)]
    try:
        completed = subprocess.run(cmd, check=True, text=True, capture_output=True)
        return completed.stdout
    except subprocess.CalledProcessError as e:
        sys.stderr.write(f"[错误] 运行 {' '.join(cmd)} 失败\n{e.stderr}\n")
        sys.exit(1)


def parse_output(output: str):
    """
    解析 tlb.c 的输出文本。
    返回 list[(step_size:int, time:float)]，长度应为 16 (对应 0..15 的步长指数)。
    """
    results = []
    for line in output.splitlines():
        m = LINE_RE.search(line)
        if m:
            step = int(m.group(1))
            time_cycle = float(m.group(2))
            results.append((step, time_cycle))
    if not results:
        sys.stderr.write("[警告] 未能解析任何数据，请检查 tlb 输出格式\n")
    return results


def main():
    data = defaultdict(list)  # pages -> list of (step, time)

    for i in range(MAX_POW + 1):
        pages = 1 << i
        print(f"[信息] 运行 ./tlb {N_MEASURE} {pages} ...")
        out = run_tlb(pages)
        parsed = parse_output(out)
        if parsed:
            # 按 step 升序排序，确保绘图时一致
            parsed.sort(key=lambda x: x[0])
            data[pages] = parsed

    if not data:
        sys.stderr.write("[错误] 未获取到任何数据，程序终止\n")
        sys.exit(1)

    # 绘图
    plt.figure(figsize=(10, 6))
    for pages, records in sorted(data.items()):
        steps, times = zip(*records)
        plt.plot(steps, times, marker='o', label=f'{pages} pages')

    plt.xlabel('Stride (bytes)')
    plt.ylabel('Average cycles per access')
    plt.title('TLB Experiment: Stride vs Access Latency')
    plt.xscale('log', base=2)
    plt.yscale('log')
    plt.grid(True, which='both', ls='--', alpha=0.5)
    plt.legend()
    plt.tight_layout()
    # 先保存图片，方便在无图形界面的环境下查看
    output_png = 'tlb.png'
    plt.savefig(output_png)
    print(f"[信息] 图形已保存至 {output_png}，如未弹出窗口可手动查看该文件。")
    # 如果图形后端支持交互，再尝试弹窗
    plt.show()


if __name__ == '__main__':
    main()