JPRS ID: 9845 USSR REPORT LIFE SCIENCES BIOMEDICAL AND BEHAVIORAL SCIENCES

• Document Type: CREST
• Collection: JPRS
• Document Number (FOIA) /ESDN (CREST): CIA-RDP82-00850R000400070026-2
• Release Decision: RIF
• Original Classification: U
• Document Page Count: 105
• Document Creation Date: November 1, 2016
• Sequence Number: 26
• Content Type: REPORTS

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
JPRS L/10111
10 NovAmber 1981
Translation
COMPUTING SYSTEl~AS AND SYNCHRONOUS ARITHMETIC
- BY
M.A. Kartsed and V.A. Brik
FBiS F~REICf~ BROADCAST INFORMATION SERVICE
FOR OFFICIAL USE ONtY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
NOTE
JPRS publications contain information primarily from foreign
~,ewspapers, periodicals and books, but also from news agency
transmissions and broadcasts. Materials from foreign-Language
sources are translated; those from English-language sources
ar~ transcribed or reprinted, with the original phrasing and
other characteristics retained.
Headlines, editorial reports, and material enclosed in brackets
[J are supplied by JPRS. Processing indicators such as [Text]
or [Excerpt] in the first line of each item, or following the
- last line of a brief, indicate how the original information was
processed. Where no processing indicator is given, the infor-
mation was summarized or extracted.
~ Unfamiliar names rendered phonetically or transliterated are
enclosed in parentheses. Words or names preceded by a ques-
tion mark and enclosed in parentheses were not clear in the
original but have been supplied as appropriate in context.
= Other unattributed parenthetical notss within the body of an
- item originate with the saurce. Times within items are as
given by source.
The contents of this publication in no way represent the poli-
cies, views or at.titudes of the U.S. Government.
COPYRIGHT LAWS AND REGULATIONS GOVERNING OWNERSHIP OF
MAT~RIALS REPRODUCED HEREIN REQUIRE THAT DISSEMINATION
OF THIS PUBLICATION BE RESTRICT'ED FOR OFFICIAL USE ONLY.
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
JPRS L/10111
10 November 1981
COMPUTING SYSTEMS AND SY~~CHRONOUS ARITNME~YC
Moscow VYCHISLITEL'NYYE SISTEMY I SINKHRONNAYA ARIFMETIKA in Russian
1981 (signed to press 26 Mar 8I) pp 2-5, 162-275, 348-359
[Annc~tation, table of contents, preface, ch~:~.uters 4 and 5, bibliography
and index from book "Computing Systems and Synchronous Arithmetic", by
Mikhail Aleksandrovich Kartsev and Vladimir Arkad'yevich Brik,
Izdatel'stvo "Radio i svyaz 10,000 copies, 360 pages, UDC 681.32]
' . CONTENTS
Annotation ~ i
Preface
4. High-Speed Synchronous Multir,liers .
4.1. Decreasing the Time For Adding Fartial Products 3
4.2. Preliminary Formation of Multiples of Multiplicand 5
4.3. Use of Negative Partial Products ~
4.3.1. Method of Multiplication by Group of q Bits of Multiplier
with Decoding of q+l Bits of Multiplier ~
4.3.2. Method of Multiplication from Low-0rder Bi~s of Multiplier 9
4.4. Analysis and Technique of Building Simultaneous Multipliera 13
4.4.1. Classif ication of Simultaneous Multipliers 13
4.4.2. Analysis of Processea of Adding Partial Products in
Homogeneous Simultaneous Array Multipliers
4.4.3. Analyais of Processes of "Decay" in Hamogeneous
Simultaneous Array Multipliers 25
4.4.4. Multilayer Simultaneoua Array Multipliers 27
5. High-SPeed Synchronous Dividers
5.1. Methods of Short Restoring Division 47
5.2. Stefanelly's Methods 48
5.3. Performing Division by Multiplication 49
5.4. Short Nonrestoring Division 52
5.4.1. General Description of Nonrestoring Divis~on 52
5.4.2. Classical Methad of Division 56
5.4.3. Graphic-Analytic Method of Analysis of Processes of Division 62
5.4.4. Division Using Symmetrical Set of Integers Including Zero 65
5.4.5. Generalized Method of Nonrestoring Division and
Investigation of It 70
5.4.6. Example of Implementation of Generalized Method of
~ Nonrestoring Division 83
_ g- jI - USSR - N FOUO]
- FOR OFFI~CIAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED F~R RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICiAL USE ONLY
Bibliography ~8
S ubject Index 96
Table of Contents 99
- b -
FOR OFFICIAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00854R400404070026-2
FOR OFFICIAL USF ONLY
. .
[Text] Annotation
The authors investigate, on the one hand, the organization of structures of
multimachine, multiprocessor axzd conveyor computing systems and the organization
of computations in them, and one the other hand, the ma~oritq of lmowa methods
fur building high-speed synchronaua adders, multipliers and devices for division
_ used in computing systems and machines.
- Preface ~
' When we starzed on this book, we realized there is currently no shortage of material
on computing systems. On the contrary, the flow of books and articles on this sub-
ject is essentially outstripping the development of technology and methods of
applying computing systems. The number of titles of ~ust monographs on this sub~ect
probably exceeds t:ie number of computing systems that have been imp~emented and are.
operating in the world. Meanwhile, there are still tao many points not yet clear '
in this f ield.
Even the termi.nology has not stabilizQd. In this book,Iby the phrase "computing
- system," used in the title, we mean computing resources designed to execute para11e1
computations; a precise definition of this concept is in section 1.1.1.
But the question least analyzed, in our view, is throughput of computing systems.
Too often the data given on the throughput of a computing system in design or pro-
duction are obtained by simply adding the throughput of the individual resources
that make up the system. Meanwhile, the situations users of the actual computing
system encounter may be considerably different;~ accordingly, the data on system
throughput that he needs are also different.
If the system is used within a major computer center, where a large number of users
solve their relatively small problems, total system throughput is of little interest
to each individual user. It is important to him only to the extent that it affects
- 1
~ FOR OFFICIAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPR~VED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
the ti~~w hc ~ets tur up~ruCinb iu tt~e interactive mode or the jobs accept~d trum
him for processing in the batch mode.
We deal with a very similar situationv as a rule, in using a computing systeJn with-
in an automated production manageinent system (on the scale of an enterpr~.se, sector
and the national economy as a whole) and in various information retrieval sysCems.
Here too there is usually a number of small ~abs with few links to each other, but
operating with a common data bank. But the designer of an ASU [automated manage-
ment syste~nJ or.information retriev~l system must, of course, be interested in
, the total throughput of computir~g resourc.es since the specific set of jobs in his
system must be executed within specific time intervals (somet3mes within several
. hours, or several days or several weeks).
We encounter a fundamentally different situation in automated process control sys-
tems, in solving major scieneific problems and in other cases. High throughput ~f
~ compyting resources is needed in this case to obtain within a brief time a solution
to one, but rather massive, problem. It seeins to us in many cases neither the com-
puter system designers, nor those expecting to use the systems for the purposes in-
dicated cl=arly understand that the same computer system cannot achieve identical
throughput in solving major problems of different classes and that there has to be
a specific correspondence between the specific problem properties and the computing
- system structure for computing system capabilities to be used reasonably effi-
cieiitly.
In this book, when we speak of high-throughput computing systems, basically we have
in mind precisely the latter situation (precise definitions ot actual user through-
put and user efficiency of a computing system are given in section 1.Y.2.).
Chapters 1 and 2 are devoted to a detailed consideration of precisely these points.
Singled out as a result is the type of synchronous computing systems wnich poten-
tially can achieve the maximum in actual user throughput. Naturally, this through-
put can be implemented when a cerrtain class of problems is run (i.e. problems
- having certain properties), but th3s class is rather broad and includes rather
najor problems.
Chapters 3-6 are devoted to an examination of the most compleac technical questions
that arise in building these systems--development of synchronous methods of execu-
ting arithmetic and logic operations, i.e. methods tt?at provide for minimal time
in executing an operation irrespective of the operands on which it is executed.
The importance of these chapters is considerably broader than could be deduced from
the precedin~,, sin~e the use of synchronous methods for executing operations is
necessary even when building conventional (aingle-procesaor) control machines de-
sig*_~ed to operate in real time. In many cases, these synchronous methods of execu-
ting operations achieve higher speed than the well known asynchronous methods, and
it is expedient to apply them in developing any high-speed digital computer in
general,
Chapter 7 is intended for the reader who needs more background and who would like
to understand fully the content of the whole book. He should start reading the
book precisely from this chapter which contai~s elementary information an the
principles of computer teehnology.
2
FOR UFFICIAL US~ ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00854R400404070026-2
~c)R l1FFICTAL l?S~ QNI~Y
Chapters 1 and 2 of ~this book were written by M. A. Kartsev and chapters 3-7 by
V. A. Brik.
The authors will be grateful to readers for comments made on the book's content.
' V. A. Brik, M. A. Kartsev
- 4. High-Speed Synchronous Multipliers
Multiplication has to be performed to solve the ma~ority of computing problem~.
Problems that include division can often be solved by using multiplication, addition
and subtraction. Division can be performed, for example, by using multiplication
and tables of inverse values stored in memory. There are many m~thods �or '~getting
azound" division, i.e. accomplishing it without special-purpose devices designed
for this.
Multiplication cannot be "avoided." The only way to avoid direct calculation of a
product is to use multiplication tables. However, employing this method in ma-
chines with parallel operation requires a large amount of storage. ,Any software
method of multiplication requires repeated addition which cannot be perfcrmed as
quickly as multip~ication is performed by uaing higli-apeed hardware methods.~ There-
fore, the rapid hardware method for performing multiplication is a very common
approach in designing the arithmetic unit.
~ All known synchronc~us methods for speeding up multiplicarion reduce essentfally to
th~ separate or complex use of the followi~ng three methods:
1. Reducing the time needed for performing addition of partial pioducfis~ i.~e. the .
products of the nultiplicand by the individual digits or groups of digits of the
multiplier.
2. Reducing the number of partial products by using multiplicand multiples formed
in advance.
3. Using subtraction in multiplication which permits reducing the number of
additional adders needed to form multiples of the multiplicand.
This classification is based on logical and mathanatical ideas, the implementation
of which leads to raising speed. Each of these directions is anbodied in the group
of inethods for sp~eding up multiplication, the hardware solutions of which can
differ considerably from each other.
In this chapter, the basic synchronous methods for speeding up execution of multi-
plication are discussed.
4.1. Decreasing the Time for Adding Partial Products
The time for ~dding all the partial products can be reduc~d by three methods:
speeding up the procedure.for adding the next partial product to the sum of the
preceding par~ial products; starting the addition of the following partial product
prior to completion of the addition of the preceding partial product; and fina3~ly,
building circuits that add the running sum of partial products at once to several
successive partial products.
_ 3
FOR OFFICIAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
The main implementation of the first method is the use of a fast adder for adding
the next partial product to the sum of the preceding. If onQ deaires, this group
of inethods may also include the use of the well known multiplying circuits that
ov~rlap addition with a shift of the multiplicand (fig. 7.7.1, b and d[not repro-
ducedJ).
The second method is implemented in the method of multiplying in which the so-called
carry save adder is used (1 and section 4.3.2.]. The idea of this method consists
in fox~ing the running sum of the next partial product with the sum of the preceding
partial products in the form of a two-digit code, i.e. i~i the form of two numbers.
In the extreme case, one of these two numb~rs is formed from the step-by-step sums
s, and the other from the s*.ep-by-step carries e. The principle of operation o�
this de~ice is illustrated by the simplified structural diagram shown in fig. 4.1.1.
KeY; � ~S)
1. Rgl register 1 1 t P~z
2. Rg2 register 2
3. Rg3 register 3 ~M
4. Rg4 register 4 ~ s
5. P-- next partial product
6. Sm coincidence-type adder t3 P'4 ~
7. e step-by-step carries
8. s-- step-by-step sums Fig. 4.1.1
nr (5)
ICey : Pt i ~ Pz 2 ,
1. Rgl register 1
2. Rg2 register 2 cn~.
3. Rg3 register 3 7 e s ~(g)
4. Rg4 register 4
5. P1 partial prodact 1 ~y~
6, Sml adder 1 S 8
7. e-- step-by-step carries PrJ ~ oza ~
8. s step-by-step sums
9. P2 partial product 2 . ~"~s 11
~
10. Sm2 adder 2
11. Sm3 adder 3 5~8~
Fig. 4.1.2
During each cycle, the next partial product P is added to the sum of the preceding
partial products in the coincidence-type adder Sm. At the end of the cycle, the
values of the signals e and s are stored in registers Rg3 and Rg4, and at the start
of the next cycle are sent to registers Rgl and Rg2. A gain in speed is achieved
_ because there is no carry propagation procesa in the adder Sm; its ope~at3ng time in
this case is reduced, obviously, to the operating time of one one-dtgit adder.
With more economical (but also slower) versions, the entire adder is subdivided not
into individual digits, but into relatively quick q-digit (1 ~ q~ n) adders. In
doing so, the first of the two indicated numbers is formed from the outputs of the
sums of these adders, and the second number, containing q-fold fewer significant
digits, from the carry signals generated in the q-dig3t adders (by one signal for
each such adder).
4
FOR OFFICIAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
In any of these versions, after the two-digit code of the final product is obtained,
the two-digit code is translated into one-digit, i.e. conventional addition. This
may be done in a conventional parallel, or eten better--in a fast parallel, adder.
In the device shown in fig. 4.1.1, final addition may be performed in the adder Sm~
which must in this case, after running through al]. tk?e cycles of addition with the
partial products, be "retuned" from the mode for translating three-digit code (i.e.
three numbers) into two-digit--to the mode fdr translating t~ao-digit code into
one-digit. Instead of this, final addition may be performed in a separate adder,
which should be installed after registers Rg3 and Rg4. This ver.sion of the device
will be shown in fig. 4.1.2.
_ The third method for speeding up the process of add~,ng partial products assumes the
introduction of additional adders into the arithmeti~c unit. The number m of partial
- products that are simultaneously added to the running sum of partial products may
vary. A multiplication operation, in the process~ consists oF a ser.ies of cycles,
during each of which m new partial products are added. In doing so, the carry
storage method is also usually used and this speeds up the process further. In fig.
4.1.2, as an example, it is shown how another two (m = 2) partial products P1 and P2
can be added in each cycle to the running sum of partial products and with that the
sum formed in the f.orn? of two-digit code. Final addition in this scheme is done by
adder Sm3 wh~ch it is advisable to make fast.
- In the ultimate version, the multiplier composes at once all partial products.
Multiplication in this case is performed 3n one cycle. Multipliers of this type are
called simultaneous (array, synchronous, pyramidb of adders etc.). An analysis and
description of these devices are given in sections 4.4. and 6.3.
4.2. Preliminary Formation of Multiples of the 'riultiplicand
In this method of multiplication, the multiplier is subdivided into groups of q
digits each and may have yet another group containing less than q digits. Each
group of digits is decoded independently of the others as a conventional binary num-
ber. Considering by convention that the point is located at the right of the group,
in decoding there is generated one of the numbers (signals)
_ 0, 1, 2, 3, , 2q - 1
and used as the next partial product ~.:3 respectively one of the 2q multiples of the
multiplicand C, shifted the necessary way relative to the running sum of partial
products:
_ 0, 1C, 2C, 3C, (2q - 1)C.
The rule for decoding one group for the case q= 3 is shown in table 4.2.1.
Table 4.2.1.
Digits I Digits Digits Digits
of group Multiple~ of group Multiple o~ gr.~up rIultiple of group Multiple
I
000 0 O10 2C 100 4C 110 6C
J
- 001 1C O11 3C 101 SC 111 7C
5
FOR OFFZr,IAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
Thus, the individual digits of the group when decoded correspond to the natural
weight s : . - - -
Q digits �
^ 1
X X ' ' � / \
2y_~ 2a_:2y_� 2~ 2�
Let us designate the number of groups into which the multiplier is subdivided (or,
" which is the same, the number of partial producta) by m. The relationship between
n, q and m has the following form:
~ m= ] Q f (4.2.1) .
~
]d[ is the smallest integer not less than d.
Extreme cases of subdividing of the mul~tiplier into groups are the case when all
groups are "full" : ~ - - - - -
~
~ Q
-
X ~
I _ n~ - 1 m
(lengths of the groups are indicated at the top, their numbers at the bottom)~ and
the case when a group not full contains only one digit:
~ Q~ i~~
X. .X . X.. ~ ~
~ �
_ (the group not full is shown at the~left, but it can be in any other position of the
mu~tiplier). The remaining cases are intera~ediate between these two. What has been
said is illustrated by the double tnequality
(m-1) 9-}-1 3 M(n)-T , if
n~T~~~~n (T-1, 2, This means that the quantity of layers of simultaneous
multipliers when any n~3 can be determined, after selecting from the series of
numbers n~~~, n~l~, the two ad~acent numbers n~T~l~ and n~T~ that satisfy the
given inequality. Then M(n)=T. We will often use this technique later. If there
is known the time taui of operation of any i-th layer and if taul tau2= =tauM
tau, then the value of M defines the time of operation of the entire device from
the moment the n=n~ initial numbers (partial products) are fed to the inputs of the
first layer to the result of the two-digit code of the product; this time equals
M tau.
Corollary 9. If ni_1 n~T~, then ni n~T-1~. In fact, since in this case ni numbers
are contracted T-1 layers, then owing to corollary 8
ncT-s~~ n{ >,
If it would turn out that it{R ~ then when all no>n n,
would equal X, and M would equal some constant maximal value M(i.e. corollary 5
would not exist). ~ M
In the process~ n~"~ would equal infinity~ and n~ when M>1~l
would not exist (i.e. corollary 6 also would not exist).
30
. ,
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400074026-2
FOR OFFICIAL USE ONLY
Using corollary 8~ one can write the following system of inequalities:
rc~"'-~~ > ~M=2~ i=1, 2,..., M. ~4.4.2)
31
FOR OFFT~IAL USE ONLY
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
.
n~
4 f~'f
t i.-r
^ ,
_ 0 Y 4 n~_~
a) n~T~=2, 4, 8, 1G, 32, 64 ~j') n~T~=2~ 8, 4, 6, 9. 13
~ C) n~T>=2, 3, 7, 15, 35, 80 d�) n~T~=2, 3, 7, 22, 78, 288
r '
t1
k+1 ~..,f
.
:
.���1k+1
e) n~T~-2, 3, 7, 127,2~s~-1 n~r>=2, 3, 5, 9, 17, 32 (;~en
2,~a~_~ - I k=8)
r3~
. J?.....�.../
~ .
...~..il .
N 1N
8) ntr~~2, 8, 32, 128, 512, 2048
(wheii N=8)
Fig. 4.4.16. Type assembly: a) and b)--counters (3~ 2); c)--counter (7,3);
d)--counter (15, 4); e)--counter (k, m); f)--k-bit adder;
g)---translator N-~2. T= 0~ 1~ 2, 3, 4, 5.
32
, ,
APPROVED FOR RELEASE: 2007/02/09: CIA-RDP82-00850R000400070026-2

APPROVED FOR RELEASE: 2007/42/09: CIA-RDP82-00850R000400070026-2
FOR OFFICIAL USE ONLY
The sum of the two numbers obtained at the autputs of the last, M-th layer, as
stated earlier, equals the product of AC.
It can also be seen from (4.4.1) that with the given ni the maximal value of ~i~l
_ -
is 2ni. Therefore, from corolldry 9 .
ncT)=2n~T->> (T~1, 2,
Since n~~~=2, then n~1~=4, n~2~=8, i.e.
` n~M~=2M+i ~M=p, 1, (4.4.3)
The first six numbers of n~T~ are given in fig. 4.4.16, a.
Since for any n there is such T, that
- ncT-i)=2T