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:20260522T150116Z
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:Wonchan Lee (Stanford University), George Stelle and Patrick M
 cCormick (Los Alamos National Laboratory), and Alex Aiken (Stanford Univer
 sity)\n\nIn this paper, we formally verify the correctness of dynamic depe
 ndence analysis, a key algorithm for parallelizing programs in implicitly 
 parallel tasking systems. A dynamic dependence analysis of a program resul
 ts in a task graph, a DAG of tasks constraining the order of task executio
 n. Because a program is automatically parallelized based on its task graph
 , the analysis algorithm must generate a graph with all the dependencies t
 hat are necessary to preserve the program’s original semantics for any non
 -deterministic parallel execution of tasks. However, this correctness is n
 ot straightforward to verify as implicitly parallel tasking systems often 
 use an optimized dependence analysis algorithm. To study the correctness o
 f dynamic dependence analysis in a realistic setting, we design a model al
 gorithm that captures the essence of realistic analysis algorithms. We pro
 ve that this algorithm constructs task graphs that soundly and completely 
 express correct parallel executions of programs. We also show that the gen
 erated task graph is the most succinct one for a program when the program 
 satisfies certain conditions.\n\nTag: Applications, Correctness, Debugging
 , Floating Point, MPI, OpenMP, Runtime Systems, Tools, Verification\n\nReg
 istration Category: Workshop Reg Pass\n\nSession Chairs: Ignacio Laguna (L
 awrence Livermore National Laboratory (LLNL)) and Cindy Rubio-González (Un
 iversity of California, Davis)\n\n
END:VEVENT
END:VCALENDAR