Skip to content

Instantly share code, notes, and snippets.

@jkoenen

jkoenen/ryg_papers_01.md

Last active January 28, 2021 12:34
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jkoenen/589451c1cc399f71e42b41767ecbe04e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jkoenen/589451c1cc399f71e42b41767ecbe04e to your computer and use it in GitHub Desktop.
Download ZIP
Fabians list of great papers 1/N
Raw
ryg_papers_01.md
  1. Let's start meta: Lamport-State the Problem Before Describing the Solution (1978). https://www.microsoft.com/en-us/research/publication/state-problem-describing-solution/ … 1-page memo. Read it.
  2. Herlihy-"Wait-free synchronization" http://www.diku.dk/OLD/undervisning/2005f/dat-os/skrifter/lockfree.pdf …. Truly seminal. Lucid + enough good ideas for 4 papers easily.
  3. Cook-"How complex systems fail" (1998) https://www.researchgate.net/profile/Richard_Cook3/publication/228797158_How_complex_systems_fail/links/0c96053410db96a89c000000.pdf … 4 pages that anyone working on/with complex systems should read.
  4. Moffat, Turpin-"On the Implementation of Minimum Redundancy Prefix Codes" (1997) https://pdfs.semanticscholar.org/bda3/442cc6b1d10e4b36b574af0a34a668492230.pdf … Much has been written about Huffman coding, a lot of it wrong. Almost everything worth knowing is in this (short!) paper.
  5. Dybvig, Hieb, Butler-"Destination-Driven Code Generation" (1990) https://pdfs.semanticscholar.org/dcb8/8719880e1f76ad71fb1c5aebb118e2ecfe71.pdf … A simple, beautiful way to improve code gen for fast one-pass compilers. 5b. Milliken-"One-pass Code Generation in V8" (year?) http://cs.au.dk/~mis/dOvs/slides/46b-codegeneration-in-V8.pdf … makes a great companion piece.
  6. Valmari-"Fast brief practical DFA minimization" (2012) http://www.cs.cmu.edu/~./cdm/pdf/Valmari12.pdf … Takes a classic algorithm by Hopcroft that textbooks struggled to explain (or mostly omitted entirely) for decades, and simplifies it down to a (not particularly technical) 5-page paper.
  7. Sarnak, Tarjan-"Planar Point Location Using Persistent Search Trees" (1986) http://users.cs.fiu.edu/~giri/teach/6405/s04/SarnakTarjanCACM86.pdf … an interesting problem in its own right, and this paper solves it by introducing persistent search trees made efficient using a beautiful idea (section 3!).
  8. Porter, Duff-"Compositing Digital Images" (1984) https://keithp.com/~keithp/porterduff/p253-porter.pdf … Obligatory mention. Every half-year or so, another blog post crosses my timeline where someone excitedly sings the praises of premultiplied alpha. We need to get better about teaching this.
  9. Brandt-"Hard Sync Without Aliasing" (2001) http://elthariel.free.fr/ebooks/icmc01-hardsync.pdf … Introducing MinBLEPs for bandlimited synthesis. Such an awesome idea!
  10. Veach-"Robust Monte Carlo Methods for Light Transport Simulation" (PhD thesis, 1997) http://graphics.stanford.edu/papers/veach_thesis/ … wherein he invents a big chunk of modern light transport sim. A tour de force.
  11. Goto, van de Geijn-"Anatomy of high-performance matrix multiplication" (2008) http://www.cs.utexas.edu/~flame/pubs/GotoTOMS_revision.pdf … - how a high-perf GEMM works.
  12. Chazelle-"Filtering search: a new approach to query-answering" (1986) https://www.cs.princeton.edu/~chazelle/pubs/FilteringSearch.pdf … - balancing preprocessing and query time, as applied to several geometric search problems. Not exactly easy reading but worth your time!
  13. McIllroy-"A Killer Adversary for Quicksort" (1999) https://pdfs.semanticscholar.org/dd00/6b6383bd512c7645d8408fa6c97875c27318.pdf … - how to do adversarial testing right. Worth studying!
  14. Knuth-"Structured Programming with go to Statements" (1974) https://sbel.wisc.edu/Courses/ME964/Literature/knuthProgramming1974.pdf … - oft-quoted, rarely read. It may surprise you.
  15. Bryant-"Graph-Based Algorithms for Boolean Function Manipulation" (1986) http://mtv.ece.ucsb.edu/courses/ece156B_14/randy_obdd86.pdf … - introducing ROBDDs and kickstarting a revolution in formal ASIC verification in the process.
  16. Donoghue et al.-"Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding" (2016) http://stanford.edu/~boyd/papers/scs.html …a great example of good theory making for an elegant, practical algorithm.
  17. Braun et al.-"Simple and Efficient Construction of Static Single Assignment Form" (2013) http://pp.ipd.kit.edu/uploads/publikationen/braun13cc.pdf … There are many SSA construction algorithms; this is the slickest one I know.
  18. Lamport, Palais-"On the Glitch Phenomenon" (1976) http://lamport.azurewebsites.net/pubs/pubs.html#glitch … - arbitration is hard. Read Lamport's notes on it too!
  19. Curtsinger, Berger-"Stabilizer: Statistically sound performance evaluation" (2013) http://people.cs.umass.edu/~emery/pubs/stabilizer-asplos13.pdf- … on how the ubiquity of address-indexed caches distorts program performance measurements, and what to do about it.
  20. Tomasulo-"An efficient algorihm for exploiting multiple arithmetic units" (1967) http://www.ece.umd.edu/class/enee646.F2014/Tomasulo.PDF … - to my knowledged, the first Out of Order execution implementation that actually shipped - and applied to a small enough problem that it's easy to understand.
  21. Wilson, Johnstone, Neely, Boles - "Dynamic storage allocation: A survey and critical review" (1995) http://www-2.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15213-f98/doc/dsa.pdf … Knuth got this one wrong.
  22. Meyer, Tischer-"GLICBAWLS" (2001) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.131.4042&rep=rep1&type=pdf … Two Aussies make a dirty joke for an IOCCC entry, accidentally develop a fairly competitive lossless image coder in the process. It happens.
  23. Hutton et al.-"Improving FPGA Performance and Area Using an Adaptive Logic Module" (2004) http://www2.engr.arizona.edu/~ece506/readings/project-reading/6-cad/altera-alm.pdf … Mainly geekery for me; feel free to skip this one if you're not interested in FPGA arch, I just thought it was really cool when I first saw it! (2010 or so)
  24. O'Neill-"PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation" (2014)http://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf … Introduces a new, pretty cool RNG and makes for a great introduction to the topic in general.
  25. Cook, Podelski, Rybalchenko-"Termination Proofs for Systems Code" http://homedirs.ccs.neu.edu/wahl/Teaching/Software-Model-Checking/2016-Spring/Papers/termination.pdf … The Halting Problem: SOLVED!* *for a limited but very practically relevant class of programs; e.g. device drivers.
  26. O'Neill - "The Genuine Sieve of Eratosthenes" (2009) https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf … The standard example implementation as a pure functional program is not, in fact, the same algorithm, and it's very instructive to see how it fails.
  27. Qureshi, Jaleel et al. - "Adaptive Insertion Policies for High Performance Caching" (2007) http://web.ece.ucdavis.edu/~anhttran/files/download/caching/ISCA-2007-Qureshi-SetDuelingControl.pdf … - this is a HW paper, but the design principles here have been a great inspiration for me in designing adaptive algs in SW.
  28. Thompson-"Reflections on Trusting Trust" (1984 Turing Award lecture) https://www.cs.colorado.edu/~jrblack/class/csci6268/s14/p761-thompson.pdf … a classic. If you haven't read it, do so!
  29. Dijkstra, Lamport et. al-"On-the-fly Garbage Collection: an Exercise in Cooperation" (1978) http://lamport.azurewebsites.net/pubs/garbage.pdf … introducing tri-color marking. No matter where you stand on GC, this is well worth reading.
  30. Lamport-"Multiple Byte Processing with Full-Word Instructions" (1975) http://lamport.azurewebsites.net/pubs/multiple-byte.pdf … I thought I wouldn't need to do this
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment