论文标题
跨硬件解决方案范围内的蚂蚁菌落优化加速供应链
Accelerating supply chains with Ant Colony Optimization across range of hardware solutions
论文作者
论文摘要
蚂蚁菌落算法已应用于各种优化问题，但是以前的大多数缩放和并行性都集中在旅行推销员问题（TSP）上。尽管对于基准和新想法比较有用，但算法动力学并不总是转移到复杂的现实生活中的问题，在解决方案构造过程中需要额外的元数据。本文使用两个平行的ACO架构 - 独立的蚂蚁菌落（IAC）和平行的蚂蚁（PA）来研究使用蚂蚁菌落优化（ACO）及其缩放动力学的现实出站供应链问题。结果表明，随着平行实例数量的增加，PA能够在更少的迭代中达到更高的溶液质量。此外，在三种不同的硬件解决方案中测量了速度性能-16个核心CPU，68 Core Xeon Phi和高达4 GEFORCE GPU。使用C ++和CUDA实施了最新的ACO矢量化技术，例如SS-Roulette。尽管非常适合TSP，但得出的结论是，对于给定的供应链问题，GPU不适合元数据访问足迹。此外，与它们的顺序对应物相比，矢量化的CPU AVX2实现在CPU上达到了25.4倍的速度，而Xeon Phi的AVX512指令集在PA上以vectorized（PAWV）达到148倍。因此，PAWV能够在解决的供应链网络问题上至少可以扩展至少1024个并行实例。
Ant Colony algorithm has been applied to various optimization problems, however most of the previous work on scaling and parallelism focuses on Travelling Salesman Problems (TSPs). Although, useful for benchmarks and new idea comparison, the algorithmic dynamics does not always transfer to complex real-life problems, where additional meta-data is required during solution construction. This paper looks at real-life outbound supply chain problem using Ant Colony Optimization (ACO) and its scaling dynamics with two parallel ACO architectures - Independent Ant Colonies (IAC) and Parallel Ants (PA). Results showed that PA was able to reach a higher solution quality in fewer iterations as the number of parallel instances increased. Furthermore, speed performance was measured across three different hardware solutions - 16 core CPU, 68 core Xeon Phi and up to 4 Geforce GPUs. State of the art, ACO vectorization techniques such as SS-Roulette were implemented using C++ and CUDA. Although excellent for TSP, it was concluded that for the given supply chain problem GPUs are not suitable due to meta-data access footprint required. Furthermore, compared to their sequential counterpart, vectorized CPU AVX2 implementation achieved 25.4x speedup on CPU while Xeon Phi with its AVX512 instruction set reached 148x on PA with Vectorized (PAwV). PAwV is therefore able to scale at least up to 1024 parallel instances on the supply chain network problem solved.
