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

Eliminating partially dead code in explicitly parallel programs

THEORETICAL COMPUTER SCIENCE 1998年第1-2期196卷 365-393页

作者： Knoop, J Carl von Ossietzky Univ Oldenburg Fachbereich Informat 10 D-26111 Oldenburg Germany

Eliminating partially dead code has proved to be a powerful technique for the runtime optimization of sequential programs. In this article, we show how this technique can be adapted to explicitly parallel programs with shared memory and interleaving semantics. The basis of this adaption is a recently presented framework for efficient and precise bitvector analyses for this program setting. Whereas the framework underlying our approach allows a straightforward adaptation of the required data flow analyses to the parallel case, the transformation part of the optimization requires special care in order to preserve parallelism This preservation is an absolute must in order to guarantee that the optimization does never impair efficiency. The introduction of an appropriate natural side condition suffices to lift even the optimality result known from the sequential setting to the parallel setting. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： parallelism interleaving semantics shared memory program optimization partial dead-code elimination

来源：评论

学校读者我要写书评

暂无评论

Formal callability and its relevance and application to interprocedural data-flow analysis

Formal callability and its relevance and application to inte...

引用

1998 International Conference on Computer Languages

作者： Knoop, J Univ Passau Fak Math & Informat D-94030 Passau Germany

ISBN: (纸本)0780350057

Formal callability is the problem of determining for every formal procedure call of a program the set of procedures it may call at run-time. The's information is the key for constructing the procedure call graph of a program, a common prerequisite of static analyses of programs with procedures. Moreover, under specific side-conditions it reduces in interprocedural data-flow analysis the analysis of programs with formal procedure calls to the analysis of programs without formal calls by treating formal calls as higher-order branch statements. We demonstrate that formal callability yields as a by-product the solution of the well-known formal reachability problem. This directly implies that formal callability is in general not decidable. However, we show that formal callability is decidable for programs, where formal procedure parameters do not occur in procedures, which are local to the procedure of their declaration (usually known as programs without global (formal) procedure parameters), but within a time bound which is exponential in the program size. Thus, we complement the new decidability result by introducing in addition a safe approximation of formal callability called potential passability, which can efficiently be computed. Moreover, for programs of mode depth 2 (i.e., formal procedures do not have procedures as parameters) without global procedure parameters, formal callability and potential passability coincide.

关键词： formal callability formal reachability call graph analysis interprocedural data-flow analysis program optimization

来源：评论

学校读者我要写书评

暂无评论

Code motion and code placement:: Just synonyms? 7th

Code motion and code placement:: Just synonyms?

引用

7th European Symposium on programming (ESOP'98) at the Joint European Conferences on Theory and Practice of Software (ETAPS'98)

作者： Knoop, J Rüthing, O Steffen, B Univ Passau D-94030 Passau Germany Univ Dortmund D-44221 Dortmund Germany

ISBN: (纸本)3540643028

We prow that there is no difference between code motion (CM) and code placement (CP) in the traditional syntactic setting, however, a dramatic difference in the semantic setting. We demonstrate this by re-investigating semantic CM under the perspective of the recent development of syntactic CM. Besides clarifying and highlighting the analogies and essential differences between the syntactic and the semantic approach, this leads as a side-effect to a drastical reduction of the conceptual complexity of the value-flow based procedure for semantic CM of [20], as the original bidirectional analysis is decomposed into purely unidirectional components. On the theoretical side, this establishes a natural semantical understanding in terms of the Herbrand interpretation (transparent equivalence), and thus eases the proof of correctness;moreover, it shows the frontier of semantic CM, and gives reason for the lack of algorithms going beyond. On the practical side, it simplifies the implementation and increases the efficiency, which, hire for its syntactic counterpart, can be the catalyst for its migration from academia into industrial practice.

关键词： program optimization data-flow analysis code motion code placement partial redundancy elimination transparent equivalence Herbrand interpretation

来源：评论

学校读者我要写书评

暂无评论

Iteration space partitioning

引用

FUTURE GENERATION COMPUTER SYSTEMS 1997年第5期12卷 421-429页

作者： Bik, AJC Wijshoff, HAG High Performance Computing Division Department of Computer Science Leiden University PO Box 9512 2300 RA Leiden The Netherlands

In this paper, we present a general method to isolate the loop-body of a nested loop for all iterations in a particular polyhedral set. This isolation is done by successively partitioning execution sets of individual DO-loops in the loop, thereby partitioning the iteration space according to the linear inequalities that define the polyhedral set. In particular, this method is useful to perform program simplifications or to support data structure transformations.

关键词： iteration space partitioning loop transformation program restructuring program optimization

来源：评论

学校读者我要写书评

暂无评论

Evidence-based static branch prediction using machine learning

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 1997年第1期19卷 188-222页

作者： Calder, B Grunwald, D Jones, M Lindsay, D Martin, J Mozer, M Zorn, B UNIV COLORADO DEPT COMP SCI BOULDER CO 80309 USA

Correctly predicting the direction that branches will take is increasingly important in today's nide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this article, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this article, we use neural networks and decision trees la map static features associated with each branch to a prediction that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique;it is effective across a range of programming languages and programming styles;and it does not rely on the use of expert-defined heuristics. In this article, me describe the application of ESP to the problem of static branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. We provide results showing how sensitive ESP is to the number and type of static features and programs included in the ESP training sets, and we compare the efficacy of static branch prediction for subroutine libraries. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.

关键词： branch prediction decision trees machine learning neural networks performance evaluation program optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast strictness analysis based on demand propagation

引用

ACM TRANSACTIONS ON programMING LANGUAGES AND SYSTEMS 1995年第6期17卷 896-937页

作者： Sekar, R Ramakrishnan, IV SUNY STONY BROOK DEPT COMP SCISTONY BROOKNY 11794

Strictness analysis is a well-known technique used in compilers for optimization of sequential and parallel evaluation of lazy functional programming languages. Ever since Mycroft's pioneering research in strictness analysis, there have been substantial research efforts in advancing the basic technique in several directions such as higher-order functions, nonflat domains, etc. While almost all of these methods define strictness based on denotational semantics, in 1990 we proposed an operational method called ee-analysis. Operational methods directly address the primary aspect of the strictness analysis problem, namely nontermination of evaluation, and can yield simplicity both in formulation and computational algorithms. Moreover, the use of operational approach has led us to a simple and natural treatment of polymorphism, While ee-analysis reasoned about normal-form evaluation herein we extend its power substantially so as to deal with other degrees of evaluation that are intermediate between normal and head-normal form. An interesting aspect of our approach is our formulation of a strictness property as a constraint that relates the demand placed on the output of a function to the demands placed on its arguments. Strictness properties are then computed using symbolic constraint-solving techniques. An important advantage of constraint-driven analysis is that it captures interargument dependencies accurately. Moreover, the analysis performance is relatively insensitive to domain size. Based on our implementation of this method, we show that our analysis techniques are efficient, as well as effective.

关键词： algorithms languages theory program analysis program optimization strictness analysis

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：