公开(公告)号：US09459851B2

公开(公告)日：2016-10-04

申请号：US12823244

申请日：2010-06-25

申请人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

发明人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

IPC分类号： G06F9/45

CPC分类号： G06F8/4442

摘要： Mechanisms are provided for arranging binary code to reduce instruction cache conflict misses. These mechanisms generate a call graph of a portion of code. Nodes and edges in the call graph are weighted to generate a weighted call graph. The weighted call graph is then partitioned according to the weights, affinities between nodes of the call graph, and the size of cache lines in an instruction cache of the data processing system, so that binary code associated with one or more subsets of nodes in the call graph are combined into individual cache lines based on the partitioning. The binary code corresponding to the partitioned call graph is then output for execution in a computing device.

摘要翻译： 提供了用于布置二进制代码以减少指令高速缓存冲突未命中的机制。 这些机制产生一部分代码的调用图。 调用图中的节点和边被加权以生成加权调用图。 然后根据权重，调用图的节点之间的亲和度和数据处理系统的指令高速缓存中的高速缓存行的大小来分配加权调用图，使得与一个或多个节点的子集相关联的二进制代码 调用图被组合到基于分区的各个高速缓存行。 然后输出与划分的调用图对应的二进制代码，以在计算设备中执行。

公开(公告)号：US08789025B2

公开(公告)日：2014-07-22

申请号：US12835820

申请日：2010-07-14

申请人： John K. P. O'Brien ,  Kai-Ting Amy Wang ,  Mark Yamashita ,  Xiaotong Zhuang

发明人： John K. P. O'Brien ,  Kai-Ting Amy Wang ,  Mark Yamashita ,  Xiaotong Zhuang

IPC分类号： G06F9/45

CPC分类号： G06F8/441

摘要： A mechanism is provided for path-sensitive analysis for reducing rollback overheads. The mechanism receives, in a compiler, program code to be compiled to form compiled code. The mechanism divides the code into basic blocks. The mechanism then determines a restore register set for each of the one or more basic blocks to form one or more restore register sets. The mechanism then stores the one or more register sets such that responsive to a rollback during execution of the compiled code. A rollback routine identifies a restore register set from the one or more restore register sets and restores registers identified in the identified restore register set.

摘要翻译： 提供了一种用于路径敏感分析以减少回滚开销的机制。 该机制在编译器中接收要编译的程序代码，以形成编译代码。 该机制将代码分为基本块。 该机制然后为一个或多个基本块中的每一个确定恢复寄存器集合以形成一个或多个恢复寄存器集。 该机制然后存储一个或多个寄存器集，以便响应于在编译代码的执行期间的回滚。 回滚程序从一个或多个恢复寄存器集中识别恢复寄存器集，并恢复在所识别的恢复寄存器集中识别的寄存器。

公开(公告)号：US08522225B2

公开(公告)日：2013-08-27

申请号：US12823204

申请日：2010-06-25

申请人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

发明人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

IPC分类号： G06F9/45

CPC分类号： G06F8/4436 ,  G06F8/433 ,  G06F8/4442

摘要： Mechanisms are provided for rewriting branch instructions in a portion of code. The mechanisms receive a portion of source code having an original branch instruction. The mechanisms generate a branch stub for the original branch instruction. The branch stub stores information about the original branch instruction including an original target address of the original branch instruction. Moreover, the mechanisms rewrite the original branch instruction so that a target of the rewritten branch instruction references the branch stub. In addition, the mechanisms output compiled code including the rewritten branch instruction and the branch stub for execution by a computing device. The branch stub is utilized by the computing device at runtime to determine if execution of the rewritten branch instruction can be redirected directly to a target instruction corresponding to the original target address in an instruction cache of the computing device without intervention by an instruction cache runtime system.

摘要翻译： 提供了用于在一部分代码中重写分支指令的机制。 该机制接收一部分具有原始分支指令的源代码。 机制为原始分支指令生成分支存根。 分支存根存储关于原始分支指令的信息，包括原始分支指令的原始目标地址。 此外，机制重写原始分支指令，使得重写的分支指令的目标引用分支存根。 此外，机制输出编译代码，包括重写的分支指令和分支存根，以供计算设备执行。 计算设备在运行时利用分支存根来确定重写的分支指令的执行是否可以被直接重定向到与计算设备的指令高速缓存中的原始目标地址相对应的目标指令，而无需指令高速缓存运行时系统的干预 。

公开(公告)号：US08087010B2

公开(公告)日：2011-12-27

申请号：US11861493

申请日：2007-09-26

申请人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

发明人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

IPC分类号： G06F9/45

CPC分类号： G06F8/4452

摘要： Mechanisms for selective code generation optimization for an advanced dual-representation polyhedral loop transformation framework are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization.

摘要翻译： 提供了用于高级双重表示多面体环转换框架的选择性代码生成优化的机制。 说明性实施例的机制通过提供用于在通过源代码的多面体环转换优化生成的中间表示中对各个语句实例执行代码生成变换的机制来解决已知的基于多面体循环变换的方法的弱点。 这些代码生成转换具有重要的属性，它们不改变中间表示中的语句的程序顺序。 该属性允许通过示例性实施例的新的重新导入路径将代码生成转换的结果提供给程序语句视图中的多面体循环变换机制，用于附加优化。

公开(公告)号：US20090307673A1

公开(公告)日：2009-12-10

申请号：US11861503

申请日：2007-09-26

申请人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

发明人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

IPC分类号： G06F9/45

CPC分类号： G06F8/452

摘要： A system and method for domain stretching for an advanced dual-representation polyhedral loop transformation framework are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization. In addition, mechanisms are provided for stretching the domains of statements in a program loop view of the source code to thereby normalize the domains.

摘要翻译： 提供了一种用于高级双重表示多面体环转换框架的域拉伸的系统和方法。 说明性实施例的机制通过提供用于在通过源代码的多面体环转换优化生成的中间表示中对各个语句实例执行代码生成变换的机制来解决已知的基于多面体循环变换的方法的弱点。 这些代码生成转换具有重要的属性，它们不改变中间表示中的语句的程序顺序。 该属性允许通过示例性实施例的新的重新导入路径将代码生成转换的结果提供给程序语句视图中的多面体循环变换机制，用于附加优化。 另外，提供了用于在源代码的程序循环视图中拉伸语句的域的机制，从而使域标准化。

公开(公告)号：US09600253B2

公开(公告)日：2017-03-21

申请号：US13444907

申请日：2012-04-12

申请人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

发明人： Tong Chen ,  Brian Flachs ,  Brad W. Michael ,  Mark R. Nutter ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Tao Zhang

IPC分类号： G06F9/45

CPC分类号： G06F8/4442

摘要： Mechanisms are provided for arranging binary code to reduce instruction cache conflict misses. These mechanisms generate a call graph of a portion of code. Nodes and edges in the call graph are weighted to generate a weighted call graph. The weighted call graph is then partitioned according to the weights, affinities between nodes of the call graph, and the size of cache lines in an instruction cache of the data processing system, so that binary code associated with one or more subsets of nodes in the call graph are combined into individual cache lines based on the partitioning. The binary code corresponding to the partitioned call graph is then output for execution in a computing device.

公开(公告)号：US08881159B2

公开(公告)日：2014-11-04

申请号：US13070811

申请日：2011-03-24

申请人： Alexandre E. Eichenberger ,  John K. P. O'Brien

发明人： Alexandre E. Eichenberger ,  John K. P. O'Brien

IPC分类号： G06F9/46 ,  G06F9/50

CPC分类号： G06F9/5066

摘要： Mechanisms are provided for allocating threads for execution of a parallel region of code. A request for allocation of worker threads to execute the parallel region of code is received from a master thread. Cached thread allocation information identifying prior thread allocations that have been performed for the master thread are accessed. Worker threads are allocated to the master thread based on the cached thread allocation information. The parallel region of code is executed using the allocated worker threads.

摘要翻译： 提供了用于分配用于执行并行区域代码的线程的机制。 从主线程接收到用于分配工作线程以执行代码并行区域的请求。 识别为主线程执行的先前线程分配的缓存线程分配信息被访问。 工作线程基于缓存的线程分配信息分配给主线程。 使用分配的工作线程来执行代码的并行区域。

公开(公告)号：US20120017203A1

公开(公告)日：2012-01-19

申请号：US12835820

申请日：2010-07-14

申请人： John K. P. O'Brien ,  Kai-Ting Amy Wang ,  Mark Yamashita ,  Xiaotong Zhuang

发明人： John K. P. O'Brien ,  Kai-Ting Amy Wang ,  Mark Yamashita ,  Xiaotong Zhuang

IPC分类号： G06F9/45

CPC分类号： G06F8/441

摘要： A mechanism is provided for path-sensitive analysis for reducing rollback overheads. The mechanism receives, in a compiler, program code to be compiled to form compiled code. The mechanism divides the code into basic blocks. The mechanism then determines a restore register set for each of the one or more basic blocks to form one or more restore register sets. The mechanism then stores the one or more register sets such that responsive to a rollback during execution of the compiled code. A rollback routine identifies a restore register set from the one or more restore register sets and restores registers identified in the identified restore register set.

摘要翻译： 提供了一种用于路径敏感分析以减少回滚开销的机制。 该机制在编译器中接收要编译的程序代码，以形成编译代码。 该机制将代码分为基本块。 该机制然后为一个或多个基本块中的每一个确定恢复寄存器集合以形成一个或多个恢复寄存器集。 该机制然后存储一个或多个寄存器集，以便响应于在编译代码的执行期间的回滚。 回滚程序从一个或多个恢复寄存器集中识别恢复寄存器集，并恢复在所识别的恢复寄存器集中识别的寄存器。

公开(公告)号：US20090083724A1

公开(公告)日：2009-03-26

申请号：US11861449

申请日：2007-09-26

申请人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

发明人： Alexandre E. Eichenberger ,  John K. P. O'Brien ,  Kathryn M. O'Brien ,  Nicolas T. Vasilache

IPC分类号： G06F9/45

CPC分类号： G06F8/447

摘要： A system and method for advanced polyhedral loop transformations of source code in a compiler are provided. The mechanisms of the illustrative embodiments address the weaknesses of the known polyhedral loop transformation based approaches by providing mechanisms for performing code generation transformations on individual statement instances in an intermediate representation generated by the polyhedral loop transformation optimization of the source code. These code generation transformations have the important property that they do not change program order of the statements in the intermediate representation. This property allows the result of the code generation transformations to be provided back to the polyhedral loop transformation mechanisms in a program statement view, via a new re-entrance path of the illustrative embodiments, for additional optimization.

摘要翻译： 提供了一种用于编译器中源代码的高级多面体循环变换的系统和方法。 说明性实施例的机制通过提供用于在通过源代码的多面体环转换优化生成的中间表示中对各个语句实例执行代码生成变换的机制来解决已知的基于多面体循环变换的方法的弱点。 这些代码生成转换具有重要的属性，它们不改变中间表示中的语句的程序顺序。 该属性允许通过示例性实施例的新的重新导入路径将代码生成转换的结果提供给程序语句视图中的多面体循环变换机制，用于附加优化。

公开(公告)号：US5202995A

公开(公告)日：1993-04-13

申请号：US939586

申请日：1992-09-03

申请人： John K. P. O'Brien

发明人： John K. P. O'Brien

IPC分类号： G06F9/45

CPC分类号： G06F8/443

摘要： Removal of invariant branches from nests of loops results in an optimized computer program with increased speed of execution. To accomplish this objective, each loop of a program is then examined, looking at inner loops before their containing outer loops, to locate conditional branch instructions which are loop invariant. Each conditional branch which is evaluated based upon loop invariant calculations is rewritten, outside the outermost loop for which this branch is invariant. The moved branch is modified to branch around the loop in which it was originally contained if its condition is evaluated false. A new copy of the loop is made in which the invariant branch is rewritten as an unconditional branch. In the original copy of the loop, the invariant branch is deleted, and a branch is inserted after the modified original loop to skip around the new copy when the original copy is executed. Finally, any sections of the program which will never be executed as a result of the above described transformation are deleted.

摘要翻译： 从循环巢中移除不变分支导致优化的计算机程序，执行速度提高。 为了完成这个目标，然后检查程序的每个循环，在包含外部循环之前查看内部循环，以定位循环不变的条件分支指令。 基于循环不变计算进行评估的每个条件分支被重写，该分支是不变的最外层循环之外。 被移动的分支被修改为在其条件被评估为假的情况下在其最初被包含的循环周围分支。 进行循环的新副本，其中不变分支被重写为无条件分支。 在循环的原始副本中，删除不变分支，并且在执行原始副本后，在修改的原始循环之后插入分支以跳过新副本。 最后，将删除由于上述转换而永远不执行的程序的任何部分。