A note on the energy-aware mapping for NoCs

The mapping problem for NoCs is to decide how to assign the tasks of an application onto the PEs of a network such that some objective function is optimized. The mapping problem is one of the most fundamental problems on the design of NoCs, since the application mapping onto the network greatly impacts both the performance and energy consumption of the NoC. It has been known that the energy-aware mapping problem is NP-hard even if an application graph is a caterpillar with vertex degree at most 4 and a network graph is a square mesh. This paper considers a special case of the problem which is solvable in polynomial time. We show that if an application graph is a caterpillar with vertex degree at most 3 and a network graph is a ladder, the problem can be solved in linear time.