A method for avoiding loops while decomposing the task description graph in system-level synthesis

In system-level synthesis, the graph describing the task may consist of a great number of vertices, thus the design algorithms (e.g. hardware-software partitioning, pipeline synthesis, etc.) may become extremely complicated. This difficulty is relaxed by decomposing the task description graph that is usually unavoidable in system-level synthesis. The decomposing algorithms unite certain vertices of the graph, thus the resulting graph consists of less vertices. However, loops may appear in the decomposed graph, even if the original graph was loop-free, that endangers the efficiency of the design algorithms. We propose an algorithm that generates allowable cuts. We prove that any decomposition made along these cuts always yields a loop-free graph. The method is demonstrated on a simple example. Incorporating optimization criteria in the cut generation is also discussed.