JP2011141703A - System, method and program for arranging resource - Google Patents

Abstract

The present invention analyzes a coupling strength between resources, determines an allocation method of individual resources to a plurality of processor cores based on the coupling strength, and performs resource allocation.
When a resource such as an application task, a common function, or a common variable is allocated to a plurality of processor cores, a coupling strength between resources is obtained, and allocation is performed according to the obtained coupling strength between resources. Thereby, more optimal assignment is possible than the user arbitrarily assigns. As a result, application performance can be improved.
[Selection] Figure 4

Description

  The present invention relates to a resource allocation system, and more particularly to a resource allocation system that allocates resources in a static system.

  Conventionally, in a system having a plurality of CPUs (Central Processing Unit) cores such as RTOS (Real-Time Operating System) corresponding to a multiprocessor and a memory, as shown in FIG. The user decides. In FIG. 1, a core 1 and a core 2 are shown as CPU cores.

  At this time, as shown in FIG. 2, the memory holds a source file as a basis of a task arranged in each of a plurality of CPU cores and an RTOS information definition file indicating a task arrangement method determined by a user. is doing.

  For example, in the related art described in Japanese Patent Application Laid-Open No. 2006-003972 (Patent Document 1), memory access between nodes is reduced without consuming computer resources that reduce performance.

  The prior art assumes a ccNUMA (Cache Coherent Non-Uniform Memory Access) architecture having a plurality of CPU cores and memories. ccNUMA is a variation of NUMA (Non-Uniform Memory Access) for multiprocessor computer systems. The NUMA system is composed of a plurality of server building blocks. Each block includes a processor, memory, and input / output components. In the ccNUMA system, the CPU core and the memory are divided in units of nodes. Each process of one or more processes (tasks) included in the program is assigned to the divided node.

  As an example, assume that a process A exists and there is a node 1 that is scheduled to execute the process A. Further, it is assumed that there is a node 2 having the highest number of accesses to the process A.

The prior art has proposed the following three means.
(1) The node 1 and the node 2 in the above example are detected.
(2) It is determined whether the detected node 1 and node 2 are not the same.
(3) If the detected node 1 and node 2 are not the same, the allocation of process A is changed to node 2.

  The prior art is based on the idea of dynamically changing process assignments. However, there are systems that assign processes statically. When assigning processes statically, unlike dynamic, there is no determination index for assigning processes. Since there is no judgment index, the user must understand the configuration of the application (application program) and decide the process allocation. However, when a user who does not know the configuration of the application decides the arrangement, there is a risk of improper arrangement.

  As described above, there are the following two problems when arranging resources in a static system.

(1) Enlargement of the system As the system becomes enormous, the number of tasks used in the user application increases. It is difficult to determine how to allocate resources to the core because the association between tasks is difficult.

(2) Improvement of hardware technology Technological performance and low power consumption have advanced, and the number of multiprocessor cores is currently increasing. In other words, it is difficult to determine which task should be placed in which core.

  Due to the above two problems, it is difficult to determine how to allocate resources to the multiprocessor core.

  As a related technique, Japanese Patent Laid-Open No. 2006-003972 (Patent Document 1) discloses a process placement apparatus, a process placement method, and a process placement program. In this related technique, a process placement apparatus is a method in which each of one or more processes included in a program is executed using a CPU belonging to any node of the ccNUMA architecture and a memory belonging to any node. Applies to This process placement apparatus includes node detection means, node match determination means, and CPU allocation change means. The node detection means detects, for each process, a first node that is a node to which a CPU executing the process belongs and a second node that is a node to which a memory having the highest number of accesses by the CPU within a predetermined time period belongs. . The node match determination means determines whether the first node and the second node match for each process. The CPU allocation changing means changes the CPU executing the process to a CPU belonging to the second node when the first node and the second node do not match for each process.

JP 2006-003972 A

  The present invention relates to the field of multi-processor-compatible RTOS, and analyzes the coupling strength between resources in comparison with a method for statically defining a resource allocation method that has been a problem of the prior art. Based on the above, a method for determining the allocation of individual resources to a plurality of processor cores is determined, and a solution is made by allocating resources.

  The resource allocation system of the present invention once executes an application program and outputs trace information as an operation result, and handles application tasks, common functions, and common variables as resources, and determines the number of data accesses between resources from the trace information. A host PC (personal computer) that calculates and treats the calculated data access count as a coupling strength between resources, and distributes resources to the cores of the multiprocessor according to the coupling strength between resources.

  In the resource allocation method of the present invention, an application program is executed once, and trace information is output as an operation result. Next, application tasks, common functions, and common variables are treated as resources, the number of data accesses between resources is calculated from the trace information, and the calculated number of data accesses is treated as the connection strength between resources. Depending on the strength, resources are allocated to the cores of the multiprocessor.

  The resource allocation program of the present invention executes an application program once, outputs trace information as an operation result, treats application tasks, common functions, and common variables as resources, and counts the number of data accesses between resources from the trace information. A program for causing the computer to execute the step of allocating resources to the cores of the multiprocessor according to the coupling strength between the resources. is there. The resource allocation program of the present invention can be stored in a storage device or a storage medium.

  When allocating resources such as application tasks, common functions, and common variables to a plurality of processor cores, the connection strength between resources is obtained, and allocation is performed according to the obtained connection strength between resources. Thereby, more optimal assignment is possible than the user arbitrarily assigns. As a result, application performance can be improved.

It is a resource allocation diagram in a static system. It is a schematic diagram of a resource arrangement method during application development using RTOS. It is a figure of the Example of this invention. It is a figure of the structure and process flow of this invention. It is a flowchart which shows the flow of a process of this invention. It is a figure of the example of data access frequency analysis between resources. It is a figure of the joint analysis result between resources. It is a figure of description of the division | segmentation algorithm of a resource. It is a figure of description of the division | segmentation algorithm of a resource. It is a figure of description of the division | segmentation algorithm of a resource. It is a figure of description of the division | segmentation algorithm of a resource. It is a figure of reflection of a division result.

  Embodiments of the present invention will be described below with reference to the accompanying drawings.

<Definition of terms>
First, in the present invention, the term “resource” is defined as follows.
-RTOS resource = task-Common resource = Common function and common variable

Moreover, the weight of the bond strength between resources is defined as follows.
・ Binding strength = Number of data accesses from one resource to another

<Overview>
A method of obtaining the bond strength between resources, analyzing the obtained bond strength, and assigning the CPU is the configuration of the present invention. A specific method for determining the bond strength between resources and a method for assigning to CPUs will be described below.

  The reason why the strength of coupling between resources is defined as the number of data accesses is that attention is paid to performance, and overhead that hinders performance is taken into consideration. In a multiprocessor, data access across cores generates overhead. That is, as the number of data accesses across cores increases, the overhead increases. In the present invention, those having a relatively large number of data accesses between resources compared to other resources are arranged in the same core, and the number of data accesses between resources is relatively large compared to between other resources. By placing few things on separate cores, the overhead between cores is reduced. For example, if the average value (or intermediate value) of the number of data accesses between resources is obtained and the number of data accesses between resources is greater than the average value (or intermediate value), these resources are placed in the same core and When the number of data accesses is equal to or less than the average value (or intermediate value), these resources are allocated to different cores. Here, the average value (or intermediate value) is the threshold value. Note that the number of data accesses may be determined using a predetermined number of times as a threshold. Alternatively, a predetermined number of data accesses between resources may be arranged in different cores in ascending order. As described above, the present invention is a method for performing resource allocation by analyzing the number of data accesses between resources in a system that statically determines resource allocation, determining a resource allocation method with less overhead between cores. .

<Example>
Here, as an example, consider a case where a user creates an application as shown in FIG. The configuration of application resources in FIG. 3 is as shown in Table 1 below.

  In the present invention, the resource allocation method described above is not left to the user in a system where resources are statically allocated to multiprocessors.

FIG. 4 shows a series of procedures for determining the allocation of resources to the core.
As shown in FIG. 4, the resource allocation system of the present invention includes a host PC (personal computer) 10 and a debugger 20. The host PC 10 is a multiprocessor-compatible RTOS computer having a plurality of CPU cores and memories. The host PC 10 includes at least a core 1, a core 2, and a memory. The memory holds the source file and execution file of the user application, and the RTOS information definition file. The contents of the executable file are as shown in FIG. The debugger 20 includes a simulator 21. The simulator 21 includes a CPU 22. The CPU 22 executes user applications and RTOS.

  Here, a PC is assumed as an example of the host PC 10 and the debugger 20. In addition, as examples of the host PC 10 and the debugger 20, a computer such as a thin client terminal / server, a workstation, a mainframe, and a supercomputer can be considered. However, actually, it is not limited to these examples.

  The host PC (personal computer) 10 and the debugger 20 can be connected via a network. Examples of networks include the Internet, a LAN (Local Area Network), a wireless LAN (Wireless LAN), a WAN (Wide Area Network), a backbone (Backbone), a cable television (CATV) line, a fixed telephone network, a mobile phone network, WiMAX ( IEEE 802.16a), 3G (3rd Generation), leased line, IrDA (Infrared Data Association), Bluetooth (registered trademark), serial communication line, data bus, and the like can be considered. However, actually, it is not limited to these examples.

  Further, a CPU is assumed as an example of the core 1 and the core 2. Other examples of the core 1 and the core 2 include a microprocessor, a microcontroller, or a semiconductor integrated circuit (Integrated Circuit (IC)) having a similar function. However, actually, it is not limited to these examples.

  Further, as examples of memory, semiconductor storage devices such as RAM (Random Access Memory), ROM (Read Only Memory), EEPROM (Electrically Erasable and Programmable Read Only Memory), flash memory, and HDD (Vard Hard SD) An auxiliary storage device such as State Drive) or a storage medium (media) such as a DVD (Digital Versatile Disk) or a memory card can be considered. However, actually, it is not limited to these examples.

  In FIG. 4, the host PC 10 and the debugger 20 are described as independent devices, but actually, the host PC 10 and the debugger 20 may be the same device.

  FIG. 5 shows a detailed processing flow when determining the allocation of resources to the core.

(1) Step S1
The host PC 10 creates a user application in response to an instruction from the user. Here, the core 1 or the core 2 creates a source file of the user application in accordance with an instruction from the user. At this time, the user does not need to consider the allocation of resources to the core.

(2) Step S2
The host PC 10 creates an execution file. Here, the core 1 or the core 2 creates an execution file based on the source file of the user application. For example, the core 1 or the core 2 converts the source file of the user application into a format that can be executed on a computer by compiling. The host PC 10 provides the executable file to the debugger 20.

(3) Step S3
The debugger 20 operates the user application for a certain period and outputs trace information as an operation result. For example, an operation method incorporating a test pattern expected by the user is also effective as a method for operating the user application. As an operating environment, for example, the target multiprocessor is operated on a simulator assuming a single processor. Here, the debugger 20 downloads an execution file from the host PC 10. The simulator 21 causes the CPU 22 to execute the RTOS and the execution file, operate the user application for a certain period, and output trace information as an operation result. In order to output the trace information, a mechanism for outputting the trace information is required. Therefore, a mechanism for outputting trace information may be incorporated in the RTOS.

(4) Step S4
The host PC 10 refers to the input trace information, analyzes data access between resources, derives the number of data accesses as a coupling strength, and outputs an analysis result. Here, the core 1 or the core 2 calculates the number of data accesses between resources from the trace information. The data access analyzed from the trace information has two points: “state transition from RTOS resource to RTOS resource” and “data access from RTOS resource to common resource”.

(5) Step S5
Based on the analysis result, the host PC 10 determines a resource allocation method to the core, and performs resource allocation according to the determined allocation method. The graph can be divided by using a well-known graph theory. Here, the host PC 10 stores, in a memory, an RTOS information definition file indicating a method for allocating resources to the core. The cores 1 and 2 acquire RTOS resources and common resources based on the RTOS information definition file. Alternatively, a core dedicated to resource allocation (not shown) in the host PC 10 may allocate RTOS resources and common resources to the cores 1 and 2 based on the RTOS information definition file.

FIG. 6 shows an example of a method for analyzing the number of data accesses from the trace information.
In this example, since the state transition is first performed from task 1 to task 2, data access between task 1 and task 2 is “1”. Next, since the data access from the task 2 to the common resource 1 is performed, the data access of the task 2 and the common resource becomes “1”. Similarly, since state transition is performed from task 2 to task 3, data access between task 2 and task 3 is “1”. In this way, the number of data accesses between resources is derived from the trace information operated for a certain period. The obtained data access count is treated as the coupling strength between resources.

  Next, a method for determining a resource allocation method from the obtained number of data accesses will be described below.

  As a result of the data access analysis, the host PC 10 determines a location where the number of data accesses between resources is small, and divides the location. A known technique may be used as an algorithm for dividing. Here, the idea of a known divide-and-conquer method is used as an algorithm for dividing. As a result of the division, the host PC 10 can determine an arrangement method with less data access across cores.

As an example, assume that a data access result as shown in FIG. 7 is obtained.
The value added to the arrow in FIG. 7 represents the number of data accesses, which is the coupling strength between resources. The host PC 10 separates (cuts) the connection between resources by using a division algorithm from this information, and divides it into subsets. After dividing into subsets, the allocation of resources to the core is determined for each subset. Apply the divide and conquer algorithm as a cutting method.

[Divisional governance law]
The procedure of the Divide-and-Conquer Law is as follows.
The host PC 10 takes the average value of all data access times (rounded up after the decimal point) and defines the average value as a threshold value. The host PC 10 cuts the connection between resources whose data access count is less than or equal to the threshold value.

  This will be described with reference to FIGS.

The various arrows in FIG. 7 have the following meanings.
Dotted arrows: coupling between resources Solid arrows: coupling between resources to be cut

Here, the average value of all data accesses is
(1 + 7 + 3 + 8 + 5 + 2 + 10 + 6 + 1 + 2 + 6) /11=4.6.
It becomes. That is, the threshold value is “5”.

  FIG. 8 shows a cut target between resources whose number of data accesses is equal to or less than a threshold value.

  The host PC 10 further performs the following processing on the result obtained by the above-described method.

First, the host PC 10 determines whether or not the following conditions (a) and (b) are met.
(A) The subset is smaller than the number of cores of the multiprocessor.
(B) There are more subsets than the number of cores of the multiprocessor.

  Condition (a) is, for example, a case where only one divided subset exists in a multiprocessor having two cores. For this problem, the host PC 10 increases the threshold value determined by the divide-and-conquer method by 1, and further performs cutting.

  The condition (b) is, for example, a case where a multiprocessor having two cores has three divided subsets. In response to this problem, the host PC 10 restores the portion where the data access frequency of the cut data access is the largest in the subset with the least resources in the subset. By doing so, it is combined with other subsets. When there are a plurality of subsets with the fewest resources, the host PC 10 selects the one with the largest sum of data access (number of data accesses) in the subset.

FIG. 9 shows the result of cutting FIG. Here, there are four subsets.
It can be seen that there is a large number of subsets when trying to arrange on a multi-processor with two cores. In this case, the above condition (b) applies. Therefore, the following procedure is performed.

  In the host PC 10, the task 5 is a subset having the least resources.

  The host PC 10 restores the value having the largest number of data accesses in the task 5 subset. That is, in the subset of task 5, the connection between resources that maximizes the number of data accesses is restored. Here, the host PC 10 restores the combination of task 5 and task 3 as shown in FIG. Black arrows represent the restoration of binding. Now there are three subsets.

  Next, the small subset is a subset of common resource 1 and task 1 or task 6 and common resource 2. The host PC 10 selects the sum of both data accesses because the sum of the subsets of the common resource 1 and the task 1 is larger.

  The host PC 10 restores the value with the largest number of data accesses among the subsets of the common resource 1 and the task 1. That is, in the subset of the common resource 1 and the task 1, the connection between the resources having the maximum number of data accesses is restored. Here, the host PC 10 restores the combination of task 1 and task 6 as shown in FIG. Now there are two subsets.

  Since the host PC 10 was able to divide the subset into two, as shown in FIG. 12, the resources are allocated to each core in units of subsets.

  With the above procedure, the host PC 10 can determine an arrangement method in which a portion where the number of data accesses between resources is small is cut.

  In this embodiment, as a method of cutting a portion having a low bond strength between resources, the divide-and-conquer method using an average value has been described. However, the method is not limited to this method. Various algorithms of the graph partitioning theory can be applied as a method for obtaining a portion having a low coupling strength. For example, the Dijkstra method is known, and this method is also applicable.

  The series of processing in the present invention stores hardware such as a processing device driven by a program, software such as a program for driving the hardware to execute desired processing, and the software and various data. It may be realized by a storage device. For example, when the series of processes in the present invention is a resource allocation method, the resource allocation may be performed by the host PC 10 executing a resource allocation program for causing a computer to execute this resource allocation method. .

<Problem solving mechanism>
Clearly, as the system grows, resources increase. In a system that statically determines the allocation of resources, the user must determine the allocation by determining how the resources should be allocated and whether maximum performance can be derived.

  Also, recent processors tend to increase the number of cores and improve performance. However, if the number of cores increases, it is difficult to make a user's judgment because it is necessary to consider how resources are arranged to provide the best performance, such as dependency between cores.

  As can be seen from the above example, instead of letting the user decide the resource placement, the analysis of the coupling strength between the resources results in the determination of the division decision index, and the placement is determined from that decision measure. Need not be determined by the user.

<Summary>
As described above, the resource allocation system of the present invention derives a determination index used when determining the allocation of resources to the cores of multiprocessors. As a determination method, attention is paid to the number of data accesses between resources.

  In a multiprocessor-compatible RTOS, in a system that statically determines a method for allocating resources to the core, the user determines it, but this is difficult to judge. The cause is an increase in the system and an increase in the number of cores of the processor.

  By using the present invention, a determination index of an arrangement method of RTOS resources (tasks) and common resources (common functions and common variables) that should be determined by the user to the core is derived, and resource allocation is determined from the determination indexes. be able to. First, an application is assembled and the application is operated once without making the user aware of resource allocation. From the operation result, the number of times of data access between resources is derived (as a judgment index), and the result is defined as the coupling strength between resources. The resource allocation method is determined by determining the resource allocation method to the core of the multiprocessor based on the strength of coupling between resources (in the present invention, the number of times of data access).

  As mentioned above, although embodiment of this invention was explained in full detail, actually, it is not restricted to said embodiment, Even if there is a change of the range which does not deviate from the summary of this invention, it is included in this invention.

10 ... Host PC
20 ... Debugger 21 ... Simulator 22 ... CPU

Claims (16)

A debugger that once executes an application program and outputs trace information as an operation result;
The task, common function, and common variable of the application are treated as resources, the number of data accesses between resources is calculated from the trace information, the calculated number of data accesses is treated as the coupling strength between resources, and the coupling strength between resources And a host PC for allocating resources to the cores of the multiprocessor according to the resource allocation system. The resource allocation system according to claim 1,
The host PC places each resource whose number of data accesses between resources is greater than a threshold value in the same core, and places each resource whose number of data accesses between resources is less than or equal to the threshold value in a separate core. Resource allocation system that suppresses overhead between cores due to increase in the number of cores. The resource allocation system according to claim 2, wherein
The host PC calculates the average value of all data access times, separates the connections between resources whose data access times are less than the average value, and divides them into subsets, and allocates resources to the cores of multiprocessors for each subset. Do resource allocation system. The resource allocation system according to claim 3, wherein
The host PC restores the connection between resources having the largest number of data accesses in the subset in order from the subset with the least resources. The resource allocation system according to any one of claims 1 to 4,
The host PC treats tasks as RTOS (Real-Time Operating System) resources, treats common functions and variables as common resources, and makes state transition from RTOS resources to RTOS resources and common to RTOS resources from the trace information. A resource allocation system that analyzes data access to resources and calculates the number of data accesses between resources.   A computer used as at least one of a debugger and a host PC in the resource allocation system according to any one of claims 1 to 5. Once the application program is executed and trace information is output as the operation result,
The application task, common function, and common variable are treated as resources, the number of data accesses between resources is calculated from the trace information, the calculated number of data accesses is treated as the connection strength between resources, and the resources are combined Allocating resources to the cores of the multiprocessor according to the strength. The resource allocation method according to claim 7,
Each resource whose number of data accesses between resources is greater than the threshold is placed in the same core, and each resource whose number of data accesses between resources is less than or equal to the threshold is placed in a separate core. A resource allocation method further comprising suppressing the occurrence of overhead. The resource allocation method according to claim 8,
Calculating an average value of all data access times, separating connections between resources whose data access times are less than the average value and dividing them into subsets, and further allocating resources to the multiprocessor cores for each subset Includes resource allocation methods. The resource allocation method according to claim 9, wherein
A resource allocation method further comprising restoring a connection between resources having the largest number of data accesses in the subset in order from the subset having the least resources. The resource allocation method according to any one of claims 7 to 10,
Tasks are treated as RTOS (Real-Time Operating System) resources, common functions and variables are treated as common resources, state transition from RTOS resources to RTOS resources, and data access from RTOS resources to common resources And calculating the number of data accesses between resources. A step of executing an application program once and outputting trace information as an operation result;
The application task, common function, and common variable are treated as resources, the number of data accesses between resources is calculated from the trace information, the calculated number of data accesses is treated as the connection strength between resources, and the resources are combined A resource allocation program for causing a computer to execute a step of allocating resources to cores of a multiprocessor according to strength. A resource allocation program according to claim 12, wherein
Each resource whose number of data accesses between resources is greater than the threshold is placed in the same core, and each resource whose number of data accesses between resources is less than or equal to the threshold is placed in a separate core. A resource allocation program for causing a computer to further execute a step of suppressing the occurrence of overhead. A program for resource allocation according to claim 13,
Calculating the average value of all data access times, separating the connection between resources whose data access times are less than the average value and dividing them into subsets, and further allocating resources to the multiprocessor cores for each subset A resource allocation program to be executed by a computer. A resource allocation program according to claim 14, wherein
A resource allocation program for causing a computer to further execute a step of restoring a connection between resources having the largest number of data accesses in the subset in order from a subset having the least resources. The resource allocation program according to any one of claims 12 to 15,
Tasks are treated as RTOS (Real-Time Operating System) resources, common functions and variables are treated as common resources, state transition from RTOS resources to RTOS resources, and data access from RTOS resources to common resources And a resource allocation program for causing a computer to further execute a step of calculating the number of data accesses between resources.

Images