JPH0528290A - Data driven type computer - Google Patents

Abstract

(57) [Summary] [Object] To obtain a data-driven computer capable of avoiding unnecessary congestion of a cyclic pipeline due to overflow packets, and avoiding congestion due to overflow packets and execution suspension due to hash collision. A queuing processing unit 101 is provided which has a hash memory as a queuing memory, and is provided with an OV flag which is set at each address of the hash memory when a hash collision occurs at the hash address and an overflow packet is output. The extended ignition processor 106 has a hash memory that stores the overflow packet output from the ignition processing unit 101 by using the same hash function as the hash memory and using a chain connection. The packet is stored in either the ignition processing unit 101 or the extended ignition processing unit 106, and
With respect to the address in which the V flag is set, both the firing processing unit 101 and the extended firing processing unit 106 are accessed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a data driven type computer which drives processing based on data dependency, and more particularly to avoiding execution suspension due to overflow of queuing memory in a cyclic pipeline configuration. ..

[0002]

2. Description of the Related Art FIG. 16 is a conceptual diagram of data processing in a data driven computer and shows how two data are added. In the figure, when a packet 81 having a value of “A” and an identifier of “a” is given to the ignition processing unit 87, the identifier field comparison unit 84 of this ignition processing unit 87 causes the ignition processing unit 87 It is searched whether or not a packet having an identifier matching the identifier "a" of the newly input packet 81 is already stored in the waiting memory 85 of FIG. In the example of FIG. 16, since the packet 82 having the value “B” and the identifier “a” has already been stored, this packet 82 is read from the queuing memory 85, and the data together with the input packet 81 is read. It is transferred to the pair forming unit 86.

The data pair forming unit 86 includes packets 81 and 82.
Are combined to form data 83 in which the identifier “a” is added to the values “A” and “B” (this is called firing), and the data 83 is transferred to the data processing unit 88. The data processing unit 88 executes the operation of “A + B”. The calculation result is read out from the memory by using a part of the identifier as an address in a program memory (not shown), and after updating the identifier, is output to the outside or is input to the ignition processing unit 87 again. These ignition processing units 87,
A cyclic pipeline is composed of the data processing unit 88 and a program memory (not shown).

In the example of FIG. 16, the input packet 81
Although the packet 82 having the same identifier “a” as the above is already stored in the queuing memory 85, the packet having the same identifier as the input packet 81 is queuing memory 8
If it is not stored in 5, the input packet 81 is stored in the queuing memory 85, and is made to wait until a packet having an identifier matching this is input.

As described above, the ignition processing section 87 has a function of searching for a packet to be calculated in the data driven computer and coalescing and outputting the packet having the same identifier.

In such a data driven computer, since the bit width of the identifier corresponds to the bit width of the program space, it becomes several tens of bits, and if a memory space is allocated for each identifier, the memory capacity becomes enormous. It becomes a thing. For this reason, conventionally, as a memory used for the queuing memory 85, a memory that compresses (hashes) the bit width under a certain rule and uses this as a memory address, that is, a hash memory is used.

FIG. 17 is a bit map diagram showing an example of the structure of an input packet, and FIG. 18 is a block diagram showing an example of the structure of a hash memory. The input packet shown in FIG. 17 is the 18-bit operand data OD to be operated.
And a 7-bit operation code OC, which is a code indicating the operation content, and a 1-bit processor selection bit P
S, 1 indicating whether the input packet is a 2-input command or a 1-input command
A 7-bit selection code SC for performing various selections, including an FC processing selection bit of a bit and a 1-bit left / right data selection bit indicating that it is placed on the left or right of a calculation location (node) according to the calculation order, and input data -Bit color / generation identification number DN indicating attributes such as input order
And a 21-bit node number NN indicating a place where an operation should be performed, totaling 62 bits, and a 31-bit identifier is constituted by the processor selection bit PS, the color / generation identification number DN, and the node number NN. .. However, when the processor selection bit PS is "1", the input packet is output after processing and sent to another processor, so that the processor number is stored in the upper 9 bits of the node number NN.

The hash memory 601 shown in FIG. 18 is accessed by using the lower 9 bits of the node number NN as a hash address, and a read / write signal W / bar R · H that determines a read / write cycle, write data, and A set / reset signal S / bar R for updating the presence bit PB indicating the validity / invalidity of each address is applied.

The write data stored in the hash memory 601 is 18-bit operand data OD,
9-bit color / generation identification number DN and node number N
The remaining 12 bits of N are 21 bits in total, and a total of 40 bits of 1 bit of processor selection bit PS. Separately from this, 1-bit presence bit PB is stored, and a total of 41 bits per word is formed. Further, the address space is 2 ⁹ = 512, and the hash memory 60
1 has a size of 41 bits / word × 512.

[0010]

The conventional data-driven computer is configured as described above, and the packets that cannot be stored in the waiting memory of the ignition processing section circulate randomly in the loop of the cyclic pipeline configuration. I was waiting for a free space in the waiting memory. When such overflow packets circulate in the loop, the pipeline becomes crowded. Further, since the overflow packets cannot fire together, there is a risk of deadlock, that is, execution stop. Further, when the hash memory 601 is used,
When accessing a hashed address (hash address), collision at the same address, so-called hash collision, may occur. That is, hash collision means that when a part of the identifier is used as a hash address and the hash address matches the data already stored in the hash memory 601, the remaining data that does not match the identifier is accessed. , This occurs because the address storing the data is already occupied.

Now, let us consider a case where a data driven computer in which the hash memory 601 is applied to the waiting memory 85 of FIG. 16 executes the data flow graph shown in FIG. 19 (a). In order to simplify the description, the hash memory 601 is accessed by using the lower 2 bits of the node number as a hash address and has a capacity enough to store four packets (address space = 2 ² =
4) will be described.

First, as shown in FIG. 19A, the number of nodes is 8 in this data flow, and six input packets are arithmetically processed. The second packet that is the left input of the node is also the left input of the node of number 7. The memory addresses that access the hash memory 601 are four memory addresses, and the node numbers and memory addresses in the data flow graph of FIG. 19A have a correspondence relationship as shown in FIG. 19B. At this time, in FIG. 19A, the first packet that is the left input of the node of number 3 (“011”) and the second packet that is the left input of the node of number 7 (“111”).
Since the lower 2 bits of the node number have the same value (“11”), the packet indicates the same memory address “3 (“ 11 ”)” of the hash memory 601.

In the case of a data driven computer, it is generally guaranteed that the same result can be obtained regardless of the data arrival order. However, the following problems occur when the hash memory capacity is small. That is, when the second packet is stored in the hash memory 601 before the first packet, the second packet waits for the third packet which is the right input of the node with the number 7, but the third packet is the number. It will not be generated unless the nodes 3, 5 and 6 are executed.
However, since the second packet has been stored in the hash memory 601 prior to the first packet, the second packet will not appear even after the third packet, which is the waiting partner, does not appear. Therefore, the second packet remains stored in the hash memory 601, and the first packet and the second packet are in a state of causing a hash collision. As a result, the first packet is no longer stored in the hash memory 601, so that the calculation of the node with the number 3 is not executed permanently, and the calculation process is eventually stopped.

When a data flow graph larger than the capacity of the hash memory 601 is executed in this way, a plurality of nodes may use the same memory address for firing, so hash collision may occur depending on the order of arrival of packets. However, there was a problem that the execution of the data flow graph was stopped halfway.

Therefore, as one of the means for solving such a problem, the present applicant uses not only a waiting memory using a hash memory but also a small-capacity (32-word) associative memory accessed simultaneously with the hash memory. It has already been proposed that a packet that cannot be stored in the queuing memory due to hash collision is stored in the associative memory and queuing is performed here. However, in the configuration in which the associative memory is provided, when a hash collision exceeding the capacity of the associative memory occurs, the same problem as described above occurs. This can be solved by increasing the capacity of the associative memory, but not only does the hardware configuration become large-scale, but when searching for a packet with a matching destination node number, all Since the address is searched, the whole pipeline processing speed is significantly reduced.

An object of the present invention is to avoid unnecessary congestion of the pipeline due to overflow packets,
(EN) It is possible to obtain a data driven computer capable of avoiding execution suspension due to congestion due to overflow packets or hash collision.

[0017]

SUMMARY OF THE INVENTION The present invention comprises a queuing memory for storing a packet having identification information and data including at least a destination node number indicating the location of an instruction to be executed next, and stored in the queuing memory. In a data-driven computer having a cyclic pipeline configuration having a firing processing unit that detects a packet in which at least a destination node number of a newly input packet and a newly input packet match, and performs a firing process to combine the matched packets,
The waiting memory includes a hash memory as the queuing memory, and a first firing processing unit provided with an OV flag which is set at each address of the hash memory when a hash collision occurs at the hash address and an overflow packet is output. And a second ignition processing unit having a hash memory for storing the overflow packet output from the first ignition processing unit with the same hash function as the hash memory and using a chain connection. The firing processing unit outputs the overflow packet generated by the hash collision to the second firing processing unit, sets the OV flag of the address in which the hash collision has occurred, and thereafter does not fire at the hash address in which the OV flag is set. The packet is sent to the second ignition processing unit The second firing processing unit compares the packet already stored in the hash memory with the newly input packet, and performs firing processing if there is at least a packet having the same destination node number, When the packet is the only packet connected to the chain from the hash address, the OVC flag added to indicate the fact to the ignition packet is set, and is output to the first ignition processing unit. The ignition processing unit 1 is configured to clear the OV flag of the hash address when the OVC flag of the input ignition packet is set.

[0018]

In the present invention, the packet that has overflowed from the conventional first ignition processing unit is sent to the newly provided second ignition processing unit, where the ignition processing is performed. At that time, the OV flag of the overflowed hash address is set, and thereafter only the packet having the hash address with the OV flag set is set to the first firing processing unit and the second firing processing unit. Matching is performed in both the ignition processing units. The OV flag is O when all the chain-connected packets corresponding to the relevant hash address of the second firing processing unit are fired and output.
It is cleared by the firing packet with the VC flag set. In this way, by providing a second ignition processing unit that accepts overflow packets and accessing both ignition processing units once overflow occurs, it is possible to prevent pipeline congestion and deadlock (execution stop) due to overflow. You can

[0019]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described below with reference to the drawings. FIG. 1 is a block diagram showing an embodiment of a data driven computer to which the present invention is applied. An ignition processing unit (first ignition processing unit) 101, an arithmetic processing unit 102, a program storage unit 103, a branch control unit 104. , A merge control unit 105 and an extended ignition processing unit (second ignition processing unit) 106. The firing processing unit 101 has a hash memory as a waiting memory, and sets an OV when an overflow packet is output due to a hash collision at the hash address at each address of the hash memory.
A flag is provided, and an EX flag indicating that the overflow packet is to be sent to the extended ignition processor 106 is set to “1” and output to the overflow packet caused by the hash collision, and the address in which the hash collision has occurred. O
Set the V flag. Further, when the hash address with the OV flag set is fired to become empty and a new packet is stored, the NS flag added to indicate that fact is set to “1”, Moreover, the EX flag is also set and output. Ignition processing unit 101
The packet output from the above to the cyclic pipeline is input to the branch control unit 104. In the branch control unit 104, based on the EX flag added to the packet, when the EX flag is not set (EX = 0), the packet including the data and the tag (identifier) is sent to the arithmetic processing unit 102 as in the conventional case. , EX flag is set (EX = 1)
Branches a packet including data, a tag, and an NS flag to the extended ignition processor 106.

The extended firing processor 106 uses the overflow packet as a waiting memory to fire the overflow packet.
The hash memory has the same hash function as the one hash memory and stores using a chain connection, and the packet already stored in this hash memory is compared with the newly input packet. Then, if there is a packet with at least the destination node number matching, the firing process is performed and the packet is output as a firing packet. However, when the other packet is the only packet connected to the chain from the hash address, the fact is notified to the firing packet. The OVC flag added for indicating is output, and when the NS flag is set for the packet, the PKC flag added for indicating to that effect is set and output. When the overflow packet is not fired, it is stored, but when the input packet with the NS flag set (the packet already stored in the firing processing unit 101) is not fired, the overflow packet is stored in the ignition processing unit 101. The packet is deleted to prevent the packet from being stored in both of the extended firing processors 106.

The ignition packet output from the extended ignition processor 106 is sent to the ignition processor 10 via the merge controller 105.
Input to 1. The ignition processing unit 101 allows the input ignition packet to pass through, but clears the packet stored at the hash address when the PKC flag is set, and clears the packet at the hash address when the OVC flag is set. Clear the OV flag. In addition,
The ignition packet output from the ignition processing unit 101 is input to the calculation processing unit 102 via the branch control unit 104, and the calculation result is updated in the tag in the program storage unit 103, and the ignition processing unit 101 is updated via the merge control unit 105. Will be entered again.

FIG. 2 is a block diagram of the ignition processing unit 101, which has already been proposed by the applicant of the present invention and has an associative memory in addition to the hash memory (Japanese Patent Application No. 3-122).
No. 338, etc.) shows a schematic configuration to which the present invention is applied, but it goes without saying that it can be applied to only a hash memory. As shown, this ignition processing unit 10
Reference numeral 1 is composed of a hash memory 1, an associative memory 2, a hash processor 3, a comparator 4, a controller 5, a selector 6, an operand exchanger 7 and the like, and is almost the same as that of the above-mentioned previous application. However, some function expansion is required to realize the above-mentioned functions. As the extension content, a field for storing the above-mentioned OV flag is added to each address of the hash memory 1 to newly add PKC, OVC, N described above.
That is, four signals of S and EX are added. This makes the operation of the control unit 5 somewhat complicated. FIG. 3 shows the hash memory storage data field, and FIG. 4 shows the control contents of the control unit 5.

FIG. 5 is a block diagram showing the detailed construction of the extended ignition processor 106. In the figure, 201 is an input packet such as an overflow packet sent without being fired by the ignition processing unit 101 due to hash collision, 202
Is a hash processor that compresses the address indicated by some bits of the tag to generate a hash address, 205 is an address translation table write data selector, 206 is an address translation table (CT), and 207 is an address for storing packets. Write address pointer (A
P), 208 is a chain rewriting register (CCR) that stores the address that has been read immediately before, 209 is a read address register (RR) that stores the address that has been read last, 210 is an address selector,
211 is a packet memory for storing the input packet, 212 is a chain pointer memory for storing the chain relation of the packet memory 211, 213 is a chain address register (CAR) for storing the chain address CA,
Reference numeral 214 is a chain bit register (CBR) that stores the chain bit CB, 215 is a chain pointer write selector that selects write data of the chain pointer, and 216 is a comparison between the tag of the input packet 201 and the tag read from the packet memory 211. Comparator,
A control unit 217 controls the entire operation. Note that all registers are updated when reading the memory. The hash function of the hash processor 202 is set to be the same as that of the hash processor 3 of the ignition processor 101 described above.

As shown in FIG. 6, the address conversion table 206 is composed of a plurality of areas which can be designated by a table search key, and stores a packet storage address PA indicating a packet storage address in the packet memory 211. When the storage address portion 223 and the valid packet storage address PA are stored, PB = 1,
Presence bit PB with PB = 0 if not stored
And a presence bit unit 222 for storing the address, and the hash address output from the hash processor 202 is accessed as a table search key, and this search key is converted into an address of the packet memory 211 to be searched. FIG. 6 shows that the packet searched by the table search key is stored at the address n ₁ of the packet memory 211.

As shown in FIG. 7, the packet memory 211 and the chain pointer memory 212 are composed of a plurality of areas which can be designated by the packet storage address PA. The packet memory 211 has a tag section 21 for storing tags.
8 and a data section 219 for storing data, and the chain pointer memory 212 has a chain bit section 220 for storing a chain bit CB and a chain address C.
And a chain address part 221 for storing A. For example, if the address n ₁ is accessed by the packet storage address PA, the packet having the tag = T ₁ and the data = D ₁ stored at this address n ₁ is read from the packet memory 211 and the chain bit CB. = 1 and the chain address CA = n ₁₁ are read from the chain pointer memory 212.

The chain bit CB = 1 indicates that there is another packet having the same hash address as the tag T _1, and the chain address CA indicates the address where the packet is stored, and CB = 0. The case indicates that there are no more packets having the same hash address. For example, the example of FIG. 7 indicates that packets having the same hash address are stored at the addresses of the packet memory 211 having the packet storage addresses PA of n ₁ , n ₁₁ , and n ₁₃ .

Next, the general operation of the extended ignition processor 106 will be described with reference to the flowchart of FIG.
First, in step S1, it is determined whether or not the NS flag of the input packet 201 is set to "1", that is, whether the packet is already stored in the ignition processing unit 101 or is an overflow packet. In the case of an overflow packet, since the NS flag is not set and is "0", the process proceeds to step S2, it is determined whether or not a fire has occurred, and if it does not fire, it is stored (step S3). If the packet is fired in the determination in step S2, the process proceeds to step S4 and it is determined whether or not the packet of the other party of firing is the only packet connected to the chain from the hash address. If it is not the only packet, OVC flag, P
Without setting the KC flag (OVC = 0, PKC =
0), and output as an ignition packet 224 (step S
5). If it is the only packet, only the OVC flag is set (OVC = 1, PKC = 0) and output as the ignition packet 224 (step S6). On the other hand, if the input packet 201 is already stored in the ignition processing unit 101, the NS flag is set and “1” is set.
Therefore, the process proceeds from step S1 to step S7, it is determined whether or not a fire is generated, and if it is not fired, it is erased to prevent duplicate storage (step S8). If the packet is fired in the determination in step S7, the process proceeds to step S9 and it is determined whether or not the packet of the other party of firing is the only packet connected to the chain from the hash address. If it is not the only packet, only the PKC flag is set (OVC = 0, PKC = 1) and output as an ignition packet 224 (step S10). If it is the only packet, both the OVC flag and the PKC flag are set (OVC = 1, PKC = 1), and the packet is output as an ignition packet 224 (step S11).

Next, taking an overflow packet as an example, details of packet storage and firing processing using a chain connection will be described with reference to the flowchart of FIG. It should be noted that the input packet, which has already been stored in the ignition processing unit 101 and has the NS flag set, is substantially the same except that it is deleted when it is not fired. In addition, the detailed contents of each process denoted by (1) and (2) in FIG. 9 are shown in FIGS. First, the input packet 201
When the overflow packet is input as, the hash address is generated by compressing the tag of the overflow packet in the hash processor 202,
The address conversion table 206 is searched by the generated hash address (step S1). As a result, if the presence bit PB of the address in the address conversion table 206 indicated by the hash address is "0" (step S2), it means that no packet is stored. The address is stored in the address of the packet memory 211 designated by the write address pointer 207, and the presence bit PB of the conversion table 206 is rewritten to "1" (step S3, see FIG. 10 for details).

In step S2, if the presence bit PB of the table address indicated by the hash address is "1", the control unit 217 causes the selector 210 to operate.
To the output side of the address conversion table 206, and
The packet storage address PA read from the table address with B = 1 is input as a search address of the packet memory 211 through the selector 210,
The packet stored at the address indicated by the packet storage address PA is read (step S4, FIG. 11).
See).

The tag of the packet read from the packet memory 211 is input to the comparator 216, and is compared with the tag of the overflow packet input here, and if the tags match as a result (step S5), it is fired. The address is cleared as the process is performed (step S6, see FIG. 12). These packets are combined and output as an ignition packet 224, and the merging control unit 10
5, transferred to the ignition processing unit 101, the branch control unit 104, and the arithmetic processing unit 102.

In step S5, the packet memory 2
If the tags of the packet read from 11 and the input overflow packet do not match, the chain bit CB read from the chain pointer memory 212 and stored in the chain bit register (CBR) 214 is “0”. Whether or not there is another packet having the same hash address depending on whether it is "1" or not (step S7), and if CB = 0, the input overflow packet is stored in the packet memory 211 (step S8, FIG. 13). See). On the other hand, if CB = 1, there is another packet having the same hash address, so the chain address register (CAR) 213
The packet memory 211 is searched according to the chain address CA stored in (step S9, see FIG. 14). This is because the chain address CA read from the chain pointer memory 212 and set in the chain address register (CAR) 213 is the selector 21.
It is performed by inputting the address of the packet memory 211 through 0. As a result, the chain address C
A packet having the same hash address as the previously read packet is read from the address indicated by A. The tag of this packet is input to the comparator 216 in the same manner as the previous packet, and is compared with the overflow packet input here. As a result, if the tags match (step S10), the firing process is performed and the address is cleared (step S11, see FIG. 15). These packets are the same as the above, and the ignition packet 22
4, the merge control unit 105 and the ignition processing unit 10 are combined.
1, the branch control unit 104, and the arithmetic processing unit 102. However, if the tags do not match, the process returns to step S7, and the processes after step S7 are repeated.

As described above, in the present embodiment, when an overflow occurs in the ignition processing unit 101 using a hash memory, an overflow packet is sent to the extended ignition processor 106, and the OV flag of the hash memory in which the collision has occurred. Set. When the ignition processing unit 101 does not fire and the hash address is an empty address,
When the OV flag is "1", the packet is the ignition processing unit 1
However, the extended ignition processor 106 is also accessed. If the ignition processing unit 101 does not ignite, and the extended ignition processor 106 fires, the extended ignition processor 10
The packet fired in 6 clears the packet already stored in the firing processing unit 101 when passing through the firing processing unit 101. If the extended firing processor 106 does not fire, the packet is erased in the extended firing processor 106 to prevent the packet from being redundantly stored. If there is no empty address in the ignition processing unit 101, it is stored as a matter of course. The OV flag is cleared by the firing packet with the OVC flag set when all the chain-connected packets corresponding to the relevant hash address of the extended firing processor 106 are fired and output. That is, the packet is stored in either the firing processing unit 101 or the extended firing processing unit 106, and both the firing processing unit 101 and the extended firing processing unit 106 are accessed with respect to the address in which the OV flag is set.

As a result, unnecessary congestion of the pipeline due to overflow packets can be avoided, and deadlock due to congestion due to overflow packets and hash collision, that is, execution suspension, can be avoided. The extended ignition processor 106 can be configured with a small amount of logic and the usual DRAM and SRAM, and is reasonably priced.

In the above embodiment, the ignition processing unit 101
In, when the hash address with the OV flag set fires and becomes empty, and a new packet is stored, the NS added to the packet to indicate that fact.
Although the flag is set to "1" and is output to the extended firing processor 106, even if the hash address in which the OV flag is set is fired and becomes empty, the OV flag is set as long as it remains set. Even if a new packet arrives at the hash address, it may be output as an overflow packet to the extended ignition processor 106 without being stored. In this case, the extended ignition processor 106 and the ignition processing unit 10 are provided.
It is not necessary to delete or clear the corresponding packet in 1 and the related NS flag and PKC flag are also unnecessary. Further, in the above embodiment, all packets are output from the firing processing unit 101 onto the cyclic pipeline, and the branch control unit 104
Although the overflow packet or the like is branched to the extended ignition processor 106 based on the EX flag, the packet may be directly transmitted from the ignition processor 101 to the extended ignition processor 106. In this case, the branch control is performed. Part 1
04 and the EX flag are unnecessary.

[0035]

As described above, according to the present invention, a hash memory is provided as a waiting memory, and an OV flag set when an overflow packet is output at each address of this hash memory when a hash collision occurs at the hash address. A hash memory that includes the first firing processing unit that is provided and that stores an overflow packet output from the first firing processing unit as a waiting memory with the same hash function as the hash memory and using a chain connection is provided. And a second ignition processing unit having the second ignition processing unit, wherein the first ignition processing unit outputs the overflow packet generated by the hash collision to the second ignition processing unit, and sets the OV flag of the address causing the hash collision. , And thereafter, the hash address with the OV flag set The packet which is not fired at is output to the second firing processing unit, and the second firing processing unit compares the packet already stored in the hash memory with the newly input packet, and at least the destination node number is If there is a matching packet, the firing process is performed, and if the packet is the only packet connected to the chain from the hash address, the OVC flag added to indicate the fact is set in the firing packet. It outputs to the first ignition processing unit, and the first ignition processing unit clears the OV flag of the hash address when the OVC flag of the input ignition packet is set. It is possible to avoid unnecessary congestion of the pipeline due to congestion, congestion due to overflow packets and hash collision. There is advantage of the ability to avoid the execution stop due to.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of a data driven computer according to an embodiment of the present invention.

FIG. 2 is a configuration diagram showing an embodiment of an ignition processing unit in FIG.

FIG. 3 is a diagram showing a hash memory storage data field of FIG. 2;

FIG. 4 is a diagram showing control contents of a control unit in FIG.

5 is a detailed configuration diagram showing an embodiment of the extended ignition processor of FIG.

6 is an explanatory diagram of a configuration of an address conversion table shown in FIG.

FIG. 7 is an explanatory diagram of configurations of a packet memory and a chain pointer memory in FIG.

FIG. 8 is a flowchart showing the overall operation of the extended ignition processor of the embodiment.

FIG. 9 is a flowchart showing a detailed operation of the extended ignition processor of the embodiment.

FIG. 10 is a flowchart showing details of packet storage (1) in FIG.

11 is a flowchart showing details of packet search (1) in FIG. 9. FIG.

FIG. 12 is a flowchart showing details of address clear (1) in FIG.

13 is a flowchart showing details of packet storage (2) in FIG.

14 is a flowchart showing details of packet search (2) in FIG. 9. FIG.

15 is a flowchart showing details of address clear (2) in FIG.

FIG. 16 is an explanatory diagram showing the concept of data processing of a conventional data driven computer.

FIG. 17 is a bit map diagram showing an example of the structure of a packet.

FIG. 18 is a block diagram showing a configuration of an example of a hash memory.

FIG. 19 is an explanatory diagram showing the relationship between an example of a data flow graph and memory addresses and node numbers.

[Explanation of symbols]

 1 Hash Memory 2 Associative Memory 3,202 Hash Processor 4,216 Comparator 5,217 Control Unit 101 Ignition Processing Unit (First Ignition Processing Unit) 102 Arithmetic Processing Unit 103 Program Storage Unit 104 Branch Control Unit 105 Confluence Control Unit 106 Extended Fire Processor (Second Fire Processor) 206 Address Conversion Table 211 Packet Memory (Hash Memory) 212 Chain Pointer Memory

─────────────────────────────────────────────────── ───

[Procedure amendment]

[Submission date] June 4, 1992

[Procedure Amendment 1]

[Document name to be corrected] Drawing

[Name of item to be corrected] Fig. 4

[Correction method] Change

[Correction content]

[Figure 4]

Claims (1)

Claims: 1. A queuing memory for storing a packet having identification information and data including at least a destination node number indicating a location of an instruction to be executed next, and the packet stored in the queuing memory. In the data-driven computer having a cyclic pipeline structure having a firing processing unit that detects a packet in which at least the destination node number of the newly input packet and the destination node number match and performs a firing process to combine the matched packets, the waiting memory As a queuing memory, and has a first ignition processing unit having an OV flag to be set when a hash collision occurs at the hash address and an overflow packet is output at each address of the hash memory. 1 is output from the ignition processing unit A second ignition processing unit having a hash memory for storing an overflow packet with the same hash function as the hash memory and using a chain connection is provided, wherein the first ignition processing unit is an overflow packet generated by a hash collision. Is output to the second firing processing unit, and the OV flag of the address in which the hash collision has occurred is set, and thereafter, the packet that does not fire at the hash address with the OV flag set is output to the second firing processing unit, The second firing processing unit compares the packet already stored in the hash memory with the newly input packet, performs firing processing if there is at least a packet having a matching destination node number, and If the only packet connected to the chain from the hash address is An OVC flag added to indicate the fact to the ignition packet is set and output to the first ignition processing unit, and the first ignition processing unit has the OVC flag of the input ignition packet set. A data-driven computer characterized by clearing the OV flag of the hash address at that time.