Cellular Algorithm of High-Speed Arithmetic

List of the participants:

Summary:
The purpose of this project is to design cellular high-speed algorithm of the main arithmetic operations. The design and investigation tool is the computer simulating system Animating Language Tools (ALT) [1,7]. It realizes properties of an original model of distributed (cellular) computation named Parallel Substitution Algorithm (PSA) [1]. PSA explicit maps of computation processes, specified by a set of parallel substitutions, into cellular arrays.

Following investigations are intended to be done:
  1. To design cellular high-speed algorithm of the main arithmetic operations in different number systems (NS) maximum using parallelism and piplining on all levels, different input/output formats.
  2. To simulate the proposed algorithms by means ALT-system.
  3. To assess the time and space complexity of cellular arithmetic algorithms.
  4. To perform the comparative analysis of using number systems with respect to performance of cellular arithmetic algorithms.

Applications:
Obtained results have the following applications:

Simulation of given algorithm is to be realized in cellular structure in different number systems and production of its the time and space complexity.

The main result:
  1. The library of cellular high-speed arithmetic algorithms in binary, binary signed-digit and Knuth number systems (length of operands is double).
  2. Computer tools for cellular algorithms simulation are elaborated.

Perspectives:
  1. A new library of cellular high-speed arithmetic algorithm with dynamically changed length of operands are to be developed on base the available library.
  2. The time and space complexity of new cellular arithmetic algorithms is to be assessed.

List of publications:
  1. S.M.Achasova, O.L.Bandman, V.P.Markova, S.V.Piskunov Parallel Substitution Algorithm. Theory and Application // World Scientific: Singapore, 1994. - 220 pp.
  2. O.Bandman, V.Markova, S.Piskunov. 2D->3D Transformation of Cellular Algorithm // Proceedings of the International Conference on Parallel Computing Technologies, ed. V. Malyshkin. Obninsk (Russia), August 30 - September 4, 1993, Vol. 1. - P.117.
  3. V.P.Markova Electrooptical implementation of cellular multiplier // Avtometriya, N3, 1993. - P.14-27.
  4. V.P.Markova The Cellular Knuth Algorithm for Complex Number Multiplication // Parcella'94. Proceedings of the VI International Workshop on Parallel Processing by Cellular Automata and Arrays, Potsdam, Sept. 21-23, 1994. - P.91-98.
  5. V.P.Markova, S.V.Piskunov Computer Models of 3D Cellular Structures // Lect. Notes Comput. Sci., N964, 1995. - P.70-84.
  6. V.P.Markova Multilayer Cellular Algorithm for Complex Number Multiplication // Proceedings of ASAP-95, Strasburg, France, Ju y 16-20, 1995. - IEEE Computer Society Press: Los-Alamos, USA
  7. V.Markova, U.Pogudin, S.Piskunov. Formal Methods, Language Tools and Technigues for Synthesis of Cellular Algorithm and Architecture // To appear in Programmirovanie, 1996, N4.
  8. V.P.Markova 3D Cellular Pipelined Algorithm for Many Number Pairs Multiplication. // To appear in Proc. PARCELLA'95.

Please contact Valentina Markova for all the questions concerning this project.
E-mail: mark@sscc.ru


Last update: June 14, 1996