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

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 Spektrum
Volume17
Issue number2-3
DOIs
Publication statusPublished - 1995
Externally publishedYes

Fingerprint

Partitioning
Graph
Local search
High performance

Cite this

de Kock, E.A. ; Aarts, E.H.L. ; Essink, G. ; Jansen, R.E.J. ; Korst, J.H.M. / A variable-depth search algorithm for recursive bi-partitioning of signal flow graphs. In: OR Spektrum. 1995 ; Vol. 17, No. 2-3. pp. 159-172.
@article{e50aebaff80549d1876d9a97e61da4f4,
title = "A variable-depth search algorithm for recursive bi-partitioning of signal flow graphs",
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.",
author = "{de Kock}, E.A. and E.H.L. Aarts and G. Essink and R.E.J. Jansen and J.H.M. Korst",
year = "1995",
doi = "10.1007/BF01719261",
language = "English",
volume = "17",
pages = "159--172",
journal = "OR Spektrum",
issn = "0171-6468",
publisher = "Springer Verlag",
number = "2-3",

}

A variable-depth search algorithm for recursive bi-partitioning of signal flow graphs. / de Kock, E.A.; Aarts, E.H.L.; Essink, G.; Jansen, R.E.J.; Korst, J.H.M.

In: OR Spektrum, Vol. 17, No. 2-3, 1995, p. 159-172.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - de Kock, E.A.

AU - Aarts, E.H.L.

AU - Essink, G.

AU - Jansen, R.E.J.

AU - Korst, J.H.M.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

U2 - 10.1007/BF01719261

DO - 10.1007/BF01719261

M3 - Article

VL - 17

SP - 159

EP - 172

JO - OR Spektrum

JF - OR Spektrum

SN - 0171-6468

IS - 2-3

ER -