Performance analysis pf parallelizing compilers on the PerfectBenchmarks programs

The speedups of the Perfect Benchmarks codes that result from automatic parallelization are reported. The performance gains caused by individual restructuring techniques have also been measured. Specific reasons for the successes and failures of the transformations are discussed, and potential improvements that result in measurably better program performance are analyzed. The most important findings are that available restructurers often cause insignificant performance gains in real programs and that only few restructuring techniques contribute to this gain. However, it can be shown that there is potential for advancing compiler technology so that many of the most important loops in these programs can be parallelized     

Generic programming techniques for parallelizing and extending procedural finite element programs

We outline an approach for extending procedural finite-element software components using generic programming. A layer of generic software components consisting of C++ containers and algorithms is used for parallelization of the finite-element solver and for solver coupling in multi-physics applications. The advantages of generic programming in connection with finite-element codes are discussed and compared with those of object-oriented programming. The use of the proposed generic programming techniques is demonstrated in a tutorial fashion through basic illustrative examples as well as code excerpts from a large-scale finite-element program for serial and parallel computing platforms.

Heuristics for model checking Java programs

Model checking of software programs has two goals – the verification of correct software and the discovery of errors in faulty software. Some techniques for dealing with the most crucial problem in model checking, the state space explosion problem, concentrate on the first of these goals. In this paper we present an array of heuristic model checking techniques for combating the state space explosion when searching for errors. Previous work on this topic has mostly focused on property-specific heuristics closely related to particular kinds of errors. We present structural heuristics that attempt to explore the structure (branching structure, thread interdependency structure, abstraction structure) of a program in a manner intended to expose errors efficiently. Experimental results show the utility of this class of heuristics. In contrast to these very general heuristics, we also present very lightweight techniques for introducing program-specific heuristic guidance.     

Client-based cohesion metrics for Java programs

One purpose of software metrics is to measure the quality of programs. The results can be for example used to predict maintenance costs or improve code quality. An emerging view is that if software metrics are going to be used to improve quality, they must help in finding code that should be refactored. Often refactoring or applying a design pattern is related to the role of the class to be refactored. In client-based metrics, a project gives the class a context. These metrics measure how a class is used by other classes in the context. We present a new client-based metric LCIC (Lack of Coherence in Clients), which analyses if the class being measured has a coherent set of roles in the program. Interfaces represent the roles of classes. If a class does not have a coherent set of roles, it should be refactored, or a new interface should be defined for the class.We have implemented a tool for measuring the metric LCIC for Java projects in the Eclipse environment. We calculated LCIC values for classes of several open source projects. We compare these results with results of other related metrics, and inspect the measured classes to find out what kind of refactorings are needed. We also analyse the relation of different design patterns and refactorings to our metric. Our experiments reveal the usefulness of client-based metrics to improve the quality of code.     

Dynamic data flow analysis for Java programs

A large portion of high-level computer programs consists of data declaration. Thus, an increased focus on testing the data flow aspects of programs should be considered. In this paper, we consider testing the data flow in Java programs dynamically. Data flow analysis has been applied for testing procedural and some object-oriented programs. We have extended the dynamic data flow analysis technique to test Java programs and show how it can be applied to detect data flow anomalies.     

A mutation analysis tool for Java programs

Program mutation is a fault-based technique for measuring the effectiveness of test cases that, although powerful, is computationally expensive. The principal expense of mutation is that many faulty versions of the program under test, called mutants, must be created and repeatedly executed. This paper describes a tool, called JavaMut, that implements 26 traditional and object-oriented mutation operators for supporting mutation analysis of Java programs. The current version of that tool is based on syntactic analysis and reflection for implementing mutation operators. JavaMut is interactive; it provides a graphical user interface to make mutation analysis faster and less painful. Thanks to such automated tools, mutation analysis should be achieved within reasonable costs.     

一种新的并行Java程序的监护模型

提出了一种新的并行Java程序异常处理的监护模型。该模型针对并行Java程序异步信息传递方式进行异常处理。当并行Java程序的某个线程出现异常时,该线程的监护模块把检测到的异常情况的信息传递到其它线程的监护模块,每个线程根据当前事项与异常事项的向量时钟关系,对当前事项进行回滚或停止操作,以达到对并行Java程序的保护。过去一些并行程序的监护方案是在信息交换的基础上把并行程序结构化为许多原子行为,把多个并行异常当作单个异常进行处理,具有较大的局限性。提出的监护模型是从全局上对并行Java程序的异常情况进行处理,并指导每个线程根据自身情况作出相应反映。实验证明提出的新的并行Java程序监护模型具有较强的实际操作性,并能有效地保护并行Java程序。     

Model-checking multi-threaded distributed Java programs

State-space exploration is a powerful technique for verification of concurrent software systems. Applying it to software systems written in standard programming languages requires powerful abstractions (of data) and reductions (of atomicity), which focus on simplifying the data and control, respectively, by aggregation. We propose a reduction that exploits a common pattern of synchronization, namely, the use of locks to protect shared data structures. This pattern of synchronization is particularly common in concurrent Java programs, because Java provides built-in locks. We describe the design of a new tool for state-less state-space exploration of Java programs that incorporates this reduction. We also describe an implementation of the reduction in Java PathFinder, a more traditional state-space exploration tool for Java programs. Published online: 2 October 2002 RID="*" ID="*"Present address: Computer Science Dept., SUNY at Stony Brook, Stony Brook, NY 11794-4400, USA. The author gratefully acknowledges the support of ONR under Grants N00014-99-1-0358 and N00014-01-1-0109 and the support of NSF under Grant CCR-9876058.     

对Java并发程序进行模型检测

随着多核处理器的发展,多线程并发程序成为现代程序设计的趋势.但并发线程的执行存在不确定性,传统的测试方法很难发现这类错误.针时这个问题,提出了一种直接分析Java源代码,从中提取并发程序模型的方法;并以此方法为基础开发了工具JTS(Java to SPIN),实现了对Java并发程序的自动化分析和模型检测.实验表明JTS能够成功地检测出Java并发程序中存在的错误并给出相应的错误路径.这项工作给Java并发程序的测试与验证提供了新的途径.     

A deadlock detection tool for concurrent Java programs

This paper presents some issues related to the design and implementation of a concurrency analysis tool able to detect deadlock situations in Java programs that make use of multithreading mechanisms. An abstract formal model is generated from the Java source using the Java2Spin translator. The model is expressed in the PROMELA language, and the SPIN tool is used to perform its formal analysis. The paper mainly focuses on the design of the Java2Spin translator. A set of experiments, carried out to evaluate the performances of the analysis tool, is also presented. Copyright © 1999 John Wiley & Sons, Ltd.     

A generic static analyzer for multithreaded Java programs

In this paper, we present heckmate , the first generic static analyzer of multithreaded Java programs based on abstract interpretation. heckmate can be tuned at different levels of precision and efficiency in order to prove various properties (e.g., absence of divisions by zero and data races), and it is sound for multithreaded programs. It supports all the most relevant features of Java multithreading, such as dynamic thread creation, runtime creation of monitors, and dynamic allocation of memory. The experimental results demonstrate that heckmate is accurate and efficient enough to analyze programs with some thousands of statements and a potentially infinite number of threads. Copyright © 2012 John Wiley & Sons, Ltd.     

Flexible resource monitoring of Java programs

Monitoring resource consumptions is fundamental in software engineering, e.g., in validation of quality requirements, performance engineering, or adaptive software systems. However, resource monitoring does not come for free as it typically leads to overhead in the observed program. Minimizing this overhead and increasing the reliability of the monitored data is a major goal in realizing resource monitoring tools. Typically, this is achieved by limiting capabilities, e.g., supported resources, granularity of the monitoring focus, or runtime access to results. Thus, in practice often several approaches must be combined to obtain relevant information.We describe SPASS-meter, a novel resource monitoring approach for Java and Android Apps, which combines these conflicting capabilities with low overhead. SPASS-meter supports a large set of resources, flexible configuration of the monitoring scope even for user-defined semantic units (components), runtime analysis and online access to monitoring results in a platform-independent way. We discuss the concepts of SPASS-meter, its architecture, realization and validation, the latter in terms of case studies and an overhead analysis based on performance experiments with SPASS-meter, OpenCore and Kieker. SPASS-meter provides a detailed view of the runtime resource consumption at reasonable overhead of less than 3% processing power and 0.5% memory consumption in our experiments.     

Safety-critical Java programs from Circus models

Safety-Critical Java (SCJ) is a novel version of Java that addresses issues related to real-time programming and certification of safety-critical applications. In this paper, we propose a technique that reveals the issues involved in the formal verification of an SCJ program, and provides guidelines for tackling them in a refinement-based approach. It is based on Circus, a combination of well established notations: Z, CSP, Timed CSP, and object orientation. We cater for the specification of timing requirements and their decomposition towards the structure of missions and event handlers of SCJ. We also consider the integrated refinement of value-based specifications into class-based designs using SCJ scoped memory areas. We present a refinement strategy, a Circus variant that captures the essence of the SCJ paradigm, and a substantial example based approach on a concurrent version of a case study that has been used as a benchmark by the SCJ community: an aircraft collision detector.     

Verifying temporal specifications of Java programs

Software Quality Journal - Many Java programs encode temporal behaviors in their source code, typically mixing three features provided by the Java language: (1) pausing the execution for a limited...     

Weakest pre-condition reasoning for Java programs with JML annotations

This paper distinguishes several different approaches to organising a weakest pre-condition (WP) calculus in a theorem prover. The implementation of two of these approaches for Java within the LOOP project is described. This involves the WP-infrastructures in the higher order logic of the theorem prover PVS, together with associated rules and strategies for automatically proving JML specifications for Java implementations. The soundness of all WP-rules has been proven on the basis of the underlying Java semantics. These WP-calculi are integrated with the existing Hoare logic, and together form a verification toolkit in PVS: typically one uses Hoare logic rules to break a large verification task up into smaller parts that can be handled automatically by one of the WP-strategies.     

Specification and verification challenges for sequential object-oriented programs

The state of knowledge in how to specify sequential programs in object-oriented languages such as Java and C# and the state of the art in automated verification tools for such programs have made measurable progress in the last several years. This paper describes several remaining challenges and approaches to their solution.     

Retargeting sequential image-processing programs for data parallel execution

New compact, low-power implementation technologies for processors and imaging arrays can enable a new generation of portable video products. However, software compatibility with large bodies of existing applications written in C prevents more efficient, higher performance data parallel architectures from being used in these embedded products. If this software could be automatically retargeted explicitly for data parallel execution, product designers could incorporate these architectures into embedded products. The key challenge is exposing the parallelism that is inherent in these applications but that is obscured by artifacts imposed by sequential programming languages. This paper presents a recognition-based approach for automatically extracting a data parallel program model from sequential image processing code and retargeting it to data parallel execution mechanisms. The explicitly parallel model presented, called multidimensional data flow (MDDF), captures a model of how operations on data regions (e.g., rows, columns, and tiled blocks) are composed and interact. To extract an MDDF model, a partial recognition technique is used that focuses on identifying array access patterns in loops, transforming only those program elements that hinder parallelization, while leaving the core algorithmic computations intact. The paper presents results of retargeting a set of production programs to a representative data parallel processor array to demonstrate the capacity to extract parallelism using this technique. The retargeted applications yield a potential execution throughput limited only by the number of processing elements, exceeding thousands of instructions per cycle in massively parallel implementations.     

Analysis of sequential PROLOG programs

We consider the characteristics of sequential PROLOG programs using static and dynamic analyzers. They were developed to analyze ICOT-developed PROLOG programs and to collect various data items for studying program characteristics. Thirty-nine programs were statistically analyzed; two of these were also analyzed dynamically. The static analyzer is written in DEC-10 PROLOG. It simply reads a program from the beginning and outputs various types of information about the program. The dynamic analyzer is also written in DEC-10 PROLOG. It executes a program that can be executed in parallel by providing a goal for the program. During the execution, it collects various data including those obtained in the static analysis.