ABSTRACT
This chapter looks into the various strategies adopted to solve the problem. It also looks into the mathematical definition of the problem. The chapter discusses various strategies for application mapping. While integer linear programming (ILP)-based approaches produce the best results, the overall computation time is high, restricting its usage to only a few cores in the application graph. The chapter also discusses an ILP formulation of the application mapping problem and uses the following variables to express the constraints and the objective function. It explores one of the constructive techniques, known as binomial mapping (BMAP) algorithm. In constructive heuristics, partial solutions are generated sequentially, and at the end the final mapping solution is obtained. Some of the techniques perform an additional iterative improvement phase after getting the initial solution. The chapter provides the context of mesh topology. The on-chip network design flow in BMAP and shows a task-level decomposition of a video object plane decoder application.
