多核平台计算机视觉应用并行优化关键技术研究

摘要

多核体系结构是计算机发展历史上的重大转变，在传统的通过频率提升来提高处理器性能的方法遇到巨大困难的情况下，人们开始转向在相对低的主频下，通过提高半导体的密度，集成更多处理单元来提供计算能力的持续提升，以满足计算机视觉等新兴的万亿级别RMS(Tera-Scaled Recognition，Mining，Synthesis)应用的计算需求。近年来，多核和众核体系的快速发展和广泛应用为此类应用的实时实现提供了硬件基础和可能。不过，由于必须通过并行的方式才能获得对硬件计算能力的有效利用，如何有效地发掘可用的程序并行性到可用的硬件并行性的最佳映射，成为了多核和众核体系平台下计算机视觉应用开发面临的一个关键挑战。本文以车辆辅助驾驶系统中车辆识别算法这一核心的计算机视觉应用的并行化研究为背景，从应用模型和负载分析入手，研究了此类应用的计算特性，识别出此类应用并行优化中需要满足的三个关键能力需求;总结了六种关键的数据并行模式;并且提出:在领域知识的指导下，结合先验的并行策略，基于实时负载特性、硬件特性的动、静态结合的并行优化是针对上面问题的一个比较理想的解决思路。本文具体工作内容如下:
　　首先，针对并行性的抽象和表达技术，本文在TStreams模型的基础上，通过引入组成(Composition)关系、等价(Equivalence)关系和特性权重(Character Weight)的概念，提出了一个改进的TStreams并行计算模型。可以以一致的形式对包括数据并行性、任务并行性、流水线并行性等在内的各种算法并行性的抽象表达提供方便的支持;同时，该模型还将作为算法和硬件交互的公共“交流语言”，在后续并行优化过程中，有效地支持多层次、多粒度的并行性发掘。
　　其次，针对并行性发掘技术，本文引入了面向计算机视觉应用的领域编程语言(DSL)用以描述算法特性以及优化过程中可适用的优化规则。优化规则是领域知识的抽象，针对特定函数给出的优化规则描述了该函数各种可能的变形实现。本文引入了编译驱动的自动优化工具，可根据优化规则描述，构造算法并行优化的解空间，并以半自动化的方式查找最适合的并行优化候选解空间。由此，可将并行优化工作中复杂、繁琐的优化“决策”工作转化为目标算法和多核、众核平台的可用并行性和算法领域知识规则的“描述”工作，极大地降低了并行优化的难度，提高了并行优化的效率。
　　第三，针对动态任务调度技术，本文引入了面向特性权重的运行时环境的概念。运行时环境根据实时输入数据，利用目标程序的扩展TStreams模型表示中的组成关系和特性权重信息，从自动优化工具生成的候选解空间中动态选择合适的优化算法，并进行底层优化，以获得局域性好、并行度高、负载均衡的动态调度。
　　最后，本文将上述研究成果综合在一起，以工具和运行时库(Runtime Library)的形式提供了一个动静态结合的，针对计算机视觉应用的半自动并行优化框架原型（FAPOF, Feature Awared Parallel Optimization Framework），并应用于面向辅助驾驶系统(DAS)的车辆识别算法的并行优化过程中，取得了良好的并行优化效果。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．1．1 计算机视觉应用的复杂性

1．1．2 多核和众核平台的复杂性

1．1．3 并行开发任务的复杂性

1．2 存在问题和相关研究方向

1．2．1 存在问题

1．2．2 相关研究方向

1．3 主要研究内容和目标

1．4 论文结构和章节安排

第2章 计算机视觉应用并行优化研究现状

2．1 计算机视觉应用特性分析

2．1．1 计算机视觉应用模型

2．1．2 计算机视觉应用负载分析

2．1．3 并行优化关键能力需求

2．2 多核平台并行优化相关研究

2．2．1 多核和众核硬件体系

2．2．2 并行计算模型

2．2．3 并行编程语言和规范

2．2．4 自动优化工具和框架

2．3 并行优化评估方法

2．3．1 并行加速比

2．3．2 负载均衡度

2．4 本章小结

第3章 并行计算模型和优化方法研究

3．1 并行计算模型研究

3．1．1 存在问题

3．1．2 扩展的TStreams模型

3．1．3 并行性描述能力的改进

3．2 并行优化方法研究

3．2．1 FAPOF：并行优化框架

3．2．2 细化的并行优化评估方法

3．3 本章小结

第4章 并行优化核心过程关键技术研究

4．1 并行性抽象和表达

4．1．1 基于扩展模型的中间表达

4．1．2 声明性并行说明语言

4．2 并行性发掘和发现

4．2．1 并行性发掘的基本过程

4．2．2 并行性发掘的规则

4．2．3 并行性发掘的搜索算法

4．3 输入依赖的动态调度

4．3．1 动态输入评估和调度算法

4．3．2 FAPOF动态调度的性能改进

4．4 本章小结

第5章 并行优化框架实现技术研究

5．1 并行优化框架结构

5．2 DSL语言支持

5．2．1 DSL编译器构造

5．2．2 中间表达构建API

5．2．3 骨架中间表达生成

5．3 自动优化工具支持

5．3．1 高层优化(HLO)实现

5．3．2 底层优化(LLO)实现

5．4 运行时环境支持

5．4．1 DWE模块实现

5．4．2 动态调度支持的相关问题

5．5 本章小结

第6章 并行优化关键技术应用和评估

6．1 目标算法与实验平台简介

6．1．1 车辆识别算法简介

6．1．2 多核体系实验平台简介

6．1．3 实验样本和测试方法

6．2 车辆识别算法整体的优化

6．3 基于知识的分割算法的优化和评估

6．3．1 串行算法简介

6．3．2 基于FAPOF的优化

6．3．3 分割算法优化评估

6．4 基于知识的识别算法优化和评估

6．4．1 串行算法简介

6．4．2 基于FAPOF的优化

6．4．3 基于知识的识别算法优化评估

6．5 基于机器学习的识别算法优化和评估

6．5．1 基于机器学习的识别算法简介

6．5．2 基于FAPOF的优化

6．5．3 机器学习算法优化评估

6．6 算法整体的优化性能评估

6．7 小结

第7章 结论

7．1 研究总结

7．2 未来研究方向

参考文献

致谢

作者简介

攻读学位期间发表的论文及科研工作