JPH02240784A - Data driven data processor - Google Patents

Abstract

PURPOSE:To execute the processing at a high speed by executing a vector processing for performing repeatedly the same processing to each element data of vector data in a vector storage unit by a control of a vector instruction control unit. CONSTITUTION:When a vector instruction packet for instructing a vector instruction is inputted to an instruction executing unit EXE, a vector processing for performing repeatedly the same processing to each element data of vector data in a vector storage unit PS is executed by a control of a vector instruction control unit NC. Accordingly, a vector arithmetic mechanism is led into the instruction executing unit EXE, and a vector arithmetic instruction can be executed locally to array data stored in the vector storage unit PS. In such a way, the vector arithmetic processing can be simplified and can be executed at a high speed.

Description

DETAILED DESCRIPTION OF THE INVENTION (a) Field of Industrial Application The present invention relates to a data-driven data processing device such as a dataflow computer that executes a dataflow graph as a program.

(b) Conventional technology In recent years, research has been progressing toward the realization of practical parallel processing computers, and the inventor has already completed the development and evaluation of a data-driven computer and its language processing software. are doing.

(Tanaka et al.: "Prototype of data-driven computer SPM", Information Processing Society of Japan Figure 36 National Conference Proceedings 7B-5゜Nishiyo et al.: "Compiler for data-driven computer SPM",
7B-6゜Tanaka et al. = “Performance evaluation of data-driven computer SPM (1)
"Information J/FI Processing Society Figure 37 National Conference Lecture Proceedings lN
-4゜Okamoto et al.: “Performance evaluation of data-driven computer SPM (
2)'' same lN-5゜] In general, a data-driven computer executes as a program a data flow graph in which various instructions are connected by arcs indicating the flow of data. Arithmetic processing is performed using simple execution rules in accordance with the non-Neumann philosophy of "executing processing from the beginning."

Such a data-driven computer mainly consists of three components: a data pair detection mechanism, an arithmetic processing mechanism, and a program storage mechanism, and the outline of its execution processing is as follows.

First, a data-driven computer uses a set of data called a packet as a unit, and the packet is composed of data to be processed, connection information (node number) of a data flow graph, instruction code, and the like.

This data pair detection mechanism detects and outputs a set of operand packets that can be operated on. The detected set of operand packets is then processed by the arithmetic processing unit. The resulting packet is assigned a new node number in the program storage and sent to the data pair detection mechanism. By continuing to repeat this process, a series of processes is executed.

The applicant of this application has developed a highly parallel data-driven computer EDDEN (Enhancement), which is a data-driven computer as described above, in particular, which has various improvements made to its processor architecture.
d Data Driven ENGine). In the second EDDEN, we aim to operate a large-scale data-driven computer that connects up to 1024 element processors realized by 1-chip 108LSI, and also a small-scale system with several PEs, and a small-scale system with several dozen PEs. The goal is to enable a flexible configuration such as a medium-sized system, and to adapt it to a wide range of fields such as signal processing, image processing, graphics, various simulations, and CAD.

(c) Problems to be Solved by the Invention Although data processing devices such as the data-driven computer mentioned above are suitable for non-formal arithmetic processing, due to their original mechanism, they cannot handle calculations such as vector inner product calculations. Due to the repeated processing of regular, simple calculations, a decrease in processing speed and performance was unavoidable.

Accordingly, one object of the present invention is to provide a data-driven data processing device and a data processing method that can compensate for the performance degradation in vector arithmetic processing and enable high-speed processing.

(d) Means for Solving the Problems The data-driven data processing device of the present invention includes an instruction execution unit that executes instructions such as logic and arithmetic operation instructions, and a unit that controls the execution of vector instructions following the instruction execution unit. and a vector storage unit in which vector data is stored, and when a vector instruction packet instructing a vector instruction is input to the instruction execution unit, the vector instruction control unit Vector processing is performed in which the same processing is repeatedly performed on each element data of vector data in a storage unit. Further, according to the device of the present invention, the arithmetic unit in the instruction execution unit executes a scalar operation or a vector operation.

Further, in the data processing method of the data-driven data processing device of the present invention, the instruction execution unit includes a binary operation instruction packet containing two operand data for a binary operation;
When a scalar operation instruction packet such as a unary operation instruction packet containing single operand data for a unary operation is input, the instruction execution unit performs a predetermined operation process on the operand data in the operation within the instruction execution unit. It is executed using a device and outputs a result packet storing the obtained calculation result data.

(e) Effect: According to the data-driven data processing device of the present invention, a vector operation mechanism is introduced into the instruction execution unit, and vector operation instructions can be locally executed on array data stored in the vector storage unit. , it is possible to simplify and speed up vector calculation processing.

Furthermore, according to the data processing method of the present invention, the arithmetic unit in the instruction execution unit is shared in time-sharing for normal scalar data arithmetic processing and vector data arithmetic processing. In other words, vector arithmetic processing can be performed in the free time of scalar arithmetic processing, thereby improving the sufficiency rate of the arithmetic pipeline.

(f) Embodiment FIG. 1 shows a highly parallel data-driven computer system as an embodiment of the present invention, and FIG. 2 shows the configuration of element processors.

First, the element processor (PE) shown in Fig. 2 basically consists of a program storage (PS), a firing control/color management section (FC
CM), instruction execution unit (EXE), and queue memory (Q
) are connected in a circular pipeline (ring) structure.

The program storage (ps) updates node numbers, assigns constants, and copies results. Ignition control/color management department (
FCCM) performs firing control and management of color acquisition and release using a two-stage queue storage method. Instruction execution unit (E
XE) executes instructions such as floating point/integer operations, conditional judgment, branching, and simple constant generation, and composite instructions thereof.

(Q) is a buffer that absorbs any data flow fluctuations on the ring. Buffer storage is required for ■copying, ■forced input to the ring, ■output delay from the ring,
(2) This is when a search of the waiting list in FCCM occurs. This element processor (PE) has a queue (Q
) is added with a function to dynamically change the operation mode of ■ to ■ according to the data retention amount, thereby controlling the degree of parallelism. Furthermore, when the queue (CQ) inevitably overflows, an external queue is created on the external data memory (E D M ) to absorb the overflow and continue program execution.

The network control unit (NC) maintains four communication ports for north, south, east, and west, and performs routing control based on a torus connection network of a maximum of 1024 processors (PEs). The vector calculation control unit (VC) controls the execution of vector calculation related instructions and normal memory access patrol. The control section (VC), the input control section (IC) and the output control section (QC)
) A bypass line for communication is provided between the structure and vector). The external data memory (E D M ) is a data memory that stores structures, etc., and has a capacity of 512 KB.
e (128 words x 32 bits). The clock system is synchronous, but the network control unit (NC)
It is assumed that the internal operation is self-synchronous.

EDDEN using many such elemental processors (PE)
The basic system configuration of nXn is shown in Figure 1.
The basic idea is to connect two element processors with a torus connection network. The torus connection network is a network in which a large number of processors are arranged in rows and columns, and a plurality of vertical communication lines cyclically connect processor rows in each vertical direction, that is, north-south direction (N-5), and each horizontal direction, that is, east-west direction (N-5). Data communication between arbitrary processors is made possible by a plurality of horizontal communication lines that cyclically connect the processor rows of .about.VE).

In the system of this embodiment, data exchange with the network is performed by inserting a network interface (NIF) into any communication link in the north-south direction (N-8). The interface (N IF) and 16 to 64 element processors are mounted on one processor board, and torus connection links are formed on the printed circuit board.

The configuration of a small/medium-sized system is to use a general-purpose EWS or a personal computer as the host computer, and connect it to the network interface (NIF) via the bus interface.In terms of implementation, one to four processor boards and One bus interface board will be directly inserted into a rack such as an EWS.

As for the configuration of a large-scale system, the following two types of configuration methods can be considered depending on the field of application.

■Cluster connection The processor boards described above are connected as one cluster, and the clusters are connected via a cluster interface.

The cluster interface manages the collection and distribution of data within each cluster.

■ Large torus connection 1024 (32 x 32) element processors are connected by a torus connection network. As a mounting form, 32 element processors and NIFs in the north-south (N-9) direction are mounted on one printed circuit board, and links in the east-west (W-E) direction are formed on the motherboard.

The data packets used in the data-driven computer configured as described above can be broadly divided into execution packets used for program execution and non-execution packets used for purposes other than program execution.The packet format is a packet that holds a structure body. Other than that, the length is fixed, and 33 bits x 2 words are used on the pipeline ring in the processor (PE), and 18 bits x 48 HFft is used on the network.

FIG. 3 shows the configuration of an instruction execution section (EXE) connected to a vector calculation control section (VC), and its operation will be briefly summarized below based on the figure.

(i) The instruction execution unit (EXE)
When an operation packet in which a code indicating instruction execution in XE) is written, the processing specified by the main instruction code and sub-instruction code further written in the packet is executed.

(ii) The main instruction code specifies the processing in the integer/floating point calculation section (A), and the sub instruction code specifies the processing in the integer/floating point calculation section (C) and the vector calculation control section (VC).
Specifies the processing in

(iii) The input control unit (1) prepares the following data as input data to the calculation unit (A).

■Data from the firing control/color management unit (FCCM) preceding the instruction execution unit (EXE).

■ Data read from the external data memory (EDM) under the control of the memory control (MC) of the vector calculation control unit (VC).

■ Simple constant data generated based on sub-instruction code.

(iv) The condition determination/branching unit (C) determines the truth or falsehood of the condition specified by the sub-instruction code and performs branch processing.

(v) The vector operation control unit (VC) performs control to continuously process the vector operation specified by the main instruction code in the form specified by the sub instruction code.

(vi) The arithmetic instruction of the arithmetic unit (A) is 32-bit v! These include logical operations on numbers, addition, subtraction, multiplication, and integer/real number conversion.

(vii) The types of instructions can be broadly classified as follows, and various compound instructions can be executed.

■ [Arithmetic instruction code: Only the arithmetic unit (A) is used.

■[Read & calculation instructions], [Constant generation & calculation instructions:
Uses input control section (1) and condition judgment/branch section (C).

■[Operation & Conditional Judgment/Branch Instruction (When the operation unit (A) is a no-operation, it is just a conditional branch instruction)]: Operation unit (
Use A) and conditional judgment/branching section (C).

■[Vector operation instructions, [memory access instructions]:
Uses an arithmetic unit (A) and a vector arithmetic control unit (VC).

The feature of the present invention lies in the vector computation control section (VC) for performing vector computation, and the vector computation control section (VC) coupled to the instruction execution section (EXE) shown in FIG.
VC) is shown in more detail in FIG.

In the circuit configuration diagram of FIG. 4, (ICTL) is an input data control circuit forming the input control section N) of FIG.
The left operand (L) and the right operand (R) of the input data packet obtained from the CCM are exchanged and the left operand is copied to the right operand.

(ALU) constitutes the arithmetic unit (A) in FIG. 3 mentioned above.

(CN D B RN ) is a condition determination/branching circuit forming the condition determination/branching section (C) in FIG. 3 described above.

(ALU) is operation 6 and performs a logical operation.

(PRI) to (PH1) are pipeline registers.

(MUXI>~(MUX7) are multiplexers.

(NC'NT) is a vector operation number counter, the number of vector operations is set by a register setting instruction, and is decremented each time an operation is performed during vector operation.

(SAR) is a scalar address register, which holds a memory address when executing a memory read/write instruction using a normal packet or when executing a load/dump.

(LAR) is a left operand address register, an initial value of which is set by a register setting instruction, and updated each time reading of one operand is completed during vector operation.

(L I R) is a left operand address difference register, which outputs an address difference value for updating the left operand address register (LAR) during vector operations.

(RAR) is a right operand address register, and the address initial value for the right operand is set and updated in the same manner as the address processing for the left operand of the left operand address register (LAR).

(RIR) is the right operand address difference register, and the above left operand address difference register (LIR)
Similarly to the address processing for the left operand, the address difference value for the right operand is output during vector operations.

(DAR) is the result operand address register;
Both operand address registers (LAR) (RAR
) As with the address processing for each operand, the address initial value for the operand is set and updated as a result of the operation result.

(D I R) is a result operand address difference register, and both operand address difference registers (L
Similarly to the address processing for each operand in IR), the address difference value for the operand is output as the result of the operation.

(LTR) is the left operand temporary register,
Temporarily holds the left operand data read earlier during vector operations.

(DDR) is a result data register, which holds the operation result for each unit operation during vector operations.

(V HE A D ) is a header register of the vector operation instruction packet, and holds information on the t ahth (header) of the vector operation instruction packet.

(SHEAD) is the header register of the normal instruction packet, and the first word (SHEAD) of the vector operation instruction packet is the header register of the normal instruction packet.
Retain Hezodano's information.

(ZDCD) is a zero determination circuit, which determines whether the vector operation number counter (N CNT ) is zero.

(, MA-BUS) is a memory address bus.

(MD-Bus) is a memory data bus.

(DBCTL) is a data bus arbitration circuit that switches the data transmission direction of the memory data bus (MD-BUS), which is a bidirectional bus. That is, when reading memory, vector operation operand data (VD) on the memory data bus (MD-BUS) is output to the arithmetic unit (ALU), and when writing memory, memory write data (VWD) is output from the memory data bus (MD-BUS). MD-BUs>. Note that when using the contents of the result data register (DDR) as an operand for the next operation, this memory write data (VWD)
The value of is outputted to the arithmetic unit (ALU) as vector operation operand data (VD).

(CTLGEN) is a control signal generation circuit that includes various registers, multiplexers (MUX), counters (NCNT
), an arithmetic unit (ALU), an adder (ADDER), and a data/< space arbitration circuit (DBCTL).

Note that (PDI) and (PDO) are input packet data,
Shows output packet data.

The operations of the instruction execution section (EXE) and vector calculation control section (VC) consisting of the above circuit configuration are shown in Fig. 5(a) to (e).
This will be described in detail below with reference to an example packet.

■ Loading initial data to data memory First, for vector calculation, external data memory (EDM) l:n+
A loading process for storing each element <xo...xn> of a one-dimensional vector X and each element <yo...yn> of a vector Y will be described.

The input data load packet is, for example, shown in FIG.
), and the lA! of this packet is of the form The [load address] in the header is the input packet data (PDI)
line, scalar address register C5AR>, scalar address (SA) line, multiplexer ()H; ] is the input packet data (PDI) line, the multiplexer (MUX7
), the memory write data (VWD) line, and the memory data bus (MD-) via the data bus arbitration circuit (DBCTL).
BUS), the data write signal (WRN) is set to '0', and this [load data] is written to the external data memory (EDM).

By repeating such write processing, data is loaded into the external data memory (EDM) as shown in the initial data storage example of FIG. Incidentally, FIG. 7 shows an example of data storage in the external data memo J (EDM) after vector calculation, which will be described later.

11 Rows of vectors As shown in Figure 6, each element of vector For X+Y
This section describes the instruction execution for vector operations.

FIG. 5(b) shows an example of a register value setting command packet for performing vector operations. The instruction code is sent from the pipeline register (PR1) to the normal instruction packet header register (SHEAD) and the control signal generation circuit (CTLGEN) via the normal operation instruction code (SOP) line.
) is entered. For the packet in Figure 5(b),
The instruction code written in the first word (header b) is decoded by the control signal generation circuit (CTLGEN),
A predetermined register to be set is determined.

On the other hand, register setting data is input packet data (PD
I) line, via multiplexer (MUX4) (VA)
Output to line. After that, the control signal generation circuit (CTLG)
Under the control of EN), only the latch signal of a predetermined register is output, and the value of register setting data is output to the predetermined register.

With such a register value setting instruction, the left operand address register (LAR) is set to address [XA0], the right operand address register (RAR) is set to address [YAO], and the result operand is set to correspond to the data storage example in Figure 7. The address register (DAR) contains the address [ZA
O] is set. Furthermore, a difference value [1] is set in each of the left operand address difference register (LIR), right operand address difference register (RIR>), and resultant operand address difference register (DIR).

Fig. 5 (An example of a vector operation instruction packet is shown in C>.) In the a!th (header C), an instruction code indicating vector operation, in this case, vector addition X+Y, is written, and furthermore, in the second word, is vector length (number of vector operations) −
It is assumed that 1=n is written.

When such a packet is input, each address register (LAR), (RAR), (DAR) at that time
, and each address difference register (LIR), (RI R
), (DIR) are used to start the vector operation.

Furthermore, the data value n is stored in the vector operation number counter (NCNT) via the input packet data (FDP) at the time of starting the vector operation. In this way, by the control operation of the control signal generation circuit (CTLGEN), vector elements X and y read from the external data memory (EDM)
The addition process in the arithmetic unit (ALU) for o is Xo+yo
The processing is performed sequentially from xn+yn, and the summed values are sequentially stored in an external data memory (EDM) as shown in FIG.

111 Normal Performance Scalar Execution Meanwhile,
The execution of a normal arithmetic (scalar arithmetic) instruction that is processed by a normal data-driven data processing device will be described.

FIG. 5(d) shows an example of a normal operation command packet obtained from the firing control/color management unit (FCCM). The first word (header d) of the packet in the figure holds multiplication "x" as an instruction code, and the second word holds a left operand [5dx1] and a right operand [5dyl].

Furthermore, FIG. 5(e) shows another example of a normal operation instruction packet, and the first word (header e) of the packet in the same figure holds a subtraction "-" as an instruction code. ,2
The left operand [s d x
2] and the right operand [s dy 2] are retained.

When a packet such as the above two packets for such a scalar operation is input, the left operand is a vibration line register filter (PRl), an input data control circuit <1 (TL
), the multiplexer (MUXI), the left operand data (LD 1 ) line, and the pipeline register (PH1), and is input to the arithmetic unit (ALU). On the other hand, the right operand includes the pipeline register (PH1), input data control circuit (ICTL), multiplexer (MUX2), and right operand data (RD 1 )! , pipeline register CPR4) and is input to the arithmetic unit (ALU). At this time, an arithmetic operation is performed in the arithmetic unit (ALU), and the resultant data is output to the multiplexer (MUX3) and to the output packet data (PDO) line. Also, the header of the first word of the packet is the pipeline register (PRI).
) is temporarily stored in the header register (SHEAD), and then output to the output packet data (PDU) line via the multiplexer (MUX3). This output packet data (PDU) is output to the first word while retaining the contents of the ladder register (SHEAD) as it is.
This becomes a two-word packet that holds result data in each word.

■ Line 1 of vector '°- and scalar operation As mentioned in 1 and ■1 above, the incision data is loaded into the instruction execution unit (EXE) [Figure 5 (a)] 6 at t&
registers (LAR), (RAR), +DAR), (
LIR), (RIR), rDIR) with values set [
5(b)], the packets shown in FIG. 5(c), (d), and (e) as described in II and Ill above were continuously input from the firing control/color management unit (FCCM). Parallel time-sharing instruction execution processing of vector operations and scalar operations in this case will be described based on the signal timing diagram of FIG.

In the case of the same figure, the vector operation instruction packet of FIG. 5(c) is input at time [-1, and the operation unit (ALU) is
In l, the first element addition of vector operation <x0+y. =
z O> is performed, and the number of nails continues at time t3.15. ...
Addition of subsequent elements < x + + Y += z
+>, < x *+ y w= z *>...
・ will be performed sequentially.

In the arithmetic unit (A L U ), normal data-driven scalar operations, such as binary operations such as addition and multiplication, are executed at even-numbered times due to data-driven regulations.

A packet indicating the end of such a vector operation is sent at time t
2n◆1. Output packet data (PDO) at t2n◆2
Output to line.

For the scalar operation packet y) in FIG. 5(d) input at time t1, the arithmetic unit (ALU) is <5d at time t4.
xl+5dyl>, this value appears on the output packet data (PDO) line at time t5, and the value appears on the output packet data (PDO) line at time t6.
is output. Subsequently, Fig. 5 (e
) at time t6 for the scalar operation packet of the arithmetic unit (
ALU) performs the calculation process <5dx2+5dy2>, and the value of the lever at time t7 appears on the output packet data (PDO) line and is output at time t8.

Therefore, the scalar operation and the vector operation are time-divisionally driven so that the arithmetic operations proceed simultaneously without waiting for each other. In other words, when a program is executed in which vector operation instruction packets and normal operation 'g and Qr instruction packets are mixed and input to the instruction execution unit (EXE), the operation unit (ALU) operates effectively without interruption. As a result, calculation processing efficiency is improved.

(G) Effects of the Invention According to the present invention, regular operations (vector operations) that repeat simple calculations on regular structures such as arrays, which has been a problem with conventional data-driven data processing devices, are now possible. A data processing method that prevents performance degradation and enables high-speed processing,
In addition, a data processing device can be realized.

[Brief explanation of drawings]

FIG. 1 is a system configuration diagram of a data-driven data processing device of the present invention, FIG. 2 is a schematic configuration diagram of a processor of the device of the present invention, FIG. 3 is a configuration diagram of main parts of the processor in FIG. 2, and FIG. 4 5(a) is a block diagram showing a specific configuration of the main parts of the processor (instruction execution section and vector operation control section) in FIG. 3.
6 and 7 are memory diagrams, and FIG. 8 is a signal timing chart for disabling the main parts of the processor shown in FIG. 4. (PE)...Element processor, (EXE)...Instruction execution unit, <EDM)...External data memory, (NC)
...Network control section, (VC)...Vector calculation control section. Figure 1

Claims (4)

[Claims] (1) In a data-driven data processing device that executes a data flow graph as a program, there is an instruction execution unit that executes instructions such as logic and arithmetic operation instructions, and an instruction execution unit that is connected to the instruction execution unit and controls the execution of vector instructions. and a vector storage unit in which vector data is stored, and when a vector instruction packet instructing a vector instruction is input to the instruction execution unit, the vector instruction control unit A data-driven data processing device characterized by executing vector processing in which the same processing is repeatedly performed on each element data of vector data in a storage unit. (2) The instruction execution unit includes an arithmetic unit that performs logical and arithmetic operations, and when the vector instruction indicates arithmetic processing on a vector in the vector storage unit, the vector instruction control unit repeated operations on vector data and constant data by successively reading out each element data of the vector data from the storage unit and continuously supplying it to the arithmetic unit;
2. The data-driven data processing device according to claim 1, wherein the data-driven data processing device performs vector operations such as repeated operations on different vector data. (3) The instruction execution unit receives a scalar operation instruction packet such as a binary operation instruction packet containing two operand data for a binary operation or a unary operation instruction packet containing single operand data for a unary operation. 2. The data-driven data processing device according to claim 1, wherein when the instruction execution unit receives the input data, the instruction execution unit executes predetermined arithmetic processing on the operand data using an arithmetic unit in the instruction execution unit. (4) An instruction execution unit that executes instructions such as logic and arithmetic operation instructions, a vector instruction control unit that is connected to the instruction execution unit and controls the execution of vector instructions, and a vector storage unit that stores vector data. In the data processing method of the data-driven data processing device, the instruction execution unit includes two units for binary operations.
When a scalar operation instruction packet such as a binary operation instruction packet containing two operand data or a unary operation instruction packet containing single operand data for a unary operation is input, the instruction execution unit performs a predetermined operation on the operand data. A data processing method, characterized in that the arithmetic processing is executed using arithmetic units in the instruction execution unit in a time-sharing manner, and a result packet storing the obtained arithmetic result data is output.