JP2008015668A - Task management device - Google Patents

Abstract

A technique capable of reducing cache miss hits and speeding up memory access is provided.
In a task management device, task execution control is performed using a task management table that stores the execution start time of each task and the storage location (start address and size) on the main memory. Based on the task management table, a prefetch unit that prefetches the instruction code constituting the task before the start of the task execution is provided, so that when a new task enters the execution state, the instruction code of the task is cached. Since it is taken in the memory, cache miss hits can be reduced.
[Selection] Figure 5

Description

  The present invention relates to a task management device.

  In general, in an information processing apparatus, an instruction code and data stored in a main memory such as a RAM are read, and a CPU (central processing unit) interprets the instruction code and executes processing on the read data. . Access from the CPU to the main memory is much slower than the instruction execution speed of the CPU. Therefore, when the CPU reads an instruction code and data (here, simply referred to as data without distinguishing both) from the main memory each time, the CPU enters a waiting state during memory access, and the processing speed does not improve. Therefore, it is common to provide a cache memory between the CPU and the main memory. As the cache memory, a memory that can be accessed at a higher speed than the main memory is used. By temporarily storing frequently used data in a cache memory that can be accessed at high speed, the CPU can read data from the cache memory without accessing the low-speed main memory, thereby improving the processing speed. .

  Conversely, when accessing data that has not been read into the cache memory, that is, when a cache miss occurs, the processing speed is slowed down because the main memory must be accessed. By avoiding such a cache miss hit, the memory access speed is increased and the processing speed is improved.

  If the CPU knows in advance what data it needs next, it can avoid cache misses by fetching the data into the cache memory. In this manner, processing for fetching necessary data in the cache memory in advance is called pre-fetch.

  Although prefetch enables high-speed data access, generally the next required data is not surely known. Therefore, data that is likely to be required next is prefetched for the time being. However, a high-speed accessible memory used as a cache memory is expensive and has a smaller capacity than the main memory. Therefore, if unnecessary prefetching is performed, there is a case where really necessary data is evicted from the cache memory. In other words, in order to effectively use the cache memory, it is important to predict the next necessary data and prefetch only the necessary data.

As such a technique, Patent Document 1 discloses a technique for prefetching data (instruction code and data) corresponding to a task waiting for execution from the main memory before the task transitions to the executing state. ing. Patent Document 2 discloses a real-time control system that guarantees that the replacement of the cache is completed before the switching of the control mode in the interrupt process.
JP 2002-259209 A JP 2005-44231 A

  An object of the present invention is to provide a technique capable of reducing cache miss hits and speeding up memory access.

  In order to achieve the above object, in the present invention, the following means or processing is used to manage tasks and prefetch instruction codes constituting the tasks.

  The task management device according to the present invention has a main memory and a cache memory as hardware. The cache memory is a memory that can be accessed faster than the main memory. By storing the instruction code stored in the main memory in the cache memory, the instruction code can be accessed at high speed.

  The task management apparatus according to the present invention further includes a task management table, task management means, and prefetch means.

  The task management table stores the execution start time of each task and the storage location of the instruction code constituting each task in the main memory for a plurality of tasks scheduled to be executed. The storage location of the instruction code is preferably stored in the task management table as the start address and code size (capacity) of the storage location.

  The task management means controls task execution according to the task execution start time stored in the task management table. That is, when the execution start time of a certain task comes, the task management means interrupts the execution of the task that has been executed so far and executes a new task. Thus, the task management means controls the execution of a plurality of tasks according to the schedule stored in the task management table.

  The prefetch means fetches the instruction code from the main memory into the cache memory in advance (prefetch) based on the storage position of the instruction code of the task stored in the task management table for the task scheduled to be executed. It is preferable that the prefetch means prefetches all instruction codes constituting the task with respect to the task to be executed.

  As described above, according to the task management device of the present invention, for a task to be executed in the future, the instruction code of the task is prefetched into the cache memory, so that cache misses can be reduced. Therefore, according to the task management device of the present invention, the memory access is speeded up and the processing efficiency is improved.

  Here, the prefetch means may prefetch the instruction code of the task to be newly executed when the task management means switches the task to be executed.

  The prefetch means may prefetch the instruction code of a task to be executed after the task when the task management means switches the task to be executed.

  Further, the instruction code that the prefetch means prefetches at a time need not be the instruction code of one task. That is, the prefetch means may prefetch the instruction codes of a plurality of tasks to be executed in the future when the task management means switches the tasks to be executed. In this case, it is preferable that the number of tasks to be prefetched collectively is determined based on the sum of the instruction code sizes constituting the tasks and the capacity of the cache memory.

The task management apparatus according to the present invention may be configured as a multiprocessor system or a multicore system. In this case, it is preferable that one processor or processor core is assigned to the execution of the task management means and the prefetch means, and another processor or processor core is assigned to the execution of the task. As described above, in the multiprocessor system or the multi-core system, the task management unit and the prefetch unit and the task can operate in parallel, so that the task management unit and the prefetch unit can be always executed. Therefore, it is possible to minimize the cache miss hit related to the instruction code of the task.

  Note that the cache memory of the task management apparatus according to the present invention can be configured as a multi-level cache memory. In this case, fetching the instruction code into the cache memory (prefetching) means fetching the instruction code into at least one of the multi-level cache memories.

  The present invention can be understood as a task management device having at least a part of the above means. The present invention can also be understood as a task management method including at least a part of the above processing, or a program for realizing the method. Each of the above means and processes can be combined with each other as much as possible to constitute the present invention.

  For example, a task management method as one aspect of the present invention is a task management method performed by an information processing apparatus having a main memory and a cache memory, and for a plurality of tasks scheduled to be executed, A step of storing a storage position of an instruction code constituting a task in the main memory in a task management table; a step of controlling execution of the task according to a task execution start time stored in the task management table; And fetching the instruction code from the main memory into the cache memory in advance based on the storage position of the instruction code of the task stored in the task management table.

  In addition, the task management program as one aspect of the present invention is directed to an information processing apparatus having a main memory and a cache memory. The step of storing the storage location of the code in the main memory in a task management table, the step of controlling the execution of the task according to the execution start time of the task stored in the task management table, and the task scheduled to be executed, Based on the storage location of the instruction code of the task stored in the task management table, a step of prefetching the instruction code from the main memory into the cache memory is executed.

  According to the present invention, it is possible to reduce cache miss hits and increase memory access speed.

  Exemplary embodiments of the present invention will be described in detail below with reference to the drawings.

<Configuration>
FIG. 1 is a diagram illustrating a hardware configuration of a task management apparatus according to the present embodiment. The task management device 1 includes a CPU (central processing unit) 2, a main memory 3 such as a RAM, an auxiliary storage device 4 such as a hard disk device, an input device 5 such as a keyboard and a mouse, and an output device 6 such as a display. Each of these devices is connected by a bus 7.

  FIG. 2 is a diagram showing a more detailed configuration of the CPU 2. The CPU 2 includes a processor core 21 that interprets an instruction code and executes processing, and a cache memory 22.

  Regarding the access speed to the cache memory 22 and the main memory 3, the access speed to the cache memory 22 is faster than the access speed to the main memory 3. Conversely, the memory capacity of the main memory 3 is larger than the memory capacity of the cache memory 22.

  When reading the instruction code from the main memory 3, the CPU 2 determines whether the instruction code has already been taken into the cache memory 22, and reads the instruction code from the cache memory 22 if it has already been taken in. On the other hand, when the instruction code is not taken into the cache memory 22, the instruction code is read from the main memory 3 and taken into the cache memory 22. In this way, the high-speed cache memory is used to reduce access to the main memory 3 and reduce the processing time required for memory access.

  Next, functional units of the task management device 1 according to the present embodiment will be described. FIG. 3 is a diagram showing functional blocks of the task management device 1 according to the present embodiment. The task management apparatus 1 includes a task scheduler 101, a task management table 102, a prefetch unit 103, and a plurality of tasks 104. The task scheduler 101 controls which task the CPU 2 executes according to the task management table 102.

The task management apparatus 1 according to the present embodiment may perform task scheduling according to any specific scheduling algorithm. For example, as a scheduling algorithm, a DM method (Deadline Monotonic) that preferentially executes a task having a short time from task activation to deadline in a periodic task can be used. In addition, as a scheduling algorithm, an RM method (Rate Monotonic) in which a task with a shorter task execution cycle is preferentially executed in a periodic task can be used. Further, as a scheduling algorithm, an EDF method (Earliest Deadline First) that is executed preferentially from the task with the closest deadline can be used. Any other scheduling algorithm may be used. In either case, the task scheduler 101 controls task execution according to the task management table 102.

  FIG. 4A shows a table structure of the task management table 102. The task management table 102 includes a task ID 41, an execution start time 42 of the task to be executed, a start address 43 of a storage location of the instruction code constituting the task in the main memory 3, and a code size 44 of the instruction code constituting the task. Is stored. That is, the task management table stores, for each task, when to execute the task and the storage location of the instruction code constituting the task in the main memory 3.

  FIG. 4B is a diagram illustrating task scheduling according to the task management table of FIG. As shown in FIG. 4B, according to the task management table of FIG. 4A, task A is executed at time t1, task B at time t2, task A at time t3, task A at time t4. C executes task B at time t5.

  The prefetch unit 103 executes a prefetch instruction and performs a process of fetching an instruction code stored in the main memory 3 into the cache memory 22. In accordance with an instruction from the task scheduler 101, the prefetch unit 103 performs processing for fetching an instruction code constituting the task 104 scheduled to be executed from the main memory 3 into the cache memory 22. Specific processing will be described later.

  The functions of the task scheduler 101 and the prefetch unit 103 are realized when a program stored in the auxiliary storage device 4 is loaded into the main memory 3 and executed by the CPU 2. The task management table 102 is constructed (stored) on the main memory 3. Since the task management table 102 is data stored on the main memory 3, the task management table 102 may be captured on the cache memory 22. The task 104 is a program that is loaded from the auxiliary storage device 4 to the main memory 3 and is executed by the CPU 2 itself.

<Processing flow>
The process illustrated in FIG. 5 is a process performed by the task scheduler 101 and the prefetch unit 103. This processing routine is periodically executed at predetermined intervals. First, when the task scheduler 101 enters an execution state, it is determined whether or not a task to be executed has been switched based on the task management table 102 (S10). That is, it is determined whether or not there is a task whose execution start time 42 stored in the task management table 102 has arrived. If task switching has not occurred (S10-NO), the process routine is exited. When task switching occurs (S10-YES), the prefetch unit 103 determines a task to be prefetched (S11).

  The following method can be considered as a method for the prefetch unit 103 to determine a task to be prefetched.

  1. In this routine, the task to be executed by the task scheduler is prefetched. According to this method, the instruction code of the task to be executed next is stored in the cache memory 22, whereby the instruction code of the task to be executed can be acquired from the cache memory 22.

  2. In this routine, a task to be executed is prefetched after a task to be executed by the task scheduler. In this case, a task to be executed next to a task to be executed this time may be a prefetch target, and a task to be executed after a predetermined number of times may be a prefetch target. Since the order of tasks to be executed is stored in the task management table 102, the prefetch unit 103 can determine a task to be executed after a predetermined number of times by referring to the task management table 102.

  According to this method, even if it takes a long time to prefetch the instruction code, prefetching is performed before the task actually enters the execution state. Therefore, when the task enters the execution state, the instruction of the task The code is stored in the cache memory.

  3. A task executed during a predetermined time zone after the current time, that is, a task that starts after T1 seconds after the current time and starts before T2 seconds may be prefetched. it can. Since the start time of each task is stored in the task management table 102, the prefetch unit 103 can determine a task to be executed in a predetermined time zone by referring to the task management table 102.

  By this method, the same effect as the method 2 can be obtained. In addition, since the task to be prefetched is determined based on the time when the task is in the execution state, it is possible to control to fetch the cache memory 22 more reliably until the execution of the task is started.

4). A plurality of tasks to be executed in the future may be prefetched. In this case, the number of tasks to be prefetched is selected so that the total number of instruction codes constituting the task is within a predetermined threshold. The predetermined threshold needs to be within the size of the cache memory 22. When both the instruction code and data are taken into the cache memory 22, it is not preferable to satisfy all of the instruction code and data with the instruction code. Therefore, it is preferable to use a predetermined capacity of the cache memory 22 as a threshold value.

Specifically, the task to be executed in the current routine is T ₀ , the task to be executed n times after that is T _n , the instruction code size of task T _i is S (T _i ), Assuming that the threshold is S, the maximum N satisfying the following Equation 1 can be obtained, and T _{0 to} T _N can be set as prefetch targets.

In addition, although tasks after T ₀ are prefetched here, k may be a predetermined integer and T _{k to} T _N may be prefetched (N is obtained in the same manner as described above).

  Also by this method, the instruction code constituting the task scheduled to be executed in the future is surely taken into the cache memory 22. In this method, many instruction codes are prefetched into the cache memory 22, but even if a prefetch instruction is issued for an instruction code already fetched in the cache memory 22, it is ignored. Will not be inefficient.

  The prefetch unit 103 determines a task to be prefetched by any of the methods described above. Next, the prefetch unit 103 issues a prefetch instruction for fetching the instruction code constituting the task to be prefetched into the cache memory 22 (S12). Since the task management table 102 stores the storage location of each task in the main memory 3, that is, the start address and the code size, the prefetch unit 103 refers to the task management table 102 to determine which memory in the main memory 3. It can be determined whether the region should be prefetched.

  Finally, the task scheduler 101 switches the task to be executed (S13). Here, since the instruction code of the task to be executed is already prefetched into the cache memory 22 by the prefetch unit 103, the CPU can access the instruction code of the task to be switched at high speed.

<Effect of embodiment>
According to the task management device according to the present embodiment, it is possible to prefetch the instruction code constituting the task into the cache memory before the task enters the execution state. Therefore, cache miss hits can be avoided, and execution delays due to memory access during task switching can be reduced.

  In addition, since the instruction code to be prefetched is determined based on the task management table that manages the task execution order, a situation in which prefetching is not actually read into the CPU does not occur, and efficient prefetching is performed. be able to.

In addition, since the task scheduler 101 and the prefetch unit 103 determine which instruction code is prefetched at which timing, the program creator explicitly writes a processing code related to cache control in the (task) program. This is unnecessary, and the burden on the program creator can be reduced.

<Modification 1>
Although the CPU 2 in this embodiment has only one level of cache memory 22, the CPU 1 may have multiple levels of cache memory. In this case, the prefetch unit 103 performs control for the purpose of prefetching the instruction code up to the cache memory of a specific hierarchy. For example, in the case of a two-level cache configuration of the L1 cache and the L2 cache, the prefetch unit 103 may prefetch the instruction code up to the L1 cache or only prefetch up to the L2 cache. The same applies to a cache configuration with three or more layers.

<Modification 2>
In the present embodiment, the task management apparatus 1 has only one CPU 2, but may be configured as a multiprocessor system having a plurality of CPUs. In this case, it is preferable that the plurality of CPUs share the cache memory installed outside the CPU. A specific configuration is shown in FIG. In FIG. 6, the CPU 201 and the CPU 202 share the external cache 203. The CPU 201 and the CPU 202 have a cache memory therein, but the prefetch unit 103 issues an instruction for prefetching an instruction code to the external cache 203. As a result, the instruction code prefetched by the CPU 201 can also be used by the CPU 202. Note that the number of CPUs does not have to be two and may be three or more.

  Further, the task management apparatus 1 may be configured as a multi-core system. That is, the CPU 2 may be configured to have a plurality of processor cores. Various forms are conceivable for the multi-core system, an example of which is shown in FIG. As shown in FIG. 7, the CPU 2 has two processor cores 21 a and 21 b in one package, and each shares a cache memory 22. Note that the number of processor cores is not necessarily two, and may be three or more.

  When the task management device 1 is configured as a multiprocessor system or a multicore system, it is preferable that a certain processor or processor core is assigned exclusively for executing the task scheduler 101 and the prefetch unit 103. According to this configuration, it is possible to always start the task scheduler 101 and the prefetch unit 103, so that the instruction code can be prefetched without delay, and cache miss hits regarding the instruction code are minimized. Is possible.

<Modification 3>
In this embodiment, the functions of the task scheduler 101 and the prefetch unit 103 are realized by the CPU 2 executing a program, but the task scheduler 101 and the prefetch unit 103 may be configured as dedicated chips. Also in this case, the prefetch unit 103 prefetches an instruction code constituting the task to the cache memory 22 connected to the CPU 2 that executes the task.

It is a figure which shows the hardware constitutions of the task management apparatus which concerns on this embodiment. It is a figure which shows the structure of CPU in this embodiment. It is a figure which shows the functional block of the task management apparatus which concerns on this embodiment. It is a figure which shows the table structure of the task management table in this embodiment. It is a flowchart which shows the flow of a process of the task management apparatus which concerns on this embodiment. It is a figure explaining a multiprocessor system. It is a figure explaining a multi-core system.

Explanation of symbols

1 Task management device 2 CPU
3 Main memory 4 Auxiliary storage device 5 Input device 6 Output device 7 Bus 21 Processor core 22 Cache memory

Claims (9)

A task management device having a main memory and a cache memory,
For a plurality of tasks scheduled to be executed, a task management table that stores the execution start time of each task and the storage location of the instruction code constituting the task in the main memory;
Task management means for controlling task execution according to the task execution start time stored in the task management table;
Prefetch means for pre-fetching the instruction code from the main memory into the cache memory based on the storage position of the instruction code of the task stored in the task management table for the task to be executed;
A task management device comprising: The task management apparatus according to claim 1, wherein a storage location of the instruction code stored in the task management table in the main memory is stored as a start address and a size of the instruction code. 3. The task according to claim 1, wherein the prefetch unit fetches an instruction code of a task to be newly executed from the main memory into the cache memory when the task management unit switches execution tasks. 4. Management device. The prefetch means fetches an instruction code of a task to be executed after a newly executed task from the main memory into the cache memory when the task management means switches execution tasks. 2. The task management device according to 2. The said prefetch means fetches the instruction codes of a plurality of tasks to be executed in the future from the main memory into the cache memory when the task management means switches execution tasks. Task management device. The task management device has at least first and second processors,
The task management means and the prefetch means are executed by the first processor,
The task is executed by the second processor. The task management device according to claim 1, wherein the task is executed by the second processor. The task management device has a processor including at least first and second processor cores,
The task management means and the prefetch means are executed by the first processor core,
The task is executed by the second processor core. The task management device according to claim 1, wherein the task is executed by the second processor core. A task management method performed by an information processing apparatus having a main memory and a cache memory,
For a plurality of tasks scheduled to be executed, storing in the task management table the execution start time of each task and the storage location of the instruction code constituting the task in the main memory;
Controlling the execution of the task according to the execution start time of the task stored in the task management table;
Pre-fetching the instruction code from the main memory into the cache memory based on the storage position of the instruction code of the task stored in the task management table for the task to be executed;
A task management method comprising: For an information processing apparatus having a main memory and a cache memory,
For a plurality of tasks scheduled to be executed, storing in the task management table the execution start time of each task and the storage location of the instruction code constituting the task in the main memory;
Controlling the execution of the task according to the execution start time of the task stored in the task management table;
Pre-fetching the instruction code from the main memory into the cache memory based on the storage position of the instruction code of the task stored in the task management table for the task to be executed;
A task management program characterized by causing

Images