doc/guide/src/GoogleSummerOfCode2014.adoc

   1 Google Summer of Code (2014)
   2 ============================
   3 :toc:
   4
   5 == Mentors ==
   6
   7 The following developers have agreed to serve as mentors for the 2014 Google Summer of Code:
   8
   9 * http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
  10 * http://www.cse.buffalo.edu/%7Elziarek/[Lukasz (Luke) Ziarek]
  11 * http://people.cs.uchicago.edu/~jhr/[John Reppy]
  12 * http://www.cs.purdue.edu/homes/chandras[KC Sivaramakrishnan]
  13 /////
  14 * http://www.cs.purdue.edu/homes/suresh/[Suresh Jagannathan]
  15 /////
  16
  17 == Ideas List ==
  18
  19 === Implement a Partial Redundancy Elimination (PRE) Optimization ===
  20
  21 Partial redundancy elimination (PRE) is a program transformation that
  22 removes operations that are redundant on some, but not necessarily all
  23 paths, through the program.  PRE can subsume both common subexpression
  24 elimination and loop-invariant code motion, and is therefore a
  25 potentially powerful optimization.  However, a na&iuml;ve
  26 implementation of PRE on a program in static single assignment (SSA)
  27 form is unlikely to be effective.  This project aims to adapt and
  28 implement the SSAPRE algorithm(s) of Thomas VanDrunen in MLton's SSA
  29 intermediate language.
  30
  31 Background:
  32 --
  33 * http://onlinelibrary.wiley.com/doi/10.1002/spe.618/abstract[Anticipation-based partial redundancy elimination for static single assignment form]; Thomas VanDrunen and Antony L. Hosking
  34 * http://cs.wheaton.edu/%7Etvandrun/writings/thesis.pdf[Partial Redundancy Elimination for Global Value Numbering]; Thomas VanDrunen
  35 * http://www.springerlink.com/content/w06m3cw453nphm1u/[Value-Based Partial Redundancy Elimination]; Thomas VanDrunen and Antony L. Hosking
  36 * http://portal.acm.org/citation.cfm?doid=319301.319348[Partial redundancy elimination in SSA form]; Robert Kennedy, Sun Chan, Shin-Ming Liu, Raymond Lo, Peng Tu, and Fred Chow
  37 --
  38
  39 Recommended Skills: SML programming experience; some middle-end compiler experience
  40
  41 /////
  42 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
  43 /////
  44
  45 === Design and Implement a Heap Profiler ===
  46
  47 A heap profile is a description of the space usage of a program.  A
  48 heap profile is concerned with the allocation, retention, and
  49 deallocation (via garbage collection) of heap data during the
  50 execution of a program.  A heap profile can be used to diagnose
  51 performance problems in a functional program that arise from space
  52 leaks.  This project aims to design and implement a heap profiler for
  53 MLton compiled programs.
  54
  55 Background:
  56 --
  57 * http://portal.acm.org/citation.cfm?doid=583854.582451[GCspy: an adaptable heap visualisation framework]; Tony Printezis and Richard Jones
  58 * http://journals.cambridge.org/action/displayAbstract?aid=1349892[New dimensions in heap profiling]; Colin Runciman and Niklas R&ouml;jemo
  59 * http://www.springerlink.com/content/710501660722gw37/[Heap profiling for space efficiency]; Colin Runciman and Niklas R&ouml;jemo
  60 * http://journals.cambridge.org/action/displayAbstract?aid=1323096[Heap profiling of lazy functional programs]; Colin Runciman and David Wakeling
  61 --
  62
  63 Recommended Skills: C and SML programming experience; some experience with UI and visualization
  64
  65 /////
  66 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
  67 /////
  68
  69 === Garbage Collector Improvements ===
  70
  71 The garbage collector plays a significant role in the performance of
  72 functional languages.  Garbage collect too often, and program
  73 performance suffers due to the excessive time spent in the garbage
  74 collector.  Garbage collect not often enough, and program performance
  75 suffers due to the excessive space used by the uncollected garbage.
  76 One particular issue is ensuring that a program utilizing a garbage
  77 collector "plays nice" with other processes on the system, by not
  78 using too much or too little physical memory.  While there are some
  79 reasonable theoretical results about garbage collections with heaps of
  80 fixed size, there seems to be insufficient work that really looks
  81 carefully at the question of dynamically resizing the heap in response
  82 to the live data demands of the application and, similarly, in
  83 response to the behavior of the operating system and other processes.
  84 This project aims to investigate improvements to the memory behavior of
  85 MLton compiled programs through better tuning of the garbage
  86 collector.
  87
  88 Background:
  89 --
  90 * http://www.dcs.gla.ac.uk/%7Ewhited/papers/automated_heap_sizing.pdf[Automated Heap Sizing in the Poly/ML Runtime (Position Paper)]; David White, Jeremy Singer, Jonathan Aitken, and David Matthews
  91 * http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4145125[Isla Vista Heap Sizing: Using Feedback to Avoid Paging]; Chris Grzegorczyk, Sunil Soman, Chandra Krintz, and Rich Wolski
  92 * http://portal.acm.org/citation.cfm?doid=1152649.1152652[Controlling garbage collection and heap growth to reduce the execution time of Java applications]; Tim Brecht, Eshrat Arjomandi, Chang Li, and Hang Pham
  93 * http://portal.acm.org/citation.cfm?doid=1065010.1065028[Garbage collection without paging]; Matthew Hertz, Yi Feng, and Emery D. Berger
  94 * http://portal.acm.org/citation.cfm?doid=1029873.1029881[Automatic heap sizing: taking real memory into account]; Ting Yang, Matthew Hertz, Emery D. Berger, Scott F. Kaplan, and J. Eliot B. Moss
  95 --
  96
  97 Recommended Skills: C programming experience; some operating systems and/or systems programming experience; some compiler and garbage collector experience
  98
  99 /////
 100 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
 101 /////
 102
 103 === Implement Successor{nbsp}ML Language Features ===
 104
 105 Any programming language, including Standard{nbsp}ML, can be improved.
 106 The community has identified a number of modest extensions and
 107 revisions to the Standard{nbsp}ML programming language that would
 108 likely prove useful in practice.  This project aims to implement these
 109 language features in the MLton compiler.
 110
 111 Background:
 112 --
 113 * http://successor-ml.org/index.php?title=Main_Page[Successor{nbsp}ML]
 114 * http://www.mpi-sws.org/%7Erossberg/hamlet/index.html#successor-ml[HaMLet (Successor{nbsp}ML)]
 115 * http://journals.cambridge.org/action/displayAbstract?aid=1322628[A critique of Standard{nbsp}ML]; Andrew W. Appel
 116 --
 117
 118 Recommended Skills: SML programming experience; some front-end compiler experience (i.e., scanners and parsers)
 119
 120 /////
 121 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
 122 /////
 123
 124 === Implement Source-level Debugging ===
 125
 126 Debugging is a fact of programming life.  Unfortunately, most SML
 127 implementations (including MLton) provide little to no source-level
 128 debugging support.  This project aims to add basic to intermediate
 129 source-level debugging support to the MLton compiler.  MLton already
 130 supports source-level profiling, which can be used to attribute bytes
 131 allocated or time spent in source functions.  It should be relatively
 132 straightforward to leverage this source-level information into basic
 133 source-level debugging support, with the ability to set/unset
 134 breakpoints and step through declarations and functions.  It may be
 135 possible to also provide intermediate source-level debugging support,
 136 with the ability to inspect in-scope variables of basic types (e.g.,
 137 types compatible with MLton's foreign function interface).
 138
 139 Background:
 140 --
 141 * http://mlton.org/HowProfilingWorks[MLton -- How Profiling Works]
 142 * http://mlton.org/ForeignFunctionInterfaceTypes[MLton -- Foreign Function Interface Types]
 143 * http://dwarfstd.org/[DWARF Debugging Standard]
 144 * http://sourceware.org/gdb/current/onlinedocs/stabs/index.html[STABS Debugging Format]
 145 --
 146
 147 Recommended Skills: SML programming experience; some compiler experience
 148
 149 /////
 150 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
 151 /////
 152
 153 === Region Based Memory Management ===
 154
 155 Region based memory management is an alternative automatic memory
 156 management scheme to garbage collection.  Regions can be inferred by
 157 the compiler (e.g., Cyclone and MLKit) or provided to the programmer
 158 through a library.  Since many students do not have extensive
 159 experience with compilers we plan on adopting the later approach.
 160 Creating a viable region based memory solution requires the removal of
 161 the GC and changes to the allocator.  Additionally, write barriers
 162 will be necessary to ensure references between two ML objects is never
 163 established if the left hand side of the assignment has a longer
 164 lifetime than the right hand side.  Students will need to come up with
 165 an appropriate interface for creating, entering, and exiting regions
 166 (examples include RTSJ scoped memory and SCJ scoped memory).
 167
 168 Background:
 169 --
 170 * Cyclone
 171 * MLKit
 172 * RTSJ + SCJ scopes
 173 --
 174
 175 Recommended Skills: SML programming experience; C programming experience; some compiler and garbage collector experience
 176
 177 /////
 178 Mentor: http://www.cse.buffalo.edu/%7Elziarek/[Lukasz (Luke) Ziarek]
 179 /////
 180
 181 === Integration of Multi-MLton ===
 182
 183 http://multimlton.cs.purdue.edu[MultiMLton] is a compiler and runtime
 184 environment that targets scalable multicore platforms.  It is an
 185 extension of MLton.  It combines new language abstractions and
 186 associated compiler analyses for expressing and implementing various
 187 kinds of fine-grained parallelism (safe futures, speculation,
 188 transactions, etc.), along with a sophisticated runtime system tuned
 189 to efficiently handle large numbers of lightweight threads.  The core
 190 stable features of MultiMLton will need to be integrated with the
 191 latest MLton public release.  Certain experimental features, such as
 192 support for the Intel SCC and distributed runtime will be omitted.
 193 This project requires students to understand the delta between the
 194 MultiMLton code base and the MLton code base.  Students will need to
 195 create build and configuration scripts for MLton to enable MultiMLton
 196 features.
 197
 198 Background
 199 --
 200 * http://multimlton.cs.purdue.edu/mML/Publications.html[MultiMLton -- Publications]
 201 --
 202
 203 Recommended Skills: SML programming experience; C programming experience; some compiler experience
 204
 205 /////
 206 Mentor: http://www.cse.buffalo.edu/%7Elziarek/[Lukasz (Luke) Ziarek]
 207 /////
 208
 209 === Concurrent{nbsp}ML Improvements ===
 210
 211 http://cml.cs.uchicago.edu/[Concurrent ML] is an SML concurrency
 212 library based on synchronous message passing.  MLton has a partial
 213 implementation of the CML message-passing primitives, but its use in
 214 real-world applications has been stymied by the lack of completeness
 215 and thread-safe I/O libraries.  This project would aim to flesh out
 216 the CML implementation in MLton to be fully compatible with the
 217 "official" version distributed as part of SML/NJ.  Furthermore, time
 218 permitting, runtime system support could be added to allow use of
 219 modern OS features, such as asynchronous I/O, in the implementation of
 220 CML's system interfaces.
 221
 222 Background
 223 --
 224 * http://cml.cs.uchicago.edu/
 225 * http://mlton.org/ConcurrentML
 226 * http://mlton.org/ConcurrentMLImplementation
 227 --
 228
 229 Recommended Skills: SML programming experience; knowledge of concurrent programming; some operating systems and/or systems programming experience
 230
 231 /////
 232 Mentor: http://people.cs.uchicago.edu/~jhr/[John Reppy]
 233 Mentor: http://www.cs.rit.edu/%7Emtf[Matthew Fluet]
 234 /////
 235
 236 /////
 237 === SML3d Development ===
 238
 239 The SML3d Project is a collection of libraries to support 3D graphics
 240 programming using Standard ML and the http://opengl.org/[OpenGL]
 241 graphics API. It currently requires the MLton implementation of SML
 242 and is supported on Linux, Mac OS X, and Microsoft Windows. There is
 243 also support for http://www.khronos.org/opencl/[OpenCL].  This project
 244 aims to continue development of the SML3d Project.
 245
 246 Background
 247 --
 248 * http://sml3d.cs.uchicago.edu/
 249 --
 250
 251 Mentor: http://people.cs.uchicago.edu/~jhr/[John Reppy]
 252 /////