1 of 54

Tracking and Reducing Uncertainty in Dataflow Analysis-Based Dynamic Parallel Monitoring

Michelle Goodstein*

Phillip Gibbons*

Michael Kozuch‡

Todd Mowry*

​

*Carnegie Mellon University ‡Intel Labs

​

2 of 54

A Challenge of Parallel Programming

It is easy to accidentally introduce bugs when creating parallel software.

​

​

​

​

​

Idea: Adapt techniques to detect bugs in sequential applications

​

​

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

2

Michelle Goodstein

3 of 54

Techniques to Detect Bugs in Sequential Applications

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

3

Michelle Goodstein

Static Analysis

  • Detect bugs based on source code
  • Reason about all possible paths
  • Better at handling scalars than heap-allocated data

x=y+7;

x*=4;

Source Code

Dynamic Analysis

  • Monitor programs at runtime
  • Analyze only taken path
  • Pointer values/memory locations are known at runtime

​

​

P

mov (%ecx), %eax

add $0x7, %eax

shl $0x2, %eax

Running App

4 of 54

Dynamic Program Monitoring

  • Application is dynamically monitored by a lifeguard as it runs
    • Monitors each dynamic instruction
  • Lifeguard maintains finite-state machine model of correct execution
    • Checks metadata to see if program does something wrong
      • Ex: Is performing *p2 safe (e.g., is p2 untainted)?

​

Tracking and Reducing Uncertainty in DADPM

4

Michelle Goodstein

Update p2’s metadata

.

.

taint p2

.

.

*p2

.

.

Lifeguard

Update

metadata

Application

p1

0

p2

​

p3

.

p4

.

Metadata:

Tainted?

Commit Order

0

1

5 of 54

Dynamic Program Monitoring

  • Application is dynamically monitored by a lifeguard as it runs
    • Monitors each dynamic instruction
  • Lifeguard maintains finite-state machine model of correct execution
    • Checks metadata to see if program does something wrong
      • Ex: Is performing *p2 safe (e.g., is p2 untainted)?

​

Tracking and Reducing Uncertainty in DADPM

5

Michelle Goodstein

Is *p2 safe ?

ERROR: metadata for

p2 tainted

.

.

taint p2

.

.

*p2

.

.

Lifeguard

Check

metadata

Application

p1

0

p2

1

p3

.

p4

.

Metadata:

Tainted?

Commit Order

6 of 54

Dynamic Analysis: Challenges in Monitoring Parallel Programs

  • Taint Tracking: Check if *p is trusted (untaint) or untrusted (taint)

​

​

Tracking and Reducing Uncertainty in DADPM

6

Michelle Goodstein

.

.

.

.

.

C: taint p

​

P

Taint Tracking

.

.

A: untaint p

.

.

B: *p=…

​

P

Thread 0

Thread 1

Program Order

7 of 54

Dynamic Analysis: Challenges in Monitoring Parallel Programs

  • Taint Tracking: Check if *p is trusted (untaint) or untrusted (taint)
    • Ordering of *p and taint p determines safety of *p
  • Parallel apps: inter-thread data dependences complicate lifeguards
  • One solution: Dataflow Analysis-Based Dynamic Parallel Monitoring

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

7

Michelle Goodstein

.

.

A: untaint p

.

.

B: *p=…

​

P

.

.

.

.

.

C: taint p

​

P

Thread 0

Thread 1

Program Order

Lifeguard Thread 0

Three Possible Orderings

A

B

C

p is tainted

*p unsafe

A

B

C

p is untainted *p safe

A

B

C

Lifeguard must behave conservatively

8 of 54

Dataflow-Analysis Based Dynamic Parallel Monitoring (DADPM)

​

  • Butterfly Analysis [ASPLOS 2010]

+ Parallel analysis proceeds without capturing inter-thread data dependences

+ Supports relaxed memory consistency models

    • Ignores explicit software synchronization

​

​

​

Tracking and Reducing Uncertainty in DADPM

8

Michelle Goodstein

.

.

.

untaint p

*p

.

.

Thread 1

.

.

.

.

taint p

.

.

.

Thread 2

Lifeguard 2

Lifeguard 1

.

.

.

.

.

.

.

.

Thread 0

Lifeguard 0

Commit Order

9 of 54

Dataflow-Analysis Based Dynamic Parallel Monitoring (DADPM)

​

  • Butterfly Analysis [ASPLOS 2010]

+ Parallel analysis proceeds without capturing inter-thread data dependences

+ Supports relaxed memory consistency models

    • Ignores explicit software synchronization
  • Chrysalis Analysis [PACT 2012]

+ Generalization of Butterfly Analysis to include sync arcs

+ Improved precision (compared to Butterfly Analysis)

Tracking and Reducing Uncertainty in DADPM

9

Michelle Goodstein

.

untaint p

*p

unlock L

.

.

.

.

Thread 1

.

.

.

.

.

lock L

taint p

.

Thread 2

Lifeguard 2

Lifeguard 1

.

.

.

.

.

.

.

.

Thread 0

Lifeguard 0

Commit Order

10 of 54

Prior DADPM Cannot Distinguish True Errors From False Positives

​

​

​

​

​

​

​

​

​

  • Ex: Reuse taint state for truly tainted and conservative judgments

​

Tracking and Reducing Uncertainty in DADPM

10

Michelle Goodstein

.

.

A: untaint p

.

.

B: *p=…

​

P

.

.

.

.

.

C: taint p

​

P

Thread 0

Thread 1

Program Order

Lifeguard Thread 0

Three Possible Orderings

A

B

C

p is tainted

*p unsafe

A

B

C

p is untainted *p safe

A

B

C

11 of 54

This Work: Tracking and Reducing Uncertainty in DADPM

​

​

​

​

​

​

​

  • Idea: Create an intermediate state, uncertain
    • Partition known errors from those which might be errors
    • Precise safe and unsafe states, conservative uncertain state
    • Running Example: TaintCheck (Taint Tracking)
  • Our experiments: 100% of Butterfly Analysis false positives classified as “uncertain”

​

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

11

Michelle Goodstein

.

A: untaint p

.

B: *p=…

​

P

..

.

.

C: taint p

​

P

Thread 0

Thread 1

Prgram Order

Lifeguard Thread 0

Three Possible Orderings

A

B

C

A

B

C

p is uncertain

*p potentially unsafe

A

B

C

Idea: What if we could “zoom in” and resolve uncertainty?

​

12 of 54

Contribution: Reducing Uncertainty in DADPM

​

  • Leverage uncertainty: “zoom in” on-the-fly when detecting uncertainty

​

​

Tracking and Reducing Uncertainty in DADPM

12

Michelle Goodstein

P

P

Lifeguard Thread 0

Thread 0

A: untaint p

​

​

​

​

​

​

B: *p=…

Thread 1

​

​

​

​

C: taint p

Three Possible Orderings

A

B

C

p is tainted

*p unsafe

A

B

C

p is untainted *p safe

A

B

C

13 of 54

Contribution: Reducing Uncertainty in DADPM

​

  • Leverage uncertainty: “zoom in” on-the-fly when detecting uncertainty
  • Eliminate conflicting orderings: can make precise conclusion

​

​

Tracking and Reducing Uncertainty in DADPM

13

Michelle Goodstein

P

P

Lifeguard Thread 0

“Zoom in”: One Order

A

B

C

p is tainted

*p unsafe

Thread 0

A: untaint p

B: *p=…

Thread 1

C: taint p

14 of 54

Related Work: Uncertainty In Static Analysis

  • Pointer Alias Analysis [Emami94, Hind99]
  • Shape Analysis [Dillig11, Yorsh07, Sagiv99]
  • Abstract interpretation: [Dillig11, Yorsh07, Sagiv99, Reps04]

Static analysis: run-time data values and control flow are unknown

​

​

  • DADPM: run-time data values, control flow are known
  • Unknown in DADPM: interleaving of inter-thread data dependences

Tracking and Reducing Uncertainty in DADPM

14

Michelle Goodstein

15 of 54

Roadmap to Remainder of Talk

  • Motivation and Background
  • Related Work
  • Review of Butterfly Analysis
  • Butterfly Analysis with Uncertainty Extensions
  • Dynamic Epoch Resizing
  • Experimental Evaluation
  • Contributions

Tracking and Reducing Uncertainty in DADPM

15

Michelle Goodstein

16 of 54

Butterfly Analysis: Fundamentals

  • Key Insight: Only consider a window W of uncertainty
    • W must account for all buffering in pipeline and memory system
      • Large relative to ROB, memory access latency
      • Small relative to total execution
    • Our experiments: 1000s-10,000s of instructions/thread

​

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

16

Michelle Goodstein

.

.

.

​

.

.

.

.

.

.

.

.

.

​

untaint p

*p

.

.

.

.

.

​

.

.

taint p

​

.

​

Concurrent

region

​

Occurs strictly

before *p

​

​

.

​

Occurs strictly

before *p

​

Commit Order

​

Concurrent

region

​

Window

17 of 54

Butterfly Analysis: A Brief Review

Consider an online execution trace

Tracking and Reducing Uncertainty in DADPM

17

Michelle Goodstein

.

.

.

.

.

.

.

untaint p

*p

.

.

.

.

.

.

.

.

.

.

.

.

taint p

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Commit Order

18 of 54

Butterfly Analysis Review: Epochs Partition Thread Execution

Tracking and Reducing Uncertainty in DADPM

18

Michelle Goodstein

taint p

untaint p

*p

Epoch 1

Epoch 0

Epoch 2

Epoch 3

Epoch 4

Execution divided into epochs separated by at least W events/thread

Commit Order

W

19 of 54

Butterfly Analysis Review: Reasoning About Concurrency

  • From the perspective of the center epoch
  • Most epochs are non-adjacent
    • Instructions in these epochs execute strictly before or strictly after
  • Two epochs are adjacent to center epoch
  • 3 epoch window of potentially concurrent instructions

​

Tracking and Reducing Uncertainty in DADPM

19

Michelle Goodstein

taint p

untaint p

*p

Sliding window

limited to 3 epochs

W

Relative To Center Epoch

W

untaint p

*p

Commit Order

20 of 54

Butterfly Analysis Review: Concurrency Within Three Epoch Window

Tracking and Reducing Uncertainty in DADPM

20

Michelle Goodstein

Tail

Body

Head

Epochs

l

l-1

l+1

Thread t

Wings

Wings

Commit Order

21 of 54

Butterfly Analysis Review: Side-In and Side-Out

  • Extend standard dataflow primitives (In, Out, Gen, Kill)
  • Introduced two new primitives: Side-Out and Side-In
    • Side-Out: Effects of concurrency a block exposes to other threads

Tracking and Reducing Uncertainty in DADPM

21

Michelle Goodstein

Head

Tail

Body

Epochs

l

l-1

l+1

Thread t

Wings

Wings

Commit Order

22 of 54

Butterfly Analysis: Parallel Dataflow Analysis (DADPM)

  • Extend standard dataflow primitives (In, Out, Gen, Kill)
  • Introduced two new primitives: Side-Out and Side-In
    • Side-Out: Effects of concurrency a block exposes to other threads
    • Side-In: Effects of concurrency other threads expose to a block

Tracking and Reducing Uncertainty in DADPM

22

Michelle Goodstein

Head

Tail

Body

Epochs

l

l-1

l+1

Thread t

Wings

Wings

Commit Order

23 of 54

Butterfly Analysis: Parallel Dataflow Analysis (DADPM)

Tracking and Reducing Uncertainty in DADPM

23

Michelle Goodstein

Head

Tail

Body

Epochs

l

l-1

l+1

Thread t

Wings

Wings

  • Two-pass lifeguard analysis over 3-epoch sliding window
  • Lifeguard threads execute in parallel
  • Maintains state
    • Global state (SOS): Summarizes earlier epochs outside the window
    • Local state (LSOS): Global state augmented with info from the head

Commit Order

24 of 54

Tracking and Reducing Uncertainty in DADPM

24

Michelle Goodstein

Butterfly Analysis: Reasoning About Concurrent Regions

24

.

.

.

A: untaint p

​

B: *p

.

.

Thread 1

Thread 2

.

.

.

.

C: taint p

.

.

.

.

Commit Order

.

.

.

.

.

.

.

.

Thread 0

Lifeguard 1

Concurrent Region of Execution Traces

Lifeguard must behave conservatively

Three Possible Orderings

A

B

C

p tainted

*p unsafe

A

B

C

p untainted

*p safe

A

B

C

25 of 54

Tracking and Reducing Uncertainty in DADPM

25

Michelle Goodstein

This Work: Butterfly Analysis With Uncertainty Extensions

25

.

.

.

A: untaint p

​

B: *p

.

.

Thread 1

Thread 2

.

.

.

.

C: taint p

.

.

.

.

Commit Order

.

.

.

.

.

.

.

.

Thread 0

Lifeguard 1

Concurrent Region of Execution Traces

Three Possible Orderings

A

B

C

A

B

C

A

B

C

p uncertain

*p potentially unsafe

Isolate all false positives

26 of 54

Challenge: Two Precise States with Non-Binary Metadata

Side-In/Side-Out

  • Butterfly and Chrysalis Analyses (Reaching Defns):
    • Gen-Side-{In,Out}
  • Butterfly Analysis with New Uncertainty Extensions:
    • Gen-Side-{In,Out}, Kill-Side-{In,Out} and Maybe-Side-{In,Out}

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

26

Michelle Goodstein

.

.

.

GSO

GSI

Butterfly Analysis

.

.

.

GSO

GSI

Butterfly Analysis with New Uncertainty Ext.

MSO

KSO

MSI

KSI

Thread 0

Thread 0

27 of 54

Example: Conflicting taint, untaint in the wings

Dataflow Analysis-Based Dynamic Parallel Monitoring

27

Michelle Goodstein

untaint p

​

​

​

​

​

taint p

Epochs

l

l-1

l+1

Thread t

Wings

Wings

​

​

​

​

*p

​

​

​

​

Commit Order

28 of 54

Butterfly Analysis: Had Only Single Side-Out

Dataflow Analysis-Based Dynamic Parallel Monitoring

28

Michelle Goodstein

taint p

Epochs

l

l-1

l+1

Thread t

Wings

Wings

​

​

​

​

*p

​

​

​

​

Commit Order

untaint p

​

p

​

​

​

​

Taint-Side-Out

29 of 54

New Uncertainty Extensions: Additional Side-Outs Add Complexity

Dataflow Analysis-Based Dynamic Parallel Monitoring

29

Michelle Goodstein

taint p

Epochs

l

l-1

l+1

Thread t

Wings

​

​

​

​

*p

​

​

​

​

Commit Order

Wings

.

.

.

.

.

.

.

.

.

​

p

​

untaint p

​

​

​

p

Taint-Side-Out

Uncertain-Side-Out

Untaint-Side-Out

30 of 54

Butterfly Analysis Had Only Single Side-In

Dataflow Analysis-Based Dynamic Parallel Monitoring

30

Michelle Goodstein

taint p

Epochs

l

l-1

l+1

Thread t

Wings

Wings

​

​

​

​

*p

​

​

​

​

Commit Order

untaint p

​

p

​

​

​

​

Taint Side-In: p

31 of 54

New Uncertainty Extensions: Multiple Side-Ins Add Complexity

Dataflow Analysis-Based Dynamic Parallel Monitoring

31

Michelle Goodstein

taint p

Epochs

l

l-1

l+1

Thread t

Wings

​

​

​

​

*p

​

​

​

​

Commit Order

Wings

.

.

.

.

.

.

.

.

.

​

p

​

untaint p

​

​

​

p

Taint

Side-In

Uncertain Side-In: p

Untaint

Side-In

32 of 54

Challenge: Two Precise States with Non-Binary Metadata

Global (SOS) and Local (LSOS) State

  • Butterfly and Chrysalis Analyses (Reaching Defns):
    • SOS, LSOS
  • Butterfly Analysis with New Uncertainty Extensions:
    • SOSG, SOSK, SOSM, LSOSG, LSOSK, LSOSM

​

  • Increased complexity in state computations and exchanges

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

32

Michelle Goodstein

.

.

.

Butterfly Analysis

.

.

.

Butterfly Analysis with New Uncertainty Ext.

Thread 0

Thread 0

LSOS

​

​

SOS

​

LSOSG

​

LSOSM

​

LSOSK

​

​

SOSG

​

​

SOSM

​

​

SOSK

​

33 of 54

Incorporating Uncertainty: Theoretical Contributions

  • Canonical example: “Reaching Definitions”
    • Gen and Kill are now both precise (“must”)
    • Uncertain state (equivalent to Not-A-Constant in Constant Prop)
  • Lifeguard: TaintCheck
  • Provably sound (never misses true errors)

​

​

​

Can now segregate true errors from potential errors

  • Leverage uncertainty: Dynamically resize epoch boundaries
    • Retains all theoretical guarantees by design
    • Goal: Precision of small epochs with performance of large epochs

​

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

33

Michelle Goodstein

34 of 54

Opportunity: Dynamically Resize Epochs

  • Problem: uncertainty detected after epoch boundaries generated
  • Solution: generate “small” epochs, but elide most of them
    • When necessary, drop down to smaller epochs to resolve uncertainty
    • Potential cost to rollback upon detection

​

​

​

Tracking and Reducing Uncertainty in DADPM

34

Michelle Goodstein

.

A: untaint p

.

.

.

.

.

.

.

..

B: *p=…

.

.

Thread 0

Thread 1

.

.

.

.

.

.

C: taint p

.

.

.

.

Program Order

Concurrent Region of Execution Traces

p uncertain

*p potentially unsafe

Three Possible Orderings

A

B

C

A

B

C

A

B

C

Epoch 5

35 of 54

Dynamically Resizing Epochs in Response to Uncertainty

  • Problem: uncertainty detected after epoch boundaries generated
  • Solution: generate “small” epochs, but elide most of them
    • When necessary, drop down to smaller epochs to resolve uncertainty
    • Potential cost to rollback upon detection

​

Tracking and Reducing Uncertainty in DADPM

35

Michelle Goodstein

Thread 0

Thread 1

Program Order

Concurrent Region of Execution Traces

One Possible Ordering

A

B

C

p tainted

*p unsafe

A: untaint p

B: *p=…

C: taint p

​

5.1

​

5.2

​

5.3

​

5.4

​

5.4

Epoch

36 of 54

Comparison: Butterfly Analysis vs. Butterfly + Uncertainty Ext.

Butterfly Analysis

  • Simple state model: SOS, LSOS

​

  • Simple meet operation: union

​

​

  • Static epoch sizing

Cannot distinguish true errors from false positives

​

​

Butterfly Analysis + Uncertainty Ext.

  • 3x states: SOSM,SOSK,SOSG, LSOSM,LSOSK,LSOSG
  • Complex meet operation: union, intersection & set difference

​

  • Dynamic epoch resizing

Isolates true errors from potential errors

​

Tracking and Reducing Uncertainty in DADPM

36

Michelle Goodstein

Epochs

l

l-1

l+1

Thread t

Wings

Wings

Epochs

l

l-1

l+1

Thread t

Wings

Wings

?

Research Challenges

37 of 54

Dynamic Epoch Resizing Methodology

  • Traces captured with a baseline (“small”) epoch size of 1024 inst/thread
  • Large config: elide all but every 16th epoch boundary
    • Effective epoch size: 16K instructions/thread

​

​

​

​

​

Tracking and Reducing Uncertainty in DADPM

37

Michelle Goodstein

Thread 1

Thread 0

Thread 2

Epochs

l

l-1

l+1

Thread 1

Thread 0

Thread 2

38 of 54

Dynamic Epoch Resizing Methodology

  • Traces captured with a baseline (“small”) epoch size of 1024 inst/thread
  • Large config: elide all but every 16th epoch boundary
    • Effective epoch size: 16K instructions/thread
  • Three dynamic epoch resizing schemes:

​

​

​

Tracking and Reducing Uncertainty in DADPM

38

Michelle Goodstein

Epochs

l

l-1

l+1

Thread 1

Thread 0

Thread 2

?

39 of 54

Dynamic Epoch Resizing Methodology

  • Traces captured with a baseline (“small”) epoch size of 1024 inst/thread
  • Large config: elide all but every 16th epoch boundary
    • Effective epoch size: 16K instructions/thread
  • Three dynamic epoch resizing schemes:

​

Dynamic[l-1,l+1]

Equivalently, Dynamic3

​

​

​

Tracking and Reducing Uncertainty in DADPM

39

Michelle Goodstein

Epochs

l

l-1

l+1

Thread 1

?

Thread 0

Thread 2

2 epoch rollback

​

40 of 54

Dynamic Epoch Resizing Methodology

  • Traces captured with a baseline (“small”) epoch size of 1024 inst/thread
  • Large config: elide all but every 16th epoch boundary
    • Effective epoch size: 16K instructions/thread
  • Three dynamic epoch resizing schemes:

​

Dynamic[l,l+1]

Equivalently, Dynamic2

​

​

​

Tracking and Reducing Uncertainty in DADPM

40

Michelle Goodstein

Epochs

l

l-1

l+1

Thread 1

?

Thread 0

Thread 2

1 epoch rollback

​

41 of 54

Dynamic Epoch Resizing Methodology

  • Traces captured with a baseline (“small”) epoch size of 1024 inst/thread
  • Large config: elide all but every 16th epoch boundary
    • Effective epoch size: 16K instructions/thread
  • Three dynamic epoch resizing schemes:

​

Dynamicl

Equivalently, Dynamic1

​

​

​

Tracking and Reducing Uncertainty in DADPM

41

Michelle Goodstein

Epochs

l

l-1

l+1

Thread 1

Thread 0

?

Thread 2

1 epoch rollback

​

42 of 54

Experimental Methodology

  • Evaluated word-granularity version of TaintCheck on 4 splash benchmarks
  • Synthetically tainted 15% of input data (fixed seed)
  • Traces used 1k inst/thread epoch size
  • Simulated small, large, dynamic configurations

​

  • Uncertainty types:
    • Heuristic: Threshold in 2nd pass analysis hit, analysis returned “heuristic” instead of continuing to explore
    • Uncertain: All other types of uncertainty

​

  • Precision: Count number of failed taint/heuristic/uncertain ops

​

Tracking and Reducing Uncertainty in DADPM

42

Michelle Goodstein

43 of 54

Experimental Methodology

  • Traces gathered using LBA framework [Chen ‘08]
  • Epoch elision performed offline (once per configuration)
    • Simulating dynamic epoch resizing

​

​

  • Measured precision and performance across all configurations
    • Configs: small, large, dynamic1-3
    • Large config: noted which epochs experienced uncertainty
    • Dynamic configs: used small epochs whenever large config experienced uncertainty

Tracking and Reducing Uncertainty in DADPM

43

Michelle Goodstein

44 of 54

Precision: Failed Checks Across 5 Configurations

Tracking and Reducing Uncertainty in DADPM

44

Michelle Goodstein

66

Lower is better

45 of 54

Precision: Failed Checks Across 5 Configurations

Tracking and Reducing Uncertainty in DADPM

45

Michelle Goodstein

66

Zero Failed Taint: All potential false positives isolated to uncertain

46 of 54

Precision: Failed Checks Across 5 Configurations

Tracking and Reducing Uncertainty in DADPM

46

Michelle Goodstein

66

Precision of dynamic runs similar or matches small config (smaller is better)

47 of 54

Precision: Failed Checks Across 5 Configurations

Tracking and Reducing Uncertainty in DADPM

47

Michelle Goodstein

66

Precision of dynamic runs similar or matches small config (smaller is better)

48 of 54

Performance Results: Average Parallel Execution Time

Tracking and Reducing Uncertainty in DADPM

48

Michelle Goodstein

Results shown: averaged over 10 runs, with 95% confidence intervals

Zoomed in

49 of 54

Performance Results: Average Parallel Execution Time

Tracking and Reducing Uncertainty in DADPM

49

Michelle Goodstein

Dynamic configs: performance on par/outperforming large, faster than small

50 of 54

Performance Results: Average Parallel Execution Time

Tracking and Reducing Uncertainty in DADPM

50

Michelle Goodstein

No single dynamic config is best —dynamic1/dynamic2 good enough

51 of 54

Parallel Execution Time, Breakdown Into Phases

Tracking and Reducing Uncertainty in DADPM

51

Michelle Goodstein

Large/dynamic configs have 29-54% reduction in boundary time vs small configs

52 of 54

Contributions: Uncertainty with Dynamic Epoch Resizing

  • Explicitly track all causes of uncertainty in Butterfly Analysis
  • Leverage presence of uncertainty to perform dynamic adaptations
  • Extended Chrysalis Analysis, proved soundness [PhD Thesis, 2014]

​

​

+ Can segregate known errors from potential errors

+ Dynamic epoch resizing : performance of large epochs with precision of small epoch

​

Tracking and Reducing Uncertainty in DADPM

52

Michelle Goodstein

Epochs

l

l-1

l+1

Thread t

Wings

Wings

Epochs

l

l-1

l+1

Thread t

Wings

Wings

?

53 of 54

Tracking and Reducing Uncertainty in Dataflow Analysis-Based Dynamic Parallel Monitoring

Michelle Goodstein

Phillip Gibbons

Michael Kozuch

Todd Mowry

​

Carnegie Mellon University and Intel Labs

​

54 of 54

Contributions: Uncertainty with Dynamic Epoch Resizing

  • Explicitly track all causes of uncertainty in Butterfly and Chrysalis Analyses
  • Leverage presence of uncertainty to perform dynamic adaptations
  • Extended Chrysalis Analysis, proved soundness [PhD Thesis, 2014]

​

​

+ Can segregate known errors from potential errors

+ Dynamic epoch resizing : performance of large epochs with precision of small epoch

​

Tracking and Reducing Uncertainty in DADPM

54

Michelle Goodstein

Epochs

l

l-1

l+1

Thread t

Wings

Wings

?

Epochs

l

l-1

l+1

Thread t

Wings

Wings

?