A variable-depth search algorithm for recursive bi-partitioning of signal flow graphs

E.A. de Kock, E.H.L. Aarts, G. Essink, R.E.J. Jansen, J.H.M. Korst

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)159-172
Number of pages14
JournalOR Spectrum
Volume17
Issue number2-3
DOIs
Publication statusPublished - 1995
Externally publishedYes

Fingerprint

Dive into the research topics of 'A variable-depth search algorithm for recursive bi-partitioning of signal flow graphs'. Together they form a unique fingerprint.

Cite this