Exact memory size estimation for array computations without loop unrolling

Ying Zhao, Sharad Malik

Research output: Contribution to journalConference article

35 Scopus citations

Abstract

This paper presents a new algorithm for exact estimation of the minimum memory size required by programs dealing with array computations. Memory size is an important factor affecting area and power cost of memory units. For programs dealing mostly with array computations, memory cost is a dominant factor in the overall system cost. Thus, exact estimation of memory size required by a program is necessary to provide quantitative information for making high-level design decisions. Based on formulated live variables analysis, our algorithm transforms the minimum memory size estimation into an equivalent problem: integer point counting for intersection/union of mappings of parameterized polytopes. Then, a heuristics was proposed to solve the counting problem. Experimental results show that the algorithm achieves the exactness traditionally associated with totally-unrolling loops while exploiting the reduced computation complexity by preserving original loop structure.

Original languageEnglish (US)
Pages (from-to)811-816
Number of pages6
JournalProceedings - Design Automation Conference
DOIs
StatePublished - Jan 1 1999
EventProceedings of the 1999 36th Annual Design Automation Conference (DAC) - New Orleans, LA, USA
Duration: Jun 21 1999Jun 25 1999

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering

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

  • Cite this