UC Santa Cruz

Tuesdays at 12:30 pm (bring your own lunch)

Email list: http://www.soe.ucsc.edu/mailman/listinfo/proglang

• October 9
  • Discussion of possible topics
• October 16: No Free Lunch
  • Feedback directed implicit parallelism. T Harris, S Singh. ICFP 2007.
• October 23: Commutativity
  • Commutativity analysis: a new analysis framework for parallelizing compilers. MC Rinard, PC Diniz. PLDI 1996.
  • Optimistic Parallelism Requires Abstractions. M Kulkarni, K Pingali, B Walter, G Ramanarayanan, K Bala, LP Chew. PLDI 2007.
• October 30: Cost Models
  • Exploiting Purely Functional Programming to Obtain Bounded Resource Behaviour: the Hume Approach. CEFP 2005.
  • Questions and Answers about BSP. D Skillicorn, JMD Hill, WF McColl. Tech Report 1996.
  • (Optional) A Parallel Complexity Model for Functional Languages. G Blelloch, J Greiner. Tech Report 1994.
  • (Optional) A Compiler Cost Model for Speculative Parallelization. J Dou, M Cintra. TACO 2007.
• November 6: Morphisms this and morphisms that
  • Sorting Morphisms. L Augusteijn. AFP 1998.
  • Fold and Unfold for Program Semantics. G Hutton. ICFP 1998.
  • (Optional and brief background in sections 1 and 2) Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire. E Meijer, M Fokkinga, R Paterson. FPCA 1991.
• November 13: ZPL
  • The high-level parallel language ZPL improves productivity and performance. BL Chamberlain, SE Choi, SJ Deitz, L Snyder. P-PHEC 2004.
  • Abstractions for dynamic data distribution. SJ Deitz, BL Chamberlain, L Snyder HIP 2004.
  • (Optional) High-level language support for user-defined reductions. SJ Deitz, BL Chamberlain, L Snyder. Supercomputing 2002.
  • (Optional) A Comic Book Introduction to ZPL.
• November 20: JITing
  • HotpathVM: an effective JIT compiler for resource-constrained devices. A Gal, CW Probst, M Franz. VEE 2006
  • The Jrpm System for Dynamically Parallelizing Java Programs. MK Chen, K Olukotun. ISCA 2003.
• November 27: Nested Data-Parallelism in NESL and Haskell
  • More Types for Nested Data Parallel Programming. MMT Chakravarty, G Keller. ICFP 2000.
  • Data Parallel Haskell: A status report. M Chakravarty, R Leshchinskiy, SP Jones, G Keller, S Marlow. DAMP 2007.
  • (Optional) Higher Order Flattening. R Leshchinskiy, MMT Chakravarty, G Keller. PAPP 2006
  • (Optional) Implementation of a portable nested data-parallel language. G Blelloch, J Hardwick, S Chatterjee, J Sipelstein, M Zagha. PPoPP 1993
• December 4: Parallelism at POPL:
  • Contextual Effects for Version-Consistent Dynamic Software Updating and Safe Concurrent Programming. I Neamtiu, M Hicks, JS Foster, P Pratikakis. POPL 2008.
  • http://research.microsoft.com/~tharris/papers/2008-popl.pdfSemantics of Transactional Memory and Automatic Mutual Exclusion. M Abadi, A Birrell, T Harris, M Isard. POPL 2008.
  • High-Level Small-Step Operational Semantics for Transactions. KF Moore, D Grossman. POPL 2008.
• Sequoia and the memory hierarchy
  • Sequoia: Programming the Memory Hierarchy. K Fatahalian, TJ Knight, M Houston, M Erez, DR Horn, L Leem, JY Park, M Ren, A Aiken, WJ Dally, P Hanrahan. CS 2006.
  • Cache-Oblivious Algorithms. M Frigo, CE Leiserson, H Prokop, S Ramachandran. FOCS 1999.
  • (Optional) Compilation for Explicitly Managed Memory Hierarchies. TJ Knight, JY Park, M Ren, M Houston, M Erez, K Fatahalian, A Aiken, WJ Dally, Pat Hanrahan. PPoPP 2007.
• Tiling
  • Effective Automatic Parallelization of Stencil Computations
  • Parameterized Tiled Loops for Free
• JIT
  • Online Optimizations Driven by Hardware Performance Monitoring
• List Homomorphism Theory
  • The Third Homomorphism Theorem
  • Automatic Inversion Generates Divide-and-Conquer Parallel Programs
• Enforcing Isolation and Ordering in STM
• Automatically Classifying Benign and Harmful Data Races Using Replay Analysis
• Software Behavior Oriented Parallelization
• Misc pages on parallel stuff
  • http://research.microsoft.com/~simonpj/Papers/papers.html#parallel
  • http://www.cs.cmu.edu/~guyb/pubs.html
  • http://cm.bell-labs.com/who/girija/pubs.html
  • http://www.haskell.org//pipermail/haskell/2005-January/015198.html
• Links to the 253 class
  • http://www.cse.unsw.edu.au/~chak/papers/CLPKM07.html
  • http://www.di.ens.fr/~goubault/index1.html
  • Automatic Inversion Generates Divide-and-Conquer Parallel Programs. K Morita, A Morihata, K Matsuzaki, Z Hu, M Takeichi. PLDI 2007.
• Accessible classics
  • The Essence of Functional Programming
  • From System F to Typed Assembly Language (or possibly Chlipala PLDI 2007's new version of the same idea)
  • Theorems for free!
  • Functional programming w/ bananas, lenses, and barbed wire
  • Scrap your boilerplate

Below is a dumping ground of topics and papers that have accumulated for a while. Any of this could surface in the reading group.

• Computing Procedure Summaries for Interprocedural Analysis. S Gulwani, A Tiwari.
• Concurrency
  • The continuing saga of compilers which prove or are proved correct
    • http://research.microsoft.com/research/pubs/view.aspx?0rc=p&type=technical+report&id=1273
    • http://lambda-the-ultimate.org/node/1232
    • http://lambda-the-ultimate.org/node/2146
    • http://lambda-the-ultimate.org/node/2171
• Algorithms and Complexity
  • From Fast Exponentiation to Square Matrices: An Adventure in Types. C Okasaki. ICFP 1999.
  • Adventures In Time and Space. N Danner, J Royer. POPL 2006.
  • A Dependently Typed Framework For Static Analysis Of Program Execution Costs. E Brady, K Hammond. IFL 2005.
  • http://swiss.csail.mit.edu/~adams/BB/
  • Stuff from Guy Blelloch and Chris Okasaki
• Security
  • Authenticity by typing for security protocols. AD Gordon. JCS 2003.
  • Types and effects for asymmetric cryptographic protocols. AD Gordon. JCS 2004.
  • http://www.cs.ucla.edu/~palsberg/tba/papers/hofmann-njc00.pdf
• Abstract Interpretation
• Garbage Collection
• Optimization
• Computer Algebra Systems (Languages to host mathematics more than “user” programs)
• Aspect-Oriented Programming
• Fixes for C
  • Modular Information Hiding and Type-Safe Linking for C. S Srivastava, M Hicks, J Foster. TLDI 2007.
• Fun with Types (and Category Theory!)
  • Inferring Type Isomorphisms Generically. F Atanassow, J Jeuring. MPC '04
• Typed Assembly Language
• Modules and Linking
  • Program fragments, linking, and modularization. L Cardelli. POPL 1997
  • From Structures and Functors to Modules and Units. S Owens, M Flatt. ICFP 2006
  • A Calculus for Dynamic Linking. D Ancona, S Fagorzi, E Zucca. ICTCS '03
  • A Calculus for Link-time Compilation. E Machkasova, F Turbak. ESOP '00

Some Real-time testing reads:

• Online On-the-Fly Testing of Real-Time Systems
• Automated Test Generation from Timed Automata