JP2006039824A - Method for controlling multiprocessor-mounted system LSI - Google Patents

Abstract

PROBLEM TO BE SOLVED To generalize and optimize multitask control of a multiprocessor.
A hardware configuration includes a processor group having a data cache inside a system LSI and a large-capacity external shared memory.
A plurality of task combination candidates are generated, and the same task is duplicated and executed speculatively by many processors. By adopting the result of the combination of the processor and task that avoids the penalty as the penalty between communication between processors, the consistency of the entire system between the data cache and shared memory is achieved while using the most efficient processing procedure. Take.
[Selection] Figure 1

Description

  The present invention relates to an LSI configuration method called a system LSI or system-on-chip (SOC), which includes a plurality of CPUs, that is, multiprocessors, and is incorporated in one LSI together with a dedicated hardware circuit. It is related with the method of performing what is called multitasking which performs different programs simultaneously and independently, and communicates and controls between programs.

  In recent years, with the advancement of semiconductor manufacturing processes and integration, LSIs called so-called system LSIs or system-on-chip (SOC), which are configured by incorporating a CPU with a dedicated hardware circuit into a single LSI, are used extensively. It has come to be. Furthermore, with the increase in the degree of integration of semiconductors, it is relatively easy to mount a plurality of CPUs in terms of the area occupied by a CPU in an LSI, and a multi-CPU including a plurality of CPUs is mounted to improve performance. The SOC by the processor is gradually being used. In the future, due to further improvements in the degree of integration of semiconductors, the impact on the price of LSI will be more limited by the number of pins connected to the outside, and mounting of a very large number of CPUs, such as tens to hundreds, From the viewpoint of area, it is expected that an era will be possible on the SOC at a very low cost.

  On the other hand, software used in digital devices has become relatively complex, and an operating system (OS) that can be used in so-called multitasking that executes programs simultaneously and independently and communicates and controls between programs is provided. Use is increasing.

On the other hand, it is considered difficult to continue to increase the operating frequency at a conventional pace from the viewpoint of the physical properties of semiconductors, power consumption, and heat generation. In the past, application software by multiprocessors and multitasking OS for multiprocessors have been developed and used for high-speed processing. Thousands of processors are used for large-scale parallel numerical calculations, or two. A multitasking multitasking OS using four processors is used.
JP-A-3-21656

  However, the conventional method has the following problems.

  1) Application software with a large number of multiprocessors is effective in cases where specific parallel operations can be performed, for example, image processing, numerical calculations for solving field equations, etc., but control system processing that cannot be easily divided in parallel However, it is difficult to automatically parallelize algorithms. For example, the dependency of individual tasks in a multitasking application is different for each specific application. There is no general solution for generating parallel algorithms in such control system processing, and automation is difficult.

  2) When using a shared memory that simultaneously accesses memory in one area by a multiprocessor, the bus traffic to the shared memory increases and the access speed decreases as the number of processors increases. For this reason, it is necessary to increase the speed by using a copy to a local high-speed memory that can be accessed for each processor such as a cache mechanism. In this case, the consistency between the cache and the shared memory for each processor must be taken. Becomes difficult. Although it is possible to arrange only the distributed memory close to each processor, in this case, it is difficult to exchange data between the distributed memories, and the consistency of the contents of the distributed memory should be ensured in a general control algorithm. Is difficult.

  3) It is difficult to select an appropriate method for improving the data processing efficiency of the entire system when a plurality of tasks are assigned to a plurality of processors.

  As an example, when tasks Ta, Tb, and Tc are operated by processors Px and Py, a certain task Ta is assigned to one processor and Px: (Ta), Py: (Tb, Tc) In addition, there is a method in which a plurality of tasks Ta and Tb are assigned to one processor and Px: (Ta, Tb) and Py: (Tc) are set. Here, with respect to the task Ta, the task Ta clearly operates at a high speed from the viewpoint that the former method has no task transition in the processor and does not require register data exchange (context switch) in the processor. On the other hand, when operations are performed by communicating messages between tasks Ta and Tb, communication must be performed between different processors, and when the overhead for that is large, the former method is speedy. Will be a factor to decrease. The synchronization overhead between processors varies depending on the hardware system configuration such as multiprocessor and memory and the control configuration of the multitasking software program. As a result, the configuration of complex tasks and processors In this case, it can be said that it is a case-by-case whether the former method or the latter method can process data more efficiently. As described above, it is difficult to select a method for assigning tasks to multiprocessors.

  In such an environment that can solve the above problems and can use a huge number of processors at low cost, the data transfer speed to the shared memory does not become a bottleneck, and the consistency of the data in a large number of distributed memories is achieved. The architecture and algorithm to execute this software at high speed were desired.

  In order to solve the above-mentioned problems, the present invention has the following configuration.

  A multiprocessor, a data cache memory and an instruction cache memory connected to each processor P1, P2, P3,..., A bus connected in a shared manner so as to be accessible from all processors, and externally through the bus A system LSI having at least an internal memory controller to which a shared memory can be connected. The above processor is a processor having means for allowing the user to control the timing of delayed writing and refilling of the data cache, and performs multitasking. , Means for preparing a plurality of types of allocation methods to the processors T1, T2, T3,... As allocation method tables D1, D2, D3,. Assigned to the same task Is used for processing of a distribution method that is executed on a plurality of processors, a method for detecting the progress of transition between tasks for each distribution method, and a distribution method that is most advanced based on the detection unit. A multitask control method for a multiprocessor-mounted system LSI, comprising means for writing back the contents of a distributed memory of a processor to the shared memory.

  As described above, according to the present invention, when assigning a multitask to a multiprocessor, a plurality of distribution method candidates are increased and applied to the processor, and the most efficient task assignment result is left. Thus, the following effects can be obtained.

  1) Multitask allocation scheduling to multiprocessors that are difficult to predict is optimized.

  2) Since the subsequent optimal allocation is not predicted by taking a history (log), the dynamic optimal allocation at that moment is made even for state transitions that are difficult to reproducibly and statistically difficult to predict.

  3) Even if the number of processors increases or the number of tasks increases, it can be scalable with the same algorithm.

  This is particularly effective when using a system LSI that requires a small number of package pins even if the number of processors is enormous. For example, even if a large number of processors are arranged so that the number of processors is sufficiently larger than the number of tasks, the number of processors This is particularly effective when using a configuration with a high degree of integration that does not significantly affect the cost, or when using a small processor core.

<Embodiment 1>
Hereinafter, the principle of the present invention will be described with reference to an example of a preferred embodiment of the present invention. In the following, embodiments based on the principle of the present invention are illustrated and described for the purpose of facilitating understanding, and the scope of the present invention is not necessarily limited by the details of the embodiments.

  FIG. 1 is a diagram showing the basic concept of the present invention.

  FIG. 1A shows the hardware configuration of a system LSI, and FIG. 1B shows a control method showing how multitasks are allocated on the multiprocessor.

  As shown in FIG. 1A, high-speed distributed memories M1, M2, M3,... And processors P1, P2, P3,. Yes. A shared memory 200 is connected to the bus 100 via a memory controller (not shown). An arbitration processor 500 receives and controls a signal from each processor Pn. A DMA controller 400 can perform data transfer between the shared memory and the high-speed distributed memory. Reference numeral 300 denotes a part constituted by a system LSI. On the other hand, T1, T2, T3,... Are prepared as tasks that are software programs executed on the processor. FIG. 1 (b) shows a part of it.

  Each processor is equipped with a data cache D $ and an instruction cache I $. The data cache D $ has a delayed write (write back) function, and in the present invention, as an instruction set that can be used by the user, the data cache D $ holds a write-back stop state with respect to the data cache, and a store instruction cache miss line When all of the above are valid, the cache write-back and refill are stopped, and a notification signal is issued outside the processor in a wait state.

  Here, an example in which there are seven or more processors and three tasks T1, T2, and T3 will be described. First, there are the following possibilities for task distribution. This is shown below as distribution method tables D1 to D5. Here, (task...) Indicates a task assigned to one processor. For example, (T1, T2) indicates that tasks T1 and T2 are assigned to one processor. Further, {(task...)...} Indicates a method of assigning all tasks to the processors by the above assignment.

  For example, D2 = {(T1, T2), (T3)} assigns tasks T1 and T2 to one processor, and all tasks are executed by assigning a task T3 to another processor. D2 is shown.

D1 = {(T1), (T2), (T3)}
D2 = {(T1, T2), (T3)}
D3 = {(T2, T3), (T1)}
D4 = {(T3, T1), (T2)}
D5 = {(T1, T2, T3)}
In this example, a task Tn is assigned to the processor Pn as follows, for example.

P1: (T1)
P2: (T2)
P3: (T3)
P4: (T1, T2)
P5: (T2, T3)
P6: (T3, T1)
P7: (T1, T2, T3)
As described above, the same task is assigned to a plurality of processors.

  Therefore, the processors are assigned to the distribution method table Dn as follows.

D1 = {P1, P2, P3}
D2 = {P4, P3}
D3 = {P5, P1}
D4 = {P6, P2}
D5 = {P7}
Here, as described above, the same processor Pn is assigned to different distribution method tables Dn. For example, the processor P1 is commonly used in the distribution method tables D1 and D3, and therefore, the required number of processors is smaller than the total number of processors required for each distribution method table.

  First, as a processing start sequence, the data cache of each processor sets all the cache lines as data invalid. When the operation of the processor is started, a processor to which two or more tasks are assigned among the processors repeats a transition between assigned tasks by the kernel being switched by a timer interrupt (not shown).

  While this state continues, each processor notifies the arbitration processor when the appropriate task patrol stop condition is satisfied, and stops its operation. Here, an appropriate task cyclic stop condition is, for example, a case where a message from a task other than the task operating in the current processor is requested.

  The operation at this time will be described with an example in which tasks T1 and T2 are assigned to the processor P4. Since the OS of the processor P4 knows that the tasks assigned to it are T1 and T2 at the start of execution, when it is determined that the message requested by the task T1 is obtained from the task T3, P4 passes through the OS. Notify the arbitration processor of the stop state and stop.

  In this way, each processor informs the arbitration processor and stops when information from a task other than the task operating inside itself becomes necessary. In this way, the processor stops one after another.

In addition, another stop condition is as follows. In the initial state, all cache lines of each processor's data cache are invalid (invalid), so each line is filled with data valid (valid) by read / write, but the cache write-back is stopped. ing. After all the data cache lines are filled with valid data, the cache line continues to operate until all lines are dirty, that is, all the cache lines are written from the processor. When a miss occurs, the processor stops without performing write back refill, and notifies the arbitration processor of the stop state. (The operation continues in the case of overwriting the dirty line again due to a data cache hit, or replacing a line when there is a cache line that is not dirty even if the data is valid.)
In this way, when it becomes necessary to write back the data cache contents to the shared memory, the arbitration processor is notified of the processor number in which all the data caches are dirty lines, and all the processors are stopped.

  Here, as described in the problem to be solved by the invention of the preceding paragraph, the data processing amount of each task until the stop is the highest data processing efficiency without task transition when one task is assigned to one processor. Note that is not necessarily expensive. This is because in this configuration, messages between tasks are held in the high-speed cache, and if the messages in the high-speed cache can be exchanged between tasks operating in one processor, they operate between different processors. This is because processing may be more efficient than message communication between tasks.

  For example, it is assumed that the processor Pn and the task Tn are assigned as follows.

P1: (T1)
P2: (T2)
P4: (T1, T2)
At this time, although P1 and P2 are high-speed when there is no task transition, the caches directly connected to the processors are different. Therefore, when message communication occurs between the tasks, data synchronization between different processors and caches is performed. Processing time. Furthermore, when the number of processors is enormous and the communication mechanism between tasks is complicated, it is complicated to synchronize the caches. On the other hand, in P4, there are a plurality of tasks and task transitions occur. However, regarding the communication between tasks in this processor, the data consistency is ensured in the same cache, so the processing time required for data synchronization is not necessary. . Therefore, it can be said that which combination is more efficient is more case-by-case than the operation being executed.

  Here, the arbitration processor invalidates the table including the stopped processor every time the processor stops in the distribution method table Dn. Thus, the task group operating on the table processor that survives to the end and the cache contents are validated. In other words, the data regarding the task control in the cache that has survived as valid is valid at this time. After that, when the processor stops, the valid contents of the cache are written back to the shared memory. When a plurality of tables are valid at the time of stopping, an arbitrary method, preferably a sorting table with a small number of processors may be selected.

On the other hand, as described above, when all the data caches of a certain processor become dirty lines and all the processors are stopped, the distribution method table including the processors whose caches are all dirty lines is validated. For example, when all of the data caches of the processor P3 become dirty lines and are notified to the arbitrating processor and all the processors are stopped, the distribution method tables D1 and D2
D1 = {P1, P2, P3}
D2 = {P4, P3}
Since the processor P3 is included, the data cache of the processor D1 or D2 is written back to the shared memory. Here, as an example, the data of the processors P4 and P3 in the distribution method table D2 is written back.

  Thereafter, the process is returned to the process start sequence again, all the cache lines are set as data invalid, and the same process is repeated.

At this time, the cache data in the plurality of surviving processors is written to the shared memory. In this case, the consistency of the data caches of the plurality of processors is as follows. For example, regarding processor Pn and task Tn,
P3: (T3)
P4: (T1, T2)
Is valid until the end,
The data caches of P3 and P4 are written back to the shared memory. At this time, if the cache line points to the same address, there will be a plurality of data to be written to the shared memory by the cache, the exclusive control is not performed, and a contradiction occurs. However, when such a phenomenon occurs, the communication procedure is ignored without permission between independent tasks (in the above example, between (T1, T2) and (T3)), and data is transferred to the common address. It is an access that does not expect an invalid or unique result. Therefore, in this case, a mechanism (not shown) that notifies the arbitration processor of an error if the same address line is in the cache of a different processor at the time of write-back execution is connected, and whether or not the user has a program mistake Can be determined. When the user explicitly writes data in the common area, it is necessary to perform message communication in advance between tasks crossing the processors. In this case, the processor is normally stopped by the control procedure of the present invention. (However, as an exception, the following problem unintended by the user may also occur. For example, when 1 byte of data is used as a global variable and the cache line is 32 bytes. There is a possibility that two different global variables of 1 byte may be placed in the same 32-byte cache line, and if they are accessed independently by tasks, even if they are treated as independent data areas between tasks, In order to avoid this problem, global variables are aligned at the cache line number of bytes, eg 32 bytes, at compile time. Must be set.)
In the configuration example of the present invention, the input / output data uses a part of the shared memory as a ring buffer for the input / output data, and the ring buffer and the I / O controller are controlled by the arbitration processor to ensure data consistency. keep.

  In the above-described embodiment, the distribution method table for all multiprocessor combinations is generated in the case of three tasks. However, the number of tables may be limited to an appropriate number by combining the number of processors and the number of tasks. .

System LSI hardware configuration and multitask control method

Explanation of symbols

100 bus 200 shared memory 300 part composed of system LSI 400 DMA controller 500 arbitration processor

Claims (2)

A multiprocessor, a data cache memory and an instruction cache memory connected to each processor P1, P2, P3,..., A bus connected in a shared manner so as to be accessible from all processors, and externally through the bus A system LSI having at least an internal memory controller to which a shared memory can be connected,
The above processor is a processor having a means for allowing the user to control the timing of delayed writing and refilling of the data cache, and in the execution of multitasking, candidates for allocation methods to each processor of tasks T1, T2, T3,... Means for preparing a plurality of types as the distribution method tables D1, D2, D3,.
Means for speculatively executing the same task on a plurality of processors by assigning processors to tasks using the table, means for detecting the progress of transition between tasks for each distribution method, and
Multitask control of a multiprocessor-mounted system LSI, characterized by having means for writing back the contents of the distributed memory of the processor used for the processing of the distribution method that has been most advanced based on the detection means to the shared memory Method.   2. The multi-method according to claim 1, wherein in each of the distribution method tables D1, D2, D3,..., The processors are shared among the distribution method tables when the tasks assigned to the processors are the same. Multitask control method for processor-mounted system LSI.

Images