Dynamic space warping algorithms on fine-grain array processors

We present a new mapping strategy of the dynamic space warping algorithm (DSWA) onto a 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. The new mapping scheme uses O(N² ) processors to generate each computation result in O(N+W² ) time. We also show the experimental results and performance comparison between Connection Machine (CM) 200 and the MGAP