• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Operating systems review >Compiler-Based Prefetching for Recursive Data Structures
【24h】

Compiler-Based Prefetching for Recursive Data Structures

机译：基于编译器的递归数据结构预取

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Software-controlled data prefetching offers the potential for bridging the ever-increasing speed gap between the memory subsystem and today's high-performance processors. While prefetching has enjoyed considerable success in array-based numeric codes, its potential in pointer-based applications has remained largely unexplored. This paper investigates compiler-based prefetching for pointer-based applications—in particular, those containing recursive data structures. We identify the fundamental problem in prefetching pointer-based data structures and propose a guideline for devising successful prefetching schemes. Based on this guideline, we design three prefetching schemes, we automate the most widely applicable scheme (greedy prefetching) in an optimizing research compiler, and we evaluate the performance of all three schemes on a modern superscalar processor similar to the MIPS R10000. Our results demonstrate that compiler-inserted prefetching can significantly improve the execution speed of pointer-based codes—as much as 45% for the applications we study. In addition, the more sophisticated algorithms (which we currently perform by hand, but which might be implemented in future compilers) can improve performance by as much as twofold. Compared with the only other compiler-based pointer prefetching scheme in the literature, our algorithms offer substantially better performance by avoiding unnecessary overhead and hiding more latency.
机译：软件控制的数据预取为弥合内存子系统与当今高性能处理器之间不断扩大的速度差距提供了潜力。尽管预取在基于数组的数字代码中获得了相当大的成功，但在基于指针的应用程序中的潜力仍未得到开发。本文研究了基于指针的应用程序的基于编译器的预取，尤其是那些包含递归数据结构的应用程序。我们确定了预取基于指针的数据结构中的基本问题，并提出了设计成功的预取方案的指南。基于此指南，我们设计了三种预取方案，在优化的研究编译器中使最广泛应用的方案（贪婪预取）自动化，并在类似于MIPS R10000的现代超标量处理器上评估了这三种方案的性能。我们的结果表明，插入编译器的预取可以显着提高基于指针的代码的执行速度-对于我们研究的应用程序，其执行速度高达45％。另外，更复杂的算法（我们目前手工执行，但可能会在将来的编译器中实现）可以将性能提高两倍。与文献中仅有的其他基于编译器的指针预取方案相比，我们的算法可避免不必要的开销并隐藏更多的延迟，从而显着提高性能。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号