Parallel algorithms for force directed scheduling of flattened and hierarchical signal flow graphs

In this paper, we present some novel algorithms for scheduling hierarchical signal flow graphs in the domain of high-level synthesis. With complex chi ps that need to be designed in the future, it is expected that the runtimes of these scheduling algorithms will be quite large. The key contributions of this paper are as follows: First, we develop a novel extension of the se quential force-directed scheduling algorithm which naturally handles loops and conditionals by coming up with a scheme of scheduling hierarchical sign al flow graphs. Second, we develop three new parallel algorithms for the sc heduling problem. Our parallel algorithms are portable across a wide range of parallel platforms. We report results on a set of high-level synthesis b enchmarks on 8-processor SGI Origin and a 64 processor IBM SP-2. While some parallel algorithms for VLSI CAD reported by earlier researchers have repo rted a loss of qualities of results, our parallel algorithms produce exactl y the same results as the sequential algorithms on which they are based.