PowerList, ParList, and PList theories and their multidimensional extensions PowerArray, ParArray, and PArray are well suited to express recursive, data-parallel algorithms. Their abstractness is very high and assures simple and correct design of parallel programs.
Base on these theories a model of parallel computation with a very high level of abstraction is defined – PARES (Parallel Recursive Structures).
A model of parallel computation, to be useful must address the following set of requirements:
- abstractness,
- software development methodology,
- architecture independence,
- cost measures,
- no preferred scale of granularity,
- efficiently implementable.
It can be shown that all these requirements are fulfilled for the proposed model.
Being defined based on well-defined theories, programs could be defined to be correct by construction, and also using proving tools assistants – as Coq – programs could be also automatically extracted from specifications.
Related Papers:
- V. Niculescu. PARES – A Model for Parallel Recursive Programs, Romanian Journal of Information Science and Technology (ROMJIST), Ed. Academiei Romane, Volume 14(2011), No. 2, pp. 159–182, 2011 (.pdf).
- Frédéric Loulergue, Virginia Niculescu, Julien Tesson. Implementing powerlists with Bulk Synchronous Parallel ML. In 16th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC2014), Timisoara, Romania, 22-25 sept. 2014, IEEE Computer Society, 2014, pp 325-332. [DOI ]
- Frédéric Loulergue, Virginia Niculescu, and Simon Robillard. Powerlists in Coq: Programming and Reasoning. In First International Symposium on Computing and Networking (CANDAR 2013) Matsuyama, Japan, Dec. 4-6, 2013, pages 57-65. IEEE Computer Society, 2013. [DOI].
- 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, A. Guran. Efficient Recursive Parallel Programs for Polynomial Interpolation. Studia Universitatis “Babes-Bolyai”, Informatica, Special Issue, Vol. LIV , 2009, pp. 227-230 (.pdf).
- Niculescu, V., Guran, A., Bounded Parallelism in PowerList and ParList Theories, SYNASC 2009, Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Timisoara, 2009, IEEE Society Press, pp. 237-244 (ISI – Conference Proceedings Citation Index).