首页 > 学院 > 开发设计 > 正文

HPC-paperweekly-01(3月)

2019-11-06 06:29:58
字体:
来源:转载
供稿:网友

Merge Path - Parallel Merging Made Simple

来源:2014 ipDPS

解决的问题

Parallel merging two sorted arrays。解决这个问题,需要从以下几个方面思考:

balancing the load among compute cores -minimizing the extra work brought about by parallelization -minimizing inter-thread synchronization -Efficient use of memory

主要创新点

提出了一种新的并行分割方式,虽然分割结果和计算复杂度和以前的并行算法相同,但是我们的分割方法是不同的,具有启发性的。在此基础上,提出了一种synchronization-free, cache-efficient merging算法(memory-efficient version)。

方法详述

抽象出了merge matrix和merge path两个辅助分割的数据结构。具体如下图所示。 merge matrix and merge path 其中,矩阵是这样构建的:若A[i] >= B[i], 则matrix[i][j] = 1, or matrix[i][j] =0; 其中,路径就是1与0的交界线(线上有一些点组成,pair(x, y)的集合)。在上一步构造出merge path后,每个线程平均分配任务,如,第i个线程从第j个元素开始处理,则每个线程的起始pair是这样获得的:x+y = j。 algo: algo example:

实验平台及主要的实验结果

它的实验结果是多线程与单线程比的。(起始单线程效果是比串行差很多的,一方面计算对角线与mergepath交点需要开销,另一方面omp开启有开销。)

n个线程,相比单线程,大约能获得n倍的加速比。

test performance

实现代码

在github上发现一份代码:mergePathOMP我需要自己写一份。
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表