Investigation of associative algorithms
for vertical processing systems

List of the participants:

This project is supported by the Russian Foundation for Basic Research under Grant N 96-01-01704.

Summary:
Fine-grained SIMD-systems with bit-serial (vertical) processing and simple single-bit PEs have been the subject of intensive research in the recent years. Well-known multi-processors STARAN, DAP, MPP, CM-2 belong to this class of architectures. One of the most important fields of vertical processing systems (VPS) application is the non-numeric processing, that is, data bases, knowledge bases, expert systems and other problems of artificial intelligence. Therefore such processors can be used as a component in the combined architecture. We will analyze algorithms for STARAN-like associative parallel processors (APPs). Such an architecture is well suited for solving problems employing tabular data. Our prime interest is in associative system applications for solving graph theoretical problems. To this end we use an abstract semantic model (the STAR-machine) of the SIMD type with vertical data processing. Its primitive operations are sufficiently rich to allow efficient itilization of massive parallelism.

The project includes the following stages:
  1. to select a class of graph theoretical problems which can be effectively solved in a robust natural way by means of APPs;
  2. to analyze the corresponding associative algorithms, to prove their correctness and evaluate their complexity;
  3. to select the corresponding primitive procedures for which it would be appropriate for use some accelerators (specialized processors);
  4. to state some proposals for extending the capabilities of APPs.

Perspectives:
We are planning to design an experimental system STAR on IBM PC which will include the STAR translator and knowledge base. The latter one will consist of the main basic procedures for different problem oriented shells which will be used for designing algorithms. As a result of our investigation we hope to obtain proposals for designing new dedicated hardware means providing parallel high-performance solution of those problems.

List of publications:
  1. A.S.Nepomniaschaya. Language STAR for Associative and Parallel Computation with Vertical Data Processing, in: Proc. of the Intern. Conf. "Parallel Computing Technologies", (Novosibirsk, USSR, 1991) 258--265.
  2. A.S.Nepomniaschaya Investigation of Associative Search Algorithms in Vertical Processing Systems. in: Proc. of the Intern. Conf. "Parallel Computing Technologies", (Obninsk, Russia, 1993).
  3. A.S.Nepomniaschaya. Comparison of two MST Algorithms for Associative Parallel Processors, in: Proc. of the 3-d Intern. Conf. "Parallel Computing Technologies", PaCT--95, (St. Peterburg, Russia), Lecture Notes in Computer Science, 964, (1995) 85--93.
  4. A.S.Nepomniaschaya, Y.I.Fet. Investigation of Some Hardware Accelerators for Relational Algebra Operations. - IEEE, Proceedings of the First Aizu Intern. Symp. on Parallel Algorithms/Architectures Synthesis, Japan, 1995.
  5. A.S.Nepomniaschaya. Representations of the Prim--Dijkstra algorithm on associative parallel processors, to appear in Proceedings of PARCELLA'96.
  6. A.S.Nepomniaschaya. An Associative Version of the Prim--Dijkstra Algorithm and its Application to Some Graph Problems, to appear in LNCS, Proceedings of the Second Intern. Memorial Conf. "Perspectives of System Informatics", 1996.
  7. A.S.Nepomniaschaya. Representation of the Gabow algorithm for finding smallest spanning trees with a degree constraint on associative parallel processors, to appear in LNCS, Proceedings of the EuroPar'96.

Please contact Ann Nepomniaschaya for all the questions concerning this project.
E-mail: anep@ssd.sscc.ru

Last update: June 5, 1996