The Pilot Approach To Cluster Programming In C

The Pilot Approach to ClusterProgramming in CJ. Carter, Bill Gardner, G. GrewalModeling & Design Automation GroupDept. of Computing & Information ScienceUniversity of GuelphOntario, Canada

OutlinezzzzzzzIntroduction & relationship to MPIAbstractions for parallel program designProgramming with Pilot APIImplementation overviewIntegrated deadlock detectionPerformanceExperiences & future work23/APR/10PDSEC2

IntroductionzPilot is a C library for SPMD-style,message-passing cluster programmingzzTarget audience: novice HPC programmers,scientific programmerszzLatest version introduces Fortran APIGoal: break down barriers to adopting HPCFeatures:zzz23/APR/10Simple abstractions for parallel program designSmall, easy-to-remember APIBuilt-in deadlock detectionPDSEC3

Relationship to MPIzNot intended to “replace MPI”zzBuilt as thin layer on top of any standard MPIPurposeszzSimpler way to teach message-passing programmingMay be “good enough” for novice programmerzzz23/APR/10But still suitable for realistic applications in own right (not a toy)Applications mentioned belowCan serve as “ramp” to transition novice to MPIif/when they require more advanced functionalityPDSEC4

Theoretical basiszzzzPilot embodies the process and channelabstractions of Communicating SequentialProcesses (CSP) formal process algebraUsers design solutions based onprocess/channel architecture before they codeEasy to translate design into Pilot function callsUsers need not know CSP (concepts kept underthe hood)23/APR/10PDSEC5

Using process/channel designzVisualize the organization of your algorithmzzDraw processes to divide up your workDraw channels, using arrows since they’re /APR/10Stage2PDSEC6

stdio metaphorzHow to make Pilot functions simple, easy toremember?zzzzzEngineered to conform to fprintf/fscanf syntaxPrintf: “Most common method of debugging”Even novice C programmer will be familiarChannel objects like FILE* variable/arrayMessage list like format stringExample Æ23/APR/10PDSEC7

Simple code sample#include “pilot.h”z Create 2 processes, blue and green:PI PROCESS *blue PI CreateProcess( blue func, 0, NULL );PI PROCESS *green PI CreateProcess( green func, 0, NULL );zzLike POSIX pthread create(), function can execute multiple processesCreate a channel from blue to green:PI CHANNEL *chan PI CreateChannel( blue, green );int blue func( int n, void *v ){PI Write( chan, “%d”, 25 );}23/APR/10int green func( int n, void *v ){int data;PI Read( chan, “%d”, &data );}PDSEC8

Comparing APIsGoal: send an array of 12 float coefficients, 888double data values, and the 888 lengthfloat coeffs[12]; double data[1000]; int len 888;zPilot version:PI Write( chan, “%12f %*lf %d”, coeffs, len, data, len );zMPI version:MPI Send( coeffs, 12, MPI FLOAT, dest, tag, comm );MPI Send( data, 888, MPI DOUBLE, dest, tag, comm );MPI Send( len, 1, MPI INT, dest, tag, comm );23/APR/10PDSEC9

BenefitszEliminates ability to commit some kinds ofcommunication errorszzzMessages allowed to flow between designatedprocesses onlyzzNo low-level arguments (dest, tag, communicator)Removes some (not all) deadlock opportunitiesPilot detects channel not bound to calling process,process at “read” end trying to write, etc.Channels not typed Æ data type not checkedz23/APR/10Avoids undue proliferationPDSEC10

Collective abstractionzMPI (and underlying hardware) may implementcollective operations with special efficiencyzzHow to take advantage in Pilot without breaking theCSP-based model?Solution: Add one more abstractionzz23/APR/10Arbitrary group of channels Æ bundleMust have one common process endpointPDSEC11

Bundle designz“Cone” denotes the bundle of asterBroadcasting to workersSelecting on channelsfrom workers:Which has data to read?(“Master” is a role; does nothave to be rank 0 process)23/APR/10Worker2PDSEC12

Bundle functionszConcept:zIn MPI, why do we code MPI Bcast in a process thatis receiving data?zzzRationale lies in pure SPMD approachNot obvious for novice programmer to graspPilot draws a veil over this peculiarityzzz23/APR/10MasterN WorkersPI Broadcast( bundle ) Æ PI Read( channeli )PI Gather( bundle )Å PI Write( channeli )n PI Select( bundle ) Å PI Write( channeli )PI Read( channel[n] )PDSEC13

Pilot skeleton programzConfiguration phase (executed on allprocessors):zzInterprets command line args, starts MPIPI CreateProcess Channel BundleConfigurationPI ConfigurePI CreateXXXExecutionzExecution phase: PI StartAllzEach Pilot process begins executing itsassociated functionzzmain() continues as rank 0 process(aka PI MAIN)z23/APR/10Exits by returning from functionExits by calling PI StopMainPDSECPI StartAllPI MAIN.PI ion14

Implementation overviewzzzzPilot processes Æ MPI processesPilot channels Æ MPI tagsPilot bundles Æ MPI communicatorsExtensive runtime error checkingzz23/APR/10Diagnostic prints out file name/line no. of Pilot callLevel of checking can be turned lower for lessoverheadPDSEC15

Deadlock: commonparallel programming hazardzDeadlock exacts a harsh penaltyzzzMPI program typically keeps running till time budgetexhaustedBaffling for novice users to diagnoseConcept: “Why do users resist tools?”zzzzz23/APR/10DeSouza & Squyres ‘05, “Why MPI Makes You Scream!”Many barriers to overcome re 3rd-party tools (e.g.,deadlock detector like Umpire)May not be installed on your systemMay cost (Feared to) involve additional serious learning curvePDSEC16

Pilot’s deadlock detectionzSolution: integrate D/D into PilotzzzTrivial to turn on: “-pisvc d” command line argConsumes one additional MPI processAborts program with diagnosis of Pilot function callsinvolved in:zzzzDeadly embraceCircular wait“Dead” wait (other end of channel process exited)Since Pilot functions utilize tiny subset of MPI,D/D implementation much less complex23/APR/10PDSEC17

PerformancezPilot adds very little overhead to MPINo. Reps.IMB V3.1 pingpong TimingsSHARCNET 2.2 GHz Opteron ClusterMPI TimePilot TimeMPI ThruputPilot Thruput1000016001200100010080010600Thruput (MB/sec)Time (usec) &No. 210246412832168421000.1Message Size (bytes)PDSEC18

ExperienceszzPilot development sponsored by SHARCNETconsortium (SW Ontario)Pilot used for graduate HPC course {Guelph,McMaster, Brock, UOIT}zzProjects: parallel MRI reconstruction,scatter search metaheuristicPilot used for undergradparallel programming coursez23/APR/10Fortran: Mars Rover“search for water”spectroscopy simulationPDSEC19

Future workzzzzMore collective functionsMore performance measurementUsability study (we think it’s easier to use )Applying to mixed cluster of Cell BE’s andother platformszzzzSHARCNET has, but almost no one using itPilot for intra-Cell PPE ÅÆ SPE, and inter-nodecommunicationProgrammer uses same process/channel paradigmrather than two or three different librariesFormal verification (based on CSP)23/APR/10PDSEC20

Home page:http://carmel.cis.uoguelph.ca/pilotzzFree download,install guide, tutorialFortran API tested withIntel and Sun StudiozzUses ISO C BINDINGUpcoming Torontoarea tutorialszzSHARCNET SummerSchool, May 31HPCS, June 523/APR/10PDSEC21

Significance of name1.2.3.4.Surface meaning: one who safely guidesyour parallel program to its destinationNod to formalism:π-calculusNod to MPINod to SHARCNET:pilot fish “friend of sharks”23/APR/10PDSEC23

ReactionszzUsers (undergrad and graduate students)appreciate getting a model to use in designingparallel programsDeadlock detector uncovers mysterious hangszzStill have to remind them to turn it onQuote from scientific programmer:z23/APR/10“It's less headache to organize channels and bundlesthan bothering about synchronization betweenprocessors. It turned out more simple andunderstandable for me. PILOT fits my way of thinking.”PDSEC24

Just teach subset of MPI?zCertainly valid, but zzz23/APR/10Pilot process/channel abstractions teach ageneralized conceptual model for designing aparallel solutionMPI programmers still have to deal with low-levelargumentsPilot provides helpful diagnosis for usage problems,including integrated deadlock checkingPDSEC25

IP StatuszNot (yet) open sourcezzzSource code copyright by Univ. of GuelphFree for anyone to download/usePrefer to control development at early stage toavoid zzz23/APR/10bloating of APIbreaking underlying formalismEventual open source release plannedPDSEC26

23/APR/10 PDSEC 3 Introduction zPilot is a C library for SPMD-style, message-passing cluster programming zLatest version introduces Fortran API zTarget audience: novice HPC programmers, scientific programmers zGoal: break down barriers to adopting HPC zFeatures: zSimple abstractions for parallel program design