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

The authors 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. The authors present the partitioning problem and the representation of video algorithms by signal flow graphs. Furthermore, they 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 frequency cited flexibility of local search techniques can be successfully exploited in handling complicated problems.