Parallel variable-resolution bathymetric estimation with static load balancing

作     者：Calder, B. R. 

作者机构：Univ New Hampshire Ctr Coastal & Ocean Mapping Durham NH 03824 USA Univ New Hampshire NOAA Joint Hydrog Ctr Durham NH 03824 USA 

出 版 物：《COMPUTERS & GEOSCIENCES》 (计算机与地学)

年 卷 期：2019年第123卷第Feb.期

页      面：73-82页

核心收录：

学科分类：08[工学] 0708[理学-地球物理学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NOAA [NA10NOS4000073  NA15NOS4000200] 

主　　题：Parallel processing CHRT CUBE Data-driven estimation Branch and bound Bathymetric data processing Surface estimation 

摘      要：A method for partitioning a large computation task (direct, variable resolution bathymetric grid construction from raw observations) into thread-parallel code is described. Based on the data density estimated for the first pass of the CHRT algorithm, this algorithm statically partitions the estimation task into spatially distinct blocks of approximately equal total data observation count so that each can be executed in parallel and be expected to complete approximately concurrently. No communication between blocks or further load balancing is therefore required. A branch-and-bound algorithm is used to control the complexity of the partitioning task, but the computation time increases significantly as more partitions are required, leading to a degree of diminishing returns for allocating further computational resources and suggesting alternative approaches for high thread count systems. Speed-up of the algorithm over a pair of test datasets (using real-world hydrographic survey data) shows that the performance consistently improves with the number of computational tasks assigned, initially (super-) linearly, although ultimately sub-linearly as other resource sharing limitations take over. An overall speedup of 4.1 times is demonstrated with a quad-core single-processor workstation.