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

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

Graph partition based mapping algorithm on multiprocessors for streaming applications

To take advantage of multiprocessor platform, it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements. Parallelism graph was proposed to quantify and model the concurrency among tasks of the application. An algorithm was also proposed to construct the parallelism graph based on the self-timed schedule and transform the mapping problem to a graph partitioning problem. The graph partitioning problem as a pure 0-1 integer linear programming model was further formulated and the ILP solver to find the optimal result. A lot of randomly generated synchronous dataflow graphs and a set of practical applications were used to evaluate the performance of the proposed method. The experimental results demonstrate that the proposed method outperforms available algorithms.