BSP 与超步:同步的图并行模型
BSP(Bulk Synchronous Parallel)把图计算切成一段段「超步」:每超步内所有顶点并行计算,超步之间有一道同步屏障,屏障后消息才可见。
超步时序
flowchart LR
S0["超步 0:源点设距离 0,发消息给邻居"]
B0{"同步屏障:收齐全部消息"}
S1["超步 1:邻居比较距离并转发"]
B1{"同步屏障:收齐全部消息"}
S2["超步 2:末端收敛、投票停止"]
S0 --> B0 --> S1 --> B1 --> S2
BSP 账本
bsp 用例 16:BFS 源点距离 0。用例 17:BFS 末端距离 3,超步数 = 距离 + 1。用例 18:路径图 4 顶点 3 条边共 4 个超步(源点 + 3 层)。同步保证每超步的消息必然来自前一超步,语义简单;代价是慢者拖累快者(straggler),这是同步模型的固有取舍。
对齐卷六:exchange 屏障
卷六的 exchange 是 shuffle 前的同步点;BSP 的屏障是超步间的同步点。区别:exchange 一次任务只做一轮,BSP 把多轮同步串成迭代骨架。
验证
从卷十一实验包 解包,运行 Java 账本:bsp 用例 16-18 验证 BFS 源点距离 0、末端距离 3、路径图(4 顶点 3 边)共 4 个超步——超步数 = 距离 + 1 的同步账本。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。