唐麒，吴尚峰，施峻武，魏急波



基于图分割的流应用多处理器映射算法

唐麒，吴尚峰，施峻武，魏急波

（国防科技大学电子科学与工程学院，湖南长沙 410073）

为了充分利用多处理器平台所提供的计算资源，需要将应用以适当的方式映射到不同处理器，从而最大程度地挖掘应用所提供的并发性以满足应用严格的实时性要求。提出了并发图来量化、建模应用任务间的并发性，提出了一种基于自同步调度的并发图构建算法，并将任务映射问题转换成图分割问题，然后将并发图分割问题建模为纯0-1整数线性规划模型并采用ILP求解器获得最优解。采用了大量随机生成的同步数据流图以及一组实际应用对所提方法进行性能评估，实验结果表明所提方法性能优于已有算法。

同步数据流图；映射；多处理器；图分割

1 引言

同步数据流图（SDFG，synchronous dataflow graph）广泛用于建模现代流应用，包括视频、音频编解码、软件无线电等。为了满足消费者对应用的质量要求，这些应用的计算复杂度日益增加，给硬件设计带来了巨大挑战。许多应用有严格的实时性要求，例如，系统输入与输出间的延时或系统吞吐量要满足特定指标。为了满足这些要求，一种直接的方法是增加处理器时钟频率，然而，随着时钟频率的提升，系统能耗急剧增加，降低了这一方法的实用性。另外，时钟频率正逐渐接近物理极限，依靠这一方法增加计算能力难以为继。多处理器平台提供了另一种方案，可以在计算能力与功耗间达到更好的平衡，因此，在嵌入式系统设计中得到了大量应用。……