Constraint programming (CP) is in its substance non-algorithmic programming, not last because it is often being applied to problems for which no efficient algorithms exist. A not immediately obvious consequence of thi...
详细信息
In this paper, we show how Ada 95 can be used as an implementationlanguage for object-oriented designs. We present a strategy to map Fusion class descriptions into Ada specifications, considering the various kinds of...
详细信息
This paper discusses the implementation model for supporting Ada 95 controlled types in the GNAT compiler [1]. After reviewing the semantics of controlled types, we outline the associated implementation problems and d...
详细信息
Ada 95 adds many new, powerful constructs to the ones Ada 83 already offered. From the perspective of a designer and implementor of Ada software components, this should encourage an evolution in the architecture of co...
详细信息
The effective synergy of a number of different techniques is the key to the successful development of an efficient Reverse Engineering environment. Compiler technology, pattern matching techniques, visualization tools...
详细信息
ISBN:
(纸本)0818671114
The effective synergy of a number of different techniques is the key to the successful development of an efficient Reverse Engineering environment. Compiler technology, pattern matching techniques, visualization tools, and software repositories play an important role for the identification of procedural, data, and abstract-data-type related concepts in the source code. This paper describes a number of techniques used for the development of a distributed reverse engineering environment. design recovery is investigated through code-to-code and abstract-descriptions-to-code pattern matching techniques used to locate code that may implement a particular plan or algorithm. The code-to-code matching uses dynamic programming techniques to locate similar code fragments and is targeted for large software systems (1M LOC). Patterns are specified either as source code or as a sequence of abstract statements written in an concept language developed for this purpose. Markov models are used to compute similarity measures between an abstract description and a code fragment in terms of the probability that a given abstract statement can generate a given code fragment. The abstract-description-to-code matcher is under implementation and early experiments show it is a promising technique.
Given the large communication overheads characteristic of modern parallel machines, optimizations that eliminate, hide or parallelize communication may improve the performance of parallel computations. This paper desc...
详细信息
Given the large communication overheads characteristic of modern parallel machines, optimizations that eliminate, hide or parallelize communication may improve the performance of parallel computations. This paper describes our experience automatically applying communication optimizations in the context of Jade, a portable, implicitly parallel programminglanguagedesigned for exploiting task-level concurrency. Jade programmers start with a program written in a standard serial, imperative language, then use Jade constructs to declare how parts of the program access data. The Jade implementation uses this data access information to automatically extract the concurrency and apply communication optimizations. Jade implementations exist for both shared memory and message passing machines; each Jade implementation applies communication optimizations appropriate for the machine on which it runs. We present performance results for several Jade applications running on both a shared memory machine (the Stanford DASH machine) and a message passing machine (the Intel iPSC/860). We use these results to characterize the overall performance impact of the communication optimizations. For our application set replicating data for concurrent read access and improving the locality of the computation by placing tasks close to the data that they access are the most important optimizations. Broadcasting widely accessed data has a significant performance impact on one application; other optimizations such as concurrently fetching remote data and overlapping computation with communication have no effect.
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms we...
详细信息
ISBN:
(纸本)089791662X
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms were proposed recently to alleviate this problem. Both require the flowgraph and the program dependence graph of the program to be modified. In this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. We also show that this algorithm permits an extremely efficient, conservative adaptation for use with programs that contain only `structured' jump statements.
Object-oriented programs are difficult to optimize because they execute many dynamically-dispatched calls. These calls cannot easily be eliminated because the compiler does not know which callee will be invoked at run...
详细信息
ISBN:
(纸本)089791662X
Object-oriented programs are difficult to optimize because they execute many dynamically-dispatched calls. These calls cannot easily be eliminated because the compiler does not know which callee will be invoked at runtime. We have developed a simple technique that feeds back type information from the runtime system to the compiler. With this type feedback, the compiler can inline any dynamically-dispatched call. Our compiler drastically reduces the call frequency of a suite of large SELF applications (by a factor of 3.6) and improves performance by a factor of 1.7. We believe that type feedback could significantly reduce call frequencies and improve performance for most other object-oriented languages (statically-typed or not) as well as for languages with type-dependent operations such as generic arithmetic.
Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a...
详细信息
ISBN:
(纸本)089791662X
Type analysis of Prolog is of primary importance for high-performance compilers, since type information may lead to better indexing and to sophisticated specializations of unification and built-in predicates to name a few. However, these optimizations often require a sophisticated type inference system capable of inferring disjunctive and recursive types and hence expensive in computation time. The purpose of this paper is to describe a type analysis system for Prolog based on abstract interpretation and type graphs (i.e. disjunctive rational trees) with this functionality. The system (about 15,000 lines of C) consists of the combination of a generic fixpoint algorithm, a generic pattern domain, and a type graph domain. The main contribution of the paper is to show that this approach can be engineered to be practical for medium-sized programs without sacrificing accuracy. The main technical contributions to achieve this result are (1) a novel widening operator for type graphs which appears to be accurate and effective in keeping the sizes of the graphs, and hence the computation time, reasonably small;(2) the use of the generic pattern domain to obtain a compact representation of equality constraints between subterms and to factor out sure structural information.
Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondete...
详细信息
ISBN:
(纸本)089791662X
Constraint logic programming (CLP) is a generalization of logic programming where unification is replaced by constraint solving as the basic operation of the language. The combination of constraint solving and nondeterminism (approximated by backtracking) makes these languages appealing for a variety of combinatorial search problems. Existing CLP languages support backtracking by generalizing traditional Prolog implementations: modifications to the constraint system are trailed and restored on backtracking. Although simple and efficient, trailing may be very demanding in memory space, since the constraint system may potentially be saved at each choice point. This paper proposes a fundamentally new implementation scheme for backtracking in CLP languages over linear (rational or real) arithmetic. The new scheme, called semantic backtracking, does not use trailing but rather exploits the semantics of the constraints to undo the effect of newly added constraints. Semantic backtracking reduces the space complexity by an order of magnitude compared to implementations based on trailing and makes space complexity essentially independent of the number of choice points. In addition, semantic backtracking introduces negligible space and time overhead on deterministic programs. The price for this improvement is an increase in backtracking time, although constraint-solving time may actually decrease. The scheme has been implemented as part of a complete CLP system CLP (RLin) and compared analytically and experimentally with an optimized trailing implementation. Experimental results indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small.
暂无评论