Codestitcher: inter-procedural basic block layout optimization
Codestitcher: inter-procedural basic block layout optimization
复制标题
Codestitcher：程序间基本块布局优化
DOI：
10.1145/3302516.3307358
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ding, Chen
中科院分区：
文献类型：
--
作者：
Lavaee, Rahman;Criswell, John;Ding, Chen
现代软件执行大量代码。以前的代码布局优化技术是一二十年前开发的，已经不足以应对编译器、浏览器、解释器、语言虚拟机和共享库等新型应用程序的规模和复杂性。本文介绍了 Codestitcher，这是一种过程间基本块代码布局优化器，它对可执行文件中的基本块进行重新排序，以从更好的缓存和 TLB 性能中受益。 Codestitcher 提供了一个分层框架，可用于改进内存分层结构各层中的局部性。我们的评估表明，Codestitcher 在 5 个广泛使用的大代码应用程序（MySQL、Clang、Firefox、PHP 服务器和 Python）上将原始程序（已经使用 O3 和链接时间优化进行了优化）的性能提高了 3% 到 25%（平均提高了 10%）。与最佳函数重排序技术相结合，它比 LLVM 的 PGO 提高了 4%，比 PGO 提高了 3%。对于分析，Codestitcher 不需要仪器。相反，它使用在原始程序执行期间收集的分支历史样本。 Codestitcher 的分析和跟踪处理总共产生 22.5% 的平均开销，而 LLVM 的 PGO 的平均开销为 90%。
Modern software executes a large amount of code. Previous techniques of code layout optimization were developed one or two decades ago and have become inadequate to cope with the scale and complexity of new types of applications such as compilers, browsers, interpreters, language VMs and shared libraries.This paper presents Codestitcher, an inter-procedural basic block code layout optimizer which reorders basic blocks in an executable to benefit from better cache and TLB performance. Codestitcher provides a hierarchical framework which can be used to improve locality in various layers of the memory hierarchy. Our evaluation shows that Codestitcher improves the performance of the original program (already optimized with O3 and link time optimizations) by 3% to 25% (on average, by 10%) on 5 widely used applications with large code sizes: MySQL, Clang, Firefox, PHP server, and Python. It gives an additional improvement of 4% over LLVM's PGO and 3% over PGO combined with the best function reordering technique. For profiling, Codestitcher does not need instrumentation. Instead it uses branch history samples which are collected during the execution of the original program. Codestitcher's profiling and trace processing together incur an average overhead of 22.5%, compared to an average overhead of 90% from LLVM's PGO.
最大非对称TSP的5/8近似算法
影响因子：
0.8
作者：
Moshe Lewenstein;M. Sviridenko
通讯作者：
M. Sviridenko
用于数据打包的高效参数化算法
DOI：
--
发表时间：
2019
期刊：
Proc. ACM Program. Lang.
影响因子：
--
作者：
K. Chatterjee;A. Goharshady;Nastaran Okati;Andreas Pavlogiannis
通讯作者：
Andreas Pavlogiannis
DOI：
--
发表时间：
2017
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
H. Attiya;Gili Yavneh
通讯作者：
Gili Yavneh