CN101833438A - A general data processing method based on multiple parallelism - Google Patents

Abstract

The invention discloses a general data processing method based on multiple parallel, comprising the steps of: (1) dividing an application program for data processing into a plurality of execution behaviors; (2) dividing all of the execution behaviors into a plurality of tasks according to the basic operation types of data by the execution behavior; (3) dividing the data to be processed by the application program into static data and dynamic data; and (4) operating computational tasks on a GPU (Graphic Processing Unit), and operating logical judgment tasks on a CPU (Central Processing Unit) until the execution of the application program is finished. The data processing method performs specialized optimization for complex algorithm with dynamically-characterized performance behavior and irregular data structures, and can carry out dynamic management on the data according to a memory locality principle and an SIMD (Single Instruction Multiple Data) operation mechanism during data processing so as to effectively utilize the computing resources and the memory resources of hardware furthest during the data processing by the application program.

Description

A general data processing method based on multiple parallelism

technical field

The invention relates to the technical field of parallel computing, in particular to a general data parallel processing method based on a heterogeneous multi-core architecture.

Background technique

With the rapid development of today's science and technology, high-performance computing has become a strategically important research method in the development of science and technology. Together with traditional theoretical research and laboratory experiments, it constitutes a complementary and mutual Correlative research methods are known internationally as the three "pillars" of scientific research in the 21st century. The application fields of high-performance computers are mainly concentrated in scientific research and development, telecommunications, finance, government, etc., so the contribution of high-performance computers to the country is of course indispensable. In order to speed up the pace of today's information construction, more and more fields of application to high-performance computing technology. High-performance computing greatly accelerates the calculation speed and shortens the development and production cycle. Its application has greatly broadened research capabilities, promoted and promoted the development of modern science and engineering technology. Accelerating the development of high-performance computing is of great strategic significance for improving my country's independent innovation capabilities in science and technology, enhancing national competitiveness, safeguarding national security, promoting national economic construction, and building an innovative country.

In the development process of the high-performance computing field, the minicomputer dominated by the RISC architecture once dominated the high-performance computing market. Later, due to the development of the X86 architecture, the X86 architecture, which has an absolute advantage in price, finally replaced the minicomputer in the form of a cluster. . Although some large-scale computing problems can be solved by creating a distributed system, the distributed system has weaknesses such as high communication overhead and high failure rate; complex data access structure and high overhead; data security and confidentiality are difficult to control and other weaknesses. With the rapid improvement and low price of computer processors, especially GPU (Graphical Processing Unit) computing power, high-performance computing has gradually entered the desktop (low-end) field, making it possible for every researcher, scientist and engineer to have Our own supercomputer can solve problems faster and speed up the pace of scientific development. The current GPU contains hundreds of processing units, which can achieve 1TFLOPS performance for single-precision floating-point operations, and more than 80GFLOPS performance for double-precision floating-point operations. It can have 4GB of video memory and a bandwidth of more than 100GB/s. Although the GPU is originally a processor designed for graphics computing, it is especially suitable for large-scale parallel computing due to its powerful computing performance, low energy consumption, low price, and small footprint. Appears in the field of high performance computing for many non-graphics applications. Today, many important scientific projects are trying to add GPU computing power to their code. Software engineers are eagerly awaiting the superior performance of GPUs for their work.

However, most of the current applications directly ported to the GPU will not immediately improve the performance, and even the performance will drop. This is mainly because these programs and structures are not designed for the characteristics of the GPU architecture, and cannot tap the full computing power of the GPU. How to use parallel applications for efficient data processing is usually a complex and time-consuming task.

Contents of the invention

The present invention provides a multi-parallel data processing method that integrates data parallelism, task parallelism, and pipeline parallelism, which can enable application programs to effectively use hardware computing resources and storage resources to the greatest extent when performing data processing.

A method for general data processing based on multiple parallelism, executed in a computer with GPU and CPU processors:

(1) Divide the application program for data processing into several execution behaviors;

Each execution behavior can complete at least one basic operation on data, such as data access, data storage, etc., or calculation instructions;

(2) Divide all execution behaviors into several tasks according to the basic operation types of execution behaviors on data and the types of calculation instructions, that is, to divide similar execution behaviors into the same calculation task;

Similar execution behavior refers to having the same calculation operation or similar storage operation, and similar storage operation means that the access to data is kept in the local scope of the storage area.

The division of this step can satisfy the SIMD (Single Instruction, Multiple Data) execution characteristics of the hardware and the local access characteristics of the storage.

Each task completes the specified computing task, and the division time is as short as possible and has a single function. The tasks can be executed in parallel or serially according to the specific situation.

(3) The data that the application program needs to be processed is divided into static data and dynamic data, and the storage space (storage pool) is divided in the computer video memory that can execute the application program, and the storage space is respectively static data and dynamic data. Divide the storage area, that is, a part of the storage space is used to store static data, and the rest is used to store dynamic data.

The static data refers to data that does not change during the execution of the application program, and the dynamic data refers to new data generated during the execution of the application program. All this information is pre-recorded in a configuration file;

(4) According to the processing mode to data, the task in step (2) is divided into calculation type task and logic judgment type task, runs calculation type task on GPU, runs logic judgment type task on CPU, the present invention adopts based on pipeline Multiple parallel execution methods of parallel, data parallel, and task parallel complete the execution of the application program.

The pipeline is a producer-consumer execution mode, which is suitable for the calculation process of most applications, and the pipeline can effectively balance the workload through data reorganization, so as to avoid the excessive output of a certain unit and the load of the entire calculation process. Both; the data parallel execution model is just like the current mainstream programming model, such as CUDA (Compute Unified Device Architecture), which can make full use of the hardware SIMD characteristics for large-scale neat and homogeneous data sets, and hide the memory access delay; the task execution model is a It is an extensible execution mode, which can clearly express the interdependence of each unit and the dynamic execution behavior in the process of program execution. In order to give full play to the characteristics of the heterogeneous multi-core architecture and rationally use hardware resources, the present invention adopts the pipeline parallel data processing mode to run the application program execution pipeline involving a large number of calculations on the GPU, and the data task scheduling pipeline involving a large number of logical judgments to run On the CPU, the two pipelines are executed asynchronously and in parallel, and the data task scheduling pipeline runs ahead of the application execution pipeline. Through this pipeline parallel execution mode, the independence and parallelism of calculations can be guaranteed, and expensive synchronization operations such as atomics and locks can be avoided.

In the application execution pipeline, the execution behavior within the same computing task is executed in a data parallel manner, while the execution behavior between different computing tasks is executed asynchronously in a task parallel manner.

A condition in which the entire execution pipeline is unbalanced due to the unpredictable amount of data that some programs may generate. The execution mode of data parallelism is likely to cause a task to generate a large amount of new data, it is difficult to store and use these data at the same time, and a large amount of new data may quickly consume limited video memory, and because the generation of these data is random Unpredictability also increases the difficulty of data management. Therefore, before performing step (4), it is judged whether the size of the new data that will be generated by the task to be executed exceeds the remaining space of the current storage pool; Data is grouped so that data is processed in batches. This method will greatly reduce the burden on system storage and bandwidth caused by some algorithms involving massive data, so that the data in the video memory is the data required by the thread being calculated, thereby further enhancing the parallel computing efficiency of the thread and improving effective use of hardware.

Since unpredictable new tasks may appear when tasks are running, the present invention adopts priority-based dynamic scheduling, and manages corresponding data transfer according to the scheduled tasks at the same time.

Set a priority status for each task (including the task in step (2) and the new task that appears when the task is running), and when a new task appears, select the task with higher priority in order according to the priority status of all tasks run.

Prioritization of tasks is based primarily on the location of the data it requires in the storage hierarchy, the type of processor it requires, and the size of the data set it requires. Task scheduling is performed in a data-driven manner, and scheduling is performed according to the type of the idle processor and the tasks corresponding to the static data in the current storage pool. Specifically, combine the following principles in descending order of priority:

(1) The execution of the task does not require static data;

(2) The required data is in the cache;

(3) Prioritize the tasks with sufficient similarity data, or the generated data can be coordinated

It can help other tasks to increase the priority of execution, or the execution of multiple tasks is similar.

(4) The required data is in the GPU memory;

(5) The required data is in the CPU memory;

(6) The required data is being transferred from the hard disk to the memory;

(7) The required data set is too small to fully utilize the hardware computing power.

The implementation of the method of the present invention is based on a more mature heterogeneous multi-core architecture, such as the newly released Fermi architecture of NVIDIA Corporation, or the Larrabee architecture to be launched by Inter Corporation. Processors, hundreds of hardware threads, and complex memory hierarchies.

The data processing method of the present invention is specially optimized for complex algorithms with dynamic characteristic execution behavior and irregular data structure, and can dynamically manage data according to the principle of storage locality and SIMD operation mechanism during data processing, so that the application program can perform data processing It can maximize the effective use of hardware computing resources and storage resources. The method of the invention can quickly and conveniently develop a high-performance parallel execution application program, which will undoubtedly greatly accelerate the progress and efficiency of program development and save research and development costs.

Description of drawings

Fig. 1 is a performance analysis of CUDA and the model of the present invention as scene complexity increases.

Detailed ways

Select one to be equipped with a 4-core CPU of Intel Xeon 3.7GHz, a PC of NvidiaGTX285 (1G video memory) to verify the feasibility of the present invention. Based on the PTX instruction set, a set of programming interface based on the above method is realized, and according to the method proposed by the present invention, the ray tracing algorithm with a large number of dynamic irregular behaviors in graphics is redesigned and written, and it is used with Nvidia's The effect of the code written by the CUDA programming model is compared, and the following analysis is made.

Divide the application program into several computing tasks. In order to meet the SIMD/SIMT operation and local memory access characteristics of the hardware, we encapsulate the calculations with similar execution behavior or similar memory access behavior in one computing task for effective processing. Each Computing tasks should be as short as possible and have a single function. Computing tasks can be executed in parallel or serially according to the specific situation. Computing tasks are computed in a data-parallel manner internally, and asynchronously computed between computing tasks in a task-parallel manner. Each computing task has a state to handle the execution of computing tasks that may have interdependencies.

According to the characteristics of the calculation tasks in the ray tracing algorithm, six calculation tasks are created in the application execution pipeline, which respectively perform calculation tasks such as ray generation, traversal acceleration structure, patch intersection, coloring, and shadow, and are carried out in the data task scheduling pipeline at the same time. Ray sequencing and creation of ray packages. These tasks all have good parallel execution capabilities, that is, a wide SIMD execution width, but the recursive nature of light makes the effective SIMD usage rate likely to drop sharply as the recursion proceeds. In addition, we use delayed calculation technology to further improve SIMD utilization during implementation, that is, if the shading task cannot generate enough rays to form a complete ray package after calculation, the intersection calculation will be delayed until the complete ray package has been formed; Likewise, if the intersection computation task cannot generate enough rays for the shading computation, the shading computation will also be delayed.

Divide data into static data and dynamic data, where static data refers to data that does not change during the execution of the application, and dynamic data refers to new data that is constantly changing during the execution of the application. Set up a storage pool during initialization, allocate a certain amount of space for static data in the video memory according to the specific application program, and the rest of the space is occupied by dynamic data. All this information is recorded in a configuration file.

The size of the static data required by some applications may exceed the size of the video memory, so it is possible to dynamically schedule the static data during program execution, and the size of the data imported each time may not be exactly the same as the last time, so it may be in the static Data areas and dynamic data ranges generate fragments. In order to avoid fragmentation and effectively use the video memory, we can use a two-way allocation method in the video memory to store static data at the low address end of the storage pool, and store dynamic data at the high address end of the storage pool.

As mentioned above, in order to give full play to the characteristics of the heterogeneous multi-core architecture and rationally use hardware resources, the present invention designs a pipeline parallel execution mode that combines the application program execution pipeline and the data task scheduling pipeline, and the application program execution pipeline that involves a large number of calculations It runs on the GPU, while the data task scheduling pipeline involving a large number of logical judgments runs on the CPU. The two pipelines are executed asynchronously and in parallel, and the data task scheduling pipeline runs ahead of the application execution pipeline. Through this pipeline parallel execution mode, we can not only guarantee the independence and parallelism of calculations, but also avoid expensive synchronization operations such as atomics and locks.

When implementing, the present invention designs the data task scheduling pipeline based on the following three principles: 1. the access to static data should be kept at the fastest layer (i.e. cache, shared memory, etc.) in the hardware storage hierarchy as far as possible, and at the same time Try to delay access to data until such access is unavoidable. ② Prioritize the tasks with sufficient similarity data, or the generated data can assist other tasks to improve the priority of execution, or the execution of multiple tasks has similarity. ③ Task scheduling is performed in a data-driven manner, and scheduling is performed according to the type of the idle processor and the tasks corresponding to the static data in the current storage pool.

1) The present invention designs a data analyzer to dynamically control the use of data, so as to solve the situation that some programs may generate unpredictable data volumes and cause unbalanced load of the entire execution pipeline. The execution mode of data parallelism is likely to cause a large amount of new data to be generated by a computing task. It is difficult to store and use these data at the same time. A large amount of new data may also quickly consume limited video memory. The unpredictability of data also increases the difficulty of data management. Therefore, the present invention is provided with a data analyzer, and before the calculation task is executed each time, it is necessary to judge whether the size of the new data to be generated exceeds the current remaining display memory (the specific evaluation method is determined according to the corresponding application); Judging that the remaining video memory capacity is exceeded, we will group the input data to process the data in batches. Our method will greatly reduce the burden on system storage and bandwidth caused by some algorithms involving massive data, so that the data in the video memory is all the data required by the thread being calculated, thereby further enhancing the parallel computing efficiency of the thread , Improve the effective use of hardware.

A data cache area is set up for each computing task to manage the data generated or consumed by each computing task. Since the generation and consumption of data in some complex algorithms are dynamic and irregular, in order to satisfy the principle of local similarity and SIMD operation characteristics, so that the calculation can be concentrated in the local data set as much as possible, it is necessary to reorganize these data to ensure that the calculation can continue Do it efficiently in hardware. The powerful bandwidth capability of the current hardware and the powerful logical processing capability of the CPU make the dynamic data reorganization operation very feasible.

2) A task scheduler is designed to perform priority-based dynamic scheduling of unpredictable task execution sequences, and manage corresponding data transfers according to the scheduled tasks. We use the method of on-demand scheduling. When a certain processor is available, ① set a semaphore and lock the scheduler; ② scan the entire task sequence to be executed, select the task with the highest priority, and mark it; unlock.

Priority determination is the core part of our scheduler. Given the characteristics of mixed processing resources, we prioritize tasks based on the location of the required data in the storage hierarchy, the type of processor required, and the size of the required data set. Specifically, the following principles are combined in order of priority from high to low: (1) The execution of tasks does not require static data; (2) The required data is in the cache; (3) Prioritize data with sufficient similarity The tasks, or the generated data can assist other tasks to improve the execution priority, or the execution of multiple tasks is similar. (4) The required data is in the GPU memory; (5) The required data is in the CPU memory; (6) The required data is being transferred from the hard disk to the memory; (7) The required data set is too small to fully utilize the hardware computing power.

Select test scenarios with different geometric complexity, Bunny, Fairy, BART Kitchen as test model files,

Fairy is a dynamic scene with two reflection calculations, and the rendering resolution is 1024*1024. We used the method of the present invention and the CUDA programming model to test this scenario, and the results are shown in Table 1. It can be seen that the method of the present invention has achieved better performance than CUDA. The pipeline parallel mechanism implements priority-based task scheduling according to the balanced load of processing cores by rationally using hardware computing resources and storage resources.

Table 1

CUDA The method of the present invention Bunny 9.3 11.1 Fairy 4.3 5.6 BART Kitchen 3.8 5.1

Table 1 uses CUDA and this model to draw frames per second for scenes Bunny, Fairy, and BART Kitchen at a resolution of 1024*1024.

In order to verify the parallel use ability of the method of the present invention for hardware, the utilization rate of the scalar processor is tested, which directly reflects whether our scheduling and organization method for data and tasks can maximize the parallel execution ability of the algorithm on the hardware. Note that we did not use ALU usage as our test standard, because sometimes even if thread slots are occupied, ALU may not be fully used due to memory access latency or low SIMD utilization. As shown in Table 2, compared with the CUDA programming model, the method of the present invention can use GPU computing resources more effectively.

Table 2

CUDA The method of the present invention Bunny 90% 90% Fairy 72% 85% BART Kitchen 69% 80%

Table 2 Comparison of GPU utilization between CUDA and this model.

In order to illustrate that the method of the present invention can dynamically organize data and schedule tasks for scenes of different complexity without unbalanced load, it can be seen from Figure 1 that when the complexity of the scene is extremely increased, the CUDA programming model will have obvious load imbalance However, poor utilization of processing resources will eventually lead to performance degradation, while the method of the present invention maintains relatively stable performance.

Claims (6)

1. the general data processing method based on multiple parallel is characterized in that, in computing machine with GPU and CPU processor:

(1) application program that will carry out data processing is divided into some act of execution;

(2) according to the similarity of act of execution, all act of execution are divided into several tasks to data or calculating;

(3) data that application program need be handled are divided into static data and dynamic data, divide storage space in can carrying out the computing machine video memory of described application program, be respectively static data and dynamic data and divide storage area in this storage space;

(4) on GPU and CPU, set up the execution pipeline respectively, according to processing mode to data, task in the step (2) is divided into calculation type task and logic determines type task, operation calculation type task on GPU, operation logic judgement type task on CPU is until the execution of finishing application program, wherein in the GPU pipeline, task inside is moved in the mode of data parallel, and the mode with tasks in parallel between the task is moved.

2. general data processing method according to claim 1 is characterized in that, each act of execution may be done to few a basic operation or a calculating operation to data.

3. data parallel processing method according to claim 1 is characterized in that, described static data is the data that can not change in the application program implementation, and described dynamic data is the data that produce in the application program implementation.

4. data parallel processing method according to claim 1, it is characterized in that, on GPU and CPU, set up respectively and carry out pipeline, according to processing mode to data, task is divided into calculation type task and logic determines type task, operation calculation type task on GPU, operation logic judgement type task on CPU, two kinds of pipeline executed in parallel.

5. data parallel processing method according to claim 1 is characterized in that, in the step (4), the act of execution of same task inside is moved in the data parallel mode, and between different task act of execution with the parallel mode asynchronous operation.

6. data parallel processing method according to claim 1 is characterized in that, each task all is provided with a priority state, when new task occurs, selects the high task of priority to move successively according to the priority state of all tasks.

Images