JPS6246026B2 - - Google Patents

Description

[Detailed description of the invention]

[Technical Field to Which the Invention Pertains] The present invention relates to a parallel processing method, and particularly to a parallel processing method in a data processing device. Generally, one of the methods for speeding up arithmetic processing is a parallel processing method. This parallel processing method uses different processors to execute parts of the program that can be executed in parallel, and ideally aims to obtain N times the performance using N processors (in reality, (Because of the parts that cannot be executed in parallel and the extra time required to control the parallel operations...overhead...the performance is only N times lower.) [Prior Art] Conventional parallel processing methods have , a plurality of data memories each storing data, a plurality of processors connected in parallel to the control processor, and a memory switch for interconnecting the plurality of processors and the plurality of data memories in parallel. each of the plurality of processors includes a processor element, a control processor interface for connecting the processor element to the control processor, and a memory for connecting the processor element to the memory switch. It is configured to include a switch interface. Next, a conventional parallel processing method will be explained in detail with reference to the drawings. FIG. 1 is a system configuration diagram showing an example of a conventional parallel processing system, and FIG. 2 is a detailed block diagram showing an example of the processor shown in FIG. 1. The parallel processing method shown in Figure 1 is based on the control processor
CP, control-only memories CPM1 and CPM2 dedicated to this control processor CP, processors PP1 to PP16 connected in parallel to the control processor CP, and memories MM1 to MM1 to store programs and data.
It includes a memory switch having 16×32=512 connection points for connecting the MM 32, 16 processors, and 32 memories in parallel. Processors PP1 to PP16 all have the same configuration, and as shown in Figure 2, they have a processor element PE and a memory switch interface.
MS1 and control processor interface CP1
Contains. Memory interface MS1
sends an access request to read data or a program from the processor element PE to the memories MM1 to MM via the memory switch MS.
32 and the memories MM1 to MM32.
The data read from the processor element
In addition to supplying the data to the processor PE, the data is also supplied to the memories MM1 to MM32 to store the calculation results and the like in the processor PE. control processor interface
CP1 is connected to the control processor CP via interface a, and receives instructions to start program execution.
START and program execution stop instruction STOP are supplied from the control processor CP and supplied to the processor element PE.
Processor CP that controls processing end notification END from PE
supply to. In other words, 16 processors PP1 to PP16 are connected to 32 memories MM1 to PP16 via memory switch MS.
The MM32 can be accessed, and each of the processors PP1 to PP16 can independently execute programs. control processor
CP issues a program execution start instruction START through interface a with processors PP1 to PP16.
or receive a processing completion notification END when the processor completes execution. Under the control of the control processor CP, the processors PP1 to PP16 share and execute the parallel processing portion of the program to be solved. For example a ₁
+b ₁ , a ₂ +b ₂ , . . . , a _o +b _o , the i-th processor PP _i calculates a _i +b _i . To improve the performance of such conventional parallel processing systems, it is necessary to increase the performance of each processor or increase the number of processors. However, increasing the performance of the processor increases the size of the device, making it difficult to line up a large number of processors. Furthermore, if you increase the number of processors, you will need to expand the memory so that they can be used in parallel, and the memory switch will increase in size by the product of the number of processors and the number of memory, making it large and complex. It will still be difficult to realize (for example, considering a crossbar switch, if you double the number of processors and the number of memories, the scale of the switch will double.
×2 = 4 times). Due to these drawbacks, large-scale, ultra-high-performance parallel processing systems have hardly been put into practical use. That is, the conventional parallel processing method has a drawback in that it is difficult to increase the degree of parallelism. [Object of the Invention] An object of the present invention is to provide a parallel processing method that can increase the degree of parallelism. That is, an object of the present invention is to solve the above-mentioned drawbacks by increasing the degree of parallelism without increasing the scale of the memory switch by making each processor that performs parallel processing into a parallel processing processor consisting of a plurality of processor elements. The objective is to provide a parallel processing system with high scale and ultra-high performance. [Configuration of the Invention] The parallel processing method of the present invention includes a control processor,
a plurality of data memories each storing data; a plurality of processors connected in parallel to the control processor; a memory switch for interconnecting the plurality of processors and the plurality of data memories in parallel; Each of the plurality of processors includes a plurality of processor elements provided in parallel, a plurality of program memories provided corresponding to each processor element and storing programs, and a plurality of processor elements arranged in parallel. a control processor interface for connecting to the control processor; a memory switch interface for connecting the plurality of processor elements to the memory switch;
The data cache memory is connected to the memory switch interface and stores a copy of a portion of the data stored in the data memory. That is, the parallel processing method of the present invention consists of a plurality of processor elements each having a program memory, a data cache memory shared by the plurality of processor elements, and an access request to the data memory generated from the plurality of processor elements. A plurality of arithmetic processing units, a plurality of data memories, and an access to any of the above data memories from any of the above arithmetic processing units, and a circuit that selects and processes one of the above at each data memory access timing. It is configured with a memory switch that enables Furthermore, in addition to the above configuration, the parallel processing system of the present invention includes a control processor, a communication means for instructing all of the processor elements to start program execution from the control processor, and a control processor for controlling the end of program execution from each of the processor elements. and means for notifying the processor, and is configured to execute parallel processing portions of one program in parallel by all of the processor elements under the control of the control processor. In other words, each processor that shares the parallel processing method of the present invention is composed of a plurality of processor elements that operate in parallel, and the actual number of parallel processing processors is increased without increasing the scale of the memory switch. . That is, the parallel processing system of the present invention includes n processors and m processors, i.e., n or
Each of the n processors includes n or more data memories such as 2n processors, and a memory switch having n×m connection points for connecting the n processors and the m data memories. The internal structure of one processor consists of l processor elements and l processor elements that store programs to be executed by the corresponding processor elements in memory used exclusively for each processor element. It includes a program memory and a memory switch interface that receives and processes access requests to the m data memories from each of the l processor elements. In other words, this memory switch interface selects one of the access requests from any one or more of the l processor elements at each memory access timing, and responds to the selected access request. is sent to the data memory via the memory switch. If this access request is a read request, the data sent from the data memory is passed to the requesting processor element. In this way, since the memory switch interface is limited to one interface for accessing the data memory, the scale of the memory switch (the number of interfaces for connecting the processor) can be reduced to 1/1. In this case, access to the data memory is competed among the l processor elements, which may become a performance bottleneck. However, this problem is alleviated by first providing each processor element with its own program memory. In other words, in a normal computer, programs and data are stored in the same memory, but in the processor used in the present invention, programs are stored in a dedicated program memory for each processor element, so they cannot be transferred via the memory switch interface. Access to memory is limited to data, and the access frequency is reduced to 1/2 at most compared to a normal computer. Second, a data cache memory connected to the memory switch interface further reduces the frequency of data memory access.
In other words, data that does not necessarily need to be stored in the data memory, such as data that can be commonly used by l processor elements (such as constants) and intermediate results of calculations, is stored in the data cache memory. Reduce the number of accesses. Therefore, when a processor element requests access to data memory, the memory switch interface checks whether the data is already stored in the data cache memory.
If it is stored there, it is read from there, and only when it is not, a request is made to the data memory. [Description of Embodiments] Next, embodiments of the present invention will be described in detail with reference to the drawings. FIG. 3 is a system configuration diagram showing one embodiment of the present invention, and FIG. 4 is a detailed block diagram of the processor shown in FIG. 3. Processors PP1' to PP16' are parallel processing type processors that internally contain eight processor elements PE1 to PE8, and each has the ability to execute eight programs in parallel. The number of processor elements is not limited to this example. Each processor PP1' to PP16' can access any data memory DM1 to DM3 via a memory switch MS.
Data can be read and written to 2. The number of data memories is 32 in Figure 3, but
This depends on the number of processors, data memory performance,
It is determined by the frequency of use of the data memory and is not limited to this example. Furthermore, there are many configuration methods for the configuration of the memory switch MS, including a complete crossbar type, but the configuration is not limited to any one of them. Here, as an example, a complete crossbar system is assumed, and even if multiple processors issue requests to access the data memory at the same time, no contention will occur as long as they do not access the same data memory. Even if a memory switch MS having a different configuration is used, the effects of the present invention will not be affected. The control processor has control-only memory CPM1,
It has CPM2 and can also access data memories DM1 to DM32 via memory switch MS. Although the number of control-only memories is two in this example, it is not limited to this. The control processor CP can communicate with each of the processors PP1' to PP16' via their respective control processor interface CPI' via an interface a. FIG. 4 is a block diagram showing an example of the processor shown in FIG. 3. Processor elements PE1 to PE8 each have the ability to execute a program, and the program is a processor element that has the ability to execute a program.
The programs are stored in dedicated program memories PM1 to PM8 connected to PE1 to PE8, respectively. The memory switch interface MSI' is a control circuit for each processor element PE1 to PE8 to access data memories DM1 to DM32 shown in FIG.
When access requests are received simultaneously from PEs 1 to 8, one of them is selected according to a certain algorithm, and the selected access request is sent to the data memories DM1 to DM32 via the memory switch MS.
Send to either. In the case of a read operation, control is also performed to transfer data sent from the corresponding data memory to the requesting processor element according to the sent address. The data cache memory DC operates in the same way as a general computer cache memory. That is, processor elements PE1 to PE8
When there is an access request to data memory DM1 to DM32 from
MSI' checks the contents of the data cache memory DC, and if the desired data is already stored there, it is read from there and sent to the processor element.
Pass to PE1 to PE8. If not, data memory
An access request is made to DM1 to DM32, and the data sent from the data memories DM1 to DM32 is transferred to the requesting processor elements PE1 to PE8, and the memory switch interface is
MSI' is also stored in case the same data is requested again (this request may be made from another processor element). Furthermore, when writing to the data memories DM1 to DM32, the same data is also stored in the data cache memory DC in preparation for reading it again later. Although general techniques for caches on general-purpose computers can be applied to the algorithm for eviction from the cache, since this computer system is a dedicated machine, it may be possible to control it by the programs of the processor elements PE1 to PE8. Dew. In other words, you can have the program specify the data that you want to store in the cache and the data that does not need to be stored, or you can use addressable memory instead of the cache (in this case, data is not stored in the cache from processor elements PE1 to PE8). memory DM
1 to DM32, and what is stored there is all specified by the processor element program). The control processor interface CPI' is a circuit for communicating with the control processor CP and connects each processor element PE1 to PE8 and the control processor.
Communication between CPs and their processors PP1' to PP1
6' Controls communication between itself and the control processor CP (in this method, what is visible from the software is each processor element PE1 to PE8;
PP1' to PP16' have meaning only as a physical unit (device unit), so they cannot be used as control processors.
Logically, communication with the CP is mainly between the processor element and the control processor CP). An example of this communication is each processor element.
There is a program execution start instruction START, which instructs PE1 to PE8 to start program execution, and a program execution stop instruction STOP. Processor elements PE1 to PE8 are instructed to start program execution
Upon receiving START, the program starts executing, and stops when a predetermined condition is met or when a program execution stop instruction STOP is received. Also,
The control processor interface CPI connects processor elements PE1 to PE8 to the control processor.
It also controls the transmission of information to the CP via interface a. For example, after receiving the program execution start instruction START and starting execution, if certain conditions are met, such as when specific processor elements PE1 to PE8 have finished execution, the processor that controls it
It is also the control processor interface CPI' that informs the CP. The configuration of each processor element PE1-PE8 is basically the same as that of a general computer, but the difference is that instruction words are read from the corresponding program memories PM1-PM8. In a general computer, instructions and data are stored in the same memory, but in the parallel processing system using this invention, the data memory
Access to DM1 to DM32 To reduce the load on the path, the instruction words are from program memory PM1 to PM.
It is stored in 8. This means that data must be transferred between each processor element PE1 to PE8, and each processor element PP1' to
Since it is necessary to transfer data between PP16's, it is necessary to store it in a common data memory,
This is not necessary for the program, and the program utilizes the property that each processor element PE1 to PE8 can be stored in a dedicated memory. Each processor element PE1 to PE8 reads and processes data from the data cache memory DC or data memory DM1 to DM32 according to the program stored in the program memory PM1 to PM8, and stores the results in the data memory DM1 to DM3.
2 and returning to the data cache memory DC are repeated. The operation when executing a program in the parallel processing system shown in FIG. 3 is as follows. As an example, each of 128 pieces of data A _i and B _i (i=1
~128)

Let us consider the case of calculating [Formula]. Before starting the calculation, the data A _i and B _i are controlled by the processor.
The CP stores the data in the data memories DM1 to DM32. For example, data A ₁ to A ₈ are stored in data memory DM1, data A ₉ to A ₁₆ are stored in data memory DM2, and data A ₁₂₀ to A ₁₂₈ are stored in data memory DM2 in the same manner.
Store in DM16. Similarly, data B ₁ to B ₈ are stored in the data memory DM17, data B ₉ to B ₁₆ are stored in the data memory DM18, and data B ₁₂₀ to B ₁₂₈ are stored in the data memory DM32. In this example, there are 16 (number of processors) x 8 (number of processor elements in each processor) = 128 processor elements in the system, and the i-th processor element PE _i is A _i x B _i The calculation result C _i is stored in the data memory. The program for performing this calculation is stored in the program memories PM1 to PM8 attached to each processor element PE1 to PE8, and the instruction address register in each processor element PE1 to PE8 contains the processor The address of the program memory PM1-PM8 of the first instruction word to be executed by the elements PE1-PE8 is set. It connects data memories DM1 to DM32 to memory switch MS and memory switch interface under the control of control processor CP.
MSI' or through interface a and control processor interface CPI'. The control processor CP performs the above preparations, and when completed, sends a program execution start instruction START addressed to all 128 processor elements to the processors PP1' to PP16' through the interface a. As a result, all processor elements PE1 to PE8 are assigned to program memories PM1 to PM8 according to the value of each instruction address register.
Reads the instruction word from, decodes and executes it. Now, taking processor element PE1 in processor PP1' as an example, A ₁ ×B ₁ is calculated for data A ₁ read from data memory DM1 and data B1 read from data memory DM17, and the calculation result C is obtained. Store ₁ in data memory. Similarly, processor element PE2 calculates A ₂ ×B ₂ and stores the calculation result C ₂ , and similarly, processor element PE8 processes A ₈ ×B ₈ →C ₈ . These processes are simultaneously executed in parallel by each of the processor elements PE1 to PE8. In this example, it is assumed that all processor elements execute the same program, but it may be a different program, and even if the program is the same, if a conditional branch is included, it is assumed that each processor element executes the same program. There is a possibility that a different instruction sequence will be executed from the middle. In addition, access requests from each processor element PE1 to PE8 to each data memory DM1 to DM32 (requests for reading A _i and B _i or storing C _i ) are handled by the memory switch interface.
Traffic is controlled by MSI', and if there is a conflict, only one is selected and the others are made to wait, so the timing of instruction execution of each processor element PE1 to PE8 may be different, and all processor elements PE1 to PE8 PE8 does not synchronize perfectly and perform the same operations and processes at the same time. When the processing A _i ×B _i →C _i is completed, the control processor CP is notified of this through the control processor interface CPI' and the interface a. The control processor CP waits for completion notifications from all 128 processor elements PE1 to PE8.

Process [expression]. Since the calculation line product C _i is stored in the data memories DM1 to DM32, the control processor CP switches the memory switch.
The data memories DM1 to DM32 are accessed via the MS and the calculation results C _i are added in the order of reading. This operation is the same as addition in a general computer, and the calculation results C ₁ , C ₂ , . . . , C ₁₂₈ are read out one by one and added by a program in the control processor CP. When this addition is completed, the desired answer is obtained. The notification from each processor element PE1 to PE8 to the control processor CP may be notified to the control processor CP every time each processor element PE1 to PE8 finishes, as described above, but
It may also be possible to reduce the amount of communication with the control processor CP by notifying all of them within PP16'. Also, as above

〔Effect of the invention〕

The parallel processing method of the present invention is such that each of the processors connected in parallel to the control processor and connected to each other in parallel via a plurality of data memories and memory switches is configured in parallel, instead of consisting of a single processor element. By providing multiple operating processor elements in parallel, when viewed from the memory switch side, it appears to have only a single processor element, but multiple processor elements can be connected to the memory switch in a time-sharing manner. Since it can be connected, it has the effect of increasing the degree of parallelism. In other words, the parallel processing method of the present invention facilitates the realization of parallel operations with a large degree of parallelism by arranging processors containing a plurality of processor elements in parallel and configuring them to operate in parallel under the control of a control processor. , and the parts that cannot be computed in parallel can be processed by a control processor, which has the effect of increasing flexibility and expanding the field of application.

[Brief explanation of the drawing]

FIG. 1 is a system configuration diagram showing a conventional example, FIG. 2 is a detailed block diagram of the processor shown in FIG. 1, FIG. 3 is a system configuration diagram showing an embodiment of the present invention, and FIG. FIG. 2 is a detailed block diagram of the processor shown in the figure. CP...Control processor, PP1 to PP16, PP
1' to PP16'...Processor, CPM1, CPM2
...control-only memory, MS...memory switch,
MM1 to MM32...Memory, MSI, MSI'...Memory switch interface, CPI, CPI'...
Control processor interface, PE, PE1~
PE8...Processor element, DM1 to DM3
2...Data memory, DC...Data cache memory, PM1 to PM8...Program memory,
a...interface.

Claims (1)

[Claims] 1. A control processor, a plurality of data memories each storing data, a plurality of processors connected in parallel to the control processor, and the plurality of processors and the plurality of data memories are interconnected in parallel. each of the plurality of processors includes a plurality of processor elements provided in parallel;
a plurality of program memories for storing programs provided corresponding to each processor element; a control processor interface for connecting the plurality of processor elements to the control processor; and a control processor interface for connecting the plurality of processor elements to the control processor. a memory switch interface for connecting to a memory switch; and a data cache memory connected to the memory switch interface and storing a copy of a portion of the data stored in the data memory. Processing method.