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

A compiler optimization algorithm for shared-memory multiprocessors

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1998年第8期9卷 769-787页

作者： McKinley, KS Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

This paper presents a new compiler optimization algorithm that parallelizes applications for symmetric, shared-memory multiprocessors. The algorithm considers data locality, parallelism, and the granularity of parallelism. It uses dependence analysis and a simple cache model to drive its optimizations. It also optimizes across procedures by using interprocedural analysis and transformations. We validate the algorithm by hand-applying it to sequential versions of parallel, Fortran programs operating over dense matrices. The programs initially were hand-coded to target a variety of parallel machines using loop parallelism. We ignore the user's parallel loop directives, and use known and implemented dependence and interprocedural analysis to find parallelism. We then apply our new optimization algorithm to the resulting program. We compare the original parallel program to the hand-optimized program, and show that our algorithm improves three programs, matches four programs, and degrades one program in our test suite on a shared-memory, bus-based parallel machine with local caches. This experiment suggests existing dependence and interprocedural array analysis can automatically detect user parallelism, and demonstrates that user parallelized codes often benefit from our compiler optimizations, providing evidence that we need both parallel algorithms and compiler optimizations to effectively utilize parallel machines.

关键词： program Parallelization Parallelization Techniques program optimization Data Locality Restructuring Compilers Performance Evaluation

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

The narrowing-driven approach to functional logic program specialization

引用

NEW GENERATION COMPUTING 2002年第1期20卷 3-26页

作者： Albert, E Vidal, G Univ Politecn Valencia DSIC E-46022 Valencia Spain

Partial evaluation is a semantics-based program optimization technique which has been investigated within different programming paradigms and applied to a wide variety of languages. Recently, a partial evaluation framework for functional logic programs has been proposed. In this framework, narrowing-the standard operational semantics of integrated languages-is used to drive the partial evaluation process. This paper surveys the essentials of narrowing-driven partial evaluation.

关键词： program optimization partial evaluation narrowing

来源：评论

学校读者我要写书评

暂无评论

Algorithms for computing the static single assignment form

引用

JOURNAL OF THE ACM 2003年第3期50卷 375-425页

作者： Bilardi, G Pingali, K Univ Padua Dipartimento Ingn Informaz I-35131 Padua Italy Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

The Static Single Assignment (SSA) form is a program representation used in many optimizing compilers. The key step in converting a program to SSA form is called phi-placement. Many algorithms for phi-placement have been proposed in the literature, but the relationships between these algorithms are not well understood. In this article, we propose a framework within which we systematically derive (i) properties of the SSA form and (ii) phi-placement algorithms. This framework is based on a new relation called merge which captures succinctly the structure of a program's control flow graph that is relevant to its SSA form. The phi-placement algorithms we derive include most of the ones described in the literature, as well as several new ones. We also evaluate experimentally the performance of some of these algorithms on the SPEC92 benchmarks. Some of the algorithms described here are optimal for a single variable. However, their repeated application is not necessarily optimal for multiple variables. We conclude the article by describing such an optimal algorithm, based on the transitive reduction of the merge relation, for multi-variable phi-placement in structured programs. The problem for general programs remains open.

关键词： algorithms languages theory control dependence optimizing compilers program optimization program transformation static single assignment form

来源：评论

学校读者我要写书评

暂无评论

GENERATING OPTIMAL CONTIGUOUS EVALUATIONS FOR EXPRESSION DAGS

引用

COMPUTER LANGUAGES 1995年第2期21卷 113-127页

作者： KESSLER, CW RAUBER, T Computer Science Department Universität des Saarlandes Postfach 151150 66041 Saarbrücken Germany

We consider the NP-complete problem of generating contiguous evaluations for expression DAGs with a minimal number of registers. We present two algorithms that generate optimal contiguous evaluation for a given DAG. The first is a modification of a complete search algorithm that omits the generation of redundant evaluations. The second algorithm generates only the most promising evaluations by splitting the DAG into trees with import and export nodes and evaluating the trees with a modified labeling scheme. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithms generate optimal contiguous evaluations quite fast.

关键词： program optimization BASIC BLOCK EXPRESSION DAG CONTIGUOUS EVALUATION REGISTER ALLOCATION CODE GENERATION

来源：评论

学校读者我要写书评

暂无评论

Scheduling expression DAGs for minimal register need

引用

COMPUTER LANGUAGES 1998年第1期24卷 33-53页

作者： Kessler, CW Univ Trier FB Informat 4 D-54286 Trier Germany

Generating schedules for expression DAGs that use a minimal number of registers is a classical NP-complete optimization problem. Up to now an exact solution could only be computed for small DAGs (with up to 20 nodes), using a trivial O(n!) enumeration algorithm. We present a new algorithm with worst-case complexity O(n2(2n)) and very good average behavior. Applying a dynamic programming scheme and reordering techniques, our algorithm is able to defer the combinatorial explosion and to generate an optimal schedule not only for small DAGs:but also for medium-sized ones with up to 50 nodes, a class that contains nearly all DAGs encountered in typical application programs. Experiments with randomly generated DAGs and large DAGs from real application programs confirm that the new algorithm generates optimal schedules quite fast. We extend our algorithm to cope with delay slots and multiple functional units, two common features of modern superscalar processors. (C) 1998 Elsevier Science Ltd. All rights reserved.

关键词： program optimization basic block expression DAG instruction scheduling register allocation code generation

来源：评论

学校读者我要写书评

暂无评论

REGION ANALYSIS - A PARALLEL ELIMINATION METHOD FOR DATA-FLOW ANALYSIS

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1995年第11期21卷 913-926页

作者： LEE, YF RYDER, BG FIUCZYNSKI, ME RUTGERS STATE UNIV DEPT COMP SCIHILL CTRPISCATAWAYNJ 08855 UNIV WASHINGTON DEPT COMP SCI & ENGNSEATTLEWA 98195

Parallel data flow analysis methods offer the promise of calculating detailed semantic information about a program at compile-time more efficiently than sequential techniques, Previous work on parallel elimination methods [1], [2] has been hampered by the lack of control over interval size;this can prohibit effective parallel execution of these methods, To overcome this problem, we have designed the region analysis method, a new elimination method for data flow analysis. Region analysis emphasizes flow graph partitioning to enable better load balancing in a more effective;parallel algorithm, In this paper, we present the design of region analysis and the empirical results we have obtained that indicate 1) the prevalence of large intervals in flow graphs derived from real programs and 2) the performance improvement of region analysis over parallel Allen-Cocke interval analysis, Our implementation analyzed programs from the Perfect Benchmarks [3] and netlib [4] running on a Sequent Symmetry S81.

关键词： DATA FLOW ANALYSIS ELIMINATION ALGORITHMS INTERVAL ANALYSIS PARALLEL ALGORITHMS program optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：