新闻 图说CPC赛事通知新网直通车 新网会客厅

CPC2020初赛赛题公布

浏览次数:3544 发布时间:2020-06-01-12:06:00

各参赛队,CPC2020初赛赛题公布如下:

参赛对象:CPC2020成功报名且收到参赛账号的队伍

初赛赛题:广度优先搜索

上机平台:神威·太湖之光

程序描述

对无向图从某个节点出发进行广度优先搜索。输入:图G,起始节点编号s;输出:数组π;π[i]表示编号为i的节点的前驱;对于起始节点π[s]=s;对于不可达的节点j,π[j]=-1。

其算法写成迭代形式后如下

代码框架

benchmark.c为主调函数,不可修改。

check.a为正确性验证程序,不可删除。

utils.c为读取数据的文件,不可修改。

graph-sequential.c为单个计算节点的串行实现,以此版本为基准进行并行,不可修改。

graph -load-balance.c为参赛者自行实现并行版本代码。

common.h仅增加部分函数声明,关键参数不可修改。


其他说明

图1:数据结构

无权图由两个整数v、e和两个32位整数数组v_pos、e_dst表示。v_pos的长度为v+1,e_dst的长度为e,其中v_pos[0]=0,v_pos[v]=e,从e_dst[v_pos[i]]到e_dst[v_pos[i+1]](不含)的元素表示与第i个节点相连的节点编号。

图2:分布式数据结构

在多进程程序中,节点数据的分布式存储格式由local_v,offset_v表示:编号从offset_v到offset_v+local_v的节点属于该进程,这是输出数据的存储格式。边数据的存储格式有根据源节点的一维划分、和根据源节点与目标节点的二维划分等。初始状态下,节点数据为按节点数的均匀一维划分,边数据为按源节点的一维划分。

提供数据预处理接口preprocess,可以对图预处理,比如调整每个进程上节点数。经过预处理后,图数据结构就完全由自己实现了,但是local_v和offset_v和输出结果正确性有关,不能随意设置。

在测试程序中,将会重复运行bfs多次,每次运行都使用随机起始节点。为避免只遍历到一个很小规模的子图,出现这种情况时视为无效结果(trivial)。

优化建议:

程序默认的读取数据方式为按照节点划分并行读取数据,可根据自身算法实现分配每个进程的数据规模。在任务划分时,每个进程分到的节点数和边数可以不同。

对于不同的图,最佳的算法可能是不一样的,可以通过一些简单的统计数据,如边数除以节点数等,选择最佳算法。

程序说明:

源码

源码:/home/export/online1/cpc/CPC_graph.tar.gz

参赛队拷贝到自己目录下后解压缩:tar -xvzf CPC_graph.tar.gz

编译:

在CPU_graph目录下:

$ make   编译graph-sequential及graph-load-balance

$ make graph-sequential         编译graph-sequential

graph-sequential为原始可执行程序,了解程序算法及计算,不计算成绩。

$make graph-load-balance        编译graph-load-balance

graph-load-balance为参赛者优化版本,计算成绩。

计算数据说明:

目前输入文件放置在/home/export/online1/cpc/graph_data/目录下,参赛者无需拷贝,运行时添加路径即可访问。

建议先用较小的图如Freescale1进行实验,串行版本在大规模数据下会很慢,如europe_osm

运行:

运行脚本示例参见CPC_graph/run.sh

脚本包含3个参数,可执行程序、输入数据文件、进程数。

./run.sh graph-load-balance cage15 16运行并行版本cage15.csr数据文件,16进程的算例。

如需运行其他配置的算例,请对应修改提交命令行中的参数。

赛题的计时区时间为preprocess和bfs调用前后(start = MPI_Wtime(); end = MPI_Wtime(); )之间的时间。程序运行结束时会打印preprocess time和compute time,以及程序计算性能。

正确性验证说明:

验证程序check_answer在每次调用bfs后执行,在所有运行结束后输出验证结果。

竞赛内容

在原始串行代码基础上实现并优化bfs算法,获得最短的运算时间。请在规则允许范围内实现高效的MPI并行和众核并行代码,仅允许修改规定源代码文件(参考代码框架部分内容),着重提高代码并行计算效率和发挥申威CPU计算潜力,不合理的改动,修改结果验证环节等将导致成绩无效。

硬件环境及成绩提交:

  • 初赛期间,为每支参赛队提供q_sw_cpc_1或q_sw_cpc_2的国产队列,每支参赛队最多可用16个节点供比赛期间测试。

  • 评分细则

本次比赛采用四个输入数据,参赛队可使用不超过16个节点(64进程)运行代码并记录成绩。在能够通过结果验证的前提下,以获得最少运行时间为目标,参赛队应对程序并行效率进行优化,并尝试使用申威众核处理器的协处理器对计算过程进行加速,尽可能发挥众核处理器的体系结构优势。


参考文献

图算法是一个非常活跃的研究领域,本处列出一些基本参考文献。鼓励参赛队伍自行搜索更多的相关参考文献。

1.Soctt Beamer, Krste Asanovic, and David Patterson. 2013. Direction-optimizing breadth-first search. Scientific Programming 21, 3-4(2013), 137-148.

2.Maciej Besta, MichaAC Podstawski, Linus Groner, Edgar Solomonik, and Torsten Hoefler. 2017. To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations. In The International Symposium on High-p Parallel and Distributed Computing. 93-104.

3.C.E. Leiserson and T.B. Schardl. A work-efficient parallel breadth-first search algorithm (or how to cod e with the nondeterminism of reducers). In Proc. 22nd ACM Symp. On Parallism in Algorithms and Architectures (SPAA’ 10), pages 303-314, June 2010.

4.Gonzalez, Joseph E., et al. "Powergraph: Distributed graph-parallel computation on natural graphs." Presented as part of the 10th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 12). 2012.

5.Chen, Rong, et al. "Powerlyra: Differentiated graph computation and partitioning on skewed graphs." ACM Transactions on Parallel Computing (TOPC) 5.3 (2019): 1-39.


赛题及比赛平台由国家超级计算无锡中心提供。



版权所有 国产CPU并行应用挑战赛