专利快速检索-快速检索全球专利，免费商用专利数据库-IPRDB

1. 发明授权

US06839895B1 Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring 有权
标题翻译：方法，系统和计算机程序产品，通过代码重组提供有效利用存储器层次结构
公开(公告)号：US06839895B1
公开(公告)日：2005-01-04
申请号：US09685481
申请日：2000-10-10
申请人： Dz Ching Ju , Kalyan Muthukumar , Shankar Ramaswamy , Barbara Bluestein Simons
发明人： Dz Ching Ju , Kalyan Muthukumar , Shankar Ramaswamy , Barbara Bluestein Simons
IPC分类号： G06F9/45
CPC分类号： G06F8/4442
摘要： Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocs it connects.
摘要翻译：通过构建对应于存储器层级的级别的程序执行图（PEG）来提供基于分析信息和存储器层次结构的代码重构或重新排序，对该PEG进行划分以减少低于上限的估计的内存开销成本，以及构建用于来自分区PEG的内存层次结构的下一级别。 PEG由要重组程序的配置文件的控制流程和频率信息构成。 PEG是加权无向图，包括表示基本块的节点和表示基本块对之间的控制传输的边。节点的权重是其表示的基本块的大小，边的权重是其连接的一对基本块之间的转换频率。

2. 发明授权

US06175957B1 Method of, system for, and computer program product for providing efficient utilization of memory hierarchy through code restructuring 失效
标题翻译：方法，系统和计算机程序产品，通过代码重组提供有效利用存储器层次结构
公开(公告)号：US06175957B1
公开(公告)日：2001-01-16
申请号：US08987911
申请日：1997-12-09
申请人： Dz Ching Ju , Kalyan Muthukumar , Shankar Ramaswamy , Barbara Bluestein Simons
发明人： Dz Ching Ju , Kalyan Muthukumar , Shankar Ramaswamy , Barbara Bluestein Simons
IPC分类号： G06F9445
CPC分类号： G06F8/4442
摘要： Code restructuring or reordering based on profiling information and memory hierarchy is provided by constructing a Program Execution Graph (PEG) corresponding to a level of the memory hierarchy, partitioning this PEG to reduce estimated memory overhead costs below an upper bound, and constructing a PEG for a next level of the memory hierarchy from the partitioned PEG. The PEG is constructed from control flow and frequency information from a profile of the program to be restructured. The PEG is a weighted undirected graph comprising nodes representing basic blocks and edges representing transfer of control between pairs of basic blocks. The weight of a node is the size of the basic block it represents and the weight of an edge is the frequency of transition between the pair of basic blocks it connects. The nodes of the PEG are partitioned or clustered into clusters such that the sum of the weights of the nodes in any cluster is no greater than an upper bound. A next PEG is then constructed from the clusters of the partitioned PEG such that a node in the next PEG corresponds to a cluster in the partitioned PEG, and such that there is an edge between two nodes in the next PEG if there is an edge between the clusters represented by the two nodes. Weights are assigned to the nodes and edges of the next PEG to produce a PEG, and then the PEG partitioning, basic block reordering, and PEG construction steps may be repeated for each level of the memory hierarchy. After the clustering is completed, the basic blocks are reordered in memory by grouping all of the nodes of a cluster in an adjacent order beginning at a boundary for all the levels of the memory hierarchy. Because clusters must not cross boundaries of memory hierarchies, NOPs are added to fill out the portion of a memory hierarchy level that is not filled by the clusters.
摘要翻译：通过构建对应于存储器层级的级别的程序执行图（PEG）来提供基于分析信息和存储器层次结构的代码重构或重新排序，对该PEG进行划分以减少低于上限的估计的内存开销成本，以及构建用于来自分区PEG的内存层次结构的下一级别。 PEG由要重组程序的配置文件的控制流程和频率信息构成。 PEG是加权无向图，包括表示基本块的节点和表示基本块对之间的控制传输的边。节点的权重是其表示的基本块的大小，边的权重是其连接的一对基本块之间的转换频率。 PEG的节点被分区或聚类成簇，使得任何簇中的节点的权重之和不大于上限。然后从分隔的PEG的簇构建下一个PEG，使得下一个PEG中的节点对应于分离的PEG中的簇，并且使得在下一个PEG中的两个节点之间存在边缘，如果在由两个节点代表的群集。将权重分配给下一个PEG的节点和边缘以产生PEG，然后可以针对存储器层级的每个级别重复PEG划分，基本块重排序和PEG构建步骤。在聚类完成之后，基本块在存储器中被重新排序，所以在存储器层次结构的所有级别的边界处以相邻顺序对簇的所有节点进行分组。因为集群不能跨越内存层次结构的边界，所以添加NOP以填充未由集群填充的内存层次结构级别的部分。

3. 发明授权

US06292938B1 Retargeting optimized code by matching tree patterns in directed acyclic graphs 失效
标题翻译：通过在有向非循环图中匹配树形图来重定向优化的代码
公开(公告)号：US06292938B1
公开(公告)日：2001-09-18
申请号：US09204210
申请日：1998-12-02
申请人： Vivek Sarkar , Mauricio Jose Serrano , Barbara Bluestein Simons
发明人： Vivek Sarkar , Mauricio Jose Serrano , Barbara Bluestein Simons
IPC分类号： G06F945
CPC分类号： G06F8/47
摘要： An optimizing, compiler that performs retargetable object code generation for a specific processor by matching tree patterns in directed acyclic graphs derived from the source code.
摘要翻译：一种优化的编译器，通过从源代码派生的有向无环图中匹配树形图案，为特定处理器执行可重定向目标代码生成。

4. 发明授权

US6044222A System, method, and program product for loop instruction scheduling hardware lookahead 失效
标题翻译：系统，方法和程序产品用于循环指令调度硬件的前瞻
公开(公告)号：US6044222A
公开(公告)日：2000-03-28
申请号：US882724
申请日：1997-06-23
申请人： Barbara Bluestein Simons , Vivek Sarkar
发明人： Barbara Bluestein Simons , Vivek Sarkar
IPC分类号： G06F9/45 , G06F9/44
CPC分类号： G06F8/4452
摘要： Improved scheduling of instructions within a loop for execution by a computer system having hardware lookahead is provided. A dependence graph is constructed which contains all the nodes of a dependence graph corresponding to the loop, but which only contains loop-independent dependence edges. A start node simulating a previous iteration of the loop may be added to the dependence graph, and an end node simulating a next iteration of the loop may also added to the dependence graph. A loop-independent edge between a source node and the start node is added to the dependence graph, and a loop-independent edge between a sink node and the end node is added to the dependence graph. Loop-carried edges which satisfy a computed lower bound on the time required for a single loop iteration are eliminated from a dependence graph, and loop-carried edges which do not satisfy the computed lower bound are replaced by a pair of loop-independent edges. Instructions may be scheduled for execution based on the dependence graph.
摘要翻译：提供了改进的循环内的指令的调度，以便由具有硬件前瞻的计算机系统执行。构造依赖图，其包含对应于循环的依赖图的所有节点，但是仅包含与循环无关的依赖性边。模拟循环的先前迭代的起始节点可以被添加到依赖图，并且模拟循环的下一个迭代的结束节点也可以被添加到依赖图。源节点和起始节点之间的环路无关的边缘被添加到依赖关系图中，并且汇点节点和终端节点之间的与环路无关的边缘被添加到依赖图中。从依赖图中消除满足单循环迭代所需时间的计算下界的循环传送边，并且不满足计算下界的循环传送边被一对独立于循环的边替换。可以根据依赖图计划执行指令。

5. 发明授权

US5887174A System, method, and program product for instruction scheduling in the presence of hardware lookahead accomplished by the rescheduling of idle slots 失效
标题翻译：在存在通过重新安排空闲插槽实现的硬件前瞻的情况下进行指令调度的系统，方法和程序产品
公开(公告)号：US5887174A
公开(公告)日：1999-03-23
申请号：US666719
申请日：1996-06-18
申请人： Barbara Bluestein Simons , Vivek Sarkar
发明人： Barbara Bluestein Simons , Vivek Sarkar
IPC分类号： G06F9/45 , G06F9/44
CPC分类号： G06F8/445
摘要： Instructions are scheduled for execution by a processor having a lookahead buffer by identifying an idle slot in a first instruction schedule of a first basic block of instructions, and by rescheduling the idle slot later in the first instruction schedule. The idle slot is rescheduled by determining if the first basic block of instructions may be rescheduled into a second instruction schedule in which the identified idle slot is scheduled later than in the first instruction schedule. The first basic block of instructions is rescheduled by determining a completion deadline of the first instruction schedule, decreasing the completion deadline, and determining the second instruction schedule based on the decreased completion deadline. Deadlines are determined by computing a rank of each node of a DAG corresponding to the first basic block of instructions; constructing an ordered list of the DAG nodes in nondecreasing rank order; and applying a greedy scheduling heuristic to the ordered list. An instruction in a second subsequent basic block of instructions may be rescheduled to execute in the rescheduled idle slot. This process may be repeated for each idle slot.
摘要翻译：通过在第一基本指令块的第一指令调度中识别空闲时隙，并且通过在第一指令调度中稍后再调度空闲时隙，调度具有前瞻缓冲器的处理器执行指令。通过确定第一基本指令块是否可以重新安排到第二指令调度中来重新调度空闲时隙，其中所标识的空闲时隙晚于第一指令调度中的调度。通过确定第一指令调度的完成期限，减少完成期限以及基于完成截止时间缩短来确定第二指令调度表来重新安排第一基本指令块。通过计算与第一基本指令块相对应的DAG的每个节点的等级来确定截止日期; 以不降序的顺序构建DAG节点的有序列表; 并将贪心调度启发式应用于有序列表。在第二后续基本指令块中的指令可以被重新调度以在重新安排的空闲时隙中执行。可以针对每个空闲时隙重复该过程。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式