A GRASP for Placement and Routing of Dataflow Process Networks on Many-Core Architectures

We propose a GRASP heuristic for solving the joint problem of placement and routing of process networks from the field of compilation for embedded many core architectures. The method we propose consists in assigning applications expressed as dataflow process networks on homogeneous many core architectures by taking into account the routing maximal capacity of the arcs for the underlying Network-On-Chip. Our experiments illustrate the algorithm ability to efficiently obtain good quality routable assignments, within an acceptable computational time, even for large size instances. Moreover, validation of our approach is also realized on data coming from an embedded application of video processing.