探究一种新的可配置处理器的异构多核线程级动态调度模型

本文针对基于可配置处理器的异构多核结构，提出一种新的线程级动态调度模型。此类异构多核系统中每个核分别针对某一应用做指令集扩展，调度器通过线程、处理器核以及指令集间的映射关系，动态调度线程至适合的处理器核，从而在没有大幅增加芯片面积的前提下，达到与每个核都

1.概述

多核处理器从结构上可以分为同构多核和异构多核两类。同构多核使用多个相同的处理核，通过并行处理提高系统性能；异构多核使用多个不同的处理核，增加并行性的同时还可针对特定应用做硬件加速，因此具有更好的加速比。不过，由于异构多核的核间指令集存在差异，动态调度较难实现。

本文针对基于可配置处理器的异构多核结构，提出一种新的线程级动态调度模型。此类异构多核系统中每个核分别针对某一应用做指令集扩展，调度器通过线程、处理器核以及指令集间的映射关系，动态调度线程至适合的处理器核，从而在没有大幅增加芯片面积的前提下，达到与每个核都具有全扩展指令集相近似的加速比，此外该模型还可以有效减少编程模型的复杂度。

2.新模型的数学描述

2.1 现有异构多核分析

同构多核核间无差异，因此动态调度容易实现，而异构多核动态调度可行与否取决于指令集结构设计。现有异构多核指令集结构设计大致可分为三类：

● 指令集完全不同

此类设计中，设计者选择不同功能导向的处理器核组成异构多核系统，每一种核针对某一类处理都具有较强功能，核之间的指令集存在巨大差异，因此动态调度在此类设计中无法实现，只能通过静态调度的方式完成任务指派［3］。

● 指令集完全相同

此类设计中，设计者选取具有相同指令集但硬件配置上有所不同的处理器核，组成异构多核系统［2］。

● 指令集部分相同

此类设计中，处理核心是一组可配置处理器，所有的处理核心具有一个公共的指令集，每个核心都可以根据应用增加一些扩展指令，以增强对应用某一方面的处理能力［4］。

2.2. 新模型的数学描述

本文提出的调度模型即针对基于可配置处理器的异构多核。该模型成立基于以下假设，每个核的指令集配置完成于芯片设计阶段，芯片一旦生产，任意一个核的指令集配置都不可修改。实际上，动态可配置指令集对芯片面积及功耗都会带来巨大消耗，因此现在市场上绝大部分可配置处理器都符合上述假设。为描述简单起见，下文中一个处理器核被称为core。

首先定义模型中使用的三个集合。

集合 C= {Xi|Xi是系统中某个core}

集合 I={Yi|Yi是系统中某种指令集}

集合 T={Zi|Zi是系统中某个线程}

对于上述集合，存在映射关系

f ：C→∪Ii，Ii.I且Ii≠φ，即任意一个core必然存在一个I的非空子集Im与之对应，其实际意义表示该core可以运行集合Im所包含的指令。根据模型的成立条件，core的指令集在系统运行时不可修改，因此不同core对应的Im可能相同，但是每个core仅对应一个Im，故f是单射，即　XIi∈C，Im.I，且Im ≠φ，f（Xi）=Im （式1）　类似的。

还存在映射关系　g:T→∪Ii，Ii.I且Ii≠φ，即任意一个线程必然存在一个I的非空子集In与之对应，其实际意义表示该线程必须运行在具有指令集In 的处理器上。任意一个时刻每个线程仅有一个In与之对应，此外不同的线程对应的In可能相同，故g也是单射，即　Zi∈T，In.I，且In≠φ，g（Zi）=In （式2）　根据上述公式，对任意的Xi，可以得到一个Im，任意的Zi，可以得到一个In，则公式（3）成立。

这是模型中的调度函数，当线程所需指令集是core指令集的子集，match（Im，In）值为1，表示线程Zi可以运行在处理器核Xi上。

3. 模型实现

上述模型可以有多种实现方式，本文参考位图的思想完成其中一种实现。

3.1. 三个集合的确定

考虑常用多核规模，32 种指令集已可满足指令集种类数量要求，因此该实现将无符号二进制32位整数的每一位对应一种指令集，其最低有效位为20，记为ISA1，最高有效位为231，记为ISA32，若可以运行指令集ISAm，则该无符号整数的第m位为1，故集合I在基于位图的实现中定义为I={ISAm无符号整数第m-1位为1，1≤m≤32}。

任意I中几个元素，对其依次做或运算（OR）得到一个新整数，该整数即可表示由这几个元素构成的I的子集。系统中所有的core具有公共指令集，将此指令集记为ISA1。

系统中每个core具有一个唯一编号，因此集合C= {0， 1， ……， n.1}，n为系统中core的数量。

此外，根据线程的定义，不同的线程不能具有相同的线程句柄，因此T={所有线程句柄}。

3.2. 三个公式的实现

定义一个二维的无符号整数数组cpu_isa_map，数组每行第一个元素为core的编号，第二个元素为I的一个非空子集，表示该core可以运行的所有指令集，最后一行用于循环结束，第一个元素为无穷大（0xFFFFFFFF），第二个元素为空集。以core的编号对该数组遍历查询即可实现公式1。图1为该数组的一个例子。

POSIX线程标准中，每个线程具有pthread_attr_t结构体类型的属性参数，为了兼容POSIX标准，扩展该结构体，添加一个无符号整数变量runnable_isa，表示该线程可以运行的指令集集合。创建线程时需要显示设置runnable_isa，如果没有设置，该变量默认值为公共指令集ISA1，这样就实现了公式2。

对于公式3，首先根据调度器当前运行的core编号查询cpu_isa_map获得core支持的指令集core_isa，然后遍历线程调度器的就绪线程队列，将每个线程的runnable_isa属性与core_isa做与操作（AND），若结果不为0且runnable小于等于core_isa，则说明该core的指令集配置满足线程所需的运行要求。

即match（Im，In）为1，线程可以被运行，如果所有线程均无法运行在该核上，则返回空指针。图2为此算法实现，其中HEAD（state）为获得就绪线程队列的头指针，该队列尾指针的next指针为空指针。至此，模型已经全部实现完毕。

4. 实验结果

本文使用基于Xtensa处理器组成的异构多核系统，以Motion-JPEG作为测试程序对该模型进行实验分析。

4.1. 实验平台简介

Xtensa处理器是Tensilica公司推出的一种可配置处理器，该处理器除了具有一组固定的指令集之外，还可以通过TIE功能扩展指令集以加速程序运行。Tensilica公司提供了该处理器基于SystemC的仿真模型。本文的实验平台是由3个Xtensa处理器仿真模型组成的异构多核系统，分别记为core0，core1，core2。

本文节选自：中国集成威廉希尔官方网站

编辑：jq