JPS595941B2 - Data array engineering - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION The present invention relates to an arithmetic processing device that performs arithmetic processing on a data array that constitutes a column of a plurality of elements.

Conventionally, operations on data arrays have had few general requirements and have been limited to specific operations.

For this reason, a dedicated device was used for the calculation. In that case, in order to process the calculation at high speed, the necessary calculation processing is divided into the minimum calculation units, and the calculation units are sequentially
That is, they are carried out in series. It had a so-called pipeline configuration. This arithmetic device was unable to perform other arithmetic operations than one predetermined arithmetic function. On the other hand, if you use a microprogram control device, you can perform various functions by replacing the program.
Full of flexibility. However, this operation involves reading data from the storage device, performing an operation on one minimum unit of operation, storing it once in the storage device, and performing the operation repeatedly. It takes a very long time to perform an operation that requires a plurality of minimum operation units.

SUMMARY OF THE INVENTION An object of the present invention is to provide a data array calculation device that is highly flexible and capable of performing high-speed calculations.

According to the invention, at least one readable/writable memory device is provided in which a data array is stored sequentially addressed with respect to its constituent elements.

Data is read out from this storage device by being specified by an address generated by an address generator, and the data is supplied to an arithmetic unit through a read bus. This arithmetic device has a pipeline configuration in which the read/write cycle of the storage device is the minimum arithmetic unit, and arithmetic processing is completed in multiples of the arithmetic unit. The calculation results from this calculation device are supplied as write data to the storage device via the write bus. The above read/write control is performed by a microprogram control device. Various programs can be rewritten to the microprogram control device so that various calculations can be performed. Further, a switch is inserted into the arithmetic device, and the arithmetic function can be changed by controlling the switch, or a plurality of arithmetic devices with different arithmetic functions are provided in advance. By setting the arithmetic function specification, storage device specification, etc. in the set-up register before starting the arithmetic operation, the microinstruction during the arithmetic operation can use the bits for specifying the arithmetic function and storage device. Don't use. Further, even if the flexibility of microinstructions is increased by configuring the arithmetic unit in a pipeline and providing appropriate control registers, the number of bits constituting the microinstructions can be made relatively small, so that the processing speed does not decrease. In addition, data is read from and written to the storage device every cycle, except until the pipeline in the arithmetic unit becomes clogged at the beginning and end of the operation, and until data is output from the pipeline. At each step of the pipeline, the minimum unit of operation is processed, and the data within it is moved one step. One calculation result is obtained each time the storage device is read, and high-speed processing is performed. Next, the data array arithmetic device according to the present invention will be explained in detail with reference to the drawings.

As shown in FIG. 1, in this example, the main memories MM, MM2, MM3 are capable of random access type reading and writing.
The data in write registers WR1-WR3 is written into these main memories MM, -MM3, respectively, and the data read from MM1-MM3 are stored in read registers RR1-RR3, respectively. Each address in the main memory devices MM, ~MM3 is divided into 16 bits on the left and right, and each element of the data array is stored in one address in each of these main memory devices, and each element is consecutive in the order of the array. The data is stored sequentially at the address. Addresses for these main memories MM1 to MM3 are generated by address generator MAU. In the address generator MAU, the data counter DC is incremented by 1 each time the main memory MM is read, and the output of the counter is directly added to the contents of the base address registers BARl and BAR2 in circuits 10 and 11 of FIG. 6, respectively. , or subtracted and provided as address information to main memories MM1 and MM2, and further to MM3 as necessary, through address shift registers ASR1 and ASR2, respectively.

Alternatively, as will be explained in detail later, the bit order of the output of the data counter DC is changed by the bit switching circuit 1X, and the base address is added or subtracted, and then the output is sent to the main memories MM, to MM3 through the address register ASR. (
MM, MM2, and MM3 are hereinafter referred to as MM). The output of the data counter DC and its bit order changed are selectively sent to the address correction circuit TW.
A is given to the main memory device MM3 through A. writing bus 1
2 and 13 are 32-bit buses, respectively, and the data on these buses is written to the address specified by the address generator MAU in the main memory devices MM1 to MM3, and is written to the specified address in the memory devices MM1 to MM3. The data read from the address is sent to the 32-bit outbus 14, 15, respectively.
transmitted to.

Buses 12 to 15 are switched by bus skiing unit BSU depending on whether the width of the data passing through them is 1 word (16 bits) or 2 words (32 bits). Furthermore, the switching unit BSS can select the bus to be connected between the bus and the storage device MM. A read/write cycle of the main memory device MM is taken as the minimum calculation unit, and one calculation function is completed by multiple times the calculation unit.

An arithmetic unit FALU having a so-called pipeline configuration is provided. A switch is inserted into this arithmetic device, and its control provides a plurality of arithmetic functions. Storage device MM, ~M
The data read from M3 is supplied to the arithmetic unit FALU via the bus 14 or 15, and is operated on by the arithmetic unit FALU, and the result is written to one of the memory devices MM, -MM3 via the bus 12 or 13. As will be understood from the following description, the data read from the memory device MM3 can also be directly supplied to the arithmetic unit FALU without passing through the read bus. Setting the calculation mode for what kind of calculation is to be performed in the calculation unit FALU, setting the initial address of the address generator MAU, that is, setting the base address registers BARl, BAR2, and storing the memory devices MMl to MM3.
A control program is stored in the microprogram control device CM from a processing device (not shown) through an interface device INT to the microprogram control device CM, which controls writing and reading of the data. Next, details of each part will be explained as an example of digitally Fourier transforming the signal f(t). First, regarding Fourier transformation, generally the signal f(t) can be Fourier transformed. T is the period of f(t) and is j--1. Fourier coefficient D

If the number of sampling points in period T is N, (2)
The formula can be approximated as follows.

By performing this calculation, any signal can be digitally developed into a Fourier series, that is, signal analysis can be performed digitally. However, performing the above calculations one by one requires a huge amount of calculations, and using a conventional electronic computer, the calculation time for 1024 sampling points is 1 hour, making it impractical. From this point, the values of the sampling points of the signal are appropriately combined, the sum and the weighted difference between the combinations are sequentially extracted, and the same process is repeated for the obtained data array to compare the results. It is known that digital Fourier transform can be performed with a small number of calculations. For example, U.S. Patent No. 351
No.7173DigitalPrOcessOrfOrP
erfOrmingfastFourierTrans
As the Fourier transform method described in fOrms, the Coolichi-Yukiy method and the Sunday Chikyuki method are known, and the latter will be explained here.

For example, as shown in FIG. 2, when N=16 in equation (3), the input array is X.

-X, 5 is a time series of each value of 16 points, and in the first stage, X. -X7 and X8 to X,5 are added to each other to obtain E. -E7 is obtained, X8~Xl is obtained from XO~X7
5 are respectively subtracted, and the corresponding trigonometric function values W are respectively subtracted. ~W7 is multiplied to E8~E
l5 is obtained. Wn is 2πX7exp(-j?).

E at 1G in the second stage.

- Sum D of each of E3 and E4 to E7. ~D3 is E again. -W to the corresponding value obtained by subtracting each of E4 to E7 from E3. ．． D4 to D7 are obtained by multiplying W2, W4, and W6, respectively. The same process is repeated thereafter, and the result of the fourth stage calculation is F. -F,5 is found, and by dividing these by N=16, the Fourier coefficient D(o) ~ D
O5) can be found. The above calculations are shown in FIG. A program necessary for this calculation is imported from the electronic computer to the microprogram control device CM through the interface device 1NT.

From this, the micro-programmed leg device CM will start,
Data necessary for the calculation is stored in the main memory from the electronic computer through the interface device 1NT. For example, X. -X7 is located at addresses O to 7 of the main memory device MMl;
~Xl. are respectively stored in addresses 8 to 15 of the main memory device MM2. From a practical standpoint, the trigonometric function value Wn is, for example, 2.
Values obtained when π is divided into 8192 points are stored in advance, and necessary values are extracted according to the number of sampling points. However, if the cosine and sine values of 1024 equally spaced points from O to π/4 are known, each of the other points will be one of these values or a value with a negative sign attached to it. Therefore, as shown in FIG. 4, in the main memory device MM3, COs (? )
are respectively memorized.

In this state, as shown in the preparation process in the flowchart of FIG. 5, initial address values are set in the base address registers BAR1 and BAR2 as shown in FIG.

Since the main memory device MM contains a data array starting from address 0, its first element is X. The address O that contains is the BAR.
Since the main memory device MM2 contains a data array starting from address 8, address 8 containing the first element X8 is set to BAR2. Next, the size of the data array, that is, the data array X. 1/2 of the number N of constituent elements of ~Xl5, 8 in this example, is set in the data size instruction register DSI. Furthermore, a shift register SCSR for counting the number of stages indicating the number of arithmetic stages is set. This number r is determined by N=2r for the number N of the constituent elements of the data array, that is, sampling points, and in this example, N
= 16, so r = 4, and this shift register S
The CSR shifts by one for each stage. Also, calculation device F
A value indicating the length of the pipeline in the ALU, ie, the number of minimum units of operation in which the operation ends, is set in the pipeline instruction register PLl. In this example, the pipeline length is 4 stages, so from the initial state the processing unit FA
When data is input to the LU four times and the flow of data within the arithmetic unit advances four stages, the arithmetic result is output from the arithmetic unit, and from this time on, the operation to write the arithmetic result to the main memory is performed. become. The effective address, that is, the contents of the base address register BARl and the contents of the data counter DC added in circuit 10 of FIG. 6, and the contents of the base address register BAR2 and the contents of data counter DC added in circuit 11 of FIG. The added values are set in the first stages of address registers ASR1 and ASR2, respectively. Address shift registers ASRl and ASR
2, the drive circuit 18 in FIG.
The contents of the main memories MMl and MM2 are read out through the drive circuits 18 and 19, respectively, and the contents of the main memories MMl and MM2 are read out through the drive circuits 18 and 19 according to the stage address of the value set in the address shift registers ASRl and ASR2 and the pipeline instruction register PLI. Writing is performed to.

A pipeline shift register PLSR is provided which indicates the step state of the operation in the arithmetic unit FALU. An index selection register IXMCR is set which indicates which of the output 1X1 of the data counter DC or the output 1X2 with its bit order switched is to be selected. In addition, the bus control register BCR, which controls and sets the bus skew unit BSU and switching unit SK, is
The memory control register MCR is set for connecting the memory device MM1 to the arithmetic unit FALU, and the memory control register MCR for controlling reading and writing of the memory devices MM1 to MM2 is set.The memory device MM3 is set only for reading. The setting of the arithmetic function in the arithmetic unit FALU is set in the arithmetic control register FCR1, and the control of the switch in the device FALU is set in the arithmetic control register FCR2. Finally, the data counter DC is cleared. It should be noted that the data required for the above-mentioned various sets have been previously input into the microprogram control device CM from the electronic computer. Next, as shown in FIG. 5, in the pre-processing of the first stage, the setting value of the pipeline instruction register PLI and the pipeline progress value indicated by the pipeline shift register PLSR are compared, and initially PLI is 4, but PLS
R is 1 and does not match address shift register ASR
Main memory device MM at the first stage address of l and ASR2
,,MM2 are read simultaneously, ie, X.

and X8 are read out and applied to the arithmetic unit FALU via the read bus. After this reading, the data counter DC is incremented by 1, and this output is output from the circuits 10 and 1 in FIG.
given to 1. Also, pipeline shift register PL
SR is also shifted by one. After that, the contents of PLI and PLSR
, and similar operations are performed. For example, the arithmetic unit FALU has input terminals 21 and 2 as shown in FIG.
2 are respectively connected to read buses 14 and 15 in FIG.
Output terminals 23 and 24 are connected to write buses 12 and 13, respectively, in FIG. 6.

Input terminal 21 is connected to switch S7-S, -latch (for example, flip-flop or delay circuit) LlL2-switch S.
3-addition/subtraction circuit 25-switch S2-latch L3-L4
The input terminal 22 is connected to the output terminal 23 through switch S8 - latch L5 - switch S1 - SlO - latch L6 - switch S6 - addition/subtraction circuit 26 - switch S4 - multiplication circuit 27 latch L7 - switch S2 - latch L8. 24. The output of latch L2 is also connected to the other input of addition/subtraction circuit 26 through switch S3, and the output of latch L6 is also connected to the other input of addition/subtraction circuit 25 through switch S6. The switches S1 and S2 are interlocked, and in addition to the switching position shown by the solid line as in the above connection, the switch S7 is shown as the dotted line.
is connected to switch SlO, the output side of latch L5 is connected to latch L,
Also, the output side of the adder/subtracter circuit 25 is connected to the input 1 of the latch L8.
11, the outputs of latch L7 are respectively connected to the inputs of latch L3. The input terminal 28 is directly connected to the read output side of the main memory device MM3, and the terminal 28 is connected directly to the read output side of the main memory device MM3.
It is connected to the other input side of the multiplier circuit 27 through - latch L9 - switch S9 - latch L1O. It is now assumed that main memories MMl and MM2 are connected to read buses 14 and 15 and to write buses 12 and 13, respectively. In the pre-processing of the first stage in FIG. 5, first, X. and X
When 8 is read, XO goes into latch L, and X8 goes into latch L5. At this time, W from main memory device MM3. is read out and entered into latch L9. In the next operation cycle, the first stages of address shift registers ASRl and ASR2 are addresses 1 and 9, and Xl, X, , Wl are read from main memories MMl, MM2, MM3, respectively, and latches L,
, L5, enter L9, XO, X8, WO enter latch L2,
Enter L6, LIO. According to the arithmetic mode designation of the preparatory process, the adder/subtracter circuit 25 performs an addition operation and the adder/subtracter circuit 26 performs a subtraction operation under the control of the arithmetic control circuits CTLl and CTL2. Therefore, the addition/subtraction circuit 25 outputs "X". +X8=E
O becomes X in the addition/subtraction circuit 26. −X8=El is calculated,
Furthermore, EiXWOE8 is performed in the multiplication circuit 27. Similarly, in the next calculation cycle, X2, XlO, W2
is read and the latch L1? Enter L52L9, X Alliance X9
7Wl moves to latches L2, L6, LlO, X, +X9
=E1,X,-X,=Ed. EdXWl=E, is calculated, and EO and E8 enter latches L3 and L7.

Furthermore, in the next operation cycle, X3, Xll, and W3 are read out and entered into latches L1, L5, and L9, and other data are sequentially transferred to the output side, and E is input to latches L4 and L8. , E8 are respectively input. At this time, the pipeline shift register PLSR counts 4, and the pipeline specification register P
This matches the value of LI, and it is detected that the pipeline of the arithmetic unit FALU is completely clogged. Therefore, up until now, the read mode and write mode for the storage device were blocked in each calculation cycle, but this write mode is now also enabled, and the address shift register AS
The value indicated by the pipeline instruction register PLI of Rl, ASR2, that is, the address O and 8 in the fourth stage are set to E.
. and E8 are written respectively. From this state, the first stage processing shown in FIG. 5 begins.

At this stage, the contents of the data counter DC and the contents N/2 of the data size instruction register DSI are compared, and if they do not match, they are read out simultaneously from the main memories MM, MM2 at the addresses in the first stage of address shift registers ASRl and ASR2. The calculation result of the calculation unit FALU is then supplied to the output terminals 23 and 24.
ASRl and A of main memories MMl and MM2, respectively.
Each address is written in the fourth stage of SR2. After writing, the data counter DC is incremented by 1, and it is checked whether the value matches the set value of DSI, and the same process is repeated, and the calculations in the first stage in Fig. 3 are performed one after another. It is done. weights to be multiplied in the multiplication circuit 27;
That is, the trigonometric function value, the so-called twiddle factor Wn, is COsO~COsπ/4 and SinO−Sinπ/4, as described above.
The value of 4 is 1 π? Each X- is stored in the main memory device MM3 in the order of its address.

The size of the input data array N-2m is 1024X4=1
012 or less, only the necessary twiddle factors are skipped and read and used according to the index m. Therefore, in the address correction unit TWA shown in FIG.
Output 1X1 of C or output 1X with changed bit position
2 is shifted to the left and the lower bit is set to 0, that is, the address set to O is not read out. However, the address correction unit TWA has a capacity of 12 bits, and any overflow beyond this capacity is ignored. Therefore, as in the above example, N=
If 16=24 and first stage r=1, then 1-1+1
IXl from the address counter is shifted to the left by 34=9 bits to read every 29th address in main memory MM3. For example, this address correction unit TWA
Each bit of Xl or IX2 is input to a set of gates,
The gate output is shifted by a predetermined number of bits, and this gate is transferred to the stage counting shift register SCSR.
A gate is provided which is opened at the corresponding output stage, inputs the above 1X1 or IX2 corresponding to each stage, and obtains a predetermined bit-shifted output, and only one set of these gates is opened for each stage. It is composed of logic circuits like this. As shown in Figure 8, SinO is positive between O and π, and COsθ is positive between O and π/2, but between π/2 and
It is negative between π.

Therefore, if the 11th and 12th bits of the output address of the address correction unit TWA are both 61'' or both are ``O'', it is assumed that COsθ is between O and π/2 and is positive, and 11
One of the 1st and 12th bits is "r" and the other is 60
In the case of ', it is between π/2 and π, and COsθ is negative. In addition, in FIG. 8, the curve 30 of COsθ and the curve 30 of Sin
As can be understood by comparing the curve 31 of θ, COsθ
The absolute value of π/4 to π/2 is equal to π/4 to 0 of 81nθ, so for COsθ, O
Read up to address 10, use the value of COsθ, and calculate π/
4 to π/2 is read in the opposite way to addresses 210 to 2s, and the value of Sin θ at that time is used. Furthermore, COsθ is π/2~
For 3π/4, read addresses 2 to 210 sequentially and add a negative sign to the value of Sinθ at that time, and for 3π/4 to π, 210
It is sufficient to read the address ˜2θ and add a negative sign to the value of COsθ. Regarding Sinθ, it is also 21 for π/4 to π/2.
0-2. Read the address in reverse and use the value of COsθ at that time, and for π/2 to 3π/4, COs at addresses 2 to 210
For θ, the sin θ values at addresses 210 to 22 may be used for 3π/4 to π, respectively. For both COsθ and Sinθ, once addresses 2 to 210 have been read, all that is required is to read them in reverse order, and at that time, the stored values of COsθ and Sinθ can be changed to the actual values. The relationship between the twiddle factor Wnf) COs and Sin is based on the above relationship. If the 10th and 11th bits of the address bits for the storage device MM3 are both 1r" or both "0", the storage device MM3 COsθ and Sin
Let θ be the real part and imaginary part of the twiddle factor Wn, respectively, and if one is "1" and the other is "O", COsθ and Sinθ
Let be the imaginary part and the real part of Wn, respectively. COsθ and Sinθ read from the main memory device MM3 are stored in the twiddle factor exchange control unit TWSC according to the exclusive OR result of the 10th and 11th bits of the address.
θ and Sin θ are switched between real and imaginary parts, and the sign of the real part is determined based on the result of the exclusive OR of the 11th and 12th bits. The output of the replacement part TWSC is the arithmetic unit F.
It is applied to the input terminal 28 of the ALU. As described above, the main memories MMl to MM3 are read, arithmetic operations are performed, and write operations are performed, but in this case, the steps in the first stage processing and the preceding stage processing, the contents of the data counter DC, and the address shift register ASRl are ,AS
Contents given to R2 (hereinafter referred to as index), read addresses of memory devices MM, MM2, address correction unit TW
Output of A (hereinafter referred to as TW index), main memory M
The read address of M3 and the output of the twiddle factor exchange control unit TWSC are as shown in the table of the first stage in FIG.

When the first stage processing in the flowchart of FIG. 5 is performed and the content of the data counter DC reaches the set value N/2 of the data size instruction register DSI, data X7 and Xl5 are transferred from the main memories MMl and MM2. Each of the data is sent to the arithmetic unit FALU, and all the data of the first stage has been read out. Reading of MMl and MM2 is stopped until the calculation results for the data X7 and Xl5 are written into the pupil recording devices MM, MM2. That is, as shown in the first stage post-processing of FIG. 5, DS-DC is YES.
When this happens, the pipeline shift register PLSR is cleared, and until this matches the contents of the pipeline instruction register PLI, the operation result of the arithmetic unit FALU is specified by the fourth stage address of the address shift registers ASR1 and ASR2. are written into the storage devices MM, , MM2, and then the pipeline shift register PLSR is shifted by one stage, and this and the pipeline instruction register PLSR are written.
The comparison with the contents of I is repeated. In this way, the calculation results for data X7, X, 5 are stored in the storage device M.
When written to Ml, MM2, PLI=PLSR is Y
It becomes ES. The second stage is now entered, and preparation processing for that stage is performed.

First, the index selection register IXMCR in FIG.
Then, instead of IXl, the output 1X2 of the bit order change circuit
It is set so that it is supplied to the R2 address correction section TWA. This IX2 and base address register BARl,B
The contents of AR2 are added in circuits 10 and 11, respectively, and set in the first stages of address shift registers ASR1 and ASR2, respectively. In addition, the mode and switch control of the arithmetic unit FALU are specified; in this case, the mode is Fourier computation as described above, and register FCR2 is set so that switching of switches Sl and S2 is omitted for each computation step. be done. As can be understood from FIGS. 2 and 3, the calculations in this second stage are EO+E4, (EO-E4)WO, . E8+El2
, (E8-E,2)WO, etc.

By the way, as mentioned above, E in the calculation result in the first stage. −E7 to addresses O to 7 of the storage device MMl, E8 to E,
5 in addresses 8 to 15 of the storage device MM2, the main storage devices MMl and MM in the second stage
2 becomes extremely easy to generate. That is, in general, when the data size N=2r, the bit arrangement of the lower (m-r+1) bits in the output of the data counter DC may be inverted in the r-th stage in the bit switching circuit 1X. In this bit switching circuit 1X, for example, each bit of a data counter DC is supplied to a set of gates, and the output side of the gate is connected so that the bit order of a predetermined lower bit in the gate is switched. Gate is shift register SC for stage counter
At the output of a given stage of SR. Gates are opened and the lower bits are replaced corresponding to each stage.
Depending on the state of register SCSR, only one set of gates is automatically opened. In the case of N=16 above, m=4, and in the second stage, the bit order is inverted by the lower order by 4-2+1=3, and the result of the inversion is the 9th bit order.
・It is shown as index IX of the second stage in the figure, and from this, the first calculation step of this second stage is
At the th address O and 8 are the storage devices MM, MM
2 to E respectively.

and E8 are read out and applied to latches L1 and L5 of the arithmetic unit. Next, from addresses 4 and 12, E4 and El
2 are respectively read out, and at this time the switch Sl of the arithmetic unit is
, S2 are switched as shown by the dotted lines, so they enter latches L6 and L5, and EO and E8 enter latches L2 and Ll, respectively.
Therefore, E of L2. and E4 of L6 are arithmetic circuits 25 and 26
, 27, EO+E4=DO, (EO−
E4) WO-D4 are calculated respectively. Next, E2 and ElO are read from addresses 2 and 10, respectively, switches Sl and S2 are solid lines, so they go into Ll and L5, E8, E, and 2 go into L2 and L6, respectively, and E8
+El2-D8, (E8-El2)WO-D2 is calculated, and the previous D is calculated. , D4 enters L3 and L7. Next, E6 and E,4 are read from addresses 6 and 14, respectively, and L
6 and L5 respectively, E2+E6=D2, (E2-
E6) W4=D6 is calculated, DO, D4 are L4, L3
Then, D8, D, and 2 enter L8 and L7, respectively. At this time, the contents of the pipeline instruction register PLI and the count value of the pipeline shift register PLSR match, that is, the pipeline of the arithmetic unit FALU is completely clogged, and the pre-processing of the second stage ends. Therefore, storage devices MMl, MM2
Until then, only reading was performed for MM1 and MM2, but from the next calculation step, writing to MM1 and MM2 will also be performed. In this case, D2 and D8 appear on the terminals 23 and 24 by operating the switches Sl and S2, and are written to addresses O and 8 of the storage devices MMl and MM2 indicated by the contents of the fourth stage of the address shift register ASRlASR2, respectively. be included. In this way, two pieces of data, which should not be calculated on each other, can be read out at the same time and two calculation results can be obtained at the same time, and calculations can be performed at high speed. Second
Stage data Ell and El5 are read out, and the contents of the data size instruction register DSI and the data counter DC are read out.
If the contents of the stage shift register SCS match, the stage shift register SCS
R is shifted by 1 and the process moves to the third stage of arithmetic processing. In this case, the bit switching circuit 1X and the address correction circuit TWA are activated by the output of the stage shift register SCSR shown in FIG.
r is changed. Therefore, in the third stage, only the lower two bits in circuit 1X are reversed in bit order, and in TWA they are shifted to the left by 11 bits.

In this state, the same operation as in the second stage is performed. In this case, various addresses etc. are as shown in the third stage of FIG. The fourth stage is processed in the same way. In this example, m=4, and the maximum number of stages is 4, so when data Cl4 and Cl5 are read in the fourth stage, the stage shift register SCSR is shifted, and thus overflows. After that, the process moves to the final process of processing the data remaining in the arithmetic unit FALU, which is similar to the post-processing of the first stage, but when the pipeline shift register PLSR matches the contents of the pipeline instruction register PLI, all data are processed. The calculation ends. In this way, 16 sampling points
. -Fourier coefficient F in the Fourier transform of the signal f(t) represented by X,5. -Fl5 is obtained. To perform inverse Fourier transform, switch S9 in arithmetic unit FALU is set to the imaginary part sign inversion switching circuit 50 side, and the output of latch L9 is passed through this circuit 50, with the sign of the imaginary part inverted and supplied to latches L and O. All you have to do is set the mode so that

Furthermore, Fourier transform extracts a finite section of a continuous waveform and analyzes it on the assumption that it is a periodic function of that section.
However, this is not necessarily the case. Therefore, an error occurs in the analytical value. In order to reduce this error as much as possible, so-called window processing is performed in conventional digital Fourier transform devices. This window processing includes the Hamming method, Hanning method, Bartlett method, etc., and such window processing can also be performed in the apparatus of the present invention. For example, the Hanning method uses 1m (1-C
The data is multiplied by 2Nm by the compensation function Os-2π),
Since this value COs-2π is stored as a twiddle factor in the storage device NMM3, it can be used.

For this purpose, in the arithmetic unit FALU shown in FIG.
O is switched to one terminal 51 or 52 and only O is input, and data Xn is input from the other side. Also Switch S9
is switched to the circuit 53 side, and this circuit 53 consists of a circuit 54 that subtracts the input from 1 and a circuit 55 that shifts the output by 1 bit to the right and divides it by 2.
COs-m from 2πm is the operation N of 1 (1-COs?)
2N is performed in circuit 53.

The data Xn read from the storage devices MMl and MM2 is inputted to one of the terminals 21 and 22, which is connected to the switches S7 and S8, and the twiddle factor is read from the storage device MM3 and supplied to the circuit 53 through the terminal 28. . For example, when data is applied to the terminal 22, the input of the latch L is always O, the addition/subtraction circuit 26 is set to addition mode, and the data from the terminal 22 is multiplied by 1 (12πMcOs?) from the circuit 53 in the circuit 27. Depending on the state of the switch NS2, the data is output from one of the terminals 23 and 24 to the write bus, and further written to the memory devices MM, MM2.

The device of the present invention described above can perform not only Fourier transform but also various data array operations.

An example will be described below. Addition and subtraction between the two data arrays is performed by setting the switches S1 and S2 as solid lines in FIG. 7, setting the switch S3 to the latch L2 side, setting the switch S4 to the latch L7 side, and setting the switch S6 to the latch L6 side, and adding or subtracting the addition/subtraction circuit 25. The addition/subtraction circuit 26 is designated to perform either subtraction or addition. In response to input data An, Bn at terminals 21, 22, data arrays An+Bn, . An-Bn or An-Bn, . An+
Bn is obtained. For multiplication of data array An-Bn, zeta AnBn is put into one of terminals 21 and 22 and terminal 28,
The side to which data of switches S7 and S8 is not supplied is terminal 5.
1 and 52 and O is input, switch S5 is connected to terminal 28, switch S9 is connected to latch L, and the rest is the same as the window processing. As a result, terminals 23, 2
An array of multiplication results is obtained on one side of 4. An arbitrary constant K is added to, subtracted from, or multiplied by the data array An. For addition and subtraction, set zeta An to one of terminals 21 and 22 and constant K to the other.
, and perform the addition and subtraction of the data array AnBn described above. Further, by inputting the data array An to one of the terminals 21 and 22 and the constant K to the terminal 28 and performing the same multiplication as described above, a data array KAn is obtained. Furthermore, for conversion from data array to data array, for example, in the case of integration, switch S is set as a dotted line, S2 is set as a solid line, switch S3 is set as a dotted line, S2 is set as a solid line,
, S4 are respectively on the latch L7 side, switch S7 is connected to terminal 21, S8 is connected to terminal 52, S5 is connected to switch S8,
Connect each SlO to switch S1 and add/subtract circuit 2.
6 to add operation.

A data array An is applied to terminal 21. When data AO enters latch L7, it is added to A in circuit 26, and A
O+A1, then A in the next step. +A1+A2 is obtained and the integrated array is obtained at terminal 24. In the case of differential operation, switches S,, S2 are connected to solid lines, switch S3 is connected to latch L2, S6 is connected to latch L6, and S and O are connected to latch L2, respectively, and the rest is the same as in the case of integral operation.
The circuit 26 is operated as a subtractor. As a result, the difference between the previous result from latch L7 and the new data from latch L6 is taken in circuit 26, and the result is input to L7 to provide a differential data array at terminal 24. Furthermore, to obtain the sum of each element of the data array, the same integration operation as described above is used, but only the final value is written into the storage device. Alternatively, in FIG. 1, one or more 1-word registers GR are provided, for example GR1 to GR4, which are connected to the write bus and the read bus through switching circuits, respectively. Therefore, when performing the above-mentioned sunmation, if the calculation output is written to one of the registers GR, the newest calculation result is always stored in this register. The above-mentioned embodiment is capable of performing the above-described calculations on the various data arrays, but the control for this is performed by the microprogram pedestal device CM as described above.

In that case, the number of microinstruction bits would be extremely large if all controls were to be set each time using microinstructions. Therefore, settings that do not change during one operation, such as the data bus, bit width, type of operation, and address pattern to be generated, are set in the setup register under microprogram control, and the settings in that register are kept unchanged during the operation. The contents of are fixed. Control of the timing of reading and writing of the storage device, address updating, progress of calculations, status sense, etc. are given as microinstructions.

Examples of typical microinstructions are described below. First, the move or MD instruction (MOveData instruction) consists of 32 bits as shown in FIG. device FALU,
Data is then transferred to the main memories MM1 and MM2. In this case, the read storage device and the write storage device may be separate devices. Control fields are 0th to 5th
bit, the 0th bit is 10゛, interrupt is accepted,
“INTDS (Interru
ptDisable), and the first bit RET,SE
T (ReturnAddressSet) is 60'' is N
OOperatiOn, and 1 bit stores the address currently being executed +1 in the return address register. Second
Bit RET (Return) is O and NO Operat
iOn (NOP), 11'' jumps to the content address of the return address register. However, this is not performed when an interrupt trap occurs. The third bit DAR-HIT (HitD
directAddressRegister) is NOP with "O", and the content of the direct address register is incremented by 1 with "."R5. 4th bit IXHIT (HitInde
xCounter) is ``0'' and NOP.6l'' increases the contents of the data counter DC by 1. 5th bit ASR-S
ET(SetAddressShiftRegister
r) is 10゛ and NOP. ．． At 8l, the index is set in the address shift register. The 6th and 7th bits are NOP at 60', and the memory control field at 1' controls reading and writing of the main memory according to the contents of the memory read control register MRCR and the memory write control register MWCR. If the 6th bit is 6r'', it is read from the storage device, and if the 7th bit is 11'', it is written to the storage device. Note that the 6th and 7th bits cannot be set to 61'' at the same time in one instruction. The 9th bit is the BCR field, which controls the transfer between the main memory device MM or general register GR, the bus, and the arithmetic unit FALU according to the contents of the bus control register BCR.The 8th bit "1" controls the bus on the write side. Transfer data according to register BCR,
The 9th bit 61 is the bus control register BC on the read side.
Transfer data according to R. The 8th and 9th bits cannot be set to ``1'' at the same time.The 10th to 18th bits are trap fields, and they read the index direct data bit (IX-DDB) and accept traps. Decide whether or not to execute, and specify the next execution address at the time of acceptance.The 10th to 13th bits are IX
DDBCOND (IndexDDBcOnditiOn
) corresponding to the bit that is ``1'' in the field
Assume that the trap condition is satisfied when all bits of DB are "1"2.

14th bit IXDDBCLR (NdcxDDBcle
ar) only when a trap is accepted at 11゛5,
I corresponding to "1" in the IX-DDBCOND field
Set all bits of X-DDB to "0".

The address of the next instruction to be executed when a trap is accepted is determined by the 15th to 18th bits TRAPADDRESS. The 19th to 24th bits are pulse fields, and the 19th bit X-CTL (IndexcOntrOl
) is the index mode control register (X-MC
R) is valid only when the CTL bit is "r", and 60
” selects IXl as the address source of address shift register ASR2, and when “1” selects IX2 as the address source of ASR2. 20th bit PUSH bar
' sends an arithmetic execution pulse to the arithmetic unit specified by the bus control register BCR. The 21st to 24th bits T1 to T7 are "
r'' sends pulses to the arithmetic unit at specific times T, T3, T5, and T7.If the 27th bit NOTRAP is 0, it is possible to accept a trap, and when it is 61, it is prohibited to accept a trap.
The EMIT instruction, which transfers the data written in the instruction field to the register of the connected arithmetic unit, has the 0th to 5th bits the same as the MD instruction, as shown in FIG. 10B.
The 6th to 9th bits instruct the arithmetic unit that should receive the data, the 10th to 13th bits specify the register within that arithmetic unit, and the 14th to 29th bits display the data to be transferred. .

The SS instruction (SetStatus) that transfers the contents of the read buffer register or general register of the main memory to the register in the specified arithmetic unit is shown in Figure 10C, and the parts corresponding to Figure 10B have the same symbols. The 14th to 16th bits REG are used to command the storage device serving as the data source. For L/R, 0゛ is transfer from the left half, and ``1'' is transfer from right half. FS transfers the contents of the control register in the arithmetic unit to the storage device or general register.
For the instruction (FetchStatus), as shown in FIG. 10D, the 14th to 17th bits indicate the storage device or register to be stored. Other ALOP instructions that perform arithmetic and logical operations in general registers, LR instructions that store data in a storage device to general registers, SR instructions that write data in general registers to storage devices, and interrupt processing routines. Return RFI instructionStatus sensing conditionsJOTJNT instruction, senses the Status and jumps to one of the five addresses following the instructionS
AM that only performs KP command, reading and writing of storage device
There are commands, etc.

In the above, various array operations were made possible by changing the operation function by switching the switch in the operation unit FALU, but as mentioned earlier, there are multiple array operations with different functions between the read bus and the write bus. Connect your computing devices and use what you need. For example, as shown in FIG. 11, an arithmetic unit FALU for performing digital Fourier transform, a division arithmetic unit DALU, a square root arithmetic unit SALU, and the like are connected between write buses 12 and 13 and read buses 14 and 15, respectively. All of these arithmetic units have a pipeline configuration, and in the division arithmetic unit DALU, for example, the first
As shown in FIG. 2, it consists of four stages of pipelines PLl to PL4. Each pipeline has a register LR where a 32-bit dividend is stored, a register LR'' where a 16-bit divisor is input, and a register LR from the number in register LR.
an adder/subtracter ASU that subtracts the number in ', a shift circuit SLU that receives the remainder and shifts the pit one bit to the left, and an output of the shift circuit that is sent to the dividend register LR.
and a SW that is switched and connected to the dividend register LR of the next step, a control circuit LC that detects whether or not a carry has occurred from the adder/subtractor ASU in a circuit C, and controls based on the detection state, and a control circuit LC that performs addition/subtraction using the circuit LC. It consists of a register RR into which the division result obtained by adding one bit for each operation of the unit ASU is input. Data is transferred from the read bus to register L.
When input to R and LR', they are subtracted from each other in a subtracter ASU, 1 is input to register RR, and the subtraction result is shifted to the left by 1 bit, and is stored in register L.
It can be placed in R. The contents of this register LR are rounded by the contents of the divisor register LR', and as a result, the register RR becomes 1.
The result of the subtraction is shifted one bit to the left and input into the register LR, and the same process is repeated. When subtraction is performed four times, the number of times of each subtraction is stored in the counter LC.
The switch SW is connected to the dividend register LR of the next stage, and the value obtained by shifting the subtraction result to the left by one bit is supplied to the dividend register LR of the next stage. Next, when new data is input from the storage device to the arithmetic unit DALU, the contents of the divisor register LR' in the first step PLl are changed to the divisor register L of the second step PL2.
At R/, the contents of the register RR of the division result of the first step are respectively transferred to the result register RR of the second step PL2. Similarly, the divisor register LR7 of each step,
Each content of the result register RR is transferred to its corresponding one in the next stage. In this way, the fourth step PL4
When the calculation is performed, the 32-bit dividend becomes 1 for the first time.
Shifted to the left by 6 bits, division by the 16 bit divisor is completed and provided to the write bus. In this way, even if the calculation speed of division is slower than the read cycle of the main memory, the division can be performed without reducing the read speed of the main memory. As described above, according to the data array arithmetic device of the present invention, the arithmetic device has a pipeline configuration, taking advantage of its high speed and flexibility in microprogram control, allowing various arithmetic functions to be performed by the same device. I can do it.

In this case, appropriate control registers are provided to reduce the number of bits constituting the microinstruction, thereby making various controls possible. Note that it takes a long time to perform an operation on data other than a data array using a pipeline-configured arithmetic unit. From this point on, a conventional arithmetic unit ALU can also be connected between the read bus and the write bus.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an example of an array calculation device according to the present invention, FIG. 2 is a diagram for explaining a digital Fourier transform algorithm using the Sunday-Chiyuki method, and FIG.
Figure 4 is a table showing the calculation, Figure 4 is a diagram showing the storage status of twiddle factors, Figure 5 is a flowchart of digital Fourier transform, Figure 6 is a block diagram showing an example of the address generation section, and Figure 7 is a diagram showing the storage state of twiddle factors. A block diagram showing an example of an arithmetic device; FIG. 8 is a diagram showing the relationship between sine values and cosine values; FIG. 9 is a table showing the relationship between counters, indexes, and twiddle factors at each stage;
FIG. 10 is a diagram showing examples of various microinstructions, FIG. 11 is a block diagram showing another example of the array arithmetic device of the present invention, and FIG. 12 is a block diagram showing an example of the division arithmetic device.

Claims (1)

[Claims] 1 At least one readable and writable storage device in which a data array is stored in a sequentially addressed manner, an address generator that generates read and write addresses for the storage device, and a read and write cycle of the storage device that minimizes read and write cycles. The unit of operation is multiple times the unit of operation to complete one operation, two data array input terminals, at least one output terminal to which the data array of the operation result is output, and the amount of delay of the minimum operation unit. at least one delay element, at least one arithmetic element, and at least one switch for switching the connection of these input terminals, delay element, and arithmetic element, and the arithmetic function to be processed can be changed by controlling the switch. a readout bus that supplies two data arrays read from the storage device to two input terminals of the calculation device; and a readout bus that supplies the calculation results from the output terminals of the calculation device to the storage device. controls a write bus to be supplied as write data to the memory device and the switch to designate the arithmetic function of the arithmetic device, read the data array from the storage device, and write the arithmetic results of the arithmetic device to the storage device. A data array arithmetic processing device comprising a microprogram control device.