面向并行負載平衡的數據剖分技術

0 引言

并行數據剖分通過將整體問題分而治之，把計算任務剖分成若干子任務，并按一定的映射方法分配給各個處理器。其原則是盡量保持處理機任務的計算負載均衡，通信開銷最低。均衡的并行數據剖分是高效并行計算的前提。一般來說，在計算過程中無須改變的剖分稱為靜態剖分，在計算執行前可預先確定；在并行計算中需再次對數據進行剖分的通常稱為動態剖分或重剖分，如對自適應網格計算問題一般采用動態剖分方法，否則會導致嚴重的負載不平衡，影響并行性能。從算法特點上看，數據剖分大致分為幾何剖分和圖剖分兩類，其中對圖剖分方法的研究與應用較多。由于這些剖分方法在剖分質量、執行時間和并行可擴展性等方面存在很大差異，且具體剖分方法往往需要根據應用問題特點進行專門的適應性研究，很難簡單地判定哪種方法最優，需要綜合考慮剖分方法及應用對象的特點，選擇合適的數據剖分方案。本文旨在綜述并行數據剖分算法的發展現狀，分析典型并行數據剖分軟件的特點和功能。