Nepomnaschaya Anna Shmilievna

Position: Senior researcher

Email: anep@ssd.sscc.ru

Phone: (+73832) 30-89-94

Room: 408

Education:

1981, Ph.D. , Computer Science, Novosibirsk Computer Center, Siberian Division, USSR Academy of Sciences.
1967, M.S. Mathematics, with Honors, Chernovtsy State University, Ukraine

Interests:

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. However, to solve tasks on these systems, it is necessary to construct new approaches and methods which take into account the advantages of this architecture. We have constructed a natural straight forward implementation of a group of classical graph algorithms on a model of associative parallel systems (the STAR-machine) using simple and natural data structures. For directed graphs, we have proposed associative versions of Warshall's algorithm for finding transitive closure, of Floyd's algorithm for finding the all-pairs shortest paths, of Dijkstra's algorithm and of the Bellman-Ford one for finding the single-source shortest paths, and of Edmonds' algorithm for finding optimum branchings. For undirected graphs, we have suggested associative versions of Kruskal's algorithm and of the Prim-Dijkstra one for finding the minimal spanning tree, and of Gabow's algorithm for finding the smallest spanning tree with a degree constraint. Associative versions of algorithms have been given as the corresponding procedures represented on the STAR-machine and their correctness has been proved. 92 papers have been published in automata theory, theory of formal grammars and languages, theory of parallel algorithms and parallel processing.

Activities:

Awards:
1994. International Science Foundation. Project “Associative parallel computations.”
1996. Russian Basic Foundation. Project “Investigation of associative parallel algorithms.”
1999. Russian Basic Research Foundation. Project “Associative parallel algorithms of optimization on graphs.”
2003. Russian Basic Research Foundation. Project “Associative parallel algorithms of updating trees.”

Publications:

(Here listed main ones since 1997, total amount of publications is 92):

1. Comparison of models for associative parallel computations In: Programming, 1997, No.6, 41-50 (in Russian). (English translation by Plenum Press, USA). (with M.A. Vladyko).
2. An Efficient Associative Algorithm for Finding the Smallest Spanning Tree with a Degree Constrained. In: Cybernetics and System Analysis. Kiev: Naukova Dumka, 1998, No.1, 94--103 (in Russian). (English translation by Plenum Press, USA).
3. An Associative Parallel Algorithm for Finding a Critical Cycle in Directed Graphs. In: Proceedings of the Seventh International Conference on Parallel and Distributed Systems, IEEE Computer Society Press, (ICPADS 2000), Iwate, Japan, 2000, 455-462.
4. A Simple Implementation of Dijkstra's Shortest Path Algorithm on Associative Parallel Processors. In: Fundamenta Informaticae, IOS Press, Amsterdam, v. 43, 2000, 227-243. (with M.A. Dvoskina).
5. Comparison of performing the Prim--Dijkstra alrorithm and the Kruskal algorithm by means of associative parallel processors. In: Cybertetics and System Analysis, Kiev: Naukova Dumka, No. 2, 2000, 19-27. (in Russian). (English translation by Plenum Press, USA).
6. Representation of Edmonds' algorithm for finding optimum branching on associative parallel processors. In: Programming, No. 4, 2001, 43-52. (in Russian). (English translation by Plenum Press, USA).
7. An Associative Version of the Bellman-Ford Algorithm for Finding the Shortest Paths in~Directed Graphs, Proceedings of the 6-th Intern. Conf. PaCT-2001, Lect. Notes in Comp. Sci., (Springer--Verlag, Berlin), 2001, v. 2127, 285-292.
8. Efficient Implementation of Edmonds' Algorithm for Finding Optimum Branchings on Associative Parallel Processors, Proc. of the Eighth Intern. Conf. on Parallel and Distributed Systems (ICPADS'01), (IEEE Computer Society Press), KyongJu City, Korea, 2001, 3-8.
9. Associative Parallel Algorithms for Dynamic Edge Updates of Minimum Spanning Trees. Intern. Conf. Pact 2003, Proceedings, Lecture Notes in Computer Science, 2003, v. 2763, 141-150.
10. Associative Graph Processor and its Properties. Proc. of the International Conference on Parallel Computing in Electrical Engineering (PARELEC 2004), Dresden, Germany, 2004, 297-302 (together with Kokosinski).