CN102193779A - MPSoC (multi-processor system-on-chip)-oriented multithread scheduling method - Google Patents
MPSoC (multi-processor system-on-chip)-oriented multithread scheduling methodDownload PDFInfo
- Publication number
- CN102193779A CN102193779ACN2011101252627ACN201110125262ACN102193779ACN 102193779 ACN102193779 ACN 102193779ACN 2011101252627 ACN2011101252627 ACN 2011101252627ACN 201110125262 ACN201110125262 ACN 201110125262ACN 102193779 ACN102193779 ACN 102193779A
- Authority
- CN
- China
- Prior art keywords
- processor core
- core group
- processor
- thread
- threads
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034methodMethods0.000titleclaimsabstractdescription51
- 230000008569processEffects0.000claimsabstractdescription26
- 238000005457optimizationMethods0.000claimsdescription6
- 238000013508migrationMethods0.000claimsdescription3
- 230000005012migrationEffects0.000claimsdescription3
- 241001522296Erithacus rubeculaSpecies0.000claims1
- 239000000126substanceSubstances0.000claims1
- 238000004891communicationMethods0.000abstractdescription23
- 238000005265energy consumptionMethods0.000description8
- 238000005516engineering processMethods0.000description8
- 230000010354integrationEffects0.000description5
- 238000012545processingMethods0.000description5
- 238000011161developmentMethods0.000description3
- 238000010586diagramMethods0.000description3
- 230000006870functionEffects0.000description3
- 230000008092positive effectEffects0.000description2
- 230000007547defectEffects0.000description1
- 230000001934delayEffects0.000description1
- 238000013461designMethods0.000description1
- 230000006872improvementEffects0.000description1
- 239000004065semiconductorSubstances0.000description1
- 238000012546transferMethods0.000description1
Images
Landscapes
- Multi Processors (AREA)
Abstract
Translated fromChinese
Description
Translated fromChinese技术领域technical field
本发明属于嵌入式操作系统的多线程调度技术领域，具体涉及一种面向MPSoC的多线程调度方法。The invention belongs to the technical field of multi-thread scheduling of an embedded operating system, and in particular relates to an MPSoC-oriented multi-thread scheduling method.
背景技术Background technique
随着半导体技术的不断进步，VLSI(超大规模集成电路，Very Large-ScaleIntegrated)的集成密度在大幅度增加。单一芯片上的集成度不断提高，使得SoC技术得到了发展和应用。SoC技术是将一个系统的全部功能模块集成到单一的芯片上，从而实现在单个芯片上集成完备的系统功能。处理器核也简称为核。With the continuous advancement of semiconductor technology, the integration density of VLSI (Very Large-Scale Integrated) is increasing significantly. The continuous improvement of integration on a single chip has enabled the development and application of SoC technology. SoC technology integrates all functional modules of a system into a single chip, so as to realize the integration of complete system functions on a single chip. The processor core is also referred to simply as a core.
集成在SoC芯片上的通常是IP(知识产权，Intellectual Property)核。这些可重用的IP核包括嵌入式处理器，存储模块，接口模块和面向应用定制的处理构件。在SoC上集成的IP核可以分为三类：软核(Soft IP)，是指使用RTL(寄存器传送级别，Register Transfer Level)或者更高级别进行描述的IP核；硬核(HardIP)，是指具有固定的层结构，并且针对特定过程中的特定应用进行了定制的优化过的IP核；固化核(Firm IP)是指已经做了描述但是提供了参数供设计人员进行应用定制的IP核。Integrated on the SoC chip is usually an IP (intellectual property, Intellectual Property) core. These reusable IP cores include embedded processors, memory modules, interface modules and application-specific processing components. The IP core integrated on the SoC can be divided into three categories: soft core (Soft IP), which refers to the IP core described by RTL (Register Transfer Level) or higher level; hard core (Hard IP), which is Refers to an IP core that has a fixed layer structure and is customized and optimized for a specific application in a specific process; a fixed core (Firm IP) refers to an IP core that has been described but provides parameters for the designer to customize the application .
SoC不仅集成的晶体管数量多，而且由于集成了不同种类的功能和技术，并且由于软硬件的协同工作，使得SoC具有复杂的体系结构和逻辑接口。SoC的高集成度也使得SoC的功能极为丰富，提高了对片上面积的有效利用，缩短了片上连线的长度，从而提高了整个系统的性能。由于IP核具有可重用性，在IP核设计完成后，相当数量的IP核被大多数SoC系统所使用和集成。在设计平台级的嵌入式系统时，这种重用性极大的提高了开发效率。SoC not only integrates a large number of transistors, but also integrates different kinds of functions and technologies, and because of the cooperative work of software and hardware, SoC has complex architecture and logic interface. The high integration of SoC also makes the function of SoC extremely rich, which improves the effective use of the area on the chip, shortens the length of the connection on the chip, and thus improves the performance of the whole system. Due to the reusability of IP cores, a considerable number of IP cores are used and integrated by most SoC systems after the IP core design is completed. When designing platform-level embedded systems, this reusability greatly improves development efficiency.
MPSoC是对SoC技术的进一步发展，是指具有多于一个嵌入式指令集处理器的SoC。MPSoC结合SoC技术与多核技术的特点。多核技术是指在一个芯片上集成多核处理器核，以提高处理器的处理能力；如果芯片上所集成的多个处理器核相同，核间地位相同，则称为同构多核处理器；如果芯片上所集成的处理器核不同，有主处理器和协处理器之分，则称为异构多核处理器。MPSoC片上既有多核处理器核，又集成了不同种类的软硬件，兼具了SoC和多核的优点。在SoC与MPSoC芯片上，往往会集成存储器，为处理器核提供存储服务，从而提高处理器的效率。MPSoC is a further development of SoC technology, which refers to a SoC with more than one embedded instruction set processor. MPSoC combines the characteristics of SoC technology and multi-core technology. Multi-core technology refers to the integration of multi-core processor cores on a chip to improve the processing capability of the processor; if the multiple processor cores integrated on the chip are the same and have the same status among the cores, it is called a homogeneous multi-core processor; if The processor cores integrated on the chip are different, and there are main processors and coprocessors, which are called heterogeneous multi-core processors. MPSoC not only has multi-core processor cores, but also integrates different types of hardware and software, which combines the advantages of SoC and multi-core. On SoC and MPSoC chips, memory is often integrated to provide storage services for the processor core, thereby improving the efficiency of the processor.
MPSoC上计算资源丰富(即拥有多个处理器核)，因此，通常会采用多线程并行的方式来利用这些计算资源。同时，尽管这些处理器核(简称为处理核或者核)同在一个处理器芯片上，由于核间连线长短不同，核间的通信代价也不同。一般来说，研究表明，核的物理位置越远，核间连线就越长，通信代价也就越大。目前在现有的多线程调度算法中，尚无解决这种情况的高效率方法。Computational resources are abundant on the MPSoC (that is, there are multiple processor cores), so multi-threaded parallel methods are usually used to utilize these computing resources. At the same time, although these processor cores (referred to as processing cores or cores) are on the same processor chip, the communication costs between the cores are also different due to the different lengths of the connections between the cores. In general, studies have shown that the farther the cores are physically located, the longer the inter-core wires and the greater the communication cost. Currently, in the existing multi-thread scheduling algorithm, there is no high-efficiency method to solve this situation.
发明内容Contents of the invention
本发明旨在克服现有技术缺陷，目的在于提供一种能降低线程之间的通信代价和提高调度效率的面向MPSoC的多线程调度方法。The invention aims to overcome the defects of the prior art, and aims to provide an MPSoC-oriented multi-thread scheduling method that can reduce the communication cost between threads and improve scheduling efficiency.
为实现上述目的，本发明采用的技术方案为如下步骤：To achieve the above object, the technical solution adopted in the present invention is the following steps:
第一步、处理器核组划分The first step, processor core group division
将MPSoC上的多个处理器核按物理位置关系划分为处理器核组，相邻的处理器核划分到同一个处理器核组当中；采用处理器核组配置表的形式，将划分后的处理器核组提供给嵌入式操作系统；处理器核组配置表的基本内容包括处理器核组个数和每个处理器核组的标识，处理器核组配置表的附加内容为处理器核频率、处理器核数量、处理器核组划分依据、处理器核温度范围中的一种以上。Divide multiple processor cores on the MPSoC into processor core groups according to the physical position relationship, and divide adjacent processor cores into the same processor core group; adopt the form of processor core group configuration table, divide the divided The processor core group is provided to the embedded operating system; the basic content of the processor core group configuration table includes the number of processor core groups and the identification of each processor core group, and the additional content of the processor core group configuration table is the processor core group configuration table. One or more of frequency, number of processor cores, division basis of processor core groups, and temperature range of processor cores.
第二步、线程组划分The second step, thread group division
进行线程组划分，将多线程进行分组；分组的方法是将属于同一个进程的线程划分到同一个线程组。Carry out thread group division and group multiple threads; the method of grouping is to divide threads belonging to the same process into the same thread group.
第三步、线程组调度The third step, thread group scheduling
采用嵌入式操作系统的调度算法，依据处理器核组配置表对线程组进行调度。The scheduling algorithm of the embedded operating system is adopted, and the thread group is scheduled according to the configuration table of the processor core group.
第四步、线程调度The fourth step, thread scheduling
在同一个处理器核组内，采用分时调度或轮转调度算法对线程进行调度。In the same processor core group, threads are scheduled using time-sharing scheduling or round-robin scheduling algorithms.
第五步、线程调度优化The fifth step, thread scheduling optimization
1)当处理器上存在空闲的处理器核组时，繁忙的处理器核组的就绪队列中仍然存在多个线程，采用如下的策略进行调度优化：1) When there is an idle processor core group on the processor, there are still multiple threads in the ready queue of the busy processor core group, and the following strategy is used for scheduling optimization:
将属于同一个进程的线程从繁忙的处理器核组迁移到空闲的处理器核组，迁移的线程数目Mi为：Migrate the threads belonging to the same process from the busy processor core group to the idle processor core group, the number of migrating threads Mi is:
Mi＝Cs (1)Mi =Cs (1)
式(1)中：In formula (1):
Cs是空闲的处理器核组中处理器核的数目。Cs is the number of processor cores in the idle processor core group.
2)如果仍然有处理器核组空闲，并且剩下的就绪队列中，存在同一个进程的线程无法全部调度到一个处理器核组当中的情况时，将多余的线程按照第五步中的1)所述方法进行调度。2) If there are still processor core groups idle, and in the remaining ready queues, there is a situation that the threads of the same process cannot be all scheduled to a processor core group, the redundant threads are allocated according to step 1 in the fifth step ) method for scheduling.
所述空闲的处理器核组是指处理器核组中的所有处理器核没有正在执行地线程；空闲的处理器核组个数是：对于m个处理器核组，存在n个进程，当n小于m时，存在m-n个空闲的处理器核组；其中，m和n均为自然数，且m大于或等于2。The idle processor core group refers to that all processor cores in the processor core group are not executing threads; the number of idle processor core groups is: for m processor core groups, there are n processes, when When n is less than m, there are m-n idle processor core groups; wherein, m and n are both natural numbers, and m is greater than or equal to 2.
由于采用上述技术方案，本发明通过多核处理器上处理器核组的划分，将物理距离近的处理器核划分到同一处理器核组内，提高了通信的效率，并减少了线路上的通信能耗；而处理器核组间的线程迁移则降低了繁忙的处理器核组的工作负担，利用空闲的处理器核组执行线程，提高了处理器的执行效率。与现有技术相比，具有如下积极效果是：Due to the adoption of the above technical scheme, the present invention divides the processor cores with close physical distances into the same processor core group through the division of processor core groups on the multi-core processor, which improves the efficiency of communication and reduces the communication on the line. Energy consumption; thread migration between processor core groups reduces the workload of busy processor core groups, and uses idle processor core groups to execute threads, improving processor execution efficiency. Compared with the prior art, it has the following positive effects:
(1)高效性。本发明利用分组对多核多线程进行调度，将物理位置上相距近的处理器核划分到同一个处理器核组，同一个处理器核组内部通信距离短，通信效率高；同时，由于将繁忙的处理器核组中的线程迁移到了空闲的处理器核组，提高了处理器核的利用效率和线程的执行效率。(1) Efficiency. The present invention uses grouping to schedule multi-core and multi-thread, and divides the processor cores that are physically close to each other into the same processor core group, the internal communication distance of the same processor core group is short, and the communication efficiency is high; at the same time, due to the busy The threads in the processor core group are migrated to the idle processor core group, which improves the utilization efficiency of the processor core and the execution efficiency of the thread.
(2)低能耗。本发明中将多个处理器核分组，线程间通信以处理器核组内通信为主，而同一处理器核组的线程通信物理距离短，需要消耗在线路上的能耗也低，从而降低了多线程通信的能耗。(2) Low energy consumption. In the present invention, a plurality of processor cores are grouped, and the inter-thread communication is mainly based on the communication within the processor core group, while the thread communication physical distance of the same processor core group is short, and the energy consumption required to be consumed on the line is also low, thereby reducing Energy consumption of multithreaded communication.
因此，本发明根据MPSoC上处理器核间的物理距离不同将处理器核划分为处理器核组，将多线程划分为不同的线程组，将线程组在处理器核组上进行调度，减少了线程之间的通信代价，提高了调度的效率。Therefore, the present invention divides the processor cores into processor core groups according to the physical distance between the processor cores on the MPSoC, divides the multithreading into different thread groups, and schedules the thread groups on the processor core groups, reducing the The communication cost between threads improves the scheduling efficiency.
附图说明Description of drawings
图1是本发明的实施过程示意图；Fig. 1 is a schematic diagram of the implementation process of the present invention;
图2是本发明的4核处理器的处理器核组划分示意图；Fig. 2 is a schematic diagram of the processor core group division of the 4-core processor of the present invention;
图3是本发明的8核处理器的处理器核组划分示意图。FIG. 3 is a schematic diagram of processor core group division of an 8-core processor according to the present invention.
具体实施方式Detailed ways
实施例1Example 1
一种面向MPSoC的多线程调度方法。其方法如图1所示步骤：A multi-thread scheduling method for MPSoC. Its method steps as shown in Figure 1:
第一步、处理器核组划分The first step, processor core group division
将MPSoC上的多个处理器核按物理位置关系划分为处理器核组，相邻的处理器核划分到同一个处理器核组当中；采用处理器核组配置表的形式，将分后的处理器核组提供给嵌入式操作系统；处理器核组配置表的基本内容包括处理器核组个数和每个处理器核组的标识，处理器核组配置表的附加内容为处理器核频率、处理器核数量、处理器核组划分依据、处理器核温度范围中的一种以上。Divide multiple processor cores on the MPSoC into processor core groups according to their physical position, and divide adjacent processor cores into the same processor core group; adopt the form of processor core group configuration table, divide the divided The processor core group is provided to the embedded operating system; the basic content of the processor core group configuration table includes the number of processor core groups and the identification of each processor core group, and the additional content of the processor core group configuration table is the processor core group configuration table. One or more of frequency, number of processor cores, division basis of processor core groups, and temperature range of processor cores.
在MPSoC上集成了多个处理器核。为了充分利用片上的多个处理器核，将MPSoC上的多个处理器核按物理位置关系进行划分，通过对处理器核的分组，形成不同的处理器核组，以减少访问延迟。对于多核嵌入式系统MPSoC来说，最为重要的片上计算资源就是这些处理器核。因此，在划分时是以处理器核的物理位置为划分的主要依据。Multiple processor cores are integrated on the MPSoC. In order to make full use of the multiple processor cores on the chip, the multiple processor cores on the MPSoC are divided according to the physical location relationship, and different processor core groups are formed by grouping the processor cores to reduce access delays. For multi-core embedded system MPSoC, the most important on-chip computing resources are these processor cores. Therefore, when dividing, the physical location of the processor core is used as the main basis for dividing.
MPSoC上有多个处理器核。对于相邻的处理器核，将它们划分到同一个处理器核组。而每个处理器核组内都是由一个以上的处理器核组成，故片上的处理器核就会被划分进不同的处理器核组之内。这样，位于同一个处理器核组内的处理器核被聚集成一个整体，能够做为更大的调度单元，由操作系统进行调度。There are multiple processor cores on MPSoC. For adjacent processor cores, divide them into the same processor core group. And each processor core group is composed of more than one processor core, so the processor cores on the chip will be divided into different processor core groups. In this way, the processor cores in the same processor core group are aggregated into a whole, and can be used as a larger scheduling unit for scheduling by the operating system.
处理器核的划分依据是根据处理器核间的物理位置，相邻的处理器核划分到同一个处理器核组当中。例如，对于一个拥有4个处理器核的MPSoC来说，如图2所示，处理器核0和处理器核3在片上的物理距离小，物理位置近，划分为处理器核组0；而处理器核1和处理器核2在片上的物理距离小，物理位置近，划分为处理器核组1。这样划分的原因，是因为物理位置小，通信代价也小。The division of processor cores is based on the physical location between processor cores, and adjacent processor cores are divided into the same processor core group. For example, for an MPSoC with 4 processor cores, as shown in Figure 2, the physical distance between
处理器核的划分是根据实际需要进行划分，每个处理器核组中包含的处理器核的数目相同或不同。例如，将拥有4个处理器核的MPSoC划分为处理器核0为处理器核组0，处理器核1、处理器核2、处理器核3划分为处理器核组1。The processor cores are divided according to actual needs, and the number of processor cores included in each processor core group is the same or different. For example, an MPSoC with 4 processor cores is divided into
采用处理器核组配置表的形式，将划分后的处理器核组提供给嵌入式操作系统。处理器核组配置表的基本内容包括处理器核组个数和每个处理器核组的标识，处理器核组配置表的附加内容为处理器核频率、处理器核数量、处理器核组划分依据、处理器核温度范围中的一种以上。The divided processor core groups are provided to the embedded operating system in the form of a processor core group configuration table. The basic content of the processor core group configuration table includes the number of processor core groups and the identification of each processor core group. The additional contents of the processor core group configuration table are processor core frequency, number of processor cores, processor core group More than one of the classification basis and processor core temperature range.
如图2所示的多核处理器，在经过处理器核组划分后，选择处理器核数量和处理器核频率为处理器核组配置表的附加内容，则处理器核组配置表内容为：For the multi-core processor shown in Figure 2, after the division of the processor core groups, the number of processor cores and the frequency of the processor cores are selected as the additional contents of the processor core group configuration table, then the contents of the processor core group configuration table are:
1)处理器核组0：处理器核1，处理器核31) Processor core group 0: processor core 1, processor core 3
2)处理器核组1，处理器核0，处理器核22) Processor core group 1,
3)处理器核数量：43) Number of processor cores: 4
4)处理器核频率：处理器核0(500MHz)，处理器核1(500MHz)，处理器核2(500MHz)，处理器核3(500MHz)。4) Processor core frequency: processor core 0 (500MHz), processor core 1 (500MHz), processor core 2 (500MHz), processor core 3 (500MHz).
第二步、线程组划分The second step, thread group division
进行线程组划分，将多线程进行分组；分组的方法是将属于同一个进程的线程划分到同一个线程组。Carry out thread group division and group multiple threads; the method of grouping is to divide threads belonging to the same process into the same thread group.
在MPSoC上，为了充分利用多核处理器的处理能力，采用多线程并行的方法。处理器核组划分完毕之后，为了进行更好的调度优化，进行线程组划分，将多线程进行分组。分组的方法是将属于同一个进程的线程划分到同一个线程组。例如，对于线程T1、T2、T3、T4、T5、T6和T7，其中线程T1、T2和T3属于进程P1；线程T4、T5、T6和T7属于进程P2。线程T1、T2和T3将划分到同一个线程组G1；线程T4、T5、T6和T7划分到同一个线程组G2。On MPSoC, in order to make full use of the processing ability of the multi-core processor, adopt the method of multi-thread parallelism. After the processor core group is divided, in order to perform better scheduling optimization, the thread group is divided and the multi-threads are grouped. The method of grouping is to divide threads belonging to the same process into the same thread group. For example, for threads T1, T2, T3, T4, T5, T6 and T7, wherein threads T1, T2 and T3 belong to process P1; threads T4, T5, T6 and T7 belong to process P2. Threads T1, T2, and T3 will be assigned to the same thread group G1; threads T4, T5, T6, and T7 will be assigned to the same thread group G2.
第三步、线程组调度The third step, thread group scheduling
采用嵌入式操作系统的调度算法，依据处理器核组配置表对线程组进行调度。The scheduling algorithm of the embedded operating system is adopted, and the thread group is scheduled according to the configuration table of the processor core group.
采用嵌入式操作系统的调度算法，依据处理器核组配置表对线程组进行调度。MPSoC上的处理器核被划分为处理器核组后，对于嵌入式操作系统来说，调度时以处理器核组为单位，依据处理器核组配置表获取处理器核组的信息；同时将单个处理器核组当作一个基本的分配单元，在多个线程组之间进行调度和分配。对于每个处理器核组，嵌入式操作系统都维持一个就绪队列，就绪队列中有就绪线程组，就绪线程组是可执行的一组线程，就绪线程组中的线程属于同一个线程组(即同一个进程)。当某个处理器核组上的线程组运行结束后，操作系统就分配就绪线程组到这个处理器核组上去。The scheduling algorithm of the embedded operating system is adopted, and the thread group is scheduled according to the configuration table of the processor core group. After the processor cores on the MPSoC are divided into processor core groups, for the embedded operating system, the processor core group is used as the unit for scheduling, and the processor core group information is obtained according to the processor core group configuration table; at the same time, the A single processor core group is used as a basic allocation unit to schedule and allocate among multiple thread groups. For each processor core group, the embedded operating system maintains a ready queue. There are ready thread groups in the ready queue. The ready thread group is a group of threads that can be executed. The threads in the ready thread group belong to the same thread group (ie the same process). When the thread group on a processor core group finishes running, the operating system assigns the ready thread group to the processor core group.
第四步、线程调度The fourth step, thread scheduling
同一个进程内的线程被调度到同一个就绪队列当中。在对处理器核组进行划分时，一个处理器核组内有多个处理器核。因此，当线程组中的多线程运行时，尽管该进程只能使用某个处理器核组，但由于处理器核组内部的计算资源同样丰富，当这个就绪队列对应的处理器核组可用时，该进程对应的线程被分配到这个处理器核组上运行。在同一个处理器核组内，采用分时调度算法对线程进行调度。Threads in the same process are scheduled into the same ready queue. When dividing the processor core group, there are multiple processor cores in one processor core group. Therefore, when multiple threads in the thread group are running, although the process can only use a certain processor core group, since the computing resources inside the processor core group are also abundant, when the processor core group corresponding to the ready queue is available , the thread corresponding to the process is assigned to run on this processor core group. In the same processor core group, threads are scheduled using a time-sharing scheduling algorithm.
第五步、线程调度优化The fifth step, thread scheduling optimization
1)为了提高对处理器核资源的利用效率，在处理器上存在空闲的处理器核组的情况下，将单个进程的多个线程同时调度到多个就绪队列当中。当处理器上存在空闲的处理器核组时，繁忙的处理器核组的就绪队列中仍然存在多个线程，采用如下的策略进行调度优化：1) In order to improve the utilization efficiency of processor core resources, when there is an idle processor core group on the processor, multiple threads of a single process are scheduled to multiple ready queues at the same time. When there is an idle processor core group on the processor, there are still multiple threads in the ready queue of the busy processor core group, and the following strategy is used for scheduling optimization:
将属于同一个进程的线程从繁忙的处理器核组迁移到空闲的处理器核组，迁移的线程数目Mi为：Migrate the threads belonging to the same process from the busy processor core group to the idle processor core group, the number of migrating threads Mi is:
Mi＝Cs (1)Mi =Cs (1)
式(1)中：In formula (1):
Cs是空闲的处理器核组中处理器核的数目；Cs is the number of processor cores in the idle processor core group;
空闲的处理器核组是指处理器核组中的所有处理器核没有正在执行地线程；空闲的处理器核组个数是：对于m个处理器核组，存在n个进程，当n小于m时，存在m-n个空闲的处理器核组；其中，m和n均为自然数，且m大于或等于2。The idle processor core group means that all the processor cores in the processor core group are not executing threads; the number of idle processor core groups is: for m processor core groups, there are n processes, when n is less than When m, there are m-n idle processor core groups; wherein, both m and n are natural numbers, and m is greater than or equal to 2.
2)如果仍然有处理器核组空闲，并且剩下的就绪队列中，存在同一个进程的线程无法全部调度到一个处理器核组当中的情况时，将多余的线程按照第五步中的1)所述方法进行调度。2) If there are still processor core groups idle, and in the remaining ready queues, there is a situation that the threads of the same process cannot be all scheduled to a processor core group, the redundant threads are allocated according to step 1 in the fifth step ) method for scheduling.
通过上述方法，对线程调度进行优化来提高处理器核的利用率。Through the above method, the thread scheduling is optimized to improve the utilization rate of the processor core.
实施例2Example 2
一种面向MPSoC的多线程调度方法。该方法的步骤是：A multi-thread scheduling method for MPSoC. The steps of this method are:
第一步、处理器核组划分，处理器有8个处理器核。其划分方法如图3所示，以物理位置为依据，将处理器核0，处理器核3，处理器核4划分为处理器核组0，处理器核1，处理器核2划分为处理器核组1，处理器核5，处理器核6，处理器核7划分为处理器核组2。The first step is to divide the processor core group, and the processor has 8 processor cores. The division method is shown in Figure 3. Based on the physical location,
第四步、线程调度中，同一个进程内线程被调度到同一个就绪队列当中。在对处理器核组进行划分时，一个处理器核组内有多个处理器核。因此，当线程组中的多线程运行时，尽管该进程只能使用某个处理器核组，但是由于处理器核组内部的计算资源同样丰富，当这个就绪队列对应的处理器核组可用时，该进程对应的线程被分配到这个处理器核组上运行。在同一个处理器核组内，采用轮转调度算法对线程进行调度。In the fourth step, in thread scheduling, the same in-process thread is scheduled to the same ready queue. When dividing the processor core group, there are multiple processor cores in one processor core group. Therefore, when the multi-threads in the thread group are running, although the process can only use a certain processor core group, because the computing resources inside the processor core group are also abundant, when the processor core group corresponding to the ready queue is available , the thread corresponding to the process is assigned to run on this processor core group. In the same processor core group, threads are scheduled using a round-robin scheduling algorithm.
其余同实施例1。All the other are with embodiment 1.
本具体实施方式通过对处理器核组的划分，将物理距离近的处理器核划分到同一处理器核组内，提高了通信的效率，并减少了线路上的通信能耗；而处理器核组间的线程迁移则降低了繁忙的处理器核组的工作负担，利用空闲的处理器核组执行线程，提高了处理器的执行效率。与现有技术相比，具有如下积极效果是：In this specific embodiment, by dividing the processor core groups, the processor cores with close physical distances are divided into the same processor core group, which improves the communication efficiency and reduces the communication energy consumption on the line; and the processor cores Thread migration between groups reduces the workload of busy processor core groups, uses idle processor core groups to execute threads, and improves processor execution efficiency. Compared with the prior art, it has the following positive effects:
(1)高效性。利用分组对多核多线程进行调度，将物理位置上相距近的处理器核划分到同一个处理器核组，同一个处理器核组内部通信距离短，通信效率高；同时，由于将繁忙的处理器核组中的线程迁移到了空闲的处理器核组，提高了处理器核的利用效率和线程的执行效率。(1) Efficiency. Use grouping to schedule multi-core and multi-thread, divide the processor cores that are physically close to each other into the same processor core group, the internal communication distance of the same processor core group is short, and the communication efficiency is high; at the same time, due to the busy processing The threads in the processor core group are migrated to the idle processor core group, which improves the utilization efficiency of the processor core and the execution efficiency of the thread.
(2)低能耗。将多处理器核分组后，线程间通信以处理器核组内通信为主，而同一处理器核组的线程通信物理距离短，需要消耗在线路上的能耗也低，从而降低了多线程通信的能耗。(2) Low energy consumption. After the multi-processor cores are grouped, the inter-thread communication is mainly based on the communication within the processor core group, and the physical distance of the thread communication of the same processor core group is short, and the energy consumption on the line is also low, thereby reducing the multi-thread communication. energy consumption.
因此，本具体实施方式根据MPSoC上处理器核间的物理距离不同将处理器核划分为处理器核组，将多线程划分为不同的线程组，将线程组在处理器核组上进行调度，减少了线程之间的通信代价，提高了调度的效率。Therefore, this embodiment divides the processor cores into processor core groups according to the different physical distances between processor cores on the MPSoC, divides the multithreading into different thread groups, and schedules the thread groups on the processor core groups. The cost of communication between threads is reduced, and the efficiency of scheduling is improved.
Claims (2)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2011101252627ACN102193779A (en) | 2011-05-16 | 2011-05-16 | MPSoC (multi-processor system-on-chip)-oriented multithread scheduling method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2011101252627ACN102193779A (en) | 2011-05-16 | 2011-05-16 | MPSoC (multi-processor system-on-chip)-oriented multithread scheduling method |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN102193779Atrue CN102193779A (en) | 2011-09-21 |
Family
ID=44601902
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2011101252627APendingCN102193779A (en) | 2011-05-16 | 2011-05-16 | MPSoC (multi-processor system-on-chip)-oriented multithread scheduling method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN102193779A (en) |
Cited By (19)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102855153A (en)* | 2012-07-27 | 2013-01-02 | 华中科技大学 | Flow compilation optimization method oriented to chip multi-core processor |
| CN103294541A (en)* | 2013-05-24 | 2013-09-11 | 福建联迪商用设备有限公司 | Star-structured multi-process communication method and device |
| CN103838631A (en)* | 2014-03-11 | 2014-06-04 | 武汉科技大学 | A Method for Realizing Multi-thread Scheduling for Network-on-Chip |
| WO2014082562A1 (en)* | 2012-11-29 | 2014-06-05 | Tencent Technology (Shenzhen) Company Limited | Method, device, and system for information processing based on distributed buses |
| CN104156267A (en)* | 2013-05-14 | 2014-11-19 | 华为技术有限公司 | Task allocation method, task allocation device and on-chip network |
| CN104375882A (en)* | 2014-11-21 | 2015-02-25 | 北京应用物理与计算数学研究所 | Multistage nested data drive calculation method matched with high-performance computer structure |
| WO2015070789A1 (en)* | 2013-11-14 | 2015-05-21 | Mediatek Inc. | Task scheduling method and related non-transitory computer readable medium for dispatching task in multi-core processor system based at least partly on distribution of tasks sharing same data and/or accessing same memory address (es) |
| US9195493B2 (en) | 2014-03-27 | 2015-11-24 | International Business Machines Corporation | Dispatching multiple threads in a computer |
| US9213569B2 (en) | 2014-03-27 | 2015-12-15 | International Business Machines Corporation | Exiting multiple threads in a computer |
| US9223574B2 (en) | 2014-03-27 | 2015-12-29 | International Business Machines Corporation | Start virtual execution instruction for dispatching multiple threads in a computer |
| WO2016044980A1 (en)* | 2014-09-22 | 2016-03-31 | 华为技术有限公司 | Thread migration method, apparatus and system |
| CN105528330A (en)* | 2014-09-30 | 2016-04-27 | 杭州华为数字技术有限公司 | Load balancing method and device, cluster and many-core processor |
| CN105868016A (en)* | 2015-01-20 | 2016-08-17 | 复旦大学 | Thread transfer distribution method capable of preventing local overheat of multi-core processor |
| US9501069B2 (en) | 2014-03-13 | 2016-11-22 | International Business Machines Corporation | Control of solid state memory device temperature using queue depth management |
| CN106489132A (en)* | 2014-09-19 | 2017-03-08 | 华为技术有限公司 | The method of read-write data, device, storage device and computer system |
| CN106933663A (en)* | 2017-03-07 | 2017-07-07 | 武汉科技大学 | A kind of multithread scheduling method and system towards many-core system |
| US9772867B2 (en) | 2014-03-27 | 2017-09-26 | International Business Machines Corporation | Control area for managing multiple threads in a computer |
| CN108139938A (en)* | 2015-07-31 | 2018-06-08 | 华为技术有限公司 | Apparatus, method and computer program for utilizing secondary threads to assist main thread in performing application tasks |
| CN108829510A (en)* | 2018-05-04 | 2018-11-16 | 天津猎鹰网络技术有限公司 | Thread binds treating method and apparatus |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5574939A (en)* | 1993-05-14 | 1996-11-12 | Massachusetts Institute Of Technology | Multiprocessor coupling system with integrated compile and run time scheduling for parallelism |
| CN101069161A (en)* | 2004-12-01 | 2007-11-07 | 索尼计算机娱乐公司 | Scheduling method, scheduling device and multiprocessor system |
| CN101923491A (en)* | 2010-08-11 | 2010-12-22 | 上海交通大学 | Method for thread group address space scheduling and thread switching in multi-core environment |
- 2011
- 2011-05-16CNCN2011101252627Apatent/CN102193779A/enactivePending
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5574939A (en)* | 1993-05-14 | 1996-11-12 | Massachusetts Institute Of Technology | Multiprocessor coupling system with integrated compile and run time scheduling for parallelism |
| CN101069161A (en)* | 2004-12-01 | 2007-11-07 | 索尼计算机娱乐公司 | Scheduling method, scheduling device and multiprocessor system |
| CN101923491A (en)* | 2010-08-11 | 2010-12-22 | 上海交通大学 | Method for thread group address space scheduling and thread switching in multi-core environment |
Cited By (37)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102855153B (en)* | 2012-07-27 | 2016-03-02 | 华中科技大学 | Towards the stream compile optimization method of chip polycaryon processor |
| CN102855153A (en)* | 2012-07-27 | 2013-01-02 | 华中科技大学 | Flow compilation optimization method oriented to chip multi-core processor |
| WO2014082562A1 (en)* | 2012-11-29 | 2014-06-05 | Tencent Technology (Shenzhen) Company Limited | Method, device, and system for information processing based on distributed buses |
| US9537786B2 (en) | 2012-11-29 | 2017-01-03 | Tencent Technology (Shenzhen) Company Limited | Method, device, and system for information processing based on distributed buses |
| US10671447B2 (en) | 2013-05-14 | 2020-06-02 | Huawei Technologies Co., Ltd. | Method, apparatus, and network-on-chip for task allocation based on predicted traffic in an extended area |
| CN104156267A (en)* | 2013-05-14 | 2014-11-19 | 华为技术有限公司 | Task allocation method, task allocation device and on-chip network |
| WO2014183530A1 (en)* | 2013-05-14 | 2014-11-20 | 华为技术有限公司 | Task assigning method, task assigning apparatus, and network-on-chip |
| US9965335B2 (en) | 2013-05-14 | 2018-05-08 | Huawei Technologies Co., Ltd. | Allocating threads on a non-rectangular area on a NoC based on predicted traffic of a smallest rectangular area |
| CN104156267B (en)* | 2013-05-14 | 2017-10-10 | 华为技术有限公司 | Method for allocating tasks, task allocation apparatus and network-on-chip |
| CN103294541A (en)* | 2013-05-24 | 2013-09-11 | 福建联迪商用设备有限公司 | Star-structured multi-process communication method and device |
| WO2014187166A1 (en)* | 2013-05-24 | 2014-11-27 | 福建联迪商用设备有限公司 | Communication method and apparatus among multiple processes in star structure |
| CN103294541B (en)* | 2013-05-24 | 2017-04-26 | 福建联迪商用设备有限公司 | Star-structured multi-process communication method and device |
| CN104995603A (en)* | 2013-11-14 | 2015-10-21 | 联发科技股份有限公司 | Task scheduling method based at least in part on distribution of tasks sharing the same data and/or accessing the same memory address and related non-transitory computer readable medium for distributing tasks in a multi-core processor system |
| WO2015070789A1 (en)* | 2013-11-14 | 2015-05-21 | Mediatek Inc. | Task scheduling method and related non-transitory computer readable medium for dispatching task in multi-core processor system based at least partly on distribution of tasks sharing same data and/or accessing same memory address (es) |
| CN103838631A (en)* | 2014-03-11 | 2014-06-04 | 武汉科技大学 | A Method for Realizing Multi-thread Scheduling for Network-on-Chip |
| CN103838631B (en)* | 2014-03-11 | 2017-04-19 | 武汉科技大学 | Multi-thread scheduling realization method oriented to network on chip |
| US9501069B2 (en) | 2014-03-13 | 2016-11-22 | International Business Machines Corporation | Control of solid state memory device temperature using queue depth management |
| US9213569B2 (en) | 2014-03-27 | 2015-12-15 | International Business Machines Corporation | Exiting multiple threads in a computer |
| TWI617986B (en)* | 2014-03-27 | 2018-03-11 | 萬國商業機器公司 | Assign multiple threads to the computer |
| US9223574B2 (en) | 2014-03-27 | 2015-12-29 | International Business Machines Corporation | Start virtual execution instruction for dispatching multiple threads in a computer |
| US9772867B2 (en) | 2014-03-27 | 2017-09-26 | International Business Machines Corporation | Control area for managing multiple threads in a computer |
| US9195493B2 (en) | 2014-03-27 | 2015-11-24 | International Business Machines Corporation | Dispatching multiple threads in a computer |
| CN106489132B (en)* | 2014-09-19 | 2019-04-19 | 华为技术有限公司 | Method, device, storage device and computer system for reading and writing data |
| CN106489132A (en)* | 2014-09-19 | 2017-03-08 | 华为技术有限公司 | The method of read-write data, device, storage device and computer system |
| US10303474B2 (en) | 2014-09-19 | 2019-05-28 | Huawei Technologies Co., Ltd. | Data read/write method and apparatus, storage device, and computer system |
| WO2016044980A1 (en)* | 2014-09-22 | 2016-03-31 | 华为技术有限公司 | Thread migration method, apparatus and system |
| CN105528330A (en)* | 2014-09-30 | 2016-04-27 | 杭州华为数字技术有限公司 | Load balancing method and device, cluster and many-core processor |
| CN105528330B (en)* | 2014-09-30 | 2019-05-28 | 杭州华为数字技术有限公司 | The method, apparatus of load balancing is gathered together and many-core processor |
| CN104375882A (en)* | 2014-11-21 | 2015-02-25 | 北京应用物理与计算数学研究所 | Multistage nested data drive calculation method matched with high-performance computer structure |
| CN104375882B (en)* | 2014-11-21 | 2016-06-01 | 北京应用物理与计算数学研究所 | The multistage nested data being matched with high-performance computer structure drives method of calculation |
| CN105868016B (en)* | 2015-01-20 | 2019-04-02 | 复旦大学 | A kind of thread transfer distribution method avoiding multi-core processor hot-spot |
| CN105868016A (en)* | 2015-01-20 | 2016-08-17 | 复旦大学 | Thread transfer distribution method capable of preventing local overheat of multi-core processor |
| CN108139938A (en)* | 2015-07-31 | 2018-06-08 | 华为技术有限公司 | Apparatus, method and computer program for utilizing secondary threads to assist main thread in performing application tasks |
| CN106933663B (en)* | 2017-03-07 | 2019-07-23 | 武汉科技大学 | A kind of multithread scheduling method and system towards many-core system |
| CN106933663A (en)* | 2017-03-07 | 2017-07-07 | 武汉科技大学 | A kind of multithread scheduling method and system towards many-core system |
| CN108829510A (en)* | 2018-05-04 | 2018-11-16 | 天津猎鹰网络技术有限公司 | Thread binds treating method and apparatus |
| CN108829510B (en)* | 2018-05-04 | 2021-01-29 | 天津猎鹰网络技术有限公司 | Thread binding processing method and device |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102193779A (en) | MPSoC (multi-processor system-on-chip)-oriented multithread scheduling method | |
| CN102360309B (en) | Scheduling system and scheduling execution method of multi-core heterogeneous system on chip | |
| CN103336718B (en) | A kind of GPU thread scheduling optimization method | |
| CN101833368B (en) | A Partial Dynamic Reconfigurable System Energy Management Method Based on Coordinated Processing of Software and Hardware | |
| CN102831011B (en) | A kind of method for scheduling task based on many core systems and device | |
| WO2020117388A1 (en) | Accelerating dataflow signal processing applications across heterogeneous cpu/gpu systems | |
| CN102193826A (en) | Method for high-efficiency task scheduling of heterogeneous multi-core processor | |
| CN101169731A (en) | Multi-channel multi-core server and its CPU virtualization processing method | |
| CN101673223B (en) | Thread dispatching implementation method based on on-chip multiprocessor | |
| CN1825286A (en) | Embedded SRAM Operating System Thread Realization and Thread State Conversion Method | |
| CN103984595A (en) | Isomerous CMP (Chip Multi-Processor) static state task scheduling method | |
| CN114661460A (en) | AI framework two-stage parallel acceleration method for heterogeneous many-core processor | |
| CN101290592B (en) | Realization method for multiple program sharing SPM on MPSOC | |
| CN106648866B (en) | A Resource Scheduling Method Based on KVM Platform to Meet Task Time Limit | |
| CN105653243A (en) | Method for distributing tasks by general purpose graphic processing unit in multi-task concurrent execution manner | |
| CN102023846B (en) | Shared front-end assembly line structure based on monolithic multiprocessor system | |
| CN103777995B (en) | Synchronization optimized dispatching system and dispatching method based on group dispatching in virtualization environment | |
| Ottaviano et al. | ControlPULP: a RISC-V power controller for HPC processors with parallel control-law computation acceleration | |
| CN103631659A (en) | Schedule optimization method for communication energy consumption in on-chip network | |
| Wu et al. | Argus: Efficient job scheduling in rdma-assisted big data processing | |
| Zaykov et al. | Reconfigurable multithreading architectures: A survey | |
| Vaidya et al. | Dynamic scheduler for multi-core systems | |
| CN111221640B (en) | GPU-CPU cooperative energy saving method | |
| CN103294623A (en) | Configurable multi-thread dispatch circuit for SIMD system | |
| Xiao et al. | Brief industry paper: Retention-based energy-efficient scheduling of arbitrary-deadline dag tasks on multicore platforms |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C12 | Rejection of a patent application after its publication | ||
| RJ01 | Rejection of invention patent application after publication | Application publication date:20110921 |