Tongxin xuebao (Jun 2016)
Graph partition based mapping algorithm on multiprocessors for streaming applications
Abstract
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.
