4 ms·

What program was used to create the dependency diagrams? And is there some more general introduction for using this sort of dependency analysis for low level op

What program was used to create the dependency diagrams? And is there some more general introduction for using this sort of dependency analysis for low level optimizations?

gerbenst 6y ago
That was just hand analysis of the data flow together with Google Diagrams. As I mention in the article, dependency analysis has, IMO, not received the widespread attention it should. I like Fabian Giesen's article if you want an introduction. https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/ https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...
- matt_d 6y ago
  FWIW, there are some interesting tools for microarchitectural performance analysis which are getting closer (although it's a work in progress): https://github.com/MattPD/cpplinks/blob/master/performance.tools.md#microarchitecture https://github.com/MattPD/cpplinks/blob/master/performance.t... One particularly interesting example in this context is OSACA (Open Source Architecture Code Analyzer), https://github.com/RRZE-HPC/osaca https://github.com/RRZE-HPC/osaca The related publications explain the approach used to model and perform critical path analysis relevant for the modern superscalar out-of-order processors: - Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels (2019): https://arxiv.org/abs/1910.00214 https://arxiv.org/abs/1910.00214 - Cross-Architecture Automatic Critical Path Detection For In-Core Performance Analysis (2020): https://hpc.fau.de/files/2020/02/Masterarbeit_JL-_final.pdf https://hpc.fau.de/files/2020/02/Masterarbeit_JL-_final.pdf There's also a broader line of research on performance modeling in this vein (some pretty detailed, including microarchitectural details like branch misprediction penalties, ROB capacity, etc.): https://gist.github.com/MattPD/85aad98ee8b135e675d49c571b67fde9#file-performance-modeling-criticality-md https://gist.github.com/MattPD/85aad98ee8b135e675d49c571b67f... More on modeling microarchitectural details (chronological order): - Tejas S. Karkhanis and James E. Smith. "A First-Order Superscalar Processor Model." (ISCA 2004) - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79... http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79..... - Stijn Eyerman, Lieven Eeckhout, Tejas Karkhanis, and James E. Smith. "A mechanistic performance model for superscalar out-of-order processors." ACM Trans. Comput. Syst. 27, 2 (2009) - http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf - Maximilien B. Breughe, Stijn Eyerman, and Lieven Eeckhout. "Mechanistic analytical modeling of superscalar in-order processor performance." ACM Trans. Architec. Code Optim. 11, 4, Article 50 (2014) - https://users.elis.ugent.be/~leeckhou/papers/taco2015-breugh.. https://users.elis.ugent.be/~leeckhou/papers/taco2015-breugh.... - "Modeling Superscalar Processor Memory-Level Parallelism", Sam Van den Steen and Lieven Eeckhout, IEEE Computer Architecture Letters (CAL), Vol 17, No 1 (2018) - https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf

What program was used to create the dependency diagrams? And is there some more general introduction for using this sort of dependency analysis for low level optimizations?

gerbenst 6y ago

That was just hand analysis of the data flow together with Google Diagrams. As I mention in the article, dependency analysis has, IMO, not received the widespread attention it should. I like Fabian Giesen's article if you want an introduction. https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introduction-to-dataflow-graphs/ https://fgiesen.wordpress.com/2018/03/05/a-whirlwind-introdu...

matt_d 6y ago
FWIW, there are some interesting tools for microarchitectural performance analysis which are getting closer (although it's a work in progress): https://github.com/MattPD/cpplinks/blob/master/performance.tools.md#microarchitecture https://github.com/MattPD/cpplinks/blob/master/performance.t... One particularly interesting example in this context is OSACA (Open Source Architecture Code Analyzer), https://github.com/RRZE-HPC/osaca https://github.com/RRZE-HPC/osaca The related publications explain the approach used to model and perform critical path analysis relevant for the modern superscalar out-of-order processors: - Automatic Throughput and Critical Path Analysis of x86 and ARM Assembly Kernels (2019): https://arxiv.org/abs/1910.00214 https://arxiv.org/abs/1910.00214 - Cross-Architecture Automatic Critical Path Detection For In-Core Performance Analysis (2020): https://hpc.fau.de/files/2020/02/Masterarbeit_JL-_final.pdf https://hpc.fau.de/files/2020/02/Masterarbeit_JL-_final.pdf There's also a broader line of research on performance modeling in this vein (some pretty detailed, including microarchitectural details like branch misprediction penalties, ROB capacity, etc.): https://gist.github.com/MattPD/85aad98ee8b135e675d49c571b67fde9#file-performance-modeling-criticality-md https://gist.github.com/MattPD/85aad98ee8b135e675d49c571b67f... More on modeling microarchitectural details (chronological order): - Tejas S. Karkhanis and James E. Smith. "A First-Order Superscalar Processor Model." (ISCA 2004) - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79... http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.79..... - Stijn Eyerman, Lieven Eeckhout, Tejas Karkhanis, and James E. Smith. "A mechanistic performance model for superscalar out-of-order processors." ACM Trans. Comput. Syst. 27, 2 (2009) - http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf http://www.elis.ugent.be/~leeckhou/papers/tocs09.pdf - Maximilien B. Breughe, Stijn Eyerman, and Lieven Eeckhout. "Mechanistic analytical modeling of superscalar in-order processor performance." ACM Trans. Architec. Code Optim. 11, 4, Article 50 (2014) - https://users.elis.ugent.be/~leeckhou/papers/taco2015-breugh.. https://users.elis.ugent.be/~leeckhou/papers/taco2015-breugh.... - "Modeling Superscalar Processor Memory-Level Parallelism", Sam Van den Steen and Lieven Eeckhout, IEEE Computer Architecture Letters (CAL), Vol 17, No 1 (2018) - https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf https://users.elis.ugent.be/~leeckhou/papers/cal2018-MLP.pdf