基于切比雪夫距离的支撑点选择算法的并行优化研究

Research of Parallel Optimization of Pivot Selection Algorithm Based on Chebyshev Distance

求解切比雪夫距离的支撑点选择算法中,由于计算量较大,如何快速判断支撑点的优劣是一个难以解决的问题,为此,提出一套以切比雪夫距离为目标函数的快速支撑点优选策略。通过并行化分析找出相对独立的计算任务,使用OpenMP对支撑点的选择并行化处理;为降低算法层面的时间复杂度,将切比雪夫距离转化为曼哈顿距离,减少了总体计算量;采用多线程的方法对目标函数值的排序环节进行总体重构,避免了无意义的访存开销。实验结果表明,相比传统方法,支撑点优选算法具有较为明显的加速效果,加速比达到了174.62,并解决了算法的数据依赖问题。

In the pivot selection algorithm for solving Chebyshev distance,how to quickly determine the strength and weakness of pivot has always been a difficult problem to solve due to the large amount of calculation.Therefore,a set of fast pivot optimization strategy with Chebyshev distance as the objective function was proposed.Through parallelized analysis,relatively independent computing tasks were found,and OpenMP was used to parallelize the selection of pivot.In order to reduce the time complexity at the algorithm level,the Chebyshev distance was converted into the Manhattan distance,which reduces the overall calculation amount.The multi-threaded method was used to reconstruct the ordering link of the objective function value as a whole,which avoids the meaningless memory fetching overhead.The experimental results show that the pivot optimization algorithm is a more obvious acceleration effect than the traditional method,and the speedup reaches 174.62,and the data dependence problem of the algorithm is solved.