Dynamic space warping algorithms on fine-grain array processors

Heung Nam Kim, Mary Jane Irwin, Robert M. Owens, Chen Mi Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we present a new mapping strategy of the dynamic space warping algorithm (DSWA) onto our micro-grained array processor (MGAP). This new mapping strategy reduces the communication complexity between processing elements and increases the performance due to data pipelining and interleaving. The DSWA, which can be applied to image recognition, originally needs a four-dimensional array. Practically, however, this four-dimensional algorithm must be mapped onto a two-dimensional array processor. A previous mapping used O(NW) processors to compute the distance between an N × N input image and a reference image with the warping distance W in O(NW) time. Our new mapping scheme uses O(N)2 processors to generate each computation result in O(N+W2) time. We also show the experimental results and performance comparison between Connection Machine (CM) 200 and the MGAP.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages921-925
Number of pages5
ISBN (Print)0818656026
StatePublished - Jan 1 1994
EventProceedings of the 8th International Parallel Processing Symposium - Cancun, Mex
Duration: Apr 26 1994Apr 29 1994

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings of the 8th International Parallel Processing Symposium
CityCancun, Mex
Period4/26/944/29/94

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Dynamic space warping algorithms on fine-grain array processors'. Together they form a unique fingerprint.

Cite this