CN105487838B - A task-level parallel scheduling method and system for a dynamically reconfigurable processor - Google Patents

Abstract

The present invention proposes a task-level parallel scheduling method and system for a dynamically reconfigurable processor, wherein the system includes a main controller, a plurality of reconfigurable processing units, a main memory, direct storage access and a system bus, wherein the Each reconfigurable processing unit is composed of a co-controller, multiple reconfigurable processing unit arrays responsible for reconfigurable computing, and multiple shared memories for data storage, wherein the reconfigurable processing unit array and shared memory Arranged adjacently, the shared memory can be read and written by two surrounding reconfigurable processing unit arrays. The task-level parallel scheduling method and system of the dynamic reconfigurable processor proposed by the present invention can perform different scheduling methods for different tasks by adjusting the scheduling method, and basically all parallel tasks can be obtained on this reconfigurable processor. Nice parallel speedup.

Description

A task-level parallel scheduling method and system for a dynamically reconfigurable processor

technical field

The invention relates to the field of computers, and in particular to a task-level parallel scheduling method and system of a dynamically reconfigurable processor.

Background technique

In the previous processor computing models, they are usually divided into the following two categories. The traditional general-purpose computing based on the von Neumann processor is extremely flexible, but its instruction stream-driven execution mode, limited computing unit and memory bandwidth make its overall performance and power consumption unsatisfactory. Dedicated computing can optimize structures and circuits for specific applications without requiring an instruction set, with fast execution speed and low power consumption. However, there are fatal flaws in dedicated computing systems, such as poor flexibility and scalability, and the ever-evolving and more complex applications often cannot be completed through simple expansion. For different applications, different dedicated computing systems must be designed, so hardware design often cannot keep up with the update speed of applications. At the same time, the design cycle of the dedicated computing system is long, and the one-time engineering investment cost is too high. Reconfigurable computing is a computing method that combines the flexibility of software and the efficiency of hardware in this context. Reconfigurable computing technology combines the advantages of both general-purpose processors and ASICs. It can provide high efficiency of hardware and programmability of software. It achieves a better balance between key indicators such as performance, power consumption and flexibility, and fills the gap between general-purpose computing and special-purpose computing.

At this stage, the mainstream processors in computers are multi-core CPUs and many-core GPUs with 2 to 8 cores, and this design also makes parallel processing a hot topic. Parallel algorithms and parallel programming have also become a must for programmers to understand and master. Content. In June 2007, NVIDIA launched CUDA, a software and hardware system that uses GPU as a data parallel computing device. CUDA becomes a model with the CPU as the host and the GPU as the coprocessor. The CUDA parallel computing function running on the GPU is called the kernel (kernel). A kenerl function is not a complete program, but steps in the entire CUDA program that can be executed in parallel. In this way, the CPU and GPU are well divided to achieve various levels of parallelism.

However, there is no uniform parallel processing specification for the general-purpose reconfigurable processor targeted by the present invention. A typical reconfigurable processor architecture includes a general-purpose processor and one or more reconfigurable processing units (Reconfigurable Processing Unit, RPU), how to implement multi-tasking applications on this coarse-grained reconfigurable processor Task allocation, the present invention proposes a set of RPU allocation and task scheduling methods and systems.

Contents of the invention

The present invention proposes a task-level parallel scheduling method and system for a dynamically reconfigurable processor. By adjusting the scheduling method, different scheduling methods can be implemented for different tasks. Basically, all parallel tasks can be performed on this reconfigurable processor. Get good parallel speedup.

In order to achieve the above object, the present invention proposes a task-level parallel scheduling system of a dynamically reconfigurable processor, including a main controller, a plurality of reconfigurable processing units, a main memory, direct storage access and a system bus,

Wherein, each reconfigurable processing unit is composed of a co-controller, a plurality of reconfigurable processing unit arrays responsible for reconfigurable computing, and a plurality of shared memories for data storage, wherein the reconfigurable processing unit The array and the shared memory are arranged adjacently, and the shared memory can be read and written by two reconfigurable processing unit arrays connected around them.

Further, the main controller is used to execute serial codes in the program that are not suitable for processing by the reconfigurable processing unit, and is responsible for scheduling, starting and running of multiple reconfigurable processing units.

Further, the reconfigurable processing unit is responsible for computing intensive parallel codes in the computing program.

Further, the co-controller is used to carry the data and configuration information required for calculation of multiple reconfigurable processing unit arrays, and control the start, operation and termination of multiple reconfigurable processing unit arrays.

In order to achieve the above object, the present invention also proposes a task-level parallel scheduling method of a dynamically reconfigurable processor, comprising the following steps:

Encapsulate the computationally intensive parallelizable code in the application as a kernel function;

Compile the serial code and the parallel code respectively to generate executable code suitable for the main controller and the reconfigurable processing unit;

the host controller executes the serial portion of code;

When part of the code of the kernel function is executed, the main controller schedules and assigns the reconfigurable processing unit to process the part of the code of the kernel function.

Further, the main controller schedules the reconfigurable processing unit in two parallel ways: synchronous call and asynchronous call:

If it is a synchronous call, the main controller will search for a reconfigurable processing unit that is not running, and load the executable code and configuration information. The reconfigurable processing units call at the same time to process the contents of different data blocks. After all the reconfigurable processing units are processed, the processing results are updated through the return value of the synchronization function, and the serial code execution of the main controller is continued;

If it is an asynchronous call, the main controller looks for a reconfigurable processing unit that is not running, and at the same time loads the executable code and configuration information without interrupting the main controller, and starts the reconfigurable processing unit , the main controller continues to run until the reconfigurable processing unit needs to return data, and then stops waiting for the reconfigurable processing unit to complete calculation and return data.

Further, when the kernel function instructions are few and one reconfigurable processing unit can complete the calculation task of the entire kernel function alone, multiple reconfigurable processing unit arrays inside it execute the same configuration information in parallel, and each reconfigurable processing unit The array of reconfigurable processing units is responsible for data computation in its own shared memory.

Further, when there are many instructions of the kernel function, and all statements of the kernel function cannot be executed at one time, the kernel function is divided into a plurality of subtasks with the same length, and the configuration information of the subtasks is assigned to multiple subtasks in order respectively. A reconfigurable processing unit array, because each reconfigurable processing unit array can read and write the adjacent upper layer shared memory and lower layer shared memory, each shared memory is divided into A block and B block of equal size, in the task pipeline During the process, each reconfigurable processing unit array first reads data from block A of the upper-layer shared memory, and writes the result into block B of the lower-layer shared memory. Block B of the shared memory reads data and writes the result to block A of the underlying shared memory. At the same time as these two processes, data is transferred to the main memory for the part of the first and last shared memory that does not participate in the calculation.

Compared with the prior art, the above-mentioned technical solution includes the following innovations and beneficial effects (advantages):

1. The task-level parallel scheduling method of the present invention is designed and implemented for a specific three-level heterogeneous coarse-grained reconfigurable processor, and the data-intensive and calculation-intensive parts of the application are packaged by the kernel function method , the main controller is responsible for the processing of serial codes and the allocation of reconfigurable processing units, and the kernel functions are processed by reconfigurable processing units with strong parallel computing capabilities. Arrays are constructed for calculation processing. In this way, the parallel computing capability of the multi-level heterogeneous coarse-grained reconfigurable processor can be fully utilized, and in conjunction with a specific compiler, it can fully accelerate computing-intensive applications in parallel.

2. On the basis of the GPU parallel computing tool CUDA, the present invention transplants its parallel scheduling method to a multi-level heterogeneous coarse-grained reconfigurable processor, and proposes a new pipelined scheduling method, expanding the support for different types of The task scheduling method.

3. The present invention realizes the scheduling process of multi-task and multi-reconfigurable processing units. By adjusting the scheduling method, different scheduling methods can be carried out for different tasks, avoiding the requirement of a single scheduling method for tasks, and basically all parallel tasks can be Get good parallel speedup on this reconfigurable processor.

Description of drawings

FIG. 1 is a schematic structural diagram of a task-level parallel scheduling system of a dynamically reconfigurable processor according to a preferred embodiment of the present invention.

FIG. 2 is a flowchart of a task-level parallel scheduling method for a dynamically reconfigurable processor according to a preferred embodiment of the present invention.

FIG. 3 and FIG. 4 are schematic diagrams of a synchronous scheduling method when the number of kernel function instructions is small.

FIG. 5 is a schematic diagram of an asynchronous scheduling method when there are many kernel function instructions.

detailed description

The specific embodiments of the present invention are given below in conjunction with the accompanying drawings, but the present invention is not limited to the following embodiments. Advantages and features of the present invention will be apparent from the following description and claims. It should be noted that all the drawings are in very simplified form and use imprecise ratios, which are only used for the purpose of conveniently and clearly assisting in describing the embodiments of the present invention.

Please refer to Fig. 1, Fig. 1 shows the schematic structural diagram of the task-level parallel scheduling system of the dynamic reconfigurable processor of the preferred embodiment of the present invention, wherein the enlarged view of RPU1 on the right side of the box to show its internal functional structure . The present invention proposes a task-level parallel scheduling system of a dynamically reconfigurable processor, including a main controller ARM11, a plurality of reconfigurable processing units (Reconfigurable Process Unit, RPU), a main memory DDR, a direct memory access (Direct Memory Access, DMA) and a system bus AHB, wherein each reconfigurable processing unit RPU is composed of a co-controller ARM7, a plurality of reconfigurable processing unit arrays (Processing Element Array, PEA) responsible for reconfigurable computing, and a plurality of It is composed of a shared memory (Shared Memory, SM) for data storage, wherein the reconfigurable processing unit array PEA and the shared memory SM are arranged adjacently, and the shared memory SM can be connected by two reconfigurable processing unit arrays Read and write by PEA.

According to a preferred embodiment of the present invention, the main controller ARM11 is used to execute serial codes in the program that are not suitable for processing by the reconfigurable processing unit RPU, and is responsible for scheduling, starting and running of multiple reconfigurable processing units RPU. The reconfigurable processing unit RPU is responsible for computing intensive parallel codes in computing programs. Further, the co-controller ARM7 is used to carry the data and configuration information required for calculation of multiple reconfigurable processing unit arrays PEA, and control the start, operation and termination of multiple reconfigurable processing unit arrays PEA.

According to a preferred embodiment of the present invention, each reconfigurable processing unit RPU includes 4 reconfigurable processing unit arrays PEA and 4 shared memories SM.

Please refer to FIG. 2 , which is a flow chart of a task-level parallel scheduling method for a dynamically reconfigurable processor according to a preferred embodiment of the present invention. The present invention also proposes a task-level parallel scheduling method of a dynamically reconfigurable processor, comprising the following steps:

Step S100: encapsulating the computationally intensive parallelizable code in the application program as a kernel function;

Step S200: compiling the serial code and the parallel code respectively to generate executable code suitable for the main controller and the reconfigurable processing unit;

Step S300: the main controller executes the serial code;

Step S400: When the kernel function part code is executed, the main controller schedules and allocates the reconfigurable processing unit to process the kernel function part code.

For general reconfigurable processors, most of the parallel processes only use the high-speed operations of reconfigurable components to process a large number of repetitive calculation-intensive operations. Architectural processor, which includes three levels of computing modules, namely the main controller, co-controller and PEA. The memory of the three is independent, and together constitute a three-level reconfigurable heterogeneous architecture. In the process of processing applications, the method of task-level parallelism not only includes the parallelism of reconfigurable units, but also includes the allocation and scheduling of multiple RPUs.

For a C code program of an application, we encapsulate the computationally intensive parallel code as a kernal (kernel) function. In an application, there may be multiple kernal functions with different functions and complexity. During the compilation process, the serial part and the parallel part are respectively compiled to generate executable codes suitable for the main controller part and the reconfigurable processing unit RPU part. There are two levels of parallelism in the kernel function, which are the synchronous and asynchronous parallelism between different RPUs and the code parallelism on the 4 PEAs inside the RPU.

For a multi-tasking application, when executing on the reconfigurable architecture, the main controller first executes the serial part of the code, and when executing the kernal part, the RPU scheduler of the main controller will allocate the RPU, and Divided into two parallel ways of synchronous call and asynchronous call:

If it is a synchronous call, the main controller will search for a reconfigurable processing unit that is not running, and load the executable code and configuration information. The reconfigurable processing units call at the same time to process the contents of different data blocks. After all the reconfigurable processing units are processed, the processing results are updated through the return value of the synchronization function, and the serial code execution of the main controller is continued;

If it is an asynchronous call, the main controller looks for a reconfigurable processing unit that is not running, and at the same time loads the executable code and configuration information without interrupting the main controller, and starts the reconfigurable processing unit , the main controller continues to run until the reconfigurable processing unit needs to return data, and then stops waiting for the reconfigurable processing unit to complete calculation and return data. The synchronous call method can process the kernal function with a large amount of data through multi-RPU parallel computing, while the asynchronous call can parallelize different kernal functions without dependencies.

After allocating and scheduling the RPU that executes the kernal function, there is also task parallelism inside the RPU, which is the second level of parallel computing. In the hardware architecture that the present invention relies on, each RPU contains 4 PEAs and corresponding SMs, where the SMs can be read and written by the two PEAs connected around, so that we can complete the kernal type for this architecture Two ways of parallel computing methods.

Please refer to FIG. 3 and FIG. 4 . FIG. 3 and FIG. 4 are schematic diagrams of a synchronous scheduling method when the number of kernel function instructions is small. When the kernel function instructions are few and one reconfigurable processing unit can complete the calculation task of the entire kernel function alone, multiple reconfigurable processing unit arrays inside it execute the same configuration information in parallel, and each reconfigurable processing unit The cell array is responsible for data calculations in its own shared memory, which reduces kernal execution time by up to a quarter. The first row of boxes block1~4 means that the co-controller copies data from DDR to the left half of SM, the circle means PEA execution, and the second row of boxes block1~4 means that PEA outputs the calculated data to the right side of SM Half part, the third row of blocks block1~4 indicates that the co-controller outputs data from the right half of SM to DDR, and the above is the loop body in the program.

When there are many kernel function instructions and it is impossible to execute all the statements of the kernel function at one time, in this case, we need to adopt a pipeline method for task parallelism. The specific solution is to divide the kernel function into no more than 4 Each subtask has the same length as possible, and the configuration information of the subtasks is assigned to four PEAs in sequence. Since each reconfigurable processing unit array can read and write adjacent upper-layer shared memory and lower-layer shared memory, the Each shared memory is divided into block A and block B of equal size. During the task pipeline process, each reconfigurable processing unit array first reads data from block A of the upper shared memory, and writes the result to the lower shared memory. Block B, after processing, each reconfigurable processing unit array reads data from block B of the upper-layer shared memory and writes the result to block A of the lower-layer shared memory. The part of the shared memory that does not participate in the calculation performs data transfer to the main memory. In this way, there is no additional data transfer time in the whole process, and the kernal function can be executed in an uninterrupted pipeline.

Please refer to FIG. 5 , which is a schematic diagram of an asynchronous scheduling method when there are many kernel function instructions. As shown in Figure 5, the programmer divides all the commands in the loop into several parts according to a certain method. When the compiler processes GR-C, these commands will be compiled into different PEA configuration packages respectively. The PEAs are called sequentially, and the clock cycle is delayed by one cycle to achieve the effect of water flow. In the first cycle, PEA1 calculates the data in part A of SM1, and puts the result into block B of SM2. In one cycle, PEA1 calculates the data of part B in SM1, and at the same time, PEA2 calculates the data of block B of SM2, and puts them into the A blocks of SM2 and SM3 respectively, and so on to form a pipeline process. After PEA4 calculates the data, it directly Copy the data to main memory until all the data has been processed. Inside the RPU, the complete execution process is divided by task, where block1~block5 represent different data streams, and the rightmost box represents the data output from SM3 to DDR.

Although the present invention has been disclosed above with preferred embodiments, it is not intended to limit the present invention. Those skilled in the art of the present invention can make various changes and modifications without departing from the spirit and scope of the present invention. Therefore, the scope of protection of the present invention should be defined by the claims.

Claims (3)

1. A task-level parallel scheduling method of a dynamically reconfigurable processor, characterized in that, comprising the following steps: Encapsulate the computationally intensive parallelizable code in the application as a kernel function; Compile the serial code and the parallel code respectively to generate executable code suitable for the main controller and the reconfigurable processing unit; the host controller executes the serial portion of code; When part of the code of the kernel function is executed, the main controller schedules and allocates the reconfigurable processing unit to process the part of the code of the kernel function; Wherein, when there are many instructions of the kernel function, and all statements of the kernel function cannot be executed at one time, the kernel function is divided into a plurality of subtasks with the same length, and the configuration information of the subtasks is assigned to multiple subtasks in order respectively. Reconfigurable processing unit array, since each reconfigurable processing unit array can read and write adjacent upper-layer shared memory and lower-layer shared memory, each shared memory is divided into A block and B block of equal size, during the task pipeline process In , each reconfigurable processing unit array first reads data from block A of the upper shared memory, and writes the result into block B of the lower shared memory. After processing, each reconfigurable processing unit array reads data from the upper shared memory Block B of the memory reads data and writes the result to block A of the underlying shared memory. At the same time as these two processes, the data is transferred to the main memory for the part of the first and last shared memory that does not participate in the calculation. 2. The task-level parallel scheduling method of a dynamically reconfigurable processor according to claim 1, wherein the scheduling of the reconfigurable processing unit by the main controller is divided into two parallel modes of synchronous invocation and asynchronous invocation : If it is a synchronous call, the main controller will search for a reconfigurable processing unit that is not running, and load the executable code and configuration information. The reconfigurable processing units call at the same time to process the contents of different data blocks. After all the reconfigurable processing units are processed, the processing results are updated through the return value of the synchronization function, and the serial code execution of the main controller is continued; If it is an asynchronous call, the main controller looks for a reconfigurable processing unit that is not running, and at the same time loads the executable code and configuration information without interrupting the main controller, and starts the reconfigurable processing unit , the main controller continues to run until the reconfigurable processing unit needs to return data, and then stops waiting for the reconfigurable processing unit to complete calculation and return data. 3. the task level parallel scheduling method of dynamic reconfigurable processor according to claim 1, is characterized in that, when described kernel function instruction is less, a reconfigurable processing unit can finish the calculation task of whole kernel function independently When , multiple reconfigurable processing unit arrays inside it execute the same configuration information in parallel, and each reconfigurable processing unit array is responsible for data calculation of its own shared memory.