Programs written for GPUs often contain correctness errors such as races, deadlocks, or may compute the wrong result. Existing debugging tools often miss these errors because of their limited input-space and execution-space exploration. Existing tools based on conservative static analysis or conservative modeling of SIMD concurrency generate false alarms resulting in wasted bug-hunting. They also often do not target performance bugs (non-coalesced memory accesses, memory bank conflicts, and divergent warps). We provide a new framework called GKLEE that can analyze C++ GPU programs, locating the aforesaid correctness and performance bugs. For these programs, GKLEE can also automatically generate tests that provide high coverage. These tests serve as concrete witnesses for every reported bug. They can also be used for downstream debugging, for example to test the kernel on the actual hardware. We describe the architecture of GKLEE, its symbolic virtual machine model, and describe previously unknown bugs and performance issues that it detected on commercial SDK kernels. We describe GKLEE's test-case reduction heuristics, and the resulting scalability improvement for a given coverage target.

To be effective, software model checking needs powerful reduction techniques. In this paper, we present an experimental study that demonstrates effectiveness of environment generation combined with slicing as a model generation and reduction technique. Automatic environments were obtained using the Bandera Environment Generator (BEG) and slicing was performed using the Indus Java slicer. The results show that environment generation implemented in BEG is an aggressive reduction technique. However, it may miss behaviors in the environment and consequently in the module under analysis, making it unsafe. As such, this technique can be effective for detection of errors but not sufficient to prove their absence.Slicing, while a safe technique, may be too approximate and not scalable. Also, slicing implemented in Indus requires a closed system and cannot be safely applied to a module without its environment. In this paper, we show how environment generation and slicing can be combined to detect errors and prove their absence. We applied the combined approach to verify parts of Fujitsu's enterprise software called Interstage Business Process Management (I-BPM)

Model checking can be an effective technique for detecting concurrency-related errors in software systems. However, due to scalability issues, to handle industrial-strength software, model checking needs to be combined with powerful reduction techniques. In this work, we applied modular model checking to detect errors in Interstage Business Process Management (I-BPM) software, a Java client-server application spanning more than 500,000 lines of code. To model check a separate module, one needs to represent its context of execution, i.e., its environment. Environment generation is a significant challenge, since the environment is to be general enough to uncover the module's errors, yet restrictive enough to allow tractable model checking.In this paper, we present an experimental study that demonstrates the effectiveness of environment generation as a reduction technique in general and the effectiveness of automated environment generation in particular. Since model checking of the original application was intractable, we compared performance of automatically generated environments to environments written previously by hand. Automatic environments were obtained using Bandera Environment Generator (BEG). We present results of modular verification for both manual and automatic environments. The results show that automatically generated environments produce systems with a smaller state space, yet, for faulty modules, uncover the errors and, for error-free modules, produce coverage similar to manual environments.

No abstract available.

A standard design methodology for embedded processors today is the system-on-a-chip design with potentially multiple heterogeneous processing elements on a chip, such as a very long instruction word (VLIW) processor, digital signal processor (DSP), and field-programmable gate array. To be able to program these devices, we need compilers that are capable of generating efficient code for the different types of processing elements with efficiency measured in terms of power, area, and execution time. In addition, the compilers should also be highly retargetable to enable the system designer to quickly evaluate different cores for the application on hand and reduce the time to market. In this paper, we show that we can extend a conventional VLIW compilation environment to develop highly retargetable optimizing compilers for DSPs with irregular architectures. We have used the second generation Fujitsu Hiperion fixed-point DSP as our primary example to evaluate the compiler framework. We demonstrate through experimental results that execution time for the assembly code generated using our framework is roughly two times better than that of the code generated by a widely used commercially available DSP compiler. Even without incorporating DSP-specific optimizations in our extended VLIW framework, we demonstrate that the compiled code has a better performance than the code generated by a commercial DSP-specific compiler in all our examples.

This paper describes a novel formal verification approach for equivalence checking of small, assembly-language routines for digital signal processors (DSP). By combining control-flow analysis, symbolic simulation, automatic decision procedures, and some domain-specific optimizations, we have built an automatic verification tool that compares structurally similar DSP assembly language routines. We tested our tool on code samples taken from a real application program and discovered several previously unknown bugs automatically. Runtime and memory requirements were reasonable on all examples. Our approach should generalize easily for multiple DSP architectures, eventually allowing comparison of code for two different DSPs (e.g., to verify a port from one DSP to another) and handling more complex DSPs (e.g. statically-scheduled, VLIW).

Asynchronous Transfer Mode (ATM) has emerged as a backbone for high-speed broadband telecommunication networks. In this paper, we present ATM switch design, starting from a parametric high-level model and debugging the model using a combination of formal verification and simulation. The model has been used to synthesize ATM switches according to customers' choices, by choosing concrete values for each of the generic parameters. We provide a pragmatic combination of simulation, model checking, and theorem proving to gain confidence in the ATM switch design correctness.

In this article we provide a practical transformational approach to the synthesis of correct synchronous digital hardware designs from high-level specifications. We do this while taking into account the complete life cycle of a design from early prototype to full custom implementation. Besides time-to-market, both flexibility with respect to target architecture and efficiency issues are addressed by the methodology. The utilization of user-selected behavior-preserving transformation steps ensures first-time-right design while exploiting the experience, flexibility, and creativity of the designer. To ensure that design transformations are indeed behavior-preserving a novel mechanized approach to the specification and verification of design transformations on control data flow graphs which is independent of a specific behavioral model or graph size has been developed. As a demonstration of an industrial application we use a video processing algorithm needed for the conversion from a line-interlaced to progressively scanned video format. Both a video signal processor-based prototype implementation as well as a very efficient full custom implementation are developed starting from a single high-level behavioral specification of the algorithm in VHDL. Results are compared with those previously obtained using different tools and methodologies.