Solution of path problems using associative parallel processors

Author

Nepomniaschaya, A.S.

Author_Institution

Supercomput. Software Dept., Acad. of Sci., Novosibirsk, Russia

fYear

1997

fDate

10-13 Dec 1997

Firstpage

610

Lastpage

617

Abstract

In this paper we study a question of representing a group of associative algorithms on an abstract model of the SIMD type with vertical data processing (the STAR-machine). This group includes the Warshall transitive closure algorithm, the Floyd shortest path algorithm and the Maggs-Plotkin minimal spanning tree algorithm. These algorithms are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated

Keywords

associative processing; computational complexity; computational geometry; parallel processing; Floyd shortest path algorithm; Maggs-Plotkin minimal spanning tree algorithm; SIMD type; STAR procedures; STAR-machine; Warshall transitive closure algorithm; abstract model; associative algorithms; associative parallel processors; correctness; path problems; time complexity; vertical data processing; Arithmetic; Associative memory; Automata; Data processing; Digital audio players; Dynamic programming; Equations; Gaussian processes; Performance analysis; Supercomputers;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 1997. Proceedings., 1997 International Conference on

Conference_Location

Seoul

Print_ISBN

0-8186-8227-2

Type

conf

DOI

10.1109/ICPADS.1997.652606

Filename

652606