粗粒度可重构阵列处理器编译工具研究

论文摘要

近年来,可重构处理器在加速计算密集型应用方面显得越来越重要,越来越多的粗粒度可重构体系结构被提了出来,主要原因在于它同时综合了ASIC和通用处理器的优点。然而,如何把应用程序自动合理地映射到可重构的硬件资源上仍然是个亟待解决的问题。如果每个应用都需要手工映射到硬件上,这无疑大大地增加应用工作量并且影响资源的利用率。针对存在的这些问题,本文研究在LEAP(Loop Engine on Array Processor)粗粒度可重构阵列处理器上的程序映射方法,并设计和实现了LEAP编译工具,实现了循环在可重构阵列上映射的自动化。本文提出了“基于中间表示”的设计方案,它不直接作用于源程序,而是通过对源程序LANCE中间表示的分析来获取目标程序的信息。为了获取源程序中循环的信息,提出了在LANCE中间表示的基础上自动提取出程序中的循环和分析循环结构特征的一般方法,并实现了这两个功能模块。针对LEAP粗粒度可重构阵列处理器的阵列结构和指令结构,提出了把循环逻辑映射到LEAP上的方法,并针对LEAP处理器设计和实现了逻辑映射工具。对于循环中的流相关,反相关,输入相关及迭代间的流相关,本文提出了逻辑映射在阵列结构上时解决这些数据相关的方法,并在实现逻辑映射工具时合理地融入了这些方法,有效地解决了数据相关的问题。为了实现循环数据流图在LEAP上的物理映射,提出了同时布局布线,利用模拟退火思想优化布局和多配置二进制文件生成的方法,并采用这些方法实现了物理映射工具。为了说明编译工具的有效性和优越性,本文选取了部分典型科学计算中的核心循环和典型媒体处理中的核心循环,将这些循环用编译工具和手工映射的结果进行对比分析。测试结果表明:LEAP编译工具设计合理、功能正确、实现有效。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 可重构计算
• 1.1.2 粗粒度可重构体系结构
• 1.2 粗粒度可重构体系结构—LEAP
• 1.3 研究的内容和成果
• 1.3.1 研究内容
• 1.3.2 研究成果
• 1.4 论文结构
• 第二章 LEAP 粗粒度可重构阵列处理器
• 2.1 LEAP 的基本结构与主要特点
• 2.1.1 LEAP 的基本结构
• 2.1.2 LEAP 的主要特点
• 2.2 LEAP 的处理单元
• 2.2.1 存储处理单元
• 2.2.2 计算处理单元
• 2.3 LEAP 的循环映射
• 2.4 LEAP 的配置与重构
• 2.4.1 LEAP 的配置
• 2.4.2 LEAP 的三种配置流
• 2.4.3 LEAP 的重构
• 2.5 LEAP 描述语言
• 2.6 LEAP 配置流的示例
• 2.7 本章小结
• 第三章 LEAP 编译工具总体设计
• 3.1 设计方案
• 3.1.1 编译工具设计策略
• 3.1.2 设计思想
• 3.2 LEAP 编译工具总体流程设计
• 3.3 LEAP 编译工具功能模块设计
• 3.4 设计平台LANCE2 简介
• 3.4.1 设计平台的选择
• 3.4.2 LANCE2 系统的主要特征
• 3.4.3 LANCE2 系统的结构和工作流程
• 3.4.4 LANCE 中间表示
• 3.5 本章小结
• 第四章 循环程序的逻辑映射
• 4.1 基本循环形态
• 4.2 循环抽象和建模
• 4.2.1 循环的抽象
• 4.2.2 循环模型研究
• 4.3 逻辑映射
• 4.3.1 存储信息的数据结构
• 4.3.2 定位循环体，识别归纳变量
• 4.3.3 构造通用的信息库
• 4.3.4 生成LEAP 逻辑连接关系
• 4.4 数据流中相关处理
• 4.4.1 数据相关的基本概念
• 4.4.2 数据相关分析概述
• 4.4.3 数据直传窗口
• 4.4.4 寻找数组相关信息的算法
• 4.5 本章小结
• 第五章 循环程序物理映射
• 5.1 布局算法
• 5.1.1 布局算法的总体框图
• 5.1.2 布局算法的输入接口
• 5.1.3 利用构造树生成初始布局
• 5.1.4 利用模拟退火算法来改进
• 5.2 布线算法
• 5.2.1 布线算法的基本思想
• 5.2.2 算法改进
• 5.2.3 布线示例
• 5.3 多配置二进制文件生成工具
• 5.4 测试结果
• 5.5 本章小结
• 第六章 编译工具的测试与验证
• 6.1 测试方案
• 6.2 LIVERMORE FORTRAN KERNELS 核心循环
• 6.2.1 Kerne15
• 6.2.2 Kerne114
• 6.3 MEDIABENCH 核心循环
• 6.3.1 量化算法
• 6.3.2 Rasta 算法
• 6.3.3 Mesa 算法
• 6.4 本章小结
• 第七章 结束语
• 7.1 工作总结
• 7.2 工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果