CPC2020初赛赛题公布

各参赛队，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.