Flash memory efficient LTL model checking

As the capacity and speed of flash memories in form of solid state disks grow, they are becoming a practical alternative for standard magnetic drives. Currently, most solid-state disks are based on NAND technology and much faster than magnetic disks in random reads, while in random writes they are generally not.So far, large-scale LTL model checking algorithms have been designed to employ external memory optimized for magnetic disks. We propose algorithms optimized for flash memory access. In contrast to approaches relying on the delayed detection of duplicate states, in this work, we design and exploit appropriate hash functions to re-invent immediate duplicate detection.For flash memory efficient on-the-fly LTL model checking, which aims at finding any counter-example to the specified LTL property, we study hash functions adapted to the two-level hierarchy of RAM and flash memory. For flash memory efficient off-line LTL model checking, which aims at generating a minimal counterexample and scans the entire state space at least once, we analyze the effect of outsourcing a memory-based perfect hash function from RAM to flash memory.Since the characteristics of flash memories are different to magnetic hard disks, the existing I/O complexity model is no longer sufficient. Therefore, we provide an extended model for the computation of the I/O complexity adapted to flash memories that has a better fit to the observed behavior of our algorithms.     

The use of genetic algorithms for assessment of high voltage fields

There are several numerical methods for calculation of electric fields but they need some sort of experience and trial and error to get the correct solution. A genetic algorithm (GA) based approach is used to eliminate the need for the experience and to save time and effort spent in the trial and error. Two enhancement techniques, namely, Refreshment Method and No-Twins Method, are used with the GA operators to improve the performance of the GA in assessment of high voltage fields. The performance of these two enhancement techniques has been studied for computing the electrostatic field in high voltage applications.     

Genetic adaptive state estimation

A genetic algorithm (GA) uses the principles of evolution, natural selection, and genetics to offer a method for parallel search of complex spaces. This paper describes a GA that can perform on-line adaptive state estimation for linear and nonlinear systems. First, it shows how to construct a genetic adaptive state estimator where a GA evolves the model in a state estimator in real time so that the state estimation error is driven to zero. Next, several examples are used to illustrate the operation and performance of the genetic adaptive state estimator. Its performance is compared to that of the conventional adaptive Luenberger observer for two linear system examples. Next, a genetic adaptive state estimator is used to predict when surge and stall occur in a nonlinear jet engine. Our main conclusion is that the genetic adaptive state estimator has the potential to offer higher performance estimators for nonlinear systems over current methods.     

Towards the next generation of artificial neural networks for civil engineering

The purpose of this paper is to stimulate interest within the civil engineering research community for developing the next generation of applied artificial neural networks. In particular, it identifies what the next generation of these devices needs to achieve, and provides direction in terms of how their development may proceed. An analysis of the current situation indicates that progress in the development of artificial neural network applications has largely stagnated. Suggestions are made for advancing the field to the next level of sophistication and application, using genetic algorithms and related techniques. It is shown that this approach will require the design of some very sophisticated genetic coding mechanisms in order to develop the required higher-order network structures, and will utilize development mechanisms observed in nature such as growth, self-organization, and multi-stage objective functions. The capabilities of such an approach and the way in which they can be achieved are explored with reference to the problems of: (a) determining truck attributes from the strain envelopes they induce in structural members when crossing a bridge, and; (b) developing a decision support system for dynamic control of industrialized manufacturing of houses.     

A Review of the Application of Meta-Heuristic Algorithms to 2D Strip Packing Problems

This paper is a review of the approachesdeveloped to solve 2D packing problems withmeta-heuristic algorithms. As packing tasks arecombinatorial problems with very large searchspaces, the recent literature encourages theuse of meta-heuristic search methods, inparticular genetic algorithms. The objective ofthis paper is to present and categorise thesolution approaches in the literature for 2Dregular and irregular strip packing problems.The focus is hereby on the analysis of themethods involving genetic algorithms. Anoverview of the methods applying othermeta-heuristic algorithms including simulatedannealing, tabu search, and artificial neuralnetworks is also given.     

An Efficient Output-Size Sensitive Parallel Algorithm for Hidden-Surface Removal for Terrains

We describe an efficient parallel algorithm for hidden-surface removal for terrain maps. The algorithm runs in O(log ⁴ n) steps on the CREW PRAM model with a work bound of O((n+k) \polylog ( n)) where n and k are the input and output sizes, respectively. In order to achieve the work bound we use a number of techniques, among which our use of persistent data structures is somewhat novel in the context of parallel algorithms. Received July 29, 1998; revised October 5, 1999.     

Implementation of particle-in-cell stellar dynamics codes on the connection machine-2

The development of massively parallel supercomputers provides a unique opportunity to advance the state of the art inN-body simulations. TheseN-body codes are of great importance for simulations in stellar dynamics and plasma physics. For systems with long-range forces, such as gravity or electromagnetic forces, it is important to increase the number of particles toN 10⁷ particles. Significantly improved modeling ofN body systems can be expected by increasingN, arising from a more realistic representation of physical transport processes involving particle diffusion and energy and momentum transport. In addition, it will be possible to guarantee that physically significant portions of complex physical systems, such as Lindblad resonances of galaxies or current sheets in magnetospheres, will have an adequate population of particles for a realistic simulation. Particle-mesh (PM) and particle-particle particle-mesh (P³M) algorithms present the best prospects for the simulation of large-scaleN-body systems. As an example we present a two-dimensional PM simulation of a disk galaxy that we have developed on the Connection Machine-2, a massively parallel boolean hypercube supercomputer. The code is scalable to any CM-2 configuration available and, on the largest configuration, simulations withN = 128 M = 2²⁷ particles are possible in reasonable run times.     

A bandwidth latency tradeoff for broadcast and reduction

The “fractional tree” algorithm for broadcasting and reduction is introduced. Its communication pattern interpolates between two well known patterns—sequential pipeline and pipelined binary tree. The speedup over the best of these simple methods can approach two for large systems and messages of intermediate size. For networks which are not very densely connected the new algorithm seems to be the best known method for the important case that each processor has only a single (possibly bidirectional) channel into the communication network.     

Simulation based on learning methods

The use of simulation technology as a tool for planning and control is of increasing significance in most fields of production. The main part of the expenditure concerning simulation analyses is the modelling of the considered production. Despite the use of modern building-block-oriented modelling technology, this modelling can often not be done by the user, but only by external experts. Against this backdrop, an adaptive simulation system is being developed by the Institute for Industrial Manufacturing and Management (IFF) at the University of Stuttgart. It independently adapts to real production processes, i.e. it learns about the interdependencies of production processes, and, in this way, supports the user in constructing and maintaining the model. In terms of information technology, the research in the field of artificial intelligence, especially in the subdomain of machine learning, is the basis for the realization of such adaptive systems.