Using paths to measure, explain, and enhance program behavior

What happens when a computer program runs? The answer can be frustratingly elusive, as anyone who has debugged or tuned a program knows. As it runs, a program overwrites its previous state, which might have provided a clue as to how the program got to the point at which it computed the wrong answer or otherwise failed. This all-too-common experience is symptomatic of a more general problem: the difficulty of accurately and efficiently capturing and analyzing the sequence of events that occur when a program executes. Program paths offer an insight into a program's dynamic behavior that is difficult to achieve any other way. Unlike simpler measures such as program profiles, which aggregate information to reduce the cost of collecting or storing data, paths capture some of the usually invisible dynamic sequencing of statements. The article exploits the insight that program statements do not execute in isolation, but are typically correlated with the behavior of previously executed code     

Compiling lisp programs for parallel execution

Curare, the program restructurer described in this paper automatically transforms a sequential Lisp program into an equivalent concurrent program that runs on a multiprocessor.Data dependences constrain the program's concurrent execution because, in general, two conflicting statements cannot execute in a different order without affecting the program's result. Not all dependences are essential to produce the program's result.Curare attempts to transform the program so it computes its result with fewer conflicts. An optimized program will execute with less synchronization and more concurrency. Curare then examines loops in a program to find those that are unconstrained or lightly constrained by dependences. By necessity,Curare treats recursive functions as loops and does not limit itself to explicit program loops. Recursive functions offer several advantages over explicit loops since they provide a convenient framework for inserting locks and handling the dynamic behavior of symbolic programs. Loops that are suitable for concurrent execution are changed to execute on a set of concurrent server processes. These servers execute single loop iterations and therefore need to be extremely inexpensive to invoke.Restructured programs execute significantly faster than the original sequential programs. This improvement is large enough to attract programmers to a multiprocessor, particularly since it requires little effort on their part.This research was funded by DARPA contract numbers N00039-85-C-0269 (SPUR) and N00039-84-C-0089 (XCS) and by an NSF Presidential Young Investigator award to Paul N. Hilfinger. Additional funding came from the California MICRO program (in conjunction with Texas Instruments, Xerox, Honeywell, and Phillips/Signetics).     

Slice-based statistical fault localization

Recent techniques for fault localization statistically analyze coverage information of a set of test runs to measure the correlations between program entities and program failures. However, coverage information cannot identify those program entities whose execution affects the output and therefore weakens the aforementioned correlations. This paper proposes a slice-based statistical fault localization approach to address this problem. Our approach utilizes program slices of a set of test runs to capture the influence of a program entity's execution on the output, and uses statistical analysis to measure the suspiciousness of each program entity being faulty. In addition, this paper presents a new slicing approach called approximate dynamic backward slice to balance the size and accuracy of a slice, and applies this slice to our statistical approach. We use two standard benchmarks and three real-life UNIX utility programs as our subjects, and compare our approach with a sufficient number of fault localization techniques. The experimental results show that our approach can significantly improve the effectiveness of fault localization.     

An efficient dynamic program slicing technique

An important application of the dynamic program slicing technique is program debugging. In applications such as interactive debugging, the dynamic slicing algorithm needs to be efficient. In this context, we propose a new dynamic program slicing technique that is more efficient than the related algorithms reported in the literature. We use the program dependence graph as an intermediate program representation, and modify it by introducing the concepts of stable and unstable edges. Our algorithm is based on marking and unmarking the unstable edges as and when the dependences arise and cease during run-time. We call this algorithm edge-marking algorithm. After an execution of a node x, an unstable edge (x, y) is marked if the node x uses the value of the variable defined at node y. A marked unstable edge (x, y) is unmarked after an execution of a node z if the nodes y and z define the same variable var, and the value of var computed at the node y does not affect the present value of var defined at the node z. We show that our algorithm is more time and space efficient than the existing ones. The worst case space complexity of our algorithm is O(n²), where n is the number of statements in the program. We also briefly discuss an implementation of our algorithm.     

Semantics guided regression test cost reduction

Software maintainers are faced with the task of regression testing: retesting a modified program on an often large number of test cases. The cost of regression testing can be reduced if the size of the program is reduced and if old test cases and results can be reused. Two complimentary algorithms for reducing the cost of regression testing are presented. The first produces a program called Differences that captures the semantic change between Certified, a previously tested program, and Modified, a changed version of Certified. It is more efficient to test Differences, because it omits unchanged computations. The program Differences is computed using a combination of program slices. The second algorithm identifies test cases for which Certified and Modified produce the same output and existing test cases that test new components in Modified. The algorithm is based on the notion of common execution patterns. Program components with common execution patterns have the same execution pattern during some call to their procedure. They are computed using a calling context slice. Whereas an interprocedural slice includes the program components necessary to capture all possible executions of a statement, a calling context slice includes only those program components necessary to capture the execution of a statement in a particular calling context. Together with Differences, it is possible to test Modified by running Differences on a smaller number of test cases. This is more efficient than running Modified on a large number of test cases. A prototype implementation has been built to examine and illustrate these algorithms     

Early desire

EARLY DESIRE (Direct Executing SImulation in REal time) is the first of a series of entirely new floating-point equation-language systems for interactive continuous-system simulation. DESIRE systems combine high computing speed (1.3 to 4 times faster that threaded FORTRAN) with immediate direct execution: no external compiler, linker, or loader is needed. DESIRE employs an interpreted job-control language (essentially an advanced BASIC dialect) for slower operations such as interactive program entry, editing, file manipulation, and for programming multi-run simulation studies. The ‘dynamic’ program segment containing differential equations in first-order form is entered just like the BASIC statements and can freely access the same named variables. The relative simplicity of the time-critical dynamic segment permits us to compile it practically instantaneously into efficient machine code, since a simple, super-fast compiler will do. DESIRE utilizes existing, precompiled FORTRAN integration routines; different integration rules can be switched as disk overlays while the program runs. EARLY DESIRE runs on PDP-11 or LSI-11 mini/microcomputers. Future DESIRE systems will download dynamic program segments into a variety of multiple execution processors.Thereafter rose Desire in the beginning; Desire, the primal germ and seed of Spirit.     

基于动态反馈的标志位线性分析算法

二进制翻译可以用于解决遗产代码的迁移问题,也可以实现不同硬件平台之间软件的通用.如果源平台通过标志位进行条件跳转,那么如何处理标志位就成为翻译中的一个重要问题,对翻译的代码质量起着决定性作用.提出标志位线性分析算法,复杂度为线性,基本上能够消除所有的标志位冗余计算,提高了动态执行的效率.基于动态profiling技术,消除了间接跳转的基本块标志位冗余计算.分析了spec 2000中的大部分整点测试例子,实验结果表明,EfLA(Eflag linear analysis)算法对于大运算量的程序是非常有效的.     

The programming language superpascal

This paper defines SuperPascal—a secure programming language for publication of parallel scientific algorithms. SuperPascal extends a subset of IEEE Standard Pascal with deterministic statements for parallel processes and synchronous message communication. A parallel statement denotes parallel execution of a fixed number of statements. A forall statement denotes parallel execution of the same statement by a dynamic number of processes. Recursive procedures may be combined with parallel and forall statements to define recursive parallel processes. Parallel processes communicate by sending typed messages through channels created dynamically. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single-pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables.     

Specifying and Automatically Generating a Specialization Tool for Fortran 90

Partial evaluation is an optimization technique traditionally used in compilation. We have adapted this technique to the understanding of scientific application programs during their maintenance. We have implemented a tool that analyzes Fortran 90 application programs and performs an interprocedural pointer analysis. This paper presents a dynamic semantics of Fortran 90 and manually derives a partial evaluator from this semantics. The tool implementing the specifications is also detailed. The partial evaluator has been implemented in a generic programming environment and a graphical interface has been developed to visualize the information computed during the partial evaluation (values of variables, already analyzed procedures, scope of variables, removed statements, etc.).     

Iterative selection algorithm for service composition in distributed environments

In service oriented architecture （SOA）, service composition is a promising way to create new services. However, some technical challenges are hindering the application of service composition. One of the greatest challenges for composite service provider is to select a set of services to instantiate composite service with end- to-end quality of service （QoS） assurance across different autonomous networks and business regions. This paper presents an iterative service selection algorithm for quality driven service composition. The algorithm runs on a peer-to-peer （P2P） service execution environment--distributed intelligent service execution （DISE）, which provides scalable QoS registry, dynamic service selection and service execution services. The most significant feature of our iterative service selection algorithm is that it can work on a centralized QoS registry as well as cross decentralized ones. Network status is an optional factor in our QoS model and selection algorithm. The algorithm iteratively selects services following service execution order, so it can be applied either before service execution or at service run-time without any modification. We test our algorithm with a series of experiments on DISE. Experimental results illustrated its excellent selection and outstanding performance.     

一种基于谓词分层覆盖矩阵的缺陷定位方法

基于程序频谱的动态缺陷定位(spectrum based dynamic fault localization,简称SFL)可分为基于可执行语句覆盖的方法和基于谓词覆盖的方法。通过分析以上两类方法可以发现：(1) 基于可执行语句覆盖的方法未考虑谓词错误和执行结果之间的关联。(2)基于谓词覆盖的方法只针对谓词进行插桩,最后只计算谓词的可疑度并对谓词进行排序。如果缺陷是非谓词,此类方法无法准确定位缺陷位置。(3) 忽略了基本块之间的关联和层次特性,将各个基本块看成相互独立的个体。为解决上述问题,首先,本文将谓词错误与执行结果之间的关联性这一有用信息加入到算法的设计中;其次,加入谓词分层覆盖与分析的思想,对覆盖矩阵中的基本块进行细分和分层;最后,将二者结合,提出一种基于谓词分层覆盖矩阵的缺陷定位方法,提出了谓词分层覆盖算法Phcm。本文将西门子程序集作为目标程序,通过与其他三种缺陷定位方法进行对比实验,验证了该方法在提高缺陷定位的精准度和减小代码检查率上的有效性。     

Fault localization based on information flow coverage

Failures triggered by hard to debug defects usually involve complex interactions between many program elements. This paper hypothesizes that information flows present a good model for such interactions and presents a new fault localization technique based on information flow coverage. Using a test suite, the technique ranks the statements in a program in terms of their likelihood of being faulty by comparing the information flows induced by the failing runs with the ones induced by the passing runs. The ranking of the statements associated with a given flow is primarily determined by contrasting the percentage of failing runs to the percentage of passing runs that induced it. Generally, a higher percentage of failing runs implies a higher rank. To show its potential, the technique was applied to several open‐source Java programs and was compared, with respect to its fault localization effectiveness, with three other coverage techniques that use similar style metrics that are defined for statements, branches, and def–use pairs, respectively. The results revealed that information flow, branch, and def–use coverage performed consistently better than statement coverage. In addition, in a considerable number of cases information flow coverage performed better than branch and def–use coverage. Specifically, it was always safer but not always more precise. Copyright © 2009 John Wiley & Sons, Ltd.     

基于构图覆盖的软件需求检测方法

以需求描述模型RTRSM为基础，通过建立抽象的、能将控制流和数据流等有机地结合到一起的实时软件的动态执行模型，提出了构图覆盖的动态检测方法，并给出了其具体算法．该方法能检测嵌入式实时软件系统动态执行步中各并行成分及其相互间的执行情况，而且也可为分析员提供一些有用的检测信息以提高分析和检测软件需求的效率．     

TheaddapSystem on the iPSC/860: Automatic Data Distribution and Parallelization

This paper describes theaddapsystem—a parallelizing compiler for distributed memorymimdmachines that automatically computes a data distribution for the arrays of the source program by a branch-and-bound algorithm and parallelizes the inner loops of the program by inserting the necessary communication statements to access nonlocal array sections. The branch-and-bound algorithm incrementally constructs paths in a decision tree where each node on a path corresponds to the distribution of an array of the source program. For each path, a communication analysis tool computes the corresponding communication costs. Based on these costs, the data distribution algorithm tries to find the best data distribution by searching for the cheapest path from a leaf to the root of the decision tree. By rejecting expensive paths as early as possible, the algorithm actually builds only a few paths, corresponding to a small fraction of the decision tree. Therefore, the runtime of the data distribution phase remains quite small also for larger input programs. The structure of the algorithm makes it easy to allow redistributions during program execution. The communication analysis tool computes the communication costs of a data distribution by determining the number and size of the messages that each processor has to receive during program execution. The tool also takes sequentializations into account that are caused by data dependences. A prototype implementation of the system generates code for an Intel iPSC/860. Tests show that the communication costs are determined quite accurately and that the array distributions computed cause only a small communication overhead compared to other data distributions. This results in good speedup values for most of the parallelized programs.     

Redundant synchronization elimination for DOACROSS loops

Cross-iterations data dependences in DOACROSS loops require explicit data synchronizations to enforce them. However, the composite effect of some data synchronizations may cover the other dependences and make the enforcement of those covered dependences redundant. In this paper, we propose an efficient and general algorithm to identify redundant synchronizations in multiply nested DOACROSS loops which may have multiple statements and loop-exit control branches. Eliminating redundant synchronizations in DOACROSS loops allows more efficient execution of such loops. We also address the issues of enforcing data synchronizations in iterations near the boundary of the iteration space. Because some dependences may not exist in those boundary iterations, it adds complexity in determining the redundant synchronizations for those boundary iterations. The necessary and sufficient condition under which the synchronization is uniformly redundant is also studied. These results allow a parallelizing compiler to generate efficient data synchronization instructions for DOACROSS loops     

针对基于变异错误定位的一种动态变异执行策略

在软件调试过程中,如何快速、精确地定位程序中的错误代码是软件开发人员普遍关注的问题。基于变异的错误定位方法是一种通过分析被测程序与程序变异体之间的行为相似性来估计语句出错概率、进行错误定位的方法。该方法有较高的错误定位精确度,但由于需对大量程序变异体执行测试用例集,因此其变异执行开销较大。为此提出了一种动态变异执行策略,它通过搜集测试用例执行信息,动态地调整变异体及测试用例的执行顺序,以减少其变异执行开销。实验结果表明,在6个程序包的127个错误版本上,应用提出的动态变异执行策略可在保证错误定位精确度的前提下,减少23%~78%的变异执行开销,显著提高了基于变异的错误定位方法的效率。     

An experimental evaluation of data dependence analysis techniques

Optimizing compilers rely upon program analysis techniques to detect data dependences between program statements. Data dependence information captures the essential ordering constraints of the statements in a program that need to be preserved in order to produce valid optimized and parallel code. Data dependence testing is very important for automatic parallelization, vectorization, and any other code transformation. In this paper, we examine the impact of data dependence analysis in practice. A number of data dependence tests have been proposed in the literature. In each test, there are different trade offs between accuracy and efficiency. We present an experimental evaluation of several data dependence tests, including the Banerjee test, the I-Test, and the Omega test. We compare these tests in terms of data dependence accuracy, compilation efficiency, effectiveness in parallelization, and program execution performance. We analyze the reasons why a data dependence test can be inexact and we explain how the examined tests handle such cases. We run various experiments using the Perfect Club Benchmarks and the scientific library Lapack. We present the measured accuracy of each test and the reasons for any approximation. We compare these tests in term's of efficiency and we analyze the trade offs between accuracy and efficiency. We also determine the impact of each data dependence test on the total compilation time. Finally, we measure the number of loops parallelized by each test and we compare the execution performance of each benchmark on a multiprocessor. Our results indicate that the Omega test is more accurate, but also very inefficient in the cases where the other two tests are inaccurate. In general, the cost of the Omega test is high and uses a significant percentage of the total compilation time. Furthermore, the difference in accuracy of the Omega test over the Banerjee test and the l-Test does not improve parallelization and program execution performance.     

失效上下文统计分析的软件故障定位方法

针对程序切片方法不提供语句的可疑程度描述,而覆盖分析方法不能充分分析程序元素间的相互影响等问题,提出上下文统计分析的软件故障定位方法。首先,将源程序转换为抽象语法树和程序依赖图;接下来,插桩程序,收集运行时信息;然后,根据失效点,执行按需的反向动态切片,确定失效产生的上下文;最后,对于反向动态切片中的节点,统计计算可疑度,输出带可疑度排序的动态程序切片。该方法不但描述了失效产生的上下文,还计算上下文中各个语句的可疑度。实验结果表明,所提方法与单一的覆盖分析方法相比,平均Expense降低了1.3%,与单一的切片方法相比,平均Expense降低了5.6%,所提方法可以有效辅助开发人员定位与修正软件缺陷。     

Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times

This paper addresses scheduling problems for tasks with release and execution times. We present a number of efficient and easy to implement algorithms for constructing schedules of minimum makespan when the number of distinct task execution times is fixed. For a set of independent tasks, our algorithm in the single processor case runs in time linear in the number of tasks; with precedence constraints, our algorithm runs in time linear in the sum of the number of tasks and the size of the precedence constraints. In the multi-processor case, our algorithm constructs minimum makespan schedules for independent tasks with uniform execution times. The algorithm runs in O(n log m) time where n is the number of tasks and m is the number of processors. Received September 25, 1997; revised June 11, 1998.     

Veristic variables

We distinguish between variables having only one solution (possibilistic) and those allowing multiple solutions (veristic). A representation of information contained in statements involving veristic variables is presented. Using this representation we begin to develop a structure for the manipulation of knowledge involving variables that can have multiple solutions. The verity distribution is introduced to capture information about these variables. We show how to combine information involving veristic variables. We study qualified and quantified statements as well as the entailment and extension principles in this framework.