Scheduling I/O Latency-Hiding Futures in Task-Parallel Platforms
Scheduling I/O Latency-Hiding Futures in Task-Parallel Platforms
复制标题
在任务并行平台中调度 I/O 延迟隐藏 Future
DOI：
10.1137/1.9781611976021.11
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Lee, Angelina I-Ting
中科院分区：
文献类型：
--
作者：
Singer, Kyle;Agrawal, Kunal;Lee, Angelina I-Ting
任务并行性研究传统上侧重于优化计算密集型应用程序。由于商用并行处理器的激增，最近人们对支持交互式应用程序产生了兴趣。此类交互式应用程序经常依赖于 I/O 操作，这些操作需要很少的处理周期，但可能会导致显着的延迟才能完成。为了提高性能，当特定控制线程在 I/O 操作上被阻塞时，理想情况下，我们希望通过使用处理资源执行其他就绪工作来隐藏此延迟，而不是在此 I/O 上阻塞或旋转等待。先前关于隐藏此延迟的工作有限，并且只有一个结果为使用 I/O 操作的交互式应用程序提供了理论界限。在这项工作中，我们提出了一种任务并行平台，该平台使用 future 抽象支持 I/O 操作，以及一个相应的调度程序，该调度程序在隐藏其延迟的同时调度 I/O 操作。我们对调度算法进行了理论分析，表明我们的算法比之前的工作提供了更好的执行时间保证。我们还在 Cilk-F 运行时（一个在 Cilk Plus 语言上下文中支持 futures 的运行时系统）之上运行的实用高效原型库中实现了该算法，并进行了实验来证明我们实现的效率。
Task parallelism research has traditionally focused on optimizing computation-intensive applications. Due to the proliferation of commodity parallel processors, there has been recent interest in supporting interactive applications. Such interactive applications frequently rely on I/O operations that require few processing cycles but may incur significant latency to complete. In order to increase performance, when a particular thread of control is blocked on an I/O operation, ideally we would like to hide this latency by using the processing resources to do other ready work instead of blocking or spin waiting on this I/O. There has been limited prior work on hiding this latency and only one result that provides a theoretical bound for interactive applications that use I/O operations.In this work, we propose a task parallel platform that supports I/O operations using the futures abstraction and a corresponding scheduler that schedules the I/O operations while hiding their latency. We provide a theoretical analysis of our scheduling algorithm that shows our algorithm provides better execution time guarantees than prior work. We also implemented the algorithm in a practically efficient prototype library that runs on top of the Cilk-F runtime, a runtime system that supports futures within the context of the Cilk Plus language, and performed experiments that demonstrate the efficiency of our implementation.
登录
查看更多内容
BQ：带批处理的无锁队列
DOI：
10.1145/3210377.3210388
发表时间：
2018
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gal Milman;Alex Kogan;Yossi Lev;Victor Luchangco;E. Petrank
通讯作者：
E. Petrank
Habanero 多核软件研究项目
DOI：
10.1145/1639950.1639989
发表时间：
2009
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
R. Barik;Zoran Budimlic;Vincent Cavé;S. Chatterjee;Yi Guo;David M. Peixotto;Raghavan Raman;J. Shirako;Sagnak Tasirlar;Yonghong Yan;Yisheng Zhao;Vivek Sarkar
通讯作者：
Vivek Sarkar
在 JCIlk 中进行异常编程
DOI：
10.1016/j.scico.2006.05.008
发表时间：
2006
期刊：
Sci. Comput. Program.
影响因子：
--
作者：
John S. Danaher;I. Lee;C. Leiserson
通讯作者：
C. Leiserson
为未来主动窃取工作
DOI：
10.1145/3293883.3295735
发表时间：
2019
期刊：
Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Singer, Kyle;Xu, Yifan;Lee, I-Ting Angelina
通讯作者：
Lee, I-Ting Angelina
DOI：
10.1145/2983990.2984035
发表时间：
2016
期刊：
Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications
影响因子：
--
作者：
R. Surendran;Vivek Sarkar
通讯作者：
Vivek Sarkar