Algorithms

To improve the performance of parallel/distributed systems, we propose four parallel load balance algorithms. The new partition algorithm achieves load balance among processors via domain partition. If we assume the problem domain is evenly load distributed, this algorithm will divide the whole domain into a required number of subdomains with the same area. If a problem domain has a dynamic load distribution, although the new partition algorithm is still suitable for the initial mapping, we propose three dynamic load balance algorithms. These dynamic algorithms achieve load balance among processors by transferring load among processors. We applied the new partition algorithm to a specific domain and compared the method to some existing partition algorithms. We also simulated three dynamic load balance algorithms. Results of comparisons and simulations show that all the four algorithms have satisfactory performance.

We propose the enhanced Fibonacci cube (EFC), which is defined based on the sequence Fn = 2(n-2) + 2F(n-4). We study its topological properties, embeddings, applications, routings, VLSI/WSI implementations, and its extensions. Our results show that EFC retains many properties of the hypercube. It contains the Fibonacci cube (FC) and extended Fibonacci cube of the same order as subgraphs and maintains virtually all the desirable properties of FC. EFC is even better in some structural properties, embeddings, applications and VLSI designs than FC or hypercube. With EFC, there are more cubes with various structures and sizes for selection, and more backup cubes into which faulty hypercubes can be reconfigured, which alleviates the size limitation of the hypercube and results in a higher level of fault tolerance.

Feature extraction for handwritten character recognition has always been a challenging problem for investigators in the field. The problem gets worse due to large variations present for each type of input character. Our algorithm computes directional features for alphanumeric input mapped on to a hexagonal lattice. The algorithm implements size and scale invariance that is a requirement for achieving a reasonably good recognition rate. Functional performance has been verified for an hexagonal lattice mapped input on the data obtained from the US postal service handwritten character database. In this thesis, we implemented the algorithm in a Xilinx FPGA (XC4xxx series).

In this thesis we describe a local-neighborhood-pixel-based adaptive algorithm to track image features, both spatially and temporally, over a sequence of monocular images. The algorithm assumes no a priori knowledge about the image features to be tracked, or the relative motion between the camera and the 3-D objects. The features to be tracked are selected by the algorithm and they correspond to the peaks of '2-D intensity correlation surface' constructed from a local neighborhood in the first image of the sequence to be analyzed. Any kind of motion, i.e., 6 DOF (translation and rotation), can be tolerated keeping in mind the pixels-per-frame motion limitations. No subpixel computations are necessary. Taking into account constraints of temporal continuity, the algorithm uses simple and efficient predictive tracking over multiple frames. Trajectories of features on multiple objects can also be computed. The algorithm accepts a slow, continuous change of brightness D.C. level in the pixels of the feature. Another important aspect of the algorithm is the use of an adaptive feature matching threshold that accounts for change in relative brightness of neighboring pixels. As applications of the feature-tracking algorithm and to test the accuracy of the tracking, we show how the algorithm has been used to extract the Focus of Expansion (FOE) and compute the Time-to-contact using real image sequences of unstructured, unknown environments. In both these applications, information from multiple frames is used.

The crucial goal of enhancing industrial productivity has led researchers to look for robust and efficient solutions to problems in production systems. Evolving technologies has also, led to an immediate demand for algorithms which can exploit these developments. During the last three decades there has been a growing interest in algorithms which rely on analogies to natural processes. The best known algorithms in this class include evolutionary programming, genetic algorithms, evolution strategies and neural networks. The emergence of massively parallel systems has made these inherently parallel algorithms of high practical interest. The advantages offered by these algorithms over other classical techniques has resulted in their wide acceptance. These algorithms have been applied for solving a large class of interesting problems, for which no efficient or reasonably fast algorithm exists. This thesis extends their usage to the domain of production research. Problems of high practical interest in the domain of production research are solved using a subclass of these algorithms i.e. those based on the principle of evolution. The problems include: the flowpath design of AGV systems and vehicle routing in a transportation system. Furthermore, a Genetic Based Machine Learning (GBML) system has been developed for optimal scheduling and control of a job shop.

A novel neural network, trained with the Alopex algorithm to recognize handprinted characters, was developed in this research. It was constructed by an encoded fully connected multi-layer perceptron (EFCMP). It consists of one input layer, one intermediate layer, and one encoded output layer. The Alopex algorithm is used to supervise the training of the EFCMP. Alopex is a stochastic algorithm used to solve optimization problems. The Alopex algorithm has been shown to accelerate the rate of convergence in the training procedure. Software simulation programs were developed for training, testing and analyzing the performance of this EFCMP architecture. Several neural networks with different structures were developed and compared. Optimization of the Alopex algorithm was explored through simulations of the EFCMP training procedure with the use of different parametric values for Alopex.

Thinning is a very important step in a Character Recognition System. This thesis evolves a thinning algorithm that can be hardware implemented to improve the speed of the process. The software thinning algorithm features a simple set of rules that can be applied on both hexagonal and orthogonal character images. The hardware architecture features the SIMD structure, simple processing elements and near neighbor communications. The algorithm was simulated against the U.S. Postal Service Character Database. The architecture, evolved with consideration of both the software constraints and the physical layout limitations, was simulated using VHDL hardware description language. Subsequent to VLSI design and simulations the chip was fabricated. The project provides for a feasibility study in utilizing the parallel processor architecture for the implementation of a parallel image thinning algorithm. It is hoped that such a hardware implementation will speed up the processing and lead eventually to a real time system.

This paper surveys work of the last few years on construction of bijections for
partition identities. We use the more general setting of sieve--equivalent families. Suppose A1' ... ,An are subsets of a finite set A and B1' ... ,Bn are subsets of a finite
set B. Define AS=∩(i∈S) Ai and BS = ∩ (i∈S) Bi for all S⊆N={1,...,n}. Given explicit bijections fS: AS->BS for each S⊆N, A-∪Ai has the same size as B-∪Bi. Several
authors have given algorithms for producing an explicit bijection between these two
sets. In certain important cases they give the same result. We discuss and
compare algorithms, use Graph Theory to illustrate them, and provide PAS CAL
programs for them.

This thesis presents several algorithms to treat the problem
of closed-loop near minimum-time controls with
discontinuities. First, a neighboring control algorithm is
developed to solve the problem in which controls are bounded
by constant constraints. Secondly, the scheme is extended
to account for state-dependent control constraints. And
finally, a path tracking algorithm for robotic manipulators
is presented, which is also a neighboring control algorithm.
These algorithms are suitable for real time controls because
the on-line computations involved are relatively simple.
Simulation results show that these algorithms work well
despite the fact that the prescribed final points can not be
reached exactly.

The capabilities and limitations of Programmable Array Logic
devices (PALs) are presented and compared to other logic devices. PALs
are field programmable devices and a program called PALSAM exists to
assist the designer in programming PALs. The attributes and
limitations of PALSAM are discussed. The PALSAM Input Data File
Generator program was written to eliminate many of the limitations of
PALSAM. The need for an algorithmic method of reducing a general
logic expression to a minimal sum-of-products form is demonstrated.
Several algorithms are discussed. The Zissos, Duncan and Jones
Algorithm, which claims to produce a minimal sum-of-products
expression but is presented without proof by its authors, is
disproved by example. A modification of this algorithm is presented
without proof. When tested in the 276 possible cases involving up to
three variables, this new algorithm always produced a minimal
sum-of-products expression, while the original algorithm failed in six
of these cases. Finally, the PALSAM Input Data File Generator program
which uses the modified algorithm is presented and documented.