ACM通信

研究突出了

一种针对可重构硬件的无失速实时垃圾收集器

作者:大卫·f·培根，佩里·程，苏尼尔·舒克拉
ACM通信，2013年12月，第56卷第12期，第101-109页
10.1145/2534706.2534726
评论

频率缩放的终结促使架构师和开发人员在寻找性能时转向并行。然而，通用的MIMD并行可能是低效和耗电的，功率很快成为限制因素。这导致了对非传统芯片架构的性能研究，如gpu和其他更激进的架构。最根本的计算平台是可重构硬件，以现场可编程门阵列(fpga)的形式出现。

fpga现在有超过100万个可编程逻辑单元和8MB的片上“块RAM”，提供了大量的位级并行性，并结合单周期访问片上存储器。此外，由于内存以不同的36Kb单元分布在芯片上，潜在的内部带宽非常高。

然而，fpga的编程方法已经落后于它们的能力，因此降低了它们对通用计算的适用性。该领域的通用语言仍然是硬件描述语言(VHDL和Verilog)，其中惟一的抽象是位、位数组、寄存器、连接等等。编程它们的整个方法是围绕着合成一个恰好可以重新配置的芯片，而不是编程一个通用设备。

最近的研究集中在将抽象和可编程性的水平提高到高级基于软件的编程语言的水平:基于scala的Chisel框架，⁴基于c#的猕猴桃项目¹⁰以及开发了Lime语言的液态金属项目^3.基于Java。然而，到目前为止，无论程序员是用低级的HDLs还是像Chisel和Lime这样的高级语言编写，动态内存管理的使用才刚刚开始探索，^8，14而且垃圾回收的使用也不存在。

在本文中，我们提出了一个直接合成到硬件上的垃圾收集器，它能够收集一堆垃圾统一的并发对象完全。这些统一的堆(miniheaps)完全由固定形状的物体组成。因此，数据字段的大小和每个对象指针的位置是固定的。我们用内存布局的一些灵活性来换取收集器性能的大幅提升。在FPGA领域，这种权衡是有意义的:由于内存的分布式特性，通常可以构建流水线设计，其中管道的每个阶段都维护自己的内部数据结构，这些数据结构能够与其他管道阶段并行访问它们的本地块RAM。此外，固定数据布局可以提供数量级的更好性能，因为它们允许设计确定地处理每个时钟周期的一个操作。

从算法上讲，我们的收集器是汤坂式的一开始快照收集器，¹⁶线性扫描。通过利用像双端口存储器这样的硬件结构，在一个周期内同时读写寄存器的能力，以及原子地在整个系统中分发控制信号，我们能够开发一种收集器从来没有干扰突变体。此外，mutator对内存有单周期访问。仲裁电路将一些收集器操作延迟一个周期，以支持mutator操作，但是收集器即使在每个周期执行一个内存操作(分配限制为每隔一个周期一次)，也可以跟上mutator。

我们的无失速收集器可以直接使用用硬件描述语言手写的程序。或者，它也可以是高级语言使用的硬件“运行时系统”的一部分^3.，10系统包括动态内存分配。为了进行评估，我们还实现了一个stop-the-world变体和一个malloc/free-style系统。使用一个分配非常密集的应用程序，从内存使用、时钟频率、吞吐量(周期和墙上时钟时间)和应用程序摊位方面比较这三个收集器。我们还提出了0失速实时行为所需的最小堆大小的解析封闭最差情况边界，并进行了经验验证。更多的细节，例如能源消耗和额外的基准测试，可以在原始论文中找到。⁶

回到顶部

2.FPGA的背景

fpga是可编程逻辑设备，由许多离散的资源单元组成，这些资源单元基于用户应用程序启用和连接。资源包括可用于实现组合逻辑的查找表(lut)和可用于实现顺序逻辑或状态的触发器。在我们在这项工作中使用的Xilinx fpga上，lut和人字拖被分组片，这是报告fpga资源消耗的标准单位。

对于这项工作特别重要的是可在FPGA上使用的称为块ram (BRAMs)的离散内存块。BRAMs是嵌入FPGA内的双端口专用内存结构，用于实现资源高效的随机和顺序访问存储器。

Xilinx Virtex-5 LX330T¹⁵我们在本文中使用的设备的BRAM总容量为1.45MB。Virtex-5 FPGA中的单个BRAM可以存储高达36Kb的内存。BRAM的一个重要特征是它可以以各种形式(可寻址范围和数据宽度组合)组织起来。例如，一个36Kb BRAM可以配置为36K × 1 (36K 1位位置)，16K × 2,8k × 4, 4K × 9, 2K × 18，或1K × 36内存。

一个36Kb BRAM也可以作为两个独立的18Kb BRAM使用。通过级联多个bram可以构建更大的逻辑内存结构。设计中任何不是18Kb倍数的逻辑内存结构都会导致量化(或者，用内存系统的说法，“碎片化”)。

根据设计中的逻辑内存结构，量化效果可能相当可观(将在第7节中讨论)。BRAM可以用作真正的双端口(TDP) RAM，提供两个完全独立的读写端口。此外，每个端口支持以下三种读写操作模式:先写后读(以前存储的数据在读总线上可用)、写后读(新写入的数据在读总线上可用)和不更改(读数据总线输出保持不变)。我们的收集器大量使用了先读后写的功能，比如yuasa风格的写障碍。¹⁶

BRAMs也可以配置为FIFOs而不是随机访问内存;我们利用这个特性在收集器的跟踪阶段实现标记队列。

FPGA通常封装在专门的片外DRAM和/或SRAM板上，可通过为FPGA合成的内存控制器访问。这样的内存可以用来实现更大的堆结构。然而，我们在本文中没有考虑使用DRAM或SRAM，因为我们关注的是具有高度确定性(单周期)行为的高性能设计。

回到顶部

3.内存架构

内存体系结构，即对象字段在内存中布局的方式，以及维护空闲列表的方式，是我们对malloc/free和垃圾收集抽象的共同支持。在本节中，我们将描述我们的内存体系结构以及一些替代方案，并从质量上讨论它们之间的权衡。在第7节中，我们将定量地探讨一些折衷方案。

由于FPGA中的内存结构通常而且必然比传统软件堆中的内存结构更加统一，因此我们将内存组织为一个或多个miniheaps，其中对象在指针和数据字段之间的划分方面具有固定的大小和“形状”。

3.1.Miniheap接口

每个小堆都有一个接口，允许对象分配(以及在使用显式内存管理时释放)，并允许对单个数据字段进行读写操作。在本文中，我们只考虑具有一个或两个指针字段和一个或两个数据字段的小堆。这对于实现堆栈、列表、队列和树数据结构已经足够了。用于包处理、压缩等常见应用的FPGA模块都包含在这样的结构中。

我们的设计允许任意数量的数据字段。对于malloc风格的内存，增加指针字段的数量是很简单的。但是，对于垃圾收集的内存，扩展将需要额外的逻辑。我们相信这是相对简单的实现(包括下面的细节)，但本文中的实验结果仅限于单指针和双指针对象。

3.2.Miniheap malloc / free

有许多方法可以实现3.1节中的接口。从根本上说，这代表了可用并行操作的数量和所消耗的硬件资源数量之间的时间/空间权衡。

对于fpga，需要指定具有所需数据宽度和条目数量的逻辑内存块，合成工具试图使用各种打包策略尽可能高效地分配所需数量的单个块ram。我们将这种逻辑内存块的BRAMs称为布拉姆集．

在我们的设计中，我们为对象中的每个字段使用一个BRAM集。例如，如果有两个指针字段和一个数据字段，那么就有三个BRAM集。

非指针字段具有与其数据类型相关的自然宽度(例如32位)。但是，对于小堆大小N，指针字段只需为log₂N位宽。因为FPGA上的数据宽度是完全可定制的，所以我们精确地使用所需的位数。因此，更大的迷你堆的大小将增加，这不仅是因为条目的数量，还因为指针字段本身会变大。像在软件中一样，指针值0被保留为表示“零，所以是一个小堆大小N真的只能储存N1对象。

中显示了内存管理器的高级框图图1．它显示了内存模块的主要数据和控制字段，尽管许多信号已被省略以简化图。为了清晰地表示，它显示了一个对象字段，指针类型(指针内存)，存储在单个BRAM集合中。第二个BRAM集(Free Stack)用于存储一堆空闲对象。使用BRAM的先读后写属性，我们可以使用BRAM集合(free Stack)的端口B来实现这两个函数(alloc和free)，而不使用端口A。

对于具有f领域,有fBRAM设置了用于写和读值的相关接口(但是不一个额外的地址端口)。无论对象有多少字段，都只有一个空闲堆栈。

的Alloc信号是一种用于实现malloc操作。寄存器用于保存堆栈顶部的值。假设它非零，它被递减，然后在Free Stack BRAM集合的B端口上显示读模式。然后返回指向空闲字段的结果指针(Addr Alloc会)，但也被馈送到指针内存的B端口写模式，并将写入值硬连接到000(或“零”)。

要释放对象，将指针显示给内存管理器(Addr自由)．栈顶寄存器被用作B端口上设置的Free Stack BRAM的地址，在写模式下，带有数据值Addr自由．然后对栈顶寄存器进行递增。这将导致指向已释放对象的指针被推入空闲堆栈。

为读取或写入指针内存中的字段，将Addr读/写是呈现的，如果是书写，则用指针写．这使用BRAM的端口A设置为读或写模式，返回一个值指针值前一种情况是港口。

注意，这种设计利用了BRAMs的双移植特性，允许读写操作与分配或释放操作并行进行。

线程空闲列表．一种常见的软件优化方法不是将空闲对象表示为指针堆栈，而是将其表示为贯穿未使用对象的链表(即通过第一个指针字段的链表)。由于分配对象集和空闲对象集是互斥的，这种空间优化本质上是自由模缓存局部性效应。

然而，在硬件中，这将导致包含第一个指针的BRAM集合上的资源争用(因为它正在执行双重任务)。因此并行性降低了:对第一个指针的读或写操作不能在同一个周期内执行malloc或免费的，而后者需要两个循环而不是一个。我们选择使用堆栈是经过深思熟虑的，因为适度增加的空间使用比潜在的资源争用成本要低得多。

回到顶部

4.垃圾收集器的设计

现在，我们将在硬件中描述停止世界和完全并发收集器的实现。在软件上，这两种类型的收集器的体系结构是完全不同的。在硬件方面，由于使用了相同的基本结构和接口，所以两者之间的差距要小得多。

并发收集器有一些额外的数据结构(用BRAMs实现)，需要更仔细地分配BRAM端口以避免争用，但这些特性不会对停止世界收集器使用它产生负面影响。因此，我们将介绍并发收集器设计，这里只提到stop-the-world变体省略了来自根引擎的影子寄存器、来自跟踪引擎的写障碍寄存器和逻辑，以及来自扫描引擎的所用映射和逻辑。我们的设计包含三个独立的组件，分别处理原子根快照、跟踪和扫描。

4.1.背景:汤浅的快照算法

在深入研究实现的细节之前，我们先描述一下Yuasa的快照算法¹⁶这是我们实现的基础。虽然硬件中的机制非常不同，但有趣的是，在硬件中实现可以使我们获得比最先进的软件算法更高程度的并发性和确定性，但不必合并在此期间开发的更复杂的算法技术。

快照算法的基本原理是，当开始收集时，a逻辑获取堆的快照。然后，收集器在这个逻辑快照中运行，并收集快照时的所有垃圾。

在Yuasa的原始算法中，快照由寄存器、堆栈和全局变量组成。这组指针是同步收集的(从那时起，许多研究致力于避免在快照时间或相变期间需要任何全局同步²)．

一旦收集了根，就允许突变器继续运行，收集器同时运行，标记根的传递闭包。

如果mutator同时修改堆，它的唯一义务是确保收集器仍然可以找到快照时堆中存在的所有对象。这是通过使用一个写障碍:在任何指针被覆盖之前，它会被记录在缓冲区中，并作为根对象进行收集。

在收集期间新分配的对象不符合收集条件(按照收集器文献的说法，它们被“分配为黑色”)。

快照算法的优点是简单和确定性。由于它在某一时刻对一个逻辑快照进行操作，因此算法的不变量很容易描述。此外，终止是简单的和确定的，因为工作量在收集开始的那一刻是有限的。

4.2.根快照

并发收集器使用上面描述的“开始快照”算法。Yuasa的原始算法在记录根时需要全局暂停;从那时起，实时收集器一直努力减少根快照所需的暂停时间。在硬件中，我们可以利用硬件中的并行性和同步性来完全消除快照暂停。

快照必须考虑两种类型的根:寄存器中的根和堆栈上的根。图2显示根快照模块，简化为显示单个堆栈和单个寄存器。

快照由GC输入信号，在采集开始时，在一个时钟周期内该信号较高。快照被定义为开始时内存的状态下一个周期后GC信号是高。这允许一些设置时间并减少同步需求。请注意，如果GC在收集已经进行时断言信号，然后忽略触发器。

寄存器快照是通过使用影子寄存器获得的。在循环之后GC信号越高，寄存器的值就被复制到影子寄存器中。即使在同一个循环中，mutator也写入了寄存器，也会发生这种情况，因为新值直到循环结束才会被锁存。

栈快照是通过在栈顶寄存器之外拥有另一个寄存器(称为扫描指针)来获得的。在同样的循环中GC信号越高，堆栈顶部指针的值减去1就会被写入扫描指针(因为堆栈顶部指向实际顶部值以上的条目)。从下面的循环开始，扫描指针被用作包含堆栈的BRAM集合的端口B的源地址，并且指针被读取，通过MUX并出现在根加快照模块的端口。扫描指针也会减少，以便为接下来的循环做准备。

注意，mutator可以通过BRAM集合的端口A继续使用堆栈，而快照使用端口b。由于mutator不能比收集器读取它们更快地从堆栈弹出值，所以快照包含的属性被保留了下来完全那些存在于循环中的根GC信号。

图中省略的一个细节是，需要状态机将堆栈和影子寄存器的值通过MUX排列到根加端口。注意，必须首先处理来自堆栈的值，因为堆栈快照技术依赖于在没有任何显式同步的情况下保持在mutator之前。

如果需要多个堆栈，那么将需要一个“影子”堆栈来保存值，因为它们是在突变器可以覆盖它们之前被读取的，然后它们可以被排序到根加端口。

正如在第4.4节中所看到的，(仅)由导致空闲空间低于阈值的分配触发收集。因此，根快照逻辑的生成只需要考虑可能发生这种情况的硬件状态。任何不在这些状态下的寄存器或堆栈都可以被安全地忽略。

4.3.跟踪

跟踪引擎以及单个指针内存(对应于对象中的单个指针字段)显示在图3．的malloc/free风格的内存管理器提供相同的mutator接口图1：地址为读/写，指针为写,指针值除了外部接口Addr自由替换为内部接口(用红色表示)Addr清除，它是由Sweep模块生成的(在第4.4节中描述)。

惟一的附加接口是根加端口，它从与根引擎同名的输出端口获取输入图2．

当它执行时，有三个指针源供引擎跟踪:从快照中外部添加的根，从指针内存中内部跟踪的根，以及从指针内存中覆盖的指针(用yuasa风格的屏障捕获，以维护快照属性)。不同的指针源流经MUX，在每个周期中，一个指针可以被呈现给标记映射，它包含每个N内存位置。

使用BRAM先读后写模式时，先读取旧的标记值，然后无条件地将标记值设置为1。如果旧的标记值为0，则该指针尚未被遍历，因此使用旧标记值的反值(由气泡指示)来控制是否将该指针添加到标记队列(注意，这意味着标记队列中的所有值都已被过滤，因此最多N1个值可以通过队列)。

来自标记队列的指针在指针内存的B端口上以读地址的形式显示，如果获取的值是非空的，则通过MUX将它们提供给标记步骤。

写屏障是通过在先读后写模式下使用指针存储器BRAM的A端口实现的。当mutator写入一个指针时，旧的值首先被读出并放入Barrier Reg中。这随后通过MUX发送并标记(时间和仲裁将在下面讨论)。

考虑到标记过程中涉及三个bram，处理一个指针需要3个周期。但是，标记引擎被实现为号管道，因此它能够维持一个周期一个指针的吞吐量。

跟踪引擎配对．对于具有两个指针的对象，两个跟踪引擎配对在一起以最大化资源使用(图中没有显示这一点)。因为每个跟踪引擎只使用标记映射的一个端口，所以两个引擎都可以同时标记。

下一个要标记的项目总是从较长的队列中取出。当只有一个项目要排队时，它被放在较短的队列中。使用这种设计，我们将两个队列中的每个队列的大小设置为3N/ 8 +R(R是根的最大数量)，它保证队列永远不会溢出。

在每个周期中，从队列中删除一个指针，检查检索对象中的两个指针，并可能标记和入队。

为了减少写屏障造成的干扰，我们设计了两个写屏障寄存器。写障碍值在形成一对之前不会被处理，并且加上有两个标记队列的事实，标记引擎可以每隔一个周期进行一次处理，即使应用程序每个周期执行一次写。

痕量终止和WCET效应．标记的终止协议很简单:一旦弹出标记队列的最后一项(两个标记队列都变为空)，跟踪引擎需要2或3个周期才能完成当前的管道。如果堆返回的两个指针为空，则标记进程将在第二个循环中终止，因为在这种情况下不需要读取标记位。否则，将读取非空指针的标记位，以确保两个指针都被标记，在这种情况下，标记阶段在第三个循环中终止。

在第一个终止周期之后到达的写障碍值可以被忽略，因为快照属性必须新分配它们，或者通过跟踪堆发现它们。

但是，请注意，一些(现实的)数据结构，特别是链表，会导致一种病态行为，在这种行为中，一个指针被标记，从队列中删除，它将显示为空，然后2个周期后，链表中的下一个指针将进入队列。因此，当管道可以维持每个周期标记一个对象时，管道气泡将会出现，从而降低吞吐量。

4.4.全面

跟踪完成后，开始扫描阶段，在此阶段回收内存。高层设计如图所示图4．扫描引擎还处理分配请求并维护指向空闲内存(free stack)的指针堆栈。这里的标记地图和上面的标记地图是一样的图3．

当一个Alloc请求从mutator到达时，栈顶寄存器用于从空闲堆栈中删除指向空闲对象的指针，并且堆栈指针被减号。如果堆栈指针低于某个级别(我们通常使用25%)，则通过提升GC连接到根快照引擎的信号(图2)．

从空闲堆栈弹出的地址返回给Addr Alloc会端口。它还用于将used Map中的对象条目设置为01，意思是“新分配的”(因此是“黑色的”)。的值00表示“空闲”，在这种情况下，对象在空闲堆栈上。

跟踪完成后，将在下一个周期中开始扫描。扫描是一种简单的线性扫描。扫描指针初始化为1(因为槽位0是零)，并且在每个循环中(被分配抢占时除外)扫描指针同时呈现给标记映射和已用映射。

如果标记了对象，则将其Used Map条目设置为10．如果一个对象没有被标记，而它使用的映射条目被标记10(而且门)，那么使用的映射条目将重置为00．虽然只使用了3种状态，但特殊的位模式选择避免了关键路径中不必要的逻辑。产生的信号还用于控制是否释放当前的扫描指针地址。如果是，则将其推入空闲堆栈，并在Addr清除端口，该端口连接到标记引擎，以便将释放的数据值归零。

注意，由于清除只在扫描期间发生，所以在清除和标记之间，跟踪引擎中的指针内存端口不存在争用。此外，分配和释放可能发生在同一个周期中:使用先读后写模式访问栈顶，并作为Addr Alloc会，然后新释放的对象被推回。

当分配一个对象时，它在Mark Map中的条目为不设置(否则需要额外的联锁)。这意味着跟踪引擎可能会在其标记管道中遇到新分配的对象(通过堆中新安装的指针)，尽管最多一次，因为它们随后将被标记。这也会影响WCET分析，我们将在下一节中看到。

回到顶部

5.实时的行为

首先，我们注意到，由于实时收集器的设计允许突变和收集在单个周期中无条件地同时发生，因此最小突变器利用率(MMU⁷)，为100%，除非专用给堆的资源不足。

此外，与基于软件的收集器不同，^5，11系统是完全确定的，因为我们可以分析最坏情况下的行为直到(机器)周期。

鉴于R是根的最大个数，N是堆的大小，那么垃圾收集的最坏情况时间(以周期为单位)是多少

在哪里T_R是快照根的时候了，T_米是时间(以周期为单位)来标记，T_年代打扫的时间到了吗T_W是在标记过程中写障碍所损失的时间，T_X在标记期间，是否有时间损失在变黑新分配的对象上T_一个是在清扫期间分配的时间损失。

在最坏的情况下，如果不了解应用程序，

这些量的推理如下。在快照阶段，我们可以每个周期将一个根放入标记队列中，加上一个周期来开始和结束该阶段，占R+ 2。在标记过程中，可能会有N堆中的对象，配置为一个链表，这导致标记管道在每个对象上暂停两个周期，加上3个周期终止。扫描不受应用程序特性的影响，总是需要N周期。通过mutator写障碍抢占收集器(T_W)不考虑最坏情况分析，因为写障碍工作与收集器暂停重叠。额外的标记操作使新分配的对象变黑(T_X)也只是填补失速周期。

我们的设计允许分配操作在每一个周期，但是分配会抢占扫描阶段，这意味着这样的分配速率只能在短时间内维持。最大的可持续分配率是0.5，否则在清理完成之前堆就会被耗尽。因此T_一个＝N而且

5.1.特定于应用程序的分析

实时分析通常至少利用一些特定于应用程序的知识。对于基于硬件的系统来说尤其如此。幸运的是，这种系统的结构使得这些因素更有可能被高精度地量化，例如通过观察合成设计中每个时钟周期的操作。

让为每个周期的平均突变数(1)，为每个周期的平均分配数(< 0.5)米在任何时候堆中活动数据对象的最大数量(米<N)．这样我们就可以更精确地估计

请注意,这两个而且只能对a取平均值时间窗口保证小于或等于它们所影响的相;米是一个安全的窗口大小。

最大的不准确性仍然是由于标记过程中的管道停顿，对于这种情况，最差情况和平均情况的行为可能非常不同。因此,我们让B为管道档位数(0B2米)，所以更精确的标记界限是(同时也提高)．

对于链表，B = 2米;对于三个链表，每个链表都有自己的根，B= 0。我们假设，对于被认为是没有后缘的森林的堆，B由宽度1的级别数加上宽度2的级别数所限制(当宽度为3或更大时，有足够的并行性来保持3级管道充满并避免停顿)。

使用这些特定于应用程序的估计，我们就能够将收集的最坏情况执行时间(WCET)限定为

5.2.最小堆大小

一旦知道了收集的最坏情况执行时间，我们就可以求解收集器可以以实时行为(零档位)运行的最小堆大小。注意，如果故意选择的堆大小低于这个最小值，分配器可能会遇到内存不足的情况。作为起点，米对象必须对实时数据可用。虽然收集需要时间T_马克斯发生,另一个T_马克斯可以分配对象。然而，也可能有T_马克斯当收集开始时，从上一个循环中漂浮垃圾。因此，最小堆大小为

如果我们表示非大小相关的部分T_马克斯由式(3)得到

然后我们可以解出

回到顶部

6.实验方法

由于我们已经实现了第一个此类收集器，所以不能利用预先存在的基准集进行评估。这里，我们展示了一个分配密集型微基准测试的结果，它是一个双端队列(deque)，在许多应用程序中都经常出现。在我们的HDL实现中，可以通过将双链表推到前面或后面进行修改。工作负载由此类操作的伪随机序列组成，同时保持活动数据的最大数量接近但不超过8192。因为几乎不需要对列表元素执行计算，所以这个基准测试需要大量的分配。此外，数据结构的线性性质阻止了收集器利用图扇出的优势。这两个因素加在一起给收集器带来了巨大的挑战。

一定要注意的是，由于硬件和收集器实现中的确定性非常高，这种微基准测试可以提供比在软件中运行的基于cpu的收集器的典型评估更准确的性能情况。没有缓存效果，没有时间切片，也没有中断。因为没有这些更高阶的影响，所以由收集器呈现给mutator的性能行为(反之亦然)完全由内存管理API以周期精确的级别捕获。我们通过实验验证了这一点，表明对收集时间和最小实时堆大小的估计(来自第5.1节)非常准确。

给定的微基准可以与三种内存管理实现中的一种(Malloc、stop-the-world GC和实时GC)配对。此外，这些都是由小堆的大小参数化的，对于收集器来说，是开始收集的触发点(尽管在大多数情况下，我们只是在空闲空间低于25%时触发)。我们称这些设计点．

我们的实验是在Xilinx Virtex-5 LX330T上使用Xilinx ISE 13.4合成工具进行的，¹⁵这是Virtex5 LXT产品线中最大的FPGA。LX330T有51840个片和11664 kb (1.45MB)的块RAM。该芯片采用65纳米技术制造，理论上可以达到550兆赫，但实际设计通常在100到300兆赫之间运行。

回到顶部

7.评价

我们首先从静态资源的角度分析3种内存管理器的成本:smalloc/free(“Malloc”)、stop-the-world收集(“STW”)和实时并发收集(“RTGC”)。出于这些目的，我们在没有任何应用程序的情况下合成内存管理器。这可以深入了解内存管理本身的成本，还提供了实际应用程序的性能上限(因为它们只能使用更多的资源或导致时钟频率下降)。

我们用2的幂来计算堆大小(在对象中)从1K到64K的设计点。为了实现这些目的，我们使用了一个包含两个指针和一个32位数据字段的对象布局。为了简洁起见，我们省略了非bram逻辑资源的详细用法。注意，对于所有情况，所有3个变体和所有堆大小的逻辑消耗都低于1%就足够了。

图5显示BRAM消费。因为我们为堆大小选择了2的幂，所以最大的堆大小只使用60%的BRAM资源(当然可以自由选择其他大小)。在较小的堆大小下，垃圾收集器消耗的BRAMs比Malloc多80%。但是，在实际的堆大小下，这个数字下降到24%。此外，RTGC需要比STW多212%的内存，因为它需要额外的2位宽Used Map来处理并发分配。碎片是明显的，但不是主要因素，范围从Malloc的1131%到垃圾收集的1153%不等。与前面一样，在更大的堆大小下，碎片减少。通过更仔细地选择堆大小(不一定是2的幂)，注意BRAMs以18Kb的块提供，可以避免一些浪费。然而，在BRAMs的量化过程中，当它们连接在一起形成更大的记忆时，一些碎片丢失是固有的。

最后,图6显示合成的时钟频率在不同的设计点。在这里，我们可以看到更复杂的垃圾收集逻辑带来的显著影响:尽管它消耗的面积相对较小，但在所有设计点上，垃圾收集的时钟频率明显比Malloc慢(1539%)。另一方面，STW和RTGC之间的差异很小，RTGC通常更快。不管内存管理的形式如何，当堆变大时，时钟频率都会下降。但是，正如我们将在下面看到的，总体时钟速率很可能受到应用程序逻辑而不是收集器逻辑的限制。

7.1.吞吐量

到目前为止，我们已经讨论了在没有应用程序的情况下内存管理的成本;我们现在考虑当内存管理器“链接”到Deque微基准时会发生什么。与前一节不同的是，在前一节中，我们主要关注广泛的内存大小对静态芯片资源的影响，而在这里，我们使用一个跟踪，使用单个最大活动数据集来关注较小的内存大小范围米如前所述= 8192。然后改变堆大小N从米到2米的小数增量米/ 10。当我们使内存稀缺时，分辨率也增加到米/100表示系统在非常紧的条件下的行为。每个设计点都需要对影响频率、功率和执行时间的硬件设计进行全面综合。

图7显示所有3个方案在堆大小变化时基准测试的吞吐量。为了理解各种影响的相互作用，我们不仅在周期持续时间上检查吞吐量，而且由于可合成时钟频率的变化，在物理时间上也检查吞吐量。Deque基准测试显示了不同的行为。分配和突变率要高得多(= 0.07,= 0.13)，对捕集剂活性更为敏感。见图7 (b)，即使在堆大小N= 2米， STW消耗明显更多的周期，上升到几乎两倍的周期N= 1.1米．相比之下，RTGC消耗的周期比Malloc略少，直到它开始经历失速周期(非实时行为)N= 1.4米因为它落在突变子后面。

Deque基准测试具有非常简单的逻辑，因此收集器引入的任何频率限制都会被放大。这一效果在图7 (b): Malloc的合成频率更高，可以弥补RTGC在周期上的微小优势，平均减少25%的时间。STW受到较低时钟频率和由于同步收集而产生的额外周期的综合影响更大。平均而言，RTGC比STW快14%，而且不会中断应用程序。

这些测量结果揭示了一些令人惊讶的趋势，这与软件收集者的预期折衷完全相反:RTGC实际上是更快，更确定，需要更少的堆空间比STW !似乎没有理由使用STW，因为在硬件中实现并发的自然优势完全取代了传统的延迟与带宽权衡。

此外，RTGC允许应用程序以远低于最大活动集的倍数运行米比软件中的实时或停止世界收集器都要容易。RTGC也只比Malloc稍微慢一点，这意味着抽象的成本是可以接受的。我们没有展示其他应用程序的结果，但要注意，正如预测的那样，随着应用程序变得更加复杂，这种性能差距会减小。

7.2.实时边界的验证

因为我们的并发收集器的设计和分析旨在实现周期精确，所以我们可以验证收集器的时间和空间边界，并期望它们能够完全满足。图8显示用于垃圾收集的实际时间和分析上界(T_马克斯注意，我们同时显示了用于垃圾收集的平均时间和最大时间。堆大小的选择比前面的图要紧凑得多，因为我们这里的重点是收集器在压力(接近)时的行为N_最小值为方便起见，我们将堆大小表示为分数(N/米)的最大实时数据量，因为我们的边界几乎是线性的，当考虑米而且N．

收集的平均时间总是小于预测的最坏情况，两个程序的实际差异约为10%。我们还显示了基准所经历的停顿量作为总时间的一部分。在较大的堆尺寸下，没有摊位。随着堆大小的减小，收集器将无法跟上，mutator的分配请求将失败。对于分配密集的Deque基准，失效点出现在1.43 ×处米．我们的预测N_最小值1.457值正确地高于实际故障点。

因为平均收集时间包括一个程序的多个阶段，所以它可以显著低于最大收集时间。我们看到了两者之间的差距T_马克斯当考虑最大收集时间而不是平均收集时间时，收集时间从10%缩短到约2%和6%。的空间,N_最小值只有在每次收集时堆都足够的情况下才会有足够的堆空间，因此只有在最坏情况下才有足够的堆空间。空间限制在摊位开始时的3%以内。我们的时间和空间界限不仅经过经验验证，而且很紧。

通常，随着堆大小的减小，用于单个收集的时间会减少，因为扫描阶段将花费更少的时间。令人惊讶的是，即使在堆大小低于堆大小时也会发生这种情况N_最小值．然而，低于这个安全点会导致突变器停止，但完全不会惩罚收集器。事实上，由于mutator被暂停，它不能再干扰收集器，收集器还会加速收集，尽管速度非常小。当然，由于总体目标是避免突变者停滞，在这种情况下操作是不可取的。

回到顶部

8.相关工作

我们只提供了相关工作的简要总结，并建议读者阅读我们的完整论文⁶更多细节和引用。

关于在可重构硬件中支持高级内存抽象的工作很少，关于垃圾收集的工作更是少之又少。Simsa和辛格¹⁴已经研究了使用malloc/free编译成VHDL或Bluespec的C子程序。飞跃、便¹提供一个可扩展的内存抽象，它呈现一个BRAM接口，但如果结构太大而不能适应，则使用片外RAM，并透明地使用片内BRAM作为缓存。这样的系统可以与我们的系统相结合，以提供更大的虚拟化内存，尽管要牺牲确定性和吞吐量。

迈耶¹²在Altera APEX FPGA上构建了专用处理器和相关的垃圾回收协处理器。然而，设计和目标非常不同。Meyer的收集器适用于分配在DRAM中的通用堆，也适用于在大部分传统CPU上运行的程序。收集器是用微编码的协处理器实现的，通用CPU是用与指针相关的特殊支持修改的。由于这种硬件中软件的方法，暂停可以达到500个周期。相比之下，我们的方法是一种完全自定义的逻辑，它与内存集成得更紧密，对于“程序”也合成到硬件中，并具有确定性的单周期内存访问。这允许我们实现零停顿。

还有垃圾收集系统^9，13其中FPGA参与垃圾收集堆，但不执行收集本身。还有一些人设计了特殊用途的asic，它们执行自定义的集合算法或提供一组指令来加速更一般的一类算法。这些是根本不同的，因为堆在CPU上而不是FPGA上。

回到顶部

9.结论

我们已经描述了第一个完全合成到硬件中的垃圾收集器的设计、实现和评估。实时版本导致零变异子的干扰周期。

仔细的实现允许收集器的最坏情况执行时间(WCET)的封闭形式的解析解决方案，以及实现实时行为的堆大小的下限。这些边界也是周期精确的。

在软件中，在吞吐量、延迟和空间方面，在停止世界和实时收集之间有很大的权衡。我们的测量表明，在硬件中实时收集器更快，有更低的(零)延迟，可以在更少的空间中有效运行。

这种性能和确定性并非没有代价:我们的收集器只支持单一固定对象布局。支持具有更多指针的更大对象是我们设计的一个相对简单的扩展;支持多对象布局更具挑战性，但我们相信可以在不牺牲基本优势的情况下实现。

垃圾回收程序合成到硬件是实用和可实现的!

回到顶部

致谢

我们感谢IBM研究中心液态金属团队的成员，他们贡献了见解、基础设施和令人兴奋的工作环境:Joshua Auerbach、Ioana Baldini、Stephen Fink和Rodric Rabbah。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2013 ACM, Inc.

---

没有发现记录