X10X10Jonathan LeeJonathan LeeDaniel LeeDaniel LeeWhat is X10?What is X10?Programming language designed for high-Programming language designed for high-performance, high-productivityperformance, high-productivitycomputing on high-end computerscomputing on high-end computersDevelopment at IBM ResearchDevelopment at IBM ResearchObject oriented (OO) LanguageObject oriented (OO) LanguageIntended to have simple and clearIntended to have simple and clearsemanticssemanticsKey Design DecisionsKey Design DecisionsIntroduce a new programming languageIntroduce a new programming languageUse the Java programming language as aUse the Java programming language as astarting pointstarting pointAdded aAdded a few new things, took away some oldfew new things, took away some oldthingsthingsUses partitioned global address spaceUses partitioned global address space(PGAS) model(PGAS) modelProgramming Model: PlacesProgramming Model: PlacesCollection of data objects and activities (think ofCollection of data objects and activities (think ofas threads) that operate on the dataas threads) that operate on the dataCan think of as a Can think of as a ““virtual shared-memory multi-virtual shared-memory multi-processorprocessor””Every X10 activity runs in a placeEvery X10 activity runs in a placeCan get reference to the current place with theCan get reference to the current place with theconstant constant hereherePlaces are ordered and the methods Places are ordered and the methods next()next() and andprevprev()() can be used to cycle through them can be used to cycle through themProgramming Model: PGASProgramming Model: PGASX10 uses PGAS (Partitioned GlobalX10 uses PGAS (Partitioned GlobalAddress Space)Address Space)Each place has Each place has ““partitionpartition”” of address of addressspacespaceScalar objects are allocated completely at aScalar objects are allocated completely at asingle placesingle placeElements of an array may be distributedElements of an array may be distributedacross multiple placesacross multiple placesX10 Activities, Places, PGASX10 Activities, Places, PGASDiagramDiagramX10 activities, places, and PGASProgramming Construct: Programming Construct: asyncasyncCan create asynchronous activities usingCan create asynchronous activities usingasyncasync statementstatementasync async (P) S(P) SSpawns an activity at the place designated bySpawns an activity at the place designated byP to execute SP to execute SCreates parallelism!Creates parallelism!Can be thought of as extremelyCan be thought of as extremelylightweight threadslightweight threadsAsync Async ExampleExampleSystem.out.System.out.printlnprintln(1);(1);async async (place.next()) {(place.next()) {System.out.System.out.printlnprintln(2);(2);}}System.out.System.out.printlnprintln(3);(3);Data Structures: RegionData Structures: RegionRegions:Regions: Just a collection of pointsJust a collection of pointsSimple contiguous ranges: [0:N]Simple contiguous ranges: [0:N]Multidimensional blocks: [0:N,0:M]Multidimensional blocks: [0:N,0:M]Can create arbitrary regions of any dimensionCan create arbitrary regions of any dimensionData Structures: RegionData Structures: RegionRegion Operations:Region Operations:Union: Union: R1 || R2R1 || R2Intersection: Intersection: R1 && R2R1 && R2Set Difference: Set Difference: R1 - R2R1 - R2Data Structures: DistributionsData Structures: DistributionsDistributions: MapsDistributions: Maps each point in a regioneach point in a regionto a specific placeto a specific placeBuilt inBuilt in Distributions:Distributions:Constant:Constant: all points map to a single placeall points map to a single placeBlock: contiguous sets ofBlock: contiguous sets of points equally dividedpoints equally dividedamong placesamong placesCyclic: Every Nth pointCyclic: Every Nth point assigned to a placeassigned to a placeData Structures: DistributionsData Structures: DistributionsDistribution Operations:Distribution Operations:Also include:Also include:Range Restriction: Range Restriction: D | RD | RPlace Restriction: Place Restriction: D |D | PPIndexing for places: Indexing for places: D[p]D[p]Example: Block Star DistributionExample: Block Star DistributionDistribution d = dist.factory.block([0,N],places);Distribution d = dist.factory.block([0,N],places);Distribution Distribution blockstar blockstar = [0:-1,0:-1]->here;= [0:-1,0:-1]->here;for (point p : d) {for (point p : d) {blockstar blockstar = = blockstar blockstar || [0:M]->d[i];|| [0:M]->d[i];}}Data Structures: ArraysData Structures: ArraysX10 Arrays:X10 Arrays:Takes a distribution as a parameterTakes a distribution as a parameter to assign data toto assign data toplacesplacesExample: Example: double[.]double[.] data = new double[[0:N]->here];data = new double[[0:N]->here];Built in and user defined functionsBuilt in and user defined functions supportsupportScansScansOverlaysOverlaysReductionsReductionsLiftingLiftingInitializationInitializationProgramming Construct: forProgramming Construct: forfor (point p : R) Sfor (point p : R) SPointwise Pointwise for for sequential iteration by a singlefor for sequential iteration by a singleactivityactivityEquivalent toEquivalent to Java Java foreach foreach loopsloopsννExample:Example:Region r =Region r = [0:N];[0:N];intint[.] x = new [.] x = new intint[[r-r->here];>here];for (pointfor (point p(i) : r) {p(i) : r) {x[p] =x[p] = i * 2;i * 2;}}Programming Construct:Programming Construct:foreachforeachforeach foreach (point p : R) S(point p : R) SFor parallel iteration in a single placeFor parallel iteration in a single placeνν≡≡ for (point p : R) for (point p : R) async async (here) { S }(here) { S }ννExample:Example:Region r =Region r = [0:N];[0:N];intint[.] x = new [.] x = new intint[[r-r->here];>here];foreach foreach (point(point p(i) : r) {p(i) : r) {x[p] =x[p] = i * 2;i * 2;}}Programming Construct:Programming Construct: ateachateachateach ateach (point p : D) S(point p : D) SFor parallel iteration across multiple placesFor parallel iteration across multiple placesνν≡≡ for (point p : D) for (point p : D) async async (D[p]) { S }(D[p]) { S