Multiresolution architectures and algorithms

This thesis investigates multiresolution algorithms and the supporting multiresolution architectures, particularly pyramid networks. After a thorough evaluation of multiresolution algorithms in the literature, the algorithms have been classified into five categories based on functionality and data flow. Two novel multiresolution algorithms have been proposed, implemented, and tested for analysis, detection, and separation of mixed signals using the new mathematical tool, the wavelet transform. The first algorithm allows one to design a mother wavelet and the wavelet grid that guarantees the separation of signal components if information about the expected minimum time and frequency separation of the individual components is known. The second algorithm expands this idea to design two mother wavelets which are then combined to achieve the required separation otherwise impossible with a single wavelet. Potential applications include the analysis of many biological signals and also object detection in images. A theoretical study of the processor utilization of pyramids in running multiresolution algorithms has demonstrated that a pyramid architecture can be efficiently used to implement multiresolution algorithms. Processor utilization of the pyramid processing elements has been found to be very high except for the class of iterative multiresolution algorithms. A pyramid simulation environment has been developed on the Connection Machine CM-2 to assist researchers in implementing, analyzing, and evaluating multiresolution algorithms. The routing issues in the pyramid architecture have been analyzed using discrete event simulation using the SMPL library routines. Two pyramid routing algorithms have been developed: neighbor-tree (NT) and neighbor-descendent-tree (NDT). The average and maximum message latency for each of the three flow control schemes: packet switching, circuit switching, and worm-hole routing has been measured for both NT and NDT algorithms. The performance of the proposed algorithms is evaluated and compared with alternative routing schemes such as pyramid mesh and tree routing. This study has shown that using the vertical as well as the mesh links for routing can achieve a 10% to 30% improvement over mesh links alone. The degree of improvement depends upon the pyramid layer and the communication patterns.