dankwiki

UNIX Weapons School Weekplan: Difference between revisions

← Older edit

Dank (talk | contribs)

2 user groups
11,302 edits
 
(57 intermediate revisions by the same user not shown)
Line 1: Line 1:
This syllabus is '''''TENTATIVE!''''' It covers only lecture material, not the design meetings.
==Week 1: C/C++ development in the x86 UNIX environment==
__NOTOC__
 
==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
* SHELL LIFE aka Things I Hope You Already Know
Line 22: Line 7:
** effective use of interactive shells
** effective use of interactive shells
** shell scripting idioms.
** shell scripting idioms.
** rant: code is data and data is code so keep your home directory in source control
* HOW COAL BECOMES CAT PICTURES aka Attack of the clone()s
* HOW COAL BECOMES CAT PICTURES aka Attack of the clone()s
** UEFI. UNIX boot sequence.
** UEFI. UNIX boot sequence.
Line 28: Line 14:
** lsof, netstat, memstat, etc
** lsof, netstat, memstat, etc
* C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
* C/C++ UNIX DEVELOPMENT aka Onward Christian Soldiers
** Highlights of GCC, G++, LLVM, Clang, ICC, and NVCC.
** Highlights of [[GCC]], G++, LLVM, Clang, ICC, and NVCC.
** [[GNU Make]]
** strace, ltrace, ptrace().
** strace, ltrace, ptrace().
** GDB tricks.
** GDB tricks.
Line 35: Line 22:
** Linker tricks both stupid and less stupid.
** Linker tricks both stupid and less stupid.
** The C and C++ machine models.
** The C and C++ machine models.
* THE WORLD FATHER aka UNIX
** The Linux virtual memory implementation on x86
** The FreeBSD/Dragonfly virtual memory implementation
** The Linux process schedulers
** The Linux I/O schedulers
* OUR EARTH MOTHERS aka C/C++
* OUR EARTH MOTHERS aka C/C++
** The system call interface.
** The system call interface.
** Process-level memory management.
** Process-level memory management.
** The C standard library.
** The C standard library.
** The STL.
** [[X Macros|Xmacros]] / The STL.
** A glimpse of template metaprogramming
** A glimpse of template metaprogramming


==Week 2==
==Week 2: Systems methods for efficient use of memory and buses==


* YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
* YOUR FRIEND THE COMPUTER aka Computer Architecture in Thirty Minutes.
Line 48: Line 40:
**The memory hierarchy.
**The memory hierarchy.
** Branch prediction.
** Branch prediction.
** SIMD.
** [[SIMD]].
** Memory fences.
** Memory fences.
** Transactional memory.
** Transactional memory.
Line 62: Line 54:
* ZERO-COPY I/O aka Now We're Getting Somewhere.
* ZERO-COPY I/O aka Now We're Getting Somewhere.
** Mmap and shared memory.
** Mmap and shared memory.
** TLB invalidation and IPIs
** CLONE_VM and a glimpse of threads.  
** CLONE_VM and a glimpse of threads.  
** RDMA. The PCIe bus.
** RDMA. The PCIe bus.
Line 75: Line 68:
** NUMA and you.
** NUMA and you.


==Week 3==
==Week 3: Algorithmic methods for efficient use of CPU and memory==


* IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
* IN THE GRIM FUTURE OF WEEK 3 THERE ARE NO AKAs, ONLY ALGORITHMS
* Searching small spaces: Constant sorts. Dancing links.
* Searching small spaces: Constant sorts (sorting networks). Dancing links. Timer wheels.
* Searching large spaces: Trees for smoking and computing. PATRICIA tries. Skip lists. Suffix trees. Automata search.
* Searching large spaces: Trees. PATRICIA tries. Skip lists. Suffix trees. Automata search. Interval trees.
* Searching by content: Hashes for smoking and computing. Algorithmic complexity attacks. Universal hashes. Cuckoo hashing. Adaptive perfect hashes.
* Searching by content: Hashes. 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.
* Searching huge spaces: [[VLHU]]. 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.
* 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.
* 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.
* Yes, You Really Have to Learn Fourier Transforms.
===Algorithms for event systems===
* select(), poll(), interaction with signals
* Linux's epoll, FreeBSD's kqueue. Level- vs edge-triggered events.
** Algorithms for oneshot edge-triggered interfaces. Asynchronous I/O on POSIX systems.
* Everything as events: timerfd, signalfd, V_NODE
* Wrapping pthread events. Multithreaded event engines. Work queues, work stealing, tasklets.
** Digression: Kernel threads and interrupt handlers
* Robust systems and judicious fork()ing
* libev, libevent, libtorque


==Week 4==
==Week 4: [[Compiler Design|Compilers]] and their limitations==


* SSA, aka Planet of the Compilers
* SSA and Basic Blocks, aka Planet of the Compilers
* The Banerjee Test and the Polyhedral Model, aka Beneath the 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
* The limits of compiler-based optimization, aka Escape from the Planet of the Compilers
Line 94: Line 96:
* PGO and Genetic-O aka Battle for the Planet of the Compilers
* PGO and Genetic-O aka Battle for the Planet of the Compilers


==Week 5.1==
==Week 5==
===Allotrios===
* Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
* Windows aka Unfathomably Wretched Function Naming: I/O Completion Ports. With Fibers come Heaps.
* Libraries: objdump, nm, and how to design a shared library.
* Libraries: objdump, nm, and how to design a shared library.
* Internationalization. UTF8
* Unpleasant Details of the UNIX Environment aka What Stevens Forgot to Tell You.
* Unpleasant Details of the UNIX Environment aka What Stevens Forgot to Tell You.
** The OOM killer.
** The OOM killer.
Line 104: Line 108:
** Hardware failures.
** Hardware failures.
* Build systems aka They're All Shite
* Build systems aka They're All Shite
===Parallelism I: Hardware Parallelism===
* Models of parallelism aka They're All Shite
* Models of parallelism aka They're All Shite
==Week 5.2==
* Bit-level parallelism
* Bit-level parallelism
* Parallelism within a register
* Parallelism within a register
Line 113: Line 116:
* Parallelism among memory accesses
* Parallelism among memory accesses


==Week 6==
==Week 6: Parallelism II: Software Parallelism==


* Parallelism among tasks
* Parallelism among tasks
* Algorithms simulating parallelism and nondeterminism.
* Algorithms simulating parallelism and nondeterminism.
* POSIX threads. Userspace threading. Coroutines.
* [[Pthreads|POSIX threads]]. Userspace threading. Coroutines.
* Parallel languages and libraries. IPP and TBB.
* Parallel languages and libraries. IPP and TBB.


==Week 7==
==Week 7: Effective use of intranets and the Internet==
* Sampling theory of Nyquist
* 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 and CAKE queue disciplines.
* IPv6. Algorithms for IPv6. Zeroconf. PXE. Ad-hoc and mesh networking. Algorithms for fragmentation and sequencing. Intranet threats.
* [[Packet sockets]]. Linux's netlink(7).
* Local topology discovery
 
==Week 8: Heterogeneity==
===Hardware===
* TCP offload engines
* SolarFlare's OpenPacket
* Microsoft AMP
* NVIDIA's [[CUDA]]
* OpenCL
 
===Software===
* System / guest emulation
* Transmeta CMS (Code Morphing Software)
* Popek and Goldberg virtualization requirements / KVM / Xen


* The Linux virtual memory implementation on x86
==Week 9: The future of systems programming==
* The FreeBSD/Dragonfly virtual memory implementation
* C++11
* The Linux process schedulers
* Amorphous computing
* The Linux I/O schedulers
* RAIN/RAIM, EMC-aware programming
* Queueing theory of Kleinrock. The Linux packet queue disciplines
* COMA, ccNUMA, directories, SCI, SCA
* The Internet backbone. Preserving service via anycast networking.
* Computational memory
    Threats to the Internet. PMTUD / MSS black holes.
* Software-defined networking
* Bufferbloat. Perils of the end-user network. Hardware design of
* MRAM / FeRam / PRAM / SONOS
    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.
Retrieved from "https://nick-black.com/dankwiki/index.php?title=UNIX_Weapons_School_Weekplan"