1. NPU指令集架构解析与调度基础

任务定义

本案例面向AI编译器后端开发场景，目标是通过一个可运行的最小NPU指令集模拟器，建立对NPU指令集架构（ISA）与指令调度基本概念的具象认知。你将获得一个包含典型NPU指令类型（矩阵乘、向量运算、数据搬运）的指令集定义，并实现一个基础调度器，用于将无序发射的指令序列按照硬件资源依赖关系重排为可执行的顺序。完成本案例后，你应能解释NPU指令中显式并行与依赖约束的含义，并理解调度器在编译器后端中的作用位置。

NPU指令集架构定义

为聚焦调度核心概念，本案例定义了一个精简的NPU指令集，包含三类硬件执行单元：矩阵单元（MXU）、向量单元（VEC）和搬运单元（DMA）。每条指令由操作码、目标寄存器、源操作数寄存器及执行单元类型组成。指令间的依赖关系通过寄存器读写冲突体现：若指令B的源寄存器与指令A的目标寄存器相同，则B必须等待A完成。调度器的职责是在不违反依赖的前提下，将指令发射到对应执行单元，并尽可能缩短总执行周期。

指令类型操作码执行单元延迟（周期）语义
矩阵乘MMMXU4d = a × b（矩阵）
向量加VADDVEC2d = a + b（逐元素）
向量乘VMULVEC2d = a × b（逐元素）
数据搬运LOAD/STOREDMA3寄存器 ↔ 外部存储

指令编码采用固定32位格式：[31:28]操作码，[27:24]执行单元ID，[23:16]目标寄存器编号，[15:8]源寄存器1编号，[7:0]源寄存器2编号。寄存器文件共16个（R0–R15）。

调度器实现

下面给出一个最小可复现的调度器实现。它接收一组未排序的指令（模拟编译器前端生成的中间表示），输出满足依赖关系的发射顺序及每个周期的执行单元占用情况。核心算法采用列表调度（List Scheduling）：每个周期检查所有就绪指令（源寄存器均未被占用），选择优先级最高的发射，并更新寄存器占用表。

// npu_scheduler.h
#ifndef NPU_SCHEDULER_H
#define NPU_SCHEDULER_H

#include <stdint.h>
#include <vector>
#include <queue>
#include <string>

enum class ExecUnit { MXU = 0, VEC = 1, DMA = 2 };

struct NPUInst {
    uint32_t raw;            // 32位原始编码
    uint8_t opcode;          // 操作码
    ExecUnit unit;           // 执行单元
    uint8_t rd;              // 目标寄存器
    uint8_t rs1;             // 源寄存器1
    uint8_t rs2;             // 源寄存器2
    uint8_t latency;         // 执行延迟
    int seq_id;              // 原始序号（用于稳定排序）
};

// 将可读指令文本编码为32位原始指令
NPUInst encode_inst(const std::string& op, const std::string& unit,
                    uint8_t rd, uint8_t rs1, uint8_t rs2);

// 列表调度器：输入指令列表，输出调度后的发射周期
std::vector<int> schedule(const std::vector<NPUInst>& insts);

#endif // NPU_SCHEDULER_H
// npu_scheduler.cpp
#include "npu_scheduler.h"
#include <cassert>
#include <map>
#include <algorithm>

NPUInst encode_inst(const std::string& op, const std::string& unit,
                    uint8_t rd, uint8_t rs1, uint8_t rs2) {
    NPUInst inst;
    inst.rd = rd; inst.rs1 = rs1; inst.rs2 = rs2;
    inst.seq_id = 0;
    if (op == "MM")      { inst.opcode = 0x1; inst.latency = 4; }
    else if (op == "VADD"){ inst.opcode = 0x2; inst.latency = 2; }
    else if (op == "VMUL"){ inst.opcode = 0x3; inst.latency = 2; }
    else if (op == "LOAD"){ inst.opcode = 0x4; inst.latency = 3; }
    else if (op == "STORE"){ inst.opcode = 0x5; inst.latency = 3; }
    else assert(false && "unknown opcode");

    if (unit == "MXU")      inst.unit = ExecUnit::MXU;
    else if (unit == "VEC") inst.unit = ExecUnit::VEC;
    else if (unit == "DMA") inst.unit = ExecUnit::DMA;
    else assert(false && "unknown unit");

    inst.raw = (static_cast<uint32_t>(inst.opcode) << 28) |
               (static_cast<uint32_t>(inst.unit) << 24) |
               (static_cast<uint32_t>(inst.rd) << 16) |
               (static_cast<uint32_t>(inst.rs1) << 8) |
               static_cast<uint32_t>(inst.rs2);
    return inst;
}

std::vector<int> schedule(const std::vector<NPUInst>& insts) {
    const int NUM_REGS = 16;
    const int NUM_CYCLES = 100;  // 调度上限，防止死循环
    std::vector<int> issue_cycle(insts.size(), -1);

    // reg_busy_until[reg] = 该寄存器被占用到的周期（含）
    std::vector<int> reg_busy_until(NUM_REGS, -1);
    // unit_busy_until[unit] = 该执行单元被占用到的周期（含）
    std::vector<int> unit_busy_until(3, -1);

    std::vector<bool> issued(insts.size(), false);
    int issued_count = 0;
    int cycle = 0;

    while (issued_count < static_cast<int>(insts.size()) && cycle < NUM_CYCLES) {
        // 找到当前周期就绪且执行单元空闲的指令
        int best_idx = -1;
        int best_priority = -1;
        for (size_t i = 0; i < insts.size(); ++i) {
            if (issued[i]) continue;
            const NPUInst& inst = insts[i];
            // 检查源寄存器是否就绪（源寄存器必须已不再被占用）
            bool src_ready = true;
            if (inst.rs1 != 0 && reg_busy_until[inst.rs1] >= cycle) src_ready = false;
            if (inst.rs2 != 0 && reg_busy_until[inst.rs2] >= cycle) src_ready = false;
            if (!src_ready) continue;

            // 检查执行单元是否空闲
            int unit_id = static_cast<int>(inst.unit);
            if (unit_busy_until[unit_id] >= cycle) continue;

            // 优先级：原始顺序靠前的优先（FIFO策略，可扩展为其他启发式）
            int priority = static_cast<int>(i);
            if (best_idx == -1 || priority < best_priority) {
                best_idx = static_cast<int>(i);
                best_priority = priority;
            }
        }

        if (best_idx != -1) {
            const NPUInst& inst = insts[best_idx];
            issue_cycle[best_idx] = cycle;
            issued[best_idx] = true;
            issued_count++;

            // 更新寄存器占用：目标寄存器在 [cycle, cycle+latency-1] 被占用
            if (inst.rd != 0) {
                reg_busy_until[inst.rd] = cycle + inst.latency - 1;
            }
            // 更新执行单元占用
            int unit_id = static_cast<int>(inst.unit);
            unit_busy_until[unit_id] = cycle + inst.latency - 1;
        }
        cycle++;
    }

    // 若存在未发射指令（理论上不应发生），标记为-1
    return issue_cycle;
}
// main.cpp
#include "npu_scheduler.h"
#include <iostream>
#include <vector>

int main() {
    // 构造一个含依赖的指令序列（模拟编译器前端输出，顺序为乱序）
    std::vector<NPUInst> insts;
    // 1. LOAD R1, [addr0]  —— DMA搬运数据到R1
    insts.push_back(encode_inst("LOAD", "DMA", 1, 0, 0));
    // 2. LOAD R2, [addr1]  —— DMA搬运数据到R2
    insts.push_back(encode_inst("LOAD", "DMA", 2, 0, 0));
    // 3. MM R3, R1, R2     —— 矩阵乘，依赖R1,R2
    insts.push_back(encode_inst("MM", "MXU", 3, 1, 2));
    // 4. VADD R4, R3, R1   —— 向量加，依赖R3（MM结果）
    insts.push_back(encode_inst("VADD", "VEC", 4, 3, 1));
    // 5. VMUL R5, R4, R2   —— 向量乘，依赖R4
    insts.push_back(encode_inst("VMUL", "VEC", 5, 4, 2));
    // 6. STORE R5, [addr2] —— 存储结果
    insts.push_back(encode_inst("STORE", "DMA", 0, 5, 0));

    // 为每条指令设置原始序号（用于稳定排序）
    for (size_t i = 0; i < insts.size(); ++i) insts[i].seq_id = static_cast<int>(i);

    std::vector<int> cycles = schedule(insts);

    std::cout << "指令发射周期（按输入顺序）:" << std::endl;
    for (size_t i = 0; i < insts.size(); ++i) {
        std::cout << "指令 " << i << " (seq=" << insts[i].seq_id << ") -> 周期 "
                  << cycles[i] << std::endl;
    }

    // 计算总执行周期（最后一条指令完成时间）
    int max_end = 0;
    for (size_t i = 0; i < insts.size(); ++i) {
        int end = cycles[i] + insts[i].latency;
        if (end > max_end) max_end = end;
    }
    std::cout << "总执行周期: " << max_end << std::endl;
    return 0;
}

编译与运行

将上述三个文件保存于同一目录，执行以下命令编译并运行：

g++ -std=c++11 -o npu_sched main.cpp npu_scheduler.cpp
./npu_sched

预期输出与验证

根据代码逻辑，可唯一推出以下调度结果（预期输出，非实测数据）：

指令发射周期（按输入顺序）:
指令 0 (seq=0) -> 周期 0
指令 1 (seq=1) -> 周期 0
指令 2 (seq=2) -> 周期 3
指令 3 (seq=3) -> 周期 7
指令 4 (seq=4) -> 周期 9
指令 5 (seq=5) -> 周期 11
总执行周期: 14

验证方法：运行程序后，观察输出是否与上述周期一致。关键检查点：

  • 指令0和指令1（均为DMA搬运）无依赖且DMA单元空闲，因此都在周期0发射（同一周期不同执行单元可并行）。
  • 指令2（MM）依赖R1和R2，需等待两条LOAD完成（LOAD延迟3周期，周期0发射则周期2完成），因此最早周期3发射。
  • 指令3（VADD）依赖R3（MM结果，周期3发射+4延迟=周期6完成），因此最早周期7发射。
  • 指令4（VMUL）依赖R4（VADD结果，周期7+2=8完成），最早周期9发射。
  • 指令5（STORE）依赖R5（VMUL结果，周期9+2=10完成），最早周期11发射。

若输出与上述一致，则说明调度器正确实现了寄存器依赖约束与执行单元占用检查，案例验证通过。

调度过程可视化

NPU指令调度时序图（周期0-14） 周期 0 2 4 6 8 10 12 14 DMA MXU VEC LOAD R1 LOAD R2 STORE MM R3 VADD VMUL DMA搬运 矩阵运算 向量运算 寄存器依赖

关键概念说明

通过上述实现与可视化，可以直观观察到三个核心调度概念：

  • 资源并行：不同执行单元（DMA/MXU/VEC）的指令可在同一周期发射，如周期0两条LOAD同时执行。
  • 数据依赖约束：MM指令必须等待两条LOAD完成（周期3才可发射），VADD必须等待MM完成，形成串行链。
  • 调度窗口：编译器后端通过此类调度器将乱序指令重排为满足硬件约束的发射序列，本案例中的列表调度算法是实际产品中常用启发式方法的基础版本。

本案例的调度器仅实现了FIFO优先级策略，实际NPU编译器还会结合循环展开、软件流水线、存储层级感知等更复杂的启发式规则，但依赖检测与资源占用跟踪的基本框架与本实现一致。后续案例将在此调度器基础上扩展多核分配、存储冲突消解等优化。

← 上一章 📖 返回目录 下一章 →