JP3522779B2 - FIFO memory device and data distribution device - Google Patents

Description

Detailed Description of the Invention

[0001]

The present invention relates to an input is performed in one word unit, FIFO notes output is performed by a plurality of words
Device , and FIFO memory device in which input is a variable-length word and output is a word, and these FIFOs
The present invention relates to a data distribution device using an O memory device .

[0002]

2. Description of the Related Art FIG. 13 is a diagram for explaining a conventional technique. In FIG. 13, the distributor is a processor module having a CPU and a local memory (hereinafter,
It is called "PM". ) Is [PM0] 130,
In order to input / output data, four memories 132-
135 is provided.

Similarly, the distributor has four memories 1 for inputting / outputting data to / from [PM6] 131.
36 to 139 are provided. From one PM to another
For example, from [PM0] 130 shown in FIG. 13 to [PM
6] When data is transferred to 131, the transferred data is first word by word in order from the four memories 132 to 132 of the input side.
Written at 135.

When the writing is completed, the transfer data for four words is read out simultaneously, and the four memories 13 on the output side are read.
It is temporarily stored in 6 to 139. From here, data is transferred to the [PM6] 131 word by word.

In the distributor, while the transfer data is distributed by one path, the transfer data is stored in another memory which is not related to the path. The apparent transfer speed of this distributor is improved to be several times that of the parallel memory, but conventionally, a plurality of memories 132 to 135 and 136 to 139 are provided in parallel as described above to improve the transfer capability. I have been devising.

[0006]

With the above-mentioned configuration, the transfer performance can be improved, but conventionally, the number of words that can be transferred at one time is fixed. Therefore, if the number of words differs depending on the type of transfer data, in order to guarantee the context of the data, it is necessary to insert dummy data and align it with the designed number of words. However, there is a problem that processing time is wasted.

FIG. 14 is a diagram for explaining the problems of the prior art. In the figure, the transfer data has a total length of 7 words, and is composed of 1-word command data and 6-word parameter data. Also, the FIFO
Is provided with six memory cells arranged in parallel in three stages.

In FIG. 14, when the transfer data is written in the FIFO, as shown in the figure, the parameter data of the seventh word of the transfer data is written in the memory of the next stage. In this case, if other transfer data is continuously written to the memory cell adjacent to the memory cell, the data of six words that are simultaneously read cannot be distributed in that stage.

To solve this problem, dummy data is inserted into the remaining memory cells in that stage, and other transfer data is
You should write in the upper row. However, the method of inserting the dummy data and advancing the write address to the memory cell is time-consuming, which is a problem.

The present invention has been made in view of the above conventional problems, and unit data of an arbitrary length to be written in a memory cell can be written in a plurality of words without performing a write operation of dummy data. 1-word input / multi- word output FIF that can be read correctly and simultaneously for each
O memory device and variable length word input / one word output F
Efficient for IFO memory device and data strings of different formats
An object of the present invention is to provide a data distribution device that can be distributed well .

[0011]

According to the invention, the above mentioned objects are achieved by means of the patent claims.

Namely, the invention of claim 1, a FIFO memory device for transferring the unit data Oa Ru device which consists of one or more words to other devices, the X-direction
Plural pieces arranged and stacked in the Y direction
Memory cell and the memory cell of the write destination in the X direction.
Counts when writing a light X pointer that indicates a dress
Up, and the write X pointer of the memory cell
If you count the number in the X direction, or
When the last word of the
X-pointer control means for returning the data to 0 and the writing destination memo
Move the write Y pointer that indicates the Y-direction address of the recell forward
The count is incremented when the write X pointer returns to 0.
Y-pointer control means for making and a plurality of memos on the reading side
Read the read pointer that indicates the Y-direction address of the resel
Read pointer control hand that counts up by the take-out action
And a read point at the time of reading.
The number of memory cells located in the row indicated by
FIF characterized by the simultaneous reading of words
O memory device .

According to a second aspect of the present invention, an FIF for outputting the input unit data of variable length words in units of one word.
An O memory device in which a plurality of stacked memory cells
When the data analysis means for analyzing information about the number of words the unit data represented in the unit data, write
If there is only one operation, the unit data is read from which position of the memory cell based on the analysis result of the data analysis means.
Write to a write pointer that indicates whether to write
Add the number of words, while if there is a read operation,
Operation means for subtracting 1 from the write pointer, and read
If there is an operation, the memory cells of each stage will be
And a means for copying the data in the memory cell,
Output data is always read from the last memory cell.
A FIFO memory device, characterized in that that.

The invention of claim 3 is the first FIFO.
Consisting of a memory device and a second FIFO memory device,
A plurality of first FIFO memory devices are arranged in the X direction.
And a plurality of memory cells stacked in the Y direction
And the address in the X direction of the write destination memory cell
The write X pointer is incremented when writing,
The write X pointer is the number of memory cells in the X direction.
When counting minutes, or at the end of the unit data
When the code is written, the write X pointer is returned to 0
X pointer control means and Y direction of write destination memory cell
The write Y pointer that indicates the address
Y-point to count up when the interface returns to 0
Data control means and the Y direction of the plurality of memory cells on the read side
The read pointer that indicates the address
And a read pointer control means for raising
More than one output from each of multiple devices performing parallel processing
Each unit data composed of words is divided into unit data units.
The second FIFO memory device is stacked in a plurality of stages.
Memory cell and the unit cell indicated in the unit data.
Data analysis to analyze information about the number of words in the order data
Means and, if there is a write operation, said data analysis means
From which position of the memory cell based on the analysis result of
Write pointer indicating whether the unit data should be written
The number of write words is added to, while the read operation is performed
If there is, an operation to subtract 1 from the write pointer
When there is a means and a read operation, the memory cells of each stage
Each has a means to copy the data of the memory cell in the previous stage.
And distributed by said first FIFO memory device
Disconnect the unit data in word units, the data distribution characterized by a Turkey be transferred to a plurality of other apparatuses performing each parallel processing
It is a device .

[0015]

According to the first aspect of the invention, the write X pointer indicating the write address to the memory cell is counted at the time of writing.
And the write X pointer is in the X direction of the memory cell.
When counting the number of
The write X pointer is reset to 0 when the word is written.
Thus, the variable length data following the number of memory cells arranged in the X direction, efficiently transfer. And without inserting dummy data as a shortage of the number of parameter data,
Flexibly deal with variable-length data to increase speed.

According to the second aspect of the invention, by devising the operation of the write pointer indicating the write address,
A variable-length word input / one-word output FIFO memory device is configured to decompose variable-length data into original data in units of words. These FIFO memory devices enable high speed transfer of a large number of various variable length data. Moreover, a data decomposition mechanism of the parallel processing device can be constructed.

[0017]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS FIG. 1 shows an input according to the present invention as one word and an output as
1 shows an example of the configuration of a multi- word FIFO memory device . Further, FIG. 2 shows a configuration example of the memory cell 15 shown in FIG. In FIG. 2, the write-destination memory cell is two-dimensionally represented by a write X pointer 20 and a write Y pointer 21.

On the other hand, the plurality of memory cells on the read side are shown one-dimensionally only by the read pointer 22 in the Y direction. At the time of reading, "m + 1" words located in the stage indicated by the read pointer 22 are read at the same time.

The write X pointer 20 shown in FIG. 2 counts up at the time of writing and counts "m + 1" which is the width number of the memory cell 15 from "0" to "m", or at the end of the unit data. When a word is written it returns to '0'. The write Y pointer 21 counts up when the write X pointer 20 returns to "0".

In FIG. 1, an X pointer control circuit 11
Controls the counting operation of the write X pointer 20, and Y
The pointer control circuit 12 controls the counting operation of the write Y pointer 21. In addition, the read pointer control circuit 1
3 controls the counting operation of the read pointer 22.

As in the case of a normal FIFO structure, the readable state and writable state can be determined by comparing the write Y pointer 21 and the read pointer 22.
In FIG. 1, a flag control circuit 14 controls an empty flag for determining a readable state and a full flag for determining a writable state.

In the above embodiments, the one-word input / multi- word output FIFO memory device has been described. Conversely, a FIFO memory for inputting variable-length data and outputting data in units of one word. In order to provide the device , it is necessary to construct a FIFO memory device which is characterized by pointer operation.

FIG. 3 shows an example of the configuration. When the number of words of input data is variable, it is difficult to operate the write pointer and the read pointer as in a normal FIFO memory device . Therefore, in FIG. 3, the operation is performed only by the write pointer.

In FIG. 3, the data analysis unit 30 analyzes the number of words of the input data, and the arithmetic unit 31
After writing the variable length data to the memory cell 33,
It calculates the value of a new write pointer. The write pointer controller 32 operates the pointer by a write operation, a read operation, or the like.

In FIG. 3, when there is a write operation, the number of write words is added to the write pointer, and the value of the write pointer is updated. In the write operation example of FIG. 6, the write pointer before the write operation indicates “2”, and the write pointer after writing the input data of four words indicates “6”.

On the other hand, when there is a read operation, the write pointer is decremented by "1". By this subtraction,
The write pointer after reading one word data is obtained. In the operation example of FIG. 7, a write operation and a read operation occur.

In the write operation shown in FIG. 7, since the variable length data is 4 words, the write pointer is "4".
Only added. In the read operation, the write pointer is decremented by "1". Therefore, the value of the write pointer becomes "2" by these write and read operations.
Has been updated from '5'.

FIG. 4 shows a configuration example of the memory cell 33 shown in FIG. In FIG. 4, when a read operation is performed, the data in the memory cells in each stage are copied from the memory cells in the previous stage. Therefore, one word of output data is always
In FIG. 4A, the first memory cell labeled [memory cell 1] is taken out.

Therefore, for example, the memory cell of FIG. 4 is in the empty state when the write pointer 40 is pointing to "1", and is in the full state when the memory cells for the number of words of the next input data are not empty. can do.

FIG. 5 is a diagram for explaining the relationship between the number of each memory cell into which n words of input data will be written and the value of the write pointer. In the case of FIG. 5, n-word input data is written in n memory cells from the memory cell of the number indicated by the write pointer.

Therefore, the value of the write pointer is "mn".
If it is +2 "or more, only the data of the number of words of" n-1 "or less can be written, so it can be said that the memory in the state in which the data of n words cannot be written is in the full state.

In the memory cell, as shown in FIG. 4B, a means for directly writing input data at the time of writing,
A means for copying the data of the memory cell in the preceding stage at the time of reading can be provided and configured.

In order to implement the method shown in FIG. 1 or 3, for example, as shown in FIG. 8, it is possible to efficiently operate the transfer data in a specific data format.
The number of words of the following parameter data is embedded in unused bits in one word at the beginning of a series of data strings included in one transfer data.

Then, the command analysis unit 10 shown in FIG.
Can analyze the number of words of the transfer data and notify the X pointer control circuit 11 of the word. The data analysis unit 30 shown in FIG. 3 can also analyze the number of words of the transfer data, and can notify the arithmetic unit 31 of the number of words.

An example of the configuration of the arithmetic unit 31 shown in FIG. 3 is shown in FIG. In FIG. 9, the arithmetic unit 31 is configured by only one adder 90. In the figure, the adder 90 is
It has three inputs: the current write pointer value, the number of words of input data of variable length, and a read signal. For example, when there is a read operation, the write pointer is subtracted by "1" by detecting the read signal.

The one-word input / plural- word output FIFO memory device and the variable-length word input / one-word output FIFO memory device described above are used for parallel processing in order for the three-dimensional graphic display device to speed up graphic processing. Can be used for a data distribution circuit or the like that is required when performing.

FIG. 10 shows an embodiment to which the present invention is applied. FIG. 10 shows processor modules 101-105.
It shows a system for transferring the data calculated by the above to the processor modules 106 to 110 of the next stage via the distributor 100. In this system, FIG.
It is assumed that data flows as shown in.

As shown in FIG. 11, the data obtained from [PM1] is distributed to [PM6], [PM7], and [PM8], and the data obtained from [PM2] is [PM2].
7], [PM8], and [PM9].

At this time, [data 2] and [data 4],
When [Data 3] and [Data 5] have to follow the order, the above-described distribution operation is performed in such a manner that the output data from [PM1] is processed and then the output data from [PM2] is processed. It is specified and cannot operate in parallel.

Therefore, the processing performance of the distributor is required to be "the number of parallel lines times" the processing performance of each PM. In order to realize this processing performance and increase the transfer speed, the present invention capable of transferring a plurality of words collectively can be used.

Each of the data shown in FIGS. 11 and 12 is assumed to be variable length data composed of a processing command of one word and '0' word, or a parameter of one word or more.
At this time, the transfer data is a data string composed of one or more words. The data strings in word units output from [PM1] to [PM5] are packed and distributed in command units, and are separated again in word units at the distribution destination.

[0042] That is, according to one word input and multiple word output FIFO memory device, and distribution processing data are sequentially stored a plurality of words, the data decomposed by the FIFO memory device of the plurality word input, one word output, the following By passing the PM to the stage PM, the distribution processing capability of the distributor can be increased.

[0043]

As described above, according to the present invention,
Since multiple words can be output at one time, high speed processing can be realized. Further, there is no need to add dummy data to the transfer data, it is possible to perform efficient data transfer.

Furthermore, the data distribution device using the FIFO memory device according to the present invention can efficiently distribute data strings of different formats, and is very effective for a high-speed image processing circuit or the like. . Further, the present invention can be configured with a relatively simple circuit, so that there is an advantage that LSI can be easily formed by the gate array.

[Brief description of drawings]

FIG. 1 is a diagram showing an embodiment according to the present invention.

FIG. 2 is a diagram showing a configuration example of a memory cell.

FIG. 3 is a diagram showing another embodiment according to the present invention.

FIG. 4 is a diagram showing a configuration example of a memory cell.

FIG. 5 is a diagram showing writing positions of variable-length data.

FIG. 6 is a diagram for explaining a write operation.

FIG. 7 is a diagram for explaining a read / write operation.

FIG. 8 is a diagram showing a configuration example of transfer data.

FIG. 9 is a diagram illustrating a configuration example of an arithmetic unit.

FIG. 10 is a diagram showing an embodiment to which the present invention is applied.

FIG. 11 is a diagram showing a data flow from'PM1 '.

FIG. 12 is a diagram showing a data flow from'PM2 '.

FIG. 13 is a diagram for explaining a conventional technique.

FIG. 14 is a diagram for explaining a problem of the conventional technique.

[Explanation of symbols]

10 command analysis unit 11 X pointer control circuit 12 Y pointer control circuit 13 read pointer control circuit 14 flag control circuit 15, 33 memory cell 20 write X pointer 21 write Y pointer 22 read pointer 30 data analysis unit 31 arithmetic unit 32 write pointer control Part 40 Write pointer 90 Adder 100 Distributor 101-110, 130, 131 Processor module 132-139 Memory

Continuation of the front page (56) Reference JP-A-4-121890 (JP, A) JP-A-60-73730 (JP, A) JP-A-2-16630 (JP, A) JP-A-63-138591 (JP , A) JP-A-5-234356 (JP, A) JP-A-5-173870 (JP, A) JP-A-62-175023 (JP, A) Actual Kaihei 2-67443 (JP, U) (58) Fields investigated (Int.Cl. ⁷ , DB name) G06F 5 / 06,12 / 04,15 / 173 G11C 7/00

Claims (2)

(57) [Claims] 1. A FIFO memory device for transferring unit data composed of one or more words from one device to another device, wherein a plurality of FIFO memory devices are arranged in the X direction and stacked in a plurality of stages in the Y direction. A plurality of memory cells and a write X pointer indicating an address in the X direction of a write destination memory cell are counted up at the time of writing, and the write X pointer counts by the number of the memory cells in the X direction, or X pointer control means for returning the write X pointer to 0 when the last word of data is written, and a write Y pointer indicating the address of the memory cell at the write destination in the Y direction when the write X pointer returns to 0. Y pointer control means for moving up and a read pointer indicating addresses in the Y direction of a plurality of memory cells on the read side. Read pointer control means for counting up the data in a read operation, and at the time of reading, the same number of words in the X direction of the memory cells located in the stage indicated by the read pointer are read simultaneously. FIFO memory device. 2. A first FIFO memory device and a second FI.
The first FIFO memory device comprises a FO memory device and a distribution means , and a plurality of the first FIFO memory devices are arranged in the X direction and stacked in the Y direction.
A plurality of memory cells and a line indicating the address in the X direction of the memory cell to be written
The X pointer is incremented when writing,
The number of write X pointers is equal to the number of memory cells in the X direction.
Or the last word of the unit data is written.
An X-point that resets the write X-pointer to 0 when imbedded
Data control means and a line indicating the Y-direction address of the write destination memory cell.
When the write Y pointer returns to 0
Y pointer control means for counting up and Y direction addresses of a plurality of memory cells on the read side are set.
The indicated read pointer is counted up by the read operation.
And a read pointer control means for performing parallel processing, each of which is output by a plurality of devices performing parallel processing.
Input each unit data composed of words and read the above
In the X direction of the memory cell located at the stage indicated by the pointer
The number of words are simultaneously output, and the distribution unit outputs the first FIFO memory device output.
And the second FIFO memory in unit data units.
Distributed to the device, the second FIFO memory device includes a plurality of stages stacked memory cells, the number of words of the unit data represented in the unit data
If there is a write operation and data analysis means for analyzing information regarding the
Based on the result, from which position of the memory cell the unit
Write to a write pointer that indicates whether to write data
Add the number of words to be imbedded, and if there is a read operation,
In this case, if there is an operation means for subtracting 1 from the write pointer and a read operation, the memory cells in each stage are respectively
And a unit for copying the data of the memory cell in the preceding stage, and the unit data distributed by the distributing unit is word unit.
To one of the other multiple devices for each parallel processing.
A data distribution device characterized by transferring .