JPS626267B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to a data processing apparatus including a serial store having an arrangement for accessing a store at a plurality of nodes to perform data processing operations on data in different segments of the store.

In general, it is well known to handle defective memory locations in LSI (Large Scale Integration) RAM chips by providing a set of redundant memory cells that can be substituted for the defective cells. A disadvantage of this technique is that it requires that every chip be custom-fitted, such as using a laser to fuse the various links on the chip. hundreds of
Wafer scale integration (WSI) including LSI chips
There are difficult manufacturing issues in extending this technology to WSI in an attempt to manufacture memory. moreover,
Typical RAM chips require a 16-bit or more address bus. Extending such a bus to all wafer chips presents severe problems.

The solution according to our US Pat. No. 3,913,072 has the advantage that the wafers cannot be specially ordered. The throw line is simply set under software control. To avoid the problem of running extended buses all over the wafer (and the even more severe problem of switching buses such that slow lines are set), a serial, shift register configuration is employed. This creates other problems such as relatively slow access. A "first line" was added to allow quick commands to be sent to the individual segments of the shift register.

The above US patent describes a device of this kind in which the serial store constitutes a line called a slow line which is parallel to a fast access line. At each node, a switching device can connect the first line to itself with a segment of the store for reading and writing data. The node with which communication is established is selected by address matching. Part of the data on the fast line is an address field that is matched with an address field in the required segment of the store. Once a match is obtained, a read or write operation is performed between the data fields in the fast line of information and the data fields of the selected segment. Such devices allow serial stores to be addressed in a RAM manner such as core stores, which greatly reduces access time compared to traditional serial stores that are accessed only at one point. It is.

This address matching can take various forms, such as matching for identification, matching for identification of a unique part of an address field, or within certain constraints of one or more bits, e.g. in a "Don't Care" situation. It can take the form of matching. This can lead to the possibility of multiple matching if desired.

The aforementioned US patent specification also explains that it can be more than just reading and writing data. Data processing circuitry may be provided to perform processing operations on the stored data. For example, what is called a processing unit may be provided at each node for performing commanded operations along the fastline.
Each processing unit may be a simple arithmetic logic unit capable of performing small combinatorial basic sequential operations, such as appending fast line data to slow line data.

The problem with such devices is that the use of data processing equipment is insufficient because each elementary operation must be commanded along the fast line.

It is an object of the present invention to overcome the above-mentioned problems and to be able to efficiently and quickly replace the basic sequential operations of data storage with traditional computational operations, and which also digitally simulate physical situations. The object of the present invention is to provide an apparatus particularly suitable for performing data processing operations with respect to mapped images (described below).

An important advantage of the present invention is that the device can (though not necessarily) be constructed in the manner described in the aforementioned US patent specification, in which case the circuitry is not formed in a solely hard-wired manner. It is operatively formed in a manner that allows imperfect areas of the integrated circuit chip to be bypassed. This provides a high degree of operational reliability. For brevity,
Although this will not be explained again, it should be kept in mind when describing the present invention.

The present invention provides a series configuration in which a segment input terminal is connected to an input terminal of the shift register and an output terminal of the shift register is connected to a segment output terminal, and a segment input terminal is connected to a segment output terminal by a bypass line. A recirculating configuration in which the output terminals of the connected registers are connected to the register input terminals by feedback connections, and the segment input terminals are connected to the segment output terminals by bypass lines, and the segment input terminals and the register output terminals are connected to the input side of the arithmetic logic unit. a serial store of a plurality of segments having a shift register and switching logic operative to establish selected configurations including a processing arrangement connected to the input terminal of the register; , wherein the apparatus is configured to process words having a preliminary flag bit, each said segment further having two preliminary flag bits at the input terminal of the segment and at the output terminal of the register. When the two flag bits are different, the serial configuration is selected in response to
a logic circuit that selects a recirculation configuration when having a numerical value of 1 and converts the configuration from a recirculation configuration to a processing configuration in response to an instruction in a word entering a segment input terminal, and selects a processing operation to be performed by an arithmetic logic unit; and an instruction decoder.

The fundamental importance of such a device is, on the one hand, that the data processing operation itself does not require a fast line capable of performing read or write operations. Therefore, fast lines are not wasted and the overall operating speed of the device is greatly increased. In particular, separate parts of the serial store, also called slow lines, can be configured to operate simultaneously.

The reason that the fast line is not included in the data processing operation is that this operation involves recirculating information in a closed loop and information that is bypassing this recirculating information.

For convenience, the information in one segment will be considered to be one word, although it may include several words or bytes as is well known. in general,
The information contained in one word may include any or all address information (allowing addressing by segment contents), data, and instruction information. Instructions (perhaps better called microinstructions) that select an action for which a portion of at least one of these included words is to be performed.
form.

The main portion of the throw line is treated as if connected in a closed loop, and the main portion consists of a plurality of segments. Therefore, the main part of the slow line is assembled with data and instructions, treated as a closed loop, and the data and instructions circulate through the slow line so that the subroutines constituted by the instructions are executed autonomously. You can keep it. A segment and a main part may be described as a small loop and a large loop (subroutine), respectively. However, a small loop is only a closed loop when it is bypassed, and as mentioned, it is closed in the sense that it is functionally treated as an independent part of the throw line and autonomously executes the subroutine. It will be understood that the only thing that can be considered "closed" is that This is possible because the large loop is selectively bypassed so that the words within it pass through each other to contain processing operations.

For terminological convenience, a closed loop, whether a small loop or a large loop, can be said to be recirculating, whereas a loop that is not closed is a series loop, ie, the series portion of a slow line.

Exiting the large loop recirculation situation can be accomplished in a variety of ways. This can be done completely under external control. For example, after a central supervisory circuit has left sufficient time for the subroutines executed within it, the large loop can be brought into series, ie consisting of completely serial small loops. Alternatively, a central supervisory circuit can periodically check the subroutines to ensure they are complete. However, it is desirable for the large loop to flag onto the fast line when the subroutine completes.

The invention finds particular application outside the realm of normal digital data processing. A store can hold data that maps certain physical attributes of a field in two or more dimensions. Stores are inherently one-dimensional constructs, so for example, columns of data points are arranged serially within a store, à la television raster.
It is necessary to treat a multidimensional field as a multidimensional array of data points arranged in columns. Many situations arise in which data processing operations must be performed on data of adjacent data points within this array. Some such data points are adjacent within the store (ie, when in the same column), while other data points that are adjacent within the array are widely spaced within the store. The selective use of loops in recirculation and loops in series allows such data points to be combined from related processing operations.

The invention will be described in more detail by way of example with reference to the accompanying drawings, in which: FIG.

FIG. 1 shows a central supervisory circuit (CSC) 10 that controls the operation of the combined serial store and data processing system via a fast data line 13. The serial store, also called slow data line 12, takes the form of a long period recirculating shift register that circulates from CSC 10 back to CSC. The fast data line 13 also circulates from the CSC 10 back to the CSC via a plurality of nodes described below to which the fast line effectively has simultaneous access.

The configuration of CSC 10 does not form part of the invention. It is necessary to send instructions and data to the store and processing system to manipulate, store, and receive data that has been processed and read as described below. It is only necessary to monitor that the information from the CSC must be sent at the correct time to interact with the series circuit. This is a well-known requirement when interacting with series circuits. In fact, the entire timing is controlled from CSC 10, which sends a two-phase clock signal on line 14 for a serial store in the form of a long-period shift register (see above-cited US patent specification) in which the information is clocked. Ru.

Referring now to FIG. 2, slow line 12 can be viewed as a closed shift register (by virtue of the recirculating connection via CSC 10) around which information is clocked in the direction of arrow A. The shift register can be further considered to be divided into a plurality of large loops 11, each of which is treated as an independent structure. Figure 2 must be viewed as frozen in time, and the large loop actually all circulates around the shift register as indicated by arrow B. Furthermore, the large loop can vary in length;
The way a shift register is partitioned into large loops is variable; large loops can be divided and combined to change the pattern of large loops into which the shift register is partitioned.

Structurally, the slow line 12 is connected to the node 16
A number of segments or small loops 15 extending between
(Figure 3) One large loop includes a plurality of small loops 15, each small loop capable of storing long words, for example 40 bits or substantially more.

FIG. 3 shows a single small loop extending between node 16 (slow line) and node 17 (fast line). Fastline 13 and slowline 12 are clocked from clock line 14 (FIG. 1) and enter a 1-bit buffer stage 18 whose output is connected to routing logic 33 having the following inputs and outputs: That is, F _I = Fastline input S _I = Slow line input F _O = Fast line output S _O = Slow line output R _I = Register input R _O = Register output A _I (1) & AI (2) = Arithmetic logic unit ( ALU) input A _O = arithmetic logic unit (ALU) output A shift register 15 is connected between R _I and R _O ,
Configure slow line segments. ALU3
6 is connected between AI(1), AI(2) and A _O.

The routing logic 33 receives the micro-operation signal M
is a collection of gate devices such as _those conventionally provided in digital computers to control the path of data under the control of The principal form of routing logic 33 is described with respect to FIG. 4 and the like.

FIG. 4 shows FI connected to F _O and _the slow line is completed between S _I and S _O via resistor 15. This is a series configuration.

FIG. 5 shows S _I connected to S _O by a bypass line 30, with shift register 15 closed to itself by a feedback line 31. This is a recirculating configuration.

FIG. 6 shows a configuration for writing from the fast line to the slow line, and FIG. 7 shows a configuration for reading from the slow line to the fast line. In FIG. 7, the slow line configuration can optionally be as in FIG. 5, ie, "read" in combination with "recirculation." In this case, non-destructive reading is performed, but the case of FIG. 7 shows destructive reading.

FIG. 8 shows a configuration for performing operations by the ALU regarding WORD1 given by S _I and WORD2 given by R _O. The resulting word is new because A _O is connected to S _O
It becomes WORD2.

Obviously other configurations, not shown, are also possible. It will be appreciated that, as is customary in computer design, during the course of a word time the configuration is changed by the M _O signal to provide different operations to different fields of the word being processed. In this regard, FIG. 9 shows a possible word format.
The lowest end is bit b ₀ , which is 1 for the instruction word on the first line. In the case of a slow line word, b ₀ is 1, indicating one word in the subroutine, and the next bit b ₁ is the command word (b ₁ =
4) or used to indicate a non-command word (b ₁ = 0), b ₁ is followed by an address field, a flag bit b for flagging an address match.
_n , followed by instruction field, data field, and flag bit b _o for flagging the overflow bit. The configuration of FIG. 8 is set up, for example, only during the data field.

Returning to FIG. 3, instruction detector 19 is timed on line 20 from time slot counter 21 to test for bits b ₀ and b ₁ in time slots t ₀ and t ₁ . These bits can be denoted F _Ib0 , S _Ib0 , etc. to indicate which word they belong to. Command detector 19 provides control signals to command buffer 23 and address comparator 26 on line 22, which control signals are timed by time slot counter 21. If _FIb0 is one, the signal on line 22 gates the command field of _FI to command buffer 23. Fastline instructions thus act as interrupts and take precedence over all slowline instructions in all segments of the slowline.
All sections enter the recirculating configuration of FIG.

The buffered instructions are sent to a well-known instruction decoder 24.
It is decrypted by The decoded instructions are gated with a timing waveform from the time slot counter 21 which operates at the bit rate (or a multiple thereof). This gating action is performed by the routing logic 33 and
This takes place in the micro-operating logic 25 which provides the Mo signal that controls the ALU 36 companion.

Buffered instructions are followed only by the addressed segment. The addressed segment is the one whose address field in Ro matches the address field in _FI . This matching is detected by a serial address comparator 26 which is enabled only while in the address field by a signal on line 22 from counter 21. If F _Ib0
If =1, comparator 26 is commanded to compare the address fields of F _I and R _P . When address comparator 26 detects a match, it provides a signal on line 27 to cause decoder 24 to decode and thus follow the command. All segments without address matching remain in the recirculating configuration of the apparatus of FIG. 5 until the end of this word. Segments with this address matching follow the decoded instructions. It will be appreciated that the control provided by address matching may be provided in the logic 33 itself, or in the logic 25, or in the decoder 24 as shown. In any case, the associated Mo signal is only valid in the logic 33 of the addressed segment. For example, if the instruction is WRITE, the Mo signal changes the format of the addressed segment from that of Figure 5 to that of Figure 6 during this data field so that the instruction data of FI is written to _{R I.} It can be done.

The method by which the processor is set up and executed is as follows. The program itself, consisting of a plurality of subroutines, each subroutine consisting of a plurality of words, is entered into the slow line (from well-known peripheral input devices) by a central supervisory circuit. Each word contains at least its address. A certain word has a 1 in the instruction field.
There are three instructions, and b ₁ =1. Some words are b ₀
=1. At this stage, the word may or may not contain data. In one typical situation, a program is entered with no data. This data is inserted into the data field of the appropriate word by the addressed WRITE command on the first line. Additional data during processing can also be inserted in the same way. Intermediate and final result data can be extracted during or at the end of processing by fastline addressed READ commands.

As mentioned above, the program is organized into multiple subroutines, each of which occupies a large loop. 10th
The figure shows part of the throw line. Each small square represents one segment of the slow line (Figure 3), and a ``0'' or ``1'' indicates that bit.
b Indicates whether ₀ is 0 or 1. Each subroutine consists of a plurality of words, all with b ₀ =1. This subroutine is divided by words with b ₀ =0.

Once each subroutine exists on the slow line, it can execute itself independently of the instructions on the fast line and from other subroutines. To illustrate the principle, FIG. 11 shows the simple case of a subroutine of only three words A, B, and C.
This situation begins with C as a backword following a word with b ₀ =0, as shown in a. Because of this relationship, the configuration of FIG. 11b is taken so that C passes through B and A to reach the situation of FIG. 11c.
In FIG. 11b, closed loop R shows a segment in the recirculation configuration of FIG. 5, and this closed loop is bypassed by connection 30 as in FIG. The loop S connected to the throw line 12 represents a segment in the series configuration of FIG.

When word C passes through words B and A, the command can be implemented as commanded by C's command field, and if C has b ₁ =1, as described further below. Next, take the configuration shown in Figure 11d, and
The state shown in Figure 1e is reached. This procedure continues until stopped by a jump condition or an interrupt from the first line. Thus, within the large loop, as progressing in the slow line, the last word repeatedly jumps to the previous position, and processing operations can be performed as this word passes other words. The large loop operates in this manner several complete cycles to repeatedly execute the subroutine, if necessary.

The configurations of Figures 11b and 11d are set up completely automatically. For this purpose, the instruction detector 19 (third
Figure 1) has another circuit as shown in Figure 12. This instruction detector 19 provides an enable signal F _Ib0 =0 when there is no instruction on the first line. Under these circumstances, the exclusive OR gate 40 and the AND gate 41, responsive to b ₀ of S _I and b ₀ of RO, provide a signal S configured to ensure a series configuration by corresponding control to the routing logic 33. give. Thus, whenever adjacent words have b ₀ =0 and b ₀ =1 or vice versa, the segments with said words enter into the serial configuration of FIG. 4. On the other hand, F _Ib
AND gate 42 provides signal R when ₀ = 0, S _Ib0 = 1, ROb ₀ =1. This signal ensures the recirculation configuration of FIG. 5 and also causes the instruction buffer 23 (via line 22) to write from SI during this instruction field and places this instruction into buffer 23. This command is often treated as an _FI command. This means that this instruction is decoded and any address matching is made to correspond to it.

For this purpose, the instruction detector 19 must be configured such that S _Ib1 =1
(indicating a command) causes address comparator 26 to compare the limited address fields of R _O and S _I and generate a signal on line 27 if there is a match. This limited address field is one bit less than the full address field, so if R is correct, for example, b _{n -1} is omitted from the comparison. Every word has a separate and unique complete address, so that the word can be addressed individually by the first line, but within a subroutine there are pairs of words whose addresses differ by only b _{n -1.} do. Thus, a word results in one address matching when R is correct. Generally one such word, e.g. word C ₁ , is b ₁ =
1 command word. Other words, such as word A, are non-command words with b ₁ =0. If this command (the command at C) is, for example, ADD, then the configuration of FIG. 8 is established in this data field, the ALU 36 is commanded to ADD, and the data at A is added to the data at C.

For example, when word C passes over A, address matching can occur considering FIG. 11b. If so, match flag (line 27),
The combination of R, and C instruction fields (S _I in the A word segment) causes the properly timed M _O signal to set up the desired configuration of the logic 33 in the different fields of the word and to set up its repertoire of operations. The ALU 36 is commanded to perform the operation selected from.

The set basic commands consist of the following operations. That is, ADD = Add S _I to R _O , add the sum to R _I ADD1 = Add 1 to R _O , add the sum to R _{I INVERT = Invert R I ,} SHIFT _O to R _I = R _O by 1 bit delayed, shifted R _O to R _I EXCHANGE = S _I to R _I , R _O to S _O When ADD or ADD1 results in an overflow bit bo ₌ 1, this is the well-known conditional dive. It can be used like a command. b Jumping is performed by changing the ₀ bit and redividing the throw line. In particular, if a jump is used to change b ₀ from 1 to 0, the subroutine is split and the operation is therefore blocked. At this time, the fast line may be required to interfere so that different patterns of _b0 bits fall into the slow line. b ₀ is written within a word by addressing the previous word and timing the write operation to occur at bo ₊₁ , ie, b ₀ of the next word. or,
Jumping can be performed without interference from the first line by changing b ₀ from 0 to 1 and connecting to the next subroutine.

Due to the use of one address system, programming is clearly constrained. The operation takes place only between words whose address fields differ only in b _{n -1} . This restriction can be circumvented by adding additional operations to the repertoire described above. This operation consists of looking for the word as having flag b _n =1 (reserved by the previous operation) without address matching.
Flagged words are "addressed"
Appended to the data field of the directive.

Two very different cases of use of the invention will be briefly described. Much attention is currently being paid to data compression to facilitate storage of abstracts and the like on magnetic disks (due to computer-controlled access to information indicated by various keywords). Data compression is used to reduce storage requirements by looking for common character patterns (e.g. TION or ING) and combining them into one character (other than the normal alphabet).
This includes replacing by. When information is called, it is the shortest way to replace one character with its complete form. However, data compression involves searching for character patterns and is difficult to implement at high speed.

The apparatus described here is suitable for dealing with this problem. The encoded text to be compressed is placed in the slow line. The code of the character to be searched for is then used as a mask in other parts of the store, and the ALU is used to flag the character. For example, if we search for ING, all G's are flagged first. A search for N is then performed to remove the flag for G, and N is flagged only when the flag is present in the next character cell.
Furthermore, only I belonging to ING flagged in the same step is left. The flagged group can then be replaced by the corresponding single character (write operation). When all groups of characters are processed one after another, the text is such that all selected character groups are replaced by one type of character. Gaps that occur in the text can be filled between columns either in the store itself (by a small loop in a recirculating configuration without characters) or when reading from the store.

An entirely separate application concerns the provision of a digital analogue radar display of the amount of airway space available for use in collision avoidance systems for congested airway spaces, such as at major airports. The amount of airspace can be scanned by scanning the antenna for azimuth and altitude and by storing the radar returns for each line of sight relative to the range-bin. The airspace volume is thus effectively divided into a three-dimensional array of cells defined by azimuth, altitude, and range coordinates. Therefore, one cell is adjacent to 26 other cells. The intensities of the reflected components of all cells are converted into digital values and stored in the slow line or store of the device of the above-mentioned nature. The digital data represents strings, one indicating each viewing direction, and these strings are attached to each segment of the throw line or store, corresponding to one cell of the array.

To obtain an accurately updated display, perform the following operations. First, because the volume of airspace is repeatedly scanned, the value in each cell should be incremented in proportion to the strength of each reflection obtained for the scanned signal. Second, the numerical value in each cell should be decremented by a predetermined percentage of said numerical value, such that cells that are not incremented by the first operation have their values decreased. This somewhat reduces the intensity values of the reflections stored in the cells from the previous scan, and further reduces the values from the previous scan, so these cell values represent the tail of the wake. Third
Then, the value in each cell should be incremented by a predetermined percentage of the values in the 26 adjacent cells. The third operation is very well known in image processing operations, by which true parts of the image are re-emphasized and spurious parts resulting from noise are attenuated. Together these operations form a proper representation of a precise target in airspace, with moving targets depicted as "wakes" extending over several cells, while spurious "targets" arising from clutter and other noise average.

It is clear that the three operations listed above are themselves very simple arithmetic operations that can be easily implemented by ALU 36 using well-known techniques. However, the third operation requires interaction between each cell that appears in stores in sequentially adjacent but, with two exceptions, non-adjacent segments.
(The two exceptions are those that have the same orientation and height as the target cell, but are one step below the range of the target cell.)
For cells with one unit less range and one unit more range. These cells will have adjacent segments or small loops in one string).

The problem therefore lies in directing all segment pairs involved in the third operation to the ALU 36. It turns out that the device described above is very suitable for carrying this out. Said strings can be assigned to large loops, ie each large loop represents one radar scan in a given line of sight direction. By appropriately programming the recirculation and series configuration of small loops within all strings, operations involving adjacent segments can be performed. By suitably programming the large loop recirculation and series configurations as well, segments in different large loops can be brought together for the performance of each operation therebetween. The instructions controlling the arithmetic operations described above are placed in a slow line or store upon device setup;
Remains unchanged while data changes to maintain updated redisplay. Instructions are sent to the first line to control the composition of the segments to bring them together for processing.

For anti-collision purposes, the current contents of the throw line or store may be periodically copied to a portion of the throw line (second throw line) or store, for example every two seconds. The second slow line, or store, contains instructions that allow the processor to estimate the state of the store, ie, extend this state forward in time. These commands trace all "wakes" in the direction of their head by an amount proportional to their length.
The ``wake'' encountered indicates an aircraft on a collision course. The controller will take appropriate evasive action.

[Brief explanation of the drawing]

FIG. 1 is a block diagram of a computer embodying the invention, FIG. 2 is a block diagram of a slow line or store, FIG. 3 is a block diagram of one small loop, and FIGS. 4 through 8 are block diagrams of two different small loops. 9 is a diagram showing a word format, FIG. 10 is a diagram showing a subroutine format, FIG. 11 is a diagram showing a state in which a certain subroutine progresses along a slow line, and FIG. 12 is a diagram showing a subroutine. is 1
FIG. 6 is a diagram showing yet another portion of the two small loops. 10...Central supervisory circuit (CSC), 11...Large loop, 12...Slow (data) line, 13...
...Fast (data) line, 15...Small loop, 16, 17...Node, 18...Buffer stage, 19...Instruction detector, 24...Instruction decoder, 25...Micro operation logic, 26...Address comparator , 30... Bypass line, 3
3... Routing logic, 36... Arithmetic logic unit (ALU), 40, 41, 42... Logic circuit.

Claims (1)

[Claims] 1. A data processing device including a serial store consisting of a plurality of store segments, each store segment having a segment input terminal (SI), a segment output terminal (SO), and a shift register input terminal (RI). ) and shift register 1 with shift register output terminal (RO)
5. The switching logic circuit 3 includes an arithmetic logic unit (ALU 36) and a switching logic circuit 33 that operates to selectively establish a plurality of configurations.
3 is (a) a series configuration in which a segment input terminal (SI) is connected to a shift register input terminal (RI) and a shift register output terminal (RO) is connected to a segment output terminal (SO); and (b) a segment. a recirculating configuration in which the input terminal (SI) is connected to the segment output terminal (SO) by a bypass line 30 and the register output terminal (RO) is connected to the register input terminal (RI) by a feedback connection 31; c) A segment input terminal (SI) is connected to a segment output terminal (SO) by a bypass line 30, said segment input terminal (SI) and a register output terminal (RO).
is connected to an input of an arithmetic logic unit (ALU36), and an output of said arithmetic logic unit (ALU36) is connected to a register input terminal (RI), said data processing device further comprising a preliminary The store segment is configured to process words with flag bits, and each store segment further includes a preliminary flag bit (SIbo) at the segment input terminal (SI) and a register output terminal (RO).
selects the series configuration when the two flag bits (SIbo and RObo) are different, and selects the series configuration when the two flag bits (SIbo and RObo) both have predetermined values. logic circuit 40 for selecting a recirculation configuration;
41, 42 and segment input terminal (SI)
an instruction decoder for changing the configuration from a recirculating configuration to the processing configuration to select a processing operation to be performed by the arithmetic logic unit 36 in response to a word of instructions input to the data processing apparatus.