Loading...
Please wait, while we are loading the content...
Similar Documents
Some Complexity Results in Memory Mapping
| Content Provider | Semantic Scholar |
|---|---|
| Author | Woutersen, Erwin G. Gerez, Sabih H. |
| Copyright Year | 1996 |
| Abstract | Abstract Four combinatorial optimization problems occurring in thememory-mapping subtask of high-level synthesis turn out tobe intractable as is proven here. The first problem is cyclicregister assignment in which repetitive read-write patterns ofstorage values have to be stored in a minimal number of lo-cations situated in a register file with random access (RAM).The second problemis to partition a set of storage values in asfew RAMs as possible. The remaining problems concern thecounterparts of the RAM problems for sequential read-writememories. 1 Introduction Many combinatorial optimization problems that are encoun-tered in the field of VLSI design automation are intractable[Gar79]. In this paper a number of problems related to thememory mapping task in high-level synthesis are presentedand proven to be either NP-complete or NP-hard.High-levelsynthesis [Gaj92, DM94] is the task of transforming an al-gorithmic description of hardware into an interconnection offunctional units, such as adders and multipliers, and memoryelements. The problems to be solved include scheduling, themapping of operations from the algorithmic descriptions totime instants, and assignment, the mapping of operations tofunctional units and the mapping of storage values [Sto92],the intermediate values that have to be stored for some timebefore they are needed again, to memory elements. Obvi-ously, the creation and consumption times of the storage val-ues are known if the scheduling task has been completed. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://utelnt.el.utwente.nl/links/gerez/publications/corsica96.ps.gz |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
