GrPPI - Generic Reusable Parallel Patterns Interface

GrPPIGrPPIGeneric Reusable Parallel Patterns InterfaceARCOS GroupUniversity Carlos III of MadridSpainJanuary 2018cb e d1/105

GrPPIWarningc This work is under Attribution-NonCommercial-bedcb e dNoDerivatives 4.0 International (CC BY-NC-ND 4.0)license.You are free to Share — copy and redistribute the material in any medium or format.You must give appropriate credit, provide a link to thelicense, and indicate if changes were made. You maydo so in any reasonable manner, but not in any way thatsuggests the licensor endorses you or your use.You may not use the material for commercial purposes.If you remix, transform, or build upon the material, youmay not distribute the modified material.2/105

GrPPIARCOS@uc3mUC3M: A young international research oriented university.ARCOS: An applied research group.Lines: High Performance Computing, Big data,Cyberphysical Systems, and Programming models forapplication improvement.Improving applications:REPARA: Reengineering and Enabling Performance andpoweR of Applications. Financiado por Comisión Europea(FP7). 2013–2016RePhrase: REfactoring Parallel Heterogeneous ResourceAware Applications. Financiado por Comisión Europea(H2020). 2015–2018Standardization:ISO/IEC JTC/SC22/WG21. ISO C standards committe.cb e d3/105

GrPPIAcknowledgementsThe GrPPI library has been partially supported by:Project ICT 644235 “REPHRASE: REfactoring ParallelHeterogeneous Resource-aware Applications” fundedby the European Commission through H2020 program(2015-2018).Project TIN2016-79673-P “Towards Unification of HPCand Big Data Paradigms” funded by the Spanish Ministryof Economy and Competitiveness (2016-2019).cb e d4/105

GrPPIGrPPI teamMain teamJ. Daniel Garcia (UC3M, lead).David del Río (UC3M).Manuel F. Dolz (UC3M).Javier Fernández (UC3M).Javier Garcia Blas (UC3M).CooperationPlácido Fernández (UC3M-CERN).Marco Danelutto (Univ. Pisa)Massimo Torquati (Univ. Pisa)Marco Aldinucci (Univ. Torino).cb e d5/105

GrPPIIntroduction1Introduction2Data patterns3Task Patterns4Streaming patterns5Writing your own execution6Evaluation7Conclusionscb e d6/105

GrPPIIntroductionParallel Programming1cb e dIntroductionParallel ProgrammingDesign patterns and parallel patternsGrPPI architecture7/105

GrPPIIntroductionParallel ProgrammingThinking in Parallel is hard.cb e d8/105

GrPPIIntroductionParallel ProgrammingThinkingis hard.Yale Pattcb e d8/105

GrPPIIntroductionParallel ProgrammingSequential Programming versus Parallel ProgrammingSequential programmingWell-known set of control-structures embedded inprogramming languages.Control structures inherently sequential.cb e d9/105

GrPPIIntroductionParallel ProgrammingSequential Programming versus Parallel ProgrammingSequential programmingWell-known set of control-structures embedded inprogramming languages.Control structures inherently sequential.Parallel programmingConstructs adapting sequential control structures to theparallel world (e.g. parallel-for).cb e d9/105

GrPPIIntroductionParallel ProgrammingSequential Programming versus Parallel ProgrammingSequential programmingWell-known set of control-structures embedded inprogramming languages.Control structures inherently sequential.Parallel programmingConstructs adapting sequential control structures to theparallel world (e.g. parallel-for).But wait!What if we had constructs that could be both sequentialand parallel?cb e d9/105

GrPPIIntroductionDesign patterns and parallel patterns1cb e dIntroductionParallel ProgrammingDesign patterns and parallel patternsGrPPI architecture10/105

GrPPIIntroductionDesign patterns and parallel patternsSoftware designThere are two ways of constructing a software design:One way is to make it so simple that there areobviously no deficiencies, and the other way is tomake it so complicated that there are no obviousdeficiencies.The first method is far more ().parallel execution omp omp get num threads().APIex.set concurrency degree(4)int n ex.concurrency degree()cb e d19/105

GrPPIIntroductionGrPPI architectureDynamic back-endUseful if you want to take the decision at run-time.Holds any other execution policy (or empty).cb e d20/105

GrPPIIntroductionGrPPI architectureDynamic back-endUseful if you want to take the decision at run-time.Holds any other execution policy (or empty).Selecting the execution back-endgrppi :: dynamic execution execution mode(const std::string & opt) {using namespace grppi;if ( "seq" opt) return sequential execution{};if ( " thr " opt) return parallel execution native {};if ( "omp" opt) return parallel execution omp{};if ( "tbb" opt) return parallel execution tbb {};return {};}cb e d20/105

GrPPIIntroductionGrPPI architectureFunction objectsGrPPI is heavily based on passing code sections asfunction objects (aka functors).Alternatives:Standard C predefined functors (e.g. std::plus int ).Custom hand-written function objects.Lambda expressions.Usually lambda expressions lead to more concise code.cb e d21/105

GrPPIData patterns1Introduction2Data patterns3Task Patterns4Streaming patterns5Writing your own execution6Evaluation7Conclusionscb e d22/105

GrPPIData patternsMap pattern2cb e dData patternsMap patternReduce patternMap/reduce patternStencil pattern23/105

GrPPIData patternsMap patternMaps on data sequencesA map pattern applies an operation to every element in atuple of data sets generating a new data set.Given:A sequence x11 , x21 , . . . , xN1 T1 ,A sequence x12 , x22 , . . . , xN2 T2 ,. . . , andA sequence x1M , x2M , . . . , xNM TM ,A function f : T1 T2 . . . TM 7 UIt generates the sequencef (x11 , x12 , . . . , x1M ), f (x21 , x22 , . . . , x2M ), . . . , f (xN1 , xN2 , . . . , xNM )cb e d24/105

GrPPIData patternsMap patternMaps on data sequencescb e d25/105

GrPPIData patternsMap patternUnidimensional mapsmap pattern on a single input data set.Given:A sequence x1 , x2 , . . . , xN TA function f : T 7 UIt generates the sequence:f (x1 ), f (x2 ), . . . , f (xN )cb e d26/105

GrPPIData patternsMap patternKey elementTransformer operation: Any operation that can performthe transformation for a data item.cb e d27/105

GrPPIData patternsMap patternKey elementTransformer operation: Any operation that can performthe transformation for a data item.UnaryTransformer: Any C callable entity that takes adata item and returns the transformed value.auto square [](auto x) { return x x; };auto length []( const std:: string & s) { return s.lenght () ; };cb e d27/105

GrPPIData patternsMap patternKey elementTransformer operation: Any operation that can performthe transformation for a data item.UnaryTransformer: Any C callable entity that takes adata item and returns the transformed value.auto square [](auto x) { return x x; };auto length []( const std:: string & s) { return s.lenght () ; };MultiTransformer: Any C callable entity that takesmultiple data items and return the transformed vaue.auto normalize []( double x, double y) { return sqrt(x x y y); };auto min []( int x, int y, int z) { return std :: min(x,y,z) ; }cb e d27/105

GrPPIData patternsMap patternSingle sequences mappingDouble all elements in sequencetemplate typename Execution std :: vector double double elements(const Execution & ex,const std::vector double & v){std :: vector double res(v.size());grppi :: map(ex, v.begin(), v.end(), res.begin() ,[]( double x) { return 2 x; }) ;}cb e d28/105

GrPPIData patternsMap patternMultiple sequences mappingAdd two vectorstemplate typename Execution std :: vector double add vectors(const Execution & ex,const std::vector double & v1,const std::vector double & v2){auto size std :: min(v1.size() , v2.size () ) ;std :: vector double res(size);grppi ternSingle sequence map/reduceSum of squarestemplate typename Execution double sum squares(const Execution & ex, const std::vector double & v){return grppi :: map reduce(ex, v.begin(), v.end(), 0.0,[]( double x) { return x x; }[]( double x, double y) { return x y; });}cb e d41/105

GrPPIData patternsMap/reduce patternMap/reduce in multiple data setsA map/reduce on multiple input sequences producing asingle value.cb e d42/105

GrPPIData patternsMap/reduce patternMap/reduce in multiple data setsA map/reduce on multiple input sequences producing asingle value.Given:A sequence x11 , x21 , . . . xN1 T1A sequence x12 , x22 , . . . xN2 T2.A sequence x1M , x2M , . . . xNM TMA mapping function m : T1 T2 . . . TM 7 RA reduction identity value id I.A combine operation c : I R 7 Icb e d42/105

GrPPIData patternsMap/reduce patternMap/reduce in multiple data setsA map/reduce on multiple input sequences producing asingle value.Given:A sequence x11 , x21 , . . . xN1 T1A sequence x12 , x22 , . . . xN2 T2.A sequence x1M , x2M , . . . xNM TMA mapping function m : T1 T2 . . . TM 7 RA reduction identity value id I.A combine operation c : I R 7 IIt generates a value reducing the mapping:c(c(c(id, m1 ), m2 ), . . . , mM )Where mk m(x1k , x2k , . . . , xNk )cb e d42/105

GrPPIData patternsMap/reduce patternMap/reduce on two data setsScalar producttemplate typename Execution double scalar product(const Execution & ex,const std::vector double & v1,const std::vector double & v2){return grppi :: map reduce(ex, begin(v1), end(v1), 0.0,[]( double x, double y) { return x y; },[]( double x, double y) { return x y; },v2.begin()) ;}cb e d43/105

GrPPIData patternsMap/reduce patternCannonical map/reduceGiven a sequence of words, produce a container where:The key is the word.The value is the number of occurrences of that word.cb e d44/105

GrPPIData patternsMap/reduce patternCannonical map/reduceGiven a sequence of words, produce a container where:The key is the word.The value is the number of occurrences of that word.Word frequenciestemplate typename Execution auto word freq(const Execution & ex, const std::vector std::string & words){using namespace std;using dictionary std :: map string,int ;return grppi :: map reduce(ex, words.begin(), words.end(), dictionary{},[]( string w) dictionary { return {w,1}; }[]( dictionary & lhs, const dictionary & rhs) dictionary {for (auto & entry : rhs) { lhs [entry. first ] entry.second; }return lhs ;}) ;}cb e d44/105

GrPPIData patternsStencil pattern2cb e dData patternsMap patternReduce patternMap/reduce patternStencil pattern45/105

GrPPIData patternsStencil patternStencil patternA stencil pattern applies a transformation to every elementin one or multiple data sets, generating a new data set asan outputThe transformation is function of a data item and itsneighbourhood.cb e d46/105

GrPPIData patternsStencil patternStencil with single data setA stencil on a single input sequence producing an outputsequence.cb e d47/105

GrPPIData patternsStencil patternStencil with single data setA stencil on a single input sequence producing an outputsequence.Given:A sequence x1 , x2 , . . . , xN TA neighbourhood function n : I 7 NA transformation function f : I N 7 Ucb e d47/105

GrPPIData patternsStencil patternStencil with single data setA stencil on a single input sequence producing an outputsequence.Given:A sequence x1 , x2 , . . . , xN TA neighbourhood function n : I 7 NA transformation function f : I N 7 UIt generates the sequence:f (n(x1 )), f (n(x2 )), . . . , f (n(xN ))cb e d47/105

GrPPIData patternsStencil patternStencil patterncb e d48/105

GrPPIData patternsStencil patternSingle sequence stencilNeighbour averagetemplate typename Execution std :: vector double neib avg(const Execution & ex, const std::vector double & v){std :: vector double res(v.size());grppi :: stencil (ex, v.begin() , v.end(),[]( auto it , auto n) {return it accumulate(begin(n), end(n));},[&]( auto it ) {vector double r;if ( it ! begin(v)) r .push back( prev(it));if (distance( it ,end(end)) 1) r.push back( next(it));return r ;}) ;return res;}cb e d49/105

GrPPIData patternsStencil patternStencil with multiple data setsA stencil on multiple input sequences producing an outputsequence.cb e d50/105