应用蚁群优化算法 (ACO) 实施交通网络扩展

本文对基于 OpenMP* 的蚁群优化算法的实施进行了分析,以便了解英特尔® VTune™ Amplifier XE 2016 的瓶颈,以及使用混合 MPI-OpenMP 实现的改进。此外,本文还介绍了如何使用英特尔® 线程构建模块,来提高基于四路英特尔® 至强® E7-8890 v4 处理器系统的扩展效率。

目录

简介

交通网络的目标通常是,使用最有效的方法把货物从一个地方移动到另一个地方。 过去的几十年中,“方法”的定义不仅仅限于资金成本,还包括如环境影响、能源消耗和时间花费等因素。 随着商业及供应链的全球化发展,此类交通网络的规模和复杂性显著扩大。 因此,优化交通网络问题成为 NP 难题,通常不适用于确定性解决方案。

随着多核分布式架构的普及,基于启发法的优化技术不断得到发展和应用,如蚁群优化算法 (ACO)。 本文分析了 ACO 实施的基准及瓶颈,介绍了我们部署的进一步改进,在基于四路英特尔® 至强® 处理器的系统上实现理论上的扩展。 本文的组织结构如下:

  • ACO 算法的背景
  • 性能指标评测结果的基准实施和 VTune™ Amplifier 分析
  • 优化方案 1: 采用带有 英特尔VTune Amplifier的混合 MPI-OpenMP*
  • 优化方案 2: 采用英特尔® 线程构建模块(英特尔® TBB) - 动态内存分配
  • 优化方案 3: MPI 等级和 OpenMP 线程的结合/平衡
  • 总结

背景: ACO 算法

蚂蚁寻找食物的时候,他们走过的地方会留下信息素,从而吸引更多的蚂蚁。 信息素会蒸发,因此长路线较短路线或者近的路线更容易降解,更多的蚂蚁会涌向短路线或者近的路线;留下更多的信息素,进一步增加吸引性。  

Figure_1_Transportation_Network_Optimization

图 1: 交通网络示例。1

网络内简单的计算机代理可以利用 ACO 算法构建解决方案。 过去,ACO 算法在以下并行软件中应用,但是受到一定限制。

  • M. Rosenblum 等。 (Randall 和 Lewis, 2002) 开发了一款简单的 ACO 算法的并行版本,实现较大的加速,但是这产生了大量的通信,以维持信息素矩阵。 当在多个蚂蚁中运行紧密的并行操作时,蚂蚁之间的消息传递接口 (MPI) 通信会使性能受到限制。
  • Melsheimer M.等。 (Veluscek, 2015) 基于 OpenMP 的共享内存并行性,采用了复合目标方法,实现了交通网络优化算法。但是,最好使用内核和线程数量较少的系统。

ACO 的基准实施

基础性 ACO 软件的整体并行结构如图 2 中的流程图所示。

ACO_Baseline_Flowchart

图 2: 未优化的基础流程图。

每个月,大量的迭代被运行,释放全部蚂蚁,构建信息素矩阵,以完成解决方案。 每一个迭代的运行完全独立于其他迭代。

每个 OpenMP 线程并行运行各自的迭代,寻找线程局部解决方案时,采用的是静态工作分布。 所有线程完成各自搜索之后,主线程对所有线程局部解决方案进行比较,选出全局解决方案。

性能指标评测结果 - 基准实施

先在单插槽、NUMA 节点运行应用,然后在多插槽运行,分别采用超线程技术和不使用超线程技术,对比两者的性能差别,这是最快检测应用是否有效扩展,内核持续增加的方法之一。 在理想情形中,双路系统的性能是单路系统的两倍,四路系统的性能是单路系统的四倍(排除其它因素的影响)。 然而,图 3 的基准测试显示,当超过双路系统(48 核)时,应用的扩展性并不理想,更何况 192 核的。

Fig3_Preoptimized_Baseline_Scaling_Results

图 3: Pre-optimized baseline scaling results.

VTune Amplifier XE 分析-基准实施

如图 4 .[1] 所示,为了找到扩展问题,我们利用 英特尔VTune Amplifier XE 2016的热点功能。英特尔VTune Amplifier 的 summary 窗口显示重要热点,以及串行执行网络优化应用所花费的串行时间。

Figure_4_Pre-optimized baseline – Top Hotspots

图 4: 未优化的基准 - 重要热点。

由图 4 可以得出,应用串行执行的时间过长,会直接影响并行 CPU 利用率。 标准化字符库中的字符串分配程序是最大的热点,其在内核数量增加时的扩展性不佳。 由于 OpenMP 使用单个内存共享池,大量并行线程调用字符串构建程序或对象分配程序(采用 operatornew),内存会产生瓶颈。 如果我们在自下而上选项卡中查看 CPU 使用率(图 5),会发现应用使用全部 96 个内核,但是时间很短。

 

Figure_5_Pre-optimized baseline – CPU utilization

图 5: 未优化的基准 - CPU 使用率。

Figure_6_Pre-optimized baseline – Load imbalance

图 6: 未优化的基准 - 负载不平衡。

将算法映射到时间线上,负载不平衡表(图 6)显示,每月月底有一段时间,主线程进行有用计算,其它线程在执行自转或休眠。

优化方案 1: 添加混合 MPI-OpenMP 

为了避免基础性实施方法出现大量的 OpenMP 线程池,我们采用通用主从方法,迭代时启动多个进程[2]。 每一个进程(MPI 等级)会衍生出相对少数的 OpenMP 线程。 字符串过载和对象分配现在是通过多种 MPI 进程(等级)分配。 ACO 软件的混合 MPI-OpenMP 实施如图 7 中的流程图所示。

Optimized_MPI_Implementation_Flowchart

图 7: 优化实施#1 -流程图。

优化方案 1 的 英特尔VTune Amplifier XE 分析

我们利用 英特尔VTune Amplifier 热点特性,分析了混合 MPI-OpenMP 的实施。

summary 窗口(图 8)显示,应用字符串分配的时间相对减少,CPU 使用率提高了(图 9a 和 9b)。

Figure_8_Optimization 1 implementation – Top Hotspots

图 8: 优化方案 1 的实施 - 重要热点

 

Figure_9_Pre-optimized_baseline implementation – CPU usage histogram

图 9: 优化前基准 和优化 # 1 实施 – CPU 使用率柱状图

 

Figure_10_Optimization #1 implementation – elapsed time line

图 10: 优化 #1实施 – 消耗时间线。

图 10 显示主线程和工作线程产生的负载不平衡显著下降。 图 11 显示时间表上的 CPU 使用率接近 96 个内核。

Figure_11_Optimization #1 implementation – CPU utilization

图 11: 优化方案 1 的实施-重要热点。

获胜的等级(制定全球解决方案的等级)把解决方案发送到主等级,对结果文件进行更新。在这一过程中,OpenMP 线程自转和 MPI 通信的时间过长。 我们把原因归结为 MPI 通信开销过高。 MPI 采用分布式内存界面,每一个进程(等级)在独立的内存池内运行。 因此,一个等级的对象和数据结构的修改无法在其它等级显示,数据必须通过 MPI Send and Receive 在不同等级中共享。必须把每月一期的全局解决方案发送到主线程。[3] 全局解决方案作为复杂的 C++ 对象,包含许多衍生的类对象,存储数据的智能指示器和其他 STL 模板对象。 默认状态下,MPI 通信不能交换复杂的 C++ 对象。需要对 MPI Send and Receive 串行化,把 C++ 对象转换成数据流才能发送,接收时进行反串行,把数据流转换成对象。 图 11 用黄色(MPI 通信)和红色(自转和开销)显示开销。

优化方案 1 的结果

混合 MPI-OpenMP 版本在 MPI 等级和 OpenMP 线程之间产生更好的负载平衡性,提高了多核英特尔® 至强® 处理器 E7-8890 v4系统的使用率。 图 12 显示它能在包括超线程、多插槽(内核)环境中显著提高扩展性。

Figure12_Optimization 2 – scaling comparison

图 12: 优化方案 2 - 扩展比较。

优化方案 2: 使用英特尔® 线程构建模块动态内存分配

观察混合 MPI-OpenMP 运行时产生的重要热点,我们可以得知标准字符串分配程序库花费了很多执行时间。 我们很想知道,英特尔 TBB 动态内存分配程序库是否会受益。 英特尔 TBB 的内存分配程序模板和标准模板库 (STL) 的模板类 std::allocator 相似,包括 scalable_allocator<T> 和 cache_aligned_allocator<T>。 揭示了并行编程中的两个重大问题:

可扩展性问题产生的原因是内存分配程序有时需要争夺单个共享池,导致每次只能分配一个线程(源自原始串行程序设计问题)。

两个线程在同一个高速缓存行中访问不同的命令会造成伪共享问题。 处理器高速缓存之间交换信息的最小单位是高速缓存行,即使行内每一个处理器处理不同的命令,高速缓存行可以在多个处理器间运行。 因为传输高速缓存行需要数百小时,伪共享会降低性能。

使用英特尔线程构建模块动态内存分配的步骤

用英特尔 TBB 代理库 - libtbbmalloc_proxy.so.2.的正式版代替标准化动态内存分配功能,可以快速检测应用能否从英特尔 TBB 动态内存分配中受益。 在程序加载时使用 LD_PRELOAD 环境变量加载代理库(不要改变可执行文件),或者把主要可执行文件连接到代理库。

连接到 TBB malloc 代理库: -ltbbmalloc_proxy
OR
Set LD_PRELOAD environment variable to load the Intel® TBB malloc proxy library
       $ export LD_PRELOAD=libtbbmalloc_proxy.so.2

 

优化方案 2 的结果

默认内存分配程序的可扩展特性出现严重问题时,英特尔 TBB 动态内存分配代理库向优化的纵向扩展混合 MPI-OpenMP 版本提供额外的 6% 的份额(图 13)。

 

Figure_13_Scale-up implementation – Intel® Threading Building Blocks improvements

图 13:纵向扩展实施 – 改进英特尔® 线程构建模块

优化方案 3: MPI 等级和 OpenMP 线程的结合

最后,通过尝试把运行同一工作负载的 MPI 等级和 OpenMP 线程进行组合,实现进一步优化。 在开启超级线程的情况下,我们运行工作负载的同时实现总体系统利用率最大化,即 192 个逻辑内核全部投入使用。   当我们把 64 个 MPI 等级组合在一起,每个等级运行 3 个 OpenMP 线程时,达到的最大吞吐率如图 14 所示。

Figure_14_Optimization 3– comparison of rank and thread count combinations

图 14: 优化方案 3 - 等级和线程数组合的比较。

总结

ACO 网络管理的基准并行软件实施采用字符串分配程序和对象构建程序,展示了线程扩展问题。 优化方案 1 提高了 CPU 使用率,但是字符串分配程序所消耗的执行时间仍旧很高。 在优化方案 2 中,英特尔 TBB 动态内存分配代理库向混合 MPI-OpenMP 版本提供额外的 6% 的份额。 优化方案 3 使用 64 个 MPI 等级,每个等级使用 3 个 OpenMP 线程,实现了多达 192 核的额外的真扩展性,最终的性能提升至 5.3 倍,证明 英特尔VTune Amplifier 和英特尔 TBB 花费的时间是非常值得的。

 

Figure_15_Overall performance comparison

图 15: 整体性能对比。

附录 A: 系统配置

本文图表中提供的性能测试结果基于以下测试系统。 如欲了解更多信息,请访问:http://www.intel.com/performance

系统

四路服务器

主机处理器

英特尔® 至强® 处理器 E5-2699 V4 @ 2.20 GHz

内核、线程

96/192

主机内存

512 GB DDR-1600 MHz

编译器

英特尔® Parallel Studio XE 2016 U2

分析器

英特尔VTune Amplifier XE 2016 Update 2

主机操作系统

Linux*,3.10.0-327 版本.el7.x86_64

 

附录 B: 参考资料

 

关于作者


Sunny GogarSunny Gogar软件工程师

Sunny Gogar 获得了佛罗里达大学电子与计算机工程专业的硕士学位,以及印度孟买大学电子与电信学专业的学士学位。 目前在英特尔公司软件及服务事业部担任软件工程师。 他的兴趣在于面向多核和众核处理器架构的并行编程与优化。

 

 


[1] 英特尔VTune Amplifier 通过降低工作负载(384 次迭代),控制收集取样数据的数量。 本文所显示的其他所有性能指标评测数据都是由满工作负载生成的(1000 次迭代)。

[2] MPI 进程或 MPI 等级在本文可以互换。

[3] 序列化开销是常量,即 0(1)每月达到一次最高值(或在主线程(等级 0)找到全球解决方案时跳过),与启动的 MPI 进程数量无关。 当我们在多节点间纵向扩展时,这有助于对 MPI 通信进行限制。

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.
Возможность комментирования русскоязычного контента была отключена. Узнать подробнее.