A parallel level-building algorithm for connected-word recognition on the DADO/DSP.

The purpose of this paper is to describe and evaluate a parallel level-building algorithm for connected-word recognition, targeted for implementation on the DADO/DSP multiprocessor system. The contribution here is a decomposition and mapping of Rabiner's level-building algorithm, which enables one to efficiently exploit the massive parallelism available in the DADO/DSP architecture. This parallel algorithm on DADO/DSP is projected to execute orders of magnitude faster than the sequential version on a uniprocessor. DADO/DSP is a fine-grain parallel architecture in which processing and memory are extensively intermingled, proposed by AT&T to the DARPA Strategic Computing Program. A full-scale production version of the architecture would comprise thousands of processing elements (PE). These PEs are interconnected to form a complete binary tree, according to the design developed by S. Stolfo at Columbia University.