Construction of optimal multicast trees based on the parameterized communication model

Abstract

Many tree-based multicast algorithms have been proposed to provide an efficient software implementation on parallel platforms without hardware multicast support. These algorithms are either architecture-dependent (not portable) or architecture-independent (portable) but do not provide good performance when ported to different parallel platforms. Based on the LogP model, the proposed parameterized communication model can more accurately characterize the communication network of parallel platforms. The model encompasses a number of critical system parameters which can be easily measured on a given parallel platform. Based on the model, efficient methods to construct optimal multicast trees are proposed for both 1-port and /spl alpha/-port communication architectures. Experimental results conducted on the IBR/SP at Argonne National Laboratory are presented to compare the performance of the optimal multicast tree with two other known free-based multicast algorithms. We claim that our proposed multicast algorithms can be ported to different parallel platforms and provide a near-optimal performance as the truly machine-specific optimal performance is achievable only when the underlying detailed network characteristics are considered.