JPH02196385A - Data driving type computer - Google Patents

Abstract

PURPOSE:To reduce a hardware scale while omitting a redundant input address latch and a decoder, etc. by integrating an instruction fetching part and a desti nation designating part in one program memory, and placing this program memory in parallel to an instruction executing part. CONSTITUTION:A program memory 11 in which both an instruction code and a destination node number are stored is placed in parallel to an instruction executing part 12. Accordingly, an execution processing of the present instruction, and a readout processing of the next instruction and the destination node number are executed in parallel, and by total two cycles of this cycle and a data waiting cycle in a coincidence detecting part, the execution of one instruction is completed. In such a way, the data processing time is shortened, and also, a data driving type computer in which an unnecessary hardware is curtailed can be formed.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a so-called data-driven computer that employs a method of driving processing based on mutual dependencies between data to be processed.

[Prior art] Typical examples of conventional data-driven computers are pages 19 to 22 of the Proceedings of the Conference on Research and Development Results of High-Speed Computing Systems for Science and Technology (June 25, 1980) and IE Pulmonary CO.
MPCON '845PRING Proceedings (English) 48
It is disclosed on pages 6 to 490. All of these publicly known materials describe the configuration and operation of a data-driven computer called Sigma-1. The prior art will be described below based on these publicly known materials.

FIG. 5 shows the configuration of the conventional data-driven computer mentioned above.

This data-driven computer includes a network interface 14 that is an interface with the outside of the computer, a matching memory 10 that detects two pieces of data with matching destination node numbers from each data to be processed, and a calculation based on the node number. An instruction fetching section 15 that extracts the instruction code, an instruction execution section 12 that executes arithmetic processing according to the instruction code, a destination specifying section 16 that specifies the next destination node number of data after the arithmetic processing, and data that connect these. It consists of routes.

In addition, Figure 4 is a program (data flow graph) for explaining the specific operation of a conventional data-driven computer.
This is an example.

This data flow graph connects data A and B to node #
0, and add this resultant data G and another data C
are multiplied at node #2 to obtain the resulting data ■, and on the other hand, data D and E are added at note #1, and the resulting data H and another data F are added to node #4.
Multiply at node #7096 to obtain the resultant data J... Then, multiply data W and Find the result data Z.
It is structured as follows.

A packet (data having tag information) input from the outside via the network interface 14 Δ(201
) is composed of destination node number <0> and data [A]. This packet 201 is sent to the matching memory 10, but at the same time, the destination node number <O> (203) in the packet 201 is sent to the matching memory 10.
It will also be sent to 5. Assuming that packet B containing data [B], which is the target of a binary operation on data [A], has already been input and is waiting in the matching memory 10, the destination nodes of these two packets A and B are Since they both match #0, the matching memory 10 outputs a packet 206 that is a pair of data [A] and data [B].

On the other hand, the instruction fetching unit 15 reads and outputs the instruction code "+" (205), which is the content of the address corresponding to node number <0>.

The memory configuration of the instruction fetching unit 15 is shown in FIG. 6 (al).

Next, the destination node number input to the instruction fetching unit 15 <Q
> is sent as is to the destination specifying unit 16 as the node number <O> (20). Further, the instruction code r + J (205) read out by the instruction extraction unit 15 is given to the instruction execution unit 12 as a packet 207 together with the packet 206 of the data pair [A] and [B]. At this time,
In the destination specifying unit 16, the result data of the addition which is the operation corresponding to the node number <0> in the data flow graph of FIG. 4 represents the next node 12 to go to <2>.
(208) is read out.

The memory configuration of the destination specifying unit 16 is shown in FIG.

At the same time, in the instruction execution unit 12, [A]+[B]
The calculation is performed, and the calculation result data [G] (209)
is output. The output 208 of the destination designation unit 16 and the output 209 of the instruction execution unit 12, that is, the destination node number <0> and data [G], pass through the network interface 14 as a packet 210, and are sent to the instruction extraction unit 15 and the matching memory again. Sent to 10.

Through the chain of processing as described above, operations corresponding to all nodes of the data flow graph shown in FIG. 4 are performed, and the execution of the program is completed. At this time, the processes at the nodes where there is a data dependency relationship, for example, node #0 and node #2, can only be executed sequentially in this order.
Nodes where no data dependencies exist, e.g. node #
Processing in O and node #1 can be executed in parallel as far as processing resources allow.

Note that a data dependency relationship here refers to a connection relationship between two nodes in which the completion of the processing of one node immediately supplies the input data necessary to perform the processing of the other node. It refers to something in

The memory configurations of the instruction fetch unit 15 and the destination designation unit 6 are shown in FIGS. Here, it is assumed that the bit width of the instruction code is 4 bits and the bit width of the destination node number is 16 bits.

Furthermore, since the above-mentioned publicly known materials do not have any specific description regarding data copy operations, it was assumed that a widely and generally known method would be used for data copying.

The most significant bit “co” in the memory in the destination designation unit 16
py'' is a copy bit, and when the calculation result at a certain node in the data flow graph shown in Figure 4 is sent to multiple nodes, data is copied and the destination node number is assigned to each data. For example, in response to the calculation result at node #2 being sent to both node #7097 and node 5, the copy bit at the second address of the memory is set to “1”. In this case, the destination node number #7097 is read out and added to the calculation result [11] and output, and then the next battlefield (3rd address) is read out continuously and the destination node number is I5 is added to the same calculation result [1 and output.

[Problem to be solved by the invention]

However, conventional data-driven computers have two problems.

The first problem is that the program memory is large. In the case of the Neumann computer which is currently widely used, processing is performed sequentially according to the order written in the program, so the execution address is centrally managed by a single register called a program memory. Therefore, except for branch instructions, there is no need to specify the address of the next instruction to be executed (jump address), and programs with the same content can be stored in a smaller program memory than data-driven computers. can. On the other hand, in the case of a data-driven computer, each instruction is processed in parallel, so it is impossible to centrally manage execution addresses. For this reason, in data-driven computers, it is necessary in principle to specify the address of the next instruction to be executed (destination node number) for every instruction, which causes the size of the program memory to expand. It has become. In the above-mentioned conventional example as well, the destination node number occupies 16 bits out of the 21-bit bit width (instruction code 4 bits + destination node number 17 bits) per instruction.

The second problem is that the program memory is separated into an instruction fetch section and a destination specification section. For this reason, as shown in Figure 6 FaL (bl), if we focus on a certain node, even though the input addresses to these two memories are exactly the same, they are in different pipeline stages. Since accesses are not performed simultaneously, unnecessary processing time is required, and it is necessary to provide two independent sets of input address registers and address decoders, which unnecessarily increases the hardware scale.

Regarding the first problem mentioned above, the inventors of the present application have previously proposed a data-driven computer aimed at solving the problem in the invention of Japanese Patent Application No. 63-000000.

In view of the second problem, the present invention aims to provide a data-driven computer that reduces data processing time and eliminates unnecessary hardware.

[Means to solve the problem]

The data-driven computer of this specification integrates the instruction fetch function and destination specification function of conventional data-driven computers into one program memory, and arranges this program memory in parallel with the instruction execution section, thereby eliminating redundant functions. The input address launcher or decoder is eliminated, reducing the hardware scale.

In addition, by arranging the program memory and instruction execution section in parallel, the basic cycle for executing one instruction consists of two pipeline stages: ■ matching memory and ■ (program memory + instruction execution section). are doing.

[Effect]

In the data-driven computer according to the present invention, the program memory storing both the instruction code and the destination node number is arranged in parallel with the instruction execution unit, so that the execution process of the current instruction and the next instruction and destination node The number reading process is performed in parallel, and execution of one instruction is completed in a total of two cycles: this cycle and the data waiting cycle in the coincidence detection section.

[Embodiments of the invention]

DESCRIPTION OF THE PREFERRED EMBODIMENTS The present invention will be described in detail below based on drawings showing embodiments thereof.

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

The data-driven computer of the present invention includes a network interface 14 which is an ink interface with the outside, a matching memory 10 which is a matching detection unit which detects two pieces of data having matching destination node numbers from each data to be processed, and a node A program memory 11 has two functions: one to extract the code of an arithmetic instruction based on the number, and the other to specify the next destination node number of the data after the arithmetic processing. It is composed of an instruction execution unit 12, an adder 13 as an arithmetic means for updating the destination node number, and a data path connecting them.

The operation of the data-driven computer of the present invention when executing the program (data flow graph) shown in FIG. 3 will be described. The data flow graph shown in FIG. 3 is the same program as the program shown in FIG. 4 described above, but the node numbers are assigned differently for the purpose of explaining the present invention.

This data flow graph connects data A and B to node #
O, add this result data G and another data C
are multiplied at node #2 to obtain the resulting data I, and on the other hand, data D and E are added at node #1, and the resulting data G and another data C are added to node #5.
Multiply at node #7096 to obtain the resultant data J... Data W and X are multiplied at node #7096, and this resultant data Y and the previously obtained data
7097 to calculate the resultant data Z.
It is structured as follows.

A packet 101 input from the outside via the network interface 4 includes a destination node number <0>, data [A], and an instruction code ``+j''.

In the data-driven computer of the present invention, two-cycle pipeline processing is performed. The first stage is the waiting of data in the matching memory 10. A packet 101 input from the outside is sent to the matching memory 10, but at this time, the data [B
] has not arrived, the input packet 101 is temporarily stored in the matching memory and waits for the packet containing data [B] to arrive. Additionally, if a packet containing the other data [B] has already arrived and is stored in the matching memory, it is detected that the destination node numbers <0> of these two packets match. , a packet 102 obtained by adding data [B] to the input packet 101 is sent out from the matching memory 10.

Among the information contained in the packet 102, the destination node number <Q> (103) is sent to the program memory 11 and the adder 13, which will be described later, and the remaining data [A] [B
] and the instruction code “+” are sent to the instruction execution unit 12 as a packet 104.

In the instruction execution unit 12, data [A] and [B] are added according to the instruction code "+", and the addition result data [
G] (107) is output.

On the other hand, the processing in the program memory 11 that is executed in parallel with the processing in the instruction execution unit 12 will be described below.

FIG. 2 shows the memory configuration of the program memory 11 of the data-driven computer according to the present invention.

In the memory shown in Figure 2, the seven most significant bits of each word "
EXT'' is an extended address flag to be described later.

The lower side Bisobi C0PY” is “c0PY” in the conventional example.
This “C0PY” bit has the same meaning as the “opy” bit.
If the bit is "1", this indicates that there are a plurality of destination nodes for the operation result, and that the instruction code and destination node number information regarding each of these destination nodes are stored at the next address or later.

The lower 4 bits 1~ following this “copy” bit are:
Instruction code (OPECODE) to be executed in the next cycle
) is stored in the lower 6 bits,
If the destination node number is a relative address to the current node number (
RNODE>.

The specific operation of the data-driven computer of the present invention as described above will be explained.

When packet 10] is detected as a match in matching memory 10 and packet 102 is output, packet 1
The node number <O> (103) of 02 is input to the program memory 11. As a result, address 0 of the memory shown in FIG. 2 is accessed, the instruction code "+" and the relative destination node number 2> are read out, and the instruction code register (OPE-REG) 131 and the destination node are read out. Each number is written to the number register (DEST-REG) 132.

The instruction code is output as is from the instruction code register 131. On the other hand, the relative destination node number <2> is sent from the destination node number register 132 to the adder 13, and in the adder 13, the input node number <<
O> (103) is added to obtain the absolute value of the destination node number <2> (106).

The instruction code “+” obtained in this way, the one-line destination node number <2>, and the data output from the instruction execution unit 12 [
The packet 10B configured in
The entire program is executed by repeating this process.

However, in the present invention, since the memory bit width of the program memory 11 that stores the relative destination node number is limited to 6 bits, the actual value of the relative destination node number is 255 bits.
(= 2! -1), overflow occurs.

For example, node # in the data flow graph in Figure 3
This corresponds to the relative destination node number corresponding to the arrow from 2 to node #7079. In such a case, by setting the most significant bit "EXT" of the program memory corresponding to each node number to '1', the next address can be used as an extended address bit area to store the overflow digit. The present invention is configured so that this is possible.

The input data [G] and 1C] necessary for the processing at the node 112 in FIG.
] and [C] is output.

As described above, the instruction code and data are sent to the instruction execution unit 12, multiplication is executed, and result data [1] is output. In parallel with this, the destination node number <2> is sent to the program memory II, and the destination node number is read out.

The detailed logical operation of the program memory 11 when the input node number is <N> is shown in the flowchart of FIG.

In this flowchart, rREAD MJ is an operation to read address M of the memory, and pin-(6:0), etc. are bit strings consisting of bits 6 to 0.
EXT" and "copy" respectively represent the values of the extended address flag bit and the copy flag bit in the program memory.

When a packet with destination node number <2> is input to the program memory 11, the second
The contents of the address are read (step S4).

Of the read contents, the instruction code "+" is written to the instruction code register 131, and the relative destination node number <4> is written to the lower 6 bits of the destination node number register 132, that is, bit (6: O). (Step S5
．． S6).

Since the “EXT” bit of the read word is “0” (
Step S7), the result of adding the instruction code and destination node number register value <4> with the input node number <2> by the adder 13, <6>, is output as the destination node number (Step S8) .

At this time, the “copy” bit of the read word is “1”.
'', the read address <2> is incremented (step 510), and after clearing the loop count <L> and the contents of the destination node number register 132 (steps S2 and S3), the third address which is the address after the increment is is read out (step S4).

As with the first read, the instruction code “+” in the read word and the relative destination node number <55> (-“110
111") are written into the lower 6 bits of the instruction code register 131 and the destination node number register 132, respectively (steps S5 and S6).
” bit is “1” (step S7), the read address is incremented (step 511), the contents of the fourth address are read, and the lower 10 bits of the read word are stored in bit 15 of the destination node number register 132. to bit 6 (step 513).

Since the value of the EXT bit of the last read word is "BI" (step 515), the current instruction code r+J and the contents of the destination node number register 132 <7095>
(-“0001101110110111”) and the input node number 112, the addition result <7097> is output (step S8).

Also, the value of the copy bit of the last read word is “
0'' (step S9), the series of processing for the input packet lift having the node number <2> is completed.

As mentioned above, when the destination node number is given as a relative destination node number, even if the relative destination node number overflows beyond the predetermined bit width, the next address in the program memory is set to the extended address of the relative destination node number. Processing is completed by using the area as an area, and the present invention is applicable to programs of any size and to which node numbers are assigned.

Generally, since connections between nodes are local, it is considered that the relative destination node number rarely takes a large value, regardless of the program scale.

In fact, for a test program consisting of 3987 nodes, we evaluated the statistical distribution of relative destination node numbers when node numbers were assigned in such a way that nodes closest to the input were given smaller node numbers. . The results are shown in the graph of FIG. The turret axis of the graph shows the relative destination node number, the line axis shows the cumulative frequency percentage, and the number for each section shows the number of nodes included in that section.

From the graph of FIG. 8, it is easily understood that about 90% (88χ) of the total have relative destination node numbers within address 63. In other words, the bit width of the relative destination node number is set to 6.
Even as a bit, this means that there is about a 10% possibility that the expansion pin 1- as described above will be necessary.

The bit width of the program memory in the conventional example is 2] bits (4 bits in the instruction fetch section + 17 bits in the destination specifying section), but in the case of this embodiment it is 12 bits, and when the present invention is implemented, Even if the number of extra words required to store the extended address is 10% from the double statistics, the memory size will be compressed by (12 x 1.1) / 21 = = 0.63 times. . In this embodiment, the program memory space is 16 bits, but this compression effect becomes more noticeable as the program memory space becomes larger.

For example, if the program memory space is 32 bits, even if you expand the relative destination node number space to 8 bits and estimate that the proportion of extended address bits required is 20%, the memory size will be (relative destination node number →-flag + instruction code) Xl,
2 (destination node number 10 flag + instruction code),
Substituting the actual number of bits doubles it, making it possible to compress it to less than half.

Note that in the above embodiment, the relative destination node number is limited to a positive number to simplify the explanation, but by using a signed number (two's complement representation), a node number smaller than the output side node number can be used. It becomes possible to send data to nodes with

As a result, the present invention can be applied to programs including repetitive structures.

Furthermore, in this embodiment, the overflow bit of the relative destination node number is assigned to the extension bit, but another method is to divide the program into pages and set the address within the page to, for example, 6.
It is also possible to use a method of assigning a relative page number to an extension bit when there is a destination node beyond the page.

〔Effect of the invention〕

As explained above, in the data-driven computer of the present invention, the instruction number section and destination specification section of the data-driven computer shown in the conventional example are integrated into one program memory, and this program memory is By arranging it in parallel with the instruction execution section, redundant input address launches, decoders, etc. can be omitted, and the hardware scale can be reduced.

In addition, by arranging the program memory and instruction execution section in parallel, the basic cycle for executing one instruction consists of two pipeline stages: ■ matching memory and ■ "program memory + instruction execution section". Therefore, a short basic cycle comparable to that of conventional data-driven computers can be obtained, and the response time to a single command can also be kept short.

In general, data-driven computers are built on a computational model suitable for parallel distributed processing, and have the distinctive feature of autonomously executing multiple tasks in parallel without any special control. It is considered. However, in the case of the current system where the address of the program memory that stores each multitask is fixed,
Other tasks Tb that may share the program memory area with the currently executing task Ta cannot be executed at the same time even if there is free space in the program memory. Therefore, the reality is that the current Data\7Arpj+ type computer cannot fully utilize its inherent feature of being suitable for multitasking.

In contrast, in the data-driven computer of the present invention, the node number of every node is specified by the relative destination node number from other nodes, so if there is free space in the program memory, it is independent of the absolute address. , a new task can be externally loaded into any free space and executed in parallel with other tasks.

The above describes multitasking execution on one processor, but as shown in Figure 9, it is possible to make the individual tasks spanning each processor occupy the same program memory area within each processor. For example, it is possible to have multiprocessors that communicate packets with each other via a network execute multitasks and generate tasks, making it easy to perform high-speed parallel distributed processing using multiple data-driven computers. It can be realized.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of a data-driven computer according to the present invention, and FIG. 2 is a memory configuration of a program memory of the data-driven computer according to the present invention, and more specifically, the program shown in FIG. 3 is stored. FIG. 3 is a schematic diagram showing an example of a program (data flow graph) executed by the data-driven computer of the present invention, and FIG. 4 is a diagram of a conventional data-driven computer. Fig. 5 is a schematic diagram showing an example of a program (data flow graph) to be executed in a conventional data-driven computer. 6 (al is a diagram showing the memory configuration of the instruction fetching section in a conventional data-driven computer, and FIG. 6 (bl is a schematic diagram showing the memory configuration of the destination specifying section. FIG. 4 shows the memory contents when the program shown in FIG. The graph showing the distribution, FIG. 9, is a conceptual diagram showing a map of program memory in the execution state of multitask in a multiprocessor configuration. 10...Matching memory 11...Program memo I2...Instruction execution In the figures, the same reference numerals indicate the same or corresponding parts.

Claims (1)

[Claims] (1) A match detection unit that detects two pieces of data that have matching destination node numbers attached to each data to be processed; An arithmetic processing unit performs arithmetic processing according to the instruction code, and the content is read out using the destination node number attached to the data processed by the arithmetic processing unit as an address, and the data is processed based on the read content. A program memory for updating a destination node number and an instruction code, and concurrently performing arithmetic processing on two pieces of data whose destination node numbers have been detected to match by the coincidence detection unit and updating the destination node number and instruction code. A data-driven computer, characterized in that the arithmetic processing section and the program memory are connected in parallel to the coincidence detection section for execution.