-
题名串行算法并行化处理的数学模型与算法描述
被引量:3
- 1
-
-
作者
吴越
-
机构
河海大学理学院
-
出处
《计算机技术与发展》
2012年第5期14-18,共5页
-
文摘
并行计算是指同时使用多种计算资源解决计算问题的过程,节省了大量计算时间,极大地提高计算效率。目前各领域大量的串行程序已经相当成熟,所以如何通过一种转换,将现有大量的串行程序转化成并行程序,是提高程序运行速度的突破口。为了将串行程序并行化,以提高程序的运行效率,充分利用已经非常成熟的大量串行程序,文中从图论出发,建立并讨论了串行算法并行化的三个数学模型:有向带权图模型、集合划分模型、标记AVL树模型。通过这些数学模型,基于图论的思想方法,文中讨论了串行算法并行化的可行性,并提出了串行程序并行化的算法思想。
-
关键词
带权有向图
AVL树
并行化
串行程序
-
Keywords
directed weighted graph
AVL tree
parallelizing
serial program
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名针对子程序结构的线程级推测并行性分析
被引量:6
- 2
-
-
作者
梁博
安虹
王莉
王耀彬
-
机构
中国科学技术大学计算机科学与技术系
中国科学院计算技术研究所计算机系统结构重点实验室
-
出处
《小型微型计算机系统》
CSCD
北大核心
2009年第2期230-235,共6页
-
基金
教育部-英特尔信息技术专项科研基金项目(MOE-INTEL-08-07)资助
国家自然科学基金重点项目(60633040)资助
+1 种基金
国家“九七三”计划项目(2005CB321601)资助
国家“八六三”计划重大项目(2006AA01A102)资助
-
文摘
线程级推测技术为开发更多的线程级并行性,充分利用多核加速传统上难以手工或自动并行化的串行程序提供可行的技术途径.然而,这种技术的性能严重地依赖于线程划分方案.有研究表明,仅推测执行循环所产生的并行性是不够的,但推测执行子程序结构比循环结构要难.本文提出寻找适于推测并行执行的子程序结构的基本判定依据;通过运行由Simplescalar工具集改造得到的动态剖析工具ProRV、ProFun和SPEC CPU2000基准测试程序,我们对子程序结构线程化推测执行的适合性进行详细分析,给出具有指导意义的实验分析方法和实验数据.我们发现:1无返回值的子程序结构占据程序整体执行时间的大约40%;返回稀疏整型的子程序结构占据了程序整体执行时间的大约10%,对其返回值的预测成功率在70%左右.对于其他返回值类型的子程序结构,由于对其返回值的预测成功率过低,我们认为不适合作为线程划分的对象.2简单的last-value的值预测方案对于返回值的预测是简单而且足够有效的.3访存数据依赖普遍存在于子程序与其后继代码之间,显式同步机制对于针对子程序结构的线程级推测是必要的.
-
关键词
线程级推测
串行程序自动并行化
子程序结构
动态剖析
数据依赖分析
-
Keywords
thread-level speculation
automatically parallel of serial application
subroutine
dynamic profiling
data dependence analysis
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名串行程序的任务DAG图构造算法
- 3
-
-
作者
孙立斌
邓蓉
陈闳中
-
机构
同济大学计算科学与技术系
同济大学嵌入式系统与服务计算教育部重点实验室
-
出处
《计算机系统应用》
2012年第9期119-123,共5页
-
文摘
任务DAG图是刻画程序中各任务间依赖关系的一种手段,DAG图上除了标有任务间的依赖关系,还记录了各任务的计算量和任务之间的通信量,这些信息共同构成了任务调度的依据,国内外有许多基于任务DAG图的调度算法研究,但通过分析串行程序的相关性来构造任务DAG图的研究却不多见.分析了串行程序中存在的数据相关性和控制相关性,就程序中的顺序,分支,循环三种基本结构进行分别讨论,提出了一种串行程序任务DAG图的构造算法.
-
关键词
串行程序并行化
DAG图
数据相关性
控制相关性
资源相关性
-
Keywords
parallelization of serial programs
directed acyclic graph
data dependency
control dependency
resourcesdependency
-
分类号
TP311.11
[自动化与计算机技术—计算机软件与理论]
-