Present subjects of research
Current interests are in studying associative parallel algorithms on graphs
by means of vertical processing systems. Such an architecture belongs to
fine--grained systems with bit--serial (or vertical) processing and simple
single-bit processing elements. These systems provide very high performance
due to concurrent run of a large number of PEs. They are well suited to
solving graph theoretical problems.
Main results include:
- a high--level language STAR; its operational semantics is described
by means of an abstract model (the STAR--machine); this language is related
to Pascal, but has some special data types and the corresponding operations
for them providing associative and parallel processing; algorithms are
represented as the corresponding STAR procedures;
- design of associative algorithms for finding a connected component,
a minimal spanning forest, transitive closure of a graph, for verifying an
articulation point and verifying a bridge in undirected weighted graphs
represented as a list of triples (edge vertices and their weights); these
algorithms are based on a new associative version of the Prim--Dijkstra
algorithm for finding a minimal spanning tree;
comparison of performing the different associative versions of
Prim--Dijkstra's algorithm for different graph representation forms on
the STAR--machine;
- an associative version of Gabow's algorithm for finding smallest
spanning trees with a degree constraint; we have shown that on an
associative parallel processor it takes the same time as a minimal spanning
tree algorithm, that is, $0(n\log n)$ time, where $n$ is the number of
vertices in a given graph;
- design of dynamic associative algorithms for solution of path
problems; it includes the transitive closure of
a directed graph (an associative version of Warshall's algorithm), the
all--pairs shortest path problem (an associative version of Floyd's
algorithm) and minimal spanning tree problem as a path finding one
(an associative version of Maggs--Plotkin's algorithm); we have shown that
on the STAR--machine having no less than $n$ processing elements any of
these algorithms takes $0(n^2)$ time;
- a new associative algorithm for finding a critical cycle in
directed weighted graphs; it uses a special construction with a trap for
saving positions of those arcs which cannot be included in a directed
cycle; the corresponding procedure takes $O(l\log n)$ time on the
STAR--machine, where $l$ is the number of arcs included in the critical
cycle.
Current projects
Main publications
(74 papers have been published in automata theory, theory of formal grammars
and languages, theory of parallel algorithms and parallel processing.)
- Very-High-Level Language PARIS (with V.\,D.\,Korneev,
N.\,N.\,Mirenkov). In: Proc. of the Intern. Conf. ``Parallel
Computing Technologies", (World Scientific, Singapure) (1991) 186--194.
- Language STAR for Associative and Parallel Computation with
Vertical Data Processing. In: Proc. of the Intern. Conf. ``Parallel
Computing Technologies", (World Scientific, Singapure) (1991) 258--265.
- Application of specialized processors for effective
realization of relational algebra operations in vertical processing
systems (with Y.I.Fet). In: Cybernetics and System Analysis,
(1993), No.2, 85--94 (in Russian).
- Investigation of associative search algorithms in vertical
processing systems. In: Proc. of the Intern. Conf. "Parallel
Computing Technologies", (part 3), Obninsk, Russia, (1993), 631--642.
- Modelling of an Associative Parallel Processor Run (Description
of a Language and its Translator), (with V.J.Tskhay). In: Teoria i
sistemi upravlenia, (Izvestia Akademii nauk, Moscow), (1995), No.3,
154--159 (in Russian).
- Optimization of representing an algorithm for finding a minimal
spanning tree on associative parallel processors. In: Cybernetics and
System Analysis}, (1995), No.4, 3--13 (in Russian).
- Investigation of Some Hardware Accelerators for Relational Algebra
Operations (with Y.I.Fet). In: IEEE, Proceedings of the First Aizu
Intern. Symp. on Parallel Algorithms/Architectures Synthesis, Japan, (1995),
308--314.
- Comparison of two MST Algorithms for Associative Parallel Processors.
In: Proc. of the 3-d Intern. Conf. "Parallel Computing Technologies",
PaCT--95, (St. Petersburg, Russia), Lecture Notes in Computer Science,
{\bf 964}, (1995) 85--93.
- Representation of the Gabow Algorithm for Finding Smallest Spanning
Trees with a Degree Constraint on Associative Parallel Processors.
In: Euro--Par'96 Parallel Processing. Second Intern. Euro--Par Conf.
Lyon, France. Proceedings, Lect. Notes in Comp. Sci., (Springer--Verlag,
Berlin, 1996), v.1123, 813--817.
- An Associative Version of the Prim--Dijkstra Algorithm and its
Application to Some Graph Problems. In: Andrei Ershov Second Intern.
Memorial Conf. ``Perspectives of System Informatics", Lecture Notes in
Computer Science, v. 1181, (Berlin: Springer--Verlag,1996) 203--213.
- Representations of the Prim--Dijkstra Algorithm on Associative
Parallel Processors. In: Proc. of VII Intern. Workshop on
Parallel Processing by Cellular Automata and Arrays. Parcella'96,
(Academie Verlag, Berlin, 1996) 184--194.
- Comparison of models for associative parallel computations
(with M.A.Vladyko). In: Programming, Moskow, (1997), No.6, 41-50
(in Russian). (English translation by Plenum Press, USA).
- Solution of Path Problems Using Associative Parallel Processors In:
Proceedings of the International Conference on Parallel and Distributed
Systems, (IEEE Computer Society Press), ICPADS'97, December 10--13, (1997),
Korea, Seoul, 610--617.
- Effective Representation of Some Graph Problems on Associative Parallel
Processors. In: Proceedings of the Twelfth International Symposium on
Computer and Information Sciences, (Bogazici University Printhouse),
ISCIS XII, October 27--29, (1997), Antalya, Turkey, 430--437.
- An Efficient Associative Algorithm for Finding the
Smallest Spanning Tree with a Degree Constrained. In: Cybernetics and
System Analysis, Kiev, (1998), No.1, 94--103 (in Russian).
(English translation by Plenum Press, USA).
- A Simple Implementation of Dijkstra's Shortest Path Algorithm on
Associative Parallel Processors. (together with Dvoskina M.A.) In:
Proceedings of the Concurrency, Specification and Programming Workshop,
Warsaw, Poland, September 28-30, (1999), 141--152.
This page last updated on Jan 25, 2000.