<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px"><div><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">Hanjun Kim will present his preFPO on Tuesday November 13 at 8:30 AM <br>in Room 402.  The members of his committee are:  David August, advisor; <br>David Wentzlaff and Kai Li, readers; JP Singh and Sharad Malik, nonreaders. <br>Everyone is invited to attend his talk.  His abstract follows below.<br>----------------------<br><br></span></div>
ASAP: Automatic Speculative Acyclic Parallelization</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">Speculative Decoupled Software Pipelining (Spec-DSWP) is a promising</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">automatic parallelization technique that speculatively partitions a</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">loop into multiple threads that communicate in a pipelined manner.</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">Speculation can complement conservative static analysis, making</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">automatic parallelization more robust and applicable. Pipelining</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">allows Spec-DSWP to speculate only rarely occurring dependences while</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">respecting the other dependences through communication among threads.</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">Acyclic communication patterns in pipelining make the parallelized</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">programs tolerant of communication latency. However, since Spec-DSWP</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">partitions a loop iteration (a transaction) into multiple</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">sub-transactions across multiple threads according to the pipeline</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">stages, a special runtime system is required that supports</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">multi-threaded transactions (MTX).</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">This dissertation proposes Automatic Speculative Acyclic</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">Parallelization (ASAP) that supports Spec-DSWP on real hardware</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">without any hardware modification. ASAP consists of a speculative</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">acyclic parallelizing compiler and an MTX runtime system. The ASAP</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">compiler automatically parallelizes loops using the Spec-DSWP</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">transformation, and the ASAP runtime system correctly executes the</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">speculatively transformed programs. With synergistic combination of</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">speculation, acyclic communication, and runtime system support, ASAP</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">achieves scalable performance for a wide range of applications on</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px"><span style="font-family:arial,sans-serif;font-size:13.333333969116211px">various parallel platforms such as multicore machines and clusters</span><br style="font-family:arial,sans-serif;font-size:13.333333969116211px">
<span style="font-family:arial,sans-serif;font-size:13.333333969116211px">without any hardware modification.</span><br><br>
</div><br></div></body></html>