Comparison of two loop-free decomposition methods

摘要

Decomposition is an important task in system-level synthesis, and in most applications, preserving the loop-free property during decomposition is crucial. We compare two decomposition algorithms that can preserve the loop-free property of the initial graph. The first algorithm does the decomposition in two steps, first it generates the list of possible cuts, and in the second step it chooses the cuts from the generated list. Theoretically this algorithm can generate all the possible results, however the list generation is not unique, and there is no known strategy for optimal list generation. The second algorithm generates segments based on the distance of the vertices from the inputs nodes. This algorithm can incorporate local cost functions, however it can not generate all the possible loop-free results. The second algorithm thus can be parametrized more effectively, however its search space is smaller than that of the first algorithm.