doc/guide/localhost/GoogleSummerOfCode2013

   1 <!DOCTYPE html>
   2 <html lang="en">
   3 <head>
   4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
   5 <meta name="generator" content="AsciiDoc 8.6.9">
   6 <title>Google Summer of Code (2013)</title>
   7 <link rel="stylesheet" href="./asciidoc.css" type="text/css">
   8 <link rel="stylesheet" href="./pygments.css" type="text/css">
   9
  10
  11 <script type="text/javascript" src="./asciidoc.js"></script>
  12 <script type="text/javascript">
  13 /*<![CDATA[*/
  14 asciidoc.install(2);
  15 /*]]>*/
  16 </script>
  17 <link rel="stylesheet" href="./mlton.css" type="text/css">
  18 </head>
  19 <body class="article">
  20 <div id="banner">
  21 <div id="banner-home">
  22 <a href="./Home">MLton 20180207</a>
  23 </div>
  24 </div>
  25 <div id="header">
  26 <h1>Google Summer of Code (2013)</h1>
  27 <div id="toc">
  28   <div id="toctitle">Table of Contents</div>
  29   <noscript><p><b>JavaScript must be enabled in your browser to display the table of contents.</b></p></noscript>
  30 </div>
  31 </div>
  32 <div id="content">
  33 <div class="sect1">
  34 <h2 id="_mentors">Mentors</h2>
  35 <div class="sectionbody">
  36 <div class="paragraph"><p>The following developers have agreed to serve as mentors for the 2013 Google Summer of Code:</p></div>
  37 <div class="ulist"><ul>
  38 <li>
  39 <p>
  40 <a href="http://www.cs.rit.edu/%7Emtf">Matthew Fluet</a>
  41 </p>
  42 </li>
  43 <li>
  44 <p>
  45 <a href="http://www.cse.buffalo.edu/%7Elziarek/">Lukasz (Luke) Ziarek</a>
  46 </p>
  47 </li>
  48 <li>
  49 <p>
  50 <a href="http://www.cs.purdue.edu/homes/suresh/">Suresh Jagannathan</a>
  51 </p>
  52 </li>
  53 </ul></div>
  54 </div>
  55 </div>
  56 <div class="sect1">
  57 <h2 id="_ideas_list">Ideas List</h2>
  58 <div class="sectionbody">
  59 <div class="sect2">
  60 <h3 id="_implement_a_partial_redundancy_elimination_pre_optimization">Implement a Partial Redundancy Elimination (PRE) Optimization</h3>
  61 <div class="paragraph"><p>Partial redundancy elimination (PRE) is a program transformation that
  62 removes operations that are redundant on some, but not necessarily all
  63 paths, through the program.  PRE can subsume both common subexpression
  64 elimination and loop-invariant code motion, and is therefore a
  65 potentially powerful optimization.  However, a na&iuml;ve
  66 implementation of PRE on a program in static single assignment (SSA)
  67 form is unlikely to be effective.  This project aims to adapt and
  68 implement the SSAPRE algorithm(s) of Thomas VanDrunen in MLton&#8217;s SSA
  69 intermediate language.</p></div>
  70 <div class="paragraph"><p>Background:</p></div>
  71 <div class="openblock">
  72 <div class="content">
  73 <div class="ulist"><ul>
  74 <li>
  75 <p>
  76 <a href="http://onlinelibrary.wiley.com/doi/10.1002/spe.618/abstract">Anticipation-based partial redundancy elimination for static single assignment form</a>; Thomas VanDrunen and Antony L. Hosking
  77 </p>
  78 </li>
  79 <li>
  80 <p>
  81 <a href="http://cs.wheaton.edu/%7Etvandrun/writings/thesis.pdf">Partial Redundancy Elimination for Global Value Numbering</a>; Thomas VanDrunen
  82 </p>
  83 </li>
  84 <li>
  85 <p>
  86 <a href="http://www.springerlink.com/content/w06m3cw453nphm1u/">Value-Based Partial Redundancy Elimination</a>; Thomas VanDrunen and Antony L. Hosking
  87 </p>
  88 </li>
  89 <li>
  90 <p>
  91 <a href="http://portal.acm.org/citation.cfm?doid=319301.319348">Partial redundancy elimination in SSA form</a>; Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow
  92 </p>
  93 </li>
  94 </ul></div>
  95 </div></div>
  96 <div class="paragraph"><p>Recommended Skills: SML programming experience; some middle-end compiler experience</p></div>
  97 </div>
  98 <div class="sect2">
  99 <h3 id="_design_and_implement_a_heap_profiler">Design and Implement a Heap Profiler</h3>
 100 <div class="paragraph"><p>A heap profile is a description of the space usage of a program.  A
 101 heap profile is concerned with the allocation, retention, and
 102 deallocation (via garbage collection) of heap data during the
 103 execution of a program.  A heap profile can be used to diagnose
 104 performance problems in a functional program that arise from space
 105 leaks.  This project aims to design and implement a heap profiler for
 106 MLton compiled programs.</p></div>
 107 <div class="paragraph"><p>Background:</p></div>
 108 <div class="openblock">
 109 <div class="content">
 110 <div class="ulist"><ul>
 111 <li>
 112 <p>
 113 <a href="http://portal.acm.org/citation.cfm?doid=583854.582451">GCspy: an adaptable heap visualisation framework</a>; Tony Printezis and Richard Jones
 114 </p>
 115 </li>
 116 <li>
 117 <p>
 118 <a href="http://journals.cambridge.org/action/displayAbstract?aid=1349892">New dimensions in heap profiling</a>; Colin Runciman and Niklas R&ouml;jemo
 119 </p>
 120 </li>
 121 <li>
 122 <p>
 123 <a href="http://www.springerlink.com/content/710501660722gw37/">Heap profiling for space efficiency</a>; Colin Runciman and Niklas R&ouml;jemo
 124 </p>
 125 </li>
 126 <li>
 127 <p>
 128 <a href="http://journals.cambridge.org/action/displayAbstract?aid=1323096">Heap profiling of lazy functional programs</a>; Colin Runciman and David Wakeling
 129 </p>
 130 </li>
 131 </ul></div>
 132 </div></div>
 133 <div class="paragraph"><p>Recommended Skills: C and SML programming experience; some experience with UI and visualization</p></div>
 134 </div>
 135 <div class="sect2">
 136 <h3 id="_garbage_collector_improvements">Garbage Collector Improvements</h3>
 137 <div class="paragraph"><p>The garbage collector plays a significant role in the performance of
 138 functional languages.  Garbage collect too often, and program
 139 performance suffers due to the excessive time spent in the garbage
 140 collector.  Garbage collect not often enough, and program performance
 141 suffers due to the excessive space used by the uncollected garbage.
 142 One particular issue is ensuring that a program utilizing a garbage
 143 collector "plays nice" with other processes on the system, by not
 144 using too much or too little physical memory.  While there are some
 145 reasonable theoretical results about garbage collections with heaps of
 146 fixed size, there seems to be insufficient work that really looks
 147 carefully at the question of dynamically resizing the heap in response
 148 to the live data demands of the application and, similarly, in
 149 response to the behavior of the operating system and other processes.
 150 This project aims to investigate improvements to the memory behavior of
 151 MLton compiled programs through better tuning of the garbage
 152 collector.</p></div>
 153 <div class="paragraph"><p>Background:</p></div>
 154 <div class="openblock">
 155 <div class="content">
 156 <div class="ulist"><ul>
 157 <li>
 158 <p>
 159 <a href="http://www.dcs.gla.ac.uk/%7Ewhited/papers/automated_heap_sizing.pdf">Automated Heap Sizing in the Poly/ML Runtime (Position Paper)</a>; David White, Jeremy Singer, Jonathan Aitken, and David Matthews
 160 </p>
 161 </li>
 162 <li>
 163 <p>
 164 <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4145125">Isla Vista Heap Sizing: Using Feedback to Avoid Paging</a>; Chris Grzegorczyk, Sunil Soman, Chandra Krintz, and Rich Wolski
 165 </p>
 166 </li>
 167 <li>
 168 <p>
 169 <a href="http://portal.acm.org/citation.cfm?doid=1152649.1152652">Controlling garbage collection and heap growth to reduce the execution time of Java applications</a>; Tim Brecht, Eshrat Arjomandi, Chang Li, and Hang Pham
 170 </p>
 171 </li>
 172 <li>
 173 <p>
 174 <a href="http://portal.acm.org/citation.cfm?doid=1065010.1065028">Garbage collection without paging</a>; Matthew Hertz, Yi Feng, and Emery D. Berger
 175 </p>
 176 </li>
 177 <li>
 178 <p>
 179 <a href="http://portal.acm.org/citation.cfm?doid=1029873.1029881">Automatic heap sizing: taking real memory into account</a>; Ting Yang, Matthew Hertz, Emery D. Berger, Scott F. Kaplan, and J. Eliot B. Moss
 180 </p>
 181 </li>
 182 </ul></div>
 183 </div></div>
 184 <div class="paragraph"><p>Recommended Skills: C programming experience; some operating systems and/or systems programming experience; some compiler and garbage collector experience</p></div>
 185 </div>
 186 <div class="sect2">
 187 <h3 id="_implement_successor_160_ml_language_features">Implement Successor&#160;ML Language Features</h3>
 188 <div class="paragraph"><p>Any programming language, including Standard&#160;ML, can be improved.
 189 The community has identified a number of modest extensions and
 190 revisions to the Standard&#160;ML programming language that would
 191 likely prove useful in practice.  This project aims to implement these
 192 language features in the MLton compiler.</p></div>
 193 <div class="paragraph"><p>Background:</p></div>
 194 <div class="openblock">
 195 <div class="content">
 196 <div class="ulist"><ul>
 197 <li>
 198 <p>
 199 <a href="http://successor-ml.org/index.php?title=Main_Page">Successor&#160;ML</a>
 200 </p>
 201 </li>
 202 <li>
 203 <p>
 204 <a href="http://www.mpi-sws.org/%7Erossberg/hamlet/index.html#successor-ml">HaMLet (Successor&#160;ML)</a>
 205 </p>
 206 </li>
 207 <li>
 208 <p>
 209 <a href="http://journals.cambridge.org/action/displayAbstract?aid=1322628">A critique of Standard&#160;ML</a>; Andrew W. Appel
 210 </p>
 211 </li>
 212 </ul></div>
 213 </div></div>
 214 <div class="paragraph"><p>Recommended Skills: SML programming experience; some front-end compiler experience (i.e., scanners and parsers)</p></div>
 215 </div>
 216 <div class="sect2">
 217 <h3 id="_implement_source_level_debugging">Implement Source-level Debugging</h3>
 218 <div class="paragraph"><p>Debugging is a fact of programming life.  Unfortunately, most SML
 219 implementations (including MLton) provide little to no source-level
 220 debugging support.  This project aims to add basic to intermediate
 221 source-level debugging support to the MLton compiler.  MLton already
 222 supports source-level profiling, which can be used to attribute bytes
 223 allocated or time spent in source functions.  It should be relatively
 224 straightforward to leverage this source-level information into basic
 225 source-level debugging support, with the ability to set/unset
 226 breakpoints and step through declarations and functions.  It may be
 227 possible to also provide intermediate source-level debugging support,
 228 with the ability to inspect in-scope variables of basic types (e.g.,
 229 types compatible with MLton&#8217;s foreign function interface).</p></div>
 230 <div class="paragraph"><p>Background:</p></div>
 231 <div class="openblock">
 232 <div class="content">
 233 <div class="ulist"><ul>
 234 <li>
 235 <p>
 236 <a href="http://mlton.org/HowProfilingWorks">MLton&#8201;&#8212;&#8201;How Profiling Works</a>
 237 </p>
 238 </li>
 239 <li>
 240 <p>
 241 <a href="http://mlton.org/ForeignFunctionInterfaceTypes">MLton&#8201;&#8212;&#8201;Foreign Function Interface Types</a>
 242 </p>
 243 </li>
 244 <li>
 245 <p>
 246 <a href="http://dwarfstd.org/">DWARF Debugging Standard</a>
 247 </p>
 248 </li>
 249 <li>
 250 <p>
 251 <a href="http://sourceware.org/gdb/current/onlinedocs/stabs/index.html">STABS Debugging Format</a>
 252 </p>
 253 </li>
 254 </ul></div>
 255 </div></div>
 256 <div class="paragraph"><p>Recommended Skills: SML programming experience; some compiler experience</p></div>
 257 </div>
 258 <div class="sect2">
 259 <h3 id="_simd_primitives">SIMD Primitives</h3>
 260 <div class="paragraph"><p>Most modern processors offer some direct support for SIMD (Single
 261 Instruction, Multiple Data) operations, such as Intel&#8217;s MMX/SSE
 262 instructions, AMD&#8217;s 3DNow!  instructions, and IBM&#8217;s AltiVec.  Such
 263 instructions are particularly useful for multimedia, scientific, and
 264 cryptographic applications.  This project aims to add preliminary
 265 support for vector data and vector operations to the MLton compiler.
 266 Ideally, after surveying SIMD instruction sets and SIMD support in
 267 other compilers, a core set of SIMD primitives with broad architecture
 268 and compiler support can be identified.  After adding SIMD primitives
 269 to the core compiler and carrying them through to the various
 270 backends, there will be opportunities to design and implement an SML
 271 library that exposes the primitives to the SML programmer as well as
 272 opportunities to design and implement auto-vectorization
 273 optimizations.</p></div>
 274 <div class="paragraph"><p>Background:</p></div>
 275 <div class="openblock">
 276 <div class="content">
 277 <div class="ulist"><ul>
 278 <li>
 279 <p>
 280 <a href="http://en.wikipedia.org/wiki/SIMD">SIMD</a>
 281 </p>
 282 </li>
 283 <li>
 284 <p>
 285 <a href="http://gcc.gnu.org/projects/tree-ssa/vectorization.html">Auto-vectorization in GCC</a>
 286 </p>
 287 </li>
 288 <li>
 289 <p>
 290 <a href="http://llvm.org/docs/Vectorizers.html">Auto-vectorization in LLVM</a>
 291 </p>
 292 </li>
 293 </ul></div>
 294 </div></div>
 295 <div class="paragraph"><p>Recommended Skills: SML programming experience; some compiler experience; some computer architecture experience</p></div>
 296 </div>
 297 <div class="sect2">
 298 <h3 id="_rtos_support">RTOS Support</h3>
 299 <div class="paragraph"><p>This project entails porting the MLton compiler to RTOSs such as:
 300 RTEMS, RT Linux, and FreeRTOS.  The project will include modifications
 301 to the MLton build and configuration process.  Students will need to
 302 extend the MLton configuration process for each of the RTOSs.  The
 303 MLton compilation process will need to be extended to invoke the C
 304 cross compilers the RTOSs provide for embedded support.  Test scripts
 305 for validation will be necessary and these will need to be run in
 306 emulators for supported architectures.</p></div>
 307 <div class="paragraph"><p>Recommended Skills: C programming experience; some scripting experience</p></div>
 308 </div>
 309 <div class="sect2">
 310 <h3 id="_region_based_memory_management">Region Based Memory Management</h3>
 311 <div class="paragraph"><p>Region based memory management is an alternative automatic memory
 312 management scheme to garbage collection.  Regions can be inferred by
 313 the compiler (e.g., Cyclone and MLKit) or provided to the programmer
 314 through a library.  Since many students do not have extensive
 315 experience with compilers we plan on adopting the later approach.
 316 Creating a viable region based memory solution requires the removal of
 317 the GC and changes to the allocator.  Additionally, write barriers
 318 will be necessary to ensure references between two ML objects is never
 319 established if the left hand side of the assignment has a longer
 320 lifetime than the right hand side.  Students will need to come up with
 321 an appropriate interface for creating, entering, and exiting regions
 322 (examples include RTSJ scoped memory and SCJ scoped memory).</p></div>
 323 <div class="paragraph"><p>Background:</p></div>
 324 <div class="openblock">
 325 <div class="content">
 326 <div class="ulist"><ul>
 327 <li>
 328 <p>
 329 Cyclone
 330 </p>
 331 </li>
 332 <li>
 333 <p>
 334 MLKit
 335 </p>
 336 </li>
 337 <li>
 338 <p>
 339 RTSJ + SCJ scopes
 340 </p>
 341 </li>
 342 </ul></div>
 343 </div></div>
 344 <div class="paragraph"><p>Recommended Skills: SML programming experience; C programming experience; some compiler and garbage collector experience</p></div>
 345 </div>
 346 <div class="sect2">
 347 <h3 id="_integration_of_multi_mlton">Integration of Multi-MLton</h3>
 348 <div class="paragraph"><p><a href="http://multimlton.cs.purdue.edu">MultiMLton</a> is a compiler and runtime
 349 environment that targets scalable multicore platforms.  It is an
 350 extension of MLton.  It combines new language abstractions and
 351 associated compiler analyses for expressing and implementing various
 352 kinds of fine-grained parallelism (safe futures, speculation,
 353 transactions, etc.), along with a sophisticated runtime system tuned
 354 to efficiently handle large numbers of lightweight threads.  The core
 355 stable features of MultiMLton will need to be integrated with the
 356 latest MLton public release.  Certain experimental features, such as
 357 support for the Intel SCC and distributed runtime will be omitted.
 358 This project requires students to understand the delta between the
 359 MultiMLton code base and the MLton code base.  Students will need to
 360 create build and configuration scripts for MLton to enable MultiMLton
 361 features.</p></div>
 362 <div class="paragraph"><p>Background</p></div>
 363 <div class="openblock">
 364 <div class="content">
 365 <div class="ulist"><ul>
 366 <li>
 367 <p>
 368 <a href="http://multimlton.cs.purdue.edu/mML/Publications.html">MultiMLton&#8201;&#8212;&#8201;Publications</a>
 369 </p>
 370 </li>
 371 </ul></div>
 372 </div></div>
 373 <div class="paragraph"><p>Recommended Skills: SML programming experience; C programming experience; some compiler experience</p></div>
 374 </div>
 375 </div>
 376 </div>
 377 </div>
 378 <div id="footnotes"><hr></div>
 379 <div id="footer">
 380 <div id="footer-text">
 381 </div>
 382 <div id="footer-badges">
 383 </div>
 384 </div>
 385 </body>
 386 </html>