Transparent Speculative Parallelization of Discrete Event Simulation Applications Using Global Variables

Parallelizing (compute-intensive) discrete event simulation (DES) applications is a classical approach for speeding up their execution and for making very large/complex simulation models tractable. This has been historically achieved via parallel DES (PDES) techniques, which are based on partitioning the simulation model into distinct simulation objects (somehow resembling objects in classical object-oriented programming), whose states are disjoint, which are executed concurrently and rely on explicit event-exchange (or event-scheduling) primitives as the means to support mutual dependencies and notification of their state updates. With this approach, the application developer is necessarily forced to reason about state separation across the objects, thus being not allowed to rely on shared information, such as global variables, within the application code. This implicitly leads to the shift of the user-exposed programming model to one where sequential-style global variable accesses within the application code are not allowed. In this article we remove this limitation by providing support for managing global variables in the context of DES code developed in ANSI-C, which gets automatically parallelized. Particularly, we focus on speculative (also termed optimistic) PDES systems that run on top of multi-core machines, where simulation objects can concurrently process their events with no guarantee of causal consistency and actual violations of causality rules are recovered through rollback/recovery schemes. In compliance with the nature of speculative processing, in our proposal global variables are transparently mapped to multi-versions, so as to avoid any form of safety predicate verification upon their updates. Consistency is ensured via the introduction of a new rollback/recovery scheme based on detecting global variables’ reads on non-correct versions. At the same time, efficiency in the execution is guaranteed by managing multi-version variables’ lists via non-blocking algorithms. Furthermore, the whole approach is fully transparent, being it based on automatized instrumentation of the application software (particularly ELF objects). Hence the programmer is exposed to the classical (and easy to code) sequential-style programming scheme while accessing any global variable. An experimental assessment of our proposal, based on a suite of case study applications, run on top of an off-the-shelf Linux machine equipped with 32 CPU-cores and 64 GB of RAM, is also presented.     

Automated Analysis of Discrete Communication Behavior

An objective methodology for the specification and analysis of communicating processes is presented. It is based on an algebraic theory that is a formalization of a particular state machine model. The approach recognizes the fact that the complexity of system interactions is such that computer aid is not only appropriate but necessary for any practical design methodology.     

Discrete Adaptive Sliding Mode Control of a State-Space System with a Bounded Disturbance

This paper presents the discrete adaptive sliding mode control of a state-space system in the presence of a bounded disturbance. The delta form of the discrete state-space model is used as it closely resembles that of the continuous model. The control law takes into account of the effect of the disturbance by using its approximate value. The system behavior in the vicinity of the sliding surface is studied. It is shown that the adaptive controller leads to a stable closed-loop system. Also, simulation results are presented to illustrate the features of the proposed adaptive control strategy.     

Dynamic Generation of Discrete Random Variates

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in O(log ^* N) expected time and updates a weight in O(2^{log^* N}) expected time in the worst case. We then show how to reduce the update time to O(log ^* N) amortized expected time. We finally show how to apply our techniques to a lookup-table technique in order to obtain expected constant time in the worst case for generation and update. We give parallel algorithms for parallel generation and update having optimal processor—time product. Besides the usual application in computer simulation, our method can be used to perform constant-time prediction in prefetching applications. We also apply our techniques to obtain an efficient dynamic algorithm for maintaining an approximate heap of N elements, in which each query is required to return an element whose value is within an ɛ multiplicative factor of the maximal element value. For ɛ= 1/polylog (N), each query, insertion, or deletion takes O(log log log N) time.     

Directed Explicit State-Space Search in the Generation of Counterexamples for Stochastic Model Checking

Current stochastic model checkers do not make counterexamples for property violations readily available. In this paper, we apply directed explicit state-space search to discrete and continuous-time Markov chains in order to compute counterexamples for the violation of PCTL or CSL properties. Directed explicit state-space search algorithms explore the state space on-the-fly, which makes our method very efficient and highly scalable. They can also be guided using heuristics which usually improve the performance of the method. Counterexamples provided by our method have two important properties. First, they include those traces which contribute the greatest amount of probability to the property violation. Hence, they show the most probable offending execution scenarios of the system. Second, the obtained counterexamples tend to be small. Hence, they can be effectively analyzed by a human user. Both properties make the counterexamples obtained by our method very useful for debugging purposes. We implemented our method based on the stochastic model checker PRISM and applied it to a number of case studies in order to illustrate its applicability.     

Automated Test Generation and Static Analysis

The study and development of techniques for automated generation of useful tests, the development of a system that implements those techniques, and the development of methods for the analysis of programs designed for solving this problem are based on the earlier works of the author of the present paper, the works by B. Korel, and on the desire to understand if the approaches suggested can be used to develop real-world software. The first problem is as follows: determine, which information on the program must be collected to automatically generate a set of tests, and develop a component for collecting this information. The emphasis was made on collecting this information statically using a powerful flow analyzer developed in a laboratory of the Institute of Information Systems. Another problem consists in developing a prototype system for trying both well-known and new test generation methods suggested by the author. As a result, path-oriented and objective-oriented methods of test generation and the chaining approach (which turned out to be the most interesting one) are considered. This approach uses the concept of influence of an input variable on an operator along a certain program execution path and is based on dynamic analysis. The concept of influence can be extended for the case of all paths; then, such influences can be detected statically. In this paper, the influence along any path is rigorously defined and its constructive flow reformulation is given. On the basis of this reformulation, a language processor is developed that performs a static analysis of dependencies and calculates, for every statement of the program, the set of input variables that influence it.     

Automated Displacement for Large Numbers of Discrete Map Objects

Effective displacement is achieved by sharing small movements among a group of objects in order to minimize loss of positional accuracy and maintain the gestalt and topology of the map objects. This research was driven by a desire to implement a simple but effective way of handling large numbers of map objects that may require displacement. The algorithm works by considering, for each object in turn, a number of alternate positions close to its current location. The location which minimizes overlap among the neighbouring objects is chosen. As the program iterates, the objects effectively migrate small distances within the map space in search of solutions. The idea is relatively simple but produces visually acceptable solutions to the displacement of large numbers of objects with very low processing overhead. This paper describes the algorithm in detail, illustrates its application, refinement and evaluation. Received December 11, 1998; revised October 14, 1999.     

Coverage-driven Automated Compiler Test Suite Generation

The paper presents a novel approach to automated compiler test suite generation based on the source level specification. Several coverage criteria are introduced. The application of the proposed methodology to testing the realistic programming language is discussed.     

Automated Generation of Cross-System Software for Microcomputers

GEN is a set of Fortran program writer modules designed to generate microcomputer assemblers and simulators. It is simple enough to be used by those with limited architecture and programming backgrounds yet flexible and powerful enough to generate efficient and well-structured assemblers and simulators for microcomputes sophisticated tectures and instruction sets. This paper describes the generating system, the generated gPoassemblers and simulators, and the advantages they offer in both programming and pedagogical applications.     

A Pattern Recognition Approach for Speculative Firing Prediction in Distributed Saturation State-Space Generation

The saturation strategy for symbolic state-space generation is particularly effective for globally-asynchronous locally-synchronous systems. A distributed version of saturation, SaturationNOW, uses the overall memory available on a network of workstations to effectively spread the memory load, but its execution is essentially sequential. To achieve true parallelism, we explore a speculative firing prediction, where idle workstations work on predicted future event firing requests. A naïve approach where all possible firings may be explored a priori, given enough idle time, can result in excessive memory requirements. Thus, we introduce a history-based approach for firing prediction that recognizes firing patterns and explores only firings conforming to these patterns. Experiments show that our heuristic improves the runtime and has a small memory overhead.     

Automated Test Case Generation for BDI Agents

We propose a coverage oriented test case generation methodology for BDI multi-agent systems. The coverage criteria involve plans and nodes within plans of multi-agent systems. We organise the criteria into a subsumption hierarchy to show the coverage relationships between the criteria. Then we apply the criteria on multi-agent systems to analyse some empirical data. The data analysed is the effect on the number of test cases generated automatically for each criterion. We use a tool, BDITESTER, to obtain the empirical data and to show that our proposal is pragmatic. Finally, we suggest some guidelines to select a criterion to automatically generate test cases for BDI agents.     

Goal-Based Automated Code Generation in Self-Adaptive System

System administrator deals with many problems, as computing environment becomes increasingly complex. Systems with an ability to recognize system states and adapt to resolve these problems offer a solution. Much experience and knowledge are required to build a self-adaptive system. Self-adaptive systems have inherent difficulties. This paper proposes a technique that automatically generates the code for the self-adaptive system. Thus the system is easier to build. Self-adaptive systems of previous research required high system resource usage. Incorrect operation could be invoked by external factors such as viruses. We propose an improved self-adaptive system approach and apply it to video conference system and robot system. We compared the lines of code, the number of classes created by the developers. We have confirmed this enhanced approach to be effective in reducing these development metrics.     

Design and Automated Generation of Japanese Picture Puzzles

We introduce the generalized nonogram, an extension of the well‐known nonogram or Japanese picture puzzle. It is not based on a regular square grid but on a subdivision (arrangement) with differently shaped cells, bounded by straight lines or curves. To generate a good, clear puzzle from a filled line drawing, the arrangement that is formed for the puzzle must meet a number of criteria. Some of these relate to the puzzle and some to the geometry. We give an overview of these criteria and show that a puzzle can be generated by an optimization method like simulated annealing. Experimentally, we analyze the convergence of the method and the remaining penalty score on several input pictures along with various other design options.     

Survey of Methods for Automated Code-Reuse Exploit Generation

Programming and Computer Software - This paper provides a survey of methods and tools for automated code-reuse exploit generation. Such exploits use code that is already contained in a vulnerable...     

Method of Automated Generation of Autotuners for Parallel Programs

This paper introduces a formal model of a method for automated adjustment of parallel applications (autotuning). The software implementation of this model is described in the form of a flexible software framework for automatic generation of autotuners using an underlain term rewriting system and expert knowledge as a source of optimizing transformations.