Making Time-stepped Applications Tick in the Cloud

Making Time-stepped Applications Tick in the Cloud Tao Zou, Guozhang Wang, Marcos Vaz Salles*, David Bindel, Alan Demers, Johannes Gehrke, Walker White Cornell University *University of Copenhagen (DIKU) 1 Time-Stepped Applications Executed with parallelism organized into

logical ticks. Implemented using Bulk Synchronous Parallel (BSP) Model Tick Tick Processors P1 P2 P3 Pn 1 Pn

Local Computation Communication Global Barrier 2 Running Example: Fish Simulation Tick

Behavioral Simulation Traffic simulation Simulation of groups of animals 3 Other Time-Stepped Applications Iterative Graph Processing Matrix Computation 4 Why Run Scientific Applications in the Cloud?

Elasticity Cost Saving Instant Availability Avoid jobs queuing for days 5 What Does Cloud Infrastructure Imply Unstable network latencies Local Cluster

VS Large Small Instance EC2 Cluster Instance Virtualization Lack of network performance isolation 6 Time-Stepped Applications under Latency Jitter

Sensitive to latencies Processors P1 P2 P3 Pn 1 Pn Remove unnecessary barriers Jitter still propagates

Local Computation Communication Barrier Synchronization 7 Problem Time-stepped applications Unstable latencies Solution space Improve the networking infrastructure

Recent proposals only tackle bandwidth problems Make applications more resistant to unstable latencies 8 Talk Outline Motivation Our Approach

Experimental Results Conclusions 9 Why not Ad-Hoc Optimizations? Disadvantages No Generality Goal: Applicable to all time-stepped applications No Ease of Programming Goal: Transparent optimization and communication Error-Prone

Goal: Correctness guarantee Programming Model + Jitter-tolerant Runtime 10 Talk Outline Motivation Our Approach Programming Model Jitter-tolerant Runtime Experimental Results Conclusions

11 Data Dependencies: What to Communicate Read Dependency Example: How far can a fish see? Write Dependency Example: How far can a fish move? Write Read

Key: Modeling Dependencies 12 Programming Model Modeling State Motivated by thinking of the applications as distributed database system Application state: Set of tuples Fish tuple Fish school application state Selection over state: Query 2D range query over fish school

13 Programming Model Modeling Data Parallelism Partition Function: PART Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 14

Programming Model Modeling Computation Parallel Computation: STEP ToCompute Context Q1 Q2 Q3 Q 4 Q 6 Q7 Q8 Q9 Context: How large? 15

Programming Model Modeling Dependencies: Read Dependency: Q R(Q) Contains all necessary tuples in context to compute STEP 16 Programming Model

Modeling Dependencies: STEP Q? R(Q) Inverse Read Dependency: Q Contains all tuples that can be computed with as context STEP 17

Programming Model Modeling Dependencies: Write Dependency: Q W(Q) Contains all tuples generated by computing 18 Programming Model

Modeling Dependencies: Inverse Write Dependency: Q Contains all tuples in the next tick after computing 19 Programming Model: All together PART data parallelism

STEP computation , read dependencies write dependencies Remarks: PageRank Users inherently think in terms of dependencies Not limited to spatial properties 20 Talk Outline Motivation

Our Approach Programming Model Jitter-tolerant Runtime Experimental Results Conclusions 21 Jitter-tolerant Runtime Input: Functions defined in programming model Output: Parallel computation results Requirement:

Efficiency and Correctness 22 Runtime Dependency Scheduling Tick Q IQ R IW (Q) IW(Q) Compute

Send out updates Wait for messages All message received Tick Compute Compute ? Compute Send out updates

Tick Compute No. Incoming message may contain updates to Q. is not influenced by the messages Intuition: schedule computation for future ticks when delayed

23 Runtime Computational Replication Tick Q WR(Q) Compute Send out updates

Wait for messages Compute Tick Compute Intuition: enlarge region to compute contents of delayed messages. ,, 24 Our Approach: Summary Programming model captures Application state

Computation logic Data dependencies Jitter-tolerant runtime Dependency scheduling Computational replication 25 Talk Outline Motivation Our Approach Programming Model Jitter-tolerant Runtime

Experimental Results Conclusions 26 Experimental Setup A prototype framework Jitter-tolerant runtime MPI for communication Three different applications A fish school behavioral simulation A linear solver using the Jacobi method

A message-passing algorithm computes PageRank Hardware Setup Up to 100 EC2 large instances (m1.large) 2.26GHz Xeon cores with 6MB cache 7.5GB main memory 27 Methodology Observation: Temporal variation in network performance Solution Execute all settings in rounds of fixed order At least 20 consecutive executions of these rounds

28 Effect of Optimization: Fish Sim Baseline: Local Synchronization; Sch: Dependency Scheduling; Rep: Computational Replication 29 Effect of Optimization: Jacobi

Baseline: Local Synchronization; Sch: Dependency Scheduling; Rep: Computational Replication 30 Scalability: Fish Simulation Baseline: Local Synchronization; Sch: Dependency Scheduling; Rep: Computational Replication 31 Conclusions Questions? Thank you!

Latency jitter is a key characteristic of todays cloud environments. Programming model + jitter-tolerant runtime Good performance under latency jitter Ease of programming Correctness We have released our framework as a public Amazon AMI: http ://www.cs.cornell.edu/bigreddata/games/. Our framework will be used this fall in CS 5220 (Applications of Parallel Computers) at Cornell. 32

Recently Viewed Presentations

  • Lesson 1: Installing Servers MOAC 70-410: Installing and

    Lesson 1: Installing Servers MOAC 70-410: Installing and

    Installing Third-Party Drivers. If hard drives are connected to a third-party controller, rather than the one integrated into the motherboard, the installation procedure may not detect your hard drive.
  • Georgia and the American Experience

    Georgia and the American Experience

    Conditions in Georgia (and the South) at the end of the war: Farms were in ruins; not enough food. Homes, railways, bridges, roads were destroyed or in need of repair. Banks were closed - Confederate money was worthless. The state...
  • Antibiotics Antivirals Antifungals Anti-tubercular ...

    Antibiotics Antivirals Antifungals Anti-tubercular ...

    drugs for bugs ?? antibiotics antiviralsa antifungals anti-tubercular antimalarial antihelminthic antimycobacterial antivirals antibiotics commonly known as
  • Aha Moku Advisory Committee Public Meeting on Draft

    Aha Moku Advisory Committee Public Meeting on Draft

    Submit comments to Island Po'o AMAC to vote on final draft in December 2015 * * On-going Steps Makua Shoreline, Makua Ahupuaa, Waianae Moku, Kakuhihewa Kaena Point, Keawaula Ahupuaa AMAC draft rules released for comment (AMAC, DLNR, OHA, AHCC, General...
  • CHA Basic Training Via Distance

    CHA Basic Training Via Distance

    BASIC TRAINING VIA DISTANCE Outcomes & Lessons Learned in Alaska Mary M. Rydesky & Dorothy Hight © 2008
  • Microsoft® Lync™

    Microsoft® Lync™

    Adam Gent. UK UC User Group. [email protected] Agenda. What is Office 365. Applications available in Office 365. Lync in Office 365. Using Exchange UM in Office 365 with on premise Lync. What is Office 365. Provides Cloud Based Solutions.
  • Basic Computer Skills

    Basic Computer Skills

    The program opens in a new window. The program will be represented by a button on the taskbar. ... Check this box to have your computer direct to your log in screen once you resume working on the computer. ......
  • Cell Transport Powerpoint - KEVIN COEN

    Cell Transport Powerpoint - KEVIN COEN

    S7L2. Students will describe the structure and function of cells, tissues, organs, and organ systems. Explain that cells take in nutrients in order to grow and divide and to make needed materials.