TW201317897A - Task scheduling and allocation for multi-core/many-core management framework and method thereof - Google Patents

Abstract

A task scheduling and allocation for multi-core/many-core management framework and a method thereof are provided. Application cores and service cores are being assigned to a CPU which contained multi-core/many-core management framework to run application tasks and service tasks by corresponding cores, and provide inter-communication between application cores and service cores via an inter-process communication (IPC). Therefore, the efficiency of managing task blocking and preemption costs directly and indirectly in task scheduling and allocation may be achieved.

Description

Work scheduling and distribution management architecture and method for multi-core/core core

A work scheduling and distribution management architecture and method thereof, in particular, a work scheduling and distribution management architecture and method for a multi-core/core core that can be executed at different designated cores by application work and service work.

In recent years, the central processor has evolved from a single-core architecture to a multi-core architecture. The increase in the number of cores has also evolved from a multi-core architecture to a many-core architecture, and due to multi-core/core With the rapid development of the architecture, system engineers will face greater challenges in the design of the system due to the expansion of the core.

In the multi-core/core architecture, the core will generate the blocking time due to the sharing of resources, so that some cores are idle and the system performance is reduced. In order to avoid the above problems, the work schedule in the core is Will be an important part.

When designing a system, there are a number of priority-calculated scheduling algorithms for independent work that have been fixed or dynamic. For example, in 1991, NC Audsley proposed "Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times". "On the Complexity of Fixed-Priority Scheduling of periodic, Real-Time Tasks" by JY-T. Leung and J. Whitehead in 1982, "Scheduling Algorithms for Multiprogramming" by CL Liu and JW Layland in 1973 In a Hard Real Time Environment" and "Fundamental Design Problems of Distributed Systems for the Hard Real Time Environment" proposed by AK Monk in 1983.

However, if the work has the status of resource sharing, there will be a phenomenon of priority inversions, which will generate unnecessary blocking costs. In order to solve the above problems, there are many work synchronization agreements. It was proposed, for example, "Stack-Based Scheduling of Realtime Processes" proposed by TP Baker in 1991, "Dynamic Priority Ceilings: A Concurrency Control Protocol for" by M.-I. Chen and K.-J. Lin in 1990. Real-Time System" and the "Priority Inheritance Protocol: An Approach to Real-Time Synchronization" proposed by L. Sha, R. Rajkumar and JP Lehoczky in 1990, etc., and the monotonic rate proposed in the priority ceiling protocol (PCP) Rate-monotonic) In the case of priority allocation, the management priority is highest and the priority inheritance is to prevent the occurrence of deadlock and priority reversal.

The problem of scheduling work and synchronization in a multi-core/core architecture is more complicated. Therefore, global scheduling algorithms and static task allocation through dynamic task migration. The cluster scheduling algorithm underneath is proposed to solve the above problems caused by the multi-core/core architecture.

The multiprocessor priority ceiling protocol (MPCP) extends the concept of the highest priority to the multi-core/core architecture, and the resources manage the remote blocking and priority reversal with the help of the global semaphore. In 2010, B. Brandenburg and J. Anderson proposed "Optimality Results for Multiprocessor Real-Time Locking" to point out the relationship between the number of job blocking and the priority reversal under multi-core/core architecture scheduling.

To illustrate the prior art work schedule with a practical example, please refer to "1", and "1" is a working schedule diagram of the prior art.

Taking a central processor having two cores as an example, it is assumed that the second work 32 is executed on the first core 41, assuming that the first work 31 and the third work 33 are performed on the second core 42, first, the second work 32 first performed on a first core 41, and then a third work 33 on the second execution core 42, at time t _0, third 33 performs work on the second core 42 successfully enter the critical section (critical section), and At time t ₁ , the second work 32 performed on the first core 31 also needs to enter the critical interval, but since the third work 33 performed on the second core 42 has successfully entered the critical interval, at this time (time t ₁ ) The second work 32 executed on the first core 41 will suspend execution to wait for the third work 33 to execute the end of the critical interval, at which time the first core 31 (time t ₁ ) will enter the idle state.

At time t ₂ , while the first job 31 having the high priority is executed on the second core 42 (time t ₂ ), the third job 33 executed on the second core 42 will be suspended, the second core 42 will begin a first high priority work 31, up to time t 42 after the execution of the second core 31 to complete the first operation, the second core 42 will then continue to work 33 ₃ third.

At time t ₄ , after the third work 33 performed on the second core 42 releases the critical interval, the second work 32 performed on the first core 41 at this time (time t ₄ ) can successfully enter the critical interval, A core 41 can continue to perform the second work 32.

In summary, it can be seen that the prior art has long existed in the prior art because of work seizure and thus a long time work blocking problem, so it is necessary to propose an improved technical means to solve this problem.

In view of the prior art prior art having a work blocking problem caused by work preemption for a long time, the present invention discloses a work scheduling and distribution management architecture for a multi-core/core core and a method thereof, wherein:

The work scheduling and distribution management architecture for multi-core/core core disclosed in the present invention comprises: a central processing unit (CPU), and the central processing unit has a multi-core/multi-core ( Many-Core), the central processor further includes: at least one Service Core and multiple Application Cores.

At least one service core is specified in the multi-core/core core, at least one core is at least one service core, the service core is designated to perform a service task (Service Task); and multiple application cores are cores that are not designated as service cores. The application core, the application core is specified to execute the application task (Application Task); wherein, when the application work performed by one of the application cores needs to enter the service work, the application core uses Inter-Process Communication (IPC) mode. Issue a service execution request to request one of the service cores to perform the service work, and the application work will suspend execution to bring the application core into an idle state; when the service core performs the service work, return to the application core through the interprocess communication to continue Perform application work.

The method for scheduling and distributing management of a multi-core/core core disclosed in the present invention comprises the following steps:

First, at least one core is designated as a Service Core in a Central Processing Unit (CPU) with a Multi-Core/Many-Core, and the rest are not designated as service cores. The core of the application is the Application Core: where the service core is specified to execute the Service Task, the application core is specified to execute the Application Task; then, when one of the application cores performs the application work When it is required to enter the service work, the application core sends a service execution request in an Inter-Process Communication (IPC) manner to request one of the service cores to perform the service work, and the application work is suspended to make the application core enter the idle state. Finally, when the service core execution service is completed, it returns to the application core through interprocess communication to continue the application work.

The apparatus and method disclosed by the present invention are as above, and the difference from the prior art is that the present invention specifies application cores and service cores in a central processing unit having multiple cores/cores to enable application work and service work. It can be executed separately in different designated cores, and the execution requests between the cores can be reached through inter-process communication, so that fewer cores need to complete the work within a certain time, and the work blocking situation can be managed more effectively.

Through the above technical means, the present invention can achieve the technical effect of effectively managing direct or indirect work interruption and work preemption during work scheduling and distribution.

The embodiments of the present invention will be described in detail below with reference to the drawings and embodiments, so that the application of the technical means to solve the technical problems and achieve the technical effects can be fully understood and implemented.

The following is a description of the work scheduling and distribution management architecture for multi-core/cores disclosed in the present invention, and please refer to "FIG. 2", and "FIG. 2" is shown as a multi-core for the present invention. / The core of the work scheduling and distribution management device schematic.

The work scheduling and distribution management architecture for multi-core/core core disclosed in the present invention comprises: a central processing unit (CPU) 10 having a multi-core (Multi-Core)/publicity The core processor (Many-Core) 11 further includes: at least one service core 111 and a plurality of application cores 112.

The service core 111 is to specify at least one core 11 in the multi-core/core core 11 as at least one service core 111, and the service core 111 is designated to perform a service task 21, such as the service work 21 described in the present invention. It is the execution of the Critical Section.

The plurality of application cores 112 are the core 11 that is not designated as the service core 111, and the application core 112 is designated to execute an application task 22, and the application work 22 described in the present invention is, for example, Application execution.

It is worth noting that the above service work 21 and application work 22 determine the priority of each service work 21 and application work 22 in a fixed-priority manner, and determine each service work in a fixed priority manner. For the priority of the application work 22, please refer to the prior art, and details are not described herein.

The service core 111 and the application core 112 determine the scheduling and allocation of the service work 21 and the application work 22 according to the priority of the service work 21 and the application work 22, and the sequence of the application work 22 is preempted, that is, has a high priority. The service work 21 and the application work 22 of the right are preferentially executed by the service core 111 and the application core 112, that is, when a certain application work 22 (in this case, the application work has the highest priority) is suspended, the application core 112 is applied. A high priority application job 22 can be executed.

When the application work 22 executed in one of the application cores 112 needs to enter the service work 21, that is, when the application work 22 executed in the application core 112 needs to execute a critical interval, the application core 112 performs inter-process communication (Inter-Process). The Communication, IPC) method issues a service execution request to request one of the service cores 111 to perform the service work 21 (ie, the execution critical interval), and the inter-process communication method may further include a Remote Procedure Call (RPC) mode. , Signal mode, Message Passing mode, Shared Memory mode, Memory-Mapped Files mode, Pipe mode, Socket mode, This is for illustrative purposes only and is not intended to limit the scope of application of the invention.

When the application core 112 issues a service execution request in an interprocess communication manner to request one of the service cores 111 to perform the service work 21, the application work 22 suspends execution to bring the application core 112 into an idle state, and the service work 21 Will be added to the sequence of service work of the service core 111, the service work 21 already prepared in the service core 111 should be scheduled according to priority, and when no service work 21 is requested to be executed, the service core 111 Will enter the idle state.

The priority of the service work 21 described above should take into account the priority of the application work 22, that is, when the priority of the application work 22 is a high priority, the priority of the service work 21 is also a high priority when the application works. When the priority of 22 is low priority, the priority of the service work 21 is also low priority.

Then, after the service core 111 performs the service work 21, the application core 112 can be returned to the application core 112 through the inter-process communication to continue the application work 22, so that the service core 111 and the application core 112 are scheduled and distributed in the work. It can effectively manage direct or indirect work blocking and work preemption costs.

Next, the operation mode and flow of the present invention will be explained below by way of an embodiment, and please refer to "Fig. 2", "3rd picture" and "4th picture", and "3rd picture" is shown as The present invention is applied to a multi-core/core core work scheduling and distribution management method flow chart; "Fig. 4" is a timing diagram of the work scheduling and distribution management for the multi-core/core core of the present invention.

In the present embodiment, a central processing unit having three cores is exemplified, and the present invention is not limited thereto. A core is designated as a service core 111 in a central processing unit having three cores, and is not designated as The core of the service core 111 is the first application core 1121 and the second application core 1122 (step 110).

It is assumed here that the second application work 222 is executed on the first application core 1121, assuming that the first application work 221 and the third application work 223 are executed on the second application core 1122, and that the service work 21 is executed on the service core 111. (Step 110).

It should be noted that the second application work 222 and the third application work 223 have the same global semaphore. Since the second application work 222 and the third application work 223 have the same global flag, the second application work 222 And the third application work 223 will request the same service work 21 (ie, critical section) to execute, but for convenience of explanation, the service work 21 requested by the second application work 222 will be represented by the second service work 212, and The service work 21 requested by the third application job 223 is represented by the third service job 213.

First, the second application work 222 is first executed on the first application core 1121, then the third application work 223 is executed on the second application core 1122, and at the time t ₀ , the third application is executed on the second application core 1122. The work 223 is to perform the third service work 213, and the second application core 1122 sends a service execution request to the service core 111 in an interprocess communication manner to request the service core 111 to perform the third service work 213 (ie, the critical interval). (time t ₀₎ of the third application work performed on the second core application 1,122,223, would be suspended at a time (time t ₀₎ of the second core application 1122 will enter an idle state (step 120).

Next, at time t _1, a second application work executing on the first application to execute a second core 1,121,222 service work 212, a first core application 1121 will issue a service request to the service execution core 111 to inter-process communication The request service core 111 performs the second service work 212 (ie, the critical interval), but at this time (the time t ₁ ) the service core 111 is performing the third service work 213 for the third application work 223, and the second application work 222 The requested second service work 212 will first enter the service sequence of the service core 111 and wait for execution. At this time (the time t ₁ ), the second application work 222 executed on the first application core 1121 will be suspended. The first application core 1121 (time t ₁ ) also enters an idle state (step 120).

Then, at time t ₂ , the first application work 221 needs to be started, and at this time (time t ₂ ) the second application core 1122 is also in an idle state, so the first application work 221 can start at the second application core 1122. Executed in.

Then, at time t _3, the third service work 213 has been executed, this time (time t ₃₎ core service 111 will then return a second application core 1122 to inter-process communication, to enable the core to execute the second application The third application work 223 on 1122 can continue to execute, but since the second application core 1122 at this time (time t ₃ ) is executing the first application work 221 (the first application work 221 being executed is a high priority), Therefore, the third application work 223 is that the third application work 223 is resumed after the execution of the first application work 221 is completed until time t ₅ (step 130).

At time t _3, the third service work 213 has been executed, will be followed by a second serving core service 111 performs the working stroke ordering 212, until time t _4, the second service 212 work has been performed Upon completion, the service core 111 at this time (time t ₄ ) will return to the first application core 1121 in an inter-process communication manner, so that the second application work 222 executed on the first application core 1111 can be resumed (step 130). ).

Therefore, the service core 111 and the application core 112 can effectively manage direct or indirect work blocking and work preemption costs during work scheduling and distribution.

In summary, it can be seen that the difference between the present invention and the prior art is that the present invention separates the application core from the service core by designating the cores in the central processing unit having multiple cores/cores to separate the application work from the service work. Execute at different designated cores and achieve execution requests between cores through inter-process communication, so that fewer cores need to complete work within a certain time, and it is more effective to manage the situation of work blocking.

The technical solution can solve the problem that the prior art existing in the prior art has a long-term work blocking problem due to job preemption, thereby effectively managing direct or indirect work blocking and work when the work scheduling and distribution are achieved. The technical effect of preemption.

While the embodiments of the present invention have been described above, the above description is not intended to limit the scope of the invention. Any changes in the form and details of the embodiments may be made without departing from the spirit and scope of the invention. The scope of the invention is to be determined by the scope of the appended claims.

10. . . CPU

11. . . core

111. . . Service core

112. . . Application core

1121. . . First application core

1122. . . Second application core

twenty one. . . Service work

212. . . Second service work

213. . . Third service work

twenty two. . . Application work

221. . . First application work

222. . . Second application work

223. . . Third application work

31. . . First job

32. . . Second job

33. . . Third job

41. . . First core

42. . . Second core

t ₀ . . . time

t ₁ . . . time

t ₂ . . . time

t ₃ . . . time

t ₄ . . . time

t ₅ . . . time

Step 110: Specify at least one core as a service core in a central processing unit having multiple cores/cores, and the remaining cores not designated as service cores are application cores, wherein the service core is designated to perform service work, and the application core is Specify to perform application work

Step 120: When the application work performed in one of the application cores needs to enter the service work, the application core issues a service execution request in an interprocess communication manner to request one of the service cores to perform the service work, and the application work is suspended to perform Application core enters idle state

Step 130: After the service core execution service is completed, return to the application core through inter-process communication to continue the application work.

FIG. 1 is a timing diagram of a work schedule of the prior art.

FIG. 2 is a schematic diagram of an apparatus for multi-core/core core work scheduling and distribution management according to the present invention.

FIG. 3 is a flow chart showing a method for scheduling and distributing management of a multi-core/core core according to the present invention.

FIG. 4 is a timing diagram of the work scheduling and allocation management for the multi-core/core core of the present invention.

10. . . CPU

11. . . core

111. . . Service core

112. . . Application core

twenty one. . . Service work

twenty two. . . Application work

Claims (10)

A work scheduling and distribution management architecture for a multi-core/core core, comprising: a Central Processing Unit (CPU) having a Multi-Core/Many Core (Many- Core), the central processing unit further includes: at least one service core, at least one core is specified as the at least one service core in the multi-core/the core, and the service core is designated to perform a service task; And a plurality of application cores, the core that is not designated as the service core is the application core, and the application core is specified to execute an application task; wherein, when one of the application cores performs an application work, When entering the service work, the application core sends a service execution request in an Inter-Process Communication (IPC) manner to request one of the service cores to perform the service work, and the application work is suspended to enable the application core to enter. Idle state; and when the service core execution service is completed, return to the application core through interprocess communication to continue The application work. The work scheduling and distribution management architecture for multi-core/core cores as described in claim 1 of the patent application, wherein the service work refers to the execution of a critical section. The work scheduling and distribution management architecture for multi-core/core cores as described in claim 1, wherein the service work and the application work determine each service work and application in a fixed-priority manner. The priority of the work, and when the application work performed in one of the application cores needs to enter the service work, the priority of the service work should take into account the priority of the application work. The work scheduling and distribution management architecture for multi-core/core cores as described in claim 3, wherein the application work performed in each application core is scheduled according to priority, and the sequence of application work It will be preempted. When the application work performed in one of the application cores needs to enter the service work, the service work will be added to the service work sequence, and the prepared service work should be scheduled according to the priority. The work scheduling and distribution management architecture for multi-core/core cores as described in claim 1, wherein the inter-process communication includes a remote procedure call (RPC), a signal (Signal), and a message. Message Passing, Shared Memory, Memory-Mapped Files, Pipes, Sockets. A work scheduling and distribution management method for a multi-core/core core, comprising the following steps: in a Multi-Core/Many-Core Central Processing Unit (CPU) At least one core is specified as the Service Core, and the rest is not designated as the application core. The core of the service is specified to execute the Service Task, and the application core is specified. Execute the application task (Application Task); when the application work performed by one of the application cores needs to enter the service work, the application core sends a service execution request in the inter-process communication (IPC) manner to request the service core. One performs the service work, and the application work is suspended to make the application core enter the idle state; and when the service core performs the service work, the application core is returned to the application core through the inter-process communication to continue the application work. The work scheduling and distribution management method for multi-core/core cores as described in claim 6 of the patent application scope, wherein the service core is specified to perform the service work step, and the service work refers to the execution of the critical section (Critical Section). . The work scheduling and distribution management method for multi-core/core cores as described in claim 6 wherein the service core is designated to perform service work, and the application core is service work and application designated to perform application work steps. Work is to determine the priority of each service work and application work in a fixed-priority manner, and when the application work performed in one of the application cores needs to enter the service work, the priority of the service work should be considered. The priority of the application work. The work scheduling and distribution management method for multi-core/core is described in claim 8, wherein the application work performed in each application core is arranged according to priority scheduling and allocation, and the sequence of application work It will be preempted. When the application work performed in one of the application cores needs to enter the service work, the service work will be added to the service work sequence, and the prepared service work should be scheduled according to the priority. The method for scheduling and assigning management for a multi-core/core core, as described in claim 8, wherein the inter-process communication includes a remote procedure call (RPC), a signal (Signal), and a message. Message Passing, Shared Memory, Memory-Mapped Files, Pipes, Sockets.