PRIA

Parallel Programming Refinements for Irregular Applications

UTAustin/CA/0056/2008

Overview

The PRIA project aims to deliver an extensible pattern-based parallel programming system for irregular applications where applications are developed by successively refining “sequential like” codes. The goal is to identify and modularise refinements (a.k.a. patterns, skeletons) that parallelise computations in programs, and to be able to compose such refinements to map base programs to efficient, platform-specific, parallel applications. Aspect and feature oriented programming (AOP/FOP) are two approaches for separation of concerns that will be used as a starting point to implement those refinements.

Project Goals/Results

The main goal of the project is to devise a new way to develop parallel programs by program refinement. The research was strongly driven by applications with an irregular structure. The project focused on two key research areas: 1) parallelisation patterns for irregular applications and 2) approaches to derive the architecture of parallel applications. The following results where attained within this international cooperation:

  • A catalogue of parallelisation patterns for irregular applications
  • A set optimisations that improve locality of references in irregular applications.
  • A parallelisation approach that modularizes parallelism related issues with Aspect-Oriented and Feature-Oriented programing.
  • A new tool to implement parallelisation as model transformations.
  • The study of the parallelisation of an irregular application, which resulted on a parallel implementation of the Superfine algorithm.

Funding

This work was funded by ERDF – European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the FCT – Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project FCOMP-01-0124-FEDER-011413.

Project funding: COMPETE; QREN; EU-FEDER; FCT

Team

  • João Luís Sobral (CCTC-UM)
  • Miguel Pessoa Monteiro (CITI-UNL)
  • Luis Paulo Santos (CCTC-UM)
  • Diogo Telmo Neves (CCTC-UM)
  • Edgar Sousa (CCTC-UM)
  • Keshav Pingali (ICES-UTA)
  • Rui Carlos Gonçalves (CCTC-UM)
  • Don Batory (CS-UTA)
  • Martin Burtscher (ICES-UTA)

Publications

  • B. Medeiros, R. Silva, and J. L. Sobral, “Gaspar: a compositional aspect-oriented approach for cluster applications,” Concurrency and Computation: Practice and Experience, vol. 28, iss. 8, p. 2353–2373, 2016. doi:10.1002/cpe.3666
    [BibTeX]
    @article{Medeiros:2015a,
    author = {Medeiros, Bruno and Silva, Rui and Sobral, João L.},
    title = {Gaspar: a compositional aspect-oriented approach for cluster applications},
    journal = {Concurrency and Computation: Practice and Experience},
    year = {2016},
    volume = {28},
    number = {8},
    pages = {2353--2373},
    doi = {10.1002/cpe.3666},
    }

  • R. C. Gonçalves, “Parallel Programming by Transformation,” PhD Thesis, 2015.
    [BibTeX] [Download PDF]
    @phdthesis{Goncalves:2015,
    author = {Gonçalves, Rui C.},
    school = {Universidades do Minho, Aveiro e Porto},
    title = {Parallel Programming by Transformation},
    year = {2015},
    url = {http://hdl.handle.net/1822/38014},
    }

  • B. Medeiros and J. L. Sobral, “AOmpLib: An Aspect Library for Large-Scale Multi-core Parallel Programming,” in ICPP ’13: Proceedings of the 42nd International Conference on Parallel Processing, 2013, p. 270–279. doi:10.1109/ICPP.2013.36
    [BibTeX]
    @inproceedings{Medeiros:2013b,
    author = {Medeiros, Bruno and Sobral, João L.},
    title = {{AOmpLib}: An Aspect Library for Large-Scale Multi-core Parallel Programming},
    booktitle = {{ICPP} '13: Proceedings of the 42nd International Conference on Parallel Processing},
    year = {2013},
    pages = {270--279},
    doi = {10.1109/ICPP.2013.36},
    }

  • B. Medeiros and J. L. Sobral, “Implementing an OpenMP-like Standard with AspectJ,” in MISS ’13: Proceedings of the 3rd Workshop on Modularity in Systems Software, 2013, p. 1–6. doi:10.1145/2451613.2451615
    [BibTeX]
    @inproceedings{Medeiros:2013,
    author = {Medeiros, Bruno and Sobral, João L.},
    title = {Implementing an {OpenMP}-like Standard with {AspectJ}},
    booktitle = {{MISS} '13: Proceedings of the 3rd Workshop on Modularity in Systems Software},
    year = {2013},
    pages = {1--6},
    doi = {10.1145/2451613.2451615},
    }

  • N. Faria, R. Silva, and J. L. Sobral, “Impact of Data Structure Layout on Performance,” in PDP ’13: Proceedings of the 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, 2013, p. 116–120. doi:10.1109/PDP.2013.24
    [BibTeX]
    @inproceedings{Faria:2013,
    author = {Faria, Nuno and Silva, Rui and Sobral, João L.},
    title = {Impact of Data Structure Layout on Performance},
    booktitle = {{PDP} '13: Proceedings of the 21st Euromicro International Conference on Parallel, Distributed, and Network-Based Processing},
    year = {2013},
    pages = {116--120},
    doi = {10.1109/PDP.2013.24},
    keywords = {locality, collections, multicore, java},
    }

  • T. L. Riché, R. C. Gonçalves, B. Marker, and D. Batory, “Pushouts in Software Architecture Design,” in GPCE ’12: Proceedings of the 11th ACM international conference on Generative programming and component engineering, 2012, p. 84–92. doi:10.1145/2371401.2371415
    [BibTeX]
    @inproceedings{Riche:2012,
    author = {Riché, Taylor. L. and Gonçalves, Rui C. and Marker, Bryan and Batory, Don},
    title = {Pushouts in Software Architecture Design},
    booktitle = {{GPCE} '12: Proceedings of the 11th {ACM} international conference on Generative programming and component engineering},
    year = {2012},
    pages = {84--92},
    doi = {10.1145/2371401.2371415},
    keywords = {mde, program derivation, pushouts, software architectures},
    }

  • D. T. Neves, T. Warnow, J. L. Sobral, and K. Pingali, “Parallelizing SuperFine,” in SAC ’12: Proceedings of the 27th Annual ACM Symposium on Applied Computing, 2012, p. 1361–1367. doi:10.1145/2245276.2231992
    [BibTeX]
    @inproceedings{Neves:2012,
    author = {Neves, Diogo T. and Warnow, Tandy and Sobral, João L. and Pingali, Keshav},
    title = {Parallelizing SuperFine},
    booktitle = {{SAC} '12: Proceedings of the 27th Annual {ACM} Symposium on Applied Computing},
    year = {2012},
    pages = {1361--1367},
    doi = {10.1145/2245276.2231992},
    keywords = {irregular applications, parallelization, phylogeny estimation, polytomy, shared memory, supertree},
    }

  • R. C. Gonçalves and J. L. Sobral, “Modular and Non-invasive Distributed Memory Parallelization,” in MISS ’12: Proceedings of the 2012 Workshop on Modularity in Systems Software, 2012, p. 33–38. doi:10.1145/2162024.2162034
    [BibTeX]
    @inproceedings{Goncalves:2012,
    author = {Gonçalves, Rui C. and Sobral, João L.},
    title = {Modular and Non-invasive Distributed Memory Parallelization},
    booktitle = {{MISS} '12: Proceedings of the 2012 Workshop on Modularity in Systems Software},
    year = {2012},
    pages = {33--38},
    doi = {10.1145/2162024.2162034},
    keywords = {aop, distributed memory, incremental development, parallel programming, software reuse},
    }

  • B. Medeiros and J. L. Sobral, “An aspect-oriented approach to fault-tolerance in grid platforms,” in Ibergrid ’11: Proceedings of the 5th Iberian Grid Infrastrucutre Conference, 2011, p. 267–276. doi:10.4272/978-84-9745-884-9.ch1
    [BibTeX] [Download PDF]
    @inproceedings{Medeiros:2011a,
    author = {Medeiros, Bruno and Sobral, João L.},
    title = {An aspect-oriented approach to fault-tolerance in grid platforms},
    booktitle = {Ibergrid '11: Proceedings of the 5th Iberian Grid Infrastrucutre Conference},
    year = {2011},
    pages = {267--276},
    doi = {10.4272/978-84-9745-884-9.ch1},
    url = {http://alba.di.uminho.pt/research/wp-content/uploads/Medeiros-2011.pdf},
    }

  • R. C. Silva and J. L. Sobral, “Optimizing Molecular Dynamics Simulations with Product Lines,” in VaMoS ’11: Proceedings of the 5th Workshop on Variability Modeling of Software-Intensive Systems, 2011, p. 151–157. doi:10.1145/1944892.1944911
    [BibTeX]
    @inproceedings{Silva:2011,
    author = {Silva, Rui C. and Sobral, João L.},
    title = {Optimizing Molecular Dynamics Simulations with Product Lines},
    booktitle = {{VaMoS} '11: Proceedings of the 5th Workshop on Variability Modeling of Software-Intensive Systems},
    year = {2011},
    pages = {151--157},
    doi = {10.1145/1944892.1944911},
    keywords = {feature oriented programming, molecular dynamics simulations, parallel programming, productline},
    }

  • R. C. Gonçalves and J. L. Sobral, “Pluggable Parallelisation,” in HPDC ’09: Proceedings of the 18th ACM international symposium on High Performance Distributed Computing, 2009, p. 11–20. doi:10.1145/1551609.1551614
    [BibTeX]
    @inproceedings{Goncalves:2009,
    author = {Gonçalves, Rui C. and Sobral, João L.},
    title = {Pluggable Parallelisation},
    booktitle = {{HPDC} '09: Proceedings of the 18th {ACM} international symposium on High Performance Distributed Computing},
    year = {2009},
    pages = {11--20},
    doi = {10.1145/1551609.1551614},
    }

  • D. T. Neves and J. L. Sobral, “Improving the Separation of Parallel Code in Skeletal Systems,” in ISPDC ’09: Proceedings of the 8th International Symposium on Parallel and Distributed Computing, 2009, p. 257–260. doi:10.1109/ISPDC.2009.36
    [BibTeX]
    @inproceedings{Neves:2009,
    author = {Neves, Diogo T. and Sobral, João L.},
    title = {Improving the Separation of Parallel Code in Skeletal Systems},
    booktitle = {{ISPDC} '09: Proceedings of the 8th International Symposium on Parallel and Distributed Computing},
    year = {2009},
    pages = {257--260},
    doi = {10.1109/ISPDC.2009.36},
    keywords = {multicore, skeletons, aspect-oriented programming, dependency injection},
    }

Tools