On the Inference of Resource Usage Upper and Lower Bounds
On the Inference of Resource Usage Upper and Lower Bounds
复制标题
DOI：
10.1145/2499937.2499943
复制
发表时间：
2013-08-01
影响因子：
0.5
通讯作者：
Masud, Abu Naser
中科院分区：
文献类型：
--
作者：
Albert, Elvira;Genaim, Samir;Masud, Abu Naser
成本分析的目的是根据程序的输入数据大小确定运行程序所需的资源量。最具挑战性的步骤是推断在程序中执行循环的代价。这需要限定每个循环的迭代次数，并为每次迭代的代价找到严格的界限。本文提出了一种从成本关系中推断上下界的新方法。这些关系是标准递归方程的扩展形式，可以是不确定的，包含不精确的大小约束，并且有多个增加和/或减少的参数。我们提出了新的技术来自动将成本关系转换为最坏情况和最佳情况的确定性单参数递归关系。每个递归关系的解提供了在程序中执行相应循环的精确上界和下界。重要的是，由于该方法是在成本方程的层次上开发的，因此我们的技术与编程语言无关。
Cost analysis aims at determining the amount of resources required to run a program in terms of its input data sizes. The most challenging step is to infer the cost of executing the loops in the program. This requires bounding the number of iterations of each loop and finding tight bounds for the cost of each of its iterations. This article presents a novel approach to infer upper and lower bounds from cost relations. These relations are an extended form of standard recurrence equations that can be nondeterministic, contain inexact size constraints and have multiple arguments that increase and/or decrease. We propose novel techniques to automatically transform cost relations into worst-case and best-case deterministic one-argument recurrence relations. The solution of each recursive relation provides a precise upper-bound and lower-bound for executing a corresponding loop in the program. Importantly, since the approach is developed at the level of the cost equations, our techniques are programming language independent.