JPH07122866B2 - Parallel Data Processing System - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to the field of parallel data processing for performing high speed data processing.

BACKGROUND ART FIGS. 4 and 5 are shown in, for example, the literature "Highly Parallel Computing"
uting" (GS Almasi, A. Gottlieb, The Benjamin/Cummi
ngs Publishing Company, Inc., 1989) pp111−112, pp301
FIG. 4 shows the basic configuration of an example of a conventional parallel data processing device shown in Japanese Patent Application Publication No. 2004-476. FIG. 4 shows a SIMD (Single Instruction Multiplexed) processor in which there is one control flow and multiple data flows to be processed.
Figure 5 shows a parallel data processor of MIMD (Multiple Instruction Streams, Multiple Data Streams) type, which has multiple control flows and multiple data flows.
This refers to a parallel data processing device of the Parallel Data Streams type.

In FIG. 4, 1, 2, 3, and 4 are arithmetic units, 5, 6, 7, and 8 are local memories, 9 is a memory bus, 10 is a shared memory, 11 is a
The fifth is the overall control unit that controls the entire device.
In the figure, 21, 22, 23, and 24 are arithmetic units, 25, 26, 27, and 28 are local memories, 35, 36, 37, and 38 are control units, 29
indicates a memory bus, 30 indicates a shared memory, and 31 indicates an overall control unit.

Next, the operation will be described.

In the SIMD type parallel data processing device shown in Fig. 4, the same instruction is simultaneously issued from the overall control unit 11, which executes the program, to all the arithmetic units 1 to 4, which process the data in each of the local memories 5 to 8. Also, during the processing, if necessary,
A shared memory 10 is accessed via a memory bus 9 .

5, on the other hand, the control units 35-38 of each processor execute programs and issue instructions to the arithmetic units 21-24, which then process the data in the local memories 25-28. If necessary during processing, the shared memory 30 is accessed via the memory bus 29. The overall control unit 31 controls the synchronization and monitoring of the entire device.

These conventional SIMD and MIMD parallel data processors each have their own advantages and disadvantages.
In the case of a parallel data processing device, the control flow is single, so the control is simple, it is easy to perform large-scale parallel processing, and it is easy to achieve extremely high speeds.
On the other hand, it has little flexibility in processing and is not suitable for complex processing.

On the other hand, in the case of MIMD parallel data processing devices, each processor operates independently, allowing each to perform advanced processing. However, this makes control more complex and makes them unsuitable for large-scale parallel processing.

As such, the parallel processing capabilities of SIMD and MIMD types are quite different, and each has its own application areas where it is suited to them, making it very difficult to cover a wide range of application areas with just one type.

In the following, a specific explanation will be given using the fields of numerical calculation and image processing, which are particularly important fields for applying parallel data processing.

First, in the field of numerical calculation, the processing model is
They can be broadly classified into (1) particle system models, such as Monte Carlo simulation, (2) continuous system models, which solve partial differential equations targeting physical phenomena, and (3) discrete system models, which solve simultaneous equations targeting network analysis, etc. Of these, continuous system models involve the repetition of a large number of regular and localized operations,
Large-scale parallel processing of the SIMD type is suitable. On the other hand, for discrete system models, large-scale parallelism is not necessary, but complex processing is required, so medium-scale parallel processing of the MIMD type is suitable. Furthermore, for particle system models, large-scale and complex processing is often required, and depending on the conditions and number of data, SI
It is necessary to distinguish between MD and MIMD.

Next, image processing can be broadly classified into (1) pixel-level processing such as density value conversion and binarization, (2) processing between neighboring pixels such as spatial filters, (3) global processing such as geometric transformation and fast Fourier transform, and (4) permeation or tracking-type processing such as labeling and boundary detection. Of these, SIMD is suitable for pixel-level processing and processing between neighboring pixels, as these are simple, large-scale processes, while MIMD is suitable for global processing, which requires complex, wide-ranging processing. For permeation/tracking-type processing, it is necessary to choose between SIMD and MIMD depending on the conditions and the amount of data.

As can be seen from the examples of numerical calculation and image processing, there are various types of processing even in a particular field, and it is difficult to provide optimal parallel processing using only one parallel processing architecture.

This invention was made to solve the problems mentioned above, and aims to make it possible to apply a parallel processing architecture that is close to optimal in any field of a wide range of applications by taking advantage of the advantages of both SIMD and MIMD types while covering their respective disadvantages.

Disclosure of the Invention: The parallel data processing system of the present invention connects a first parallel data processing device with a single control flow and multiple processed data flows, i.e., a SIMD-type parallel data processing device, and a second parallel data processing device with multiple control and data flows, i.e., a MIMD-type parallel data processing device, via a shared bus and memory. It also includes a system control unit that controls each parallel data processing device to perform processing appropriate to that device, thereby enabling the application of a wide range of optimal parallel processing methods. Simple processing requiring large amounts of data is processed by the SIMD-type parallel data processing device, while complex processing requiring small amounts of data is processed by the MIMD-type parallel data processing device. It is also possible to divide a program into modules and allocate them to each module, allowing each appropriate processing to be performed in parallel or in a pipelined manner. Data is passed between these modules via shared memory. In other words, rather than expanding one type of parallel data processing device, combining both types in this way allows
It is more effective in terms of functionality and cost if they complement each other.

Furthermore, in order to solve the problems in the fields of numerical calculation and image processing as described above, the present invention realizes a hybrid parallel data processing system that can perform efficient parallel processing in a wide range of fields by tightly coupling two different types of parallel data processing devices, SIMD and MIMD, via shared memory and a high-speed multiplexed bus and using them complementarily.

As a parallel architecture that incorporates this hybrid concept, MS is a parallel architecture that extends the functionality of conventional SIMD to MIMD.
University of Texas adopts IMD (Multiple SIMD)
TRAC (Texas Reconfigurable Array Computer) and Pur
duc University's PASM (Partitionable SIMD/MIMD syst
However, compared to these approaches, the present invention has the following features: (1)
(2) It has two parallel data processing devices, SIMD and MIMD, which are individually and tightly coupled on an equal footing; (3) each parallel data processing device utilizes the advantages of SIMD and MIMD while enhancing its functionality to compensate for its conventional shortcomings; (4) it has a high-speed multiplexed bus and large-capacity, high-speed shared memory to efficiently transfer data between the two parallel data processing devices; and (5) it is capable of hybrid pipeline processing and parallel processing that could not be achieved with conventional parallel processing.

Such a hybrid parallel data processing system is
By applying this technology to large-scale, complex processing such as image processing, it is possible to perform processing at high speed within a practical time frame, which was difficult to achieve within an effective time frame with conventional systems.

Brief Description of the Drawings: Figure 1 is a system configuration diagram showing a parallel data processing system according to one embodiment of the present invention, Figure 2 is a specific configuration diagram showing an example of a system to which the present invention is applied, Figure 3 is a diagram showing the flow of parallel processing that can be realized by implementing the present invention, Figure 4 is a basic configuration diagram showing an example of a conventional SIMD type parallel data processing device, and Figure 5 is a basic configuration diagram showing an example of a conventional MIMD type parallel data processing device.

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will now be described with reference to the accompanying drawings.

FIG. 1 is a system configuration diagram of an embodiment.
50 is a SIMD type parallel data processing device similar to that shown in FIG.
Reference numeral 51 denotes an MIMD-type parallel data processing device similar to that shown in Figure 5. Reference numeral 41 denotes a memory bus shared by both of them, 42 denotes a shared memory that is also used in common and transfers data between them, and 43 denotes a system control unit that allocates each process in the application program to the parallel data processing device that is most suitable for it.

Next, the operation will be described.

In the system shown in Fig. 1, the execution control of the application program is performed by the system control unit 43.
SIMD-type parallel data processors are suitable for MD-type processing, i.e., processing that is simple but requires large amounts of data processing.
50, and for MIMD-type processing, that is, complex processing with a small amount of data processing, the MIMD-type parallel data processor 51
In this case, the user can either explicitly specify both or implicitly use them.
An implicit example is a library, where if a user uses a library of functions, the most suitable parallel data processing device is indicated at the time the library is called.

SIMD type parallel data processor 50 and MI in one program
It is also possible to perform large-level parallel processing or pipeline processing by using both MD-type parallel data processors 51. In this case, the processing is performed under the control of the system control unit 43, but data is transferred by the shared memory 42 via the memory bus 41. For this reason, the memory bus 41 must be fast.

In the above embodiment, each parallel data processing device is
Although an example of a system consisting of two processors is shown, SIMD systems usually have a large number of processors, while MIMD systems have a relatively small number of processors. The ratio of the number of processors is determined by the performance of each processor and the characteristics of the application program.

In addition, when performing parallel operation or pipeline processing at a large level using both of the above-mentioned parallel data processing devices, the bus 41
It may also be effective to temporarily separate the buses or to have two or more buses.

As described above, according to the present invention, SIMD and MIMD parallel data processing devices are combined to perform processing suited to each parallel data processing device, which is more advantageous in terms of both performance and cost than expanding and using only one of the SIMD and MIMD types and applying it to a wide range of application fields, and has the effect of enabling parallel processing that is more suited to a wide range of fields.

Next, a specific application example of the present invention is shown in Fig. 2. The basic configuration is the same as Fig. 1, but the contents of each block are shown in more detail.

In FIG. 2, blocks 41, 42, 43, 50, and 51 respectively represent a shared memory bus, a shared memory, a system control unit, a SIMD type parallel data processor, and a MIMD type parallel data processor, as in FIG.

The shared memory bus 41 is composed of two buses 96 and 97 and their respective bus connections 94 and 95. The reason for using such a multiple bus is that the shared memory 41 from the two parallel data processors 50 and 51 is
2 and the system control unit 43
In normal mode, all signals connected to the bus can use either bus that is free, and
Either parallel data processing device can simultaneously occupy both buses for input and output respectively.
These two buses 96, 97 are connected by bus connection parts 94, 95. These bus connection parts 94, 95 have the function of connecting or separating the buses 96, 97 to the SIMD type parallel data processor 50 side and the MIMD type parallel data processor 51 side. This switching mechanism is realized by a selector, and when connected, the buses are connected as they are, and when disconnected, they are connected to bus termination resistors on both sides of the bus connection parts 94, 95, and the two parallel data processors 5
0 and 51 can be used as independent buses. The bus connection units 94 and 95 are controlled to be connected and disconnected by signals from the system control unit 43.

The shared memory 42 is generally divided into multiple segments, but Fig. 2 shows an example of four segments. Each of the segments 98, 99, 100, and 101 has a capacity of 16 megabytes and is individually connected to the shared memory bus 41.
When using the segment number and address within the segment, the segment number and address within the segment are specified. Ordinary user programs use logical segment numbers, and the correspondence with physical segment numbers is determined by the system control unit 43. Furthermore, each segment has its own address calculation function, and by avoiding the use of unnecessary address information on the bus, the two parallel data processors 50, 51 can perform high-speed data transfer with the shared memory 42, further improving the effects of the present invention (Japanese Patent Application No. 61-288740).

The system control unit 43 is composed of a data processing unit 90, a memory unit 91, a bus connection unit 92, a disk device 93, and an internal bus 106. Normally, a user program is processed by the data processing unit 90, and the program is stored in the memory unit 91. The data to be processed is stored in the disk device 93, and is transferred to the shared memory 42 via the shared memory bus connection unit 92.
The data is processed by one or both of the parallel data processors 50 and 51. The processed data is stored in a disk device 93 via a bus connection unit 92.

The SIMD type parallel data processor 50 is composed of an overall control unit 11, an output control unit 102, an input control unit 103, and 4096 arithmetic elements 108. Each arithmetic element 108 is composed of an 8-bit arithmetic unit 1 and a 16K-bit local memory 5, which are connected in a lattice pattern between four neighboring arithmetic elements. Each arithmetic unit is composed of an 8-bit adder/subtractor, multiple control flags, a 128-bit register file, etc. (US Patent No. 4,855,525).
8, 110). The entire SIMD parallel data processor 50 is controlled by the overall control unit 11, which sends the same instruction to all the processing elements 108 simultaneously. The data to be processed is sent from the shared memory 42 to each processing element 108 via the input control unit 103 in response to a command from the overall control unit 11.
The processed data is returned to the shared memory 42 via the output control unit 102. It is also possible to overlap data input/output and calculation, which allows for faster pipeline processing in block units of data, making the present invention even more effective (see Japanese Patent Application No. 59-29
(See Japanese Patent Publication No. 485 and Japanese Patent Publication No. 1-26108.) These functions enable SIMD-type parallel processing, enabling simultaneous parallel processing of large amounts of data.

The MIMD parallel data processor 51 is composed of an overall control unit 31, input/output control units 104 and 105, eight processing elements 109, and a bus 107 connecting these. Each processing element 109 has a 32-bit arithmetic unit 21, a 1 MB local memory 25, and a control unit 35, and each can individually execute different instruction sequences. MIMD
The overall control of the parallel data processing device 51 is performed by the overall control unit 31, which sends a sequence of instructions to each of the processing elements 109 for control. The data to be processed is sent from the shared memory 42 to each processing element 109 via one of the input/output control units 104 and 105 in response to a command from the overall control unit 31. The processed data is then sent to the input/output control units 104 and 105.
The data is returned to the shared memory 42 via one of the methods described above.

Next, four parallel processes that can be realized by implementing the present invention will be explained using Fig. 3. Fig. 3 describes the flow of each parallel process along time based on the system configuration example shown in Fig. 2, and basically there are two parallel process flows by two parallel data processing devices 50 and 51.
The SIMD parallel data processor 50 has 4096 operation elements 108.
It shows the flow of many fine SIMD-type parallel processes that are created by
66, 68, and 72 indicate the part where the SIMD parallel data processor 50 performs the calculation. 61 indicates the flow of highly functional and flexible MIMD parallel processing created by the eight calculation elements 109 of the MIMD parallel data processor 51, and 65, 70, and 73 indicate the part where the MIMD parallel data processor 51 performs the calculation. 62 indicates the data in the shared memory, and 63, 64, 67, 69,
71, 74, and 75 indicate the data to be accessed.
111 and 112 are SIMD type parallel data processors 50 and MIMD
1 shows the flow of hybrid processing by the parallel data processor 51.

The individual parallel processes 60 and 61 have existed for some time, and one of these parallel processes has been used up until now, but by implementing the present invention, it is possible to create a new parallel process flow that is unique to hybrid parallel processing that combines these processes.
That is, in this embodiment, the following three types of parallel processing can be used, which could not be realized in the conventional method.

(1) One or more programs executed by the system control unit 43 use the SIMD type parallel data processor 50 and the MIMD type parallel data processor 51 independently and simultaneously;
Processing can be performed on different data 64, 63 in the shared memory. Such hybrid parallel processing is
This function allows different types of parallel processing to be used simultaneously in the same procedure on a single system. In conventional methods, different systems and procedures had to be used to utilize different types of parallel processing techniques.

(2) Hybrid parallel processing is shown in 111, in which two parallel data processors 50, 51 process a series of consecutive data sets (for example, images) in a pipelined manner. Using data 67 in a shared memory, the SIMD type parallel data processor 50 first performs processing 68, and then stores the results in the shared memory (data 6
9) to the MIMD type parallel data processor 51, where a different parallel processing 70 is continuously performed. To perform this processing, the system control unit 43 controls simultaneous control and data set. Data is exchanged between the two parallel data processors 50 and 51 via the shared memory 42, and in order to minimize this overhead, the shared memory buses 96 and 97 are used.
The segments 98, 99, 100, and 101 of the shared memory 42 are used independently by the parallel data processing devices 50 and 51. As a result, the target processing can be divided into small functional levels, and a parallel data processing device suited to each function can be used, enabling efficient pipeline processing on a data set basis.

(3) Hybrid parallel processing in which two parallel data processors 50, 51 operate independently in parallel is shown in 112. In this case, data 71 in a shared memory is used, and the SIMD type parallel data processor 50 performs processing 72, while at the same time the MIMD type parallel data processor 51 uses the same data 71 to perform a different parallel processing.
73 is performed. In this case, different programs may run independently on the parallel data processing devices 50 and 51, or different parallel algorithms may be used within the same program to perform parallel processing on the same data set. This type of parallel processing allows parallel processing methods with different algorithms, convergence, accuracy, and parallelism to be applied simultaneously to the same data, making it possible to compare the results of both methods to improve reliability or to use the method that produces the fastest results to improve performance. This type of processing cannot be achieved with conventional methods and is unique to the hybrid method.

As described above, by implementing the present invention, it is possible to realize new parallel processing specific to hybrid parallel processing, and to broaden the scope of application of parallel processing both spatially and temporally beyond that of conventional methods.

Next, an example of the software configuration for implementing the present invention is shown. The present invention includes a parallel processing library for user use and system control software for controlling hybrid processing using two parallel data processing devices 50 and 51 and shared memory 42.

First, the parallel processing library is provided to allow users to easily use the two parallel data processors 50 and 51, and is usually prepared and registered for the more suitable parallel data processor.
Some libraries are prepared separately with different algorithms for each parallel data processing device. A user normally uses these libraries to use two parallel data processing devices 50, 51 by calling a subroutine from a user program running on the system control unit 43. The system control unit 43 determines which parallel data processing device to use when the library is specified and starts the appropriate parallel data processing device, but this can also be specified in advance. Alternatively, the user can directly write the execution library for one of the parallel data processing devices.
In addition, although there are considerable restrictions, user programs can be
A compiler that automatically selects the most suitable parallel data processor and replaces it with a parallel library is also effective.

On the other hand, the system control software for realizing the hybrid parallel processing of the present invention is as follows:
(i) parallel and pipeline control of the two parallel data processing devices 50 and 51; (ii) overlap control of data transfer between each of the parallel data processing devices 50 and 51 and the shared memory 42;
i) A function that allows the user to access the parallel data processing device that is more suitable for processing without being aware of it, and (iv) A function that monitors the spatial and temporal parallel processing operation of the entire system.

To achieve these functions, the system control software performs various management functions, including simultaneous execution and exclusive control of each component, such as (i) resource management of the two parallel data processors 50 and 51, (ii) data management of multiple segments of the shared memory 42, (iii) management of the parallel processing library, (iv) execution control of the parallel processing library, and (v) data input/output management of the shared memory 42.

Next, an example of application of the present invention to image processing will be described. As mentioned above, there are various types of image processing, and there are several ways to classify the processing forms. From the perspective of parallel processing, however, they can be roughly classified into: (1) neighborhood processing: processing in which a relatively simple operation is uniformly performed between pixels or between neighboring pixels;
(2) Global processing: Processing that performs relatively complex calculations on the entire image.

In order to execute these two types of processing with different characteristics efficiently and quickly in parallel, the present invention enables efficient parallel processing over a wide range by mainly allocating neighborhood processing to the SIMD parallel data processor 50 and global processing to the MIMD parallel data processor 51. In this way, by using both parallel data processors appropriately, it is possible to perform parallel processing that is more suitable for a wide range in terms of both space and time.
Furthermore, by further dividing each process and applying hybrid parallel processing, it becomes possible to perform maximum parallel processing in an even wider range of fields. The following describes in detail the performance effects of the present invention.

The effects of the present invention will be described below at the calculation level, function level, and application program level, taking image processing as an example.

First, in the evaluation of the operation level, the SIMD type parallel data processor 50 generally has a configuration suitable for integer operations and processing of short bit length data, and for these operations, it can demonstrate ultra-high speed performance through large-scale parallel processing. On the other hand, the MIMD type parallel data processor 51 has difficulty in realizing large-scale parallel processing due to the limitations of the operation units, but is suitable for floating-point operations and complex processing.

In image processing, depending on the processing, it is necessary to convert from a few-bit integer data to
It handles a wide range of data up to 32-bit real data, and by selecting the arithmetic unit configuration according to the processing content and data,
The SIMD type parallel data processor 50 can generally achieve higher performance for integer data processing with short bit lengths, while the MIMD type parallel data processor 51 can achieve higher performance for real number data processing with long bit lengths.
Therefore, by optimally allocating these two, it is possible to obtain the maximum performance through parallel processing corresponding to the processing.

Next, as an example of performance at the function level, the relative performance ratios of the SIMD type data processor 50 and the MIMD type parallel data processor 51 for five typical image processing tasks are shown. In the case of the system with the configuration shown in Figure 2, the ratios are 1:5 for affine transformation,
The ratios are 1:4 for histogram creation, 2:1 for density value conversion, 3:1 for fast Fourier transform, and 6:1 for uniform weighting filters, with the higher performance being approximately two to six times higher than the lower performance.
The SIMD type parallel data processor 50 used in this performance evaluation
The MIMD type parallel data processing device 51 has approximately the same amount of hardware, which shows that it is more efficient to adopt a hybrid parallel processing architecture as in the present invention than to use only a single parallel processing architecture.

Finally, as an application program level performance evaluation, the present invention was evaluated for a series of practical image processing tasks for data from optical sensors mounted on artificial satellites. As a result, it was found that the performance was 2.6 to 2.8 times higher than when using only a single parallel data processing device, demonstrating the effectiveness of the present invention.

By adopting the hybrid parallel processing architecture of the present invention, the applicable range of parallel processing can be significantly expanded in terms of time and space compared to a single architecture, and it has become possible to dynamically apply parallel processing suitable for each type of image processing. As a result, processing that was difficult to complete within an effective time frame on conventional computers, such as processing of large-scale, complex image data, can be performed at high speed within a practical time frame.

Claims (6)

[Claims] [Claim 1] A parallel data processing system comprising: a SIMD-type parallel data processing device with one control flow and multiple data flows to be processed; a MIMD-type parallel data processing device with multiple control flows and multiple data flows; a shared bus and memory connected to each of these parallel data processing devices; and a system control unit that tightly couples each of the parallel data processing devices via the shared bus and memory and causes each parallel data processing device to perform processing appropriate to that device. [Claim 2] A parallel data processing system as described in claim 1, characterized in that the shared bus comprises a high-speed multiple bus that can be used independently by each parallel data processing device, the shared memory comprises a large-capacity high-speed memory divided into a plurality of segments each individually connected to the high-speed multiple bus, the system control unit comprises a data processing unit in which user programs are processed, a memory unit in which programs are stored, a disk unit in which data to be processed is stored, a bus connection unit for connecting to the high-speed multiple bus, and an internal bus connecting these, and each of the parallel data processing devices comprises an input/output control unit for inputting and outputting data to and from the high-speed multiple bus. [Claim 3] A parallel data processing system as described in claim 1 or 2, characterized in that each of the parallel data processing devices is used independently and simultaneously to perform hybrid parallel processing on different data in the shared memory. 4. A parallel data processing system according to claim 1 or 2, wherein hybrid parallel processing is performed in which each of said parallel data processing devices processes a series of consecutive data sets in a pipeline manner. [Claim 5] A parallel data processing system as described in claim 1 or 2, characterized in that each of the parallel data processing devices operates individually and independently in parallel, performing hybrid parallel processing in which different parallel processing is performed on the same data in the shared memory. 6. In image processing, neighborhood processing, which uniformly performs relatively simple operations between images or between neighboring images, is performed by the SIMD
and a parallel data processor of MIMD type is mainly responsible for global processing for performing relatively complex operations on the entire image.
3. A parallel data processing system according to claim 2.