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

A New Approach to Pointer Analysis for Assignments

Journal of Computer Science & Technology 2001年第3期16卷 242-250页

作者：黄波藏斌宇李靖朱传琪 Institute of Parallel Processing Fudan University Shanghai P.R. China

Pointer analysis is a technique to identify at compile-time the potential values of the pointer expressions in a program, which promises significant benefits for optimizing and parallelizing compilers. In this paper, a new approach to pointer analysis for assignments is presented. In this approach, assignments are classified into three categories: pointer assignments, structure (union) assignments and normal assignments which don't affect the point-to information. Pointer analyses for these three kinds of assignments respectively make up the integrated algorithm. When analyzing a pointer assignment, a new method called expression expansion is used to calculate both the left targets and the right targets. The integration of recursive data structure analysis into pointer analysis is a significant originality of this paper, which uniforms the pointer analysis for heap variables and the pointer analysis for stack variables. This algorithm is implemented in Agassiz, an analyzing tool for C programs developed by institute of Parallel Processing, Fudan University. Its accuracy and effectiveness are illustrated by experimental data.

关键词： pointer analysis pointer assignment point-to information recursive data structure

来源：评论

学校读者我要写书评

暂无评论

A METHOD FOR REPRESENTING data ITEMS OF UNLIMITED LENGTH IN A COMPUTER MEMORY

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1981年第6期7卷 590-593页

作者： BABER, RL Bad Homburg Germany

Three methods are commonly used for representing variable length data in a computer memory: 1. linked linear lists, 2. prefixing the data item with a length indicator, and 3. storing a special termination symbol at the end of the data item. Although the third method can possibly be used to represent data items of unlimited length in a computer memory, an adaptation of the second method works more effectively to serve this purpose. In the adaptation, the prefix, or length field, can itself be variable in length. One can define a recursive structure for the syntax of a length specification in such a way that no limit is imposed on the length of the subject data item and the number of length fields. When encoding numbers, the radix should be chosen to minimize overhead in the most frequently used range of lengths.

关键词： Variable Length data Coding Unbounded Numbers Infinite Address Space recursive data structure Storing data In A Computer Memory Unbounded Address Space Unbounded Linear List Unlimited Length data Format Unlimited Length data Item Unlimited Length data String

来源：评论

学校读者我要写书评

暂无评论

Making context-sensitive points-to analysis with heap cloning practical for the real world 07

Making context-sensitive points-to analysis with heap clonin...

引用

Conference on Programming Language Design and Implementation

作者： Lattner, Chris Lenharth, Andrew Adve, Vikram Univ Illinois Urbana IL 61801 USA

ISBN: (纸本)9781595936332

Context-sensitive pointer analysis algorithms with full "heap cloning" are powerful but are widely considered to be too expensive to include in production compilers. This paper shows, for the first time, that a context-sensitive, field-sensitive algorithm with full heap cloning (by acyclic call paths) can indeed be both scalable and extremely fast in practice. Overall, the algorithm is able to analyze programs in the range of 100K-200K lines of C code in 1-3 seconds, takes less than 5% of the time it takes for GCC to compile the code (which includes no whole-program analysis), and scales well across five orders of magnitude of code size. It is also able to analyze the Linux kernel (about 355K lines of code) in 3.1 seconds. The paper describes the major algorithmic and engineering design choices that are required to achieve these results, including (a) using flow-insensitive and unification-based analysis, which are essential to avoid exponential behavior in practice;(b) sacrificing context-sensitivity within strongly connected components of the call graph;and (c) carefully eliminating several kinds of O(N-2) behaviors (largely without affecting precision). The techniques used for (b) and (c) eliminated several major bottlenecks to scalability, and both are generalizable to other context-sensitive algorithms. We show that the engineering choices collectively reduce analysis time by factors of up to 3x-21x in our ten largest programs, and that the savings grow strongly with program size. Finally, we briefly summarize results demonstrating the precision of the analysis.

关键词： pointer analysis context-sensitive field-sensitive interprocedural static analysis recursive data structure

来源：评论

学校读者我要写书评

暂无评论

Automatic pool allocation: Improving performance by controlling data structure layout in the heap

Automatic pool allocation: Improving performance by controll...

引用

Conference on Programming Language Design and Implementation

作者： Lattner, C Adve, V Univ Illinois Chicago IL 60680 USA

This paper describes Automatic Pool Allocation, a transformation framework that segregates distinct instances of heap-based data structures into seperate memory pools and allows heuristics to be used to partially control the internal layout of those data structures. The primary goal of this work is performance improvement, not automatic memory management, and the paper makes several new contributions. The key contribution is a new compiler algorithm for partitioning heap objects in imperative programs based on a context-sensitive pointer analysis, including a novel strategy for correct handling of indirect (and potentially unsafe) function calls. The transformation does not require type safe programs and works for the full generality of C and C++. Second, the paper describes several optimizations that exploit data structure partitioning to further improve program performance. Third, the paper evaluates how memory hierarchy behavior and overall program performance are impacted by the new transformations. Using a number of benchmarks and a few applications, we find that compilation times are extremely low, and overall running times for heap intensive programs speed up by 10-25% in many cases, about 2x in two cases, and more than 10x in two small benchmarks. Overall, we believe this work provides a new framework for optimizing pointer intensive programs by segregating and controlling the layout of heap-based data structures.

关键词： recursive data structure data layout cache static analysis pool allocation

来源：评论

学校读者我要写书评

暂无评论

High performance Cholesky factorization via blocking and recursion that uses minimal storage 5th

High performance Cholesky factorization via blocking and rec...

引用

5th International Workshop on Applied Parallel Computing (PARA 2000)

作者： Gustavson, F Jonsson, I IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Umea Univ Dept Comp Sci SE-90187 Umea Sweden

ISBN: (纸本)354041729X

We present a high performance Cholesky factorization algorithm, called BPC for Blocked Packed Cholesky, which performs better or equivalent to the LAPACK DPOTRF subroutine, but with about the same memory requirements as the LAPACK DPPTRF subroutine, which runs at level 2 BLAS speed. Algorithm BPC only calls DGEMM and level 3 kernel routines. It combines a recursive algorithm with blocking and a recursive packed data format. A full analysis of overcoming the non-linear addressing overhead imposed by recursion is given and discussed. Finally, since BPC uses GEMM to a great extent, we easily get a considerable amount of SMP parallelism from an SMP GEMM.

关键词： Cholesky factorization recursive algorithm recursive data structure packed format level 3 BLAS parallelism

来源：评论

学校读者我要写书评

暂无评论

A Technique of Algorithm Construction on Sequences

引用

IEEE Transactions on Software Engineering 1978年第1期SE-4卷 65-69页

作者： Misra, Jayadev Department of Computer Science University of Texas Austin TX 78712 United States

A technique is presented which is shown to be useful in designing algorithms which operate on sequences (strings). A generalization of the principle is presented for more general data structure. Copyright © 1978 ... 详细信息

关键词： Algorithm design recursive data structure successive approximation

来源：评论

学校读者我要写书评

暂无评论

Automatic pool allocation: Improving performance by controlling data structure layout in the heap

引用

ACM SIGPLAN NOTICES 2005年第6期40卷 129-142页

作者： Lattner, C Adve, V Univ Illinois Chicago IL 60680 USA

关键词： recursive data structure data layout cache static analysis pool allocation

来源：评论

学校读者我要写书评

暂无评论

AN APPROACH TO THE recursive RETRIEVAL PROBLEM IN THE RELATIONAL dataBASE

引用

COMMUNICATIONS OF THE ACM 1989年第2期32卷 239-245页

作者： TILLQUIST, J KUO, FY Univ. of Colorado Denver Univ. of Colorado Denver

The article examines the QUEL language of RT-Ingres to facilitate this recursive retrieval function using the Theory of Transitive Closure. Initially, a recursive data structure is converted to a directed graph, in which a node represents a data instance and an arc represents a relationship instance. An intermediate data structure is generated to represent the tree structure that is equivalent to the directed graph. Finally, a new data structure which describes transitive closure can then be derived. Under the Relational Theory, the primary key is always unique with the foreign key capable of having multiple instances. This imposes the condition of structures using the foreign key as the transversal to be one-to-many. Consider the project management graph, where each node of the graph quantifies the duration of a task. By applying associative closure, the total duration of each leg of the graph may be calculated, and the built-in MIN function would then isolate the critical path from the resultant subgraph.

关键词： QUEL recursive data structure relational database SQL

来源：评论

学校读者我要写书评

暂无评论

Making context-sensitive points-to analysis with heap cloning practical for the real world

引用

ACM SIGPLAN NOTICES 2007年第6期42卷 278-289页

作者： Lattner, Chris Lenharth, Andrew Adve, Vikram Univ Illinois Urbana IL 61801 USA

关键词： pointer analysis context-sensitive field-sensitive interprocedural static analysis recursive data structure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：