Implementation of the Pipeline Parallel Programming Technique as an HLPC: Usage, Usefulness and Performance

Mario Rossainz-Lopez, Manuel I. Capel-Tuñon, Odón Carrasco-Limón, Fernando Hernández-Polo, Bárbara Sánchez-Rinza

Abstract


This article presents the pipeline communication/interaction pattern for concurrent, parallel and distributed systems as a high-level parallel composition (HLPC) and discusses its usefulness for deriving parallel versions of sequential algorithms. In particular, we provide examples of the parallel solution for the following problems: adding numbers, sorting numbers and solving a system of linear equations. An approach based on structured parallelism and the parallel object concept is used to solve these problems. In its generic pattern, the pipeline pattern is shown as an HLPC that deploys three types of parallel objects (a manager, various stages and a collector) which are interconnected to form the pipeline processing structure. We also use a method to systematically create the HLPC pipeline and solve this type of problem. Each pipeline instance must be able to handle predefined synchronization restrictions between processes (maximum parallelism, mutual exclusion and synchronization of the producer-consumer type, the use of synchronous, asynchronous and future asynchronous communication, etc.). Finally, the article presents the performance of pipeline HLPC-based implementations of parallel algorithms for solving the problems raised in the paper by using exclusive CPUs.


Keywords


CPAN Pipeline; Paralelismo Estructurado; Objetos Paralelos; Pipeline; Descomposición Funcional; Programación Orientada a Objetos

References


Corradi, A, Leonardo, L., Zambonelli, F.: Experiences toward an Object-Oriented Approach to Structured Parallel Programming. DEIS technical report no. DEIS-LIA-95-007. (1995).

Brinch Hansen: Model Programs for Computational Science, A programming methodology for multicomputers. Concurrency, Practice and Experience, Volume 5, Number 5. (1993).

Darlington, et al.: Parallel Programming Using Skeleton Functions. Proceedings PARLE’93, Munich (1993).

Rossainz, M., Capel, M.: A Parallel Programming Methodology using Communication Patterns named CPANS or Composition of Parallel Object.20TH European Modeling & Simulation. Italy (2008).

Rossainz, M., Capel M.: Design and implementation of communication patterns using parallel objects. International Journal of Simulation and Process Modelling. Volume 12, No.1, Pp: 69-91. ISSN: 1740-2131, (2017).

Robbins, K. A., Robbins S.: UNIX Programación Práctica. Guía para la concurrencia, la comunicación y los multihilos. Prentice Hall. (1999).

Roosta, Séller: Parallel Processing and Parallel Algorithms. Theory and Computation. Springer (1999).

Wilkinson B., Allen M: Parallel Programming. Techniques and Applications Using Networked Workstations and Parallel Computers”. Prentice-Hall. U.S.A. (1999).

Corradi A., Leonardi L.: PO Constraints as tools to synchronize active objects. Pp: 42-53. Journal Object Oriented Programming 10. (1991).

Danelutto, M.; Orlando, S; et al.: Parallel Programming Models Based on Restricted Computation Structure Approach. Technical Report-Dpt. Informatica. Universitá de Pisa (1999).

Rossainz M., Pineda I., Dominguez P.: Análisis y Definición del Modelo de las Composiciones Paralelas de Alto Nivel llamadas CPANs. Modelos Matemáticos y TIC: Teoría y Aplicaciones. Dirección de Fomento Editorial. ISBN 987-607-487-834-9. Pp. 1-19. México. (2014).

Almeida F., Giménez D., Mantas J.M., Vidal A.M.: Introducción a la Programación Paralela". Paraninfo CENAGE Learning. (2008).

Blelloch, Guy E.: Programming Parallel Algorithms. Comunications of the ACM, Vol. 39, No. 3 (1996)

Butenhof, D. R. “Programming with POSIX Threads”. Addison Wesley. 1997.

Arjomandi E., OFarrell W.G., Wilson G. V.: An Object-Oriented Communication Mechanism for Parallel Systems. Conference on Object-Oriented Technologies. Toronto, Ontario, Canada, 1996. USENIX http://www.usenix.org


Full Text: PDF

Supplementary files

1. AMGP_paperCompleto_ROSSAINZ   >>  Download (852KB)

Refbacks





Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.