NBJL 2020论文导读25: Concurrent Data Structures with Near-Data-Processing: an Architecture-Aware Implementation


赵昌健

论文(以及slide)下载地址:https://jiwon-choe.github.io/

论文信息: 论文发表在SPAA2019,作者是来自Brown UniversityJiwon Choe 等人。


  1. 论文摘要

内存体系结构的最新进展引起了新的关注研究者希望通过近数据处理(NDP技术来缓解“内存”问题。 NDP架构将逻辑电路simple core)放置到紧挨着内存的地方高效的使用NDP体系结构需要重新考虑数据结构及其算法。前人的工作提供了基于经验评估的并发数据结构的设计,例如有序链表、跳跃表FIFO队列。经过模拟器级实验分析表明,前人所设计的数据结构效果并没有理论分析的那么高效,原因是前人没有考虑DRAM层面具体的硬件操作论文对并发数据结构场景下的DRAM底层活动进行了分析,同时对DRAM内存控制器进行了轻量级的修改,提高了基于NDP的并发数据结构的性能并降低了能耗,并且在大部分情况下基于NDP架构设计的并发数据结构性能要优于基于HOST架构的并发数据结构


  1. 论文内容












上图abc分别为前人工作中NDP架构下并发有序链表、跳表、队列的具体设计,对于有序链表,多个host processor会发送请求到NDP core,NDP core维护一个操作listlist中的具体操作由NDP core来完成;对于跳跃表,每一个NDP vault会存储对应key范围的nodehost processor发送对应的请求到不同的vault,由NDP core来执行相应的访存请求;对于队列,host processor会提前知道队首和队尾处于的vaulthost processor发送对应的请求到不同的vault,由NDP core来执行相应的访存请求。















论文对NDP中的内存控制器进行了修改,主要思想是,增加buffer,提高数据复用率,减少向vault发送请求的机会;新的设计在内存控制器中添加了两部分:tag registerdata buffer,分别来存储buffer中数据的地址和数据,每次有访存请求时,会先访问tag register查询当前访问数据是否存储在Buffer中,如果tag register中的地址和访存地址一致,则直接返回data buffer中的数据,否则,访问vault中的数据。


三、自己的认识和体会(包括与自己工作的联系和启发等)

论文对并发数据结构的底层DRAM activity进行分析,通过对硬件的轻量级改动,实现了高效的并发数据结构。论文中实现的数据结构为较为简单,没有涉及到cross vault access,未来可考虑复杂数据结构例如B+树如何在NDP架构下实现高效的并发。