检索结果-内蒙古大学图书馆

Towards efficient partial evaluation in logic programming

NEW GENERATION COMPUTING 1996年第2期14卷 237-259页

作者： Fuller, DA Bocic, SA Bertossi, LE Computer Science Department Pontificia Universidad Católica de Chile Santiago 22 Chile

Partial evaluation is a symbolic manipulation technique used to produce efficient algorithms when part of the input to the algorithm is known. Other applications of partial evaluators such as universal compilation and compiler generation are also known to be possible. A partial evaluator receives as input a program and partially known input to that program, and outputs a residual program which should run at least as efficient as the input program with restricted input. In this paper we study the case where both the input and residual programs are logic programs, being the partial evaluator itself a logic program. Up to now, partial evaluators have failed to process large ''non-toy'' examples. Here we present extensions to partial evaluators which will allow us to produce more efficient residual programs using less computing resources during partial evaluation. First, the introduced extensions allow the processing of large examples, which is not possible with the previous techniques. This is now possible since the extensions use less CPU time and memory consumption during the partial evaluation process. Second, the extended partial evaluator produces smaller residual programs, producing important CPU time optimizing effects. With the standard techniques, a partial evaluator will most probably act as a pessimizer, not as an optimizer. Examples are given.

关键词： partial evaluation logic programming symbolic manipulation program optimization

来源：评论

学校读者我要写书评

暂无评论

Mining control patterns from Java program corpora

引用

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 2004年第1期20卷 57-83页

作者： Chen, DJ Hwang, CC Huang, SK Chen, DTK Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 300 Taiwan Fordham Univ Dept Comp & Informat Sci Bronx NY USA Acad Sinica Inst Informat Sci Taipei 115 Taiwan

Java programming, based on the Object-Oriented (OO) paradigm, has played a major role in program design and implementation due to the fact that it is extensible, maintainable, and reusable in software system construction. Experiences with using Java programming have indicated that there also exist disadvantages with respect to its execution inefficiency and complicated runtime behaviors. Code-patterns are statically recurring structures specifically related to a programming language. They can be used in parallel to help programmer design software systems to solve particular problems. In opposition to the role of code-patterns in assisting compilation, control-pattems are dynamically recurring structures invoked during program execution time. They can be used to understand the run-time behaviors of OO-programs with respect to the underlying architecture, such as Java-VM. A control pattern describes the model of control transfer among objects during OO program execution. In this paper, several control patterns are proposed and discussed. We have analyzed and collected several control patterns from several Java program corpora. The experimental results show that control patterns do exist and provide information for quantitative analysis. Simple patterns, compound patterns, and complex patterns have different ratios depending on their source programs. Collected control patterns can be used to provide guidelines for Java programmers so that they can write more effective Java programs.

关键词： OOP control patterns data mining Java VM code patterns benchmark design program optimization static and dynamic analysis

来源：评论

学校读者我要写书评

暂无评论

Parallelism for free: Efficient and optimal bitvector analyses for parallel programs

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 1996年第3期18卷 268-299页

作者： Knoop, J Steffen, B Vollmer, J UNIV KARLSRUHE FAK INFORMAT INST PROGRAMMSTRUKTUREN & DATENORG D-76128 KARLSRUHE GERMANY

We consider parallel programs with shared memory and interleaving semantics, for which we show how to construct for unidirectional bitvector problems optimal analysis algorithms that are as efficient as their purely sequential counterparts and that can easily be implemented. Whereas the complexity result is rather obvious, our optimality result is a consequence of a new Kam/Ullman-style Coincidence Theorem. Thus using our method, the standard algorithms for sequential programs computing liveness, availability, very busyness, reaching definitions, definition-use chains, or the analyses for performing code motion, assignment motion, partial dead-code elimination or strength reduction, can straightforward be transferred to the parallel setting at almost no cost.

关键词： algorithms languages performance assignment motion bitvector problems code motion data flow analysis definition-use chains interleaving semantics parallelism partial dead-code elimination program optimization shared memory strength reduction synchronization

来源：评论

学校读者我要写书评

暂无评论

Canonical finite models of Kleene algebra with tests

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN programMING 2016年第4期85卷 595-616页

作者： Uramoto, Takeo Kyoto Univ Dept Math Sakyo Ku Kyoto 606 Japan

Kleene algebra with tests (KAT) was introduced by Kozen as an extension of Kleene algebra (KA). So far, the decidability of equational formulas (p = q) and Horn formulas (boolean AND(i)p(i) =q(i) -> p = q) in KAT has been investigated by several authors. Continuing this line of research, the current paper studies the decidability of existentially quantified equational formulas there exists q epsilon P.(p = q) in KAT, where P is a fixed collection of KAT terms and plays a role as a parameter of this decision problem. To design a systematic strategy of deciding problems of this form, given in this paper is an effective procedure of constructing from each KAT term p a finite KAT model K(p) that will be called the canonical finite model of the KAT term p. Applications of this construction are presented, proving the decidability of there exists q epsilon P.(p = q) for several non-trivial P. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Kleene algebra with tests Completeness theorem Canonical finite model Syntactic semiring Regular language program optimization

来源：评论

学校读者我要写书评

暂无评论

DyC: an expressive annotation-directed dynamic compiler for C

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期248卷 147-199页

作者： Grant, B Mock, M Philipose, M Chambers, C Eggers, SJ Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA

We present the design of DyC, a dynamic-compilation system for C based on ran-time specialization. Directed by a few declarative user annotations that specify the variables and code on which dynamic compilation should take place, a binding-time analysis computes the set of run-time constants at each program point in the annotated procedure's control-flow graph;the analysis supports program-point-specific polyvariant division and specialization The results of the analysis guide the construction of a run-time specializer for each dynamically compiled region;the specializer supports various caching strategies for managing dynamically generated code and mixes of speculative and demand-driven specialization of dynamic branch successors. Most of the key cost/benefit trade-offs in the binding-time analysis and the run-time specializer are open to user control through declarative policy annotations. DyC has been implemented in the context of an optimizing compiler, and initial results have been promising. The speedups we have obtained are good, and the dynamic-compilation overhead is among the lowest of any dynamic-compilation system, typically 20-200 cycles per instruction generated on a Digital Alpha 21164. The majority of DyC's functionality has been used to dynamically compile an instruction-set simulator, Only three annotations were required, but a few other changes to the program had to be made due to DyC's lack of support for-static global variables. This deficiency and DyC's rudimentary support for partially static data structures are the primary obstacles to making DyC easy to use. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： dynamic compilation specialization partial evaluation constant folding run-time code generation program optimization dataflow analysis C language

来源：评论

学校读者我要写书评

暂无评论

program transformation system based on Generalized Partial Computation

引用

NEW GENERATION COMPUTING 2002年第1期20卷 75-99页

作者： Futamura, Y Konishi, Z Glück, R Waseda Univ Dept Informat & Comp Sci Shinjuku Ku Tokyo 1698555 Japan

Generalized Partial Computation (GPC) is a program transformation method utilizing partial information about input data, abstract data types of auxiliary functions and the logical structure of a source program. GPC uses both an inference engine such as a theorem prover and a classical partial evaluator to optimize programs. Therefore, GPC is more powerful than classical partial evaluators but harder to implement and control. We have implemented an experimental GPC system called WSDFU (Waseda Simplify-Distribute-Fold-Unfold). This paper demonstrates the power of the program transformation system as well as its theorem prover and discusses some future works.

关键词： partial evaluation program transformation theorem proving program optimization recursion removal algebraic manipulation

来源：评论

学校读者我要写书评

暂无评论

SAFE - A SEMANTIC TECHNIQUE FOR TRANSFORMING programS IN THE PRESENCE OF ERRORS

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 1995年第1期17卷 63-84页

作者： AIKEN, A WILLIAMS, JH WIMMERS, EL IBM CORP ALMADEN RES CTRSAN JOSECA 95120

Language designers and implementors have avoided specifying and preserving the meaning of programs that produce errors. This is apparently because being forced to preserve error behavior limits severely the scope of program optimization, even for correct programs. However, error behavior preservation is desirable for debugging, and error behavior must be preserved in any language that permits user-generated errors (i.e., exceptions). This article presents a technique for expressing general program transformations for languages that possess a rich collection of distinguishable error values. This is accomplished by defining a higher-order function called Safe, which can be used to annotate those portions of a program that are guaranteed not to produce errors. It is shown that this facilitates the expression of very general program transformations, effectively giving program transformations in a language with many error values the same power and generality as program transformations in a language with only a single error value. Using the semantic properties of Safe, it is possible to provide some useful sufficient conditions for establishing the correctness of transformations in the presence of errors. In particular, a Substitutability theorem is proven, which can be used to justify ''in-context'' optimizations: transformations that alter the meanings of subexpressions without changing the meaning of the whole program. Finally, the effectiveness of the technique is demonstrated by some examples of its use in Bn optimizing compiler.

关键词： LANGUAGES THEORY EQUATIONAL REASONING EXCEPTIONS program optimization program TRANSFORMATION

来源：评论

学校读者我要写书评

暂无评论

Resource-constrained software pipelining

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1995年第12期6卷 1248-1270页

作者： Aiken, A Nicolau, A Novack, S UNIV CALIF IRVINE DEPT INFORMAT & COMP SCI IRVINE CA 92717 USA

This paper presents a software pipelining algorithm for the automatic extraction of fine-grain parallelism in general loops, The algorithm accounts for machine resource constraints in a way that smoothly integrates the management of resource constraints with software pipelining, Furthermore, generality in the software pipelining algorithm is not sacrificed to handle resource constraints, and scheduling choices are made with truly global information. Proofs of correctness and the results of experiments with an implementation are also presented.

关键词： software pipelining instruction scheduling program optimization fine-grain parallelism global scheduling

来源：评论

学校读者我要写书评

暂无评论

Optimal control dependence computation and the Roman chariots problem

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 1997年第3期19卷 462-491页

作者： Pingali, K Bilardi, G UNIV PADUA DEIPADUAITALY UNIV ILLINOIS DEPT ELECT ENGN & COMP SCICHICAGOIL 60607

The control dependence relation plays a fundamental role in program restructuring and optimization. The usual representation of this relation is the control dependence graph (CDG), but the size of the CDG can grow quadratically with the input program, even fur structured programs. In this article, we introduce the augmented postdominator tree (APT), a data structure which can be constructed in space and time proportional to the size of the program and which supports enumeration of a number of useful control dependence sets in time proportional to their size. Therefore, APT provides an optimal representation of control dependence. Specifically, the APT data structure supports enumeration of the set cd(e), which is the set of statements control dependent on control-flow edge e, of the set conds(w), which is the set of edges on which statement w is dependent, and of the set cdequiv(w), which is the set of statements having the same control dependences as w. Technically, APT can be viewed as a factored representation of the CDG where queries are processed using an approach known as filtering search.

关键词： compilers control dependence program optimization program transformation

来源：评论

学校读者我要写书评

暂无评论

Complexity-Guided Container Replacement Synthesis

引用

PROCEEDINGS OF THE ACM ON programMING LANGUAGES-PACMPL 2022年第OOPSLA期6卷 1–31页

作者： Wang, Chengpeng Yao, Peisen Tang, Wensheng Shi, Qingkai Zhang, Charles Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Ant Grp Hangzhou Peoples R China

Containers, such as lists and maps. are fundamental data structures in modern programming languages. However, improper choice of container types may lead to significant performance issues. This paper presents CRES, an approach that automatically synthesizes container replacements to improve runtime performance. The synthesis algorithm works with static analysis techniques to identify how containers are utilized in the program, and attempts to select a method with lower time complexity for each container method call. Our approach can preserve program behavior and seize the opportunity of reducing execution time effectively for general inputs. We implement CRES and evaluate it on 12 real-world Java projects. It is shown that CRES synthesizes container replacements for the projects with 384.2 KLoC in 14 minutes and discovers six categories of container replacements, which can achieve an average performance improvement of 8.1%.

关键词： program synthesis program optimization data structure specification

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：