CSC/ECE 506 Fall 2007/wiki2 6 sbh

MSIMD applications

Multiple-SIMD (MSIMD) architectures expand on SIMD architecture abilities, and alleviate some of their weaknesses. Since a single array control unit controls all processing elements in a SIMD architecture, processing elements (PE) are often under-utilized when a process comes in, but does not require the use of all the PEs. MSIMD architectures are formed with clusters of virtual SIMD machines, so there are multiple array control units to control the PEs. This allows other programs and users to utilize idle PEs.

Below are some examples, based on published papers, of research involving MSIMD architectures and the types of applications for which they have been found useful.

The GPA Machine

The GPA machine has shown to be beneficial to algorithms based on dynamic data structures and fragmented partitions. These algorithms will show substantial speedup on this architecture. Multi-user operating system development will also benefit from this architecture. A main benefit of the GPA machine architecture is the ability to allocate resources based on availability and need.

The Warwick Pyramid Machine

The Warwick Pyramid Machine (WPM) allows for the faster tracking of features within images. Each SIMD cluster within the WPM works on a region of the image. Iconic data is processed in the MSIMD array.

The WPM has been used for image analysis techniques such as: motion estimation, segmentation, object detection, edge extraction and enhancement, feature extraction and graphics, and Hough transforms. The Hough transform is used to detect specific shapes in images. Most commonly, it is used to detect straight lines and circles, which might signify a man made object in an image. These transforms cost a significant amount of time and resources, though straight line and circle detection takes fewer parameters than most other shapes. Programming a Hierarchical Hough Transform (which is more thorough and improves upon the original Hough Transform) is more complex on a M-SIMD architecture, but the relatively small amount of extra complexity pays off in enhanced performance and increased programming capability. Advantages include having adjacent clusters work on seperate instruction streams, local associativity, and improved vertical communication bandwidth.

Artificial Neural Networks

In this architecture, Processing Elements are set up locally as SIMD vector processors with local ring communication. This setup is particularly good for recognition and optimization programs.

References

[1]Alaghband, Gita. "SIMD Architectures." University of Colorado at Denver.

[2]The GPA Machine: A Generally Partitionable MSIMD Architectures

[3]A MSIMD Architecture for Feature Tracking

[4]Performance Evaluation of the Hierarchical Hough Transform on an Associative M-SIMD Architecture

[5] A Massively Parallel, Multiple-SIMD Architecture for Implementing Artificial Neural Networks