At the current state of the art, genetic programs do not contain two constructs that commonly occur in programs written by humans, that is, loops and functions with parameters. In this paper we describe an investigati...
详细信息
ISBN:
(纸本)9781424481262
At the current state of the art, genetic programs do not contain two constructs that commonly occur in programs written by humans, that is, loops and functions with parameters. In this paper we describe an investigation into the evolution of programs for a problem that can only be solved by evolving a parameterised program with one or more loops. We provide training examples of the desired program behaviour for a number of problem sizes and require the evolution of a program P(n) that will give the correct output for any value of n. We have chosen a problem, that of reproducing a binary string to a given number of bits, that can be made harder or easier by adjusting various aspects of the formulation. We are interested seeing in which formulations lead to success and which do not. We conclude that programs with parameters and loops can be successfully evolved if the search space is appropriately restricted by (1) grammars which restrict the possible programstructures, (2) limits on program depth and (3) limits on the range of random constants.
Maintenance accounts for the major part of a software system's total costs. Therein, program comprehension is an important, but complex activity: Typically, up-to-date documentation is not available, so the main r...
详细信息
ISBN:
(纸本)9780769542416
Maintenance accounts for the major part of a software system's total costs. Therein, program comprehension is an important, but complex activity: Typically, up-to-date documentation is not available, so the main reliable source of information on the implementation represent the artifacts of the system's implementation. Understanding software systems is difficult, in particular, if multithreading concepts are involved because state-of-the art development tools provide only limited support for maintenance activities. In addition, concurrency is often not directly reflected by the source code, i.e., there is only a non-obvious correlation between controlstructures in the source code and a system's runtime behavior. We present a program comprehension technique that helps to analyze and understand runtime behavior of multithreaded software systems and, thereby, facilitates software maintenance tasks. Our approach contains the following concepts: First, light-weight dynamic analysis records executed method calls at runtime. Second, visualization of multithreading trace data allows developers to explore the system behavior post-mortem. The technique forms part of a scalable tool suite for understanding the behavior of complex software systems. We also show how to apply the technique on industrial software systems to solve common maintenance problems.
Let R be a class of generators of node-labelled infinite trees, and L be a logical language for describing correctness properties of these trees. Given R is an element of R and phi is an element of L, we say that R-ph...
详细信息
ISBN:
(纸本)9780769541143
Let R be a class of generators of node-labelled infinite trees, and L be a logical language for describing correctness properties of these trees. Given R is an element of R and phi is an element of L, we say that R-phi is a phi-reflection of R just if (i) R and R. generate the same underlying tree, and (ii) suppose a node u of the tree [[R]] generated by R has label f, then the label of the node u of [[R.]] is (f) under bar if u in [[R]] satisfies phi;it is f otherwise. Thus if [[R]] is the computation tree of a program R, we may regard R-phi as a transform of R that can internally observe its behaviour against a specification phi. We say that R is (constructively) reflective w.r.t. L just if there is an algorithm that transforms a given pair (R, phi) to R-phi. In this paper, we prove that higher-order recursion schemes are reflective w.r.t. both modal mu-calculus and monadic second order (MSO) logic. To obtain this result, we give the first characterisation of the winning regions of parity games over the transition graphs of collapsible pushdown automata (CPDA): they are regular sets defined by a new class of automata. (Order-n recursion schemes are equi-expressive with order-n CPDA for generating trees.) As a corollary, we show that these schemes are closed under the operation of MSO-interpretation followed by tree unfolding a la Caucal.
Execution and communication traces are central to performance modeling and analysis. Since the traces can be very long, meaningful compression and extraction of representative behavior is important. Commonly used comp...
详细信息
Non-Termination analysis of loop programs plays a central role in many applications, especially in the field of safety critical softwares. This paper presents a method to analyze non-termination of linear programs wit...
详细信息
ISBN:
(纸本)9780769534329
Non-Termination analysis of loop programs plays a central role in many applications, especially in the field of safety critical softwares. This paper presents a method to analyze non-termination of linear programs with conditionals. We transform the linear loop programs with conditionals into the nested linear loop programs, and then check whether the inner loop terminates or not by the positive eigenvalues and their corresponding eigenvectors. If one of the inner loop in the nested linear loop is nonterminating, then the linear loop is nonterminating. Otherwise, we need to use ranking function or finite differences of expressions over transition systems to analyze the termination of the outer loop.
The most promising technique for automatically parallelizing loops when the system cannot determine dependences at compile time is speculative parallelization. Also called thread-level speculation, this technique assu...
详细信息
The most promising technique for automatically parallelizing loops when the system cannot determine dependences at compile time is speculative parallelization. Also called thread-level speculation, this technique assumes optimistically that the system can execute all iterations of a given loop in parallel. A hardware or software monitor divides the iterations into blocks and assigns them to different threads, one per processor, with no prior dependence analysis. If the system discovers a dependence violation at runtime, it stops the incorrectly computed work and restarts it with correct values. Of course, the more parallel the loop, the more benefits this technique delivers. To better understand how speculative parallelization works, it is necessary to distinguish between private and shared variables. Informally speaking, private variables are those that the program always modifies in each iteration before using them. On the other hand, values stored in shared variables are used in different iterations.
Intra-task voltage scheduling (IntraDVS), which adjusts the supply voltage within an individual task boundary, is an effective technique for developing low-power applications. In IntraDVS, slack times are estimated by...
详细信息
ISBN:
(纸本)0780387368
Intra-task voltage scheduling (IntraDVS), which adjusts the supply voltage within an individual task boundary, is an effective technique for developing low-power applications. In IntraDVS, slack times are estimated by analyzing program's control flow information. In this paper, we propose an optimization technique for IntraDVS using data flow information. The proposed algorithm improves the energy efficiency by moving the voltage scaling points to earlier instructions based on the analysis results of program's data flow. The experimental results using an MPEG-4 encoder program show that the proposed algorithm reduces the energy consumption by 40-45% over the original IntraDVS algorithm.
One of the potential difficulties in developing cost-effective value prediction mechanisms is determining which instructions should be selected for prediction when the hardware resources are limited. The authors exami...
详细信息
One of the potential difficulties in developing cost-effective value prediction mechanisms is determining which instructions should be selected for prediction when the hardware resources are limited. The authors examine a compiler algorithm that statically assigns priorities to instructions using approximate critical path information to identify the best candidates for value prediction. This static priority information is encoded into the instructions and subsequently used by the hardware to choose the most critical instructions at run-time for value prediction. The algorithm is implemented in the GCC compiler and performance potential is evaluated using an extended version of the SimpleScalar processor simulator. Our results with the SPEC95 and SPEC2000 benchmark programs show that this approximate algorithm can effectively capture the critical path information to consistently improve the performance of a processor with a hybrid value predictor compared to using no information about the criticality of instructions. Furthermore, it is shown that using only four priority levels encoded into two instruction bits is sufficient to capture enough priority information to effectively use the value prediction hardware.
The new software world is progressing steadily forward but is not yet within range of where it needs to be. This paper presents a mathematical ground for the Lyee methodology, which has already produced several achiev...
详细信息
The new software world is progressing steadily forward but is not yet within range of where it needs to be. This paper presents a mathematical ground for the Lyee methodology, which has already produced several achievements in industry. This method enables us not to attention the sequential order of program execution. By introducing the concept of a state, it is possible to prove the program structure. The construction of such a program structure allows programmers to focus on conditions and formulae that calculate the value. Through this model, a system divided for catching correct requirements quickly is integrated, and its optimal program with minimum repetitions can be generated by rearranging words into the right order. (C) 2003 Published by Elsevier B.V.
This column is about recursion: functions, subroutines, and even whole computer languages defined in terms of themselves. Recursion is a direct and elegant way to translate certain mathematical relations into programs...
详细信息
This column is about recursion: functions, subroutines, and even whole computer languages defined in terms of themselves. Recursion is a direct and elegant way to translate certain mathematical relations into programs, and it's a great technique for discovering efficient algorithms. Given its utility, you might wonder why people seldom use it.
暂无评论