Cost-efficient parallel programs based on set-distributions for polynomial interpolation

摘要

The paper presents parallel algorithms for Lagrange and Hermite interpolation methods formally derived from specifications, and using set-distributions. Set-distributions are based on set-valued mappings, and they assign a data object to more than one process. The derivation from specifications assures the correctness, and the set-distributions assure the efficiency of the programs. The obtained parallel algorithms have very good time complexities and speeds-up, and they are also cost-efficient. We consider the number of processes p to be a parameter of the algorithms, so, bounded parallelism is considered. The derivation of the algorithms is not ruled by any particular interconnection network. The possible mappings on different networks could be evaluated. The performance analysis is done considering a full-connected network, and other two interconnection networks: hypercube and multi-mesh hypercube, which preserve the cost-efficiency of the algorithms.