2633029
Principled strength reduction
This paper presents a principled approach for optimizing iterative (or recursive) programs. The approach formulates a loop body as a function f and a change operation ⊕, incrementalizes f with respect to ⊕, and adopts an incrementalized loop body to form a new loop that is more efficient. Three general optimizations are performed as part of the adoption; they systematically handle initializations, termination conditions, and final return values on exits of loops. These optimizations are either omitted, or done in implicit, limited, or ad hoc ways in previous methods.
5528420
Automatic time-bound analysis for a higher-order language
Analysis of program running time is important for several applications, including reactive systems, interactive environments, compiler optimizations and performance evaluation. Automatic and efficient prediction of accurate time bounds is particularly important, and being able to do so for high-level languages is particularly desirable. This paper presents a general approach for automatic and accurate time-bound analysis for a functional high-level language, that combines methods and techniques studied in theory, languages, and systems. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. To handle higher-order functions, special transformations are needed to build lambda expressions for computing running times, to optimize the construction of the time lambda expressions, and to optimize the symbolic evaluation. It took us several tries to obtain the simple and concise transformations for handling lambda expressions. We describe analysis and transformation algorithms and explain how they work. We have implemented this approach and performed a large number of experiments analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds. We describe our prototype system, ALPA, as well as the analysis and measurement results.
9019278
Querying Complex Graphs
This paper presents a powerful language for querying complex graphs and a method for generating efficient implementations that can answer queries with complexity guarantees. The graphs may have edge labels that may have parameters, and easily and naturally capture complex interrelated objects in object-oriented systems and XML data. The language is built on extended regular path expressions with variables and scoping, and can express queries more easily and clearly than previous query languages.The method for implementation first transforms queries into Datalog with limited extensions. It then extends a previous method to generate specialized algorithms and complexity formulas from Datalog with these extensions.
37778003
Automatic Accurate Cost-Bound Analysis for High-Level Languages
This paper describes a language-based approach for automatic and accurate cost-bound analysis. The approach consists of transformations for building cost-bound functions in the presence of partially known input structures, symbolic evaluation of the cost-bound function based on input size parameters, and optimizations to make the overall analysis efficient as well as accurate, all at the source-language level. The calculated cost bounds are expressed in terms of primitive cost parameters. These parameters can be obtained based on the language implementation or can be measured conservatively or approximately, yielding accurate, conservative, or approximate time or space bounds. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The results helped confirm the accuracy of the analysis.
8840929
Optimized Live Heap Bound Analysis
This paper describes a general approach for optimized live heap space and live heap space-bound analyses for garbage-collected languages. The approach is based on program analysis and transformations and is fully automatic. In our experience, the space-bound analysis generally produces accurate (tight) upper bounds in the presence of partially known input structures. The optimization drastically improves the analysis efficiency. The analyses have been implemented and experimental results confirm their accuracy and efficiency.
15838270
Eliminating Dead Code on Recursive Data
This paper describes a general and powerful method for dead code analysis and elimination in the presence of recursive data constructions. We represent partially dead recursive data using liveness patterns based on general regular tree grammars extended with the notion of live and dead, and we formulate the analysis as computing liveness patterns at all program points based on program semantics. This analysis yields a most precise liveness pattern for the data at each program point, which is significantly more precise than results from previous methods. The analysis algorithm takes cubic time in terms of the size of the program in the worst case but is very efficient in practice, as shown by our prototype implementation. The analysis results are used to identify and eliminate dead code. The general framework for representing and analyzing properties of recursive data structures using general regular tree grammars applies to other analyses as well.
7009361
Tractable Reasoning in First-Order Knowledge Bases with Disjunctive Information
This work proposes a new methodology for establishing the tractability of a reasoning service that deals with expressive first-order knowledge bases. It consists of defining a logic that is weaker than classical logic and that has two properties: first, the entailment problem can be reduced to the model checking problem for a small number of characteristic models; and second, the model checking problem itself is tractable for formulas with a bounded number of variables. We show this methodology in action for the reasoning service previously proposed by Liu, Lakemeyer and Levesque for dealing with disjunctive information. They show that their reasoning is tractable in the propositional case and decidable in the first-order case. Here we apply the methodology and prove that the reasoning is also tractable in the first-order case if the knowledge base and the query both use a bounded number of variables.
12158249
Bisingular maps on the sphere and the projective plane
Abstract A map is bisingular if each edge is either a loop or an isthmus (i.e., on the boundary of the same face). In this paper we study the number of rooted bisingular maps on the plane or projective plane and also we present formulae for such maps with up to three or more parameters: the root valency, the number of isthmus, the number of essential loops, and the number of planar loops.
11623191
Mapping component specifications to Enterprise JavaBeans implementations
Component-based software development has become an important approach to building complex software systems. Much research focuses on component specification to achieve the advantages of the component-based approach in theory. Most of this research pays little attention to the mappings from component specifications to component implementations. However, the mappings are important because they determine whether the implementations perform satisfactorily to meet the specifications. After presenting a general approach to component specification and the technology of Enterprise JavaBeans (EJB) component model, this paper presents three approaches to mapping from component specification to EJB implementation. This paper uses a course registration system as an example to demonstrate the ideas. The approaches presented will be helpful to those who are working on the realizations of component systems.
132343
Approaching optimal peer-to-peer overlays
In unstructured peer-to-peer (P2P) systems, there exists a serious topology mismatch problem between physical and logical network. We first analyze the relationship between the property of the overlay and the corresponding message duplications incurred by queries in a given overlay, and prove that computing an optimal overlay with global knowledge is an NP-hard problem. Motivated by the analysis results, we design a distributed overlay optimization algorithm, THANCS, to attack topology mismatch. We demonstrate its performance by comprehensive simulations in dynamic environments. The proposed THANCS has three major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal with other types of advanced search approaches.
30364080
A flexible embedded SRAM compiler
SRAM compiler uses predefined building blocks or leaf cells and connectivity information to compile SRAMs of user-specified size. In this paper, a high-speed embedded SRAM compiler is described. It is based on TSMC's 0.5 /spl mu/m CMOS process. It can compile both single-port and dual-port SRAMs. SRAM is a completely synchronous architecture with a maximal capacity 16k/spl times/64=1 Mb bits. The compiler generates the layout, behavioral level models, schematic symbols, and a layout abstraction to place and route. The program in Skill language can automatically complete the creation of all the models in different levels. The SRAM compiler has a friendly user interface. Users can specify the necessary parameters and then get all the results. The SRAM compiler can be easily integrated into Cadence and other CAD frameworks.