Data distributions have a serious impact on time complexity of parallel programs, developed
based on domain decomposition.
Set distributions represent a new kind of distributions based on set-valued mappings.
These distributions assign a data object to more than one process. The set distributions can be used especially when the number of processes is greater than the data input size, but sometimes using set distributions can lead to efficient general parallel algorithms. The work-load properties of these distributions and their impact on the number of communications can be easily analysed, since they are formally defined.
Related papers:
- V. Niculescu. On Data Distribution in the Construction of Parallel Programs, The Journal of Supercomputing, Kluwer Academic Publishers, 29(1): 5-25, July 2004 (link).
- V. Niculescu. Cost-efficient parallel programs based on set-distributions for polynomial interpolation, Journal of Parallel and Distributed Computing, Elsevier, Volume 67, Issue 8 (August 2007), pp. 935-946 [DOI].
- V. Niculescu. Using Set-Distribution in Construction of a Parallel Program for Hermite Interpolation, Proceedings of the Fifth Joint Conference on Mathematics and Computer Science, Debrecen, Hungary, June, 2004, pp. 75.
- V. Niculescu. Formal Derivation Based on Set-Distribution of a Parallel Program for Hermite Interpolation, Proceedings of InternationalSymposium on Symbolic and Numeric Algorithms for Scientific Computing SYNASC’04, Timisoara, Romania, Sept. 26-30, 2004, pp.250-258.
- V. Niculescu. Data-Distributions in PowerList Theory. Lecture Notes in Computer Science Vol. 4711: Theoretical Aspects of Computing, Proceedings of ICTAC 2007, Springer-Verlag, 2007: 396-409 [DOI].
- V. Niculescu. Parallel Algorithms for Fast Fourier Transformation using PowerList, ParList and PList Theories, Lecture Notes in Computer Science: Proceedings of International Conference EuroPar 2002, Paderborn, Germany, August 2002, Springer-Verlag, pp. 400-404.