<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div class="" style="word-wrap:break-word; line-break:after-white-space"><span class="" style="font-size:14.666666984558105px">This is an announcement of Ivy Wang's MS Presentation</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">===============================================</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Candidate: Ivy Wang</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Date: Wednesday, May 29, 2024</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Time: 10 am CT</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Location: JCL 298</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Title: Organize Fine-grained Parallelism Using Keys At Scale</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Abstract: Rapidly proliferating machine learning and graph processing applications, demand high-</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">performance on petascale datasets. Achieving this performance requires efficient exploitation</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">of irregular parallelism, as their sophisticated structures and real-world data produce com-</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">putations with extreme irregularity (e.g., million-fold skew). The need to exploit large-scale</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">parallel hardware (million-fold parallelism) is a further challenge.</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px"> Programming irregular data and parallelism using existing models (e.g., MPI) is difficult</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">because they couple naming, data mapping, and computation mapping. Further, they only</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">exploit coarse-grained parallelism. To solve this problem, we present a key-based program-</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">ming model, called key-value map-shuffle-reduce (KVMSR). The model enables programmers</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">to express fine-grained parallelism across programmer-defined key-value sets. The parallel</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">computation can then be optimized using KVMSR’s modular control for load balance and</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">data locality. KVMSR achieves this by expressing parallelism with respect to a global address</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">space and providing modular control to flexibly bind computation to compute resources.</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px"> We define the KVMSR model and illustrate it with three programs, convolution filter,</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">PageRank and BFS, to show its ability to separate computation expression from binding to</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">computation location for high performance. We evaluate KVMSR on a novel fine-grained</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">parallel architecture, called UpDown, supporting up to 4 billion fold hardware parallelism</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">in the full system design. On an 8,192-way parallel compute system, KVMSR modular</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">computation location control achieves up to 9,202x performance with static approaches and</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">an increase of 3,136x to 4,258x speedup with dynamic approaches for computation location</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">binding comparing to the single-thread CPU programs.</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Advisors: Andrew Chien</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Committee Members: Andrew Chien, John Reppy, Haryadi Gunawi, and David Gleich</span><br class="" style="font-size:14.666666984558105px">
<div class="">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<br class="x_Apple-interchange-newline">
</div>
<br class="x_Apple-interchange-newline">
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="" style="word-wrap:break-word; line-break:after-white-space">
<div class="">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
<div dir="auto" class="" style="color:rgb(0,0,0); letter-spacing:normal; text-align:start; text-indent:0px; text-transform:none; white-space:normal; word-spacing:0px; text-decoration:none; word-wrap:break-word; line-break:after-white-space">
</div>
<br class="x_Apple-interchange-newline">
</div>
<br class="x_Apple-interchange-newline">
</div>
<br class="x_Apple-interchange-newline">
</div>
<br class="x_Apple-interchange-newline">
</div>
<br class="x_Apple-interchange-newline">
<br class="x_Apple-interchange-newline">
</div>
<br class="">
</div>
</body>
</html>