基于人工智能搜索和数据依赖分析的程序并行化

摘要： 主要研究了自动并行化中的前端分析技术，引入了人工智能搜索方法，并且对其进行改进，实现了在评估函数支持下进行广度和深度搜索的方法。在前端分析的基础上探讨了传统的数据依赖分析方法，针对其不足之处出现的数组数据流分析技术，对其流程图算法进行描述，并且对终写树和写写树的思想加以实例说明。这一流程经过测试后可以很好地提高程序并行化的效率。

关键词：程序并行化； 人工智能搜索； 评估函数； 数据依赖关系

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2013）06?0001?03

0 引 言

并行性分析作为自动并行化系统的重要组成部分，它的基础是前端分析和数据依赖关系的分析。前端分析就是对读入的程序进行扫描分析；数据依赖分析的是语句及变量的之间的数据依赖关系。程序并行化就是在扫描中对程序进行初步并行性分析，然后根据数据依赖关系，判断循环并行的可能性。

文中探讨了人工智能扫描策略，并且对已有策略进行改进。为了实现大型程序中循环级并行性检测得到可靠的、精确的数据依赖关系分析，文中针对传统从数据依赖关系分析的不足研究了精确的数据依赖关系分析技术——数组数据流分析技术。

1 智能扫描分析

前端分析就是对读入的串行程序进行扫描，由于程序有很多分支，扫描时就可以分多次扫描，每次扫描的不同内容就是相当于搜索路径不同，可以通过人工智能搜索来实现。本文采用的扫描方法是iterative hill climbing method，算法思想是：

从一般的情况进行考虑，p的值是不会接近的，固应该设置一个临界值。在程序并行化智能搜索中，制定如下策略：初始阶段的搜索，控制p值使其偏大，在程序的搜索过程中向深度方向进行，目的是为尽快接近目标；当进入到一定阶段，搜索到一定程度后，应调整使p值变小，广度方向应成为搜索方向的选择，目标结点要避免错过，直至搜索成功完成。

2 数据依赖分析

建立LWT树的方法是可以实现将依赖关系精确到具体数值的，这样就为循环嵌套数组分析程序自动并行化提供了更高效的方法，同时也成为代码生成和通信优化的关键依据。

3 结 语

本文介绍的人工智能扫描方法中，针对已优化的算法进行进一步改进，在其中探讨了基于评估函数的结合深度和广度搜索的智能搜索算法，在一定程度上解决了花费时间较多、占用很大存储空间的问题。并且还探讨了优于传统数据依赖关系分析的算法——数组数据流分析算法，根据其算法流程图就终写树和写写树进行了实例分析。这两方面技术的改进能够很好的提高程序并行化的效率。

参考文献

[1] 王姗姗，赵荣彩，张平.对SUIF中依赖关系分析技术的研究与改进[J].计算机工程，2006，32（7）：89?91.

[2] Stanford Compiler Group. SUIF compiler system [M]. Versionl.0. US： Standford University， 1994.

[3] DONG Chun?li， ZHAO Rong?cai. An improving computation and data decomposition [C]// Proceedings of DCABES. [S.l.]： DCABES， 2006： 111?116.

[4] 张平.并行化编译器中并行程序自动生成和性能优化技术研究[D].郑州：信息工程大学，2006.

[5] 龚雪容，生拥宏，沈亚楠.串行程序并行化中计算代码与同步通信代码的自动生成[J].计算机应用与软件，2008（1）：91?92.

[6] 沈志宇.并行编译方法[M].北京：国防工业出版社，2000.

[7] 张磊，王广生.运动模糊图像重构的算法及其并行化处理研究[J].现代电子技术，2008，31（10）：145?147.