Narrow Results

To solve the problem of dynamic degradation over the finite precision platform of the chaotic map, a nondegenerate 2D integer domain chaotic map (2D-IDCM) over GF(2${}^n)$ is constructed. Theoretical analysis confirmed the chaotic characteristics of the 2D-IDCM. Then, the dynamic behavior analysis results showed that the 2D-IDCM has ergodicity within a sufficient parameter range. Additionally, to verify the validity of 2D-IDCM, an improved pseudo-random number generator (PRNG) is designed, by injecting the sequences generated by 2D-IDCM into the key stream generation phase of ZUC, ensuring that the proposed PRNG satisfied the criteria of irreversibility and parallelism. The simulation results indicated that the pseudo-random words generated by the PRNG are independent of each other, showing robustness and capability to withstand differential attack.

This paper discusses an experiment with a dataflow execution model for logic programs implemented on the transputer. The execution model is supported by a dataflow virtual machine, on which the execution mechanism for AND/OR-parallelism is developed. The real-time evaluation shows that small scale parallelism can be exploited from the dataflow graphs compiled from the logic programs. A conventional dataflow architecture supporting the implemented model has been emulated on a multitransputer system.

We describe APE-100, a SIMD, modular parallel processor architecture for large scale scientific computation. The largest configuration that will be implemented in the present design will deliver a peak speed of 100 Gflops. This performance is, for instance, required for high precision computations in Quantum Chromo Dynamics, for which APE-100 is very well suited.

In this paper three parallel recognition algorithms for threshold, matrogenic and box-threshold graphs, respectively, are given. These classes of graphs are inclusionwise comparable and depend only on their degree sequences. The algorithms run in O(log n) parallel time on a PRAM-EREW model of computation and require O(n/log n) processors when the degree sequence, ordered in decreasing fashion, is given as input.

In biological systems, instead of actual encoders at different joints, proprioception signals are acquired through distributed receptive fields. In robotics, a single and accurate sensor output per link (encoder) is commonly used to track the position and the velocity. Interfacing bio-inspired control systems with spiking neural networks emulating the cerebellum with conventional robots is not a straight forward task. Therefore, it is necessary to adapt this one-dimensional measure (encoder output) into a multidimensional space (inputs for a spiking neural network) to connect, for instance, the spiking cerebellar architecture; i.e. a translation from an analog space into a distributed population coding in terms of spikes. This paper analyzes how evolved receptive fields (optimized towards information transmission) can efficiently generate a sensorimotor representation that facilitates its discrimination from other "sensorimotor states". This can be seen as an abstraction of the Cuneate Nucleus (CN) functionality in a robot-arm scenario. We model the CN as a spiking neuron population coding in time according to the response of mechanoreceptors during a multi-joint movement in a robot joint space. An encoding scheme that takes into account the relative spiking time of the signals propagating from peripheral nerve fibers to second-order somatosensory neurons is proposed. Due to the enormous number of possible encodings, we have applied an evolutionary algorithm to evolve the sensory receptive field representation from random to optimized encoding. Following the nature-inspired analogy, evolved configurations have shown to outperform simple hand-tuned configurations and other homogenized configurations based on the solution provided by the optimization engine (evolutionary algorithm). We have used artificial evolutionary engines as the optimization tool to circumvent nonlinearity responses in receptive fields.

The aim of this paper is to introduce the notion of normal Jacobi operator of real hypersurfaces in complex hyperbolic two-plane Grassmannians. Furthermore, results concerning real hypersurfaces in complex hyperbolic two-plane Grassmannians whose normal Jacobi operator satisfies conditions of parallelism will be given.

We implement in a reactive programming framework a system mimicking three aspects of quantum mechanics: self-interference, state superposition, and entanglement. The system basically consists in a cellular automaton embedded in a synchronous environment which defines global discrete instants and broadcast events. The implementation shows how a simulation of fundamental aspects of quantum mechanics can be obtained from the synchronous parallel combination of a small number of elementary components.

We consider the Reactive Programming (RP) approach to simulate physical systems. The choice of RP is motivated by the fact that RP genuinely offers logical parallelism, instantaneously broadcast events, and dynamic creation/destruction of parallel components and events. To illustrate our approach, we consider the implementation of a system of Molecular Dynamics, in the context of Java with the Java3D library for 3D visualization.

Genetic algorithms are search or classification algorithms based on natural models. They present a high degree of internal parallelism. We developed two versions, differing in the way the population is organized and we studied and compared their characteristics and performances when applied to the optimization of multidimensional function problems. All the implementations are realized on transputer networks.

This paper focuses on the improvement in the quality of computation provided by parallelism. The problem of interest is that of computing the maximum of a nonlinear feedback function in a real-time environment. We show that the solution obtained in parallel is significantly, provably, and consistently better than a sequential one. It is important to note that our purpose is not to demonstrate merely that a parallel computer can obtain a solution to a computational problem that is of higher quality than one derived sequentially. The latter is an interesting (and often surprising) observation in its own right, but we wish to go further. It is shown here that the improvement in quality due to parallelism can be arbitrarily high. To be specific, the ratio of the parallel solution to the sequential one is typically superlinear in the number of processors used by the parallel computer. This result is akin to superlinear speedup—a phenomenon itself originally thought to be impossible.

This paper demonstrates how parallel programs with message-passing can be generated from abstract specifications embedded in the functional language MetaOCaml. The functional style permits to design parallel programs with a high degree of parameterization, so-called skeletons. Programmers who are unexperienced in parallelism can take such skeletons for a simple and safe generation of parallel applications. Since MetaOCaml also has efficient imperative features and an MPI interface, the entire program can be written in one language, without the need to use a language interface restricting the set of data objects which could be exchanged.

The semantics of abstract specifications is expressed by an interpreter written in MetaOCaml. A cost model is defined by abstract interpretation of the specification. Partial evaluation of the interpreter with a specification, a feature which MetaOCaml provides, yields a parallel program. The partial evaluation process takes time on each MPI process directly before the execution of the application program, exploiting knowledge of the number of processes, the current process identifier and the communication structure. Our example is the specification of a divide-and-conquer skeleton which is used to compute the multiplication of multi-digit numbers using Karatsuba's algorithm.

This paper is structured around the idea that a finite Universal Computer cannot be realized and presents in detail a series of unconventional computing paradigms supporting this idea from a quantum mechanical perspective.

Determining the optimal location of a switching center in a tree network of users is accurately modeled by the median problem. A real-time approach is used in this paper to investigate the dynamics of such a communication network in two cases: (1) a growing tree of nodes associated with equal demand rates, and (2) a stream of corrections that arbitrarily change the demand rates at the nodes. The worst-case analysis performed in both situations clearly demonstrates the importance of parallelism in such real-time paradigms. It is shown that the error generated by the best sequential algorithm in the first case can be arbitrarily large. A synergistic behavior is revealed when the quality-up is investigated in the second case.

Iterative stencil computations are important in scientific computing and more also in the embedded and mobile domain. Recent publications have shown that tiling schemes that ensure concurrent start provide efficient ways to execute these kernels. Diamond tiling and hybrid-hexagonal tiling are two tiling schemes that enable concurrent start. Both have different advantages: diamond tiling has been integrated in a general purpose optimization framework and uses a cost function to choose among tiling hyperplanes, whereas the greater flexibility with tile sizes for hybrid-hexagonal tiling has been exploited for effective generation of GPU code.

In this paper we undertake a comparative study of these two tiling approaches and propose a hybrid approach that combines them. We analyze the effects of tile size and wavefront choices on tile-level parallelism, and formulate constraints for optimal diamond tile shapes. We then extend, for the case of two dimensions, the diamond tiling formulation into a hexagonal tiling one, which offers both the flexibility of hexagonal tiling and the generality of the original diamond tiling implementation. We also show how to compute tile sizes that maximize the compute-to-communication ratio, and apply this result to compare the best achievable ratio and the associated synchronization overhead for diamond and hexagonal tiling.

This paper investigates the effects of parallelism on blackboard system scheduling heuristics. A parallel blackboard system is described that allows multiple knowledge source instantiations (KSIs) to execute in parallel using a shared-memory blackboard approach. New classes of control knowledge are defined that order the agenda by using information about the relationships between the goals of the KSIs. This control knowledge is implemented and tested in the DVMT application on a Sequent multiprocessor using BB1-style control heuristics. The usefulness of the heuristics is examined by comparing the effectiveness of problem-solving with and without the heuristics (as a group and individually). Problem solving with the new control knowledge results in improved system performance.

Thinning algorithms are widely used in pattern recognition. This processing stage is implemented on serial machines as well as on parallel machines. We can find two classes of thinning algorithms in the literature. The first class is composed of strongly sequential algorithms, based on contour tracing of the objects to be thinned. The second class is made of iterative processes in which fully parallel mask-based operators are used at each iteration.

The weakness of the contour tracing based methods is its strong dependence upon the original picture. Particularly, in the case of very complex pictures, this algorithm becomes inefficient.

The second thinning class of algorithms uses strongly regular operating processes. The general speed of those methods also depends upon the shapes to be thinned. The iteration number necessary to complete these iterative processes is proportional to the maximum thickness of the objects in the picture. The complexity of the contour of the objects does not influence the efficiency of the algorithm.

The goal of this paper is to keep the regularity of the second class of thinning processes, but to reduce the amount of standard parallel-operations. We use a partition of the original picture and we dynamically reduce the range of the full-parallel operator in its sub-picture.

This paper discusses several data allocation strategies used for the parallel implementation of basic imaging operators. It shows that depending on the operator (sequential or parallel, with regular or irregular execution time), the image data must be partitioned in very different manners: The square sub-domains are best adapted for minimizing the communication volume, but rectangles can perform better when we take into account the time for constructing messages. Block allocations are well adapted for inherently parallel operators since they minimize interprocessor interactions, but in the case of recursive operators, they lead to nearly sequential executions. In this framework, we show the usefulness of block-cyclic allocations. Finally, we illustrate the fact that allocating the same amount of image data to each processor can lead to severe load imbalance in the case of some operators with data-dependant execution times.

We propose in this paper, a parallel implementation of a ground visualization algorithm. Our input data consist in a Digital Elevation Model (DEM) covering a rectangular region, together with a raster image of the same area (the texture). The goal of the algorithm is to compute in parallel, images of the DEM from any point of view while mapping the texture onto the surface. The main originality of our approach concerns the distribution of the data, leading to a load-balanced and scalable parallel algorithm. We use a workload estimation to partition the output image, and then redistribute the input data according to this division. Special attention is paid on the data structures used for minimizing the cost of communications.

Automated theorem provers use search strategies. Unfortunately, there is no unique strategy which is uniformly successful on all problems. This motivates us to apply different strategies in parallel, in a competitive manner. In this paper, we discuss properties, problems, and perspectives of strategy parallelism in theorem proving. We develop basic concepts like the complementarity and the overlap value of strategy sets. Some of the problems such as initial strategy selection and run-time strategy exchange are discussed in more detail. The paper also contains the description of an implementation of a strategy parallel theorem prover (p-SETHEO) and an experimental evaluation.

This paper introduces and compares three parallel algorithms to compute general geometric image transformations on MIMD machines. We propose three variants of a parallel general scheme. We focus on the load balancing and the data redistributions. Experimental results are reported and compared. The implementation has been done using PPCM library allowing us to run the program over different parallel machines.

We compare logical communication schemes for message-passing machines. Since our parallel algorithm needs global communications such as multiscatters, we study the efficiency of two different logical topologies usable with PPCM.

These studies allow us to find the best combination of algorithm and virtual topology to use on a given parallel machine.