Check out my first novel, midnight's simulacra!

UNIX Weapons School Weekplan

From dankwiki
Revision as of 14:59, 9 April 2013 by Dank (talk | contribs) (→‎Week 5.1)

This syllabus is TENTATIVE! It covers only lecture material, not the design meetings.


Summary

  • Week 1: C/C++ development in the x86 UEFI UNIX environment
  • Week 2: Systems methods for efficient use of memory and buses
  • Week 3: Algorithmic methods for efficient use of CPU and memory
  • Week 4: Compilers and their limitations, both theoretical and practical
  • Week 5: Parallelism I: Hardware parallelism
  • Week 6: Parallelism II: Software parallelism
  • Week 7: Effective use of intranets and the Internet
  • Week 8: Debugging, dynamic work loads, and pathological behaviors
  • Week 9: C++11, heterogeneity, and the future of systems programming

Week 1

  • SHELL LIFE aka Things I Hope You Already Know
    • Job control
    • GNU readline
    • SSH tricks
    • effective use of interactive shells
    • shell scripting idioms.
  • HOW COAL BECOMES CAT PICTURES aka Attack of the clone()s
    • UEFI. UNIX boot sequence.
    • Everything you wanted to know about /dev and /sys and /proc but never found out.
    • Where a process comes from, what composes it while alive, and where it goes when it dies.
    • lsof, netstat, memstat, etc
  • C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
    • Highlights of GCC, G++, LLVM, Clang, ICC, and NVCC.
    • strace, ltrace, ptrace().
    • GDB tricks.
    • Profiling with perf.
    • UNIX resource management.
    • Linker tricks both stupid and less stupid.
    • The C and C++ machine models.
  • OUR EARTH MOTHERS aka C/C++
    • The system call interface.
    • Process-level memory management.
    • The C standard library.
    • The STL.
    • A glimpse of template metaprogramming

Week 2

  • YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
    • Intel Core processors.
    • The memory hierarchy.
    • Branch prediction.
    • SIMD.
    • Memory fences.
    • Transactional memory.
    • Predication.
  • DOUBLE-COPIED I/O aka Definitely More Copying Than Required.
    • C/C++ I/O using stdio.h and streams. Interactions of standard library buffering and I/O.
    • Semantics and side-effects of the I/O model.
    • popen() and the seven thousand ways it can be incorrectly used.
  • SINGLE-COPIED I/O aka Not Good Enough, Try Again.
    • UNIX I/O using bytestreams, datagrams, and sequenced packets.
    • The AF_UNIX namespace.
    • That mysterious EAGAIN.
  • ZERO-COPY I/O aka Now We're Getting Somewhere.
    • Mmap and shared memory.
    • CLONE_VM and a glimpse of threads.
    • RDMA. The PCIe bus.
  • NEGATIVE-COPY I/O aka Oh Shit! There Go My Pages!
    • COW games.
    • sendfile() and TCP.
    • splice() your way to success.
  • MORE MEMORY aka When in Doubt, Blame Memory.
    • Interactions of disk, disk paging, memory paging, caching, registers, and multiprocessing.
    • Memory characteristics of long-lived programs.
    • Life in a post-paged world.
    • Computational memory.
    • NUMA and you.

Week 3

  • IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
  • Searching small spaces: Constant sorts. Dancing links.
  • Searching large spaces: Trees for smoking and computing. PATRICIA tries. Skip lists. Suffix trees. Automata search.
  • Searching by content: Hashes for smoking and computing. Algorithmic complexity attacks. Universal hashes. Cuckoo hashing. Adaptive perfect hashes.
  • Searching huge spaces: VLRU. Octet and quadtrees. Enumeration by method of linear congruence and other space-filling parlor tricks.
  • Real-time machine learning: Support vector machines. Non-negative matrix factorization. Hierarchal hashing. Hidden Markov models.
  • Three impossible things before breakfast: Detecting an infinite loop, transforming an infinite list, and computing without executing.
  • Yes, You Really Have to Learn Fourier Transforms.

Week 4

  • SSA, aka Planet of the Compilers
  • The Banerjee Test and the Polyhedral Model, aka Beneath the Planet of the Compilers
  • The limits of compiler-based optimization, aka Escape from the Planet of the Compilers
  • Inline assembly, aka Conquest of the Planet of the Compilers
  • PGO and Genetic-O aka Battle for the Planet of the Compilers

Week 5.1

  • Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
  • Libraries: objdump, nm, and how to design a shared library.
  • Unpleasant Details of the UNIX Environment aka What Stevens Forgot to Tell You.
    • The OOM killer.
    • Atime.
    • Fragmentation, a spectre haunting your userspace.
    • Hardware failures.
  • Build systems aka They're All Shite

Week 5.2

  • Bit-level parallelism
  • Parallelism within a register
  • Parallelism among instructions
  • Parallelism among memory accesses

Week 6

  • Parallelism among tasks
  • Algorithms simulating parallelism and nondeterminism.
  • POSIX threads. Userspace threading. Coroutines.
  • Parallel languages and libraries. IPP and TBB.

Week 7

  • The Linux virtual memory implementation on x86
  • The FreeBSD/Dragonfly virtual memory implementation
  • The Linux process schedulers
  • The Linux I/O schedulers
  • Queueing theory of Kleinrock. The Linux packet queue disciplines
  • The Internet backbone. Preserving service via anycast networking.
   Threats to the Internet. PMTUD / MSS black holes.
  • Bufferbloat. Perils of the end-user network. Hardware design of

fast networking devices. The CODEL queue discipline.

  • IPv6. Algorithms for IPv6. Zeroconf. PXE. Ad-hoc and mesh networking.

Algorithms for fragmentation and sequencing. Intranet threats.