《第十六课、收缩阵列与静态调度》由会员分享，可在线阅读，更多相关《第十六课、收缩阵列与静态调度（13页珍藏版）》请在金锄头文库上搜索。
1、第十六课、收缩阵列与静态调度 一、收缩阵列 1、动机 目标：设计一个加速器具有： 简单，常规的设计（保持独特的小零件和定期） 高并发、高性能 平衡计算和 I / O（内存）带宽 思路：替换单个处理单元（PE）与 PE 的规则排列，仔细编排 PE 之间的数据流 量 好处：最大化在从内存带来的单一数据元素完成的计算 2、收缩阵列 3、收缩架构 基本原则：更换单个 PE 与 PE 的规则排列，仔细编排 PE 之间的数据流量 平衡计算和存储器带宽 与流水线的不同： 有个人的 PE 阵列结构可以是非线性的和多维的 PE 连接可以是多向的（和不同速度） PE 设备可以具有本地存储器和执行内核（而不是一指令
2、块的） 4、收缩计算实例：卷积 y1 = w1x1 + w2x2 + w3x3 y2 = w1x2 + w2x3 + w3x4 y3 = w1x3 + w2x4 + w3x5 值得单独实现加法和乘法，使重叠的 ADD/ MUL 执行 一个需要仔细协调时的数据元素输入到阵列 当输出缓冲 下面这些时候会更严重 数组维数增加 PE 之间在延迟方面是难以预料的 5、流水线并行度 6、流水线计划阶段 循环迭代被分成称为阶段的代码段 线程在不同的内核执行阶段 7、Pipelined File Compression 例子 8、The WARP Computer 二、静态指令调度 1、预测（条件执行） 思路
3、：编译器将控制依赖转换成数据依赖 分支被消除 在预测计算上每个指令都具有一个预测位 只有具有 TURE 的指令才会被允许（其它变成 NOP 指令） 2 循环展开 理念：一个迭代中复制循环体多次 +降低环路维护开销 +放大基本数据块（和分析范围） - 如果迭代次数没有解开因子的倍数？ （需要额外的代码来检测这个） - 增加代码大小 3、一些术语：基本与原子块 基本块：一个指令序列（块）与一个单一的控制流入口点和单一控制流退出点 一个基本数据块执行不间断（如果没有异常/中断） 区块：一个指令块，其中全部是完整的说明或不完整 在最现代的 ISA，执行的原子单元是指令的粒度 一个基本块可以看作是原子块
4、（如果没有异常/中断和在执行过程中可观察 到的副作用） 人们可以在原子块中自由地重新排列指令，只受真实数据依赖 4、VLIW：寻找独立操作 基本块里面有限制指令级并行（如果基本块比较小） 找到在并行执行多条指令，编译器需要考虑多个基本块 问题：移动上述分支指令是不安全的，因为指令没有允许执行 思路：通过寻找频繁执行路径在编译时放大数据块 跟踪调度 超级调度 Hyperblock 调度 5、安全性和合法性的代码移动 投机代码运动的两个特点： 安全性：无论是否可能出现伪异常 合法性：是否结果将始终是正确的 代码运动的四种可能的类型： 7、跟踪调度 跟踪：在控制流图频繁执行的路径 思路：在 trac
5、e 查找独立操作打包成 VLIW 指令。 通过 profile 分析确定 编译器增加了修复行动代码的正确性 跟踪调度理念 What bookeeping is required when Instr 1 is moved below the side entrance in the trace? What bookeeping is required when Instr 5 moves above the side entrance in the trace? 8、跟踪调度代码矫正问题 有时需要复制的指令不止一次，以确保所有路径的正确性（见 C 以下） 9、跟踪调度概述 跟踪选择 选择种子块
6、（最高频率基本块） 扩展跟踪（以及最高频率边） 不交叉回环边缘 最大的跟踪长度 跟踪调度 整个跟踪时建立数据优先图 执行列表调度和分配寄存器 添加补偿代码保持语义的正确性 推断代码移动（向上） 上述移动在确保安全的分支指令 10、数据优先图 11、VLIW 调度表 分配优先级 计算数据就绪列表（DRL） - 所有操作的先后已排定。 从 DRL 的优先顺序选择，同时检查资源约束 将最新就绪的操作添加到 DRL 和重复下一条指令 12、跟踪调度例子 fdiv f1, f2, f3 fadd f4, f1, f5 beq r1, $0 ld r2, 0(r3) add r2, r2, 4 beq r
7、2, $0 fsub f2, f2, f6 st.d f2, 0(r8) add r3, r3, 4 add r8, r8, 4 0 stall 0 stall B3 B6 1 stall fdiv f1, f2, f3 fadd f4, f1, f5 beq r1, $0 ld r2, 0(r3) add r2, r2, 4 beq r2, $0 fsub f2, f2, f6 st.d f2, 0(r8) add r3, r3, 4 add r8, r8, 4 B3 B6 fadd f4, f1, f5 Split fadd f4, f1, f5 comp. code fdiv f1, f
8、2, f3 fadd f4, f1, f5 beq r1, $0 ld r2, 0(r3) add r2, r2, 4 beq r2, $0 fsub f2, f2, f6 st.d f2, 0(r8) add r3, r3, 4 add r8, r8, 4 B3 B6 fadd f4, f1, f5 Split add r3, r3, 4 add r8, r8, 4 Join comp. code fadd f4, f1, f5 comp. code fdiv f1, f2, f3 beq r1, $0 ld r2, 0(r3) add r2, r2, 4 beq r2, $0 fsub f
9、2, f2, f6 st.d f2, 0(r8) fadd f4, f1, f5 add r3, r3, 4 add r8, r8, 4 fadd f4, f1, f5 ld r2, 4(r3) fadd f4, f1, f5 fsub f2, f3, f7 add r2, r2, 4 beq r2, $0 fsub f2, f2, f6 st.d f2, 0(r8) add r3, r3, 4 add r8, r8, 4 add r3, r3, 4 add r8, r8, 4 B3 B6 13、超级调度 跟踪：多进入，多退出块 超级块：单一进入，多退出块 例子： 14、超级调度缺点、超级调度
10、缺点 - 仍然是 profile-dependent - 如果有一个不带偏见的分支，没有一个单一的频繁执行路径 - 减少超级块的大小 - 代码膨胀和额外的固定式执行代码 15、Hyperblock 调度：调度： 理念：用预测以消除偏见的分支和增加超级数据块的大小 Hyperblock：单一入口，使用预测消除内部控制流程多出数据块（如果卷积） 优势 +减少偏见的分支机构对调度数据块大小的影响 缺点 - 需要条件执行的支持 - 条件执行的所有缺点 16、Hyperblock 形成：形成： Hyperblock 形成： 1.数据块选择 2. Tail duplication 3.如果 conversion 数据块的选择： Tail duplication
