Journal of King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com多核处理器特区Kirana，*，S.作者声明：P.穆尼什？巴蒂亚？米斯拉aaBirla Institute of Technology and Science Pilani，333031 Rajasthan，India计算机科学与信息系统系bBirla Institute of Technology and Science Pilani，333031 Rajasthan，India电气电子和仪器系接收日期：2014年10月13日;修订日期：2015年4月3日;接受日期：2015年4月14日2015年11月23日在线发布摘要多核处理器在同一个芯片上有多个处理核心单核和多核处理器在架构上是不同的。由于需要将单个指令调度到其中一个可用核上，因此它有效地减少了在多核处理器的单个核上执行的指令数量由于多核处理器的每个核都有一个私有寄存器文件，因此减少了寄存器压力。为了有效地利用多核处理器的潜在优势，必须将顺序程序分割成小的并行区域，以便在不同的核上运行，并且必须为这些核中的每个核进行寄存器分配本文讨论了可以在多核上调度的细粒度线程的寄存器分配算法溢出的计算和它的效果的加速，功耗和性能每功率比较的RAW基准套件。©2016制作和主办由Elsevier B.V.代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍再加上计算机体系结构领域的技术进步和对更快处理的无情需求，导致了多核处理器的发展。多核处理器在同一个处理器*通讯作者。电子邮件地址：dck@pilani.bits-pilani.ac.in（哥伦比亚特区）Kiran ） ， pilan.bits-pilani.ac.in （ S.Gurunarayanan ） ，jpm@pilan.bits-pilani.ac.in （ J.P.Misra ） ， munish.bhatia.gmail.com（M.Bhatia）。沙特国王大学负责同行审查芯片每个内核都有一个独立的寄存器文件，能够执行完整的指令集架构（ISA）。为了开发多核处理器的能力，在代码并行化和多处理领域进行了大量的研究。在多核系统上运行的应用程序并不能保证性能的提高，直到应用程序被明确地设计为利用处理器芯片上存在的多个核。要开发利用多核的应用程序，主要有两种方法。第一种方法是开发可以在给定处理器的多个核心上调度的显式并行代码，另一种方法是使用编译器通过识别可以并行执行的指令集来提取细粒度并行性。目前，几个新方案http://dx.doi.org/10.1016/j.jksuci.2015.04.0011319-1578© 2016制作和主办Elsevier B. V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词多芯;细粒度并行;调度;寄存器分配86D.C. Kiran等人源代码前端DAGDAG2CFGCFG细晶粒转换器线程.asm汇编代码发生器寄存器分配器提取器子块时间表正在探索有助于粗粒度并行的模型和不同的方式来利用线程和数据级并行。在顺序程序中，编译器驱动的细粒度并行性的开发在研究界还很少多核处理器可以通过向编译器和操作系统公开底层 架 构 细 节 来 利 用 给 定 代 码 的 细 粒 度 并 行 性（Zhong，2008）。该体系结构可以被设计为支持执行指令所需的最小操作集，并且提取细粒度并行性的任务可以留给编译器和运行时环境来实现。运行时环境可以管理资源分配，提取- ING不同的核心并行结构，并根据编译器生成的信息进行调度支持这些特征的一些架构是Power4（Tendler等人， 2002）、独眼巨人（Cascaval等人，2002）和RAW（Waingold等人，1997）架构。多核环境具有多个互连的瓦片，并且在每个瓦片上可以有一个类似RISC的处理器或核心。每个核心都有指令库、数据存储器、PC、功能单元、寄存器文件和源时钟。FIFO（队列）用于通信。在这里，寄存器文件是分布式的，消除了小寄存器名称空间的问题。从细粒度并行实现性能增益的挑战是从给定的单线程应用识别细粒度线程，并在多核处理器的不同核上调度这些线程。 已经相当关注通过自动细粒度并行化来提高性能，其中顺序程序被分成并行细粒度线程并被调度到多个核上（Kiran等人，2011 a，b; Kiran等人， 2012年）。一般来说，多核处理器有一个专用寄存器文件，L1数据和指令缓存和共享L2缓存。L1数据高速缓存的有限大小决定了要放入高速缓存的最佳数据量数据放置中的错误选择会导致内存停顿增加和资源利用率降低被调度到不同核上的细粒度线程需要从它们被调度在其上的核的相应寄存器堆被分配寄存器过去提出了各种寄存器分配方法（Chaitin，1982;Norris和Pollock， 1994; Gupta 等人，1994; Callahan和Koblenz，1991; Lueh等人，2000; Chow和Hennessy，1984; Briggs 等 人 ， 1989; Poletto 和 Sarkar ， 1999;Mossenbock和Pfeiffer，2002; Fu和Wilk，2002;Burkard等人，1984; Todd等人，1996年）。大多数寄存器分配算法假设CPU具有规则的寄存器文件，这些算法不能适应不规则的对于不规则架构，已经提出了几种解决方案，但如果不考虑具体的实现细节，很难实现最佳寄存器分配（Koes和Goldstein，2005; Kong和Wilken，1998; Scholz和Eckstein，2002）。在多核处理器的情况下，处理器的每个核具有单独的寄存器文件，并且最佳寄存器分配是极其重要的。多核体系结构是一个期待寄存器分配新思维的领域建议的工作探讨了多核架构的寄存器分配所需的针对多核处理器上可调度的细粒度线程，提出了两种寄存器分配算法：启发式3和启发式4结果与现有的寄存器分配方法启发式1和启发式2相比，所提出的寄存器分配策略以及考虑每个核心上的多个私有寄存器文件，通过检查寄存器压力来递增地构建干扰图，而不是现有的寄存器分配方法，其构建全局干扰图，然后执行简化以减少寄存器压力。本文的其余部分组织如下。第2节介绍了拟议工作的背景。它还讨论了一些最近的作品有关的子块创建或细粒度线程提取和调度技术。第3节详细介绍了多核环境下提出的寄存通过一个说明性的例子，在所提出的算法中涉及的步骤在第3.4节中给出。第四节对结果进行了分析和讨论，第五节提出了结论和未来工作的方向。2. 背景本节介绍拟议工作的背景建议的工作与以下工作一起进行。平行区域形成或提取细粒线（Kiran等人，2011年a）。将并行区域或细粒度线程调度到多个核上（Kiran等人，2011年b，2012年）。编译器的工作流程如图所示。1.一、两个额外的通行证被引入到编译器的正常流。细粒度提取器模块和调度器模块。细粒度提取器模块分析CFG的基本块，并将它们中的每一个划分为多个子块。调度器模块生成可以在处理器的不同核上同时执行的多寄存器分配器 模 块 使 用 Chaitin 的 寄 存 器 分 配 方 法 （ Chaitin ，1982）执行寄存器2.1. 细晶粒线细粒度线程是通过分析程序的控制流图（CFG）的基本块中的指令依赖性而形成的子块。2011年a。图1中的细粒线提取器模块创建子块。创建的子块是不相交的，可以并行运行。在图3中，CFG具有4个基本块（Bp）。不交集合运算图1编译器流程●●多核处理中细粒度线程的分配87被应用于每个基本块以形成子块SBi。属于基本块Bp的子块SBi被称为SBi Bp。2.2. 子块依赖图SDG是图G（V，E），其中每个顶点v e V是表示为SBi B p的子块。在两个依赖顶点SBie Bp和SBje Bq之间添加边eeE，其中p图 3（a）中，属于基本块B2的子块SB 1依赖于属于基本块B1的子块SB1，则将其表示为SB1B1？子块SB1 B2和子块SB1 B2应该仅在子块SB1 B1完成其执行之后被调度。2.3. 调度器调度器（块间调度器）识别CFG中的所有独立子块并制定调度（Kiran等人， 2012年）。调度器尝试为每个核心生成调度每个调度表都包含一个可以在内核上调度的子块列表通常，如果子块SBi B p的依赖列表为空，则全局调度器从子块依赖矩阵中选择子块SB i Bp子块依赖矩阵是SDG的锯齿矩阵表示，如图所示。 其中第一列包含SDG中的所有子块的列表，并且特定子块所依赖的所有子块在相应行中列出。一旦SBi Bp被调度并完成其执行，其对应的条目将从依赖列表中删除。子块执行时间的计算方法是将子块中的指令数乘以执行一条指令所需的平均时间虽然每个指令执行可能花费不同的时间量，但不失一般性，假设执行指令所花费的平均时间是恒定的。在核上调度子块的决定基于子块SBi Bp的不变量，诸如调度延迟、计算的就绪时间（Trdy）和完成时间（Tfns）。还考虑核的当前调度时间（Tsch）和可用时间（Tca）以检查核调度子块的可用性子块的Ready_time（Trdy）是子块从其所有依赖性中释放并且准备好在核上调度的时间子块的Finish_time（Tfns）是调度子块时的开始时间间隔和完成执行所花费的总时间的总和调度时间（Tsch）是可能在核上调度就绪子块的时间。它是通过找到当前执行的子块的完成时间（如果有的话）和要调度的子块的Trdy给定核的核可用时间（Tca）是该核上当前执行的子块具有空依赖列表的子块被移动到读取列表，该读取列表以子块的等待时间的降序排列。就绪子块被调度在具有最小Tca值的核上。为了计算SDG中的给定子块SBiBp的调度延迟，标识通向叶节点的所有路径。从子块SBiBp开始到叶节点的每个路径可以被认为是线性列表。计算每个路径的调度延迟，选择来自具有高延迟的路径的子块SBi Bp用于调度。调度延迟是线性表中所有节点的执行时间之和，它可以通过对它是假设执行时间是propor- tional的指令数。SDG中的叶子子块SBi Bp的调度延迟是该子块中的指令的总数非叶子子块SBi Bp的等待时间是其所有直接后继子块的最大等待时间和SBiBp中的指令总数的总和。 图 4 a显示了为双核处理器生成两个调度。3. 多核处理器本节描述如图所示的建议的寄存器分配框架。 二、在SDG创建期间捕获实时变量在SDG中，子块被表示为顶点V，并且子块之间的依赖性由有向边E表示。子块SBj Bq的Live_in变量的总数是SBj Bq和SBi Bp之间的依赖度，即依赖度中涉及的变量的总数。子块中的活动变量SBj Bq是子块中定义的所有传入边和变量的依赖度的总和初始干扰图是为子块列表中列出的每个子块本地构建的。这些干涉图大多是k-可着色的，如果不是，则它们被简化并且要溢出的变量被捕获。溢出代码在寄存器分配阶段之后插入。全局干涉图是通过逐个合并各个局部干涉子图并检查所得到的子图是否是k-可着色的来递增地构造的。该算法使用合并算子递增地合并子块以形成超级子块。合并 操 作 是 使 用 两 个 功 能 模 块 mergeSubblocks 和checkSimplifiable构建的，并产生一个超级子块H（h1，h2，h3.. . hx），其干涉图是k-可着色的.超级子块通过将最大依赖指令推到核心上以供执行来确保时间局部性。 由于超级子块是可k着色的，所以需要零溢出，并且指令将保持在各个核的私有存储器内，直到所有指令提交而不进行外部存储器引用。在寄存器分配阶段，超级子块中的变量被分配寄存器。3.1. 合并运算符合并运算符通过合并明细表中列出的子块的干涉图来产生k-可着色的超级子块。在创建超级子块时，必须检查并满足子块依赖性和可验证性条件。合并运算符的算法如下所示。算法1中使用的条件如下所列C1：如果SBj依赖于SBk。C2：如果子块SB的T_fns为SBi的T<_rdy。C3：如果SB k依赖于SB i并且SBk的Trdy> SB j的Tfns。88D.C. Kiran等人捕捉实时范围Int生成本地ph参考点聚结C4：如果SB i和SB j的干涉图是可分解的，并且合并后的结果干涉图也是可分解的。D1：不合并子块。D2：合并子块以一起调度和分配该算法通过选择两个子块SBi和SBj开始，随后是依赖性约束检查。这些约束通过条件C1、C2和C3来实施。这些条件是从全局调度程序使用的不变量中导出的。假设SBj列在处理器核心Cra的调度中，则检查条件C1、C2和C3以找出子块SBj是否可以与其前趋子块SBi合并以形成超级子块。如果子块SB j不依赖于子块SBk并且SBk被调度在不同的核CRb上，则子块SBj可以与其前趋SBi合并，其中a-b在SBj依赖于子块SBk的情况下，当SBk和SBi具有不重叠的执行时，它可以与它的前一个合并，即SBk的完成时间小于SBi的准备时间。条件C1和C2用于检验这两种可能性。条件C3有助于减少子块SBk的等待时间。如果在核心Crb上调度的子块SBk依赖于SBi，则将SBi与其后继者合并以形成超级子块将使SBk等待直到超级子块扩展完成。为了确保超级子块的零溢出，检查可验证性条件C4。在3.4节中讨论了一个说明合并操作的例子。分配寄存器插入溢出代码合并运算符合并子块检查图2修改的寄存器分配框架。不相交集森林（Cormen等人， 2001）算法可以用于合并干涉图。采用按秩并启发式算法提高并运算的运行时间，采用路径压缩算法提高求集运算的运行时间。3.2. 寄存器分配在这个阶段中，超级子块中的活动变量被分配寄存器。由于在超级子块的形成期间检查可验证性条件，因此消除了插入溢出代码的需要。着色顺序的选择由于干涉 图 是 具 有 单 纯 顶 点 的 弦 ， 因 此 简 化 了 （ Pereira 和Palsberg，2005）。投影出单纯顶点的边首先被推到颜色堆栈上，并继续直到所有边都被推到堆栈上。一旦所有的边都被推到堆栈上，颜色分配模块就会从堆栈中弹出这些边，为冲突的边分配不同的颜色。颜色堆栈用于区分着色的优先级，即堆栈中较高位置的边缘具有较高的优先级。3.3. 插入溢出代码在该阶段中，为溢出变量插入溢出代码加载/存储，该溢出变量在子块的初始干扰图的构造期间被捕获。然而，超子块的干涉图是k-可着色的，这消除了溢出代码的需要。在创建超级子块和寄存器分配阶段之后插入溢出代码以保持SSA的属性（Cytron等人，1991;Hack和Goos，2006; Pereira和Palsberg，2006）。3.4. 工作示例本节使用示例说明了针对每个具有四个寄存器的核的所提出的寄存器分配方法。 为了提取细粒度的并行线程，创建不相交的子块和SDG，如图所示 。第3（a）段。由全局调度器为双核机器创建的调度如图所示。第4（a）段。通过使用调度列表生成的超级子块如图4（b）所示。图4（c）展示了子块SB2 B1和SB2 B3 sched中的指令在双核机器的核心2上使用子块SB2B1和其后继SB 2 B 3被调度在核心2上，如图2所示。第4（a）段。子块SB2 B3不满足条件C1，因为它不依赖于任何其它子块。条件C3是算法1.合并运算符合并操作（子块SBi，子块SBj）开始初始化SB j是在用于核心Cr a的时间表中SB i的后继者。SBk是其它核心Crb的调度中的子块。如果（C1&C2C4）开始合并子块以调度和分配寄存器。端否则如果（！C1）开始如果（C3C4）开始&合并子块以调度和分配寄存器。端端否则开始不要合并子块。端端多核处理中细粒度线程的分配89双 核心Core1Core2SB3B 1SB2B 1SB1B 1SB2B 3SB1B2SB2B 2SB1B 3SB4B 4SB1B4SB 2B4SB3B 4双核心Core1Core2SB3B1SB 1B1SB2B1SB 2B3SB1B 2SB1B3SB 1B4SB2B2SB4B4SB子块SB2B 1副座SB2B 3F0=11;G0=42;H0=F0/G0;I0=G0+H0;G1=G0-I0;H1=G1+I0;F1=G1+H1;U0=G1+F1;V0=G1+H1;W0=U0+V0;V1=W0*V0;U1=W0-V1;W1=U1*W0;（一）（b）第（1）款不满足，因为SB 2 B 2所依赖的子块（即子块SB 3 B1）的T fns不小于SB 2 B 3的T rdy。因此，决定D1不将子块SB2 B2合并到超级子块中。4. 实验本节分为五个小节。第4.1节详细介绍了用于实验的体系结构、编译器和基准测试第4.2节针对不同的寄存器分配策略给出了详细的评估标准在4.3节中简要解释了不同的寄存器分配策略。第4.4节从寄存器分配方法的算法复杂性方面讨论了编译成本中表2图3（a）子块依赖图，（b）子块依赖图，dency矩阵(a)(b)（c）第（1）款图4（a）为双核处理器生成的子块列表(b) 其干扰图是k-可着色的超级子块，（c）子块SB2 B1和SB2 B3中的指令。第4.5小节给出了不同化学品的溢出情况和图。图6和图7分别示出了当针对双核和四核处理器编译程序时溢出对加速、功率和每功率性能的影响。4.1. 多核架构所使用的目标体系结构模型能够执行细粒度线程。多核处理器是网格处理器家族的一个例子，它通常由同构执行节点阵列组成。该核心相当于一个单线程的单处理器，能够执行1指令，每周期和每个核心有8个通用寄存器启发式1启发式2启发式3启发式42.521.510.50测试案例测试案例测试案例1 2 3 41 2 341 2 3 4加速功率性能/功率(c)图5（a）子块SB2 B1的干扰图，（b）子块SB2 B3的干扰图，（c）合并子块的干扰图。也不满足，因为没有其它子块依赖于SB2 B1。从图5（a）和（b）中可以明显看出，的干涉图满足条件C4，图6双核机器上的加速、功耗和性能/功耗比较。启发式1启发式2启发式3启发式443.532.521.5子块SB B和SB B。 图5（c）进一步示出了12 1 2 30.5子块SB2B1和SB 2B2的合并干扰图SB2 B3也是可着色的（3可着色），因此子块SB2 B1和SB2 B3被合并以形成单个超0测试案例测试案例测试案例1 2 3 41 2 341 2 3 4子块。尝试调度子块SB2 B3，与其后继SB2 B2合并到超级子块中加速功率性能/功率失败了由于子块SB 2 B 2依赖于子块SB 3 B 1，因此满足条件C1。条件C2也是图7四核机器上的加速、功耗和性能/功耗比较F0U0H1H0G0I0F1G1F1V0W0G1H1V1U1W1(a)（b）第（1）款G0G1H1F0H0U0V0V1W0U1W1B 1SB1SB2SB3B 2SBB 3SB2SB1SB3SB2SB4B 4SB2SB1子块依赖性列表1SB1B 12SB2B 13SB3B 14SB1B 2SB1B 15SB2B 2SB3B 16SB1B 3SB3B 17SB2B 3SB2B 18SB1B 4SB1B 29SB2B 4SB1B 3SB2B 210SB3B 411SB4B 4SB2B 2SB2B 390D.C. Kiran等人[8美元。$r15]。每个内核都有指令存储器，数据存储器，PC、功能单元、寄存器文件和源时钟。FIFO用于内核间（在不同内核上执行的线程）通信。在这里，寄存器文件是分布式的，消除了小寄存器名称空间的问题。拟议的工作使用开源的Jackcc编译器（Jack，2013）。用于评估所提出的工作的测试用例取自原始基准套件（Babb等人， 1997年）。目标体系结构是一个不规则的体系结构，因为寄存器文件是分布式的。这种设计的原则是避免与其他功能单元进行不必要的、冗余的、复杂的连接，从而减小大面积，提高访问速度，降低功耗。4.2. 评价标准本节中讨论的结果基于目标体系结构的模拟模型，包括双核和四核变体。通过对DES、快速傅立叶变换、归并排序等4种极端情况下的溢出代价、加速比、功耗和功耗性能的分析和比较，给出了测试结果。结果被标准化为基本“单元核”的性能度量全局调度器被设计为执行功率优化，即， 如果使用四个核实现的性能可以仅使用三个核实现，则通过保持第四个核空闲或将其用于某些其它计算，仅使用四核机器的三个核来执行给定任务（Kiran等人，2012年）。在一个四核机器上的三个活动的核心的结果计算了四种不同的寄存器分配策略所引起的溢出量，并比较了它们对加速比、功耗和单位功耗性能的影响。4.3. 寄存器分配算法本节描述了多核处理器架构的不同寄存器分配算法，并对其结果进行了比较。第一个启发式算法使用调度器生成的原始列表进行寄存器分配。每个子块中的指令使用Chaitin的方法在本地分配这种方法导致减少编译时间，但执行时间增加，因为个别子块被分配线程需要数据移动。第 二 种算 法 将 寄 存 器 分 配 与 全 局 调 度 相 结 合（Kiran等人， 2013年）。它主要针对相位排序问题，导致穷人的优化。考虑到寄存器要求，调度器通过选择依赖矩阵中的子块来为多个核创建调度，以维持它们的执行顺序。启发式3和启发式4遵循如图4所示的所提出的寄存器分配框架。为了促进全局调度，这些算法递增地合并由调度器生成的子块列表中的子块以产生超级子块列表。超级子块通过将最大依赖指令推到表1算法复杂度比较。启发式1复杂性O（n*log（n））启发式2时间复杂度O（m2*n2）启发式3启发式4时间复杂度O（n）时间复杂度O（m*n2）核心执行。这些算法有助于以增加编译时间为代价生成优化的代码。在启发式3中，通过合并子块来创建超级子块。子块的合并通过合并子块的干扰图并且通过检查子块依赖性、 被合 并的 子块 的Ready_time（Trdy）和Finish_time（Tfns）来执行。在这些算法中，类似于Chaitin如果干涉图不是k-可着色的，则将其简化并插入溢出代码。由于每个超级子块可以被分配一个线程，因此与算法1相比，它改善了执行时间，但是可能会添加更多的溢出代码，因为干扰图可能不是k-可着色的。建议的第四启发式克服了启发式1 - 3的局限性在这种方法中，通过向启发式算法3添加可验证性条件来创建超级子块可重构性条件确保超级子块的干扰图是k-可着色的，从而导致零溢出码。4.4. 算法复杂度在本节中，提出了所提出的寄存器分配启发式算法表1比较了其他三种算法的复杂性。设m和n是子块的数量和活动范围或变量的数量。每个子块检查其他核上的依赖子块或父代子块的存在所消耗的时间是O（m）。复杂度是O（n）的因此，对于启发式算法3，所有迭代（对于m个子块）的复杂度为O（m*n logn）。在启发式算法4中，验证各个干扰图的可扩展性、合并两个干扰图以及验证新图是否可扩展所花费的时间为O（n2）。这是一个复杂度为O（nlogn）的算法。因此，checkSimplifiable和mergeSub-blocks模块的总体复杂度为O（n2+nlogn），即O（n2）。因此，所有迭代的复杂度（对于m个子块）时间复杂度为 O（m*n2）。乍看起来，启发式4似乎在编译时间上有很大的增加。但这种复杂性是可以接受的，当考虑到整个编译过程时，因为包括寄存器分配在内的完整代码生成器贡献了不到总编译时间的20%。4.5. 结果与分析启发式1不贡献溢出代码，因为子块的干扰图是k-可着色的。该启发式算法要求运行时环境将线程分配给各个子块，并处理来自内存的相应频繁●多核处理中细粒度线程的分配91由于溢出，加速降低。这导致与试探法4相比更高的功耗和降低的每功率性能。四核处理器上的测试用例3显示，在速度方面，所有性能都相同两个仓库启发式4在四核处理器上的所有测试用例中表现更好。启发式4还提供了更好的性能方面的编译时间。从图中可以明显看出。从图6和图7可以看出，与启发式算法1、2和3相比，启发式算法4的整体性能在每功率性能方面更好。4.6. 关于登记册启发式2试图通过在调度期间分配寄存器来解决阶段排序问题，但对性能有一点妥协。这种启发式方法会导致合理数量的溢出代码，并增加编译时间。启发式3通过将线程分配给超级子块而不是子块来克服启发式1所面临的问题但是这种启发式方法会产生更多的溢出代码。启发式4通过检查超级子块的可验证性条件，结合启发式1和3的特征，导致溢出代码消除和减少的运行时环境开销。使用第四种润滑剂时的溢出量如表1所示。当使用启发式1对子块列表进行寄存器分配时，溢出几乎为零，因为子块是通过考虑寄存器需求来创建的。类似地，由于超级子块的干扰图是k-可着色的，因此所提出的启发式算法4产生零溢出。由于试探法2不是针对功率优化设计的，因此表2中的3个活动核的结果留空。性能增益是调度器和寄存器分配方法的组合效果图中的结果。图6和图7描绘了溢出对双核和四核处理器的加速、功率和性能/功率的影响。即使在零溢出的情况下，启发式算法1的每幂加速和性能也较低这是由于本地调度程序的限制本地调度器为每个子块分配一个线程，从而导致更高的数据移动。启发式2显示了测试用例2的更好的加速，这是因为集成调度器能够有效地为双核处理器创建在四核处理器上测试用例2的启发式算法2的性能由于内存争用而恶化加速-由于插入额外的溢出指令，溢出增加时速度会降低当启发式3应用于测试用例2、3和4以在双核机器上执行时，本节讨论当寄存器数量变化时，建议的寄存器分配的有效性。上一节中显示的结果是针对每个具有8个通用寄存器的内核的增加寄存器数量的效果导致当使用逻辑1、2和3时溢出减少，这是显而易见的。干涉图是通过检查依赖性和可扩展性条件逐步建立的。增加寄存器的数量可以导致超级子块中的指令数量增加，从而导致优化的代码生成，需要更少的执行时间。改进的执行时间可以归因于较大的超级子块将需要较少的数据移动到存储器和从存储器移动。根据弦图的色多项式理论，一个最大团为n的弦图的色数为n。SSA形式程序的干涉图中最大团为3，因此大多数情况下它是三色的。本工作中使用的基准程序的干扰图显示了以下k其中k的范围从3到7。子块是k可着色的，超子块也是k可着色的可着色的子块是k可着色的，并且超级子块是k+1可着色的。如果使用的寄存器数量减少到3个，则性能不会发生变化。此外，如果使用多于8个寄存器，则性能将不会改变，因为在不同核上调度的子块之间存在依赖性5. 结论这项工作提出了一个寄存器分配机制，用于多核处理器。所提出的机制，这已被量身定制的多核处理器上使用，承诺得到更好的结果比那些使用传统的寄存器分配机制构建的单核处理器。文中给出的实验结果证实了这一事实。该算法考虑了多个核的存在和它们单独的寄存器文件的存在，并利用这一途径来实现更好的寄存器分配结果。为细粒度线程分配寄存器的四种方法●●●●●●●●●●●●●表2溢出。算法启发式1，4启发式2启发式3测试用例1 双核010四核0113-活性01核测试用例2 双核013四核0103-活性00核测试用例3 双核003四核0003-活性00核测试用例4 双核012四核0023-活性02核●92D.C. Kiran等人讨论了溢出，加速，功耗和每功率的性能进行了比较，为RAW基准套件的程序生成的代码。使用这种寄存器分配技术的多核处理器是更有效的比使用传统的寄存器分配和灰的方法。所提出的工作可以扩展到每个核具有多个执行单元（浮点单元、整数单元）的多核处理器（Bhathia等人， 2013年）。虽然寄存器文件不是基于类型（浮点寄存器、整数寄存器）分布的，但在执行寄存器分配时可以考虑寄存器要求和指令类型的比例。引用Babb，J.，弗兰克，M.，Lee，V.，Waingold，E.，巴鲁阿河泰勒·J金，M.，Devabhaktuni，S.，阿加瓦尔，A.，1997.RAW基准套件：通用计算的计算结构。在：第五届IEEE基于FPGA的定制计算机器研讨会论文集134.Bhathia，Munish，Kiran，D.C. Gurunarayanan，S.，Misra，J.P.，2013. 多核处理器上的细粒度线程调度：具有多个功能单元的内核。ACM计算Briggs，P.，库珀，K.D.，肯尼迪，K.，托尔聪湖，1989. 用于寄存器分配的着色算法。 ACM SIGPLAN程序设计语言设计与实现会议论文集。ACM，pp. 275-284。Burkard ， Rainer E ， ela ， Eranda C ， Pardalos ， Panos M ，Pitsoulis，Leonidas S，1984.二次分配问题。欧洲J 操作员Res.15，283-289.Callahan，David，Koblenz，Brian，1991.通过分层图着色的寄存器分配。在：ACM SIG-2010会议程序设计语言设计和实现多伦多安大略省，加拿大，页。26比28卡斯卡瓦尔角，Castanos，J.，塞兹湖Denneau，M.，古普塔，M.，Lieber，D.，Moreira，J.E.，Strauss，K.，沃伦，H.S. ， Jr. 2002. 细 胞 计 算 的 多 线 程 架 构 评 估 。 在 ：Proceedings的第8届国际研讨会高性能计算机体系结构，页。311-322.Chaitin，G.，1982.通过图着色的寄存器分配和溢出。在：会议记录的SIGPLAN研讨会上的建筑，pp。98比105Chow，Fredrick，Hennessy，John，1984.基于优先级着色的寄存器分配。见：ACM SIGPLAN研讨会上关于建筑结构的SIGPLAN通知，19（6）。Cormen，T.，Leiserson，C.，里维斯特河，2001年算法介绍-Rithms The MIT Press，Cambridge，MA.塞隆河，Ferrante，J.，Rosen，B.K.，Wegman，M.N.，Zadeck，F.K.，一九九一年高效计算静态单赋值形式和控制依赖图。ACM翻译计划。Lang.Syst.13（4），451-490.Fu，Changing，Wilk，Kent，2002.一个更快的优化寄存器分配器。第35届IEEE/ACM国际微架构研讨会（MICRO-35）。Gupta，Rajiv，Lou Soffa，Mary，Ombres，Denise，1994.使用团分隔符通过着色实现高效的寄存器分配。ACM翻译计划。Lang.Syst.16（3），370-386.哈克，S.，古斯，G. 2006.多项式时间内SSA形式程序的最优寄存器分配。INF. 过程Lett. 98（4），150-155。希尔，医学博士 马蒂，医生 2008.多核时代的阿姆达尔IEEE计算，33-38吴东赫，李显新，2008.扩展阿姆达尔定律以实现众核时代的节能计算。IEEE计算，24-31基兰特区Gurunarayanan，S.，Misra，J.P.，2011年a。 驯服编译器以与多核处理器一起工作。IEEE Conf. Process Autom.控制计算基兰特区Radheshyam，B.，Gurunarayanan，S.，Misra，J.P.，2011年b。多核处理器的调度器辅助动态调度。IEEE Conf.Process Autom.控制计算基 兰 特 区 Gurunarayanan ， S. ， Faizan ， Khaliq ， Nawal ，Abhijeet，2012.用于多核架构的更高效和功率感知的指令级并行。国际生态友好计算和通信系统，发表在计算机和信息科学通信（CCIS）。Springer-Verlag，pp. 9-17号基兰特区Gurunarayanan，S.，Misra，J.P.，2012.用于多核处理器的编译器驱动的块间并行性。在：第六届国际信息处理会议，发表在计算机和信息科学通信（CCIS）。史普林格出版社基兰特区Gurunarayanan，S.，Misra，J.P.，Yashas，D.，2013.多核架构的集成调度和寄存器分配。在：IEEE并行计算技术会议PARCOMPTECH-2013，由C-DAC在IISC班加罗尔组织Koes David，Goldstein，Seth Copen，2005.一种用于非规则体系结构的渐进式寄存器分配器。In：CGO，pp.269比280。Kong，Timothy，Wilken，Kent D.，1998年 针对不规则架构的精确寄存器分配。微建筑国际研讨会. ACM，pp. 297-307Lueh ， Guei-Yuan ， Gross ， Thomas ， Adl-Tabatabai ， Ali-Reza，2000年。基于融合的寄存器分配。ACM翻译计划。浪22（3），431-470.Mossenbock，Hanspeter，Pfeiffer，Michael，2002.SSA形式和寄存器约束上下文中的线性扫描In：CC，LNCS，pp. 229-246诺里斯，辛迪，波洛克，洛里L.，1994.程序依赖图上的寄存器分配。SIGPLAN 94-6/94。Pereira，Fernando Magno Quintao，Palsberg，Jens，2005.基于弦图着色的寄存器分配。In APLAS，Springer，pp. 315-329Pereira，Fernando Magno Quintao，Palsberg，Jens，2006.经典SSA消除后的寄存器分配是NP完全的。软件科学和计算结构的基础。斯普林格。Poletto，Massimiliano，Sarkar，Vivek，1999年。全局线性扫描寄存器分配。ACM翻译计划。Lang.Syst.21（5），895-913。Todd，A.，Proebsting，Fischer，Charles N.，1996.概率寄存器分配，ACM SIGPLAN' 9 2 PL D 1 -6 / 9 2 / C A 。Scholz，Bernhard，Eckstein，Erik，2002.不规则架构的寄存器分配。LCTES/内窥镜。ACM，pp. 139-148。The Jack Puncher，http://jackcc.sourceforge.net.Tendler，J.M.，Dodson，J.S.，菲尔兹，杰杰，Le，H.，Sinharoy，B.，2002年。 Power 4系统微体系结构。IBMJ.Res. Dev. 46（1），5-6.Waingold，E.，泰勒，M.，Srikrishna，D.，Sarkar，V.，李，W.，Lee，V.，金，J.，弗兰克，M.，Finch，P.，巴鲁阿河Babb，J.，Amarasinghe，S.，阿加瓦尔，A.，1997.将其全部暴露给软件：原始机器。Computers 30（9），86-93.Zhong，Hongtao，2008.在多核处理器上加速单线程应用程序的架构和并行机制（Ph.D. Dissertation）。美国密歇根大学安娜堡分校（ACM）。
