片上高性能嵌入式计算—面向软基带的应用并行处理模型及体系结构

1、片上高性能嵌入式计算面向软基带的应用并行处理模型及体系结构 分类号 TP302 学号 07069036 密级 公开 工学博士学位论文 片上片上高性能高性能嵌入式嵌入式计算计算面向面向软基带软基带的应用的应用 片上片上高性能高性能嵌入式嵌入式计算计算面向面向软基带软基带的的应用应用 并行处理并行处理模型及体系结构模型及体系结构 并行处理并行处理模型及体系结构模型及体系结构 博士生姓名 张波涛 学 科 专 业 计算机科学与技术 研 究 方 向 微处理器体系结构 指 导 教 师 刘衡竹 研究员 国防科学技术大学研究生院国防科学技术大学研究生院 国防科学技术大学研究生院国防科学技术大学研究生院 二二一

2、一一年九一年九月 月 二二一一一年九一年九月月 On-Chip High Performance Embedded Computing Soft Baseband Application Parallel Processing Model Architecture CandidateZhang Botao Supervisor Professor Liu Hengzhu A dissertation Submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering in Co

3、mputer Science and Technology Graduate School of National University of Defense Technology ChangshaHunan coma September2011 独创性声明 - 学位论文版权使用授权书 - 国防科学技术大学研究生院博士学位论文 目目 录录 目目 录录 摘 要 i Abstract v 第一章 绪论 1 11 片上高性能嵌入式计算 1 com 片上高性能嵌入式计算概念 1 com 片上高性能嵌入式计算特征 2 12 软基带应用与计算类型发展 4 com 无线通信协议发展概述 4 com 基带处理

4、技术发展概述 5 13 面向软基带的片上高性能嵌入式计算的机遇和挑战 6 com VLSI 的发展带来了良好的发展机遇 6 com 不断提升的高计算量挑战 7 com 不断强化的低功耗挑战 8 com 不断加剧的硬实时挑战 9 14 相关研究工作 10 com 通信基带处理可编程专用处理单元研究现状 10 com 通信基带处理加速处理单元研究现状 12 com 通信基带处理单元互连结构研究现状 13 15 本文有关软基带处理体系结构的观点 14 16 本文主要工作和组织结构 15 com 本文主要工作和贡献 15 com 全文组织结构 18 第二章 软基带应用并行处理模型 19 21 引言 1

5、9 22 MIMO-OFDM 基带应用并行处理模型 20 com MIMO-OFDM 基带系统模型 20 com MIMO-OFDM 基带数据流模型 20 com MIMO-OFDM 基带空时二维层次数据并行模型 22 com MIMO-OFDM 基带 本原操作模型 24 23 MIMO-OFDM 基带典型系统演化 26 第 I 页 国防科学技术大学研究生院博士学位论文 com MIMO-OFDM 基带典型系统参数演进 26 com MIMO-OFDM 基带典型系统计算模式演化 28 24 面向软基带的片上系统体系结构模型 31 25 小结 31 第三章 面向软基带的向量处理单元体系结构与实现

6、 33 31 引言 33 32 可编程向量处理单元MPE 体系结构 34 com 数据类型定义 35 com 标 向量混合流水线 35 com 指令编码与汇编格式定义 36 com 指令派发机制 38 com 数据通路组织 39 com 核内存储组织方式 40 com 数据交换网络 41 33 实验与结果分析 44 com 原型设计流程与工具 44 com 测试程序性能评测 45 com 面积和功耗开销评估 47 34 面向软基带的片上 HPEC 体系结构演化 49 35 小结 51 第四章 面向软基带的多模多域无冲突并行存储结构 53 41 引言 53 42 多模多域无冲突并行存储模型 54

7、 com 经典 PMA 模型 54 com 无线通信应用访问模式分析 55 com MPMD-PMA 体系结构模型 57 43 多模多域无冲突并行存储系统实现 59 com 模式管理器 59 com 多域地址产生单元 61 com 流水线结构实现 62 44 实验与结果分析 63 com 硬件实现与开销比较 64 com 性能评估 66 45 小结 69 第 II 页 国防科学技术大学研究生院博士学位论文 第五章 FEC 加速单元算法体系结构与实现 71 51 引言 71 52 LDPC 码与 RMP-Min-Sum 译码算法 72 com LDPC 码概述 72 com RMP-Min-Su

8、m 算法描述 73 com RMP-Min-Sum 算法性能 77 com RMP-Min-Sum 算法复杂度 79 53 eIRA-LDPC 码译码加速单元 82 com eIRA-LDPC 码译码加速单元结构 82 com DVB-S2 LDPC 码译码加速单元实现与演化 86 54 便于流水均衡的关键多项式求解算法和硬件实现 90 com 关键多项式求解算法 91 com TD-iBM 算法描述 92 com 基于 TD-iBM 算法的 KES 结构 93 com 基于 TD-iBM 算法的 KES 实现 95 55 基于 TD-iBM KES 结构的 RS 译码加速单元 95 com

9、译码加速单元其他模块结构 96 com 基于 TD-iBM 的均衡三段宏流水线结构 97 com 实验结果和比较 98 56 FEC 加速单元的集成 99 57 小结 99 第六章 面向软基带的可预测异构 MPSoC 原型 101 61 引言 101 62 可预测时分复用总线 101 com 核间通信需求分析 101 com 软件可控时分复用总线 102 com PH-MPSoC 体系结构 105 63 PH-MPSoC 原型设计 106 com 简化的 LTE PDSCH 参数说明 106 com 原型映射性能评估 108 com PH-MPSoC 原型 110 64 小结 111 第七章

10、结束语 113 71 论文工作总结 113 第 III 页 国防科学技术大学研究生院博士学位论文 72 课题研究展望 115 致 谢 117 参考文献 119 作者在学期间取得的学术成果 129 攻读博士学位期间参加的科研项目 131 第 IV 页 国防科学技术大学研究生院博士学位论文 表 目 录 表 21 主流 MIMO-OFDM 基带协议的主要参数比较 19 表 22 典型 MIMO-OFDM 基带系统参数配置 27 表 31 MPE 指令执行周期 39 表 32 测试程序说明 45 表 33 原型面积和功耗评估 48 表 34 单 MPE 原型 FPGA 资源开销 49 表 4-1 域起

11、始地址产生模式 62 表 4-2 现有 PMA 配置和功能比较 64 表 4-3 MPMD-PMA 系统在 MPE 系统中的实现结果 66 表 51 LDPC 译码算法符号定义表 74 表 52 LDPC 译码器综合结果比较 87 表 53 全并行模式下主要逻辑功能的面积比例 89 表 5-4 DVB-S2 LDPC 码译码加速处理单元面积演变结果 90 表 54 KES 模块在 Viterx-2P 中的资源占用结果 95 表 55 相关 RS 译码器的译码效率比较 99 表 61 简化的 LTE PDSCH 原型参数 107 表 62 简化的 LTE PDSCH 接收系统初始流水映射结果统计

12、 109 表 63 任务流水段关键路径 ICDSN 优化结果 110 表 64 流水站优化搜索结果 110 表 65 PH-MPSoC 原型功耗面积统计分析 111 第 V 页 国防科学技术大学研究生院博士学位论文 第 VI 页 国防科学技术大学研究生院博士学位论文 图 目 录 图 11 移动通信系统演进路线图 4 图 12 无线通信收发信系统逻辑组成 5 图 13 移动通信协议基带处理计算量变化趋势 7 图 14 不断提升的效能需求以及相应处理器的效能分布 9 图 15 SIMD 典型结构代表SODA PE 11 图 16 可重构加速处理单元典型代表ADRES 12 图 17 NoC 互连典

13、型代表PicoChip 14 图 18 全文组织结构说明 18 图 21 MIMO-OFDM 基带系统模型 20 图 22 3GPP LTE FDD OFDMA 下行无线帧结构 23 图 23 MIMO-OFDM 系统 OFDM 符号层空时二维数据结构 24 图 24 Alamouti 编码过程示意图 25 图 25 8 点 FFT 操作流程 26 图 26 蝶型运算 26 图 27 一种典型 MIMO-OFDM 基带系统 27 图 28 发射机基带主要任务核心操作计算复杂度演变趋势 28 图 29 接收机基带主要任务核心操作计算复杂度演变趋势 29 图 210 基带核心任务 本原操作并行度演

14、变趋势 29 图 211 任务间通信流量演变趋势 30 图 212 面向软基带的片上系统体系结构模型框架 31 图 31 本章研究内容在片上 HPEC 体系结构框架 中的位置 33 图 32 可编程处理单元 MPE 结构 34 图 33 MPE 主要数据类型格式 35 图 34 Wi 主要算法的并行化程度 36 图 35 MPE 指令格式 37 图 36 MPE 汇编代码片段 38 图 37 MPE 指令派发机制 38 图 38 MPE 功能单元分布示意图 39 图 39 MBDMEM 存储体组织方式 41 图 310 2 种特殊簇间数据交换网络结构和示例 42 图 317 MPE 原型工具和

15、输出 44 图 318 典型测试程序复杂度的变化 46 第 VII 页 国防科学技术大学研究生院博士学位论文 图 319 多 MPE 结构和单 MPE 结构的性能比较 47 图 320 单 MPE 结构相对于 C64x 的加速比 47 图 321 单 MPE 原型 FPGA 版 图 49 图 322 面向软基带的 MPSoC 演化 50 图 41 本章研究内容在片上 HPEC 体系结构框架 中的位置 53 图 42 经典并行存储体系结构模型 54 图 43 Alamouti 算法在低位交叉编址系统中的访问冲突示例 55 图 44 LTE 下行参考信号的时频结构 常规循环前缀 56 图 45 M

16、PMD-PMA 体系结构模型顶层框 图 57 图 46 MPMD-PMA 存储组织模型 58 图 47 支 MPMD-PMA 系统所需的指令扩展 60 图 48 段查找表部件 SLUT 60 图 49 逻辑地址计算部件 LAC 61 图 410 模块地址计算部件 MAC 62 图 411 偏移地址计算部件 OAC 62 图 412 MPE 中 MPMD-PMA 的流水线结构 63 图 413 MPMD-PMA 系统主要部件 VLSI 开销 64 图 414 现有 PMA 系统 VLSI 开销比较 65 图 415 带 MPMD-PMA 系统的 MPE FPGA 版 图 65 图 416 ANG

17、 函数表达式 67 图 417 随机 SDR 访存序列加速比谱线 相对方案 2 68 图 418 类 GSM 访存序列加速比谱线 相对方案 2 68 图 419 随机 SDR 访存序列的加速比 69 图 420 类 GSM 访存序列的加速比 69 图 51 本章研究内容在片上 HPEC 体系结构框架 中的位置 71 图 52 LDPC 码校验矩阵和 Tanner 图 72 图 53 对数域 BP 算法描述 75 图 54 Min-Sum 算法描述 75 图 55 RMP 调度 BP 算法描述 76 图 56 RMP-Min-Sum 算法描述 77 图 57 RMP-Min-Sum 算法性能分析

18、结果 79 图 58 RMP-Min-Sum 算法译码所需处理器发射并行度 81 图 59 扩展非规则累积 LDPC 码的 Tanner 图 82 图 510 eIRA-LDPC 码译码数据通路 83 第 VIII 页 国防科学技术大学研究生院博士学位论文 图 511 功能单元 CFU 的逻辑结构 84 图 512 eIRA 型 LDPC 码译码控制流 85 图 513 DVB-S2 LDPC 码译码加速单元顶层结构 86 图 514 360 并行度 DVB-S2 LDPC 码译码处理阵列结构 86 图 515 各种码长和码型的 DVB-S2 LDPC 码译码净吞吐率 88 图 516 各种并

19、行度的 DVB-S2 LDPC 码译码净吞吐率 90 图 517 TD-iBM 算法流程描述 93 图 518 t 16 2 时的基于 TD-iBM 算法的 KES 结构 94 图 519 KES 模块的 FPGA 版 图 95 图 521 RS 译码器三段宏流水线结构 97 图 522 流水线均衡分布情况 98 图 523 三段宏流水结构 FPGA 版 图 98 图 61 SC-TDM 总线结构 103 图 63 SC-TDM 总线调度状态机 104 图 64 示例数据结构和调度代码 105 图 65 图 314 中调度程序对应的总线时序 105 图 66 基于双总线的 PH-MPSoC 1

20、06 图 67 简化的 LTE PDSCH 系统任务图和初始流水模型 108 第 IX 页 国防科学技术大学研究生院博士学位论文 第 X 页 国防科学技术大学研究生院博士学位论文 摘 要 以无线通信为代表的高性能嵌入式计算 已深入到国民生活工业生产和军事 科技等各个领域由于各种高性能嵌入式计算 目标应用的计算复杂度功耗预算 实时性约束变化多样且不断加强当前高性能嵌入式计算正在经历 由以通用数字 信号处理器和通用高性能嵌入式处理器为中心 的传统高性能嵌入式计算向领域优 化高性能嵌入式计算转变 无线通信协议不断演进 人们对多模通信的需求不断 增加 采用可编程处理技术完成基带处理的软基带应用逐渐兴起

21、 由于具备高计 算复杂度高性能功耗比约束强实时性的特点软基带应用成为了推动高性能 嵌入式计算模式转变的主要 因素之一使得高性能嵌入式计算的体系结构和实现 技术面临全新的挑战特别是 以 MIMO-OFDM Multi-Input Multi-Output Orthogonal Frequency Division Multiplexing 系统为代表的软基带应用 的计算需求随着无线通 信系统的演进不断强化 给面向软基带 的片上系统体系结构设计带来了前所未有 的挑战研究面向 以 MIMO-OFDM 系统为代表的软基带应用的片上高性能嵌入式 计算体系结构具有明显意义 本文在总结分析 MIMO-OFD

22、M 系统模型的基础上对以 MIMO-OFDM 基带 系统为代表的软基带应用并行处理模型面向软基带的可预测异构多核体系结构 面向软基带的多模多域无冲突并行存储结构LDPC Low Desity Parity Check 码 译码算法和加速处理单元体系结构 以及 Reed Solomon RS 码译码算法和加速 理单元体系等几个方面 的重点内容展开了深入研究 概括本文所取得 的创新性工 作主要有以下几点 A 给出了面向基于 MIMO-OFDM 软基带的应用并行处理模型包括数据流模型 空时二维数据并行模型以及 本原操作模型数据流模型描述了基带核心任 务之间的数据流关系以及流量量化模型空时二维数据并行

23、模型描述了核心任 务内部存在的特有数据级并行层次和并行度 本原操作模型则描述了各种 基带任务的任务本身所特有的操作序列模型 通过并行处理模型实例分析了典 型 MIMO-OFDM 基带系统计算模式的演化过程包括核心操作的复杂度演化 本原操作并行度演化以及任务间通信流量演化 B 提 出并研究了领域优化可编程处理单元 领域优化可编程处理单元采用标量 向量混合处理技术并借助 VLIWVery Large Instruction Word 和 SIMDSingle InstructionMultiple Data-stream 技术支持目标应用 的各种计算模式 当采用 SIMD 技术加速核心算法的本原操

24、作时考虑到存在大量簇间数据交换操作 本文所提的领域优化可编程向量处理单元内建支 了通用以及若干种专用的 簇间数据交换网络本文采用 电子系统级设计方法完成了领域优化可编程向量 第 i 页 国防科学技术大学研究生院博士学位论文 处理单元的建模和实现并通过典型算法分析了领域优化可编程向量处理单元 相对于传统信号处理器的加速比结果表明所研究的可编程向量处理单元在 理和 目标应用密切相关的核心算法时具有比较明显的加速比 C 在总结软基带应用的主要访存模式的基础上提出了专用存储组织模型并基于 该存储组织模型提 出了支 主要访存模式无冲突访问的可扩展多模多域无冲 突并行存储体系结构模型和实现技术结合所提领域

25、专用可编程处理单元进行 访存通路流水线实现并针对无线通信 目标应用的存储特点进行了仿真 实现 结果表明本文所提 出的多模多域无冲突并行存储体系结构的扩展性良好且实 现开销和相关存储结构基本相 同仿真结果表明针对无线通信 目标应用可 扩展多模多域无冲突并行存储体系结构相比于传统并行存储体系结构有明显 的加速比 D 针对前 向纠错系统中新近应用较广 的具有很高纠错性能的 LDPC 码的译码复 杂度较高的实 际提 出了 RMP 调度最小和算法 RMP-Min-Sum 算法 RMP-Min-Sum 算法采用 了行消息传递方式降低算法的迭代次数并采用最小 和译码算法 消除译码算法中的非线性操作 降低硬件

26、 实现代价 仿真表明 RMP-Min-Sum 的译码性能和传统和积算法相比具有相当性能而复杂度则明 显降低 本文研究 了 RMP-Min-Sum 软译码的可行性研究表明当前可编程 理器无法高效能实现长帧 LDPC 码的译码 最后针对扩展非规则累积 LDPC 码 给出了基于 RMP-Min-Sum 算法的并行加速单元体系结构结合 DVB-S2 LDPC 码进行了加速单元实现并对加速单元的并行度复杂度以及吞吐率进行了演 化实现结果表明采用 RMP-Min-Sum 算法的 LDPC 码译码加速单元在保证 提供同等量级的吞吐率的基础上可大幅降低硬件开销 E 提 出了支 RS 码译码结构的宏流水负载均衡

27、的关键多项式求解算法 TD-iBM 算法 TD-iBM 算法采用了分时调度各个伽罗华域乘法器技术通过时间换取 面积的方式在保证译码吞吐率的 同时提高了译码加速单元宏流水的均衡度 并降低了译码加速单元的面积开销提高了译码效率 本文基于 TD-iBM 算法 实现了 RS 255 223 码型以及相关截断码的译码加速单元实验表明与 现有的主要 RS 译码器相比本文所实现的 RS 译码加速单元具有一定译码效 率优势 F 基于可编程向量处理单元以及若干前 向纠错加速单元提 出并研究了可预测多 核片上系统体系结构以及原型系统 本文采用片内总线作为多核互连的基础 并针对强实时性需求引入了软件可控的时分复用总

28、线该总线以很小硬件代价 提供 了设计时可预测可控的总线分配模式且设计人员可通过编制不 同总线 调度程序支持各种总线分配策略考虑到软件可控的时分复用总线提供 了设计 第 ii 页 国防科学技术大学研究生院博士学位论文 时可预测可控的总线分配策略其为日益增加的总线功耗的降低提供 了可能 基于可编程向量处理单元 前向纠错加速单元以及软件可控的时分复用总线 给出了可预测多核片上系统体系结构原型并给出了面向简化的 MIMO-OFDM 基带系统流水映射方式的优化原型实现 综上所述本文面向以 MIMO-OFDM 基带系统为代表的软基带应用研究了 应用并行处理模型 领域优化多核体系结构和实现技术高效能并行存储

29、体系结 构以及前 向纠错系统核心算法改进和加速实现技术 对于推动面向软基带的片上 高性能嵌入式计算的研究和实用化具有一定的意义和价值 关键词 片上高性能嵌入式计算软基带应用并行处理模型异构多核体 系结构无冲突并行存储结构前向纠错加速单元 第 iii 页 国防科学技术大学研究生院博士学位论文 第 iv 页 国防科学技术大学研究生院博士学位论文 Abstract High Performance Embedded Computing HPEC including wireless computing is ubiquitous in society life industry applicatio

30、n and military technology The computing complexity power budget and real-time constraint of different HPEC applications are varied and strengthening the morden HPEC is undergoing the transformation from the traditional HPEC based on general Digital Signal Processor and general high performance embed

31、ded processor to domain specific HPEC The soft baseband which is resulting from the evolution of wireless protocols and the requirements of muti-mode communication is one of the main driving applications of domain specific HPEC The architecture design of On-Chip High Performance Embedded Computing O

32、CHPEC for software baseband is being challenged for its high computing complexity high performance power ratio constraint and high real-time constraint especially when MIMO-OFDM baseband system is involved Besides to meeting the computing requirements of the evoluting wireless protocols is also an i

33、ssue of architecture design of OCHPEC for soft baseband Based on the analysis of the MIMO-OFDM system model this dissertation focuses on the following research points soft baseband application parallel processing model for MIMO-OFDM Predictable Heterogeneous Multi-Processor System-on-Chip PH-MPSoC a

34、rchitecture multi-pattern multi-domain conflict-free parallel memory architecture Low Desity Parity Check LDPC code decoding algorithmaccelerator and Reed Solomon code decoding algorithmaccelerator The key contributions are summarized as follows A The application parallel processing model for MIMO-O

35、FDM based soft baseband is introduced including data stream model space-time 2-dimension data level parallel model and atom operaion model The data stream model describes the data stream dependency relationship between the baseband tasks and the stream quantifing model space-time 2-dimension data le

36、vel parallel model describes the data level parallelism of the baseband tasks atom operaion model describes the specific operaion sequences of MIMO-OFDM baseband tasks A typical MIMO-OFDM baseband system is analyzed based on this application parallel processing model the complexity evolution of the

37、kernel operaion the parallelism evolution of the atom operaions and the stream flux evolution of the tasks are showed B Domain specific programmable process unit is proposed and researched The proposed programmable process unit adopts scalar and vector hybrid processing technique It introduces VLIW

38、and SIMD to support the varied computing patterns in target applications It introduces general and application 第 v 页 国防科学技术大学研究生院博士学位论文 specific inter-cluster data exchange network to accerating the atom operaion when SIMD technique is used ESL methodology and tools are used to model and implement t

39、he domain specific programmable process unit Some typical algorithms are used for evaluating the performance of the domain specific programmable process unit The results shows the proposed domain specific programmable process unit is more efficient than others in the kernel algorithms of wireless communication C A domain specific memory organization model is propose