Developing Scalable Parallel Applications in X10 David Grove, Vijay Saraswat, Olivier Tardieu IBM TJ Watson Research Center

Tutorial Objectives

Tutorial Outline

X10 Genesis: DARPA HPCS Program (2004)

Flash forward a few years… Big Data and Commercial HPC

X10 Performance and Productivity at Scale

Partitioned Global Address Space (PGAS) Languages

X10 combines PGAS with asynchrony (APGAS)

Hello Whole World

Sequential Monty Pi

Concurrent Monty Pi

Concurrent Monty Pi (Collecting Finish)

Distributed Monty Pi (Collecting Finish)

Distributed Monty Pi (GlobalRef)

Overview of Language Features

async

finish

atomic

when

at

Distributed Object Model

Take a breath…

X10 Target Environments

X10 Implementation Summary

X10 Compilation

X10 Runtime Software Stack

Performance Model: async, finish, and when

Performance Model: Places and at

Performance Model: Native X10 vs. Managed X10

Slide 30

Towards a Scalable HelloWholeWorld

Towards a Scalable HelloWholeWorld (2)

Towards a Scalable HelloWholeWorld (3)

Towards a Scalable HelloWholeWorld (4)

Finally: a Simple and Scalable HelloWholeWorld

K-Means: description of the problem

Lloyd's Algorithm

Slide 38

Summary of Scalable KMeans in X10

KMEANS

KMeans initialization

KMeans compute kernel

LU Factorization

Summary of Scalable LU in X10

LU

Accessing Native code

Allocation of Distributed BlockedArray (in Huge Pages)

Row exchange via asynchronous RDMAs

Slide 49

Global Load Balancing

Global Load Balancing: Central Problem

Global Load Balance: The Lifeline Solution

Algorithm sketch for Lifeline-based GLB Framework

UTS: Unbalanced Tree Search

UTS

UTS Main Loop: processStack

UTS: steal

UTS: give

UTS: distribute & reject

UTS: deal

Slide 61

X10 Global Matrix Library

Global Matrix Library

Matrix Partitioning and Distribution

Slide 65

Slide 66

GML Example: PageRank

PageRank Performance

GML Example: Gaussian Non-Negative Matrix Multiplication

GNMF Performance

Global Matrix Library Summary

Sat X10

Slide 73

Slide 74

Slide 75

Slide 76

X10 Project Highlights since SC’11

Summary of X10’12 Workshop

X10 Community: StreamX10

X10 Community: Large-Scale Traffic Flow Simulation

X10 Community: ScaleGraph

X10 Community: M3R – Main Memory Map Reduce (VLDB’12)

X10 Community: ANUChem

Final Thoughts

X10 References