砺算科技嵌入式软件三面：Cache 测量、稀疏矩阵与 32 位乘法

《面试题目》

1. 如何设计程序，通过访问时延推断 CPU Cache 的层级和各级容量？
2. Cache 的主要作用是什么？
3. 缓存容量测试应如何选择工作集大小、访问方式，并定位时延拐点？
4. 缓存测量有哪些常见误差来源？如何控制？
5. 缓存行大小对缓存容量测试有什么影响？
6. 大型稀疏矩阵适合用什么数据结构存储，以节省内存并方便行列运算？
7. 只有无符号 32 位类型时，如何计算两个 32 位整数的完整乘积，分别返回高低 32 位？
8. 无符号低半部加法怎样判断进位，并把它传到高半部？
9. CPU 与 GPU 的计算特点有什么区别？哪些任务适合 GPU？
10. 用户态驱动和内核态驱动一般如何分工？
11. 手撕：只用 uint32 实现 uint32 × uint32，结果用两个 uint32 表示高低位。

《参考解析》

Cache 容量测量的本质是找“时延随工作集变化的平台段”。 用指针追逐（pointer chasing）构造一条依赖链，让每次访问都依赖上一次结果，这样 CPU 无法乱序预取，测到的就是真实的访存延迟。工作集从几 KB 逐步增大到几十 MB，每个规模重复多次取中位数或最小值，画出“工作集—延迟”曲线：L1、L2、L3 和内存会形成几个平台，平台之间的拐点大致对应各级容量。访问方式要固定步长、随机化顺序，避免硬件预取器把顺序访问优化掉；还要绑核、关掉频率波动、排除中断和后台任务干扰。缓存行会影响拐点位置：当步长小于缓存行时，相邻访问落在同一行，测到的是行内命中；步长接近或超过行大小，才能更准确地反映容量。常见误差包括频率调节、TLB、预取、多核共享缓存和测量次数不足，控制方法是固定频率、多次采样、取稳健统计量、按缓存行对齐。

稀疏矩阵存储要看运算模式。 CSR 用 values、col_idx、row_ptr 三个数组，适合按行遍历和 SpMV；CSC 按列压缩，适合按列运算；COO 存三元组，构造简单但空间开销大，适合从无序数据建矩阵；对角存储（DIA）适合带状矩阵，ELL 适合每行非零元数量接近的 GPU 场景。选择时看非零元分布、是否需要动态插入、目标算法是行优先还是列优先，以及是否要上 GPU。回答时别只报 CSR，要说出它为什么省空间、随机访问列时又为什么慢。

32 位乘法要拆成 16 位分块，再处理进位。 设 a = a1·2^16 + a0，b = b1·2^16 + b0，四个乘积 a0b0、a0b1、a1b0、a1b1 都用 32 位算。低位结果是 a0b0 的低 16 位加上中间项低 16 位左移 16 位；高位由 a1b1、两个交叉项的高 16 位、以及低位加法的进位累加得到。关键是每次 32 位加法后判断结果是否小于任一加数，若小于就说明溢出，进位加一。手写时把每一步的进位单独变量保存，最后组装 hi 和 lo；测试要覆盖 0、1、0xFFFFFFFF、以及高低位都溢出的组合。

CPU 和 GPU 的分工看“控制密集还是数据密集”。 CPU 核少但单核强，擅长分支复杂、串行依赖、低延迟任务；GPU 核多、吞吐高，擅长规则的大规模并行计算，比如矩阵乘、卷积、图像处理和批量归约。GPU 不适合分支发散严重、数据依赖强、传输开销远大于计算的任务。用户态驱动和内核态驱动的分工则是：内核态负责硬件资源管理、内存映射、中断处理和安全隔离，用户态负责具体设备的命令提交、队列管理和高性能路径，很多现代驱动把尽量多的逻辑放到用户态，内核只保留最小必要的资源控制。