More Precise Yet Widely Applicable Cost Analysis
More Precise Yet Widely Applicable Cost Analysis
复制标题
更精确且适用范围更广的成本分析
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Masud
中科院分区：
文献类型：
--
作者：
E. Albert;S. Genaim;A. Masud
成本分析旨在根据程序的输入数据大小确定运行该程序所需的资源量。自动推断精确的界限，同时能够处理广泛类别的程序，是成本分析中的主要挑战。(1)现有的方法依赖于计算机代数系统(CAS)来求解所获得的成本递推方程(CR)，适用时非常精确，但处理的CR类别非常有限。(2)为CR开发的特定求解器往往为了更广泛的适用性而牺牲精度。在本文中，我们提出了一种新的方法来推断CR的精确上下界，与(1)相比，它在保持精度的同时严格地更广泛地适用，而与(2)相比，它在实践中更精确(获得更紧的复杂性阶)，保持广泛的适用性，此外，还可以用来获得有用的下界。主要的新奇之处在于，我们能够准确地确定程序循环每次迭代的最坏情况/最好情况的成本，然后，通过对得到的序列进行求和，我们可以获得非常精确的上下界。
Cost analysis aims at determining the amount of resources required to run a program in terms of its input data sizes. Automatically inferring precise bounds, while at the same time being able to handle a wide class of programs, is a main challenge in cost analysis. (1) Existing methods which rely on computer algebra systems (CAS) to solve the obtained cost recurrence equations (CR) are very precise when applicable, but handle a very restricted class of CR. (2) Specific solvers developed for CR tend to sacrifice accuracy for wider applicability. In this paper, we present a novel approach to inferring precise upper and lower bounds on CR which, when compared to (1), is strictly more widely applicable while precision is kept and when compared to (2), is in practice more precise (obtaining even tighter complexity orders), keeps wide applicability and, besides, can be applied to obtain useful lower bounds as well. The main novelty is that we are able to accurately bound the worst-case/best-case cost of each iteration of the program loops and, then, by summing the resulting sequences, we achieve very precise upper/lower bounds.