论文笔记1——《Code-size-aware Scheduling of Synchronous Dataflow Graphs on Multicore Systems》

2022-07-05 1352 words 3 minutes

Contents

Code-size-aware Scheduling of Synchronous Dataflow Graphs on Multicore Systems

Synchronous Dataflow Graphs (SDFGs)同步数据流图作为一种方便的表示流媒体应用的手段被广泛应用于数字信号处理和多媒体领域。流应用的性能标准由吞吐量throughput表示，代表应用的数据处理速率。SDFGs能能够描述流媒体应用的所有独特特性，即使每个功能模块在一个迭代周期里面的速率是不同的。

在上图的SDFG example中，节点称为actor，有向边称为channel，不同的communication data表示为不同大小的token,黑点为initial token。带有initial token的channel表示了迭代间的数据依赖，并且initial token还能显示周期的存在和防止死锁。
Self-Timed Execution (STE)能够很好地解决SDFG scheduling的两个问题：actors执行速度不同和存在周期问题。STE通过分析Maximum Cycle Mean (MCM)确认最大吞吐量。文章通过在重定时内重叠计算与通信，将STE应用在解决多核系统的核心间通信延迟问题上，并能提高吞吐量。
减少code size也是调度优化的一个目标，为了减少使用 duplication-enabled mapping映射提升了并行性进而提高吞吐量但增大code size问题，文章在SDFG还应用了code-size-aware mapping权衡了二者。
总结：
- 提出了communication-aware STE (CA-STE) scheduling方法
- 提出了四种CA-STE调度算法
- 提出了code-size-aware mapping方法用于平衡代码大小和吞吐量
- 展示了四种调度算法比两种代表性的DAG调度算法的优越性和code-size-aware mapping牺牲小部分吞吐量达到了减少代码的目的

1、 Communication-aware Scheduling for SDFGs
- 将SDFG转化为DAG再调度的方法耗时多，且一次迭代一张DAG,没有利用并行性。
- 直接调度SDFG的现有方法或是没有考虑多核，或是随着问题规模增大存在指数型时间增长限制。
2、 Code Size Reduction for SDFGs
- 传统优化没有考虑多核系统
- 运用Binding-based 映射的多核系统虽然code size小但吞吐量不如 duplication-enabled映射

1、SDFG
- SDFG是一个有向图G=<V,E>,每个图中的actor都存在minimum repetition number，满足下列等式，其中P(ch)、Q(ch)分别表示源、目标actor的token产生和消费速率，ϒ(α)表示minimum repetition number of α 。
  
  $P (ch) × ϒ(α_{src} (ch)) = Q(ch) × ϒ(α_{dst} (ch))$
- 迭代（重叠）的最小周期数称为MCM (Maximum Cycle Mean)
- HSDFG是指每个actor的速率都一样的SDFG。
2、 Hardware Platform
- 重叠的前提是假设核心间的通信操作与计算操作并不冲突。
- token传递采用FIFO队列
3、Objectives and Criteria
- 调度S(G)的吞吐量TH(S)如下列所示，其中f(S)为调度的展开因子unfolding factor，表示迭代的次数。
  $ TH(S) = \frac{f (S)}{|S (G)|} $
- 代码大小为所有映射方式的所有核心的代码大小总和

Communication-aware Self-timed Execution
- ALGORITHM 1: Generic CA-STE scheduling
- ALGORITHM 2: Get the earliest arriving time
Actor-to-core Allocation
- ALGORITHM 3: Actor-to-core allocation
Scheduling Algorithms
- multiple allocation disabled scheduling (MADS) - Earliest ready actor scheduling (eras) - Earliest finish actor scheduling (efas)
- multiple allocation enabled scheduling (MAES)
  - meras
  - mefas
Code-size-aware Mapping
- ALGORITHM 4: Code-size-aware mapping for meras