| Author: | Ravikumar, C P |
| Advisor: | Advisor |
| Date: | 1992
|
| Publisher: | |
| Citation: | Computer-A
|
| Series/Report no.: |
|
| Item Type: | Article
|
| Keywords: | register allocation; task scheduling; interval graphs; clique partition |
| Abstract: | The paper considers an optimization technique with applications to some resource-allocation problems that arise in high-level synthesis of digital systems. In an abstract sense, the optimization problem is that of the partitioning of a set of line intervals into a minimum number of subsets such that intervals assigned to a subset satisfy certain properties. It is shown that the problem can be solved optically in O(n) time, where n is the number of line intervals. Applications of the problem to memory allocation and task scheduling are discussed. Specifically, a program called is described for the allocation of variables to multiport memories. has been implemented in on a Sun/3 workstation. |
