Data processing apparatus, data processing system, packet, recording medium, storage device, and data processing method

DATA PROCESSING APPARATUS, DATA PROCESSING SYSTEM, PACKET, RECORDING MEDIUM, STORAGE DEVICE, AND DATA PROCESSING METHOD

The present invention relates to a data processing apparatus, a data processing system, a packet, a recording medium, a storage device, and a data processing method.

As a computer architecture, a Neumann-type architecture that sequentially fetches, decodes, and executes instructions from a storage device (memory) is generally known. This Neumann-type architecture is an instruction-oriented processing system that predetermines the execution order of instructions and performs processing while collecting operands (data to be operated on) each time.

Also, in a Neumann-type computer, a superscalar processor is known as a CPU (Central Processing Unit) architecture that parallelly processes a plurality of instructions. The superscalar processor is capable of out-of-order processing, issuing and executing instructions to execution nodes in the order of arrival of operands. However, in the superscalar processor, since the scheduler rearranges the execution results in the correct order while checking the data dependency, the increase in the number of instructions that can be executed simultaneously causes the scheduler to become complicated.

On the other hand, as a non-Neumann-type architecture, a data-driven architecture in which processing is performed corresponding to a data flow (data flow) is known, paying attention to data dependency. In this data-driven architecture, multiple instructions can be processed in parallel by firing when an operand is prepared in the execution node and transmitting the execution result of the instruction to the next execution node.

For example, Patent Document 1 discloses a multiprocessor system in which a data drive type (data flow machine type in Patent Document 1) architecture is used for interprocessor control and a Neumann type architecture is used for internal processor control. This multiprocessor system uses a combination of a data-driven architecture and a Neumann-type architecture, so that parallel processing can be performed based on the execution code generated by dividing it into threads without using a complicated hardware configuration.

Further, for example, in Non-Patent Document 1, a Tera-op Reliable Intelligently Advanced Processing System (TRIPS) architecture is disclosed. This TRIPS architecture is a combination of a chip architecture called a tile processor and an instruction set architecture (ISA) called EDGE (Explicit Data Graph Execution). Among these, the tile processor avoids the problem of wiring delay by wiring only between adjacent cores, and can maintain high operating speed even when the number of cores increases. On the other hand, the EDGE architecture aims to maximize the parallelism of processing by arranging instructions statically in the execution node and executing them when the operands are prepared in the execution node, similar to the data flow architecture.

In this way, a plurality of instructions can be processed in parallel by using the computer architectures described above, either alone or in combination.

<p><patcit num="0001"><text>Japanese Patent Laid-Open No. 2007-193430</text></patcit></p>

<p><nplcit num="0001"><text> Doug Burger, et al., "Scaling to the End of Silicon with EDGE Architectures," IEEE Computer, vol. 37, no. 7, pp. 44-55, July 2004.</text></nplcit></p>

A parallel computer can process multiple instructions in parallel by using the data-driven architecture. However, since the data-driven architecture uses an instruction set different from that of the Neumann-type architecture, existing software assets for Neumann-type computers cannot be used as they are.

In order to use an existing software asset in a parallel computer, for example, a compiler technology for generating an executable code for a parallel computer from a source program for a Neumann-type computer is required. However, the parallelism of processing in the case of using the above compiler technology depends on the performance of the compiler, and the improvement of the parallelism accompanies the complexity of the compiler and may lead to an increase in the compilation time. In addition, in Patent Document 1, in order to generate an executable code for a multiprocessor system by the program processing device, it is necessary to add a thread description in advance to a source program written in a high-level language such as C language.

In addition, for example, an interpreter technology for sequentially interpreting and executing a source program for a Neumann-type computer is required. However, similarly to the case of the compiler technology, the improvement of parallelism of processing accompanies the complexity of the interpreter and may result in a decrease in the operation speed of the interpreter. In addition, although it does not entail the complexity of the compiler or the interpreter, it may cause the complexity of the parallel computer itself or a decrease in operating speed.

Accordingly, improvement in parallelism in parallel computers is a trade-off that results in an increase in cost for using existing software assets in parallel computers.

A main embodiment of the present invention for solving the above-described problems is extended identification information including data, identification information for identifying the data added to the data, and instruction information indicating one or more processing instructions for the data. a plurality of processing units configured to process packets each including, wherein each processing unit in the plurality of processing units transmits address information determined according to the extended identification information among the packets to each of the processing units in the plurality of processing units A data processing apparatus characterized by having an input/output unit configured to acquire only packets representing

Other features of the present invention will become apparent from the accompanying drawings and description of the present specification.

&lt;Cross Reference to Related Applications&gt;

This application is hereby incorporated by reference in its entirety, and Japanese Patent Application Nos. 2009-274033, 2010 filed on December 2, 2009, October 7, 2010, and January 1, 2010, respectively - Claims priority to 199711, and to U.S. Provisional Patent Application No. 61/350408.

&lt;Effect of the invention&gt;

According to the present invention, the parallelism of processing can be improved by substantially using the existing software assets as they are.

1 is a block diagram showing the configuration of a PE (processing element) according to an embodiment of the present invention. Fig. 2 is a block diagram schematically showing the configuration of the entire data processing system including the data processing apparatus. 3 is a block diagram showing the configuration of a data processing apparatus according to an embodiment of the present invention. Fig. 4 is a diagram showing an example of the relationship between a source program and a program (executable code) processed by the data processing apparatus. 5 is a diagram showing an example of an instruction set used in a data processing apparatus. 6 is a diagram showing an example of a data flow chart generated by an MCE (Memory Control Element). 7 is a diagram illustrating an example of a basic packet sequence generated by an MCE (Memory Control Element). 8 is a diagram showing an example of a packet sequence after expansion generated by an MCE (Memory Control Element). 9 is a diagram for explaining a method of calculating address information according to an embodiment of the present invention. 10 is a flowchart for explaining an example of the operation of the input/output unit. 11 is a diagram illustrating an example of a hash table mounted in a buffer memory. 12 is a diagram for explaining an operation of a data processing apparatus according to an embodiment of the present invention. Fig. 13 is a diagram showing an example of the configuration of a communication path when information is transmitted using electromagnetic waves (light). 14 is a diagram showing another example of the relationship between a source program and a program processed by the data processing apparatus. Fig. 15 is a block diagram schematically showing the configuration of a PE (processing element) in which each input/output port has a plurality of channels. Fig. 16 is a diagram showing an example of a data flow chart including execution of an instruction add instruction. Fig. 17 is a diagram showing an example of a packet sequence after expansion including execution of an instruction addition instruction. 18 is a diagram for explaining an operation of the data processing apparatus including the execution of an instruction addition instruction. 19 is a diagram showing another configuration example of a packet processed by the data processing apparatus. Fig. 20 is a diagram showing an example of a data flow chart including instruction addition processing; Fig. 21 is a diagram for explaining the operation of the data processing apparatus including instruction addition processing;

At least the following details will become apparent from a description of this specification and accompanying drawings.

=== Overview of the overall data processing system configuration ===

Hereinafter, an outline of the configuration of the entire data processing system including the data processing apparatus will be described with reference to FIG. 2 .

The data processing system shown in Fig. 2 is a parallel computer system including a data processing device 1, and in addition to the data processing device 1, a storage device 6, an input device 7, an output device 8, and It includes a bus (9). The data processing device 1 , the storage device 6 , the input device 7 , and the output device 8 are connected to each other via a bus 9 . A detailed description of the configuration of the data processing apparatus 1 will be described later.

=== Overview of the overall data processing system operation ===

Next, an outline of the overall data processing system operation will be described.

The storage device 6 includes a random access memory (RAM), a read only memory (ROM), and the like, and stores programs (executable codes), data used for execution of the programs, and the like. Further, the data processing device 1 is equivalent to the CPU of the computer system, and executes the program stored in the storage device 6 . Further, a detailed description of the operation of the data processing apparatus 1 will be described later.

The input device 7 includes a keyboard, a mouse, or the like, and inputs information including data and programs (source programs or executable codes) from the outside to the data processing system. On the other hand, the output device 8 includes a display, a printer, and the like, and outputs information as characters or images to the outside.

Incidentally, the classification of the data processing device 1 , the storage device 6 , the input device 7 , and the output device 8 is not fixed. For example, an auxiliary storage device such as a hard disk drive or an optical disk drive is used as the storage device 6, but may be classified into an input device 7 and an output device 8 for inputting and outputting information to and from the outside.

=== Configuration of data processing unit ===

Hereinafter, the configuration of a data processing apparatus according to an embodiment of the present invention will be described with reference to FIG. 3 .

The data processing device 1 shown in FIG. 3 is a PE (Processor/Processing Element: processing element/processing element) 100 to 115, MCE (Memory Control/Controlling Element: memory control element/memory control element) 300 to 303), a cache memory 400, and a communication path (transmission path) 500 .

The data processing device 1 includes a plurality of PEs each corresponding to a processing unit, and each PE is connected to each other via a communication path 500 . In the embodiment of the present invention, as an example, it is assumed that the data processing apparatus 1 includes 16 PEs 100 to 115 arranged in a matrix of 4 rows and 4 columns. Also, it is assumed that only PEs 100 to 115 adjacent to each other are connected to each other like the tile processor described above. In addition, a detailed description of the configuration of each PE will be described later.

Here, if it is assumed that the coordinates (X, Y) of the PEs 100 to 115 are represented by (0,0) to (3,3) as shown in FIG. 3 , the X coordinate for each PE is the upper 2 bits , You can set an identification number that uses the Y coordinate as the lower 2 bits. In addition, the identification number set as described above coincides with the lower two digits of the three-digit code of each PE shown in FIG. 3 . For example, the identification number of the PE 103 located at the coordinates (0, 3) becomes 3 (0011 in binary notation), and the identification number of the PE 112 located at the coordinates (3, 0) is 12 (2) 1100) in binary notation.

The data processing device 1 includes at least one MCE corresponding to the control unit, and each MCE is connected to any one of the PEs 100 to 115 via a communication path 500 . In the present embodiment, as an example, it is assumed that the data processing apparatus 1 has four MCEs 300 to 303 . Further, the MCEs 300 to 303 are connected to the adjacent PEs 100 to 103, respectively. In addition, as shown in Fig. 3, identification numbers 0 to 3 are set for the MCEs 300 to 303, respectively.

The cache memory 400 is connected to the MCEs 300 to 303 . Further, the cache memory 400 is connected to the storage device 6 external to the data processing device 1 via the above-described bus 9 (not shown).

=== Example of configuration and operation of communication path ===

The communication path 500 is an information transmission medium between PEs or between PE and MCE, and the information transmission includes transmission of optical signals by optical fibers and transmission of electromagnetic waves in free space in addition to transmission of electrical signals by electrical wiring. . Here, Fig. 13 shows an example of the configuration of the communication path 500 in the case of transmitting information using electromagnetic waves, particularly light. In this case, each PE includes at least one transmitting unit including a light emitting element and at least one receiving unit including a light receiving element. 13, the light emitting element 212 is included in the PE of the information transmission source, and the light receiving element 213 is included in the PE of the information transmission destination.

The communication path 500 shown in Fig. 13 includes a transmission material 501 that transmits light, a reflection material 502 that reflects light, and an absorber 503 that absorbs light. The transmission material 501 and the reflection material 502 respectively correspond to a core and a cladding in an optical fiber, and quartz glass, plastic, or the like can be used. In addition, the refractive index of the transmission material 501 is made higher than that of the reflection material 502 , and the optical signal is transmitted through the transmission material 501 while being totally reflected by the reflection material 502 .

The light receiving element 213 is configured to receive light of a wavelength set for each PE using an on-chip color filter (OCF) or the like. In this case, the packet can be delivered by changing the wavelength of the light emitted by the light emitting element 212 to match the wavelength set in the PE of the delivery destination. In addition, by switching a plurality of light emitting devices that emit light of different wavelengths, the packet can be delivered by matching the wavelengths set in the PE of the delivery source and the delivery destination.

In addition, any wavelength from an ultraviolet region to an infrared region may be used as the wavelength set for each PE. However, depending on the material used for the transmission material 501 and the reflection material 502, it is preferable to use a wavelength from the visible ray region to the infrared region because ultraviolet rays are absorbed and the transmittance is lowered.

=== Behavior of data processing unit ===

Next, the operation of the data processing apparatus according to the embodiment of the present invention will be described with appropriate reference to FIGS. 4 to 8 .

The cache memory 400 controls input/output between the MCEs 300 to 303 and the storage device 6 while caching. Accordingly, the programs and data stored in the storage device 6 are read by the MCEs 300 to 303 via the cache memory 400 .

Here, an example of the relationship between a source program and the program (executable code) processed by the data processing apparatus 1 is shown in FIG. The source program P0 described in the high-level language is stored in the storage device 6 after being precompiled into the executable code P1, and the MCEs 300 to 303 read the executable code P1. In Fig. 4, as an example of the source program P0, there is shown a process for storing in the array dp[1024] a value obtained by dividing each element of the array sp[1024] written in C++ by 2 in the array dp[1024]. Also, the executable code P1 may be a program written in assembly language that substantially corresponds to machine language instead of a machine language program.

The MCEs 300 to 303 generate packet sequences to be described later based on the data flow chart from the read executable code P1. Although each MCE does not need to generate the data flowchart itself, in the embodiment of the present invention, for convenience of explanation, it is assumed that the data flowchart is first generated and then the packet stream is generated based on the data flowchart.

Here, an example of the instruction set used in the data processing apparatus 1 is shown in FIG. In Fig. 5, each command is divided into a 2-input/1 output command and a 1-input/1 output command. Of these, the 2 input/1 output instruction is an instruction for executing binary operation in which two inputted data are specified as the left operand and the right operand, respectively. On the other hand, the 1 input/1 output instruction is an instruction that executes a unary operation in which one input data is specified as an operand. Further, as shown in Fig. 5, symbols corresponding to operators and hexadecimal notations in machine words are set for each instruction, and these are used in data flow charts and descriptions of packet sequences.

First, the two-input/one-output command will be described.

A symbol "+" and a hexadecimal notation 10H are set for the addition instruction that outputs the addition result (A+B or B+A) of the two data A and B. On the other hand, in the case of a subtraction instruction that outputs a subtraction result (LR) of two data (L and R), since subtraction is a non-conversion operation for which the commutative law does not hold, the left operand indicating whether each data is used as the left operand or the right operand /requires right information (direction information). Accordingly, left/right information "L" or "R" is further added to the symbol "-" corresponding to the subtraction command, and a hexadecimal notation 12H or 13H is set, respectively.

Left/right information "L" indicates data specified by the left operand, and left/right information "R" indicates data specified by the right operand. In addition, in the instruction set, the LSB (Least Significant Bit) of each instruction is allocated exclusively for left/right information. Accordingly, even in the following commands (excluding the null character), the LSB of the command including the left/right information "L" and the command without the left/right information is 0, and the left/right information "R" is The LSB of the command with is set to 1.

For a multiplication instruction outputting a multiplication result (AxB or BxA) of two data A and B, a symbol "x" having no left/right information and a hexadecimal notation 14H are set. On the other hand, for the division command for outputting the division result (L/R) of the two data (L and R), the symbols "/L" and "/R" to which left/right information is added, and the hexadecimal notation 16H and 17H) is set.

The write command in which the symbols "writeL" and "writeR" to which left/right information is added and the hexadecimal notation 18H and 19H are set are data stored in the address of the storage device 6 indicated by the data L This is a command to write data (R) to (*L). In addition, "*" is an indirect reference operand.

The data add command in which the symbols "applL" and "applR" to which left/right information is added and the hexadecimal notation 50H and 51H are set are added to the data part of the packet L, which will be described later, in the data part of the packet R. command to add In addition, the symbols "app2L" and "app2R" to which left/right information is added and the instruction addition instruction in which the hexadecimal notation 52H and 53H are set are added to the processing instruction portion of the packet L to be described later in the packet (R) This command adds the data part of

Next, one input/1 output command will be described. Also, since 1 input/1 output instruction designates only one data as an operand, neither of them has left/right information.

The symbol "NOP" and the "NOP" instruction to which the hexadecimal notation (00H) is set are instructions that do nothing. In addition, the read command in which the symbol "read" and the hexadecimal notation 02H are set is a command to read the data *A stored in the address of the storage device 6 indicated by the data A. Although it is not in the command, a hexadecimal notation (FFH) is set as a null character indicating the end of a packet, for example.

Each MCE uses the instruction set shown in FIG. 5 to generate a data flow chart similar to the case of a typical data-driven architecture. Fig. 6 shows a flow chart of data generated from the executable code P1, and corresponds to the processing in the for loop of the source program P0 shown in Fig. 4 .

In Fig. 6, D1 to D5 represent data, and I1 to I5 represent commands. The addition instruction (I4) adds data D1(dp) and data D2(ii) to output data (dp+ii), and the addition instruction (I1) adds data D3(sp) and data D4(ii) to Outputs data (sp+ii). Further, the read command I2 reads data [*(sp+ii)] from the storage device 6 . Also, the division command I3 divides the data [*(sp+ii)] by the data D5(2) to output the data [*(sp+ii)/2]. Then, the write command I5 writes the data [*(sp+ii)/2] to the data [*(dp+ii)] of the storage device 6 .

Through the above data flow, the value obtained by dividing one element of the array sp[1024] by 2 is stored in the array dp[1024]. Fig. 7 shows a basic packet sequence generated based on the data flow chart shown in Fig. 6;

Each packet includes a data section and an extended identification information section. In addition, the extended identification information section includes an identification information section and a processing instructions section. In addition, each packet may be appropriately encoded for purposes such as encryption or compression.

The data portion includes data length information of the data as well as the data body. Further, the data length information indicates, for example, the number of bytes of data, but becomes unnecessary when the data processing apparatus 1 uses only fixed-length data.

The identification information part includes, for example, an MCE ID and a process ID. For example, among these, the process ID is set for each basic packet string, so it is empty (null character) in Fig. 7 and is set when the for loop is expanded. On the other hand, the MCE ID corresponds to issuer information indicating the MCE that generated the basic packet sequence, and for example, identification numbers 0 to 3 shown in FIG. 3 are used. In addition, in the basic packet sequence, as shown in Fig. 7, when the for loop is expanded with the MCE ID as empty, the MCE ID is set together with the process ID.

In the embodiment according to the present invention, as an example, the processing instruction portion includes instruction number information in addition to up to five instructions 1 to 5. Each instruction is arranged in the reverse order of execution, the instruction to be executed first is placed at the end, and the subsequent instruction is empty. In addition, the number of instructions information indicates the number of unprocessed instructions, but may be counted every time.

As is clear from Fig. 7, the basic packet sequence is a reconstruction of the data flow chart shown in Fig. 6 for every 5 pieces of data (D1 to D5), and each packet is generated by adding identification information and processing instructions to the data. . In addition, each MCE develops a control command for a basic packet sequence such as repeat processing, and issues each packet to an adjacent PE. FIG. 8 shows the packet sequence after the for loop is expanded with respect to the basic packet sequence shown in FIG. 7 .

As shown in Fig. 4, since the for loop is an iterative process from ii=0 to ii=1023, 5×1024 packets are generated by expanding it. Further, as shown in Fig. 8, every 5 packets contain the same processing ID from 1 to 1024, and the 5 packets correspond to the basic packet sequence shown in Fig. 7, respectively. In FIG. 8, as an example, the MCE ID is set to 1, indicating that each packet is generated by the MCE 301 .

Each packet issued from the MCE 301 is transmitted through the communication path 500 to a PE indicated by address information to be described later among the PEs 100 to 115 . Further, each PE corresponds to an execution node that executes the processing instructions included in the packet. In addition, detailed description of the operation of each PE will be described later.

As described above, the data processing apparatus according to the embodiment of the present invention is significantly different from the conventional computer architecture described above in that it deals with a packet in which data designated by an operand and an instruction designated by an operator are integrated.

The data processing apparatus of the present invention is not limited to a configuration having an MCE that generates a packet stream from an executable code P1 written in machine language or assembly language, as shown in the embodiment of the present invention.

For example, in the storage device 6, a program expressed by a syntax tree as an intermediate code generated in an intermediate step at the time of compiling from the source program P0 to the executable code P1 may be stored. Since the syntax tree has a tree structure in which operands are arranged in leaf nodes and operators are arranged in internal nodes, data flowchart generation is easier compared to machine language or assembly language.

Also, for example, the storage device 6 may store a basic packet sequence generated in advance by an external device including a compiler or a packet sequence after expansion. When the basic packet sequence is stored, each MCE develops a control command for the read basic packet sequence, sets the MCE ID or process ID, and then issues each packet to the adjacent PE. On the other hand, when the packet sequence after deployment is stored, each MCE can issue each packet to an adjacent PE as it is.

Also, for example, in the storage device 6, an intermediate packet sequence in which a part or all of the identification information part is omitted or in which null characters are used among the packet sequences after expansion can be stored. In this case, each MCE sets the omitted MCE ID or process ID, and then issues each packet to the adjacent PE.

Also, for example, a packet sequence after deployment can be directly input to the data processing device from an external device. In this case, the external device may include other data processing devices operating in parallel.

Here, another example of the relationship between a source program and a program (executable code) processed by the data processing apparatus 1 is shown in FIG. In this case, the compiler generates a basic packet sequence from the source program P0 written in a high-level language based on a data flowchart, and also develops control commands for the basic packet sequence. Further, in the storage device 6, the packet sequence after the expansion is properly encoded and then stored as the executable code P2. Then, the MCEs 300 to 303 read the executable code P2.

=== Configuration of PE (Processing Element) ===

Hereinafter, a configuration of a PE according to an embodiment of the present invention will be described with reference to FIG. 1 .

The PEs 100 to 115 shown in FIG. 1 include an input/output unit 210, a comparison/selection unit 230, a buffer memory 240, operand buffers 250a and 250b, and an Arithmetic Logic Unit (ALU): arithmetic logic operation unit) 260 .

The input/output unit 210 includes an address information calculating unit 211 , output ports 214a to 214d , and input ports 215a to 215d . Further, into the input/output unit 210, packets and data read from the storage device 6 are inputted through each input port. Also, from the input/output unit 210, packets and data recorded in the storage device 6 are output through an output port. In addition, each input/output port (input port and output port) is connected to the adjacent PE and MCE via the communication path 500 (not shown) mentioned above.

For example, in the case of the PE 110 of FIG. 3 , four sets of input/output ports are connected to the PEs 109 , 106 , 111 , and 114 , respectively. Also, for example, in the case of PE 100, two sets of input/output ports are respectively connected to PEs 101 and 104, one set of input/output ports are connected to MCE 300, and one set of input/output ports. The output port is not used.

In addition, for example, in the configuration shown in FIG. 15, each input/output port includes a plurality of channels, and packets and data are input and/or output between adjacent PEs and between PEs and MCEs using the plurality of channels. can be

When information is transmitted using light, for example, the light emitting element 212 in Fig. 13 is provided in each output port, and the light receiving element 213 is provided in each input port.

A packet is input from the input/output unit 210 to the comparison/selection unit 230 . In addition, the comparison/selection unit 230 includes a hash value calculation unit 231 and inputs/outputs packets between the buffer memories 240 corresponding to the storage units. Also, from the comparison/selection unit 230 through the operand buffers 250a and 250b, packets having data designated by the left operand and the right operand, respectively, are input to the ALU 260 corresponding to the operation unit. Then, the packet newly generated by the ALU 260 is again input to the input/output unit 210 .

=== Behavior of PE (Processing Element) ===

Next, the operation of the PE according to the embodiment of the present invention will be described with appropriate reference to FIGS. 9 to 11 .

The input/output unit 210 first calculates address information of a packet inputted by the address information calculation unit 211 . The address information is information indicating a PE to process a packet, and may be obtained from the extended identification information part of the packet. Here, with reference to FIG. 9, a method of calculating the address information of the first 5 packets in which MCE ID=1 and process ID=1 in FIG. 8 will be described. Hereinafter, as shown in FIG. 9, the five packets are designated as packets P1 to P5, respectively.

The address information calculation unit 211 first extracts only the extended identification information part from each packet (interrupted in FIG. 9), and masks left/right information of the command to be executed first among the extended identification information (bottom of FIG. 9). ). As described above, in the embodiment of the present invention, the instruction to be executed first is arranged at the end of the packet, and the LSB of each instruction is allocated exclusively for left/right information. Therefore, it is only necessary to mask the last bit of the extended identification information with 0 or 1 (0 in FIG. 9). In addition, the extended identification information may include a null character, and in this case, one bit or more immediately before the null character may be masked.

The address information calculating unit 211 then generates a pseudo random number based on the masked extended identification information and calculates address information according to the pseudo random number. For example, if a 4-bit value of 0 to 15 (0000 to 1111 in binary notation) is calculated as address information, the address information has the upper two bits as the X-coordinate and the lower two bits as the Y-coordinate, as in the PE coordinates of FIG. 3 . It can also be expressed by the format of the coordinates (X, Y). In the lower part of Fig. 9, the address information is shown in the form of the above coordinates.

Since the pseudo-random number has reproducibility unlike the physical random number, the same pseudo-random number is generated from the packet having the same masked extended identification information, and the same address information is calculated. For example, as shown in the lower part of FIG. 9 , the same address information (x1, y1) is calculated from the packets (P1 and P2) including the same masked extended identification information. Similarly, the same address information (x2, y2) is calculated from the packets P3 and P4.

As described above, each packet can be appropriately encoded, but it is preferable to separately encode the data portion and the extended identification information portion so that decoding is not required each time address information is calculated. Similarly, when encoding the processing instruction part alone or the entire extended identification information part, it is preferable to use an encoding capable of masking the left/right information of the instruction to be executed first without decoding.

In addition, a known method can be used for generating a pseudo-random number. From the viewpoint of the calculation time of address information, it is preferable to use a high-speed generation method such as LCG (Linear Congruential Generator) or LFSR (Linear Feedback Shift Register).

Also, the address information calculating unit 211 may be configured to calculate address information by referring to a pre-generated pseudo-random number table. In this case, since the address information calculating unit 211 does not need to generate a pseudo-random number for each packet, it is possible to shorten the address information calculation time. In such a configuration, it is necessary for the address information calculating unit of each PE to have the same pseudo-random number table, or it is necessary for the address information calculating unit of each PE to read a common pseudo-random number table.

On the other hand, from the viewpoint of PE usage efficiency, it is preferable that the pseudo-random number is closer to the uniform distribution so that the packet distribution is uniform. In addition, if the random variable family is unpredictable, it is equivalent to a uniform distribution, so it is possible to improve the use efficiency of PE by using a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). However, since the processing time of each packet is different even by the command, the packet distribution may not be uniform even if the pseudo-random number is uniformly distributed.

Therefore, it is preferable to use pseudo-random numbers close to uniform distribution to such an extent that the calculation time of address information does not become too long. For example, it is not preferable that the calculation time of the address information becomes longer than the calculation time of the hash value, which will be described later.

The input/output unit 210 then determines whether or not the address information of the packet indicates the PE. If it indicates the PE, the input/output unit 210 acquires the packet and inputs it to the comparison/selection unit 230 . On the other hand, when the address information of the packet does not indicate the PE, the packet is transmitted to the PE adjacent to the PE indicated by the address information. Here, an example of a specific operation of the input/output unit 210 to realize acquisition and transmission of such a packet will be described with reference to FIG. 10 . In Fig. 10, the current position, that is, the coordinates of the PE is (x0, y0), and the coordinates of the PE indicated by the address information are (x1, y1).

When a packet is input from an adjacent PE or MCE (S1), the input/output unit 210 compares the Y coordinate (y0) of the current location with the Y coordinate (y1) of the address information (S2).

In S2, if the two Y coordinates coincide (S2: =), the X coordinate (x0) of the current position and the X coordinate (x1) of the address information are compared (S3).

Also, when y0 is greater than y1 (S2:&gt;), since the PE indicated by the address information is located in a direction having a smaller Y coordinate than the current position, a PE adjacent to the y0-1 direction, that is, coordinates (x0, y0-1) The packet is transmitted to the PE located at (S31), and the processing is terminated (S5). On the other hand, when y0 is smaller than y1 (S2:&lt;), the PE indicated by the address information is located in the direction with the Y coordinate greater than the current position, so the PE adjacent to the y0+1 direction, that is, the coordinates (x0, y0+1) The packet is transmitted to the PE located in (S32), and the processing is terminated (S5).

In S3, if the two X coordinates coincide (S3: =), since the address information indicates the PE, a packet is acquired and input to the comparison/selection unit 230 (S4), and the process is terminated. (S5).

Also, when x0 is greater than x1 (S3:&gt;), since the PE indicated by the address information is located in a direction having an X coordinate smaller than the current position, a PE adjacent to the x0-1 direction, that is, the coordinates (x0-1, y0) ), transmits the packet to the PE (S41), and ends the process (S5). On the other hand, when x0 is smaller than x1 (S3:&lt;), the PE indicated by the address information is located in a direction having a larger X-coordinate than the current location, so a PE adjacent to the x0+1 direction, that is, coordinates (x0+1, y0) The packet is transmitted to the PE located at (S42), and the process is terminated (S5).

When the input/output unit of each PE executes the above operation, each packet is delivered and acquired to the PE indicated by the address information. For example, in Fig. 3, when address information of a packet issued from MCE 301 to PE 101 indicates PE 115, the packet includes PE 102, PE 103, PE 107, and It is transmitted to PE 115 through PE 111 . Also, for example, when address information of a packet newly generated by processing by the PE 115 indicates the PE 104, the packet includes the PE 114, PE 113, PE 112, and PE 108. It is transmitted to the PE 104 through

That is, each packet first moves in the vertical direction in FIG. 3 until the PE and Y coordinates indicated by the address information match, and then moves in the left and right directions in FIG. 3 until the X coordinates coincide. By adopting such a movement rule, the movement path of a packet is always the shortest. In addition, the direction change during movement becomes 1 time or 0 times, and the frequency of use of the communication path 500 between PEs can be averaged.

As described above, in the data processing apparatus according to the embodiment of the present invention, PEs corresponding to execution nodes are arranged in a matrix like a tile processor, but packets to be processed are dynamically arranged based on the bit string itself. differs significantly from the EDGE architecture.

The data processing apparatus of the present invention is not limited to the arrangement and connection of the matrix shape shown in the embodiment of the present invention. For example, in Fig. 3, a ring-type connection is achieved by omitting a part of the communication path 500 between PEs. Also, for example, all PEs or between PEs and MCEs may be directly connected. In this case, as the number of PEs or MCEs increases, wiring becomes more difficult in transmission of electrical signals through electrical wiring. On the other hand, in the above-described information transmission using electromagnetic waves, the communication path 500 can be easily added.

The comparison/selection unit 230 inputs to the ALU 260 a processable one among the packets acquired by the input/output unit 210 (hereinafter, referred to as an acquisition packet). In addition, the comparison/selection unit 230 stores the unprocessable packet in the buffer memory 240 and reads the packet (hereinafter referred to as a storage packet) stored in the buffer memory 240 .

More specifically, when the first (last) instruction to be executed in the acquisition packet is a 1 input/1 output instruction, the comparison/selection unit 230 only outputs the acquisition packet through the operand buffer 250a or 250b to the ALU 260 ) in the

On the other hand, when the command to be executed first (last) of the acquisition packet is a 2-input/output command, the comparison/selection unit 230 searches for a packet in which the masked extended identification information matches the acquisition packet from the storage packet. do. And, when there is a matching storage packet, the comparison/selection unit 230 sets the two matching packets as a pair and inputs them to the ALU 260 through the operand buffers 250a and 250b. Further, when there is no matching storage packet, the comparison/selection unit 230 stores the acquisition packet in the buffer memory 240 .

In an embodiment of the present invention, the buffer memory 240 includes a hash table in order to efficiently search for a stored packet in which the masked extended identification information matches the acquisition packet. In addition, the comparison/selection unit 230 first calculates a hash value from the obtained packet by the hash value calculation unit 231 . A corresponding hash value is calculated based on the masked extended identification information of the acquisition packet similarly to the case of address information. Then, when the comparison/selection unit 230 stores the acquired packet in the buffer memory 240, the acquired packet is stored in the hash table in correspondence with the hash value.

In addition, a well-known implementation method can be used for a hash table. 11 shows an example of a hash table implemented in the buffer memory 240 . In the hash table, an open addressing method is used as a method of resolving a hash collision, and a linear probing method is used as a disaster order.

11 shows, as an example, a case in which the packet 1 having a hash value of n+3 is stored, and then packets 2 to 5 having a hash value of n are stored. Packet 1 is stored at the position of element (n+3) of the root array [256], and the flag "1" and the count value "1" are set. Also, packets 2 to 5 are stored at the positions of elements n, n+1, n+2, n+4, respectively, and the flag "1" and count value "4" are stored at the positions of element n. It is set.

The ALU 260 performs arithmetic operations (integer arithmetic and/or floating-point arithmetic) and logical operations on operands input through the operand buffers 250a and 250b, and outputs an operation result. More specifically, the ALU 260 executes the first (last) command to be executed on the data of the input packet, and adds extended identification information excluding the executed command to the data of the execution result to create a new packet. generated and inputted to the input/output unit 210 again.

As described above, each PE requests address information from the extended identification information portion of the input packet, acquires only packets whose address information indicates the PE, and transmits packets whose address information does not indicate the PE to other PEs. Then, a new packet is generated by executing an instruction to be executed first (last) with respect to the data of the acquisition packet, and adding extended identification information not including the executed instruction to the data of the execution result, and assigning the generated packet to the address Transmits or acquires information according to it.

Instead of each PE calculating address information whenever a packet is input, the calculated address information may be added to the packet to reuse the address information. For example, by adding the calculated address information when the MCE issues a packet to the PE and when the PE generates a new packet, the added address information can be used as it is in other cases. In this case, it is not necessary to calculate the address information for the packet to which the address information is added, and the address information added to the packets obtained from each PE is the same, so that the address information is stored in either the data part or the extended identification information part. can be added

In addition, when information is transmitted using light, the light emitting element of the PE, which is the information transmission source, emits light of a wavelength set for the PE of the information transmission destination indicated by the address information, so that the packet is sent to the PE indicated by the address information without repeating transmission. can be delivered directly. In this case, each PE can acquire only the packet whose address information indicates the PE without determining whether the address information of the packet input from the other PE or MCE indicates the PE.

Also, with respect to a packet newly generated by each PE, it may be configured to emit light of a wavelength set for a PE that is an information delivery destination indicated by the address information without determining whether the address information indicates the PE. In this case, the light receiving element of any one PE including the same PE as the information transmission source may receive the light of the wavelength and transmit the packet to the PE indicated by the address information.

=== A specific example of the operation of the data processing device ===

Here, a specific example of the operation of the data processing apparatus 1 for the packets P1 to P5 shown in FIG. 9 will be described with reference to FIG. 12 .

As described above, since the same address information (x1, y1) is calculated for the packets P1 and P2, the packets P1 and P2 are transmitted to the PE located at the coordinates (x1, y1) and added at the end. Instruction I4 is executed. Then, extended identification information not including the addition instruction I4 is added to the data (dp+0) of the execution result to generate a new packet P6. Let the address information calculated from the packet P6 be (x4, y4).

Similarly, since the same address information (x2, y2) is calculated for the packets P3 and P4, the packets P3 and P4 are delivered to the PE located at the coordinates (x2, y2), and the last add instruction (I1) is executed. Then, extended identification information not including the addition instruction I1 is added to the data (sp+0) of the execution result to generate a new packet (P7). Let the address information calculated from the packet P7 be (x5, y5).

The packet P7 is delivered to the PE located at the coordinates (x5, y5), and the last read command I2 (1 input/1 output command) is executed. Then, extended identification information not including the read command I2 is added to the execution result data [*(sp+0)], and a new packet P8 is generated. Since the masked extended identification information of the packet P8 becomes the same as that of the packet P5, the same address information (x3, y3) as the packet P5 is calculated.

The packets P8 and P5 are delivered to the PE located at the coordinates (x3, y3), and the last division instruction I3 is executed. Then, extended identification information not including the division instruction I3 is added to the data [*(sp+0)/2] of the execution result, and a new packet P9 is generated. Since the masked extended identification information of the packet P9 becomes the same as that of the packet P6, the same address information (x4, y4) as that of the packet P6 is calculated.

The packets P6 and P9 are delivered to the PE located at the coordinates (x4, y4), and the last write command I5 is executed. Then, extended identification information not including the write command I5 is added to the execution result data [*(dp+0)=*(sp+0)/2], and a new packet P10 is generated.

Since the packet P10 does not include a processing instruction, it is returned to the MCE 301 indicated by the MCE ID. In order to return the packet P10 to the MCE 301, the input/output unit of each PE needs to perform exception processing. In Fig. 12, as an example, the address information calculating unit 211 calculates the address information of a packet that does not include a processing instruction as (-1, m). Here, it is assumed that MCE ID=m. In this case, the address information of the packet P10 becomes (-1, 1). For example, in FIG. 3 , when PE 115 generates packet P10, packet P10 includes PE 114 , PE 113 , PE 109 , PE 105 , and PE 101 . ) through the MCE (301).

In addition, in each PE, it is preferable to return the packet up to the MCE indicated by the MCE ID even when the buffer memory or the operand buffer is full and the acquisition packet cannot be processed in a busy state. Exception processing in this case requires, for example, setting the information on the number of instructions in the packet to a value larger than the maximum number of instructions, and only calculating the address information of this packet as (-1, m). In addition, it is preferable that each MCE stop issuing a packet of a new process ID when any one PE is in a busy state. For the control of such a busy state, it is only necessary to provide, for example, control signal lines connected to all PEs and MCEs, and transmit a busy signal indicating a busy state through the control signal lines.

=== Another specific example of the operation of the data processing device ===

In the packet structure shown in Fig. 7, only up to five instructions can be included in the processing instruction portion. Therefore, in order to perform more complex processing, it is necessary to add an instruction to the processing instruction portion of the packet.

The instruction addition instruction shown in Fig. 5 (symbol/hexadecimal notation: "app2L"/52H, "app2R"/53H) can realize the additional function of these instructions. Hereinafter, a specific example of the operation of the data processing apparatus 1 including the execution of an instruction addition instruction will be described with appropriate reference to FIGS. 16 to 18 . Here, as an example, processing will be described in which each element of the array sp[1024] is multiplied by 4, then 1 is added, and a value obtained by dividing by 2 is stored in the array dp[1024].

Fig. 16 shows a data flow chart corresponding to the processing in the for loop of this processing.

In Fig. 16, D11 to D18 indicate data, Ia indicates an instruction addition instruction, and I11 to I17 indicate instructions other than the instruction addition instruction. The addition command I16 adds the data [D11(dp)] and the data [D12(ii)] to output data (dp+ii), and the addition command I11 outputs the data [D13(sp)] and the data[ D14(ii)] is added to output data (sp+ii).

The data D15 is a command sequence, and the command addition command Ia adds data D15 to the processing command part of the packet of data sp+ii. The instruction sequence of the data D15 corresponds to the processing after the instruction addition instruction Ia for the packet of data (sp+ii), and specifically corresponds to the instructions I12 to I15 and I17.

Among the commands added by the command addition command Ia, the first read command I12 reads data [*(sp+ii)] from the storage device 6 .

Then, the multiplication command I13 multiplies the data [*(sp+ii)] by the data D16(4) to output the data [*(sp+ii)*4].

Then, the addition command I14 adds the data D17(1) to the data [*(sp+ii)*4], and outputs the data [*(sp+ii)*4+1].

Then, the division command I15 divides the data [*(sp+ii)*4+1] by the data D18(2) to output the data[*(sp+ii)*4+1]/2.

Finally, the write command I17 writes the data [*(sp+ii)*4+1]/2 to the data [*(dp+ii)] of the storage device 6 .

Through the above data flow, one element of the array sp[1024] is multiplied by 4, then 1 is added, and the value obtained by dividing by 2 is stored in the array dp[1024]. FIG. 17 shows the first 8 packets (P11 to P18) with MCE ID=1 and process ID=1 among the packet sequence after the for loop is developed for the basic packet sequence generated based on the data flow chart shown in FIG. is indicating

Here, a specific example of the operation of the data processing apparatus 1 for the packets P11 to P18 shown in FIG. 17 will be described with reference to FIG. 18 .

Since the same address information is calculated for the packets P11 and P12, the packets P11 and P12 are delivered to the PE indicated by the same address information, and the last addition instruction I16 is executed. Then, extended identification information not including the addition instruction I16 is added to the data (dp+0) of the execution result to generate a new packet P19.

Similarly, since the same address information is calculated for the packets P13 and P14, it is transmitted to the PE indicated by the same address information, and the last addition instruction I11 is executed. Then, extended identification information not including the addition instruction I11 is added to the execution result data (sp+0) to generate a new packet P20. In the packet P20, the same address information as the packet P15 is calculated because the extended identification information becomes the same as that of the packet P15.

The packets P20 and P15 are delivered to the PE indicated by the same address information, and the last instruction addition instruction Ia is executed. Then, the command addition command Ia is removed from the processing command part to the data sp+0 of the packet P20, and then extended identification information to which the data D15 is added is added to generate a new packet P21. .

The packet P21 is delivered to the PE indicated by the calculated address information, and the last read command I12 (one input/1 output command) is executed. Then, extended identification information not including the read command I12 is added to the execution result data [*(sp+0)], and a new packet P22 is generated. In addition, in the packet P22, the same address information as that of the packet P16 is calculated because the masked extended identification information becomes the same as that of the packet P16.

The packets P22 and P16 are delivered to the PE indicated by the same address information, and the last multiplication instruction I13 is executed. Then, extended identification information not including the multiplication instruction I13 is added to the execution result data [*(sp+0)*4], and a new packet P23 is generated. In the packet P23, the same address information as the packet P17 is calculated because the masked extended identification information becomes the same as that of the packet P17.

The packets P23 and P17 are delivered to the PE indicated by the same address information, and the last addition instruction I14 is executed. Then, extended identification information not including the addition instruction I14 is added to the execution result data [*(sp+0)*4+1], and a new packet P24 is generated. In the packet P24, the same address information as the packet P18 is calculated because the masked extended identification information becomes the same as that of the packet P18.

The packets P24 and P18 are delivered to the PE indicated by the same address information, and the last division instruction I15 is executed. Then, extended identification information not including the division instruction I15 is added to the execution result data [*(sp+0)*4+1]/2 to generate a new packet P25. In the packet P25, the same address information as the packet P19 is calculated because the masked extended identification information becomes the same as that of the packet P19.

The packets P19 and P25 are delivered to the PE indicated by the same address information, and the last write command I17 is executed. Then, extended identification information not including the write command I17 is added to the execution result data*(dp+0)=[*(sp+0)*4+1]/2, and a new packet P26 is generated. do. Also, since the packet P26 does not include a processing instruction, it is returned to the MCE 301 indicated by the MCE ID.

By the way, by the execution of the write command I17, specifically, the data [*(dp+0)] stored in the address of the storage device 6 indicated by the data (dp+0) of the packet P19 is written to the packet ( P25) data [*(sp+0)*4+1]/2 is written. Accordingly, the data *(dp+0)=[*(sp+0)*4+1]/2 of the packet P26 indicates the execution of the write command I17 itself. Therefore, after execution of the write command I17, the packet P26 can be destroyed without returning to the MCE 301 .

In this way, by executing the instruction addition instruction shown in Fig. 5, it is possible to add an instruction to the processing instruction portion of the packet. Similarly, data may be added to the data portion of the packet by executing the data addition command (symbol/hexadecimal notation: "applL"/50H, "applR"/51H) shown in Fig. 5 .

=== Another example of packet structure ===

In FIG. 7, although the structure of the packet processed by the data processing apparatus 1 was shown, it is not limited to this. Here, another structural example of the packet processed by the data processing apparatus 1 is shown in FIG. In Fig. 19, packets P31 to P38 that can obtain the same execution results as the packets P11 to P18 shown in Fig. 17 are shown.

In FIG. 19, the extended identification information part has the same structure as that of FIG. However, each PE does not remove the executed instruction from the extended identification information part when generating a new packet. In this case, since the instruction to be executed first is not arranged at the end, the instruction number information becomes essential information to indicate the number of unprocessed instructions and the instruction to be executed first.

On the other hand, the data part includes data type information and extension flags of the data as well as the data body. In addition, the data type information indicates a data type such as "integer type" or "floating point type", for example, and by setting the data length for each data type in advance, the function of the data length information can also be realized. In addition, by providing "instruction type" as the data type, additional functions of the instruction can be realized as described later. Fig. 20 shows a data flow chart in the structure of the packet, in which the instruction addition function is realized by the instruction addition processing Pa without using the instruction addition instruction Ia. The extension flag is used in the instruction addition process Pa.

Further, in Fig. 19, the packets P31, P32, and P36 to P38 have the data body and extended identification information portions coincident with the packets P11, P12, and P16 to P18 shown in Fig. 17 . Also, in all of these packets, the data type information is "integer type" and the extension flag is set to "0".

In the packets P33 and P34, the instruction addition instruction IaL is removed from the packets P13 and P14 so that the instruction number information is "1". In addition, the extension flag is set to "1" to indicate that the command is added to the processing instruction portion in the instruction addition processing Pa instead of the instruction addition instruction IaL. In addition, all of these packets have data type information of "integer type".

Packet P35 contains the same processing instructions as packets P33 and P34 instead of instruction addition instruction IaR, and data type information is " command type". However, the instruction number information is "0" because the same processing commands as those of the packets P33 and P34 are not to be processed for the data D15 of the packet P35. In addition, in the packet P35, the extension flag is set to "0".

In Fig. 19, portions used when calculating address information and comparing an acquisition packet with a storage packet are shown in the range of arrows for each packet. For example, in the packets P31 to P34 and P36 to P38, only the unprocessed instructions indicated by the instruction number information among the identification information portion and the processing instruction portion are extracted, and left/right information of the instruction to be executed first is masked. Calculation of address information and the like are performed. Accordingly, in these packets, calculation of address information and the like are performed similarly to the case of removing an instruction executed from the extended identification information portion when a new packet is generated.

However, in the packet P35 in which the data type information is "command type" and the packet in which the extension flag is "1", when the number of instructions information is "0", the calculation of address information etc. is executed based on the entire extension identification information part. do.

Here, a specific example of the operation of the data processing apparatus 1 for the packets P31 to P38 shown in FIG. 19 will be described with reference to FIG. 21 .

Since the same address information is calculated for the packets P31 and P32, it is transmitted to the PE indicated by the same address information, and the addition instruction I16 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data (dp+0) to generate a new packet P39. Since the instruction number information becomes "1" in the packet P39, the remaining addition instruction I16 is not used for calculating the address information.

Similarly, since the same address information is calculated, the packets P33 and P34 are delivered to the PE indicated by the same address information, and the addition instruction I11 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data (sp+0) to generate a new packet P40. In the packet P40, the extension flag is "1" and the instruction number information is "0", so the same address information as that of the packet P35 is calculated based on the entire extended identification information portion.

Packets P40 and P35 in which all instruction number information is "0" are delivered to the PE indicated by the same address information, and instruction addition processing Pa is executed. Then, extended identification information is added to the data (sp+0) of the packet P40 whose extension flag is "1" as the data (D15) of the packet P35 whose data type information is "command type" as the processing instruction part, A new packet P41 is generated.

The instruction number information of the packet P41 becomes the number of instructions "5" included in the data D15. In addition, the extension flag of the packet P41 inherits the extension flag "0" of the packet P35. On the other hand, by setting the extension flag of a packet whose data type information is "instruction type" to "1"

The packet P41 is delivered to the PE indicated by the calculated address information, and the read instruction I12 (1 input/1 output instruction) to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data [*(sp+0)] to generate a new packet P42. Since the instruction number information of the packet P42 is "4", the remaining read instruction I12 is not used for calculating the address information, and the same address information as that of the packet P36 is calculated.

The packets P42 and P36 are delivered to the PE indicated by the same address information, and the multiplication instruction I13 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data [*(sp+0)*4], and a new packet P43 is generated. Since the instruction number information of the packet P43 becomes "3", the remaining multiplication instruction I13 and read instruction I12 are not used for calculating the address information, and the same address information as that of the packet P37 is calculated. .

The packets P43 and P37 are delivered to the PE indicated by the same address information, and the addition instruction I14 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data [*(sp+0)*4+1], and a new packet P44 is generated. In the packet P44, since the instruction number information becomes "2", the remaining add instruction (I14), multiplication instruction (I13), and read instruction (I12) are not used for calculation of address information, and packet (P38) The same address information as

The packets P44 and P38 are delivered to the PE indicated by the same address information, and the division instruction I15 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data [*(sp+0)*4+1]/2 to generate a new packet P45. In the packet P45, since the number of instructions information becomes "1", the remaining division instruction (I15), addition instruction (I14), multiplication instruction (I13), and read instruction (I12) are not used for calculation of address information. Instead, the same address information as that of the packet P39 is calculated.

The packets P39 and P45 are delivered to the PE indicated by the same address information, and the write instruction I17 to be executed first indicated by the instruction number information is executed. Then, extended identification information obtained by subtracting 1 from the instruction number information is added to the execution result data*(dp+0)=[*(sp+0)*4+1]/2, and a new packet P46 is generated. . In the packet P46, even if the data type information is "command type", the extension flag is not "1" and the instruction number information is "0". Accordingly, the packet P46 is returned or destroyed until the MCE 301 indicated by the MCE ID because the packet P46 does not contain a processing instruction to be processed.

In this way, an instruction can be added to the processing instruction portion of the packet by performing the instruction addition processing Pa without using the instruction addition instruction. It is also possible to add an instruction to the processing instruction portion of the packet by executing the instruction addition instruction.

As described above, in the data processing apparatus 1, each MCE generates a packet to which extended identification information including a processing instruction is added for each data, and each packet is transmitted by a PE indicated by address information determined according to the extended identification information. acquired, and the PE executes the instruction of the packet, so that the packet to be processed is arranged based on the bit string itself, and the parallelism of processing can be improved by substantially using the existing software assets as they are.

In addition, since the address information is dynamically determined according to the extended identification information, packets to be processed are dynamically arranged based on the bit string itself, so that parallelism of processing can be further improved.

In addition, by generating a pseudo-random number based on the extended identification information and calculating address information according to the pseudo-random number, the packet distribution can be approximated to a uniform distribution, and the PE usage efficiency can be improved.

In addition, by transmitting a packet whose address information does not indicate the PE to another PE, the packet can be delivered to the PE indicated by the address information.

In addition, each PE executes an instruction to be executed first in the acquisition packet, and adds the extension identification information to the data of the execution result by changing the instruction to be executed following the executed instruction among the extended identification information into the instruction to be executed first. Thus, a new packet can be created.

Further, each PE executes an instruction to be executed first in the acquisition packet, and adds the extended identification information to the data of the execution result by removing the executed instruction from the extended identification information to generate a new packet.

In addition, when there is a storage packet in which the masked extended identification information matches the acquisition packet, the two matching packets are inputted into the ALU 260 as a pair. When there is no matching storage packet, the acquisition packet is stored in the buffer memory ( 240), it is possible to execute a two-input / one-output instruction that executes binary operation.

In addition, when the instruction to be executed first of the acquisition packet is a 1-in/out-instruction, by inputting only the acquisition packet to the ALU 260, a 1-in/out instruction for executing a unary operation can be executed.

In addition, in the comparison of the extended identification information of the acquisition packet and the extended identification information of the storage packet, by masking the left/right information of the instruction to be executed first, a two-input/one-output instruction that executes a binary operation that is a non-converting operation. can run

In addition, by calculating a hash value based on the masked extended identification information of the acquisition packet, and storing the acquired packet in a hash table in correspondence with the hash value, the masked extended identification information matches the acquisition packet efficiently. can run

In addition, by generating a pseudo-random number based on the masked extended identification information and calculating address information according to the pseudo-random number, a packet having the same masked extended identification information can be delivered to the PE, and use efficiency of the PE can be improved.

Further, by connecting only adjacent PEs to each other, the problem of wiring delay can be avoided.

In addition, by arranging PEs in a matrix like a tile processor, each PE transmits the packet to an adjacent PE in a direction close to the PE indicated by the address information. can be maintained as

Further, an interpreter-type processing unit can be constructed by sequentially generating a packet sequence from the executable code or intermediate code stored in the storage device 6 by each MCE.

In addition, by returning a packet that does not contain a processing instruction to be processed up to the MCE indicated by the MCE ID, each MCE can use the processing ID again after processing of the processing ID of the packet is completed.

Further, by configuring a data processing system including the data processing device 1 in which each MCE sequentially generates packets, the parallelism of processing in an interpreter-type parallel computer system can be improved.

In addition, as described above, in the structure of the packet shown in Fig. 7 or Fig. 19, each packet is acquired by the PE indicated by the address information determined according to the extension identification information, and the instruction is executed so that the packet to be processed is It is arranged based on the bit string itself, and the parallelism of processing can be improved by substantially using the existing software assets as they are.

Further, by recording the packet sequence generated in advance from the source program P0 as the executable code P2 on a recording medium, the executable code P2 can be used in a compiler-type processing device.

Further, by storing the packet sequence generated in advance from the source program P0 as the executable code P2 in the storage device 6, each MCE can read and use the executable code P2.

Compiler-type processing after setting the omitted MCE ID or processing ID in the intermediate packet sequence by recording an intermediate packet sequence in which at least a part of the identification information part of the expanded packet sequence is omitted (null characters are used) on the recording medium It can be used in the device.

In addition, by storing in the storage device 6 an intermediate packet string in which at least a part of the identification information part of the expanded packet string is omitted (null characters are used), each MCE reads the intermediate packet string, and the omitted MCE ID and processing You can use it after setting the ID.

Further, by configuring a data processing system including the data processing apparatus 1 in which each MCE reads a packet sequence generated in advance, the parallelism of processing in a compiler-type parallel computer system can be improved.

In addition, as described above, each PE acquires a packet in which the address information determined according to the extended identification information indicates the PE among the packets to which the extended identification information including the processing command is added for each data, and executes the command to obtain the packet to be processed. It is arranged based on the bit string itself, and the parallelism of processing can be improved by using the existing software assets substantially as they are.

In addition, each PE may transmit the packet to the PE indicated by the address information by sending a packet whose address information does not indicate the PE to another PE.

In addition, each PE executes the instruction to be executed first of the acquisition packet, and adds extended identification information that changes the instruction to be executed following the executed instruction to the instruction to be executed first to the data of the execution result to generate a new packet By doing so, it is possible to dynamically place and execute the command for the new packet as well.

In addition, the said embodiment is for making the understanding of this invention easy, and is not intended to limit and interpret this invention. The present invention may be modified and improved without departing from the spirit thereof, and equivalents thereof are included in the present invention.

One : data processing unit 6: storage unit 7: input device 8: output device 9: Bus 100?115: PE (Processing Element) 210: input/output unit 211: address information calculation unit 212: light emitting element 213: light receiving element 214a?214d: output port 215a?215d: input port 230: comparison/selection unit 231: hash value calculation unit 240: buffer memory 250a, 250b: operand buffer 260: ALU (arithmetic logic operation unit) 300 to 303: MCE (memory control element) 400: cache memory 500: communication path (transmission path) 501: transmission material (core) 502: reflection material (cladding) 503: absorbent material