Cost Analysis Using Automatic Size and Time Inference
Cost Analysis Using Automatic Size and Time Inference
复制标题
使用自动大小和时间推断进行成本分析
DOI：
10.1007/3-540-44854-3_15
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Pedro B. Vasconcelos
中科院分区：
文献类型：
--
作者：
Álvaro J. Rebón Portillo;K. Hammond;Hans;Pedro B. Vasconcelos
成本信息可以在各种情况下利用，包括并行编译器，自主GRID和实时系统。在本文中，我们介绍了一种新的类型和效果系统-大小的时间系统，能够确定时间和空间成本的上限，我们最初打算应用于确定并行任务的良好粒度。分析定义为一个简单的，严格的，高阶和多态的功能语言，L，将任意大小的列表数据结构。实现这种分析的推理算法构造L表达式的成本和大小项，加上对自由大小和成本变量的约束，这些约束可以被求解以产生高阶函数的信息。本文介绍了分析和推理算法，提供的例子说明了分析的主要特点。
Cost information can be exploited in a variety of contexts, including parallelizing compilers, autonomic GRIDs and real-time systems. In this paper, we introduce a novel type and effect system - the sized time system that is capable of determining upper bounds for both time and space costs, and which we initially intend to apply to determining good granularity for parallel tasks. The analysis is defined for a simple, strict, higher-order and polymorphic functional language, L, incorporating arbitrarily-sized list data structures. The inference algorithm implementing this analysis constructs cost- and size-terms for L- expressions, plus constraints over free size and cost variables in those terms that can be solved to produce information for higher-order functions. The paper presents both the analysis and the inference algorithm, providing examples that illustrate the primary features of the analysis.