Recursive Bipartitioning of Signal Flow Graphs for Programmable Video Signal Processors
Emile Aarts, Gerben Essink, E. A. de Kock · 1996
We consider the problem of partitioning video algorithms over an arbitrary network of highperformance video signal processors. The partitioning problem under consideration is very hard due to the many constraints that need to be satis#ed. We present a solution strategy based on a recursive bipartitioning approach, which e#ectively handles the routing of the data #ows through the network under time and resource constraints. The bipartitions are generated using a variable-depth search algorithm. We present results for industrially relevant video algorithms. Key words. Graph partitioning, local search, realtime video signal processing. 1 Introduction At Philips Research, programmable video signal processors #VSPs# have been developed for #exible and rapid evaluation of video algorithms in real time. Programming of VSPs is done by mapping a speci#cation, given by a signal #ow graph #SFG#, onto a given network of VSPs. The mapping problem can be viewed as a feasibility problem in which o...