A multi-objective hypergraph partitioning model for parallel computing

摘要

Hypergraph partitioning has increasing use in parallel computing because it can accurately represent communication volume and has more expressions. However, the main shortcoming of hypergraph partitioning is that minimising the hyperedge-cut is not entirely the same as minimising the communication overhead, because it does not encapsulate the effects of communication latency and the distribution of communication overhead. We thus propose a multi-objective hypergraph partitioning model for parallel computing, which can take into account the above factors that are not captured by the hyperedge-cut-based cost metric. Moreover, freely adjustable weighting parameters in the model also promote a flexible treatment of different optimisation objectives. Thereby, the proposed model is more suitable for parallel computing. Experimental results on the sample hypergraph confirm the validity of the proposed model.