<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 12 (filtered medium)">
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman","serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-reply;
font-family:"Arial","sans-serif";
color:blue;
font-weight:normal;
font-style:normal;
text-decoration:none none;}
.MsoChpDefault
{mso-style-type:export-only;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.Section1
{page:Section1;}
-->
</style>
<!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";
color:blue'>Jack Tzu-Han Hung will present his research seminar/general exam on
Tuesday May 12 at 10AM <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";
color:blue'>in Room 402. the members of his committee are: David
August, advisor, Margaret Martonosi, <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";
color:blue'>and Doug Clark. Everyone is invited to attend his talk, and
those faculty wishing to remain for the <o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";
color:blue'>oral exam following are welcome to do so. His abstract and
reading list follow below.<o:p></o:p></span></p>
<p class=MsoNormal><span style='font-size:9.0pt;font-family:"Arial","sans-serif";
color:blue'>-----------------------------<o:p></o:p></span></p>
<p class=MsoNormal style='margin-bottom:12.0pt'>Abstract:<br>
<br>
Recently, the multicore systems have emerged as the dominate and promising
architecture in the computing area. Unfortunately, a parallelizing compiler is
essential to extract the potential parallelism from the existing sequential
programs and utilize the power of multicore systems. Independent multi-threading
(e.g., DOALL) and pipelined multi-threading (e.g., decouple software
pipelining, DSWP) parallelization techniques have been researched extensively.
However, each has its own advantages and limitations. On one hand, DOALL
exploits data parallelism and scales well to the number of cores; however, it
requires the lack of loop-carried dependencies and thus suffers from its
applicability. On the other hand, DSWP handles the program dependencies via the
use of communication queue and makes it applicable to more programs; however,
the scalability of this approach is limited by the number of stages in the
pipeline, which is usually far less than the number of cores.<br>
<br>
In this work, we propose two techniques to enhance the scalability of DSWP.
First, instead of being inner-loop-blind, as DSWP does, we examine the
structure of inner loops in the pipeline and exploit the DOALL opportunities if
applicable. This improves the scalability of DSWP since the additional cores
could be used for executing DOALL inner loops. Second, we optimize the
communication for loop live-in and live-out variables by performing pre- and
post-partitioning analyses. The post-partitioning analysis leverages the
existing liveness analysis and is applied for each partition, instead of the
entire loop. The pre-partitioning analysis takes the communication cost into
consideration and could achieve better partitioning. Our initial results show a
speedup up to 5.4x for 052.alvinn and ECLAT.<br>
<br>
Reading List:<br>
<br>
[Text Books]<br>
<br>
* Modern Compiler Implementation in ML, by A. W. Appel, Cambridge University
Press, 1998.<br>
* Compilers: Principles, Techniques, and Tools (2nd Edition) by Alfred V. Aho,
Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Addison Wesley, 2006.<br>
<br>
[Papers]<br>
<br>
* Thies, W., Chandrasekhar, V., and Amarasinghe, S. 2007. A Practical Approach
to Exploiting Coarse-Grained Pipeline Parallelism in C Programs. In Proceedings
of the 40th Annual IEEE/ACM international Symposium on Microarchitecture
(December 01 - 05, 2007).<br>
<br>
* Gordon, M. I., Thies, W., and Amarasinghe, S. 2006. Exploiting coarse-grained
task, data, and pipeline parallelism in stream programs. In Proceedings of the
12th international Conference on Architectural Support For Programming
Languages and Operating Systems (San Jose, California, USA, October 21 - 25,
2006).<br>
<br>
* Hongtao Zhong, Mojtaba Mehrara, Steve Lieberman, Scott Mahlke. "
Uncovering Hidden Loop Level Parallelism in Sequential Applications". The
14th International Symposium on High-Performance Computer Architecture (HPCA),
February, 2008.<br>
<br>
* Guilherme Ottoni, Ram Rangan, Adam Stoler, and David I. August.
Automatic Thread Extraction with Decoupled Software Pipelining. In Proceedings
of the 38th IEEE/ACM International Symposium on Microarchitecture (MICRO),
November 2005. <br>
<br>
* EaswaranRaman, Guilherme Ottoni, Arun Raman, Matthew Bridges, and David I.
August. Parallel-Stage Decoupled Software Pipelining. In Proceedings of the
2008 International Symposium on Code Generation and Optimization (CGO), April
2008. <br>
<br>
* Neil Vachharajani, Ram Rangan, Easwaran Raman, Matthew J. Bridges, Guilherme
Ottoni and David I. August. Speculative Decoupled Software Pipelining. In
Proceedings of the 16th International Conference on Parallel Architecture and
Compilation Techniques (PACT), September 2007.<br>
<br>
* Guilherme Ottoni and David I. August. Global Multi-Threaded Instruction
Scheduling: Technique and Initial Results. In Proceedings of the Sixth Workshop
on Explicitly Parallel Instruction Computer Architectures and Compiler
Technology (EPIC), March 2007. <br>
<br>
* J. R. B. Davies. Parallel loop constructs for multiprocessors. Master’s
thesis, Department<br>
of Computer Science, University of Illinois, Urbana, IL, May 1981.<br>
<br>
* J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph
and its use in optimization. ACM Transactions on Programming Languages and
Systems, 9:319–349, July 1987.<br>
<br>
<o:p></o:p></p>
</div>
</body>
</html>