ABSTRACT
This chapter explores the merging techniques to arbitrary, delayless, acyclic synchronous dataflow graphs. While the buffer merging technique as developed results in significant reductions in memory requirements, even more reduction can be obtained if other optimizations are considered. The technique of buffer merging is able to encapsulate the lifetimes of tokens on edges algebraically, and use that information to develop near-optimal overlaying strategies. Buffer merging does not render separate buffers or lifetime-based buffer sharing obsolete. Separate buffers are useful for implementing edges that contain delays efficiently. When acyclic graphs are considered, there are two other dimensions that come into play for designing merging algorithms. The first dimension is the choice of the topological ordering of the actors; each topological ordering leads to a set of single appearance schedules. The second dimension is unique to the merge cost function, and is the issue of the set of paths that buffers should be merged on.
