求循环体相关图关键路径的算法

应用循环体相关图分析循环程序的并行性对于发掘程序的并行性有重要意义,求循环体相关图的关键路径则是作这一分析的关键步骤．由于求循环体相关图的关键路径不同于求一般ＡＯＥ网的关键路径,无法直接使用已有的有关算法．为此,本文给出了一个求循环相关图的关键路径的算法,并讨论了其应用价值．     

程序设计中的循环机制

在计算机程序设计中,较为复杂的算法程序都要使用循环结构。本文分析了循环结构中循环体的共有特性,探讨了循环结构的分析与设计。     

异构计算开发最大循环并行性

首先给出了循环最大加速比的定义,它是循环体中隐含并行性大小的度量,并且讨论Do循环的各种类型和它们的相关性以及隐含的并行性．在异构环境中,如何开发这些并行性,文中给出了几种方法,这就是异构计算消除串行瓶颈,异构Do-all-loop调度,异构Do-aross调度．无论在理论分析还是在实验结果上,这些方法所得得的计算性能都优于同构计算．     

并发程序内部表示及静态切片算法的改进

通过分析Krinke切片算法对程序循环体内嵌套一个或多个线程结构会产生切片不精确现象,得出Krinke算法所基于的程序依赖图对线程间数据的依赖关系定义得过于粗糙,且对并发程序执行行为的合法性约束不够严格的结果.据此,提出一种新的并发程序依赖图,引入跨线程边界循环-承载数据依赖关系,并在此数据结构上改进了切片算法;引入区域化执行证据概念,进一步约束程序执行行为的合法性,并给出了添加跨线程边界循环-承载数据依赖关系的算法及新的并发程序切片算法的伪代码.实例分析与算法性能测试表明,改进的切片算法克服了Krinke算法的不精确现象,降低了时间开销,改善了算法的可伸缩性.     

基于优先级的单元测试技术应用研究

考虑到单元测试的并行性,提出了基于函数优先级的测试策略.分析了函数的参数、全局变量和局部变量对函数控制流正确实现的影响,建立了量化的权值影响因子数学模型,并结合函数的控制流图生成了带权值有向无环图,最后根据AOE-网关键路径求解算法,生成被测函数的关键路径,设计测试用例.测试结束之后,再进行次关键路径选择,直至达到测试标准.通过以上技术,合理分配各模块测试计划时间,有助于提高软件测试效率,保证软件质量.     

LINGO在关键路径规划求解中的应用

文章首先介绍了关键路径的相关概念,然后给出了求关键路径的算法,最后使用L INGO软件求解工程规划中经常使用的关键路径规划实例,结果显示：使用该方法求解模型简便,能大大提高优化求解关键路径的效率.     

AOE网在关系数据库中的表示及关键路径算法的实现

提出一种在关系数据库中表示AOE网的方法 ,利用数据库记录与数组内容的传递功能 ,避免了使用拓扑排序求关键路径的复杂处理 ,从而获得求关键路径的简单算法     

数据相关性分析的非精确算法

提出了一种行之有效的数据相关性分析的非精确算法．对该算法在运行效率及可行性上进行了详细分析，并在数据相关性分析非精确算法讨论的基础上，提出了一种对相邻循环进行并行性开发的一种新的程序转换技术，从而解决了相邻循环程序之间可并行执行程序段的转换问题．在多CPU高性能计算机的硬件环境下，为设计出高效率的、适合于并行处理环境的软件系统提供了一种有效的算法．     

基于循环展开的子字并行指令自动生成

针对向量编译的不足,提出一种基于循环展开的子字并行指令自动生成的方法.该方法利用传统的循环变换技术对多媒体应用中可以进行子字并行的循环进行优化,生成子字并行代码.首先识别出可并行的循环,然后通过循环展开、寄存器重命名、指令合并等技术来提升循环体基本块中的子字并行性.在TTA(transport triggered architecture)体系结构的编译框架下用该方法实现了子字并行指令的自动生成.实验表明该方法得到了较好的加速比.     

二维非线性对流扩散方程求解程序优化

在IA-64架构Itanium2处理器上,应用gprof和pfmon对二维非线性对流扩散方程求解程序源代码进行了性能测试.在分析给定程序的数据结构,子过程调用关系,重点子程序中循环体的迭代空间、数据空间、访问轨迹,输入输出数据量大小和程序结构等的基础上,应用子过程合并、循环变换、分支消除、循环顺序逆转、数组一维结构化为二维结构、输入参数给定等方法,改善了数据访问的时空局部性,程序性能有15%的提高.     

基于数据结构的关键路径算法

数据结构是计算机学科的算法理论基础和软件设计的技术基础,在计算机领域中有着举足轻重的作用。利用邻接矩阵表的存储结构,实现了在计算机上求关键路径的算法,并分析了所设计算法的时间复杂度。     

关键路径概念的延伸

描述了广义关键路径问题,提出了广义关键路径概念,给出了广义关键路径的算法,结合实例,对所给的概念和算法的实际应用作了讨论,本算法可直接用于解决规模较小,但皎为复杂的关键路径问题。     

基于Petri网分析循环语句的并行性

利用Petri网可以处理并发事件和进行并行处理的优点，结合Petri网的相关理论．对单重循环语句及多重循环语句用Petri网进行表述，通过Petri网的描述更利于分析循环语句的并行性．对单重循环的先赋值后引用和先引用后赋值的并行性的特点进行详细的分析．     

几种求关键路径算法的分析

分别从算法的时间复杂度、空间复杂度、数据结构形式以及实现的难易程度等方面分析了几种求关键路径算法的优劣．表明三种算法的时间复杂度分别为：O（n＋e）,O（n^2）,O（n＋e^2／n）．     

一类随机性EOQ模型的关键路径存贮策略

针对已有存贮策略不能直接适用于库存决策模型的问题,提出了一种基于关键路径的存贮策略,实现了一类随机性经济订货批量公式(EOQ模型)的关键路径求解.通过有限状态机构建算法(BFA),建立了适用于图论的有限状态机的资金有限型随机性EOQ模型,解决了原随机性EOQ模型不能直接应用于图论策略的问题.基于该有限状态机进一步提出了基于统筹法(PERT)的生成算法(BPA),其可将有限状态机转换为PERT图,以符合关键路径求解需求,由此可利用关键路径存贮策略来求解EOQ类模型.通过实例验证表明,所提策略能够较好地求解资金有限型随机性EOQ模型,并保证结果的完整性,同时证明了相关算法的理论性.     

顺序程序任务并行性的识别

探讨了任务并行性识别中任务执行条件的导出，利用任务结点间的相关性（包括数据相关和控制相关）就可求出并行执行条件，提出了层次任务图模型下直接生成优化任务执行条件的算法，省去了后控树及控制相关图（ＣＤＧ）的产生，其过程简单具比较高效。     

基于蚁群算法的故障识别

提出了一种新的基于蚁群算法的故障诊断知识获取算法。该算法将故障诊断中故障的识别分类问题转化为求解带约束的最优化聚类问题,并应用改进的蚁群算法,基于群体的协作与学习求解这一聚类问题。将该方法应用于一化学反应器的故障诊断过程,结果表明该算法具有实现简单、收敛速度快、本质分布式并行性、鲁棒性强以及故障识别结果可靠等优点。     

循环阵求逆的一种算法

提出了循环阵求的逆的一种算法，当循环阵非奇时，该算法求循环阵的逆，循环阵奇异时，该算法求循环阵的广义逆。     

基于DNA自组装模型解决图的最小顶点覆盖问题

在分析最小顶点覆盖问题特点的基础上,以5个顶点的图为例,将最小顶点覆盖问题转化为可满足性问题,简化问题的操作难度。再根据DNA自组装的自发性和并行性等优势,通过建立DNA自组装模型解决可满足性问题,从而解决图的最小顶点覆盖问题。相对于传统算法,本算法只应用了凝胶电泳技术,大大的降低了操作难度和误差。     

顺序程序任务并行性的识别

探讨了任务并行性识别中任务执行条件的导出，利用任务给点间的相关性（包括数据相关和控制相关）就可求出并行执行条件．提出了层次任务图模型下直接生成优化任务执行条件的算法，省去了后控树及控制相关图（ＣＤＧ）的产生，其过程简单且比较高效．