Fork me on GitHub

垃圾回收功耗优化论文阅读

发表于 | 分类于
字数统计: 2,329 | 阅读时长 ≈ 9

垃圾回收功耗优化论文阅读

1. Heap Compression for Memory-Constrained Java Environments

MS: Mark-Sweep
MC: Mark-Compact
MCC: Mark-Compact-Compress
MCL: Mark-Compact-Lazy
MCCL: Mark-Compact-Compress-Lazy

MS: “fregment problem”,即垃圾释放后空间碎片化问题

MC:

  • Mark结束后，将存活对象整理到堆的一侧，另一侧释放后作为完整的空闲区域。
  • 解决上述MS的问题。
  • 缺点：移动了对象，所以对对象的引用(reference)也需要更新。

MCC:

  • 标记存活对象并记录大小，由此得出剩余空间大小
  • 当剩余空间小于请求分配的空间时，压缩存活对象以增加可用空间。
  • 缺点：压缩和解压带来额外开销

MCL：

  • 当一个对象被创建后，实际上用到的可能只有一小部分。
  • 将大对象分解成几个子对象，当子对象遇到第一次写访问的时候才真正被allocated

MCCL：

  • MCC和MCL的结合，效果最优。

实现

  1. indirect object reference

    • 在handle pool中创建handle， 每个handle由指向instance的指针和指向class的指针构成。
    • 当handle pool空间用尽时，GC被触发。
    • 当handle pool的剩余空间小于某个阈值时，它会扩大。

  2. 压缩

  3. 解压缩
  4. 将大对象分解
  5. Lazy Allocation. 分解后的子对象直到第一次写访问时才被真正创建。

实验结果

  • 主要对比的是运行过程中堆的使用情况。
  • MCCL各阶段所花的时间与MC所花时间的对比结果：

激进的对象压缩

  • 原本，只有当compaction不足以提供足够的空闲空间用于分配时，compression才会被触发。
  • 从实验结果看，对于heap memory较小的情况来说，激进的对象压缩能够一定程度减少MCCL原本所花的时间。

去掉handle pool

由于handle pool的大小很难确定，所以去掉它会更合适。由此带来的代价是压缩率轻微下降。

相关工作

与能耗、GC相关的：

Chen et al. [14]，提出能够降低嵌入式Java应用程序能耗的方法。证明了提高GC的频率有助于增加可以放入低功耗操作模式的bank的数量。
[14] G. Chen, R. Shetty, M. Kandemir, N. Vijaykrishnan, M. J. Irwin, and M. Wolczko. Tuning garbage collection in an embedded Java environment. In the 8th International Symposium on High-Performance Computer Architecture (HPCA’02), Cambridge, MA, USA, Feb. 2002.

逃逸分析（例如[16]）提供了另一种解决方案，可以减少垃圾收集的负担。具体来说，逃逸分析器确定对象是否可以在堆栈中分配，以及对象是否仅由单个线程访问。这样，当相应的方法返回时，堆中分配的对象可以自动收集，并且可以安全地删除仅由单个线程访问的对象上的同步。Choi等人。[16] 显示出，对于他们的基准测试，多达70%的对象可以在堆栈中分配，11%到92%的锁操作可以安全删除。综上所述，他们观察到了从2%到23%的性能改进。

思路：模仿此文压缩算法，把所有对象压缩以后程序继续执行，经过多次gc后仍保持压缩的对象则放入低功耗内存中。（得先试一下每种负载中到底有多少冷对象）

2. Tuning garbage collection in an embedded Java environment

主要思路：
shuts off memory banks that do not hold live data.

个人疑问：

  • 模拟器如何实现shut off？
    • 读后感想：难道是把voltage设为0？

memory energy主要包括 dynamic energy 和 leakage energy

  • when a memory array is referenced or precharged, 动态功耗就会产生。
  • 本文主要解决的是leakage energy。方法：integrated hardware-software strategy.

实现

（疑问：模拟器能够区分RAM和ROM吗？）

  1. ROM一旦被激活就不会再关掉，因此它只有在首次引用时才会被激活，从而减少程序执行过程中没有用到的memory banks的leakage energy。
  2. 将SRAM划分为banks，根据是否装有存活对象决定是否断电。
  3. datapath energy = execution energy + gc energy
  4. gc energy = mark energy + sweep energy + compact energy(if used)
  5. memory energy = heap + runtime stack + KVM & class lib(see fig.2)
  6. 对SRAM采用的功耗模型与用于cache的模型类似。每个bank的大小以及bank的数量是可调的。
  7. 每个bank有三种状态：read/write, active（有存活对象但没有读写操作）, inactive（没有存活对象）
  8. read/write 和 active 状态产生动态功耗，inactive状态产生少量静态功耗

能耗特点及优化

A.断电法：

  1. 75.6%的heap energy来自leakage
  2. 将无用bank断电后，heap energy减少了31%， 90%是因为leakage的减少。
  3. 访问断电的bank会带来额外的开销。

提前gc法：

  1. 当对象变成垃圾后，在它被回收之前还是会持续产生能耗，因此提高gc的频率可以适当减低能耗，当然需要与gc本身的能耗做平衡。
  2. 提高gc频率的策略：k-allocation
    • 每经过k次allocation后就调用一次gc

B.调整位置法：

  1. 原本对象分配空间不考虑位置，即整个heap使用一个free list。现令每个bank单独维护一个free list，尽量将对象分配在active bank上。即active-bank-first allocation。
  2. Active Bank+：结合了active-bank-first allocation以及当现有的active bank无法满足分配要求时触发gc的策略。

以上，Active Bank+最佳。对比结果：

C.Compact 策略：

  1. 原本，heap将permanent object放在一个特定区域，现指定几个特定的bank作为这个特定的区域来存放permanent objects。
  2. 好处：当新的permanent object创建时无需移动dynamic object。
  3. 缺点：当permanent和dynamic对象都存在时需要同时激活至少2个bank。
  4. 结果：Active Bank+结合compact策略效果最优。

D.还有一个M&C2：
采用Lisp2算法代替KVM中原本的break table-based算法。（break table是更新reference时要用到的）
好处：能够处理不同大小的对象，并维持了对象被创建后的顺序，
坏处：在每个对象的header中需要添加一个4 byte的指针域。

MC2的好处：

  • 可以根据对象的生命周期移动对象。例如：生命周期相近的对象放到同一个bank中。
  • 更新reference更高效。

E.调整Heap大小以及bank数量：

相关工作

  1. Catthoor et al. [1998], Kandemir et al. [2000], and Vijaykrishnan et al. [2000] ：程序转换可以非常有效地降低以数组为主导的嵌入式应用程序的内存能量
  2. Lebeck et al. and Delaluzetal 提出了基于操作系统和基于编译器/硬件的优化策略，以降低动态功耗

3. Impact of GC Design on Power and Performance for Android

主要思路：
采用不同的GC策略，观察其对android设备的能耗和性能影响。

CMS

CMS: Dalvik Concurrent Mark-Sweep（安卓内部gc）

  1. Dalvik GC通常作为C编码的后台守护进程，在自己的本地Linux线程中并发运行，应用程序级Java变异器线程（mutator）也被调度为本地Linux线程

    • Dalvik的组成部分包括：GC deamon, JIT compiler, signal catcher, main thread, application threads
    • mutator thread: 即application thread

  2. CMS在每个collection cycle开始时将所有mutator threads 挂起，扫描heap roots, 然后在mark开始之前恢复被挂起的线程，随后并发进行mark。

  3. 当并发的mark阶段结束后，再次将mutator threads挂起，mark剩下的对象…然后恢复挂起的线程，再进行sweep。
  • targetUtil: 每次GC结束后用来调整heap大小的值
  • softLimit: 某个阈值
  • CSB 阈值：softLimit - 某个delta
  1. CMS 被触发的条件：
  • allocation 超过CSB阈值，触发background GC
  • allocation 超过softLimit 或 allocation失败， 触发 foreground GC
  • 显式GC，当 System.gc() 被调用时。

Generational CMS

  1. generational 即，假定 最近创建的对象有较低的存活概率，将堆分为young和mature两个部分。
  2. Minor GC 将young区域中存活的对象放到mature区域中。
  3. major GC则检测整个区域，包括young 和 mature
  4. Gen CMS 即 在 CMS的基础上，将新分配的对象当作young，将GC后存活的对象当作old。
  5. Gen CMS 与 CMS 触发GC的条件相同，只不过被触发的变成了minor GC，而major GC 只有当存活的对象已经超过了softLimit才会被触发。

CMSFly

  1. 当CMS进行 mark 操作时，有个stop-the-world阶段，CMSFly则解决这个问题。
  2. 当一个mutator thread的root已经被mark之后，CMSFly则立即通知它继续执行(本来是标记完一轮之后才继续执行)。

Concurrency Policies

  1. background: 由GC deamon完成
  2. foreground: 由mutator完成，与其他线程并行。

实验结果

  1. 增加堆大小并不一定能减少能耗
  2. 当GC全部是由GC deamon在后台完成时，能耗增加了。
  3. 调整heap 增长策略或并发性能减少能耗。

  4. foreground GC 改善minimum mutator utilization（与响应度相关的指标）。而background和generational策略则更适用于large heap。

  5. 不同的GC策略在不同benchmark上的能耗表现如下：(没有绝对更优，取决于benchmark以及系统配置)

相关工作

  1. 结合Mark-Sweep Compact和引用计数(An energy efficient garbage collector for Java embeded devices)
  2. Tuning garbage collection in an embedded Java environment，即文章2