Exact memory size estimation for array computations

Ying Zhao; Sharad Malik

doi:10.1109/92.894155

Exact memory size estimation for array computations

Ying Zhao, Sharad Malik

Research output: Contribution to journal › Conference article › peer-review

23 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	517-521
Number of pages	5
Journal	IEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume	8
Issue number	5
DOIs	https://doi.org/10.1109/92.894155
State	Published - Oct 2000
Event	11th International Symposium on System-Level Synthesis and Design (ISS'98) - Hsinchu, Taiwan Duration: Dec 2 1998 → Dec 4 1998

All Science Journal Classification (ASJC) codes

Software
Hardware and Architecture
Electrical and Electronic Engineering

Access to Document

10.1109/92.894155

Cite this

@article{7969f0fde5ed49a3ac072bf0f4f71049,

title = "Exact memory size estimation for array computations",

abstract = "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.",

author = "Ying Zhao and Sharad Malik",

note = "Funding Information: Manuscript received August 16, 1999. This work was supported by DARPA under the Small Memory Embedded Systems Program, by the New Jersey Center for Multimedia Research, and by the MARCO Gigascale Silicon Research Center. Copyright: Copyright 2007 Elsevier B.V., All rights reserved.; 11th International Symposium on System-Level Synthesis and Design (ISS'98) ; Conference date: 02-12-1998 Through 04-12-1998",

year = "2000",

month = oct,

doi = "10.1109/92.894155",

language = "English (US)",

volume = "8",

pages = "517--521",

journal = "IEEE Transactions on Very Large Scale Integration (VLSI) Systems",

issn = "1063-8210",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "5",

}

TY - JOUR

T1 - Exact memory size estimation for array computations

AU - Zhao, Ying

AU - Malik, Sharad

N1 - Funding Information: Manuscript received August 16, 1999. This work was supported by DARPA under the Small Memory Embedded Systems Program, by the New Jersey Center for Multimedia Research, and by the MARCO Gigascale Silicon Research Center. Copyright: Copyright 2007 Elsevier B.V., All rights reserved.

PY - 2000/10

Y1 - 2000/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034289947&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034289947&partnerID=8YFLogxK

U2 - 10.1109/92.894155

DO - 10.1109/92.894155

M3 - Conference article

AN - SCOPUS:0034289947

SN - 1063-8210

VL - 8

SP - 517

EP - 521

JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IS - 5

T2 - 11th International Symposium on System-Level Synthesis and Design (ISS'98)

Y2 - 2 December 1998 through 4 December 1998

ER -

Exact memory size estimation for array computations

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this