基于协程的异步化内存访问优化

MaLing
uranus 06月08日 字数 1374

协程之间的切换是一个物理线程/进程内部,用户态进行上下文之间的切换。通常协程上下文用使用双向链表链接,其个数由程序员决定。协程切换(设定为yield_thread函数)的代价+ 跳转延迟大约在20个周期左右,L2 延迟在 12个周期,L3延迟基本在50个周期,内存延迟在100ns(3GHZ,300个周期 ), 所以我们在一个进程内部引入多个协程,例如15个协程?(15 *20 周期等于内存访问 300个周期)

数据会由于三种原因执行 yield_thread函数:

1. 在取指令之后,根据指令地址预测是否产生数据L2缓存缺失,如果预测缺失,允许当前指令继续运行,但是对于内存的操作改为prefetch, 协程再切回来后重新执行该指令。

2. 在执行过程中,当得到内存地址之后,此时有更准确的预测能力,使用类似bloom filter的方式,开始做第二次预测,如果预测L2缺失,前端对yeild_thread函数再次取指,同时将内存操作变为prefetch,等到协程切回来再重新执行。

3. 若虽然预测命中,在发现L2缓存缺失的时候,前端对yeild_thread函数取指进行协程的上下文切换,同时不再等待指令返回,等效于跳转预测失败,再次切换回来时重新执行对应指令。

指令会由于二种原因执行 yield_thread函数:

1. 在取指令过程中,当得到指令地址之后,开始做第一次预测,如果预测L2缺失,前端对yeild_thread函数取指,保存上下文,等到协程切回来再重新执行。

2. 指令若预测命中,在发现L2缓存缺失的时候,前端对yeild_thread函数取指进行协程的上下文切换,同时不再等待指令返回,再次切换回来时重新执行对应指令。

注:无论数据还是指令产生的切换,当再次切回来时,默认指令/数据已经在缓存,除非发现真实缺失再做切换。

- 来自 水木社区APP v3.4.2

CSArch 计算机体系结构
13 个回复
kirbyzhou
下雪 你那边下雪了么? 06月16日

看着有点蒙,你这是把协当线程用了?

Yield从用户显式调用变成了随时打断。

几个问题

1. 进入yield时 寄存器保存的细节。随时打断的方式下,寄存器得全部保存吧?

2. 如果协程持锁时因为cache miss被打断了,会怎么样?

3. 很多协程yield出去的时候是要传递参数的,比如generator模式。

【 在 MaLing (uranus) 的大作中提到: 】

:  协程之间的切换是一个物理线程/进程内部,用户态进行上下文之间的切换。通常协程上下文用使用双向链表链接,其个数由程序员决定。协程切换(设定为yield_thread函数)的代价+ 跳转延迟大约在20个周期左右,L2 延迟在 12个周期,L3延迟基本在50个周期,内存延迟在100ns(3GHZ,300个周期 ), 所以我们在一个进程内部引入多个协程,例如15个协程?(15 *20 周期等于内存访问 300个周期)

:  数据会由于三种原因执行 yield_thread函数:

:  1. 在取指令之后,根据指令地址预测是否产生数据L2缓存缺失,如果预测缺失,允许当前指令继续运行,但是对于内存的操作改为prefetch, 协程再切回来后重新执行该指令。

MaLing
uranus 06月16日

“看着有点蒙,你这是把协当线程用了?”

Ling:嗯,因为超线程需要引入硬件代价,且数目受到控制,在这里引入协程,以缓存缺失作为切换事件。

1. 进入yield时 寄存器保存的细节。随时打断的方式下,寄存器得全部保存吧?

Ling: 是,15个寄存器(不包含simd寄存器)

2. 如果协程持锁时因为cache miss被打断了,会怎么样?

Ling:可以进入不被打断模式

3. 很多协程yield出去的时候是要传递参数的,比如generator模式。

Ling:没有,本质上与Linux kernel的 schedule(void)函数相同

【 在 kirbyzhou 的大作中提到: 】

: 看着有点蒙,你这是把协当线程用了?

: Yield从用户显式调用变成了随时打断。

: 几个问题

: ...................

kirbyzhou
下雪 你那边下雪了么? 06月16日

一是为啥不包含simd?

二是这个切换的代价会大于现在的yield吧,对于寄存器多的处理器尤其明显。毕竟abi规定了不用保存全部上下文。

【 在 MaLing (uranus) 的大作中提到: 】

:  “看着有点蒙,你这是把协当线程用了?”

:  Ling:嗯,因为超线程需要引入硬件代价,且数目受到控制,在这里引入协程,以缓存缺失作为切换事件。

:  1. 进入yield时 寄存器保存的细节。随时打断的方式下,寄存器得全部保存吧?

MegaStone
MegaStone 06月21日

这是在一个In-order core上用的吗?

感觉如果在Out-of-order core的话,每次L2 miss就切协程,相比一次性把一个thread内连续的多个访存指令全发射出去,性能会恶化地比较厉害。

【 在 MaLing 的大作中提到: 】

: 协程之间的切换是一个物理线程/进程内部,用户态进行上下文之间的切换。通常协程上下文用使用双向链表链接,其个数由程序员决定。协程切换(设定为yield_thread函数)的代价+ 跳转延迟大约在20个周期左右,L2 延迟在 12个周期,L3延迟基本在50个周期,内存延迟在100ns(3GHZ,300个周期 ), 所以我们在一个进程内部引入多个协程,例如15个协程?(15 *20 周期等于内存访问 300个周期)

: 数据会由于三种原因执行 yield_thread函数:

: 1. 在取指令之后,根据指令地址预测是否产生数据L2缓存缺失,如果预测缺失,允许当前指令继续运行,但是对于内存的操作改为prefetch, 协程再切回来后重新执行该指令。

: ...................

MaLing
uranus 07月02日

Ling: 这是个有趣的问题,通常情况下我们使用simd指令是在可以连续访问多片内存,没有相关性可以更多乱序,能够将多个cache miss 同时并行,例如memcpy中就是典型的案例, 因此不适适使用这种优化,所以若有这种操作可以避免切换,该优化主要为高吞吐高并行的大数据计算场景,比如我们在做的超低延迟数据库,他数据关联较多,会导致大量不连续的指令和数据的L2缺失。

Ling:17个寄存器要写内存和从内存读,x86的写和读的吞吐分别是1/cycle,2/cycle,由于彼此可以乱序,缓存命中情况下的延迟为17个周期,我们使用的是2.1GCPU,耗费了8个纳秒,接近理论值,如果要真正实现,通过进一步优化可以节省更多时间。

【 在 kirbyzhou 的大作中提到: 】

: 一是为啥不包含simd?

: 二是这个切换的代价会大于现在的yield吧,对于寄存器多的处理器尤其明显。毕竟abi规定了不用保存全部上下文。

MaLing
uranus 07月02日

Ling:乱序也可以

Ling:是的,如果有这种场景避免切换就好,例如大量simd指令的向量计算

【 在 MegaStone 的大作中提到: 】

: 这是在一个In-order core上用的吗?

: 感觉如果在Out-of-order core的话,每次L2 miss就切协程,相比一次性把一个thread内连续的多个访存指令全发射出去,性能会恶化地比较厉害。

winfredsu
winfredsu 07月15日

L2 miss的没见过,协程优化LLC miss的工作17年开始在VLDB上出现过,原理大概和你说的一样,发一个prefetch之后就yield, 可以参考这篇文章:https://infoscience.epfl.ch/record/231318

这个方法对于几个GB的树结构访问情景,LLC miss概率较大,可以有明显收益;但是我感觉有两个问题:

1. 这种能“较好预测LLC miss”的场景是否有很多?基于DRAM的数据库是一个好场景,但是还有没有更普遍的?

2. 本质上相当于在线程内部构建了一个状态机,并发处理多个请求,而这不用协程也是可以实现的(参考上面的论文)。用协程只是让编程更好看,还能得到不错的性能。

hgoldfish
老鱼 07月15日

你们太小看协程了。

协程自然是让异步编程变得更好看。还有更多的好处:

仅从语法角度看,协程避免了异步编程中到处乱飞的 closure, context 变量,可以非常有效地减少编程错误。让数据的生命周期变得简单明了。

对于 c/c++ 而言,还能额外获得效率的提升。协程代码一般局部性更强,分配变量时可以更多地分配在栈上面以减少内存复制开销,说不定带来更低的 cache miss. 如果有对协程特别支持的语言,还可以考虑协程运行过程中申请的内存都延迟到协程结束的时候释放,代替开销巨大的 gc 和 malloc/free.

介绍一下我的协程库: https://qtng.org/

【 在 winfredsu (winfredsu) 的大作中提到: 】

: L2 miss的没见过,协程优化LLC miss的工作17年开始在VLDB上出现过,原理大概和你说的一样,发一个prefetch之后就yield, 可以参考这篇文章:https://infoscience.epfl.ch/record/231318

: 这个方法对于几个GB的树结构访问情景,LLC miss概率较大,可以有明显收益;但是我感觉有两个问题:

: 1. 这种能“较好预测LLC miss”的场景是否有很多?基于DRAM的数据库是一个好场景,但是还有没有更普遍的?

: ...................

winfredsu
winfredsu 07月15日

这些优点是异步IO场景里,的确也是协程的本意。但是楼主这里讨论的是更细粒度的cache miss(把访存也看成异步的)能否用协程解决,是在拓展协程的使用场景。

我上面说的是在这种细粒度的场景下,是否就不涉及到闭包和内存分配的优势了? 我硬件做得多,对异步编程模型了解不深

【 在 hgoldfish 的大作中提到: 】

: 你们太小看协程了。

: 协程自然是让异步编程变得更好看。还有更多的好处:

: 仅从语法角度看,协程避免了异步编程中到处乱飞的 closure, context 变量,可以非常有效地减少编程错误。让数据的生命周期变得简单明了。

: ...................

MaLing
uranus 07月15日

1. 这种能“较好预测LLC miss”的场景是否有很多?基于DRAM的数据库是一个好场景,但是还有没有更普遍的?

Ling:不仅仅是数据库,根据我们计算CPI的公式显示,作为数据中心服务器的workload的瓶颈主要来自于L2 指令和数据的缺失,数据显示访问L3命中的延迟和缺失导致的内存访问延迟各占据CPI的30%,共有60%

2. 本质上相当于在线程内部构建了一个状态机,并发处理多个请求,而这不用协程也是可以实现的(参考上面的论文)。用协程只是让编程更好看,还能得到不错的性能。

Ling:不可以,虽然之前没有看过这篇论文,但是我们也考虑过用相同的方案,因为缓存(L2/L3)缺失与运行的软硬件环境紧密相关,随机性很大,如果使用静态的prefetch然后切换的方案,会做出很多无用的操作,尤其在云的需要不断迁移部署环境下。

【 在 winfredsu 的大作中提到: 】

: L2 miss的没见过,协程优化LLC miss的工作17年开始在VLDB上出现过,原理大概和你说的一样,发一个prefetch之后就yield, 可以参考这篇文章:https://infoscience.epfl.ch/record/231318

: 这个方法对于几个GB的树结构访问情景,LLC miss概率较大,可以有明显收益;但是我感觉有两个问题:

: 1. 这种能“较好预测LLC miss”的场景是否有很多?基于DRAM的数据库是一个好场景,但是还有没有更普遍的?

: ...................

winfredsu
winfredsu 07月15日

理解了你的意思,还是希望硬件动态做预测,多谢解释。不过主要挑战应该会在这个预测器上,如果基于PC好预测的话,那么大概率这个信息在静态也能得到;如果是基于访存地址的bloom filter, 需要设计一种在cache evcition时能从bloom filter中“去掉一个项”这样的操作。

【 在 MaLing 的大作中提到: 】

: 1. 这种能“较好预测LLC miss”的场景是否有很多?基于DRAM的数据库是一个好场景,但是还有没有更普遍的?

: Ling:不仅仅是数据库,根据我们计算CPI的公式显示,作为数据中心服务器的workload的瓶颈主要来自于L2 指令和数据的缺失,数据显示访问L3命中的延迟和缺失导致的内存访问延迟各占据CPI的30%,共有60%

: 2. 本质上相当于在线程内部构建了一个状态机,并发处理多个请求,而这不用协程也是可以实现的(参考上面的论文)。用协程只是让编程更好看,还能得到不错的性能。

: ...................

MaLing
uranus 07月17日
MaLing
uranus 07月20日

: 理解了你的意思,还是希望硬件动态做预测,多谢解释。不过主要挑战应该会在这个预测器上,如果基于PC好预测的话,那么大概率这个信息在静态也能得到;

Ling: 正如上面说的到的数据是否在缓存与动态运行的软硬件环境相关,这个与跳转预测(也是基于指令地址)的引入基本一致,大量取决于运行状态,而其主流也是用硬件完成,下面的三篇文章也都是使用硬件预测load-address 以及 cache Hit-Miss。文章《Load value prediction via path-based address prediction: avoiding mispredictions due to conflicting stores》和 《Correlated Load-Address Predictors》中预测load-address的准确率超过99%, 同样《Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching》使用load-address预测数据是否在缓存的准确率也超高99%,因此我们可以说在本文中的第一阶段预测,也就是通过指令地址预测数据是否在缓存中,理想情况下的准确率能接近达到 98%(0.99 * 0.99), 第二阶段通过地址预测准确率就可以达到99%。

“如果是基于访存地址的bloom filter, 需要设计一种在cache evcition时能从bloom filter中“去掉一个项”这样的操作。”

Ling:《Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching》相关内容文章中都有提到

当然只有通过真实的仿真才能有可靠的结论,这方面我们需要进行验证。

【 在 winfredsu 的大作中提到: 】

: 理解了你的意思,还是希望硬件动态做预测,多谢解释。不过主要挑战应该会在这个预测器上,如果基于PC好预测的话,那么大概率这个信息在静态也能得到;如果是基于访存地址的bloom filter, 需要设计一种在cache evcition时能从bloom filter中“去掉一个项”这样的操作。

MaLing
uranus 11月05日

同样支持TLB miss 产生的异步"page table walks",尤其在将来 rack computing on cxl大内存场景

【 在 MaLing 的大作中提到: 】

: 协程之间的切换是一个物理线程/进程内部,用户态进行上下文之间的切换。通常协程上下文用使用双向链表链接,其个数由程序员决定。协程切换(设定为yield_thread函数)的代价+ 跳转延迟大约在20个周期左右,L2 延迟在 12个周期,L3延迟基本在50个周期,内存延迟在100ns(3GHZ,300个周期 ), 所以我们在一个进程内部引入多个协程,例如15个协程?(15 *20 周期等于内存访问 300个周期)

: 数据会由于三种原因执行 yield_thread函数:

: 1. 在取指令之后,根据指令地址预测是否产生数据L2缓存缺失,如果预测缺失,允许当前指令继续运行,但是对于内存的操作改为prefetch, 协程再切回来后重新执行该指令。

: ...................