百度 AI Infra (2)

发表于 更新于 分类于 ，

Q: OpenMP并行区怎么开？

使用 #pragma omp parallel 编译器指令开启并行区域。这是 OpenMP 共享内存并行编程模型的基础，编译器在遇到该指令时 fork 出线程组来并行执行。

常见用法：

  • #pragma omp parallel for：将 for 循环的迭代自动均分到各线程，是最常用的并行化方式
  • #pragma omp parallel sections：将不同独立代码段分配到不同线程执行
  • num_threads(N)：指定线程数。默认值取环境变量 OMP_NUM_THREADS 或 CPU 核心数
  • schedule(dynamic, chunk_size)：动态调度，适合迭代计算量不均的场景

编译要求：需要编译器支持 OpenMP（GCC 加 -fopenmp，Clang 加 -fopenmp，MSVC 加 /openmp）。运行时线程池预先创建，后续并行区复用线程，避免重复创建开销。

Q: for循环中sum++在并行区内和串行区的运行结果是否相同？如何变成相同的？

不相同。多线程并行执行 sum++ 时存在数据竞争（race condition）。sum++ 包含”读取-修改-写回”三个非原子步骤，多个线程可能同时读到相同旧值并各自加 1 写回，导致更新丢失。最终结果不确定且通常小于预期值 100。

解决方法（推荐优先级排序）：

  1. reduction 子句（最优）：#pragma omp parallel for reduction(+:sum)。编译器为每个线程创建私有副本，循环结束后自动规约合并。零额外同步开销，性能最好。

  2. 原子操作：在 sum++ 前加 #pragma omp atomic。利用硬件原子指令（如 x86 的 lock xadd）保证操作不可分割。每次迭代有原子操作开销，适合不规则更新模式。

  3. 私有副本手动合并：每个线程用 private 变量累加，循环结束后进入 critical 区合并结果。

  4. 互斥锁：#pragma omp critical 包裹 sum++。所有线程在此串行化，等同于单线程执行，基本失去并行意义。仅适合临界区内逻辑复杂且无法用其他方法的情况。

Q: GPU中的内存架构是什么？

GPU 采用多层次内存架构设计，核心原则是”越靠近计算单元的存储越快但越小”：

层级 容量(A100) 延迟 作用域
寄存器 每SM 256KB ~1 cycle CUDA Core私有
共享内存/L1 每SM 192KB(可配) ~20 cycles SM内Block共享
L2 Cache 40MB ~200 cycles 全GPU所有SM共享
全局内存(HBM) 80GB ~400 cycles 全GPU所有SM共享
常量/纹理内存 64KB常量 有缓存时~L1 全GPU只读

优化核心思路：最大化数据在片上（寄存器 > 共享内存）的复用次数，将算术强度（FLOPs/Bytes）提高到超过硬件的计算-带宽比（如 A100 约 156 FLOPs/Byte），使 kernel 变为 compute-bound 而非 memory-bound。

Q: Cache映射的分类和特点？

1. 直接映射：主存块只能放到唯一确定的 Cache 行（block_addr % n_lines）。硬件最简单（一次比较即可），但冲突率高——两个频繁访问的块映射到同一行会反复驱逐（thrashing）。

2. 全相联映射：主存块可放到任意 Cache 行。冲突率最低，但需要与所有行并行比较（CAM 硬件），功耗和面积大。适合 TLB（条目数少，32-64项）。

3. 组相联映射（主流方案）：Cache 分为多组，块映射到固定组内的任意行。N 路组相联表示每组 N 行。现代 CPU 典型配置：L1 4-8路，L2/L3 8-16路。兼顾冲突率和硬件复杂度。

Q: C++智能指针的分类和用法？

C++11 引入智能指针通过 RAII 自动管理堆内存生命周期：

shared_ptr：共享所有权，内部引用计数（原子操作，线程安全）。计数归零时释放资源。注意：(1) 控制块额外 16-32 字节开销；(2) make_shared 比 shared_ptr<T>(new T) 高效（一次分配 vs 两次）；(3) 循环引用导致内存泄漏。

unique_ptr：独占所有权，不可拷贝只可 std::move 转移。无引用计数，与裸指针大小相同（零开销）。支持自定义删除器。是默认首选的智能指针。

weak_ptr：弱引用，不增加引用计数。从 shared_ptr 构造，使用前需 lock() 提升。用于打破循环引用和实现缓存/观察者模式。

选择策略：默认 unique_ptr -> 需要共享时 shared_ptr -> 需要观察但不拥有时 weak_ptr。

Q: C++多态是什么？怎么实现的？

同一接口在不同类型的对象上表现出不同行为，是面向对象的核心特性。

静态多态（编译期决议）：函数重载（同名不同参数）、模板（编译期实例化具体类型）、CRTP（奇异递归模板模式，零运行时开销的”静态虚函数”）。

动态多态（运行期决议）：通过虚函数 + 继承实现。机制：

  • 编译器为含虚函数的类生成 vtable（虚函数表），存储各虚函数的实际地址
  • 每个对象开头有 vptr（8字节指针）指向所属类的 vtable
  • 通过基类指针调用虚函数时：读 vptr -> 查 vtable -> 间接跳转
  • 开销：一次指针间接寻址（通常 L1 命中，~1-2 ns），虚函数不能内联

Q: 动态链接和动态绑定的区别？

两个完全不同层面的概念：

动态绑定（语言层面）：运行时通过 vtable 确定虚函数调用的实际目标。编译期只生成间接调用代码，运行期根据对象真实类型决议。这是 C++ 多态的核心机制。

动态链接（操作系统层面）：程序运行时才加载共享库（.so/.dll）并解析符号地址。优点：节省内存（多进程共享同一份库代码）、便于更新（不需重新编译依赖程序）。通过 PLT/GOT 实现延迟绑定（首次调用时解析）。

Q: STL中map的底层实现？

红黑树（自平衡二叉搜索树），保证插入/删除/查找均为 O(log n)。元素按 key 有序排列（中序遍历得升序）。

红黑树性质：节点染红或黑；根为黑；无连续红色；根到叶黑高相同。通过旋转和重新着色维护平衡，最坏情况树高不超过 2*log(n+1)。

使用场景：需要有序遍历、范围查询（lower_bound/upper_bound）时选 map；纯粹键值查找选 unordered_map（O(1)）。

Q: AVL树和红黑树的区别？

AVL 严格平衡（左右子树高度差<=1），树更矮查找更快；红黑树近似平衡（最长路径<=2*最短路径），插入/删除旋转次数少效率更高。

关键差异：AVL 删除可能需要 O(log n) 次旋转回溯到根，红黑树删除最多 3 次旋转。因此频繁插删选红黑树（STL map/set），纯查找密集选 AVL（数据库索引）。

Q: unordered_map的底层实现？

哈希表 + 拉链法（separate chaining）。每个 bucket 是链表，通过哈希函数将 key 映射到桶索引。平均 O(1) 查找/插入，最坏 O(n)（全部冲突）。load_factor 超过阈值（默认 1.0）时 rehash 翻倍扩容。

元素无序，不支持范围查询。自定义类型做 key 需提供 hash 函数和 == 运算符。

Q: 哈希冲突的解决方法？

  1. 链地址法（拉链法）：每桶一个链表/红黑树。实现简单、load factor 可>1、删除方便。STL unordered_map 采用。
  2. 开放定址法：冲突时探测下一个空位。线性探测（步长1，聚集严重）、二次探测（步长i^2）、双重哈希（另一个hash算步长）。cache 友好但 load factor 需<0.75。
  3. 再哈希法：使用备选哈希函数
  4. 公共溢出区：冲突元素统一存放

Q: 计算机的存储层次架构？

寄存器(<1ns) -> L1(1ns, 32-64KB) -> L2(5ns, 256KB-1MB) -> L3(15ns, 8-64MB) -> DRAM(80ns, 16-256GB) -> SSD(100us) -> HDD(10ms)

每层容量增大约 10-100 倍，延迟增大约 3-10 倍。利用程序局部性原理（90% 时间访问 10% 数据），小而快的缓存覆盖大部分访问请求。Cache miss 的性能惩罚巨大（DRAM 访问约等于 200 次 L1 访问时间）。

Q: CPU中程序员可见的寄存器分类？PC寄存器的作用？

以 x86-64 为例：通用寄存器（RAX-R15，16 个 64 位，数据运算和地址计算）、段寄存器（CS/DS/SS 等，64 位模式下基本只用 FS/GS 做 TLS）、标志/控制寄存器（RFLAGS，零标志/进位/溢出等状态位）。此外还有 SIMD 寄存器（XMM/YMM/ZMM）。

PC（程序计数器，x86 中叫 RIP）：存放下一条要执行指令的地址。CPU 据此取指、译码、执行。顺序执行时自动递增，遇到跳转/调用指令时被修改为目标地址。用户态程序无法直接写 PC，只能通过 jmp/call/ret 间接改变。

Q: 在main函数前运行函数怎么实现？

  1. 全局对象构造函数：定义全局对象，其构造函数在 main 前由 CRT 初始化代码调用。但不同翻译单元间构造顺序未定义（SIOF 问题）。
  2. **__attribute__((constructor))**（GCC/Clang）：标记函数在 main 前执行，可指定优先级。底层注册到 .init_array 段。
  3. 静态变量初始化：全局/命名空间级静态变量的初始化表达式在 main 前求值。

Q: 如何设置条件断点？

GDB：break 行号 if 条件（如 break 10 if i==50），仅条件为真时暂停。也可先设断点再 condition N expr。高级：ignore N count 跳过前 count 次命中。IDE 中右键断点设置条件表达式即可。

注意：条件断点在每次触发时都评估表达式，高频循环中会显著减慢执行速度。

Q: 如何进行堆栈监视？

GDB：bt（backtrace）查看调用栈，bt full 显示各帧局部变量，frame N 切换栈帧，info locals/info args 查看变量。

运行时检测：

  • ASan（-fsanitize=address）：检测栈缓冲区溢出、use-after-return，运行时开销 ~2x
  • Valgrind：无需重编译，检测内存泄漏、越界、未初始化读取，但慢 10-20x
  • Stack canary（-fstack-protector）：在栈帧中插入金丝雀值检测覆写

Q: 程序在内存中的分段？

从高到低：栈区（局部变量/函数调用信息，向低地址增长，默认 8MB）-> 空闲空间 -> 堆区（malloc/new 动态分配，向高地址增长）-> BSS段（未初始化全局/静态变量，加载时清零）-> 数据段（已初始化全局/静态变量）-> 代码段（只读可执行指令）。

mmap 区域在栈和堆之间，用于动态库加载和大块内存分配。ASLR 随机化各段基址增强安全性。

Q: STL中deque是怎么实现的？

分段连续存储：中控 map 数组存指针，每个指针指向固定大小缓冲区（通常 512B/sizeof(T) 个元素）。逻辑连续物理分段。

优势：O(1) 头尾插入/删除（操作头/尾缓冲区）；扩容只需新增缓冲区不需复制全部元素（对比 vector 的 realloc）。劣势：随机访问需计算所在缓冲区和偏移，cache 局部性比 vector 差。适合 BFS 队列等头尾操作频繁的场景。

Q: 寄存器和Cache哪个更快？Cache和主存实现区别？

寄存器最快（0-1 cycle，直连 ALU）。

对比 Cache (SRAM) 主存 (DRAM)
存储单元 6管/bit（双稳态触发器） 1管+1电容/bit
刷新 不需要 每 64ms 刷新一次
速度 1-20 ns 50-100 ns
密度/成本 低/高（~$100/GB） 高/低（~$3/GB）

都是易失性存储（断电丢失）。分层设计的原因：SRAM 太贵不能做大容量，DRAM 太慢不能直接喂处理器。

Q: CUDA编程模型中的内存分类？

类型 作用域 物理位置 延迟 说明
寄存器 线程私有 片上 1 cycle 最快，溢出到local memory性能剧降
本地内存 线程私有 HBM ~400 cycles 名字有误导，实际在全局内存中
共享内存 Block共享 片上SM ~20 cycles 手动管理的L1，优化关键
全局内存 所有线程 HBM ~400 cycles 容量大延迟高，需合并访问
常量内存 只读 HBM+缓存 ~L1 if cached 64KB，适合广播读取
纹理内存 只读 HBM+缓存 ~L1 if cached 2D空间局部性优化

Q: __global__关键字的作用？

修饰核函数（Kernel），由 Host（CPU）调用在 Device（GPU）执行。必须指定执行配置 <<<gridDim, blockDim, sharedMem, stream>>>，返回类型必须 void。kernel 调用是异步的（CPU 发起后立即返回），需 cudaDeviceSynchronize() 等待完成。

对比：__device__ 函数只能由 GPU 调用 GPU 执行；__host__ 函数是普通 CPU 函数。

Q: 如何获取GPU最大线程数？

cudaGetDeviceProperties(&prop, device_id) 获取设备属性。关键字段：maxThreadsPerBlock（通常 1024）、maxThreadsDim[3]（block各维度上限 [1024,1024,64]）、maxGridSize[3]（grid各维度上限）、warpSize（32）。

实际可用线程数还受寄存器用量和共享内存用量约束（影响 occupancy）。可用 CUDA Occupancy API 或 --ptxas-options=-v 查看资源使用。

Q: 贪心算法和动态规划的区别？

贪心：每步取当前局部最优，不回溯。时间复杂度通常 O(n log n)。需要证明”贪心选择性质”才能保证全局最优（如 Huffman、Dijkstra 正权图、区间调度）。

动态规划：将问题分解为重叠子问题，用备忘录/表格记录中间结果避免重复计算。保证全局最优。时间通常 O(n^2) 或更高，空间 O(n) 以上。典型：背包、LCS、编辑距离。

判断标准：若局部最优能导出全局最优用贪心（快），否则必须 DP 枚举所有可能（准但慢）。

Q: 图搜索算法？

  • BFS：队列逐层，无权图最短路径，O(V+E)
  • DFS：栈/递归深入回溯，拓扑排序/环检测/连通分量，O(V+E)
  • Dijkstra：单源最短路（正权），优先队列贪心，O((V+E)logV)
  • Bellman-Ford：支持负权，O(VE)
  • **A***：启发式搜索 f=g+h，带估价函数加速
  • Floyd：全对最短路，O(V^3)