Optimizing Parallel Performance for Carnegie Mellon GraphRat System

carnegie mellon n.w
1 / 32
Embed
Share

Explore the Carnegie Mellon GraphRats system for parallel performance optimization using weighted random movements in a KxK grid. Learn about the implementation issues and application topics discussed in the Spring 2019 course. Get insights into node count representation and simulation examples to understand the basic idea of transitions for each rat.

  • Carnegie Mellon
  • GraphRats
  • Parallel Performance
  • Optimization
  • Implementation
rayaanacharya
pro_rec Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Carnegie Mellon Assignment 3: GraphRats GraphRats 1 15-418/618 Spring 2019

  2. Carnegie Mellon Topics Application Implementation Issues Optimizing for Parallel Performance Useful Advice 2 15-418/618 Spring 2019

  3. Carnegie Mellon Basic Idea Transitions Each rat decides where to move next t = 0 Don t like crowds 0 1 2 But also don t like to be alone Weighted random choice 3 4 5 t = 1 6 7 8 0 1 2 Graph K X K grid 3 4 5 Initial State Start with all R rats in corner 6 7 8 3 15-418/618 Spring 2019

  4. Carnegie Mellon Node Count Representation (K = 12) t = 0. +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | |576| +---+---+---+---+---+---+---+---+---+---+---+---+ t = 1. +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | |165|164| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | |168| 79| +---+---+---+---+---+---+---+---+---+---+---+---+ 4 15-418/618 Spring 2019

  5. Carnegie Mellon Simulation Example t = 0. +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | |576| +---+---+---+---+---+---+---+---+---+---+---+---+ t = 30. +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | 2 | | 1 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | 3 | 2 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | 1 | 2 | 3 | 2 | 2 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | 1 | | 3 | | 9 | 7 | 11| | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 2 | 2 | 1 | | 5 | 16| 10| 11| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 2 | 1 | | 13| 12| 10| 11| 12| 7 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | 1 | 9 | 6 | 5 | 8 | 14| 13| 11| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | 1 | | 9 | 9 | 11| 7 | 10| 14| 13| 13| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | 1 | 1 | 10| 9 | 6 | 11| 10| 12| 12| 17| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 10| 7 | 12| 11| 14| 12| 11| 10| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 4 | 11| 11| 10| 9 | 10| 12| 12| +---+---+---+---+---+---+---+---+---+---+---+---+ 5 15-418/618 Spring 2019

  6. Carnegie Mellon Visualizations Text ( a for ASCII) Heat Map ( h ) t = 30. +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | 2 | | 1 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | | | | 3 | 2 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | | | | 1 | 2 | 3 | 2 | 2 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | 1 | | 3 | | 9 | 7 | 11| | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 2 | 2 | 1 | | 5 | 16| 10| 11| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 2 | 1 | | 13| 12| 10| 11| 12| 7 | +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | | 1 | 9 | 6 | 5 | 8 | 14| 13| 11| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | 1 | | 9 | 9 | 11| 7 | 10| 14| 13| 13| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | 1 | 1 | 10| 9 | 6 | 11| 10| 12| 12| 17| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 10| 7 | 12| 11| 14| 12| 11| 10| +---+---+---+---+---+---+---+---+---+---+---+---+ | | | | 1 | 4 | 11| 11| 10| 9 | 10| 12| 12| +---+---+---+---+---+---+---+---+---+---+---+---+ 6 15-418/618 Spring 2019

  7. Carnegie Mellon Running it yourself linux> cd some directory linux> git clone https//github.com/cmu15418/asst3-s19.git linux> cd asst3-s19/code Linux> make demoX X from 1 to 10 Demos 1: Text visualization, synchronous updates 2: Heap-map, synchronous updates 7 15-418/618 Spring 2019

  8. Carnegie Mellon Determining Rat Moves 300 8 40 83 120 Count number of rats at current and adjacent locations Adjacency structure represented as graph Compute reward value for each location Based on load factor l= count/average count l * Ideal load factor (ILF) (varying) ? Fitting parameter (= 0.4) 8 15-418/618 Spring 2019

  9. Carnegie Mellon Reward Function Reward Function 1.2 1 0.8 0.6 ILF 1.25 ILF 1.75 0.4 ILF 2.25 0.2 0 0 2 4 6 8 10 Load Factor Maximized at ILF Just above average population Drops for smaller loads (too few) and larger loads (too crowded) 9 15-418/618 Spring 2019

  10. Carnegie Mellon Reward Function (cont.) Reward Function 1.1 1 0.9 0.8 0.7 0.6 ILF 1.25 0.5 0.4 ILF 1.75 0.3 0.2 ILF 2.25 0.1 0 1 10 100 1000 Load Factor Falls off gradually Reward(1000)= 0.0132 10 15-418/618 Spring 2019

  11. Carnegie Mellon Computing Ideal Load Factor (ILF) Suppose node has count cl and neighbor has count cr Compute imbalance as 1 0.8 0.6 0.4 0.2 0 0.01 0.1 1 10 100 -0.2 -0.4 -0.6 -0.8 -1 11 15-418/618 Spring 2019

  12. Carnegie Mellon Computing Ideal Load Factor (cont.) For node u with population p(u) Define ILF as Minimum 1.25 When adjacent nodes much less crowded Maximum 2.25 When adjacent nodes much more crowded Changes as rats move around 12 15-418/618 Spring 2019

  13. Carnegie Mellon Selecting Next Move Population Reward (avg load = 10) 300 0.071 8 40 0.678 0.225 0.538 83 120 0.153 Weighted Choices (node followed by row-major ordering of neighbors) x = 1.24 0.00 0.10 0.20 0.30 0.40 0.50 0.60 0.70 0.80 0.90 1.00 1.10 1.20 1.30 1.40 1.50 1.60 1.70 Choose random number between 0 and sum of rewards Move according to interval hit 13 15-418/618 Spring 2019

  14. Carnegie Mellon Update Models Synchronous Demo 2 Compute next positions for all rats, and then move them Causes oscillations/instabilities Rat-order Demo 3 For each rat, compute its next position and then move it Smooth transitions, but costly Batch Demo 4 For each batch of B rats, compute next moves and then move them B = 0.02 * R Smooth enough, with better performance possibilities 14 15-418/618 Spring 2019

  15. Carnegie Mellon What We Provide Python version of simulator Demo 4 Very slow C version of simulator Fast sequential implementation Demo 5: 36X36 grid, 1,290 rats Demo 6: 180X180 grid, 1,036,800 rats That s what we ll be using for benchmarks! Generate visualizations by piping C simulator output into Python simulator Operating in visualization mode See Makefile for examples 15 15-418/618 Spring 2019

  16. Carnegie Mellon Correctness Simulator is Deterministic Global random seed Random seeds for each rat Process rats in fixed order You Must Preserve Exact Same Behavior Python simulator generates same result as C simulator Use regress.py to check Only checks small cases Useful sanity check Benchmark program compares your results to reference solution Handles full-sized graphs 16 15-418/618 Spring 2019

  17. Carnegie Mellon Graphs: Tiled (Demos 1 6) Rats spread quickly within region More slowly across regions Hub nodes tend to have high counts Base grid K X K nodes, each with nearest neighbor connectivity Hub (red) nodes connect to all other nodes in region For K = 180 Most nodes have degree 5 Hubs have degree 899 17 15-418/618 Spring 2019

  18. Carnegie Mellon Other graphs Horizontal Vertical Larger regions k = 180: Max degree = 2,699 18 15-418/618 Spring 2019

  19. Carnegie Mellon Other graphs Parquet Larger regions k = 180: Max degree = 2,699 19 15-418/618 Spring 2019

  20. Carnegie Mellon Initial States (Parquet Graph) Right Corner (r) Demo 8 Diagonal (d) Demo 9 Uniform (u) Demo 10 t = 0 t = 5 20 15-418/618 Spring 2019

  21. Carnegie Mellon Graph Representation N node, M edges neighbor_start (length = N+1) 0 1 2 0 3 7 10 14 19 23 26 30 33 3 4 5 6 7 8 0 1 3 1 0 2 4 2 1 5 3 0 4 6 neighbor Includes self edges length = N+M 4 1 3 5 7 5 2 4 8 6 3 7 Having pointer to end is useful (why?) 7 4 6 8 8 5 7 21 15-418/618 Spring 2019

  22. Carnegie Mellon Sample Code From sim.c Compute reward value for node /* Compute weight for node nid */ static inline double compute_weight(state_t *s, int nid) { int count = s->rat_count[nid]; double ilf = neighbor_ilf(s, nid); return mweight((double) count/s->load_factor, ilf); } Simulation state stored in state_t struct Reward function computed by mweight 22 15-418/618 Spring 2019

  23. Carnegie Mellon Sample Code From sim.c Compute sum of reward values for node Store for later reuse /* Compute sum of weights in region of nid */ static inline double compute_sum_weight(state_t *s, int nid) { graph_t *g = s->g; double sum = 0.0; int eid; int eid_start = g->neighbor_start[nid]; int eid_end = g->neighbor_start[nid+1]; for (eid = eid_start; eid < eid_end; eid++) { int nbrnid = g->neighbor[eid]; double w = compute_weight(s, nbrnid); s->node_weight[nbrnid] = w; sum += w; } return sum; } 23 15-418/618 Spring 2019

  24. Carnegie Mellon Sample Code Compute next move for rat static inline int next_random_move(state_t *s, int r) { int nid = s->rat_position[r]; random_t *seedp = &s->rat_seed[r]; double tsum = compute_sum_weight(s, nid); graph_t *g = s->g; double val = next_random_float(seedp, tsum); double psum = 0.0; int eid; int eid_start = g->neighbor_start[nid]; int eid_end = g->neighbor_start[nid+1]; for (eid = eid_start; eid < eid_end; eid++) { psum += s->node_weight[neighbor[eid]]; if (val < psum) { return g->neighbor[eid]; } } } 24 15-418/618 Spring 2019

  25. Carnegie Mellon Sequential Efficiency Considerations Consider move computation for rat at node with degree D How many (on average) iterations of loop in next_random_move? Is there a better way? Provided code uses many optimizations Precompute weights at start of batch Fast search 25 15-418/618 Spring 2019

  26. Carnegie Mellon Finding Parallelism Sequential constraints Must complete time steps sequentially Must complete each batch before starting next ILF values and weights then need to be recomputed Sources of parallelism Over nodes Computing ILFs and reward functions Over rats (within a batch) Computing next moves Updating node counts 26 15-418/618 Spring 2019

  27. Carnegie Mellon Performance Measurements Nanoseconds per move (NPM) R rats running for S steps Requires time T NPM = 109 * T / (R * S) Reference solution: 665 NPM for 1 thread 84 NPM for 12 threads 7.9 X speedup 27 15-418/618 Spring 2019

  28. Carnegie Mellon Performance Targets Benchmarks 6 combinations of graph/initial state Each counts 15 points Target performance T = measured time Tr = time for reference solution Tr / T = How well you reach reference solution performance Full credit when 0.9 Partial when 0.5 28 15-418/618 Spring 2019

  29. Carnegie Mellon Machines Latedays cluster 16 worker nodes + 1 head node Each is 12-core Xeon processor (dual socket with 6 cores each) You submit jobs to batch queue Assigned single processor for entire run Python script provided Code Development OK to do code development and testing on other machines But, they have different performance characteristics Make sure to use 6 or 12 threads to ensure correct partitioning of nodes across processors 29 15-418/618 Spring 2019

  30. Carnegie Mellon Instrumenting Your Code How do you know how much time each activity takes? Create simple library using cycletimer code Bracket steps in your code with library calls Use macros so that you can disable code for maximum performance START_ACTIVITY(ACTIVITY_NEXT); #pragma omp parallel for schedule(static) for (ri = 0; ri < local_count; ri++) { int rid = ri + local_start; s->rat_position[rid] = fast_next_random_move(s, rid); } FINISH_ACTIVITY(ACTIVITY_NEXT); 30 15-418/618 Spring 2019

  31. Carnegie Mellon Evaluating Your Instrumented Code 1 thread 194 ms 2077 ms 4029 ms 11733 ms 651 ms 1.0 % startup 11.1 % compute_weights 21.6 % compute_sums 62.8 % find_moves 3.5 % set_ops 0.0 % unknown 3 ms 12 threads 192 ms 426 ms 940 ms 3168 ms 1325 ms 2 ms 3.2 % startup 7.0 % compute_weights 15.5 % compute_sums 52.3 % find_moves 21.9 % set_ops 0.0 % unknown Can see which activities account for most time Can see which activities limit parallel speedup 31 15-418/618 Spring 2019

  32. Carnegie Mellon Some Logos 32 15-418/618 Spring 2019

Related


Regulatory Update for Community and Local Energy Stakeholders - December 2023

Regulatory Update for Community and Local Energy Stakeholders - December 2023

kit
WCSSF Rec Plus Coaches Meeting - Spring 2024

WCSSF Rec Plus Coaches Meeting - Spring 2024

bartleby
Mastering Color in Film: A Comprehensive Guide to Using Color Grading Techniques

Mastering Color in Film: A Comprehensive Guide to Using Color Grading Techniques

bayo
PERFEKT GLIDE 30-REC.30 Built-in Telescopic Range Hood Features and Specifications

PERFEKT GLIDE 30-REC.30 Built-in Telescopic Range Hood Features and Specifications

riva
Proposed Approach for Handling Changes in End User Categories

Proposed Approach for Handling Changes in End User Categories

sora
Find the Best Recruitment Agencies in Kochi - A Comprehensive Guide

Find the Best Recruitment Agencies in Kochi - A Comprehensive Guide

Kelvin1
Why More Job Seekers Are Turning to Recruitment Agencies in Canada

Why More Job Seekers Are Turning to Recruitment Agencies in Canada

Kelvin1
SRYA Clinic Soccer Fall 2021 Updates and Protocols

SRYA Clinic Soccer Fall 2021 Updates and Protocols

ari
Intramural Sports Information and Policies for Softball Participants

Intramural Sports Information and Policies for Softball Participants

rochford_a
Dedications in Budgetary Policy

Dedications in Budgetary Policy

erle_131
REC and SEC Coordinates in Geodesy

REC and SEC Coordinates in Geodesy

acet_3
Exciting Updates from SRYA County Soccer Fall 2021 - Important Details

Exciting Updates from SRYA County Soccer Fall 2021 - Important Details

aash265
Enhancing Recipe Recommendations with C-KGAT Model

Enhancing Recipe Recommendations with C-KGAT Model

caul_wa
Solar Observatory Open House | January 01, 2017

Solar Observatory Open House | January 01, 2017

pricev
Analysis of Vermont's Renewable Energy Standard and REC System

Analysis of Vermont's Renewable Energy Standard and REC System

jmatt
Programme Dashboard Update April 2021

Programme Dashboard Update April 2021

djos
2021-2022 Coaches Meeting: Crystal Lake Soccer Federation Overview

2021-2022 Coaches Meeting: Crystal Lake Soccer Federation Overview

kharmync
Music

Music

cod_mul
T-REC Rulemaking Milestones and Proposed Draft Rules

T-REC Rulemaking Milestones and Proposed Draft Rules

jymirmo

More Related Content