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:
- 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.
- To simulate the proposed algorithms by means ALT-system.
- To assess the time and space complexity of cellular arithmetic
algorithms.
- 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:
- The library of cellular high-speed arithmetic algorithms
in binary, binary signed-digit and Knuth number systems
(length of operands is double).
- Computer tools for cellular algorithms simulation are
elaborated.
Perspectives:
- A new library of cellular high-speed arithmetic algorithm
with dynamically changed length of operands are to be
developed on base the available library.
- The time and space complexity of new cellular arithmetic
algorithms is to be assessed.
List of publications:
-
S.M.Achasova, O.L.Bandman, V.P.Markova, S.V.Piskunov
Parallel Substitution Algorithm. Theory and
Application // World Scientific: Singapore, 1994. - 220 pp.
-
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.
-
V.P.Markova Electrooptical implementation of
cellular multiplier // Avtometriya, N3, 1993. - P.14-27.
-
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.
-
V.P.Markova, S.V.Piskunov Computer Models of 3D
Cellular Structures // Lect. Notes Comput. Sci., N964,
1995. - P.70-84.
-
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
-
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.
-
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