New Processor Array Architectures for the Longest Common Subsequence Problem |
| |
Authors: | Email author" target="_blank">Panagiotis?D?MichailidisEmail author Konstantinos?G?Margaritis |
| |
Affiliation: | (1) Department of Applied Informatics, Parallel and Distributed Processing Laboratory, University of Macedonia, 156 Egnatia str., P.O. Box 1591, 54006 Thessaloniki, Greece |
| |
Abstract: | A longest common subsequence (LCS) of two strings is a common subsequence of two strings of maximal length. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). In this paper, we present a new linear processor array for solving the LCS problem. The array is based on parallelization of a recent LCS algorithm which consists of two phases, i.e. preprocessing and computation. The computation phase is based on bit-level dynamic programming approach. Implementations of the preprocessing and computation phases are discussed on the same processor array architecture for the LCS problem. Further, we propose a block processor array architecture which reduces the overall communication and time requirements. Finally, we develop a performance model for estimating the performance of the processor array architecture on Pentium processors. |
| |
Keywords: | longest common subsequence problem linear processor arrays parallel architectures parallel algorithms VLSI |
本文献已被 SpringerLink 等数据库收录! |
|