Exact memory size estimation for array computations

Ying Zhao, Sharad Malik

Research output: Contribution to journalConference articlepeer-review

23 Scopus citations


This paper presents a new algorithm for exact estimation of the minimum memory size required by programs dealing with array computations. Based on parametric partitioning of the iteration space and formalized live variable analysis, our algorithm transforms the minimum memory size estimation into an equivalent problem: integer point counting for intersection/union of mappings of parameterized polytopes. A heuristics was then proposed to solve the counting problem. Experimental results show that the algorithm achieves the exactness traditionally associated with totally unrolling loops while exploiting reduced computation complexity by preserving the original loop structure.

Original languageEnglish (US)
Pages (from-to)517-521
Number of pages5
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number5
StatePublished - Oct 2000
Event11th International Symposium on System-Level Synthesis and Design (ISS'98) - Hsinchu, Taiwan
Duration: Dec 2 1998Dec 4 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'Exact memory size estimation for array computations'. Together they form a unique fingerprint.

Cite this