基于片上RAM的高并发访存加速方法、加速器及CPU

摘要

本发明公开了一种基于片上RAM的高并发访存加速器及访存方法以及采用该方法的处理器，该访存加速器独立于片上Cache和MSHR，与片上RAM和内存控制器相连，未完成访存请求通过该访存加速器发往内存控制器至内存系统，从而解决通用处理器在互联网和云计算应用中并发访存个数受限的问题，加速高并发访存。

说明书

技术领域

本发明属计算机领域，涉及CPU内部的结构设计，尤其涉及一种基于片上RAM 的高并发访存加速方法、加速器及CPU。

背景技术

随着互联网和云计算的发展，高并发的数据处理程序越来越多。这类程 序通常需要处理以请求（request）或作业（job）的形式提交的大量并发负载， 这些并发负载的核心业务通常涉及到海量数据的处理和分析。这类程序通常使 用多线程或多进程，线程或进程之间有较低的访存依赖或无访存依赖。

因此这类应用可以向内存系统发出大量的并发访存请求。这对访存系统 的并发性提出了挑战。如果访存系统的并发性不够高，就会成为这类应用提高 性能的瓶颈。

图1所示为典型的CPU存储结构。当CPU需要读取数据时，先到Cache 中查找，如果Cache中已经存有所需数据（Cache hit），则直接将数据返回给 CPU。如果CPU在Cache中未查到所需数据（Cache miss），CPU会到主存（Main  Memory）中将所需数据取回到Cache中。

Cache中有一组寄存器MSHR（Miss Status Handling Registers），专门用于记 录已经发向内存的cache未命中的的读请求（即Cache miss的请求）的信息。MSHR 记录的信息包括Cache Line地址、读请求的目的寄存器等。当主存完成读请求、返 回该Cache Line的数据后，记录的信息就用于填充对应的Cache Line和返回数据 到目的寄存器中。每个Cache Miss的读请求都要占用MSHR的一项。当MSHR被占满 后，新的Cache Miss的读请求就会被停住，不能发至主存。因此，MSHR支持的未 完成读请求（指读请求已经发送出去，但读请求的数据还未返回。这个读请求还没 有完成，所以还要由MSHR记录该请求）的个数，是决定访存系统并发度的关键因 素之一。

目前，比较典型的处理器的MSHR支持的未完成读请求的个数一般较少。 例如Cortex-A9处理器，L2Cache的MSHR仅支持10个未完成的读请求。当 应用程序向内存系统发出大量并发访存请求，并且这些请求局部性较低（因此 会出现大量Cache Miss）时，MSHR就会迅速被占满，成为整个系统的瓶颈。

图2所示为某型处理器的存储体系结构，该处理器提出了一种全新的访 存方式，理论上可以支持大量并发访存请求的发送。

该处理器由1个PPE（Power Processor Element）、8个SPE（Synergistic  Processing Element，协同处理单元）、1个MIC（Memory Interface Controller， 内存接口控制器）、1个EIB（Element Interconnect Bus，单元互连总线）组 成。

下面重点关注协同处理单元SPE的访存机制。

每个SPE都是一个微处理器，其程序可以运行在本地256KB的存储单元 中（RAM）。当SPE需要从主存（Main Memory）中获取数据时，需要先初始化 DMAC（Direct Memory Access Controller），将请求源地址、目的地址和请求 长度等参数写入DMAC控制队列中。DMAC根据队列中的参数自行将数据从主存 搬移到本地存储中。

这种机制理论上支持的并发请求的个数仅受限于DMA命令队列中可存储 的命令个数，或者是受限片上RAM的容量。但是，这种机制有两个缺陷：

1.由于每个DMA操作启动之前都需要先输入一些参数，如源地址、目标 地址、数据大小、TAG标记和方向等，这个过程将占用若干个指令周期。如果 SPE需要并发读取大量的小粒度数据时，DMA传输的效率是比较低的；

2.DMA状态管理的效率低。首先，程序需要为读请求的返回数据准备足 够的空间，而该方案缺乏空闲空间管理机制，长时间运行后本地存储空间利用 率将大大降低；其次，处理器获取DMA完成状态采用了软件轮询状态位的方式， 当访存请求的个数增多时，效率不高。

发明内容

为了解决上述技术问题，本发明的目的在于提出一种基于片上RAM的高并 发访存加速器及利用片上RAM管理大量并发访存请求的方法，解决通用处理器 在互联网和云计算应用中并发访存个数受限的问题，加速高并发访存。

具体地讲，本发明公开了一种基于片上RAM的高并发访存加速器，该访存加速 器独立于片上Cache和MSHR，与片上RAM和内存控制器相连，未完成访存请求通过 该访存加速器发往内存控制器至内存系统。

所述基于片上RAM的高并发访存加速器，该访存加速器所支持的待完成访存请 求的个数仅取决于片上RAM的容量，不受MSHR项数的限制。

所述基于片上RAM的高并发访存加速器，该可寻址空间中有一张读请求 表，用于存放读请求的信息，该读请求表的每一项对应一个固有的id号。

所述基于片上RAM的高并发访存加速器，该读请求表的每一项有三个域， 用于存放该读请求的类型、地址和数据，其中类型域和地址域由CPU填入，数 据域由该访存加速器填入。

所述基于片上RAM的高并发访存加速器，该读请求表的数据域过大时，可以只 存放数据指针，数据指针指向返回数据的存放地址，返回数据的存放地址由CPU进 行分配。

所述基于片上RAM的高并发访存加速器，该读请求表的每一项均为三种状 态：空闲、新的读请求和已经完成读请求，初始状态为空闲，CPU有访存请求 时，将请求填入，状态变为新的读请求，访存加速器将该请求发往内存控制器， 返回数据后将数据填入数据域，状态变为已经完成读请求，CPU从数据域中取 数据并进行处理，处理完成后状态回到空闲。

所述基于片上RAM的高并发访存加速器，每个循环队列都包括一个头指 针和一个尾指针，空闲队列的头指针和尾指针及已完成队列的头指针是软件中 的变量，由CPU负责维护；新读请求队列的头指针、尾指针和已完成队列的尾 指针是硬件寄存器，新读请求队列的头指针由访存加速器负责维护；新读请求 队列的尾指针由CPU和访存加速器共同维护，CPU只写，访存加速器只读；已 完成队列的尾指针由CPU和访存加速器共同维护，CPU只读，访存加速器只写。

本发明还公开一种基于片上RAM的高并发访存方法，包括设置一独立于 片上Cache和MSHR的访存加速器，该访存加速器与片上RAM和内存控制器相 连，未完成访存请求通过该访存加速器发往内存控制器至内存系统。

所述基于片上RAM的高并发访存方法，片上CPU将访存请求写入片上RAM的可 寻址空间，该访存加速器读取请求执行，对于读请求，待数据从内存系统返回后， 该访存加速器将数据放入该空间并通知CPU，CPU对数据进行处理。

所述基于片上RAM的高并发访存方法，该可寻址空间中有一张保存读请求 的读请求表，用于存放读请求的信息，该读请求表的每一项对应一个固有的 id号。

所述基于片上RAM的高并发访存方法，该读请求表的每一项有三个域，用 于存放该读请求的类型、地址和数据，其中类型域和地址域由CPU填入，数据 域由该访存加速器填入。

所述基于片上RAM的高并发访存方法，该读请求表的数据域过大时，可以只存 放数据指针,数据指针指向返回数据的存放地址，返回数据的存放地址由CPU进行分 配。

所述基于片上RAM的高并发访存方法，该读请求表的每一项均为三种状 态：空闲、新的读请求和已经完成读请求，初始状态为空闲，CPU有访存请求 时，将请求填入，状态变为新的读请求，访存加速器将该请求发往内存控制器， 返回数据后将数据填入数据域，状态变为已经完成读请求，CPU从数据域中取 数据并进行处理，处理完成后状态回到空闲。

本发明还公开一种基于片上RAM的高并发访存方法，包括CPU发起读请求的步 骤：

步骤S701，CPU查询片上RAM可寻址空间中的空闲队列状态，判断空闲 队列是否为空，CPU判断空闲队列为空的条件是：空闲队列的头指针与尾指针 重合，若空，则返回，若非空，则转至步骤S702。

步骤S702，CPU从空闲队列队首取id；

步骤S703，CPU填写与该id对应的读请求表项的类型域和地址域；

步骤S704，CPU将该id写入新读请求队列的队尾；

步骤S705，CPU将更新的新读请求队列队尾指针传给访存加速器；

步骤S706，CPU判断是否继续发起读请求，若是，转至步骤S701，若否， 返回。

本发明还公开一种基于片上RAM的高并发访存方法，包括CPU处理读请求返回 数据步骤：

步骤S801，CPU查询已完成队列的状态，判断已完成队列是否为空（CPU 判断已完成队列为空的条件是：已完成队列的头指针与尾指针重合），若空， 则返回；若非空，则转至步骤S802；

步骤S802，CPU从已完成队列的队首取id；

步骤S803，CPU操作与该id对应的读请求表项的数据域；

步骤S804，CPU将该id写入空闲队列的队尾；

步骤S805，CPU判断是否继续操作，若是，则转至步骤S801，若否，则 返回。

本发明还公开一种基于片上RAM的高并发访存方法，其特征在于，包括访存加 速器处理读请求的步骤：

步骤S901，访存加速器实时查询新请求队列是否为空，若非空，则转至 步骤S902，若空，则一直在此步骤查询；

步骤S902，访存加速器从新读请求队列的队首取id；

步骤S903，访存加速器取出与该id对应的读请求表项的类型域和地址域；

步骤S904，访存加速器从内存中取回数据，写入到与该id对应的读请求 表项的数据域；

步骤S905，访存加速器将该id写到已完成队列的队尾。

本发明还公开一种基于片上RAM的高并发访存方法，包括：

步骤1，CPU发起写请求时，先检查写循环队列是否已满，若不满，则填 入写请求的类型、地址和写数据；

步骤2，访存加速器检测到写循环队列非空，则自动从写循环队列头指针 处读取写请求的类型、地址和数据；

步骤3，访存加速器将写请求发给内存控制器。

本发明还公开一种采用权利要求1-17中任一项高并发访存方法或者高 并发访存器的处理器。

本发明的技术效果：

1、利用片上RAM保存1个或多个读请求表（Read table），读请求表每 一项的内容包括请求类型域、目标地址域和数据域等所有读请求的必要信息， 由于本发明使用片上RAM记录并发请求的所有信息，并发请求的数量仅受限于 片上RAM的大小。

2、将读请求表的每一项按请求状态分成3类：空闲类、新请求类和完成 类，并且每一类请求项的入口地址分别使用循环队列进行存储，便于对读请求 的状态进行管理。本发明使用循环队列管理大量的读、写请求信息，避免轮询 多个请求的状态位，查询的次数大大减少，从而对大量并发且不相关的小粒度 访存请求具有明显的加速效果。

3、通过“新请求类”的循环队列的非空状态判断是否发起访存操作，通 过读取“新请求类”循环队列的内容，获取读请求在片上RAM存储的地址，如 此，访存加速器可以自行乱序发起访存操作，不需要软件进行控制，从而支持 访存请求的乱序执行，乱序返回，方便对大量访存请求实现有针对性的调度。

4、CPU软件通过“完成类”循环队列的非空状态判断是否有读请求完成， CPU通过读取“完成类”循环队列的内容，获取读请求返回数据在片上RAM中 的地址，避免CPU轮询多个请求的状态位，提高软件查找效率。

附图说明

图1所示为现有典型的CPU存储结构；

图2所示为某型处理器的存储体系结构；

图3所示为本发明的访存加速器在处理器上的位置图；

图4所示为本发明中的可寻址空间中的Read table；

图5所示为本发明中的Read table中每一项的状态变迁；

图6所示为本发明中使用三个循环队列管理读请求的状态；

图7所示为本发明中CPU发起读请求的步骤；

图8所示为本发明中CPU处理读请求返回数据的步骤；

图9所示为本发明中访存加速器处理读请求的步骤；

图10所示为本发明中的使用一个循环队列管理写请求。

具体实施方式

本发明针对通用处理器并发访存请求个数受限的问题，提出“访存加速器” 的概念。访存加速器是CPU和内存Memory之间的另一条通路。

图3所示为本发明的访存加速器在处理器上的位置图，它绕过高速缓存 Cache和MSHR，所支持的未完成读请求的个数比MSHR多至少一个数量级。因 此，通过访存加速器，应用程序能将更多的访存请求发往内存系统，从而提高 访存的并发性。处理器包括CPU1、RAM3、访存加速器4、Cache2、MSHR3、内 存控制器6、内存7。

访存加速器需要CPU拥有一块片上可寻址的RAM空间，CPU将访存请求写 入该RAM空间，访存加速器读取请求执行。如果是读请求，待数据从Memory 返回后，访存加速器将数据放入空间并通知CPU，然后CPU对数据进行处理。

图4所示为本发明中的可寻址空间中的读请求表（Read table），可寻址 空间中要有一张保存读请求的读请求表，称为Read table。

Read table的每一项对应一个固有的id号，Read table项中可以存放读 请求的信息。每一项有三个域：type、addr、data，分别用于存放该读请求的 类型、地址和数据。type域用于编码需要的附加信息，如请求的数据长度、 请求的优先级、是否是一个分离/聚合（scatter/gather）类型的读请求等等。 使用type域，再加上辅助的硬件，就可以实现一些当前体系结构不支持的高 级访存功能。type域和addr域由CPU填入，data域由访存加速器填入。

Read table中的每一项都可以分为三种状态：空闲、新的读请求（尚未 发送给内存控制器）、已经完成的读请求（内存控制器已经返回该请求的数据， 并且数据已填入data域）。

图5所示为本发明中的Read table中每一项的状态变迁，对于Read table 中的一项，初始状态为空闲free；CPU有访存请求时，将请求填入该项，该项 状态就变为新读请求new read；访存加速器将该请求发往内存控制器，返回 数据后将数据填入该项的data域，该项的状态就变为完成度请求finished  read；CPU从data域中取数据并进行处理，处理完成后该项的状态就回到了 空闲free。

在上述过程中，有三个关键的问题需要解决：

1.CPU发送请求时如何找到Read table中的空闲项的位置？

2.访存加速器如何找到新请求项的位置？

3.CPU如何获取读请求返回项的位置？

为此，本发明提出了一种基于循环队列的请求管理方法。

图6所示为本发明中使用三个循环队列管理读请求的状态，三个循环队列为： 空闲循环队列（free entry queue），新读请求循环队列（new read queue）和完 成读请求循环队列（finished read queue），分别用于存储Read table中的空闲 项、新读请求项和已完成的读请求项的id。这三个循环队列都在可寻址空间中。每 个队列有两个指针：队头head和队尾tail，分别用于指示队列头和队列尾的位置。 图中，A是返回，CPU可以重新决定是继续发起读请求还是可以开始处理数据。未返 回前，是不允许其他操作插入的，返回后，才可以重新发起操作。

举例说明CPU使用访存加速器发起读请求的操作的过程：

1.当CPU需要读取内存数据时，先查询free entry queue是否为空。若 为空，则说明图4中的Read table被完全占满，暂时还没有空闲的Read table 项可用；若非空，则说明Read table中还有空闲项可用。如图6所示，判断 free entry queue是否为空的条件是：指针head1与指针tail1重合。

2.CPU从free entry queue的队首取出一个id号，找到该id号对应的 Read table项的地址，将新请求的type和addr域填入Read table项。同时， CPU将该id号存放到new read queue的队尾。

CPU对循环队列的操作过程如图6中虚线1所示，此操作完成后，id3将 被从head1位置挪到tail2的位置。

3.CPU将tail2指针向后移一位，并将新的tail2指针发送给访存加速器。

4.访存加速器通过比较head2和tail2指针来判断new read queue是否 为空。当访存加速器检测到new read queue非空时，则自动从new read queue 队首取出新的id，通过id找到Read table中对应的未完成的读请求项进行 处理，将请求的数据返回到Read table的data域中。处理完成后，将该id 写入finished read queue的队尾。

访存加速器对循环队列的操作过程如图6中虚线2所示，此操作完成后， id9将被从head2位置挪到tail3的位置。

5.CPU需要处理数据时，先检查finished read queue是否为空。检查方 法仍然是对比head和tail指针。若finished read queue非空，则取出一个 id号，找到该id对应的Read table项，对该项的data域进行处理。处理完 成后，将该id写入到new read queue的队尾。

CPU对循环队列的操作过程如图6中虚线3所示，此操作完成后，id2将 被从head3位置挪到tail1的位置。

6.以上过程可以重复进行。

写请求的处理相对简单。由于写请求不用返回数据，访存加速器只需将 CPU发下来的写请求传递给内存控制器即可，因此其管理结构可大大简化。

图10所示为本发明中的使用一个循环队列管理写请求，只需使用一个写 循环队列（write queue）即可管理写请求。这里将写请求的type、addr和 data域直接放入队列中。与上边的三个队列queue一样，write queue也需要 在可寻址空间中。

写循环队列(write queue)的使用方式如下：

CPU需要发新的写请求时，先检查write queue是否已满(发写请求时，需 要先确定write queue里是否还有空间可以暂存数据。满就表示ram上没有空 间了，就不能再发送写请求了。若不满，则向tail4指示的位置填入写请求的 类型、地址和写数据。

访存加速器检测到write queue非空（说明有数据，说明还有写请求未完 成，访存加速器自动将请求取出执行），则自动从head4指针处读取写请求的 type、addr和data，将写请求发给内存控制器。

综上，本发明公开了一种基于片上RAM的高并发访存加速器，该访存加速器独 立于片上Cache和MSHR，与片上RAM和内存控制器相连，未完成访存请求通过该访 存加速器发往内存控制器至内存系统。

该访存加速器所支持的该未完成访存请求的个数仅取决于片上RAM的容量，不 受MSHR项数的限制。该片上RAM为具有可寻址空间的RAM，片上CPU将访存请求写 入该可寻址空间，访存加速器读取请求执行，对于读请求，待数据从内存系统返回 后，该访存加速器将数据放入该可寻址空间并通知CPU，然后CPU对数据进行处理。

该片上RAM为片上CPU的RAM，或者独立于片上CPU。

该可寻址空间中有一张读请求表，用于存放读请求的信息，该读请求表的 每一项对应一个固有的id号。

该读请求表的每一项有三个域，用于存放该读请求的类型、地址和数据， 其中类型域和地址域由CPU填入，数据域由该访存加速器填入。

该读请求表的每一项均为三种状态：空闲、新的读请求和已经完成读请求， 初始状态为空闲，CPU有访存请求时，将请求填入，状态变为新的读请求，访 存加速器将该请求发往内存控制器，返回数据后将数据填入数据域，状态变为 已经完成读请求，CPU从数据域中取数据并进行处理，处理完成后状态回到空 闲。

该三种状态通过三个循环队列进行管理，每个循环队列包括队列头和队 列尾的位置指针。

本发明还公开了一种基于片上RAM的高并发访存方法，包括设置一独立 于片上Cache和MSHR的访存加速器，该访存加速器与片上RAM和内存控制器 相连，未完成访存请求通过该访存加速器发往内存控制器至内存系统。

所述基于片上RAM的高并发访存方法，片上CPU将访存请求写入片上RAM的可 寻址空间，该访存加速器读取请求执行，对于读请求，待数据从内存系统返回后， 该访存加速器将数据放入该空间并通知CPU，CPU对数据进行处理。

本发明还公开了一种基于片上RAM的高并发访存方法，其特征在于，包括CPU 发起读请求的步骤：

步骤S701，CPU查询片上RAM可寻址空间中的空闲队列状态，判断空闲 队列是否为空，若空，则返回，若非空，则转至步骤S702。CPU判断空闲队列 为空的条件是：空闲队列的头指针与尾指针重合。

步骤S702，CPU从空闲队列队首取id；

步骤S703，CPU填写与该id对应的读请求表项的类型域和地址域；

步骤S704，CPU将该id写入新读请求队列的队尾；

步骤S705，CPU将更新的新读请求队列队尾指针传给访存加速器；

步骤S706，CPU判断是否继续发起读请求，若是，转至步骤S701，若否， 返回。

本发明还公开了一种基于片上RAM的高并发访存方法，其特征在于，包括CPU 处理读请求返回数据步骤：

步骤S801，CPU查询已完成队列的状态，判断已完成队列是否为空，若 空，则返回；若非空，则转至步骤S802；访存加速器判断已完成队列为空的 条件是：已完成队列的头指针与尾指针重合。

步骤S802，CPU从已完成队列的队首取id；

步骤S803，CPU操作与该id对应的读请求表项的数据域；

步骤S804，CPU将该id写入空闲队列的队尾；

步骤S805，CPU判断是否继续操作，若是，则转至步骤S801，若否，则 返回。

本发明还公开了一种基于片上RAM的高并发访存方法，其特征在于，包括访存 加速器处理读请求的步骤：

步骤S901，访存加速器实时查询新请求队列是否为空，若非空，则转至 步骤S902，若空，则一直在此步骤查询；

步骤S902，访存加速器从新读请求队列的队首取id；

步骤S903，访存加速器取出与该id对应的读请求表项的类型域和地址域；

步骤S904，访存加速器从内存中取回数据，写入到与该id对应的读请求 表项的数据域；

步骤S905，访存加速器将该id写到已完成队列的队尾。

所述基于片上RAM的高并发访存方法，判断空闲队列是否为空的条件是： 队列头指针与队列尾指针重合。

该访存加速器对大量并发的读请求可以乱序发送，乱序返回。

本发明还公开了一种基于片上RAM的高并发访存方法，包括：

步骤1，CPU发起写请求时，先检查写循环队列是否已满，若不满，则填 入写请求的类型、地址和写数据；

步骤2，访存加速器检测到写循环队列非空，则自动从写循环队列头指针 处读取写请求的类型、地址和数据；

步骤3，访存加速器将写请求发给内存控制器。

本发明还公开了一种采用上述访存方法及访存器的处理器。

本发明具有如下特点：

1、访存粒度灵活：访存粒度信息编码在type域中。访存粒度不受指令 集和Cache Line的限制。访存的每一个数据都是软件所需要的，主存带宽的 有效利用率得到提高。

2、可实现一些高级访存功能：通过在type域指定访存类型，然后访存 加速器解析执行，可实现诸如scatter/gather、链表读写等高级的访存操作。

3、type域可携带一些上层信息，如线程号、优先级等，使得访存加速器 可做一些高级的QoS调度。

4、可寻址空间使用SRAM才能更好地发挥加速器的作用。该设计中，CPU 和访存加速器需要对Read table、队列和队列指针读写几次才能完成一个请 求，因此可寻址空间的读写速度必须足够快，才能起到加速作用。SRAM比DRAM 访问速度快很多，适合用在这里。

本发明的技术效果：

1、利用片上RAM保存1个或多个读请求表（Read table），读请求表每 一项的内容包括请求类型域、目标地址域和数据域等所有读请求的必要信息， 由于本发明使用片上RAM记录并发请求的所有信息，并发请求的数量仅受限于 片上RAM的大小。

2、将读请求表的每一项按请求状态分成3类：空闲类、新请求类和完成 类，并且每一类请求项的入口地址分别使用循环队列进行存储，便于对读请求 的状态进行管理。本发明使用循环队列管理大量的读、写请求信息，避免轮询 多个请求的状态位，查询的次数大大减少，从而对大量并发且不相关的小粒度 访存请求具有明显的加速效果。

3、通过“新请求类”的循环队列的非空状态判断是否发起访存操作，通 过读取“新请求类”循环队列的内容，获取读请求在片上RAM存储的地址，如 此，访存加速器可以自行乱序发起访存操作，不需要软件进行控制，从而支持 访存请求的乱序执行，乱序返回，方便对大量访存请求实现有针对性的调度。

4、CPU软件通过“完成类”循环队列的非空状态判断是否有读请求完成， CPU通过读取“完成类”循环队列的内容，获取读请求返回数据在片上RAM中 的地址，避免CPU轮询多个请求的状态位，提高软件查找效率。