Generic systolic array for genetic algorithms

The authors present a systolic design for a simple GA mechanism which provides high throughput and unidirectional pipelining by exploiting the inherent parallelism in the genetic operators. The design computes in O(N+G) time steps using O(N2) cells where N is the population size and G is the chromosome length. The area of the device is independent of the chromosome length and so can be easily scaled by replicating the arrays or by employing fine-grain migration. The array is generic in the sense that it does not rely on the fitness function and can be used as an accelerator for any GA application using uniform crossover between pairs of chromosomes. The design can also be used in hybrid systems as an add-on to complement existing designs and methods for fitness function acceleration and island-style population management

Parallel genetic algorithms for the tuning of a fuzzy AQM controller

This paper presents the results of the application of a parallel Genetic Algorithm (GA) in order to design a Fuzzy Proportional Integral (FPI) controller for active queue management on Internet routers. The Active Queue Management (AQM) policies are those policies of router queue management that allow the detection of network congestion, the notification of such occurrences to the hosts on the network borders, and the adoption of a suitable control policy. Two different parallel implementations of the genetic algorithm are adopted to determine an optimal configuration of the FPI controller parameters. Finally, the results of several experiments carried out on a forty nodes cluster of workstations are presented.

Implementing a generic systolic array for genetic algorithms

We have designed a highly parallel design for a simple genetic algorithm using a pipeline of systolic arrays. The systolic design provides high throughput and unidirectional pipelining by exploiting the implicit parallelism in the genetic operators. The design is significant because, unlike other hardware genetic algorithms, it is independent of both the fitness function and the particular chromosome length used in a problem. We have designed and simulated a version of the mutation array using Xilinix FPGA tools to investigate the feasibility of hardware implementation. A simple 5-chromosome mutation array occupies 195 CLBs and is capable of performing more than one million mutations per second. I. Introduction Genetic algorithms (GAs) are established search and optimization techniques which have been applied to a range of engineering and applied problems with considerable success [1]. They operate by maintaining a population of trial solutions encoded, using a suitable encoding scheme.

Systolic random number generation for genetic algorithms

A parallel hardware random number generator for use with a VLSI genetic algorithm processing device is proposed. The design uses an systolic array of mixed congruential random number generators. The generators are constantly reseeded with the outputs of the proceeding generators to avoid significant biasing of the randomness of the array which would result in longer times for the algorithm to converge to a solution. 1 Introduction In recent years there has been a growing interest in developing hardware genetic algorithm devices [1, 2, 3]. A genetic algorithm (GA) is a stochastic search and optimization technique which attempts to capture the power of natural selection by evolving a population of candidate solutions by a process of selection and reproduction [4]. In keeping with the evolutionary analogy, the solutions are called chromosomes with each chromosome containing a number of genes. Chromosomes are commonly simple binary strings, the bits being the genes.

Mapping and controlling molecular processes: The application of control theory and system identification algorithms to ASOPS and other fast pulse spectroscopies

Asynchronous Optical Sampling (ASOPS) [1,2] and frequency comb spectrometry [3] based on dual Ti:saphire resonators operated in a master/slave mode have the potential to improve signal to noise ratio in THz transient and IR sperctrometry. The multimode Brownian oscillator time-domain response function described by state-space models is a mathematically robust framework that can be used to describe the dispersive phenomena governed by Lorentzian, Debye and Drude responses. In addition, the optical properties of an arbitrary medium can be expressed as a linear combination of simple multimode Brownian oscillator functions. The suitability of a range of signal processing schemes adopted from the Systems Identification and Control Theory community for further processing the recorded THz transients in the time or frequency domain will be outlined [4,5]. Since a femtosecond duration pulse is capable of persistent excitation of the medium within which it propagates, such approach is perfectly justifiable. Several de-noising routines based on system identification will be shown. Furthermore, specifically developed apodization structures will be discussed. These are necessary because due to dispersion issues, the time-domain background and sample interferograms are non-symmetrical [6-8]. These procedures can lead to a more precise estimation of the complex insertion loss function. The algorithms are applicable to femtosecond spectroscopies across the EM spectrum. Finally, a methodology for femtosecond pulse shaping using genetic algorithms aiming to map and control molecular relaxation processes will be mentioned.

Root pruning as a means to encourage root growth in two ornamental shrubs, Buddleja davidii ‘Summer Beauty’ and Cistus ‘Snow Fire'

The inability of a plant to grow roots rapidly upon transplanting is one of the main factors contributing to poor establishment. In bare-rooted trees, treatments such as root pruning or application of the plant hormone auxin [e.g., indole butyric acid (IBA)] can promote root growth and aid long-term establishment. There is little information on ornamental containerised plants, however, other than the anecdotal notion that 'teasing' the roots out of the rootsoil mass before transplanting can be beneficial. In the present study we tested the ability of various root-pruning treatments and application of IBA to encourage new root and shoot growth in two shrub species, commonly produced in containers - Buddleja davidii 'Summer Beauty' and Cistus 'Snow Fire'. In a number of experiments, young plants were exposed to root manipulation (teasing, light pruning, or two types of heavy pruning) and/or treatment with IBA (at 500 or 1,000 mg l-1) before being transplanted into larger containers containing a medium of 1:1:1 (v/v/v) fine bark, sand and loam. Leaf stomatal conductance (gl) was measured 20 min, and 1, 2, 4 and 6 h after root manipulation. Net leaf CO2 assimilation (A) was measured frequently during the first week after transplanting, then at regular intervals up to 8 weeks after transplanting. Plants were harvested 8 weeks after transplanting, and root and shoot weights were measured. In both species, light root pruning alone, or in combination with 500 mg l-1 IBA, was most effective in stimulating root growth. In contrast, teasing, which is commonly used, showed no positive effect on root growth in Buddleja, and decreased new root growth in Cistus. The requirement for exogenous auxin to encourage new root growth varied between experiments and appeared to be influenced by the age and developmental stage of the plants. There were no consistent responses between root treatments and net CO2 assimilation rates, and changes in root weight were not closely correlated with changes in assimilation. The mechanisms whereby new root growth is sustained are discussed.

Rooting cuttings of Syringa vulgaris cv. Charles Joly and Corylus avellana cv. Aurea: the influence of stock plant pruning and shoot growth

The relationship between shoot growth and rooting was examined in two, 'difficult-to root' amenity trees, Syringa vulgaris L. cv. Charles Joly and Corylus avellana L. cv. Aurea. A range of treatments reflecting severity of pruning was imposed on field-grown stock prior to bud break. To minimise variation due to the numbers of buds that developed under different treatments, bud number was restricted to 30 per plant. Leafy cuttings were harvested at different stages of the active growth phase of each species. With Syringa, rooting decreased with later harvests, but loss of rooting potential was delayed in cuttings collected from the most severe pruning treatment. Rooting potential was associated with the extent of post-excision shoot growth on the cutting but regression analyses indicated that this relationship could not entirely explain the loss of rooting with time, nor the effects due to pruning. Similarly, in Corylus rooting was promoted by severe pruning, but the relationship between apical growth on the cutting and rooting was weaker than in Syringa, and only at the last harvest did growth play a critical role in determining rooting. Another unusual factor of the last harvest of Corylus was a bimodal distribution of roots per cutting, with very few rooted cuttings having less than five roots. This implies that, for this harvest at least, the potential of an individual cutting to root is probably not limited by the number of potential rooting sites.

Advanced scalable algorithms for advanced architectures

With the latest advances in the area of advanced computer architectures we are seeing already large scale machines at petascale level and we are discussing exascale computing. All these require efficient scalable algorithms in order to bridge the performance gap. In this paper examples of various approaches of designing scalable algorithms for such advanced architectures will be given and the corresponding properties of these algorithms will be outlined and discussed. Examples will outline such scalable algorithms applied to large scale problems in the area Computational Biology, Environmental Modelling etc. The key properties of such advanced and scalable algorithms will be outlined.

Economic models and algorithms for distributed systems

Distributed computing paradigms for sharing resources such as Clouds, Grids, Peer-to-Peer systems, or voluntary computing are becoming increasingly popular. While there are some success stories such as PlanetLab, OneLab, BOINC, BitTorrent, and SETI@home, a widespread use of these technologies for business applications has not yet been achieved. In a business environment, mechanisms are needed to provide incentives to potential users for participating in such networks. These mechanisms may range from simple non-monetary access rights, monetary payments to specific policies for sharing. Although a few models for a framework have been discussed (in the general area of a "Grid Economy"), none of these models has yet been realised in practice. This book attempts to fill this gap by discussing the reasons for such limited take-up and exploring incentive mechanisms for resource sharing in distributed systems. The purpose of this book is to identify research challenges in successfully using and deploying resource sharing strategies in open-source and commercial distributed systems.

An analysis of real time implementation of Fourier transform-based frequency recognition algorithms

Frequency recognition is an important task in many engineering fields such as audio signal processing and telecommunications engineering, for example in applications like Dual-Tone Multi-Frequency (DTMF) detection or the recognition of the carrier frequency of a Global Positioning, System (GPS) signal. This paper will present results of investigations on several common Fourier Transform-based frequency recognition algorithms implemented in real time on a Texas Instruments (TI) TMS320C6713 Digital Signal Processor (DSP) core. In addition, suitable metrics are going to be evaluated in order to ascertain which of these selected algorithms is appropriate for audio signal processing(1).

Search space pruning and global optimization of multiple gravity assist trajectories with deep space manoeuvres

This paper deals with the design of optimal multiple gravity assist trajectories with deep space manoeuvres. A pruning method which considers the sequential nature of the problem is presented. The method locates feasible vectors using local optimization and applies a clustering algorithm to find reduced bounding boxes which can be used in a subsequent optimization step. Since multiple local minima remain within the pruned search space, the use of a global optimization method, such as Differential Evolution, is suggested for finding solutions which are likely to be close to the global optimum. Two case studies are presented.

Pulse shaping using state space algorithms

We discuss the use of pulse shaping for optimal excitation of samples in time-domain THz spectroscopy. Pulse shaping can be performed in a 4f optical system to specifications from state space models of the system's dynamics. Subspace algorithms may be used for the identification of the state space models.

Suboptimal system recovery from communication loss in a multi-robot localization scenario using EKF algorithms

This paper describes a multi-robot localization scenario where, for a period of time, the robot team loses communication with one of the robots due to system error. In this novel approach, extended Kalman filter (EKF) algorithms utilize relative measurements to localize the robots in space. These measurements are used to reliably compensate "dead-com" periods were no information can be exchanged between the members of the robot group.