Memory-optimal evaluation of expression trees involving large objects

作者：Lam Chi Chung; Rauber Thomas; Baumgartner Gerald^*; Cociorva Daniel; Sadayappan P

来源：Computer Languages, Systems and Structures, 2011, 37(2): 63-75.

DOI：10.1016/j.cl.2010.09.003

• Expression tree
• Evaluation order
• Memory minimization
• Register allocation

The need to evaluate expression trees involving large objects arises in scientific computing applications such as electronic structure calculations. Often, the tree node objects are so large that only a subset of them can fit into memory at a time. This paper addresses the problem of finding an evaluation order of the nodes in a given expression tree that uses the least amount of memory. We present an algorithm that finds an optimal evaluation order in Theta(n log(2) n) time for an n-node expression tree and prove its correctness. We demonstrate the utility of our algorithm using representative equations from quantum chemistry.

• 出版日期2011-7