BEGIN:VCALENDAR
VERSION:2.0
PRODID:Linklings LLC
BEGIN:VTIMEZONE
TZID:America/Chicago
X-LIC-LOCATION:America/Chicago
BEGIN:DAYLIGHT
TZOFFSETFROM:-0600
TZOFFSETTO:-0500
TZNAME:CDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0500
TZOFFSETTO:-0600
TZNAME:CST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20181221T160727Z
LOCATION:D171
DTSTART;TZID=America/Chicago:20181112T111000
DTEND;TZID=America/Chicago:20181112T113000
UID:submissions.supercomputing.org_SC18_sess150_ws_corr105@linklings.com
SUMMARY:Correctness of Dynamic Dependence Analysis for Implicitly Parallel
  Tasking Systems
DESCRIPTION:Workshop\nCorrectness, Debugging, Runtime Systems, Verificatio
 n, Workshop Reg Pass\n\nCorrectness of Dynamic Dependence Analysis for Imp
 licitly Parallel Tasking Systems\n\nLee, Stelle, McCormick, Aiken\n\nIn th
 is paper, we formally verify the correctness of dynamic dependence analysi
 s, a key algorithm for parallelizing programs in implicitly parallel taski
 ng systems. A dynamic dependence analysis of a program results in a task g
 raph, a DAG of tasks constraining the order of task execution. Because a p
 rogram is automatically parallelized based on its task graph, the analysis
  algorithm must generate a graph with all the dependencies that are necess
 ary to preserve the program’s original semantics for any non-deterministic
  parallel execution of tasks. However, this correctness is not straightfor
 ward to verify as implicitly parallel tasking systems often use an optimiz
 ed dependence analysis algorithm. To study the correctness of dynamic depe
 ndence analysis in a realistic setting, we design a model algorithm that c
 aptures the essence of realistic analysis algorithms. We prove that this a
 lgorithm constructs task graphs that soundly and completely express correc
 t parallel executions of programs. We also show that the generated task gr
 aph is the most succinct one for a program when the program satisfies cert
 ain conditions.
URL:https://sc18.supercomputing.org/presentation/?id=ws_corr105&sess=sess1
 50
END:VEVENT
END:VCALENDAR