# 23-09-15-秋招-快手 岗位：机器学习平台工程师 一面挂 ## 面试问题 ### 1.gpu和 npu 的区别 华为NPU和GPU在编程模型方面的区别： 1. Host:运行在CPU上的主机程序,负责控制GPU的操作和管理GPU上的数据. 2. Device:运行在GPU上的设备程序,负责执行计算任务. 3. Kernel:在GPU上执行的函数,它是CUDA程序的核心部分,一个Kernel可以并行地执行多个线程. 4. Thread:在GPU上执行的最小计算单元,由于GPU可以支持数千个并行线程,因此可以利用这种并行性来加速计算任务. 5. Block:由多个Thread组成的线程块,一个Block中的Thread可以共享同一块共享内存. 6. Grid:由多个Block组成的线程网格,可以表示整个计算任务的并行性. CUDA编程模型基于这些概念来实现GPU上的并行计算。在CUDA程序中，主机程序可以将计算任务分配给GPU进行并行处理，GPU会创建多个Thread和Block来并行执行计算任务。在Kernel函数中，程序员可以使用CUDA提供的API来访问GPU上的内存和设备，并通过线程间同步和通信来协调计算任务。通过利用GPU的并行性，CUDA可以实现比CPU更快的计算速度。 而华为NPU中仅有Host、Device、Kernel、Block概念,每一个Block为一个并行单位,为最小的执行计算的单元.Block之间通过GM进行数据共享.NPU中有多个相同的物理核心,同一时间每个物理核心调度一个Block.其中没用线程的概念,无法像GPU那样支持数千个并行线程. ### 2.gpu的底层调度，grid block超出了实际的 sm 数量，如何调度，如何映射 GPU 上有四种调度器 #### Application scheduler 通常情况下两个不同的gpu应用是不能同时占用gpu的计算单元的，他们只能通过时分复用的方法来使用gpu。**具体来讲就是gpu按照FIFO的策略依次从runlist上拿取channel进行执行，每一个channel只能运行一定的时间，等时间片用完之后就会进行切换来运行其他的channel。但是这种时分复用的调度算法有一个缺陷就是如果App每次提交的任务都比较小就无法占满gpu SM从而导致了gpu 整体使用率比较低**。为了解决这个问题，nvidia 又提出了一另外一种调试算法叫`Multi-Process Service`，我们也叫空分。在MPS的场景下它允许两个不同的应用能够在同一时刻去占用不同的gpu sm，从而来提高gpu的使用率。 #### stream schedule 当gpu从runlist里面取出channel之后会生成相应的command和数据，而每个stream里面包含了一系列的commands。由于不同的应用的stream是可以设置不同的优先级的，所以stream scheduler主要负责不同应用的stream的调度和抢占。 #### Thread Block scheduler 它主要负责将thread block assign给gpu的sm，完成thread block跟gpu sm之间的一一映射。通常能不能将一个 kernel的thread block assign给某个sm主要看SM上的计算能力。举个例子，假如说一个sm支持 2048 threads和32 blocks，那么如果某个kernel有64个threads和64个blocks则scheduler也只能选这个kernel一半的blocks去运行。 #### warp scheduler 通常情况下一个warp包含了32个thread，warp scheduler的主要作用就是从wrap中获取准备好的待执行的instruction，并把这些instruction分配给sm上的Disaptch Unit。接着Dispatch Unit会把这些指令发送到SM的SIMD core上执行。 thread block scheduler 负责将 grid 中的 block 调度到 sm 上，如果 block 数量超过了 sm 的数量，那么调度器就会进行分时调度，先运行一部分 block，之后再运行剩下的 block。 ### 3.gpu上如何实现双缓冲 同一个 warp 中需要进行多轮循环取不同数据 双缓冲才有意义。 同样在共享内存上开辟两个缓冲区，每一轮循环的时候，先往其中一个缓冲区写入下一轮循环所需要的数据，然后中另一个缓冲区中读取数据进行计算，从而达到计算和数据读取的并行。 ### 4.nordered_map 和 map 的区别 各有什么优点 1. map： - 优点： - map元素有序（这是map最大的优点，其元素的有序性在很多应用中都会简化很多的操作）； - 其红黑树的结构使得map的很多操作都可在O(logn)下完成； - map的各项性能较为稳定，与元素插入顺序无关； - map支持范围查找。 - 缺点： - 占用的空间大：红黑树的每一个节点需要保存其父节点位置、孩子节点位置及红/黑性质，因此每一个节点占用空间大。 - 查询平均时间不如unordered_map。 - 适用场景： - 元素需要有序； - 对于单次查询时间较为敏感，必须保持查询性能的稳定性，比如实时应用等等。 2. unordered_map - 优点： - 查询速度快，平均性能接近于常数时间O(1)； - 缺点： - 元素无序； - unordered_map相对于map空间占用更大，且其利用率不高； - 查询性能不太稳定，最坏时间复杂度可达到O(n)。 - 适用场景： - 要求查找速率快，且对单次查询性能要求不敏感。 ## 手撕代码 [有序矩阵中第 K 小的元素](https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/) 给一个 n*n 的矩阵，每行和每列都是按升序排列，求矩阵中第 k 小的元素。要求复杂度小于(n2)