A variable-depth search algorithm for the recursive bipartitioning of signal flow graphs

We discuss the use of local search techniques for mapping video algorithms onto programmable high-performance video signal processors. The mapping problem is very complex due to many constraints that need to be satisfied in order to obtain a feasible solution. The complexity is reduced by decomposing the mapping problem into three subproblems, namely delay management, partitioning, and scheduling. We present the partitioning problem and the representation of video algorithms by signal flow graphs. Furthermore, we propose a solution strategy that is based on recursive bipartitioning of these graphs. The bipartitions are generated using a variable-depth search algorithm. The results demonstrate that the frequently cited flexibility of local search techniques can be successfully exploited in handling complicated problems.