4. 软件流水线调度实现

任务说明

在NPU指令调度中，循环体内部存在数据依赖（如累加、数组连续读写）时，默认顺序执行会导致流水线频繁停顿。本案例实现一个软件流水线调度器：将循环迭代拆分为取指、执行、写回三个阶段，通过迭代间重叠（即第i+1轮的取指与第i轮的执行并行）隐藏访存延迟，最终输出调度后的指令序列及理论停顿周期数。

核心实现

// sw_pipeline_scheduler.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STAGES 3
#define MAX_INSNS  64

typedef enum { FETCH, EXEC, WRITEBACK } Stage;

typedef struct {
    int opcode;      // 0: load, 1: compute, 2: store
    int dest;
    int src1;
    int src2;
    int iter;        // 所属迭代编号
    Stage stage;
} Insn;

// 解析单条循环体指令（迭代无关部分）
static Insn parse_insn(const char* line, int iter) {
    Insn ins = {0};
    char op[16];
    sscanf(line, "%s r%d r%d r%d", op, &ins.dest, &ins.src1, &ins.src2);
    if (strcmp(op, "LOAD") == 0) ins.opcode = 0;
    else if (strcmp(op, "FMA") == 0) ins.opcode = 1;
    else if (strcmp(op, "STORE") == 0) ins.opcode = 2;
    ins.iter = iter;
    return ins;
}

// 检查两条指令是否存在数据依赖（RAW/WAR/WAW）
static int has_dependency(const Insn* a, const Insn* b) {
    if (a->dest == b->src1 || a->dest == b->src2) return 1;  // RAW
    if (a->src1 == b->dest || a->src2 == b->dest) return 1;  // WAR
    if (a->dest == b->dest) return 1;                        // WAW
    return 0;
}

// 软件流水线主调度函数
// loop_body: 循环体指令文本（每行一条，最多3条）
// unroll: 展开迭代数（即重叠的迭代个数）
// 返回调度后的指令总数
int software_pipeline(const char* loop_body[], int body_len, int unroll,
                      Insn* out, int max_out) {
    Insn body[MAX_INSNS];
    int i, j, k, count = 0;

    // 解析原始循环体（迭代0）
    for (i = 0; i < body_len; i++) {
        body[i] = parse_insn(loop_body[i], 0);
    }

    // 生成展开后的指令序列（迭代0..unroll-1）
    Insn expanded[MAX_INSNS];
    int exp_cnt = 0;
    for (i = 0; i < unroll; i++) {
        for (j = 0; j < body_len; j++) {
            expanded[exp_cnt] = body[j];
            expanded[exp_cnt].iter = i;
            exp_cnt++;
        }
    }

    // 按软件流水线规则重排：
    // 规则：优先发射当前迭代的FETCH；若与已发射指令无依赖，则发射EXEC；
    //       再尝试WRITEBACK。实际采用简化模型：按阶段轮转发射。
    // 这里实现一个可验证的启发式：对每个周期，从所有未发射指令中
    // 选择“阶段号最小且与已发射指令无依赖”的指令发射。
    int emitted[MAX_INSNS] = {0};
    int cycle = 0;
    while (count < exp_cnt && count < max_out) {
        int progress = 0;
        for (i = 0; i < exp_cnt; i++) {
            if (emitted[i]) continue;
            // 计算该指令当前应处的阶段（基于迭代号和原始位置）
            int stage_idx = (expanded[i].iter * body_len + (i % body_len)) % MAX_STAGES;
            // 检查与已发射指令的依赖
            int dep = 0;
            for (j = 0; j < count; j++) {
                if (has_dependency(&out[j], &expanded[i])) { dep = 1; break; }
            }
            if (!dep) {
                out[count] = expanded[i];
                out[count].stage = (Stage)stage_idx;
                emitted[i] = 1;
                count++;
                progress = 1;
                if (count >= max_out) break;
            }
        }
        if (!progress) {
            // 无进展说明存在循环依赖，强制发射最早未发射指令（打破死锁）
            for (i = 0; i < exp_cnt; i++) {
                if (!emitted[i]) {
                    out[count] = expanded[i];
                    out[count].stage = FETCH;
                    emitted[i] = 1;
                    count++;
                    break;
                }
            }
        }
        cycle++;
        if (cycle > 100) break; // 安全保护
    }
    return count;
}

// 计算理论停顿周期数（与顺序执行对比）
int compute_stall_cycles(const Insn* sched, int total, int body_len) {
    // 顺序执行周期 = 总指令数（假设每周期1条）
    // 软件流水线周期 = 最大(迭代数*阶段数, 总指令数/流水线宽度)
    // 此处简化：停顿 = 顺序周期 - 调度后周期（调度后周期近似为指令数/3）
    int seq = total;
    int piped = (total + 2) / 3;  // 3级流水线理想吞吐
    return seq - piped;
}

int main() {
    // 示例循环体：A[i] = A[i-1] * 2 + B[i]
    // 对应三条指令：LOAD r1 <- r2(基址) ; FMA r3 <- r1, r4 ; STORE r3 -> r5
    const char* loop_body[] = {
        "LOAD r1 r2 r0",   // 从内存加载A[i-1]到r1
        "FMA  r3 r1 r4",   // r3 = r1 * 2 + B[i]（r4存B[i]）
        "STORE r3 r5 r0"   // 将r3写回A[i]
    };
    int body_len = 3;
    int unroll = 4;        // 重叠4个迭代

    Insn schedule[MAX_INSNS];
    int cnt = software_pipeline(loop_body, body_len, unroll,
                                schedule, MAX_INSNS);

    printf("=== 软件流水线调度结果 ===\n");
    printf("展开迭代数: %d, 调度指令数: %d\n", unroll, cnt);
    printf("Cycle | Iter | Stage | Opcode | Dest | Src1 | Src2\n");
    printf("-----------------------------------------------\n");
    for (int i = 0; i < cnt; i++) {
        const char* stage_str[] = {"FETCH", "EXEC", "WRITEBACK"};
        const char* op_str[] = {"LOAD", "FMA", "STORE"};
        printf("%5d | %4d | %-9s | %-6s | r%-3d | r%-3d | r%-3d\n",
               i, schedule[i].iter, stage_str[schedule[i].stage],
               op_str[schedule[i].opcode], schedule[i].dest,
               schedule[i].src1, schedule[i].src2);
    }

    int stalls = compute_stall_cycles(schedule, cnt, body_len);
    printf("\n理论停顿周期数（对比顺序执行）: %d\n", stalls);
    printf("判定: 若停顿数 > 0 且调度序列无重复/遗漏，则调度有效\n");
    return 0;
}

编译与运行

gcc -o sw_pipeline sw_pipeline_scheduler.c -Wall
./sw_pipeline

验证方法

运行程序后，观察输出调度表：

1. 完整性：调度指令总数应为 body_len × unroll = 12，每条原始指令恰好出现一次；
2. 重叠性：不同迭代（Iter列）的指令应交叉出现在相邻周期（Cycle列），而非按迭代顺序连续排列；
3. 停顿减少：输出的“理论停顿周期数”为正值，且小于顺序执行时的停顿（顺序执行时停顿为总指令数-1）；
4. 依赖保持：任意两条存在数据依赖的指令（如LOAD r1与FMA使用r1），在调度序列中前者必须位于后者之前。

满足以上4点即可判定软件流水线调度实现正确。