Page 276 - 《软件学报》2025年第8期

何贤浩 等: 面向天河新一代超算的大规模平行城市交通仿真 3699

考虑路网的划分方案. 具体而言, 在交通仿真过程中, N 个交叉口的坐标为 J i (x i ,y i ) (i = 1,2,...,N), 交叉口作为道路
,
之间车辆数据交互的节点, 可将交叉口 J i 作为图顶点 , 道路作为边, 从而将路网转化为图结构 G(V,A) V 表示顶
v i
点集合, A 表示邻接矩阵, 如果 A[i, j] = 1, 则表示图中顶点 v i 和 v j 有边相互连接.
S = {G 1 ,G 2 ,...,G n }, 需要考虑以下两个问题: (1) 每个子图的车辆数据通信开销尽
将路网 G 被划分成 n 个子图
可能小; (2) 每个子图的计算负载尽可能均衡. 假设 C(G i ) 表示子图 G i 的计算负载, T(G i ,G j ) 表示子图 G i 和 G j 的通
信开销, 每个顶点要传输的车辆数据量相同, 因此路网划分的优化目标为:

n { }
n ∑∑

S 1 = argmin T(G i ,G j )+ |V i |− |V| (2)

n
{G 1 ,G 2 ,...,G n }
i=1 j=1

其中, 第 1 项表示子图之间的通信开销, 第 2 项 |V i |− |V| 为 ϵ-Balancing 的定义, 用于表示计算的负载.
n
对于优化计算负载, 尝试尽可能保证 n 个子图 {G 1 ,G 2 ,...,G n } 的顶点数相同, 由于天河超算平台的每个节点的
体系结构相同 (多核 CPU+DSP), 这样每个子图 G i 在超算节点的负载基本相同. 而对于通信开销的优化, 需要从图
内通信和图间通信两部分考虑, 即:

( ) ( ) ( )
T G i ,G j = T in (G i )+T in G j +T out G i ,G j (3)
( ) ( )
其中, T in (G i ) 和 T in G j 表示 G i 和 G j 内部交叉口之间车辆数据的通信开销, 而 T out G i ,G j 表示车辆数据在 G i 和 G j
之间进行通信的开销. 为了最小化 T in (G i ), 可以在划分阶段使 G i 为一个连通图, 这样 G i 内部交叉口之间车辆数据
( )
交互不需要跨网络通信, 极大减少通信开销, T out G i ,G j 的通信开销取决于 G i 和 G j 之间的连接拓扑结构, 即 G i 和
G j 连接的边数越少, G i 和 G j 需要通信的开销越少. 因此, 根据定义 4 的划分代价, 优化目标 S 1 可以转化为:

n { }
n ∑∑
( ) |V|

S 2 = argmin cut G i ,G j +|V i |−
n
{G 1 ,G 2 ,...,G n }
i=1 j=1
n { }
n ∑∑ ∑

= argmin A[p,q]+ |V i |− |V| (4)
n
{G 1 ,G 2 ,...,G n }
i=1 j=1 v p ∈G i
v q ∈G j
∑
公式 (4) 的 A[p,q] 表示 G i 和 G j 的连接数. 现有的主流图划分算法能较好地实现划分策略, 但这些
v p ∈G i ,v q ∈G j
算法并未考虑路网 G 中每个顶点的地理位置. 目前, 城市大部分的道路采用“网格”结构连接, 如图 4(a) 所示, 这种
“网格”结构可定义为一个路网最小区域.

最小割
(x max , y max )
v p v q … …
… …
… … … … … …
源点 … … 汇点
… …
v i v r
(x min , y min ) m×n
(a) 路网最小区域 (b) 基于路网的最小割划分
图 4 路网划分基本策略

[
]
[
]
]
[
定义 6. 路网最小区域. 对于“网格”结构的 , A i, p = A p,q = A q,r = A[r,i] = 1, 且
G ∀v i ∈ V, ∃v p ,v q ,v r , 使得
x i ≈ x p , x r ≈ x q ,y i ≈ y r ,y p ≈ y q .
路网 G 可视为多个路网最小区域组成的结构, 因此可以采用“水平”或“竖直”的边切分方式, 将 G 划分为不同
子图.
定 理 1 . 由 多 个 路 网 最 小 区 域 组 成 的 路 网 G , 采 用 “水 平 ”或 “竖 直 ”的 边 切 分 方 式 划 分 为 G 1 , G 2 , 则

∑
A[p,q] 最小.
v p ∈G 1 ,v q ∈G 2