 |
Claims  |
|
|
What is claimed is:
1. In an array processor having a chaining channel for connection of
individual processing cells into a linear processing array:
a data storage register in each of said processing cells for storing data
for processing by said cell;
chaining channel input means in each of said processing cells for receiving
signals from a preceding cell;
chaining channel output means in each of said processing cells for
providing output signals to a succeeding processing cell;
control source for generating a plurality of control signals;
a plurality of flag flip-flops in each of said processing cells for storing
flag data in response to said control source, said flag data including
data representative of three mutually exclusive data transfer operations;
first gating means in each of said cells coupling said chaining channel
input means and said chaining channel output means, said first gating
means for decoding said flag data representative of said first data
transfer operation and for enabling said cell to transfer data from said
chaining channel input means to said chaining channel output means in
response to a first control signal from said control souce;
second gating means in each of said processing cells coupling said chaining
channel input means, said data storage register and said chaining channel
output means, said second gating means for decoding said flag data
representative of said second data transfer operation and for enabling
said cell to transfer data simultaneously from said chaining channel input
means to said data storage register and for enabling data transfer from
said data storage register to said chaining channel output means in
response to said first control signal from said control source; and
third gating means in each of said processing cells coupling said chaining
channel input means, said first flag flip-flops and said chaining channel
output means, said third gating means for decoding said flag data
representative of said third data transfer operation and for enabling said
cell to transfer data from said chaining channel input means to said first
flag flip-flop and for enabling data transfer from said first flag
flip-flop to said chaining channel output means in response to said first
control signal from said control source.
2. The processor according to claim 1 further comprising:
means coupled to each processing cells for providing individual flag data
representative of each of said three mutually exclusive data transfer
operations to three of said processing cells, respectively, said cells
responding to said first control signal and respectively providing said
three data transfer operations simultaneously.
3. The processor of claim 2 further comprising:
fourth gating means within each of said processing cells for decoding a
flag-spread word transfer state and for enabling a data present on the
chaining channel input of the cell with data present in a particular one
of said flag flip-flops is transferred to the chaining channel output of
said cell in response to a second control signal from said control source.
4. The processing array of claim 3 wherein the data transferred to the
chaining channel output of said cell is additionally transferred to said
flag flip-flop.
5. The processing array of claim 4 further comprising fifth gating means
for decoding an ORd relay word transfer state and for enabling a data
transfer operation wherein the logical OR of data present on the chaining
channel input to said cell with data present in said particular one of
said flag flip-flops is transferred to the chaining channel output of said
cell without affecting the data stored in said flag flip-flop.
6. In a linear array of processing cells providing isolation of a faulty
processing cell, each processing cell including means for detecting a
faulty processing cell, an input terminal coupled to a data storage
register for storing data to be operated thereon by the processing cell,
said data storage register being coupled to a flag register for storing
flag data to be used in the control of data transfer operations, and
including means for performing flag data transfer operations, from one to
another of said processing cells, each of said processing cells further
including output terminals for providing stored data, processed data and
flag data, each processing cell comprising:
principal chaining input means coupling the input terminal of a processing
cell to the output terminal of the preceding processing cell;
alternate chaining channel input means responsive to said means for
detecting a faulty processing cell, coupling the input terminal of a
processing cell to the output terminal of a processing cell further
removed along said linear processing array than said preceding processing
cell for inactivating the output terminal of a faulty processing cell by
selecting the output terminal of a processing cell further removed along
said linear array; and
chain channel input select logic individual to each of said processing
cells for selecting between said principal chain input means and said
alternate chaining channel input means.
7. The processing array of claim 6 wherein said processing array further
comprises:
a common output channel coupled to the output terminals of each of said
processing cells; and
means for disabling the output from each of cells coupled to said common
output channel.
8. An array processor having means for generating a plurality of control
signals, comprising:
a plurality of data processing cells;
means coupling adjacent processing cells together for transferring data
therebetween;
multi-bit data register in each of said processing cells;
a plurality of common control lines for receiving said control signals
coupled to each of said processing cells;
a plurality of common input/output lines coupled to each of said processing
cells;
arithmetic means in each of said processing cells coupled to respective
data registers and to said common input/output lines; and
a flag register in each of said processing cells for controlling data flow
and data processing within each respective cell, said flag register having
a plurality of flag bit stores including:
a first flag bit store means for holding data including control data, said
flag bit store being selectively coupled to said adjacent processing cell
by said coupling means in response to a first control signal;
a second flag bit store means coupled to said arithmetic means for
selectively recording binary output data resulting from data processing
within said processing cell;
a third flag bit store means responsive to a second control signal, and
coupled to said multi-bit data register, and including means for enabling
transfer of input signals to said data register from at least one of said
common input/output lines;
a fourth flag bit store means responsive to a third control signal, coupled
to said multi-bit data register, and including means for selectively
enabling data transfer from said data register to another one of said
common input/output lines.
9. The array processor of claim 8 further comprising:
first gating means, responsive to a fourth control signal on said common
control lines for enabling the transfer of the flag bit data from said
first flag bit store to another of said stores; and
second gating means responsive to a fifth control signal for enabling the
transfer to said first flag bit store of the flag bit data contained in
another one of said stores.
10. The array processor of claim 8 wherein each of said data processing
cells further comprises:
third gating means, responsive to a sixth control signal on said common
control lines, for directly setting the flag bit in a particular one of
said flag bit stores.
11. The array processor of claim 8 wherein each of said data processing
cells further comprises:
fourth gating means responsive to a seventh control signal on said common
lines, for circularly shifting flag bit data among a plurality of said
flag bit stores.
12. The array processor of claim 8 wherein each of said data processing
cells further comprises:
fifth gating means, responsive to a eighth control signal on said common
control lines, for forming a logical combination of flag bit data
contained in predetermined ones of said stores and for transferring said
logical combination to a selected one of said stores.
13. The array processor of claim 12 wherein said logical combination
includes an AND function.
14. The array processor of claim 12 wherein said logical combination
includes an OR function.
15. In a linear array processor having a plurality of processing cells
being responsive to common control signals, each processing cell having
arithmetic means for processing data, each processing cell comprising:
a data storage register;
a flag register coupled to said data storage register;
a chaining channel for connecting said processing cells into a linear
array;
first gating means responsive to said common control signals and to data
stored in a respective processing cell's flag register identifying data
stored in said data storage register as multiplier data or as multiplicand
data or as a product data or as data to be ignored during a multiply
operation;
second gating means for enabling transfer of multiplier data from another
processing cell on said chaining channel to a processing cell having
partial product data stored therein;
said arithmetic means for forming successive partial products by
conditionally adding multiplicand data to a partial product data;
third gating means coupled to said arithmetic means enabling transfer of
data to said storage register of said partial product data containing
processing cell.
16. The processing array of claim 15 further comprising:
means to shift data stored in the data storage shift register of a partial
product cell with respect to multiplicand data stored in the data storage
register of a multiplicand cell, whereby multiplication by said arithmetic
means may be implemented.
17. In a linear array processor having a plurality of processing cells
being responsive to common control signals, each processing cell having
arithmetic means for processing data, each processing cell comprising:
a data storage register;
a flat register coupled to said data storage register;
a chaining channel for connecting said processing cells into a linear
array;
first gating means responsive to said common control signals and to data
stored in a respective processing cell's flag register identifying data
stored in said data storage register as divisor data as dividend remainder
data or as quotient data or as data to be ignored during a divide
operation;
second gating means for enabling transfer of divisor data from another
processing cell on said chaining channel to a processing cell having
dividend/remainder data stored therein;
said arithmetic means for forming a revised remainder by adding or
subtracting divisor data from dividend/remainder data;
third gating means coupled to said arithmetic means for enabling transfer
of said revised remainder data on said chaining channel to a processing
cell containing quotient data and for forming successively revised
quotient data therefrom and storing the result in the data register of
said quotient data containing processing cell. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
TABLES OF CONTENTS
Cooperative-word linear array parallel processor
Field of the invention
Summary of the invention
Background
1. The Solomon machine
2. PEPE
3. the Holland machine
4. The Various Associative Processors
Objects
The Present Invention
Brief description of the drawings
Detailed description of a preferred embodiment
Introduction
1. Processor Architecture
2. The Individual Processing Cell
Functional Description of the Various Modes
1. Data and Control Lines
2. Fault Isolation Mode
3. Flag Shift Mode
4. Word Cycle Mode
Detailed Functional Description of the Individual Cell
1. Data Routing
(TABLE 1)
2. intra-Cell Control Lines
3. Auxiliary Input Line
4. Arithmetic and Logical Operations
A. Match
B. Approximate Match
C. Greater Than or Equal
D. Less Than
E. Exclusive-OR
f. Add
G. Subtract
H. Multiply and Divide
H1. Multiply
(TABLE 2)
h2. Divide
I. Square Root
Detailed Logical Description of the Individual Cell
1. Chain In Selection
2. Data Shift Register
3. Chain Out
4. Common Output
5. Adder
6. Miscellaneous Arithmetic Logic
7. Flag Shift Operations
8. Stored Control Lines
9. Disable
Basic Programming Considerations
1. Chaining Channel
A. Interword Data Exchange Operations
B. Word Selective Data Shifting
C. Some Uses of the Chaining Channel
2. Other Data Communication Channels
3. Match and Short Arithmetic Operations
(TABLE 3)
4. extended Arithmetic Operations
5. Effective Self-Repair
6. Processing Control and Setup
a. Processing Modes
b. Simultaneous Operations
c. Processing Speed
(TABLE 4)
Programming Examples
1. Parallel Arithmetic Computations
(TABLE 5)
2. symbol String Searching
FIELD OF THE INVENTION
This invention relates generally to data processing machines, and in
particular to "highly-parallel" processors, as distinguished from
conventional "von Neumann" machines. A highly-parallel processor is a
machine which can perform many separate operations simultaneously or else
can perform the same operation simultaneously on many data or sets of
data. In addition, this parallelism is of a high order, say at least fifty
or a hundred. Thus conventional "multi-processing" machines cannot be
considered as highly-parallel in the sense defined here.
SUMMARY OF THE INVENTION
Background
There are numerous examples of highly-parallel machines, many of which are
just paper designs. Among the prior art highly-parallel machines are the
following:
1. The Solomon Machine
This is a set of processors connected as a two-dimensional array. All of
the processors operate under central control and, in addition, each
processor can communicate with its four nearest neighbors via the array
interface. The ILLIAC-IV is an example of a Solomon machine. Solomon
machines are extremely fast on matrix-type operations. However, because of
their two-dimensional architecture, such machines are not readily
adaptable to the type of large-scale integration (LSI) wherein multiple
cells are on a single wafer; furthermore, a failure in a single processor
renders all the other processors in the same row and column relatively
useless.
2. PEPE, the Parallel-Element Processing Ensemble.
This machine is also a fixed set of processors with central control. There
is no array interface as on the Solomon machine. However, PEPE contains an
associative memory whose parts are assigned to the individual processors.
Operations on this memory serve to determine which of the processors will
perform each (centrally directed) operation. PEPE machines are designed to
be extremely fast in applications involving the application of the same
algorithm to many sets of data simultaneously. The principal potential use
of a PEPE machine would appear to be as a special purpose peripheral in a
large system, inasmuch as it lacks the pre-configuration flexibility
required to efficiently perform unrelated tasks concurrently.
3. The Holland Machine
This machine consists of a great many very simple (and identical)
processing elements connected as a two-dimensional array. Each element
contains only a single data item or a single instruction. Unlike the
machines just described, control is not central in the Holland machine.
Instead, the individual elements can initiate and control their own
operations (that is, those elements which happen to contain instructions).
Thus the Holland machine is capable of performing many different processes
(and operating on many different sets of data) simultaneously, with each
instruction-containing element processing its own data and passing on its
control to another element independently of other operations being
performed in the machine. The communication of data and control is via the
array linkage. No large Holland machine has been built. These machines
suffer from being extremely difficult to program, and from the fact that
the array linkage is inadequate for handling the complexity of operations
of which the machine is capable without serious conflicts in the
communication of data and control.
4. The Various Associative Processors
These machines all operate parallel-by-word and have logic distributed at
every word position (and often at every bit position as well). The control
is central, and there is always one and only one common operand in every
parallel operation. That is, the parallelism in an associative processor
is always between the single operand and the contents, or partial contents
of a subset of the memory words. Many associative processors also have the
capability of performing arithmetic and logical operations on subsets of
the same memory word.
Objects
Accordingly, a principal object of the present invention is to provide a
greater degree of parallelism than is to be found in prior art
multi-processing machines.
Another related object is to permit different types of operations to be
executed simultaneously; for example, arithmetic, data input and data
output operations.
Yet another object of the present invention is to provide for more
efficient parallel processing of data by permitting arguments to come
either from a common input or from neighboring words.
Still another object of the present invention is to provide a highly
parallel data processor having a flexible record size with field
boundaries being dynamically variable.
A further, related object is to provide a highly parallel processor wherein
memory can be divided into various sized regions for the various data
dependent upon the nature of the problem being solved.
An overall objective of the present invention is to provide a cooperative
word parallel processor which combines content addressable memory data
storage with a capability for efficient parallel arithmetic and logic
operations on the data.
It is a specific object of the present invention to lower the cost of array
processors by providing a cellular architecture that can be fabricated as
linear arrays on full LSI wafers using P-MOS or other state-of-the-art
semiconductor technology with 2-layer metalization.
The Present Invention
These and other objectives are satisfied by a "cooperative word"
highly-parallel processor comprising a linear array of logically identical
memory cells constructed in accordance with the present invention, the
individual cell having no individual hardward-addressing logic as such but
addressable by its contents or by means of its relative position on a
chaining channel which orders the words into a linear array.
Such a cooperative word processor has several communication channels. These
are - in the embodiment described in detail below - the Common Input
channel, the Chaining, the Auxiliary Input, and the Common Output
channels. Each of these channels may be bit-serial in operation. The
Common channel is the communication channel over which information in an
external compare register is compared simultaneously with the contents of
selected words in the memory, added to selected words, or otherwise used
as a common operand in arithmetic operations.
The Chaining channel permits information to be transferred from
word-to-word within the memory. There is only one such channel and it may
even be unidirectonal. Nevertheless, it permits such operations as
pairwise parallel arithmetic and the copying of information from one word
into another word. Unlike the Common channel, the Chaining channel can
contain different information at each word position. Depending on the
setting of a Flag register provided as part of the individual word logic,
the information transferred to the next word via the Chaining channel may
be either the information on the Chaining channel from the previous word
or the contents of the word itself or control information (flag data) or
else results of logical or arithmetic operations between the input
information and the word itself.
The Auxiliary Input and the Common Output channels, like the Common Input
channel, each contain the same information at all word positions. They
respectively carry information that it input to or output from a set of
wrods selected by logic at each word position.
Since the four channels are logically independent to a very great extent,
information may be transmitted over all four of them simultaneously during
the simultaneous performance of several different tasks. For example,
input, output, and pairwise parallel addition may be performed at the same
time. Moreover, several different operations involving only the Chaining
channel can be performed simultaneously, provided that there are no
conflicts among the data on the Chaining channel (i.e., no overlapping
paths for different items of data).
The cooperative-word parallel processor of the present invention also has
the capability of an associative processor, so it could be termed an
associative processor. However, it has a great deal of additional logic
and also a much different emphasis as to the kind of parallel-by-word
("word-cooperative") associativity inherent in its logic; that is, it
permits pairwise parallel operations between words within the memory
independent of any single common operand. In actual programs written for
the machine, the associative-memory types of operations tend to play a
subsidiary role. The primary parallel operations are those which take
advantage of the ability to communicate internally between many pairs of
words in parallel and to operate on these pairs (hence, the term
"Cooperative-Word"). It shares with the Solomon machine and PEPE the
capability of operating on many sets of data simultaneously. However, it
has the advantage over those machines that the division of the memory into
regions for the individual data sets is determined by the software, rather
than by the number and size of the individual physical processing
elements. Thus, it can operate in parallel with equal efficiency,
regardless of the number or size of the data sets, the only limitation
being on the overall size of the single Cooperative-Word memory.
As with all associative memories, the logic resident in each cell can be
operated word-parallel. However, within each word of the preferred
embodiment disclosed, logic operates serial-by-bit, and data storage is
provided by a serial shift register. Each cell contains a bit-serial adder
for match-comparison and word arthimetic. Word inputs and outputs are all
single lines for bit-serial data transfer.
Operations within words are controlled by the interaction between the
common control lines and a plurality of individual Flag flip-flops which
are part of each individual cell. The Flags stored in these flip-flops
also activate processing within the particular cell and indicate the
results of processing operations, such as matches or overflow.
The logic of the individual word cells is partitioned so that different
types of operations can be executed in the processor simultaneously, even
in the same words. In the embodiment disclosed, one arithmetic or matching
operations, one data transfer operation on the chaining channel, one data
input operation, and one data output operation can all be performed
simultaneously during the same memory word cycle. This type of parallelism
is in addition to the parallelism of doing the same operation in many
different words simultaneously.
This processing approach is made practical by careful coordination of the
processor design to LSI (large scale integrated circuit) technology. The
basic processor may be built from many copies of the same LSI wafer. This
wafer is the basic building block. Each wafer, in turn, contains many
copies of the same basic word cell. Each word cell contains one word of
processor memory along with arithmetic and control logic. In the
embodiment described, only 18 conductive pads are needed per cell, and
there are only 20 leads per wafer. These characteristics promote low-cost
producibility. One layer of metallization defines the cells. A second
layer of metal is applied to interconnect all good cells on the wafer into
a linear array. All the good cells are used on each wafer because it is
not necessary to have the same number of good cells on each wafer.
The discretionary connection technique used with this second layer metal is
not the only means possible with the present invention for assuring high
manufacturing wafer yield and low cost processor maintainability. The
design of the individual processor cells is such that a software cell test
program can be run at any time in order to detect any bad cells.
Additional logic is included with each cell so that bad cells may be
turned "off" (that is, bypassed and its output disabled) under program
control. A turned-off cell does not interfere with the proper operation of
other good cells. Although for normal operation each word uses only one
chaining input, in the interest of maintainability, the logic of the
preferred embodiment disclosed provides at least two. Data is supplied
from the word two back as well as being provided from the previous word.
This provides an alternative to the previous word in case that word's
chaining logic should fail. A Fault Isolation operation changes Chaining
channel inputs in certain words. As long as a few extra words are provided
initially, hardware memory repairs should not be needed.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates in block diagram form the major components of a
cooperative word linear array processor in accordance with the present
invention.
FIG. 2, comprising FIGS. 2a and 2b, illustrates in functional block diagram
form the major components of a processing cell constructed in accordance
with the present invention, with FIG. 2a showing possible paths of data
flow during a "Word Cycle" operation, while FIG. 2b shows data flow during
a Flag Shift operation.
FIG. 3, comprising FIGS. 3a through 3h (which are to be combined into a
single large figure), presents a detailed logic diagram for an individual
processing cell for performing the functions delineated in FIG. 2 and the
associated functional description.
FIGS. 4 through 17 illustrate the flow of data from one cell to another
during typical data processing sequences.
DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT
Introduction
1. Processor Architecture
Referring now with particularity FIG. 1 wherein the basic architecture of
the processor is illustrated, it may be seen that the processing array 10
comprises a linear array of cells 12, each cell comprising data word
storage together with associated arithmetic and control logic (thereby
forming in essence an array of individual microprocessors).
Each associative memory cell consists of a 64-bit data Shift Register for
data storage, seven Flag flip-flops for controlling operations to be
performed (or not performed) within the cell, a Disable flip-flop for
functionally disconnecting the cell in case a fault is detected in the
cell, a Chaining Input Select flip-flop for bypassing the Channel Output
from a bad cell, a full adder for use in arithmetic and logical
operations, and miscellaneous control logic.
The individual cell, including the above-mentioned Data Shift Register,
flip-flops, and other logic will be described hereinafter in greater
detail with reference to the remaining figures.
The memory cells are serially arranged along a unidirectional communication
channel 14, known as the Chaining Channel. Although the figure illustrates
an array of only three cells, it should be noted that, in a typical
application, a much larger array may be utilized, perhaps on the order of
32,000 words or cells. The data in one cell can thus be transmitted down
the Chaining channel 14 to any other cell. Data can also be entered into a
cell by the Common Input and Auxiliary Input lines 18a and 18b, which are
external lines common to all cells, Alternate Chaining Input 14a' and
Alternate Chaining Output 14b' are also provided in the interest of
reliability and repairability, particularly when more than one cell is
physically located on the same LSI wafer.
External to the processing array 10 are an input/output interface 22
through which external inputs and outputs are passed. Interface 22 is
connected by a data bus 24a and 24b to a Common Data Control buffer 26
which also receives stored data and instruction words from external
program memory 28. Not shown in FIG. 1 are the power supply and clock
lines used to power the individual cells.
2. The Individual Processing Cell
FIGS. 2a and 2b taken together illustrate possible data flow paths within
an individual cell. It should be noted that the various Flags and
processing and other logic blocks in these figures are duplicated on each
figure but that the data paths indicated are different. This has been done
in the interest of clarity and is particularly relevant to a thorough
understanding of the present invention, inasmuch as the processor has two
basic modes of operation - a "Word Cycle" mode and a "Flag Shift" mode.
Data flow within the Word Cycle mode is illustrated in FIG. 2a, and in
this figure, a path used only in the Flag Shift mode is not indicated
thereon, but rather, is indicated in FIG. 2b, wherein paths used only in
the Word Cycle mode are not indicated. In the preferred embodiment
disclosed, the processor is also provided with a "Fault Isolation" mode,
but the data flow for that mode is relatively uncomplicated and, in any
event, will become clear from the text and figures which follow.
Referring now to FIG. 2a wherein Word Cycle mode data flow is illustrated,
it may be seen that the individual word processing cell 12 of FIG. 1 is
provided with a Flag register 30 comprising a First or Head Flag 31 which
is utilized in the transfer of data between cells and also may be used as
a temporary store for data. Second Flag 32 and Third Flag 33 together are
used in the generation of a local "Word State" control signal which may be
different in different cells. It should be noted that "control signal"
paths, as distinct from "data" paths, have not been illustrated in these
FIGS. 2a and 2b, but may be found in FIG. 3. Fourth Flag 34 enables
arithmetic operations. Fifth Flag 35 identifies arguments for Multiply,
Divide, and Square Root operations. The Fourth and Fifth Flags may also
function as temporary storage of the results of arithmetic and logical
operations performed by the processing, such as Match, Approximate Match,
and Arithmetic overflow. Sixth Flag 36 may enable Auxiliary Input data to
the Shift Register, while Seventh Flag 37 may enable data to be output
from that cell onto the Common Output channel. Each cell is also provided
with Arithmetic Input Select logic 40 which, in response to local and
global control signals, selects input data either from the Common Input
18a or from the Chaining Input 14a via Chain Input Select logic 42 which
is responsive to the Fault Isolation logic 44 when the processor is in the
Fault Isolation mode. Shift Register 46 is normally a 64-bit shift
register, but, in the detailed logic which is discussed hereinafter with
reference to FIG. 3, may effectively be modified to a 65- or 63-bit shift
register configuration in order to perform left or right shifts (with
respect to other cells) in division or multiplication, respectively. The
input to this Shift Register is selected by Shift Register Input logic 48
which selects input from First Flag 31, from an Adder 50, from the
Chaining Input via logic 42, and from Auxiliary Input 18b, depending on
the setting of the Sixth Flag and also depending on the global control
signals 16 and the local word state determined by Word State logic 51
(which, as has been noted, is in turn responsive to the states of the
Second and Third Flags). In order to conserve the number of external
control lines required, a few global controls may previously be input via
Auxiliary Input 18b and Common Input 18a to a Word Cycle Control register
52 during a Flag Shift mode operation, and then the data stored in this
register may be utilized as though it were a global control signal during
the Word Cycle operation. This time-sharing is possible, inasmuch as Flag
Shift mode requires fewer active control and input/output lines than does
Word Cycle mode.
Miscellaneous logic 54 accepts data from logic 40, as well as Adder 50, and
is utilized, for example, in Multiply and Divide operations, supplying its
output to Flag 1 for output to a neighboring cell utilizing the
cooperative Word nature of the processor. Flag 1 Input and Common Output
Select logic 56 selects output data to be output on Common Output line 20
either from Chaining Input line 14a (via Select logic 42) or from Shift
Register 46, while Chain Output logic 58 selects the data to be output on
Chaining Output 14b from either the Adder 50, or the Chaining Input Select
logic 42, or shift register 46.
Each cell is also provided with Flag 2 Input Select logic 60, which is
utilized only in the Flag Shift mode. It should be emphasized that the
present figure, as well as FIG. 2b which follows, does not illustrate the
flow of global control signals from control lines 16, of word state
signals output from Word State logic 50, or external control signals
stored in register 52 to the various logic portions of the cell. This
important aspect of the present invention is covered in detail below with
reference to FIG. 3 illustrating the detailed logic diagram for a
preferred embodiment of the present invention. That figure identifies all
significant control signal paths, as well as providing in logic diagram
form a preferred implementation for the various processing and control
logic, as well as data storage functions.
Referring now with greater particularity to FIG. 2b wherein data flow in
the Flag Shift mode is illustrated, it may be seen that Flag data is input
to the First Flag 31 from either Chaining Input 14a (via Input Select
logic 42), or from Flag 2, or from Flag 7, or from Flag 1 itself, as
determined by Flag 1 Input and Common Output Select logic 56. In the
particular embodiment disclosed in detail hereinafter, there is no way to
prevent changing Flag 1 while in the Flag Shift mode, inasmuch as the
contents of Flag 1 are inverted by logic 56, should they be selected as
input.
Data is input to the remainder of Flag register 30 via second Flag 32.
Flags 2 through 7 act as a shift register with the contents of Flag 2
being shifted to Flag 3 and so on down to the contents of Flag 6 being
shifted to Flag 7. The input to this shift register is determined by the
Flag 2 Input Select logic 60, which will select either Flag 1, or Flag 7,
or a logical combination thereof, or a constant, depending on the state of
the global control lines 16. Flag 2 Input Select logic 60 may also cause a
no-shift condition for Flags 2 through 7. The output of this shift
register (the contents of Flag 7) is lost, unless output logic 56 selects
it as the input to Flag 1, or input logic 60 selects it as an input to
Flag 7, in which case the Flag register performs as a 7-bit or 6-bit
circular shift register, respectively.
Functional Description of the Various Modes
As has been noted above, the word-cooperative memory in its preferred
embodiment disclosed herein can operate in three distinct modes: Word
Cycle, Flag Shift, and Fault Isolation. Word Cycle is the primary
operational mode of the memory and is used for performing the following
arithmetic and logical operations on the memory cell data:
Exact Match
Approximate Match
Greater Than or Equal Match
Less Than Match
Exclusive-OR
Add
Subtract
Multiply
Divide
Square Root
All of these operations except Square Root utilize two operands: the Shift
Register 46 data in a given cell 10, and either the Shift Register data in
another cell (via the Chaining channel 14) or the Common Input 18a data
(which will result in one operand being common to all cells). Only one
type of arithmetic or logical operation can be executed in the memory at
any given time, and it is executed in parallel in all cells which are to
participate in the operation. The function performed by any given cell in
an arithmetic or logical operation (e.g., whether a cell is to execute an
addition or is to supply data to another cell where an addition is being
performed) is dependent upon the states of various Flag flip-flops of Flag
register 30, in conjunction with the states of the global control lines 16
and register 52.
Flag Shift mode is used to change the states of the Flag flip-flops. The
primary function of Flag Shift is to get the Flag flip-flops in the
various cells set in the correct states for a subsequent Word Cycle
operation. Memory operation thus frequently consists of alternating
between Flag Shift and Word Cycle operations.
Fault Isolation mode is used for functionally disconnecting any cell in
which a fault is detected. This mode is normally used only upon power
turn-on, prior to the execution of operational programs.
1. Data and Control Lines
The various data control lines will now be discussed. In this regard, it
should be noted that, although FIGS. 1 and 2 are simplified block diagrams
wherein a plurality of discrete lines may have been indicated as a single
bus, in the detailed logic diagram of FIG. 3 (to be described in detail
hereinafter), each line has been individually shown as an input or output
to the relevant gate flip-flop or shift register. An effort has been made
to in | | |
