JPH03223980A - Computer system - Google Patents

Abstract

PURPOSE:To enable efficient calculation and to eliminate necessity for an operator to be conscious of control structure so much in the case of programming by executing a processing by data drive concerning a part suitable for the parallel processing of a program and executing a processing according to a Neumann system concerning the other part. CONSTITUTION:A master processor 1 to successively broadcast a program statement for each program element plural memory banks 41-4n being divided in interleave, plural sub processors 31-3n to execute the program statement corresponding to the memory banks 41-4n are provided. The sub processors 31-3n are equipped with shift register files to store the program statement broadcasted from the master processor 1 and arithmetic units. Therefore, the master processor 1 can execute the calculation since a Numann type processor entrusts the broadcast of the program statement to the sub processor to a control unit. Thus, the efficient calculation can be executed.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a calculation method for an electronic computer,
Particularly concerned with computer systems that incorporate data-driven parallel processing and are capable of efficient calculations.

[Conventional technology] Conventionally, the main electronic computer systems with different calculation methods were:
There were the Neumann method, the array processor method, and the data flow one-way method.

Among these, the Neumann method sequentially executes a program written as a chain of instructions.

Furthermore, the array processor method aims to speed up processing by operating a large number of processors in parallel.

On the other hand, data-flow type electronic computers differ from the two methods mentioned above in that each operation is executed when the operand data is ready (this is called the data-driven method), allowing for efficient parallel operation. can be expected.

[Problems to be solved by the invention] In each conventional computer system as described above,
Neumann type electronic computers have the advantage of simple arithmetic control because they execute instructions one by one sequentially, but it is basically difficult to execute separate instructions in parallel. Furthermore, there is a problem in that the calculation speed is limited by the time required for memory access.

In addition, in the case of array processor type computers, synchronization and communication control between processors is complicated, and efficiency cannot be improved unless programs are created taking into account job contents and processor configuration. There was a problem.

On the other hand, in the case of a data-flow type electronic computer, efficient parallel operation can be expected because the processing is data-driven as described above, but for serial programs with little room for parallel processing, the Neumann method is The problem was that it was more efficient.

The present invention was created in order to solve the problems mentioned above, and its purpose is to perform data-driven processing on the calculation parts suitable for parallel processing of the program, and to perform processing on the other parts using the Neumann method. The object of the present invention is to provide an electronic computer that can perform efficient calculations.

[Means for solving the problem] Either a function to move up all words after a given base word by word or a function to move down consecutive spreads in a given range word by word, and an associative memory function. A storage device that has the function of writing data is called a shift register file, and either the variable name or the address of the storage area of that variable and the corresponding data, or a register identifier temporarily assigned to a word in the shift register file. , immediate data, or an operator indicating an arithmetic operation is called a program element, and a sequence of program elements that has meaning in terms of reverse Polish format or a similar format is called a program statement. It has the following characteristics.

(b) A main processor that sequentially broadcasts program statements for each program element, a plurality of memory banks divided into interleaved sections, and a plurality of sub-processors provided corresponding to the memory banks that execute program statements. Equipped with.

(rl) The sub-processor is equipped with a shift register file for storing program statements broadcast from the main processor and an arithmetic unit.

(c) Program statements are written to the shift register file immediately after the area where each program element has already been written.

(d) Data corresponding to the variable name or the address of the area corresponding to the variable is written into the corresponding word of the shift register file by the associative memory function.

(e) When a program statement whose data is complete and can be executed is detected in the shift register file, this program statement is sent to the arithmetic unit and the arithmetic operation is executed there.The result of the arithmetic operation is stored in the shift register file. The word corresponding to the area where the program statement was stored is written by the associative memory function.

In the electronic computer, when the main processor includes a conventional Neumann type processor and a control unit,
Program statements can be held in the built-in memory of the main processor, and the Neumann processor can perform calculations by entrusting the control unit with broadcasting the program statements to the sub-processors.

[Sakuten] When the main processor broadcasts a program statement meaning the calculation of a variable to all the subprocessors, the subprocessor that executes the operation writes the above program statement to the shift register file and stores the operands of the operation. A subprocessor that can directly access the storage area is set to send operand data to the shift register file in the subprocessor that executes the above operation - Operands sent to the shift register file in the subprocessor that executes the above operation Data is written to words that match variable names using the associative memory function. (In this specification, "variable name" is used to include the address of the variable's storage area or register identifier.) When a program statement whose data is complete and becomes executable is detected in the shift register file, This program statement is sent to the arithmetic unit.

At that time, in the shift register file, one word in the area where the program statement to be sent is stored is rewritten to a register identifier, and for the remaining words, all words located after (previously) are carried forward along with the sending. (goes down)
This will narrow the gap.

The operation result obtained in the operation unit is written into the corresponding word of the shift register file by the associative memory function based on the register identifier assigned when the program statement was sent from the shift register file.

In the shift register file (variable name, data, =)
When a program statement in the form of direct data assignment in which words are arranged like (variable name = data) is detected, the data is stored in the variable storage area. At this time, the space in the area of the shift register file where the program statement is stored is narrowed by moving up (down) all the words located after (before) the program statement.

[Embodiment] FIG. 1 is a block diagram of an embodiment of the present invention, including: 1
2 is a main processor, 2 is a communication network, 31 to 3n are sub processors, and 4. ~4° each represents a memory bank.

In FIG. 1, interleaved memory banks 41 to 4n are bidirectionally connected to respective sub-processors 31 to 3o provided correspondingly, and these sub-processors are connected to a communication network 2. to each other through the other sub-processors 3. .about.311 and the main processor 1.

FIG. 2 is an explanatory diagram showing a detailed 10-configuration of the main processor and sub-processor, in which 11 is a Neumann type processor, 12 is a control unit, 13 is a built-in memory, 51 is a shift register file, and 61 is described later. C represents an unstored variable list to be described later, 81 represents a fetch address queue to be described later, and 91 represents an arithmetic unit.

Note that the arithmetic unit can have a configuration in which a plurality of arithmetic operations can be performed in parallel.

Data transfer control memory stores the destination for transmitting operand data to a subprocessor that executes an operation in a subprocessor that can directly access the operand storage area, and when operand data is obtained, it is sent to that destination. This enables the transmission of

The unstored variable list stores variables that have not yet been stored in the intended storage area among the variable names whose calculations have been instructed by the program statements broadcast from the main processor.

Furthermore, the fetch address queue is configured as a queue that stores the address of the storage area of the data to be fetched from the memory pan=11.

All subprocessors have the same configuration.

The detailed configuration and operation of each component of this embodiment will be explained below.

(a) Main processor The main processor is a Neumann type processor 11. It is composed of a control unit 12 and a built-in memory 13.

A Neumann processor delegates execution of parts of a program suitable for data-driven processing to a control unit. That is, the main processor holds in its built-in memory a program statement in which program elements are arranged according to reverse Polish notation, and the control unit broadcasts the program statement to the sub-processors when instructed by the Neumann processor.

In either sub-processor, shift register file, data transfer control memory, unstored variable list,
If one of the fetch address queues is about to overflow, or if the variable name whose calculation is instructed in the program statement broadcast from the main processor 12- is in the transfer variable name column of the data transfer control memory or an unstored variable. If the variable name is stored in either of the lists (this means a revision of the variable data in use by the main processor or the subprocessor), then I! The I control unit is notified and the broadcast of the program statement is interrupted.

When the above condition is resolved, the sub-processor notifies the control unit again, and broadcasting of the program statement is resumed.

When the control unit finishes broadcasting the program text entrusted to it by the von Neumann processor, it notifies the von Neumann processor by an interrupt or the like.

In order to ensure consistency between the processing of the von Neumann-type processor and the processing of the sub-processors, a list (not shown) of variable names whose calculations are delegated to the sub-processors is prepared in the main processor, and the von Neumann-type processor Each time the built-in memory is accessed, the variable name list is searched, and in the case of a variable for which a calculation result has not been received from the sub-processor, the Neumann type processor 3-3 enters a standby state.

The control unit writes the variable name list when broadcasting a program statement, and deletes the variable name from the variable name list each time the calculation result sent from the subprocessor is stored in the built-in memory.

It is not necessary for the secondary processor to send all calculation results to the main processor, but at least if the address where the calculation results are stored is included in the range that has been copied to the internal memory of the main processor, It is necessary to send the calculation results.

Therefore, in order to determine whether or not the sub-processor should transmit the calculation result to the main processor, the control unit may assign a tag for each program element.

In addition, the distinction between variable names, data, operators, etc., the distinction between whether a variable name indicates the storage area of an operand or the storage location of a calculation result, the description of a vector variable, and the operator. In this case, it is desirable to add a tag to the program element that allows the number of operands to be displayed.

(b) Shift Register File FIG. 3 is an explanatory diagram showing the detailed structure of the shift register file. Shift register file 51 is 51
i, 52i~, and each word consists of first field 5111.5211~ second field 5121.522i~ and arithmetic control field 5131.523i~.

The first field is written with a variable name, the address of the variable storage area, a register identifier temporarily assigned to identify the word in which the calculation result obtained by the calculation unit is written, and the second field is written with an arithmetic If there is an operator indicating an operation, immediate value data, or the first field, data corresponding to the contents are written.

The shift register file has an associative memory function that uses the first field as a collation field and writes data into the second field of matching words such as variable names.

15- The calculation control field indicates whether each word means a storage location for the calculation result, an operand, or an operator; if it is an operator, how many operands there are; if it is an operand, it is This is an area for storing control information such as whether data has been written to the second field.

FIG. 5 is an explanatory diagram specifically showing the operation of the shift register file, and the operation of the shift register file will be explained below based on this diagram. (here,
In order to indicate the contents of the shift register file 51 at each step of execution, a hyphen and a number corresponding to the step are added to the end of the code of each part. ) The program statements from the main processor are e.g. (Ai,
α, 5, tree, =) (means Ai = α * 5. Also, Ai
The subscript i represents the memory bank number. ), it is written to the shift register file 51 inside the sub-processor 31 as 51-1. Here, the variable name of the operand is written in the first field, such as 521-1, and the other pro-16-Durham elements are written in the second field.

When the value '3' of the variable α is sent from another sub-processor or the data transfer control memory 61, the associative memory function stores the value '3' of the word 52i-2 in which the variable name [α] is written in the first field. This value '3' is written into field 2.

Then, the program statement (3, 5, *) (meaning 3*5) consisting of the three words 52i-2, 53i-2, and 54i2 becomes executable, so it is sent to the arithmetic unit 91 and is sent to the 51-3 As shown in , the register identifier [■i] is written in the first field of 52i-3 (the second field is left blank), and each part of 55i-2, 56i-2 ~ are all carried forward by two words to become 53i, respectively. -3,54
Move to 1-3~. Register identifiers shall be assigned in each shift register file so as not to be duplicated.

When the value '15' of the execution result of l3*5j is sent from the arithmetic unit 91, the associative memory function writes the register identifier [■i] in the first field. 2 fields with this value'
15' is written.

Then, 51 i −4, 52i −4, 53i −
Program statement (Ai, 15, =) (Ai, 15, =) (A
means i=15. ) indicates that the value of the variable Ai has been determined, so the data is sent to the storage location of the variable Ai, or in some cases, the data transfer control memory 61, and the data is sent to the data transfer control memory 61.
All the parts below i-4 are moved up by three words and are located below 51i-5. When the data storage of variable Ai is completed, the variable name (Ai) is selected from the list of unstored variables described later.
will be deleted.

In this embodiment, the shift register file is described as having the function of incrementing all words after an arbitrary word base in units of words, but the shift register file in the present invention has an arbitrary function instead of the above function. It is possible to have a function to move down consecutive indentations in the range of , word by word.

(c) Data transfer control memory 18 The data transfer control memory stores the destination for transmitting operand data to a subprocessor that executes an operation in a subprocessor that can directly access the operand storage area. When a message is obtained, it can be sent to that destination.

FIG. 4 is an explanatory diagram showing the detailed configuration of the data transfer control memory. The data transfer control memory 6j is 61i,
62i~, and each word is a destination storage area 6111.6211~, a transfer variable name storage area 6121.6221~, and a transfer data storage area 613.
1.6231~, and transfer control field 6141.6
It consists of 241~.

The data transfer control memory has an associative memory function that uses the storage area of transfer variable names as a collation field to write data into the storage area of transfer data of words with matching variable names.

The transfer control field is a storage area for each word, including control information such as a storage area for a transfer variable name and the presence/absence of writing 19- in a storage area for transfer data.

Next, the operation of the data transfer control memory will be explained.

In each subprocess, each time the operand storage area indicated in the program statement broadcast from the main processor is recognized to be directly accessible, the destination of an unused word in the data transfer control memory is determined. Writing is done in the column and the transfer variable name column. In this case, the destination refers to the subprocessor that executes the calculation, and is held in a register (not shown) during the broadcast of each program statement. The transfer variable name is the variable name of the operand. However, if a word with the same destination and the same transfer variable name written in the data transfer control memory is recognized, there is no need to newly write in another word.

Also, when a tag or the like indicates that calculation results should be sent to the main processor, or when the main processor requests data transmission via a command or the like, the end of the data transfer control memory 20- Writing is performed in the word destination field and the transfer variable name field. In this case, the destination is the main processor.

Transfer data corresponding to the transfer variable name is sent from the shift register file 51, memory bank 41, or the like. Writing of transfer data is performed in the storage area of transfer data of words with matching variable names using an associative memory function.

When the writing of the transfer data is completed and the communication network becomes available, the transfer is carried out and the corresponding word in the data transfer control memory becomes blank and can be used to transfer another variable data. .

(d) Unstored variable list The unstored variable/list is a list of variables whose calculations have been entrusted to the sub-processor by the main processor but have not yet been stored in the storage location, in order to avoid confusion due to revisions to variable data. is a list of variable names.

In each sub-processor, the following operation is performed every 21- when the variable name shown in the program statement broadcast from the main processor is recognized to be directly accessible.

■If the variable name indicated as the address of the storage destination of the calculation result does not exist in the unstored variable list or in the transfer variable name column of the data transfer control memory, wait until the end of the program statement and change the unstored variable name to Add to list. It is assumed that the variable name indicated as the storage location of the calculation result is held in a register (not shown) during the broadcast of each program statement.

(2) If the variable name indicated as the address of the storage destination of the calculation result exists in the transfer variable name column of the data transfer control memory, the main processor is requested to interrupt the broadcast of the program statement. After that, in the data transfer control memory,
When the writing of data corresponding to the same variable name is completed, the main processor is requested to resume broadcasting the program statement, waits for the end of the program statement, and writes the variable name to the unstored variable list again.

(22-) If the variable name indicated as the address of the storage destination of the calculation result exists in the unstored variable list, the main processor is requested to interrupt the broadcast of the program statement. Thereafter, when that same variable name is deleted from the unstored variable list, it requests the main processor to resume broadcasting the program statement, waits for the end of the program statement, and writes that variable name back to the unstored variable list.

■If the variable name indicated as the address of the operand storage area does not exist in the unstored variable list or in the transfer variable name column of the data transfer control memory, that variable name is written to the fetch address queue and memory The bank will be accessed.

■If the variable name indicated as the address of the operand storage area exists in the transfer variable name column of the data transfer control memory, the variable data is sent from the shift register file or memory bank to the data transfer control memory. It should come.

■If the variable name indicated as the address of the operand storage area does not exist in the transfer variable name column of the data transfer control memory but exists in the unstored variable list, the variable data is transferred from the shift register 23- isle. All you have to do is send it to the transfer control memory.

When the storage of the calculation result in the storage destination is completed, the variable name is deleted from the unstored variable list.

(e) Fetch Address Queue The fetch address queue is configured as a queue that stores the address of a storage area for data to be fetched from a memory bank.

In each sub-processor, the variable name indicated as the address of the operand storage area in the program statement broadcast from the main processor is written into the fetch address queue when the following two conditions are met.

(I) Direct access to each sub-processor at the processor. That is, a storage area for the variable exists in a memory bank corresponding to each sub-processor.

(n) Same variable name is fetch address queue, unstored variable list, data transfer t! It must not exist in any of the transfer variable name columns of I-restricted memory.

24- Data read requests for addresses written in the fetch address queue are sequentially sent to the memory bank corresponding to each sub-processor, and the fetch data is delivered to the data transfer control memory.

FIG. 6 and FIG. 7 are explanatory diagrams specifically showing the operation of the sub-processors 31 and 32 when there are two memory banks, 4+ and 42, and the explanation will be given below with reference to these diagrams. . (Again, we will add a hyphen and a number corresponding to the step to the end of the code of each part to indicate the state at the time as the execution step progresses. Also, 1.2 at the end of the variable name represents the number of the memory bank to which the variable belongs.) Initially, no writing is done to the shift register file, data transfer control memory, unstored variable list, and fetch address queue in the subprocessors 31 and 32. shall be.

The main processor executes program statements (Xi, Al.

B2. +, =) (meaning Xl=A1+B2). Since the storage area of the variable X1 to be calculated belongs to the memory bank 41, the program statement is written as 51-1 in the shift register file 5 in the sub-processor 31, and the variable name [X1] is written in the unstored variable restore 1. It is written as H1. Also, in order to retrieve the data of the operand variable A1 from the memory bank 41, the fetch address queue 8. The variable name [A1] is written as 81-1, and in order to send the extracted data to the shift register file 51, it is written as 61-1 in the shift register file 61. ('1' in the destination column represents the number of the sub-processor.) Similarly, variable B2 is written in the sub-processor 32 as 62-1.82-1.

Following the above program statement, the program statement (Y2.
X, 1. C1,4,*, -=) (Y2
=Xl-(C1*4)). The storage area for the variable Y2 to be calculated is memory bank 4.
2, the progera 26-4 statement is written in the shift register file 52 in the sub-processor 32 as 52-2, and the variable name [Y2] is written in the unstored variable restore 2 as 72-2. Further, so that the data of the operand variables X1 and 01 are sent to the subprocessor 32, they are written as 61-2 in the data transfer control memory 61, and the variable name [C1] is written as 81-2 in the fetch address queue 8. It is written as 2. Since variable name [X1] is recognized during unstored variable restore 1 like 7I-2, if the data of variable XI is sent from the shift register file 51 to the data transfer control memory 61, the memory bank 41 can be It does not need to be accessed and is not written to the fetch address queue. During this time, a fetch request for the data of variable AI is sent from the fetch address queue 81 to the memory bank 4.
1, the fetched data Ir1l is sent to the data transfer control memory 6I, and the associative memory function
It is written like the first word of 12. The same applies to variable B2.

Data 17' is associated with the second field of the second word from the beginning of the shift register file 51-3 by the transfer of the data 'c' of variable A1 defined in the first word of the data transfer control memory 61-2. Written using the memory function. At this time, in the data transfer control memory 6I, the first word is blanked out at the same time as the data transfer is executed. Similar processing is performed for the transfer of data of variable B2 defined by the first word of data transfer control memory 62-2.

The program statement (7, 3, 10) (meaning 7+3) consisting of the second, third, and fourth three words counted from the beginning in the shift register file 51-3 is executable, so the arithmetic unit 9. sent to. At this time, the register identifier [■
1] is written (the second field is left blank), and all words after the fifth are moved up by two words. Arithmetic unit 91
When the calculation result '10' is sent from , this value '10' is stored in the associative memory in the second field of the second word from the beginning where the register identifier [■1] is written in the first field. After the above process, the shift register file 51 becomes 51-
The content will be similar to 4.

Program statement consisting of the first three words in the shift register file 51-4 (Xi, 10°=)
(meaning X1=10) indicates that the value of variable All words are moved up by three words, resulting in something like 5+5. In the data transfer control memory, data 110' corresponding to variable name [X1]
is written as 6I-5 using the associative memory function. When the storage of the data of the variable X1 in the memory bank 41, which is the storage destination thereof, is completed, the variable name (Xl,) is deleted from the unstored variable list.

Thereafter, similar operations are performed one after another, and finally the value of variable Y2 is determined to be 22', this data is stored in memory bank 4, and the processing for the above two program statements is completed.

=29= Note that a state that completely matches the state of each step shown in FIGS. 6 and 7 is not necessarily realized. This is because the execution time and timing of each operation depend on the current state of the communication network and other conditions, the detailed configuration of the hardware, etc.

Further, in the above embodiment, the case where two sets of memory banks and two sub-processors are provided has been described, but the present invention can also be configured to provide sets of powers of 2 such as 4, 8, and 16 sets. It is possible.

Furthermore, it is also conceivable to pipeline the arithmetic units in the arithmetic unit or to provide a plurality of arithmetic units and operate them in parallel.

It is possible to define vector variables and use them in program statements to perform vector operations. Vector variables and scalar variables are distinguished by tags and the like. A vector variable is described by specifying, for example, the address of the first vector element, the address interval between vector elements, and the vector length. Each sub-processor is configured to determine whether vector elements belonging to the corresponding memory bank exist, and if so, perform operations on them in the same way as when scalar operations are performed individually. And it is sufficient.

[Effect of the invention] The method of the present invention has the following advantages.

(A) Efficient calculation can be performed by performing data-driven processing on parts of the program that are suitable for parallel processing, and processing other parts using the Neumann method.

(B) Since each sub-processor independently performs data-driven operations, the control structure of the sub-processor group is simple, and there is no need to be aware of this control structure during programming.

(C) If the main processor is configured to include a conventional Neumann type processor, conventional technology can be used for basic software such as an operating system. In particular, since the conversion from a high-level language to reverse Polish notation is straightforward, the burden on the compiler is reduced.

31-

[Brief explanation of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention, FIG. 2 is a block diagram showing the detailed configuration of the main processor and sub-processor, FIG. 3 is an explanatory diagram showing the detailed configuration of the shift register file, and FIG. The figure is an explanatory diagram showing the detailed configuration of the data transfer control memory, Figure 5 is an explanatory diagram showing the contents of the shift register file each time an operation is performed, and Figures 6 and 7 are the sub-processor and memory bank. FIG. 4 is an explanatory diagram showing the contents of a shift register file, a data transfer control memory, an unstored variable list, and a fetch address queue each time an operation is performed when two sets of data are provided. 1 ・−1−−−−−−−−−−−−−−−−−−1 Main processor 11 ・−11−−−−−−−−−−−−−
---Neumann type processor 12 ---
---------- Gig control unit 13 ----
−−−−−−−−−−−−−−1 built-in memory 2 ・−1 −−−−−−−−−−−−−−−−−−1 communication network 31 ~
31-3n-Sub-processor 32--41-5-6-7-8i-9-4o-Memory bank-5n-Shift register file-6n-Data transfer control memory-7o-Unstored variable list ~8o-7 Etsuchi address skew~9o-calculation unit

Claims (2)

[Claims] (1) It has either the function of moving all words after a given word forward word by word or the function of moving down a certain range of consecutive words word by word, and the function of writing data using an associative memory function. The storage device is called a shift register file, and it stores either the variable name or the address of the variable's storage area and the corresponding data, a register identifier temporarily assigned to a word in the shift register file, immediate value data, or arithmetic operations. An electronic computer that has the following characteristics: An operator that indicates the following is called a program element, and a sequence of program elements that has meaning in the reverse Polish format or a similar format is called a program statement. (b) Equipped with a main processor that sequentially broadcasts program statements for each program element, a plurality of interleaved memory banks, and a plurality of sub-processors provided corresponding to the memory banks that execute the program statements. do. (b) The sub-processor is equipped with a shift register file for storing program statements broadcast from the main processor and an arithmetic unit. (c) Program statements are written to the shift register file immediately after the area in which each program element has already been written. (d) Data corresponding to the variable name or the address of the area corresponding to the variable is written into the corresponding word of the shift register file by the associative memory function. (e) When a program statement whose data is complete and can be executed is detected in the shift register file, this program statement is sent to the arithmetic unit and the arithmetic operation is executed there.The result of the arithmetic operation is stored in the shift register file. The word corresponding to the area where the program statement was stored is written by the associative memory function. (2) In the electronic computer according to claim 1, when the main processor has a configuration including a conventional von Neumann type processor and a control unit, a program statement is held in the built-in memory of the main processor, and the von Neumann type processor stores the program statement. A computer method characterized by entrusting broadcasting to subprocessors to a control unit.