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

摘要

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