Loading...
Please wait, while we are loading the content...
Similar Documents
Buffer allocation in regular dataflow networks: an approach based on coloring circular-arc graphs.
| Content Provider | CiteSeerX |
|---|---|
| Author | Govindarajan, R. Rengarajan, S. |
| Abstract | In this paper we discuss a method to perform compile-time buffer allocation, allowing efficient buffer sharing among the arcs of a special form of dataflow graphs -- known as regular stream flow graphs -- commonly used in Digital Signal Processing applications. We relate the buffer sharing problem to that of finding independent sets in weighted circular arc graph. An important difference between the traditional graph coloring/register allocation problem and our buffer sharing problem is that in our problem the aim is to minimize the sum of the weights of the independent sets, rather than the number of independent sets. We present a heuristic algorithm and experiment it on a large number of randomly generated regular dataflow graphs as well as a few DSP applications. It is observed that the heuristic algorithm performs well, reducing the buffer requirement by 14.3% on the average. Also, we observe that buffer requirement achieved by the heuristic algorithm is within 2.1% from the lowe... |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Independent Set Buffer Allocation Regular Dataflow Network Coloring Circular-arc Graph Heuristic Algorithm Dataflow Graph Compile-time Buffer Allocation Buffer Sharing Problem Heuristic Algorithm Performs Buffer Requirement Traditional Graph Efficient Buffer Sharing Regular Stream Flow Graph Large Number Special Form Regular Dataflow Graph Dsp Application Allocation Problem Digital Signal Processing Application Weighted Circular Arc Graph Important Difference |
| Content Type | Text |
| Resource Type | Article |
