Efficient program tracing

A program trace lists the addresses of instructions executed and data referenced during a program's execution. Earlier approaches to collecting program traces, including abstract execution and optimal control tracing, are reviewed. Two tracing systems based on these techniques are presented. Results collected when using the later systems on several programs show significant reductions in the cost of collecting traces. Reduction in trace file sizes are also significant     

TraceAnalyzer: a system for processing performance traces

The performance of a program often varies significantly over the course of the program's run. Thus, to understand the performance of a program it is valuable to look not just at end‐to‐end metrics (e.g. total number of cache misses) but also the time‐varying performance of the program. Unfortunately, analyzing time‐varying performance is both cumbersome and difficult. This paper makes three contributions, all geared toward helping others in working with traces. First, it describes a system, the TraceAnalyzer, designed specifically for working with performance traces; a performance trace captures the time‐varying performance of a program run. Second, it describes lessons that we have learned from many years of working with these traces. Finally, it uses a case study to demonstrate how we have used the TraceAnalyzer to understand a performance anomaly. Copyright © 2010 John Wiley & Sons, Ltd.     

Perturbing and evaluating numerical programs without recompilation—the wonglediff way

wonglediff is a program that tests the sensitivity of arbitrary program executables or processes to changes that are introduced by a process that runs in parallel. On Unix and Linux kernels, wonglediff creates a supervisor process that runs applications and, on the fly, introduces desired changes to their process state. When execution terminates, it then summarizes the resulting changes in the output files. The technique employed has a variety of uses. This paper describes an implementation of wonglediff that checks the sensitivity of programs to random changes in the floating‐point rounding modes. It runs a program several times, ‘wongling’ it each time: randomly toggling the IEEE‐754 rounding mode of the program as it executes. By comparing the resulting output, one gets a poor man's numerical stability analysis for the program. Although the analysis does not give any kind of guarantee about a program's stability, it can reveal genuine instability, and it does serve as a particularly useful and revealing idiot light. In our implementation, differences among the output files from the program's multiple runs are summarized in a report. This report is in fact an HTML version of the output file, with inline mark‐up summarizing individual differences among the multiple instances. When viewed with a browser, the differences can be highlighted or rendered in many different ways. Copyright © 2004 John Wiley & Sons, Ltd.     

A static analyzer for finding dynamic programming errors

There are important classes of programming errors that are hard to diagnose, both manually and automatically, because they involve a program's dynamic behavior. This article describes a compile‐time analyzer that detects these dynamic errors in large, real‐world programs. The analyzer traces execution paths through the source code, modeling memory and reporting inconsistencies. In addition to avoiding false paths through the program, this approach provides valuable contextual information to the programmer who needs to understand and repair the defects. Automatically‐created models, abstracting the behavior of individual functions, allow inter‐procedural defects to be detected efficiently. A product built on these techniques has been used effectively on several large commercial programs. Copyright © 2000 John Wiley & Sons, Ltd.     

面向未解释程序的合作验证方法

未解释程序的验证问题通常是不可判定的,但是最近有研究发现,存在一类满足coherence性质的未解释程序,其验证问题是可判定的,并且计算复杂度为PSPACE完全的.在这个结果的基础上,一个针对一般未解释程序验证的基于路径抽象的反例抽象精化（CEGAR）框架被提出,并展现了良好的验证效率.即使如此,对未解释程序的验证工作依然需要多次迭代,特别是利用该方法在针对多个程序验证时,不同的程序之间的验证过程是彼此独立的,存在验证开销巨大的问题.本文发现被验证的程序之间较为相似时,不可行路径的抽象模型可以在不同的程序之间复用.因此,本文提出了一个合作验证的框架,收集在验证过程中不可行路径的抽象模型,并在对新程序进行验证时,用已保存的抽象模型对程序进行精化,提前删减一些已验证的程序路径,从而提高验证效率.此外,本文通过对验证过程中的状态信息进行精简,对现有的基于状态等价的路径抽象方法进行优化,以进一步提升其泛化能力.本文对合作验证的框架以及路径抽象的优化方法进行了实现,并在两个具有代表性的程序集上分别取得了2.70x和1.49x的加速.     

Accuracy of memory reference traces of parallel computations intrace-drive simulation

For given input the global trace generated by a parallel program in a shared memory multiprocessing environment may change as the memory architecture, and management policies change. A method is proposed for ensuring that a correct global trace is generated in the new environment. This method involves a new characterization of a parallel program that identifies its address change points and address affecting points. An extension of traditional process traces, called the intrinsic trace of each process, is developed. The intrinsic traces maximize the decoupling of program execution from simulation by describing the address flow graph and path expressions of each process program. At each point where an address is issued, the trace-driven simulator uses the intrinsic traces and the sequence of loads and stores before the current cycle, to determine the next address. The mapping between load and store sequences and next addresses to issue, sometimes, requires partial program reexecution. Programs that do not require partial program reexecution are called graph-traceable     

On estimating the useful work distribution of parallel programs under P3T: a static performance estimator

In order to improve a parallel program's performance it is critical to evaluate how even the work contained in a program is distributed over all processors dedicated to the computation. Traditional work distribution analysis is commonly performed at the machine level. The disadvantage of this method is that it cannot identify whether the processors are performing useful or redundant (replicated) work. The paper describes a novel method of statically estimating the useful work distribution of distributed-memory parallel programs at the program level, which carefully distinguishes between useful and redundant work. The amount of work contained in a parallel program, which correlates with the number of loop iterations to be executed by each processor, is estimated by accurately modeling loop iteration spaces, array access patterns and data distributions. A cost function defines the useful work distribution of loops, procedures and the entire program. Lower and upper bounds of the described parameter are presented. The computational complexity of the cost function is independent of the program's problem size, statement execution and loop iteration counts. As a consequence, estimating the work distribution based on the described method is considerably faster than simulating or actually compiling and executing the program. Automatically estimating the useful work distribution is fully implemented as part of P³T, which is a static parameter based performance prediction tool under the Vienna Fortran Compilation System (VFCS). The Lawrence Livermore Loops are used as a test case to verify the approach.     

多个NIOS程序在EPCS中的存储及切换运行

针对Altera FPGA,提出了一种在EPCS Flash中存入多个NIOS Ⅱ嵌入式程序(不同的配置文件和NIOS Ⅱ应用文件)并实现程序间相互切换运行的方法.通过搭建平台并以两个嵌入式程序为例,分别分析了它们的配置及引导流程,阐述了程序存储及切换运行的具体方法,实验结果证明了该方法的可行性.该方法使得带NIOS Ⅱ软核的FPGA嵌入式系统在调试以及应用上更加方便灵活,尤其针对系统程序的远程更新,在不破坏原有程序的基础上即可完成,大大提升了系统的安全性.     

Manipulating Wi‐Fi packet traces with WiPal: design and experience

Packet traces are important objects in networking, commonly used in a wide set of applications, including monitoring, troubleshooting, measurements, and validation, to cite a few. Many tools exist to produce and process such traces, but they are often too specific; using them as a basis for creating extended tools is then impractical. Some other tools are generic enough, but exhibit performance issues. This paper reports on our experience designing WiPal, a packet trace manipulation framework with a focus on IEEE 802.11. WiPal is designed for performance and re‐usability, while introducing several novel features compared to previous solutions. Besides presenting how WiPal's original design can benefit packet processing programs, we discuss a number of issues a program designer might encounter when writing packet trace processing software. An evaluation of WiPal shows that, albeit generic, it does not impact performance regarding execution speed. WiPal achieves performance levels observed only with specialized code and outperforms some well‐known packet processing programs. Copyright © 2011 John Wiley & Sons, Ltd.     

Event Handling in the Lego System

An event is an action that alters a program's normal flow of execution. Events can be classified into asynchronous (such as the expiration of a timer or a request to terminate a process) and synchronous (for example, arithmetic and protection faults). When an event occurs during the execution of a process, specialized software is required, either in the kernel, the process, or both. This paper describes the experiences gained in the design, implementation and operation of the event handling mechanism developed for the message-based Lego kernel and distributed system running on the iAPx86 platform. The resulting implementation is a uniform communication interface, treating all events as messages, thereby maintaining Lego's send-receive paradigm. This implementation ensures that event messages follow processes that have migrated and permit the implementation of group event software. Several applications of the event handling software are presented, as is a discussion of the design tradeoffs. The paper concludes that although the basic concept of message-based event handling is well understood, a system's process naming technique can influence how events are handled in a migration and with process groups. © 1997 by John Wiley & Sons, Ltd.     

Partial Order Trace Analyzer (POTA) for Distributed Programs

Checking the correctness of software is a growing challenge. In this paper, we present a prototype implementation of Partial Order Trace Analyzer (POTA), a tool for checking execution traces of both message passing and shared memory programs using temporal logic. So far runtime verification tools have used the total order model of an execution trace, whereas POTA uses a partial order model. The partial order model enables us to capture possibly exponential number of interleavings and, in turn, this allows us to find bugs that are not found using a total order model. However, verification in partial order model suffers from the state explosion problem – the number of possible global states in a program increases exponentially with the number of processes.POTA employs an effective abstraction technique called computation slicing. A slice of a computation (execution trace) with respect to a predicate is the computation with the least number of global states that contains all global states of the original computation for which the predicate evaluates to true. The advantage of this technique is that, it mitigates the state explosion problem by reasoning only on the part of the global state space that is of interest. In POTA, we implement computing slicing algorithms for temporal logic predicates from a subset of CTL. The overall complexity of evaluating a predicate in this logic upon using computation slicing becomes polynomial in the number of processes compared to exponential without slicing.We illustrate the effectiveness of our techniques in POTA on several test cases such as the General Inter-ORB Protocol (GIOP)[18] and the primary secondary protocol[32]. POTA also contains a module that translates execution traces to Promela[16] (input language SPIN). This module enables us to compare our results on execution traces with SPIN. In some cases, we were able to verify traces with 250 processes compared to only 10 processes using SPIN.     

Determining possible event orders by analyzing sequential traces

One of the fundamental problems encountered when debugging a parallel program is determining the possible orders in which events could have occurred. Various problems, such as data races and intermittent deadlock, arise when there is insufficient synchronization between the tasks in a parallel program. A sequential trace of an execution can be misleading, as it implies additional event orderings, distorting the concurrent nature of the computation. Algorithms to generate, from the trace of an execution, those event orderings that can be relied on by the programmer are described. By its very nature, the information in an execution trace pertains only to that execution of the program, and may not generalize to other executions. This difficulty is mitigated by defining an inferred program based on the trace and original program, analyzing this inferred program, and showing how the inferred program relates to the original. The results of the algorithms can be used by other automated tools such as a data race detector or constraint checker     

BIFER: a biphasic trace filter approach to scalable prediction of concurrency errors

Predictive trace analysis (PTA), a static trace analysis technique for concurrent programs, can offer powerful capability support for finding concurrency errors unseen in a previous program execution. Existing PTA techniques always face considerable challenges in scaling to large traces which contain numerous critical events. One main reason is that an analyzed trace includes not only redundant memory accessing events and threads that cannot contribute to discovering any additional errors different from the found candidate ones, but also many residual synchronization events which still affect PTA to check whether these candidate ones are feasible or not even after removing the redundant events. Removing them from the trace can significantly improve the scalability of PTA without affecting the quality of the PTA results. In this paper, we propose a biphasic trace filter approach, BIFER in short, to filter these redundant events and residual events for improving the scalability of PTA to expose general concurrency errors. In addition, we design a model which indicates the lock history and the happens-before history of each thread with two kinds of ways to achieve the efficient filtering. We implement a prototypical tool BIFER for Java programs on the basis of a predictive trace analysis framework. Experiments show that BIFER can improve the scalability of PTA during the process of analyzing all of the traces.     

Converting interpreters into compilers

There is an effective and quite general method of manually deriving compilers from programming-language interpreters without dealing directly with machine language. The method is an implementation of the largely theoretical and under-appreciated concept of partial computation, but can be understood on its own terms. It involves the translation of a source program's intermediate form into the interpreter's implementation language. This paper shows how the method can be used to transform both a sample iterative interpreter and a sample recursive interpreter into compilers. The result can be a large gain in program execution speed. Other advantages of the method, including the ease and practicality of applying it, are discussed.     

A Case for Compressing Traces with BDDs

Instruction-level traces are widely used for program and hardware analysis. However, program traces for just a few seconds of execution are enormous, up to several terabytes in size, uncompressed. Specialized compression can shrink traces to a few gigabytes, but trace analyzers typically stream the decompressed trace through the analysis engine. Thus, the complexity of analysis depends on the decompressed trace size (even though the decompressed trace is never stored to disk). This makes many global or interactive analyses infeasible. This paper presents a method to compress program traces using binary decision diagrams (BDDs). BDDs intrinsically support operations common to many desirable program analyses and these analyses operate directly on the BDD. Thus, they are often polynomial in the size of the compressed representation. The paper presents mechanisms to represent a variety of trace data using BDDs and shows that BDDs can store, in 1 GB of RAM, the entire data-dependence graph of traces with over 1 billion instructions. This allows rapid computation of global analyses such as heap-object liveness and dynamic slicing     

Path Dependent Analysis of Logic Programs

This paper presents an abstract semantics that uses information about execution paths to improve precision of data flow analyses of logic programs. The abstract semantics is illustrated by abstracting execution paths using call strings of fixed length and the last transfer of control. Abstract domains that have been developed for logic program analyses can be used with the new abstract semantics without modification.     

Exploiting traces in static program analysis: better model checking through {{\tt printf}}s

From operating systems and web browsers to spacecraft, many software systems maintain a log of events that provides a partial history of execution, supporting post-mortem (or post-reboot) analysis. Unfortunately, bandwidth, storage limitations, and privacy concerns limit the information content of logs, making it difficult to fully reconstruct execution from these traces. This paper presents a technique for modifying a program such that it can produce exactly those executions consistent with a given (partial) trace of events, enabling efficient analysis of the reduced program. Our method requires no additional history variables to track log events, and it can slice away code that does not execute in a given trace. We describe initial experiences with implementing our ideas by extending the CBMC bounded model checker for C programs. Applying our technique to a small, 400-line file system written in C, we get more than three orders of magnitude improvement in running time over a naïve approach based on adding history variables, along with fifty- to eighty-fold reductions in the sizes of the SAT problems solved.     

Synchronous and asynchronous handling of abnormal events in the μsystem

This paper presents a general model for dealing with abnormal events during program execution and describes how this model is implemented in the μSystem. (The μSystem is a library of C definitions that provide light-weight concurrency on uniprocessor and multiprocessor computers running the UNIX operating system.) Two different techniques can be used to deal with an abnormal event: an exception, which results in an exceptional change in control flow from the point of the abnormal event; and an intervention, which is a routine call from the point of the abnormal event that performs some corrective action. Users can define named exceptions and interventions in conjunction with ones defined by the μSystem. Exception handlers and intervention routines for dealing with abnormal events can be defined/installed at any point in a program. An exception or intervention can then be raised or called, passing data about the abnormal event and returning results for interventions. Interventions can also be activated in other tasks, like a UNIX signal. Such asynchronous interventions may interrupt a task's execution and invoke the specified intervention routine. Asynchronous interventions are found to be useful to get another task's attention when it is not listening through the synchronous communication mechanism.     

Experience compiling Fortran to program dependence graphs

The program dependence graph (PDG) is being used in research projects for compilation to parallel architectures, program version integration and program semantics. This paper describes the methods used in a prototype Fortran-to-PDG translator called the PDG Testbed. Implementation decisions and details of the PDG Testbed project are described as a complement to the formal papers detailing the abstract PDG. In addition, experimental results are given that show the storage consumption for a PDG relative to a conventional internal representation as well as execution times for several analysis and optimization steps.