Data driven type apparatus and method with router operating at a different transfer rate than system to attain higher throughput

ABSTRACT

A router is formed by an M-input, 1-output junction unit and a 1-input, N-output branching unit. Where M and N satisfy the relation of (M>N), the transfer rate of a path between the junction unit and the branching unit is made the total sum of the transfer rates of inputs of INto INM, whereby N times faster transfer becomes possible.

INFORMATION

DETAILED DESCRIPTION OF THE INVENTION

DESCRIPTION OF THE PREFERRED EMBODIMENTS

FIG. 1 is a block diagram showing a 2×2 double rate transfer router in accordance with one embodiment of the present invention. In the 2×2 router in accordance with the embodiment shown in FIG. 1, the transfer rate at the junction unit is made double the maximum transfer rate in the data driven type processor, namely, the transfer rate of the C element in the router is doubled. The router is a 2-input, 2-output router formed by one branching unit shown in FIG. and one junction unit shown in FIG. . The router has 2×2=4 different paths.

In FIG. 1, the transfer rate of a path is made double the input rate or output rate of the router. More specifically, the amount of delay provided by a delay element (delay element shown in FIG. 10) on a SEND output line in the C element (C element shown in FIG. 16) of junction unit and the amount of delay provided by the delay amount on the SEND output line in the C element (C element shown in FIG. 14) of branching unit are adjusted (for example, the number of stages of the inverter in delay element is reduced to half the number of stages of the inverters in the delay elements of C element used in the data driven type processor), so that the transfer rate of the C element in the junction unit and the transfer rate of the C element in the branching unit is made double the maximum transfer rate of the data driven type processor.

Referring to FIG. 1, the data input to junction unit at the maximum transfer rate from IN to IN are joined with the maximum transfer rate. As the transfer rate of path is double the input rate or the output rate of the router, the data can be passed through the path and transferred to branching unit with the transfer rate not lower than the maximum transfer rate. The two input data are branched to OUT and OUT at branching unit and as the C element in branching unit has the double transfer rate, each of the data can be output at the maximum transfer rate.

As compared with the conventional 2×2 router shown in FIG. 13, the embodiment of the present invention provides the following advantages.

1) As there is only one junction unit and only one branching unit, circuit scale is not increased.

2) As the transfer rate in the router is doubled, input to the router and output from the router at the maximum transfer rate, not lowering the transfer rate, are possible.

3) As the delay element is formed by the inverters, increase in circuit scale can be avoided, and the delay elements can be formed easily in a simple manner.

FIG. 2 is a block diagram of a 4×4 quadruple rate transfer router in accordance with another embodiment of the present invention. The router of the present embodiment provides 4×4=16 different paths, and it is a 4-input, 4-output router formed by the 1-input, 4-output branching unit in the prior art FIG. and three 2-input, 1-output junction units shown in FIG. . In the transfer section between each of the junction units , and and the transfer section from junction unit to branching unit , the transfer rate is doubled.

In FIG. 2, the transfer rate of the path is four times the input rate or the output rate of the router. More specifically, the delay element on the SEND output line in the C element of junction unit and the amount of delay of the delay element on the SEND output line in the C element of junction unit are adjusted (for example, the number of stages of the inverter in the delay element is reduced to one fourth the number of stages of the inverters in the delay element of C elements used in the data driven type processor), so that the transfer rate between the C element in the junction unit and the C element in the branching unit is four times the maximum transfer rate in the data driven type processor. Similarly, the transfer rate between the C element in junction unit and the C element in the JCTL circuit of junction unit , as well as the transfer rate between the C element in the junction unit and the C element in the JCTL circuit of junction unit are double the maximum transfer rate in the processor.

Referring to FIG. 2, the data input to junction unit from IN and IN at the maximum transfer rate are joined with the maximum transfer rate. As the double rate transfer is realized, the data can be passed through path without any problem and transferred to junction unit . Similarly, the data input to junction unit from IN and IN at the maximum transfer rate are passed through the path and transferred at the double rate, to junction unit . The four input data are joined at the junction unit . As the transfer rate of the path is four times the input rate or the output rate of the router, the data can be transferred to the branching unit through path with the transfer rate not lower than the maximum transfer rate. The four input data are branched to OUT, OUT, OUT and OUT at branching unit . As the transfer rate of the C element in branching unit is quadrupled rate, each data can be output at the maximum transfer rate.

FIG. 3 is a block diagram showing a 4×4 router formed by the 2×2 double rate transfer routers in accordance with a third embodiment of the present invention. In FIG. 3, the double rate transfer routers , , and are each the double rate transfer router shown in FIG. 1, and in the section of transfer from double rate transfer routers , to double rate transfer routers and , double rate transfer is utilized. The router provides 4×4=16 different paths. In FIG. 3, the transfer rate of paths , , and are made double the input rate or the output rate of the router.

More specifically, the transfer rate between the C element in the branching unit of double rate transfer router and the C element in the JCTL circuit in the junction unit of double rate transfer router , the transfer rate between the C element in the branching unit of double rate transfer router and the C element in the JCTL circuit in the junction unit of double rate transfer router , the transfer rate between the C element in the branching unit of double rate transfer router and the C element in the JCTL circuit in the junction unit of double rate transfer router and the transfer rate between the C element in the branching unit of double rate transfer router and the C element in the JCTL circuit in the junction unit of double rate transfer router are double the maximum transfer rate in the data driven type processor.

Referring to FIG. 3, when the data input from IN is to be routed to OUT and the data input from IN is to be routed to OUT, for example, the data input from IN and IN at the maximum transfer rate are passed through double rate transfer router and both are output from path . Conventionally, it is not guaranteed by the router that two or more inputs provided simultaneously are output simultaneously from the same outputs. Here, as the transfer rate of path is doubled, the data can be transferred to double rate transfer router without any problem. Thereafter, the data are output, each at the maximum transfer rate, from OUT and OUT, respectively.

The router shown in FIG. 18 described with reference to the prior art is formed by four 1-input, 4-output branching units shown in FIG. and junction unit shown in FIG. 16, and in order to maintain 4×4=16 paths and the maximum transfer rate, the circuit scale was very large. When we compare the router shown in FIG. and the router in accordance with the embodiments of the present invention, it can be understood that the circuit scale can be suppressed in such a router that uses the transfer rate corresponding to the total sum of the transfer rates of inputs to the router, or the transfer rate corresponding to the total sum of the transfer rates of the outputs from the router. More specifically, the circuit scale is the smallest in the quadruple state transfer rate router shown in FIG. 2, second smallest in the router formed by the double rate transfer router shown in FIG. and the third smallest in the router formed by the conventional router method shown in FIG. . In the example utilizing the conventional router method shown in FIG. 18, the circuit scale is considerably larger than other routers.

FIG. 4 is a block diagram of an M×N rate transfer router in accordance with a still further embodiment of the present invention. Here, M and N are natural numbers not smaller than 2, M and N may or may not be the same, and M may be larger than or smaller than N. The router shown in FIG. 4 has M inputs and N outputs, and formed by a M-input, 1-output junction unit and a 1-input, N-output branching unit . The junction unit is formed by (M−1) 2-input, 1-output junction units. The router provides M×N paths.

Referring to FIG. 4, when the relation between M and N is (M>N), the transfer rate of the path between junction unit and branching unit is the total sum of the transfer rates from input IN to INM. When inputs IN to INM all have the same transfer rate, the path will have M-times the transfer rate.

When the relation is (M

FIG. 5 is a circuit diagram of the C element used in each of the embodiments of the present invention. The C element shown in FIG. 5 is the same as that described with reference to FIG. 10, while the number of stages of delay element refers embodiment by embodiment.

When a signal at the “H” level is input to the RI terminal of the C element shown in FIG. 5 from the C element of a succeeding stage, indicating the transfer acknowledge state, the C element sets the control signal CP of the pipeline register to the “H” level, so that a data packet output from the preceding stage is held by the pipeline register formed by the D type flip-flop, and output to the succeeding stage. The data packet output from the pipeline register to the succeeding stage is subjected to prescribed processing by the logic or operating unit as shown in FIG. 9 or , and thereafter the resulting data packet is transferred and held in a pipeline register of the succeeding stage.

The structure of the C element or the pipeline register is relatively simple, and therefore, the time for processing or delay at these portions is short. By contrast, the logic unit and the operating unit have complicated circuit structures, and therefore the time for processing or the delay is considerably longer as compared with the time for processing or delay mentioned above. When data output from the pipeline register is completed and the CP signal of the C element attains to the “L”, the C element must maintain CO at the “L” level to continue transfer request, to the C element of the succeeding stage, until the data is transferred to the pipeline register of the succeeding stage through the logic unit or the operating unit.

For this purpose, a delay element is provided in the C element. As already described, the time for processing or the delay in the logic unit or the operating unit is considerably longer than the time for processing or the delay in the C element or in the pipeline register. Therefore, when the delay element in the C element used in the data driven type processor is implemented by a serial connection of inverter circuits, the delay element would have ten to several tens of stages. Therefore, the number of stages of the series connected inverters in the delay element of the C element in the router in accordance with the embodiments of the present invention can be readily reduced to ½, ¼, 1/M or 1/N (where M and N are natural numbers) of the number of stages in the C element in the data driven type processor.

In the embodiment shown in FIG. 5, the delay element inserted to the side of the CO terminal has been described. Desired effects can also be attained when the element is inserted to the side of the CI terminal. It should be noted, however, that the present invention is applied not to the C element in the junction unit of the first stage but in the C elements of other routers. Though inverter circuits are used for the delay element, the delay element may be implemented by the delay provided by capacitance or resistance components, or by the combination thereof.

As described above, according to the embodiments of the present invention, the transfer rate used in the self-synchronous transfer control circuit in the router is made different from the transfer rate used in the system. Therefore, as compared with the conventional router method, a router can be formed with significantly smaller circuit scale as compared with the conventional circuit, while maintaining the maximum transfer rate in the data driven processor. As a result, the necessary cost can be reduced, and it can cope with larger number of processes and faster speed of processing that are expected in the future. Further, the router in accordance with the present invention can be implemented in a simple circuit structure, the circuit area for the router portion can be reduced and the router can be designed efficiently.

Although the present invention has been described and illustrated in detail, it is clearly understood that the same is by way of illustration and example only and is not to be taken by way of limitation, the spirit and scope of the present invention being limited only by the terms of the appended claims.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram showing a 2×2 double rate transfer router in accordance with one embodiment of the present invention.

FIG. 2 is a block diagram showing a 4×4 quadruple rate transfer router in accordance with another embodiment of the present invention.

FIG. 3 is a block diagram showing a 4×4 router formed by the 2×2 double rate routers in accordance with a still further embodiment of the present invention.

FIG. 4 is a block diagram showing an M×N double rate transfer router in accordance with a still further embodiment of the present invention.

FIG. 5 is a circuit diagram of the C element used in the embodiment of the present invention.

FIG. 6 shows a data packet format.

FIG. 7 shows a data transfer path of a data driven type processor.

FIGS. 8A to E are timing charts of the C element.

FIG. 9 is a block diagram showing a pipeline in the data driven type processor.

FIG. 10 is a circuit diagram of the C element.

FIG. 11 is a block diagram of a data driven type processor.

FIG. 12 shows an example of use of a conventional router.

FIG. 13 is a block diagram of a 2×2 router.

FIG. 14 is a circuit diagram of a 1-input, 2-output branching unit used in the router.

FIG. 15 is a circuit diagram of a 1-input, 4-output branching unit used in the router.

FIG. 16 is a circuit diagram of a 2-input, 1-output junction unit used in the router.

FIG. 17 is a circuit diagram of the JCTL circuit in the junction unit shown in FIG. .

FIG. 18 is a block diagram showing a 4×4 router in accordance with the conventional method.

FIG. 19 is a block diagram showing a 2×2 router with a circuit scale made smaller in accordance with the conventional method.

CLAIMS

1. A method of controlling execution of a data driven type information processing apparatus including a router including an M-input, 1-output junction unit and a 1-input, N-output branching unit, controlling input/output of a data packet including at least a destination node number, an instruction code and data, and a self-synchronous transfer control circuit generating a transfer request signal and a transfer acknowledge signal controlling transfer and operating processes of said data packet, wherein a transfer rate used in the self-synchronous transfer control circuit of said router is set so as to be greater than the maximum transfer rate that can be used in said data driven type information processing apparatus, based on said maximum transfer rate.

2. The method of controlling execution of a data driven type information processing apparatus according to claim 1, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a multiplication of the transfer rate used in said system.

3. The method of controlling execution of a data driven type information processing apparatus according to claim 1, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a total sum of transfer rates of inputs to said router.

4. The method of controlling execution of a data driven type information processing apparatus according to claim 1, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a total sum of transfer rates of outputs from said router.

5. The method of controlling execution of a data driven type information processing apparatus according to claim 1, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is the larger one of the total sum of the transfer rates of the inputs to said router and the total sum of the transfer rates of the outputs from said router.

6. A data driven type information processing apparatus, comprising: a router including an M-input, 1-output junction unit and a 1-input, N-output branching unit, controlling input/output of a data packet including at least a destination node number, an instruction code and data; and a self-synchronous transfer control circuit generating a transfer request signal and a transfer acknowledge signal controlling transfer and operating processes of said data packet, wherein a transfer rate used in the self-synchronous transfer control circuit of said router is set so as to be greater than the maximum transfer rate that can be used in said data driven type information processing apparatus, based on said maximum transfer rate.

7. The data driven type information processing apparatus according to claim 6, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a multiplication of the transfer rate used in said system.

8. The data driven type information processing apparatus according to claim 6, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a total sum of transfer rates of inputs to said router.

9. The data driven type information processing apparatus according to claim 6, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is a total sum of transfer rates of outputs from said router.

10. The data driven type information processing apparatus according to claim 6, wherein the transfer rate used in said self-synchronous transfer control circuit of said router is the larger one of the total sum of the transfer rates of the inputs to said router and the total sum of the transfer rates of the outputs from said router.

11. The data driven type information processing apparatus according to claim 10, wherein a plurality of said routers are combined.

COPYRIGHT

User acknowledges that Fairview Research and its third party providers retain all right, title and interest in and to this xml under applicable copyright laws. User acquires no ownership rights to this xml including but not limited to its format. User hereby accepts the terms and conditions of the License Agreement.