On hardware synthesis and implementation of PLC programs in FPGAs

Many processes require controllers with an instant response (e.g. motor control, CNC machines). A high-performance PLC can be constructed with use of programmable logic devices. A lack of custom synthesis tools disables the use of standard languages widely accepted by automation designers. The paper presents the systematic process of a PLC program synthesis to hardware structure. An input PLC program is given according to the IEC61131-3 standard. The synthesis process has been developed for implementation of a program described with the LD and SFC languages. The essential idea of synthesis process is obtaining a massively parallel operating hardware structure that significantly reduces response processing time. The PLC program is translated into originally developed dedicated graph structure that enables a wide range of optimizations. In the next step, it is mapped into a hardware structure. In order to reduce resource requirements, a strategy with resource sharing is shown, which is an original extension of general mapping concepts. Modern FPGAs are equipped with arithmetic cores dedicated for signal processing, inspiring the development of the original DSP48 block mapping strategy. It attempts to utilize all features of the block in the pipelined calculation model. The considerations are summarized with the implementation result compared against standard PLC implementation, a mutual comparison of general hardware mapping, and with the use of DSP48 units.     

Space efficient execution of deterministic parallel programs

We model a deterministic parallel program by a directed acyclic graph of tasks, where a task can execute as soon as all tasks preceding it have been executed. Each task can allocate or release an arbitrary amount of memory (i.e., heap memory allocation can be modeled). We call a parallel schedule “space efficient” if the amount of memory required is at most equal to the number of processors times the amount of memory required for some depth-first execution of the program by a single processor. We describe a simple, locally depth-first scheduling algorithm and show that it is always space efficient. Since the scheduling algorithm is greedy, it will be within a factor of two of being optimal with respect to time. For the special case of a program having a series-parallel structure, we show how to efficiently compute the worst case memory requirements over all possible depth-first executions of a program. Finally, we show how scheduling can be decentralized, making the approach scalable to a large number of processors when there is sufficient parallelism     

Online efficient predictive safety analysis of multithreaded programs

We present an automated and configurable technique for runtime safety analysis of multithreaded programs that is able to predict safety violations from successful executions. Based on a formal specification of safety properties provided by a user, our technique enables us to automatically instrument a given program and create an observer so that the program emits relevant state update events to the observer and the observer checks these updates against the safety specification. The events are stamped with dynamic vector clocks, enabling the observer to infer a causal partial order on the state updates. All event traces that are consistent with this partial order, including the actual execution trace, are then analyzed online and in parallel. A warning is issued whenever one of these potential traces violates the specification. Our technique is scalable and can provide better coverage than conventional testing, but its coverage need not be exhaustive. In fact, one can trade off scalability and comprehensiveness: a window in the state space may be specified allowing the observer to infer some of the more likely runs; if the size of the window is 1, then only the actual execution trace is analyzed, as is the case in conventional testing; if the size of the window is ∞, then all the execution traces consistent with the actual execution trace are analyzed.     

Unified Approach for Developing EfficientAlgorithmic Programs

A unified approach called partition-and-recur for developing efficient and correct algorithmic programs is presented.An algorithm(represented by recurrence and initiation)is separated from program,and special attention is paid to algorithm manipulation rather than proram calculus.An algorithm is exactly a set of mathematical formulae.It is easier for formal erivation and proof.After getting efficient and correct algorithm,a trivial transformation is used to get a final rogram,The approach covers several known algorithm design techniques,e.g.dynamic programming,greedy,divide-and-conquer and enumeration,etc.The techniques of partition and recurrence are not new.Partition is a general approach for dealing with complicated objects and is typically used in divide-and-conquer approach.Recurrence is used in algorithm analysis,in developing loop invariants and dynamic programming approach.The main contribution is combining two techniques used in typical algorithm development into a unified and systematic approach to develop general efficient algorithmic programs and presenting a new representation of algorithm that is easier for understanding and demonstrating the correctness and ingenuity of algorithmicprograms.     

Derivation of efficient programs for computing sequences of actions

We consider a class of programs whose output is a sequence of elementary actions or moves. For that class we provide some transformation strategies for deriving efficient iterative programs with on-line behaviour, that is, programs which produce the output moves, one at the time, according to a given sequence ordering.Using the proposed methods it is possible to answer Hayes' long-standing challenge for deriving a very fast on-line program for the Towers of Hanoi and similarly defined problems.     

Symbolic synthesis of masking fault-tolerant distributed programs

We focus on automated addition of masking fault-tolerance to existing fault-intolerant distributed programs. Intuitively, a program is masking fault-tolerant, if it satisfies its safety and liveness specifications in the absence and presence of faults. Masking fault-tolerance is highly desirable in distributed programs, as the structure of such programs are fairly complex and they are often subject to various types of faults. However, the problem of synthesizing masking fault-tolerant distributed programs from their fault-intolerant version is NP-complete in the size of the program’s state space, setting the practicality of the synthesis problem in doubt. In this paper, we show that in spite of the high worst-case complexity, synthesizing moderate-sized masking distributed programs is feasible in practice. In particular, we present and implement a BDD-based synthesis heuristic for adding masking fault-tolerance to existing fault-intolerant distributed programs automatically. Our experiments validate the efficiency and effectiveness of our algorithm in the sense that synthesis is possible in reasonable amount of time and memory. We also identify several bottlenecks in synthesis of distributed programs depending upon the structure of the program at hand. We conclude that unlike verification, in program synthesis, the most challenging barrier is not the state explosion problem by itself, but the time complexity of the decision procedures.     

More efficient automatic repair of large-scale programs using weak recompilation

Automatically repairing a bug can be a time-consuming process especially for large-scale programs owing to the significant amount of time spent recompiling and reinstalling the patched program.To reduce this time overhead and speed up the repair process,in this paper we present a recompilation technique called weak recompilation.In weak recompilation,we assume that a program consists of a set of components,and for each candidate patch only the altered components are recompiled to a shared library.The original program is then dynamically updated by a function indirection mechanism.The advantage of weak recompilation is that redundant recompilation cost can be avoided,and while the reinstallation cost is completely eliminated as the original executable program is not modified at all.For maximum applicability of weak recompilation we created WAutoRepair,a scalable system for fixing bugs with high efficiency in large-scale C programs.The experiments on real bugs in widely used programs show that our repair system significantly outperforms Genprog,a wellknown approach to automatic program repair.For the wireshark program containing over 2 million lines of code,WAutoRepair is over 128 times faster in terms of recompilation cost than Genprog.     

On the total correctness of nondeterministic programs

For an arbitrary programming language with nondeterminism to be implementable, the existence of computation trees modelling the possible changes in state in the course of a computation is postulated. A general definition of what constitutes an execution method is then presented. Falling naturally out of these ideas is the correspondence between execution methods and total correctness, in that different properties are required of a program to be correct when different methods are adopted. We describe a variety of plausible methods of execution falling under the general definition and single out four particular ones. The arguments made are then illustrated by analysing the properties required by Dijkstra of guarded commands in view of these four methods. We conclude that a general approach such as that suggested here seems to be needed for dealing with programming languages and execution methods other than the particular ones treated by Dijkstra.     

On stratified disjunctive programs

We address the problem of a consistent fixpoint semantics for general disjunctive programs restricted to stratifiable programs which do not recurse through negative literals. We apply the nonmonotonic fixpoint theory developed by Apt, Blair and Walker to a closure operatorT ^c and develop a fixpoint semantics for stratified disjunctive programs. We also provide an iterative definition for negation, called the Generalized Closed World Assumption for Stratified programs (GCWAS), and show that our semantics captures this definition. We develop a model-theoretic semantics for stratified disjunctive programs and show that the least state characterized by the fixpoint semantics corresponds to a stable-state defined in a manner similar to the stable-models of Gelfond and Lifschitz. We also discuss a weaker stratification semantics for general disjunctive programs based on the Weak Generalized Closed World Assumption.     

On computing logic programs

In this paper we present and compare some classical problem-solving methods for computing the stable models of logic programs with negation. Using a graph theoretic representation of logic programs and their stable models, we discuss and compare linear programming, propositional satisfiability, constraint satisfaction, and graph methods.     

Automatic synthesis of action programs for intelligent robots

The problem of automatic synthesis of action programs for intelligent robots in a permanently changing environment is considered. Capabilities of the deductive synthesis of cyclic and self-replicating programs are investigated. New algorithms for synthesis of such action programs for a wide range of possible conditions are suggested. Results of this synthesis are reported.