Predictive Evaluation of Partitioning Algorithms through Runtime Modelling
Predictive Evaluation of Partitioning Algorithms through Runtime Modelling
复制标题
通过运行时建模对分区算法进行预测评估
DOI：
10.1109/hipc.2016.048
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Matthew J. Street
中科院分区：
文献类型：
--
作者：
Richard A. Bunt;Steven A. Wright;S. Jarvis;Y. Ho;Matthew J. Street
非结构化网格代码的性能建模是一个具有挑战性的过程，因为很难捕捉它们的内存访问模式，以及它们在不同规模下的通信模式。在本文中，我们首先开发扩展现有的运行时性能模型，旨在克服前者，我们验证了高达1,024个核心的Haswell为基础的集群，使用几何分区算法和ParMETIS划分输入甲板，与最大绝对运行时误差分别为12.63%和11.55%。为了克服后者，我们开发了一个应用程序的代表网格划分过程内部的非结构化meshcode。这个应用程序能够生成分区数据，这些数据可用于性能模型，以产生预测的应用程序运行时间，其范围为使用经验收集的数据产生的运行时间的7.31%。然后，我们通过在多达30，000个核心上对几种分区算法进行预测比较来演示性能模型的使用。此外，我们正确地预测了几何划分算法在512和1024核上的无效性。
Performance modelling unstructured mesh codesis a challenging process, due to the difficulty of capturing theirmemory access patterns, and their communication patterns atvarying scale. In this paper we first develop extensions to anexisting runtime performance model, aimed at overcoming theformer, which we validate on up to 1,024 cores of a Haswell-based cluster, using both a geometric partitioning algorithmand ParMETIS to partition the input deck, with a maximumabsolute runtime error of 12.63% and 11.55% respectively. Toovercome the latter, we develop an application representative ofthe mesh partitioning process internal to an unstructured meshcode. This application is able to generate partitioning data thatis usable with the performance model to produce predictedapplication runtimes within 7.31% of those produced usingempirically collected data. We then demonstrate the use of theperformance model by undertaking a predictive comparisonamong several partitioning algorithms on up to 30,000 cores. Additionally, we correctly predict the ineffectiveness of thegeometric partitioning algorithm at 512 and 1024 cores.