Algorithms for Modern Processor Architectures

Summary

Previous slideNext slideToggle fullscreenOpen presenter view Disk at gigabytes per second High Bandwidth Memory Xeon Max processors contain 64 GB of HBM Bandwidth 800 GB/s Some numbers Time is discrete: clock cycle Processors: 4 GHz ( cycles per second) One cycle is 0.25 nanoseconds light: 7.5 centimeters per cycle One byte per cycle: 4 GB/s Easily CPU bound Frequencies and transistors processor year frequency transistors Pentium 4 2000 3.8 GHz 0.040 billions Intel Haswell 2013 4.4 GHz 1.4 billions Apple M1 2020 3.2 GHz 16 billions Apple M2 2022 3.49 GHz 20 billions Apple M3 2024 4.05 GHz 25 billions Apple M4 2024 4.5 GHz 28 billions AMD Zen 5 2024 5.7 GHz 50 billions Where do the transistors go? More cores More superscalar execution Better speculative execution More cache, more memory-level parallelism Better data-level parallelism (SIMD) Where do the transistors go? More cores More superscalar execution (more instructions per cycle) Better speculative execution ( more instructions per cycle) More cache, more memory-level parallelism ( more instructions per cycle) Better data-level parallelism (SIMD) ( fewer instructions) Superscalar execution processor year arithmetic logic units SIMD units Pentium 4 2000 2 AMD Zen 2 2019 4 Apple M* 2019 6+ Intel Lion Cove 2024 6 AMD Zen 5 2024 6 Moving to up to 4 load/store per cycle Parsing a number double result; fast_float::from_chars( input.data(), input.data() + input.size(), result); Reference: Number Parsing at a Gigabyte per Second, Software: Practice and Experience 51 (8), 2021 Parsing a number Lemire's Rule 1 Modern processors execute nearly as many instructions per cycle as you can supply. with caveats: branching, memory, and input/output Lemire's Corrolary 1 In computational workloads (batches), minimizing instruction count is critical for achieving optimal performance. Lemire's Tips Batch your work in larger units to save instructions. Simplify the processing down to as few instructions as possible. Going back to num...