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

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

本文第 1 节介绍城市交通仿真相关问题的定义. 第 2 节介绍天河新一代超算的系统架构. 第 3 节介绍面向天
河新一代超算的平行交通仿真并行算法. 第 4 节通过对比实验验证该算法在天河新一代超算进行交通仿真的有效
性. 第 5 节总结全文并展望未来工作.

1 问题定义

定义 1. 平行城市. 平行城市的核心在于构建与实际城市等价的人工城市. 平行城市使用城市大数据和物联网
感知技术, 对实际城市进行物理建模, 从而构建多尺度、多分辨率的城市运行模拟系统. 另外, 平行城市采用人工
智能和统计等方法对城市采样数据进行法分析和预测, 最终实现城市运行过程中的问题诊断和管控.
因此, 平行城市的 3 大特点为: 精准描述、智能预测和主动引导. 首先, 对于构建与实际城市等价的人工城市,
需要将城市运行中的人、环境、基础设施等要素进行“数字化”. 这涉及将城市中的各个实体和属性转化为适当的
数据结构和软件模型, 以便在虚拟环境中进行建模和仿真. 这种数字化过程包括对城市物理空间和数字空间之间
的关联关系进行建立, 以确保模拟的结果能够准确地反映实际城市的行为和特征.
其次, 平行城市可以借助机器学习、统计等模型, 根据历史城市运行数据来预测未来城市的状态, 例如未来交
通状况. 这些预测方法的应用能够为城市规划、交通管理和资源分配等领域提供有价值的信息和决策支持.
最后, 平行城市系统能够根据预测结果和当前城市状态, 主动进行引导和管控. 通过虚实结合的方式, 平行城
市系统能够在数字空间中模拟城市运行状态, 并针对不同场景和情况制定合理的规划方案. 例如, 在预测到交通拥
堵即将发生时, 平行城市可以通过智能交通信号控制系统调整信号灯配时, 优化交通流动, 减少拥堵现象. 类似地,
在突发应急事件发生时, 平行城市可以迅速响应, 调配资源和人力, 以最佳方式应对危机并最小化影响.
在基于平行城市理论进行交通仿真过程中, 根据平行城市“精准描述”的特点, 需要将现实世界的城市道路交
通网络抽象成能用计算机表示的数据结构, 因此, 本文将城市路网转化为图数据结构, 并根据分布式交通仿真任
务, 定义了路网划分.
定义 2. 城市路网. 对于城市道路网络, 可将其抽象为一个连通无向图 G(V,E,A), 其中 V = {v 1 ,v 2 ,...,v n }, n ∈ N
表示图 G 的顶点集, E = {e 1 ,e 2 ,...,e m } 表示图 G 的边集, A ∈ R n×n 为图 G 的邻接矩阵, A[i, j] = 1 表示顶点 v i 与 v j 有
E 表示道路, 因此, A[i, j] = 1 转化为交叉
一条边相连. 在实际应用中, 顶点集 V 表示为交叉口或道路的端点, 边集
j
i
i
j
口 i 和 之间有一条道路, 并且对于任意的交叉口 和 j, 存在一个路径 Path = {e a 0 ,e a 1 ,...,e a s } 使得 和 可达. 为了
简单起见, G(V,E,A) 可省略边集 , 从而表示为 G(V,A).
E
G(V,A) 表示为一个城市的道路网络, 一个集合函数: π(G,k) = {G 1 ,G 2 ,...,G k }
定义 3. 路网划分. 假设连通无向图
将路网 G(V,A) 划分为不同的子图 G i (V i ,E i ,A i ) (i = 1,2,...,k), 且 V i ⊆ V,E i ⊆ E,A i = A[V i ]. 此外, 对于任意两个子图
G i 和 G j , 有 G i ∩G j = ∅.
G j 存在多个
当路网 G(V,A) 被划分为多个子图时, 每个子图 G i 会分布到不同的计算节点, 并且 G i 与其他子图
边的“连接”, 这是因为存在于 G i 与 G j 的顶点在路网 G(V,A) 可能有边相连, 而在传输的数据量相同时, 该“连接”可
近似作为 G i 与 G j 之间的通信代价.
π(G,k) 划分为
定义 4. 划分代价. 假设连通无向图 G(V,A) 表示为一个城市的道路网络, 且被集合函数
{G 1 ,G 2 ,...,G k }, 现定义两个子图 G i 和 G j 的划分代价为:

∑
cut(G i ,G j ) = v p ∈V i A(p,q) (1)
v q ∈V j
由于路网 G(V,A) 为连通的无向图, ∀i, j, A[i, j] = A[ j,i], 因此 cut(G i ,G j ) 具有对称性, 即 cut(G i ,G j ) = cut(G j ,G i ).
G(V,A) 被划分为多个子图时, 定义 4 cut(G i ,G j ) 提供了一种评估划分通信开销的量化方法,
当路网 的划分代价
但在大规模分布式交通仿真过程中, 每个计算节点的计算负载也需要进行分析评估. 在实际应用中, 需要根据每个
计算节点的体系结构特点, 确保每个节点的负载尽可能地均衡, 在同构节点的条件下, 定义的 ϵ-Balancing 如下.
定义 5. ϵ -Balancing. 假设路网 G(V,A) 被集合函数 π(G,k) 划分为 {G 1 ,G 2 ,...,G k }, 这些划分的子图集合 {G 1 ,G 2 ,

...,G k } 是 ϵ-Balancing 的, 当且仅当 ∃ϵ ⩾ 0,∀i, |V| −|V i | ⩽ ϵ. 当 ϵ=0 时, 表示 k 个子图的计算负载是均衡的.

k