公开(公告)号：US06530079B1

公开(公告)日：2003-03-04

申请号：US09323989

申请日：1999-06-02

申请人： Jong-Deok Choi ,  Manish Gupta ,  Mauricio J. Serrano ,  Vugranam C. Sreedhar ,  Samuel Pratt Midkiff

发明人： Jong-Deok Choi ,  Manish Gupta ,  Mauricio J. Serrano ,  Vugranam C. Sreedhar ,  Samuel Pratt Midkiff

IPC分类号： G06F9445

CPC分类号： G06F9/52 ,  G06F8/443

摘要： A method and several variants for using information about the scope of access of objects acted upon by mutual exclusion, or mutex, locks to transform a computer program by eliminating locking operations from the program or simplifying the locking operations, while strictly performing the semantics of the original program. In particular, if it can be determined by a compiler that the object locked can only be accessed by a single thread it is not necessary to perform the “acquire” or “release” part of the locking operation, and only its side effects must be performed. Likewise, if it can be determined that the side effects of a locking operation acting on a variable which is locked in multiple threads are not needed, then only the locking operation, and not the side effects, needs to be performed. This simplifies the locking operation, and leads to faster programs which use fewer computer processor resources to execute; and programs which perform fewer shared memory accesses, which in turn not only causes the optimized program, but also other programs executing on the same computing machine to execute faster. The method also describes how information about the semantics of the locking operation side effects and the information about the scope of access can also be used to eliminate performing the side effect parts of the locking operation, thereby completely eliminating the locking operation. The method also describes how to analyze the program to compute the necessary information about the scope of access. Variants of the method show how one or several of the features of the method may be performed.

摘要翻译： 一种方法和几种变体，用于使用通过互斥或互斥锁进行访问的对象的范围的信息，以通过从程序中消除锁定操作或简化锁定操作来转换计算机程序，同时严格执行 原始程序。 特别是，如果可以由编译器确定锁定的对象只能由单个线程访问，则不需要执行锁定操作的“获取”或“释放”部分，只有其副作用必须是 执行。 同样，如果可以确定不需要对锁定在多个线程中的变量作用的锁定操作的副作用，则仅需要执行锁定操作而不是副作用。 这简化了锁定操作，并导致更快的程序使用更少的计算机处理器资源来执行; 以及执行较少的共享存储器访问的程序，这又不仅导致优化的程序，而且还导致在同一计算机上执行的其他程序执行得更快。 该方法还描述了关于锁定操作侧的语义的信息如何影响以及关于访问范围的信息也可以用于消除执行锁定操作的副作用部分，从而完全消除锁定操作。 该方法还描述了如何分析程序来计算有关访问范围的必要信息。 该方法的变体显示了如何执行该方法的一个或多个特征。

公开(公告)号：US06381738B1

公开(公告)日：2002-04-30

申请号：US09354140

申请日：1999-07-16

申请人： Jong-Deok Choi ,  Manish Gupta ,  Mauricio J. Serrano ,  Vugranam C. Sreedhar ,  Samuel Pratt Midkiff

发明人： Jong-Deok Choi ,  Manish Gupta ,  Mauricio J. Serrano ,  Vugranam C. Sreedhar ,  Samuel Pratt Midkiff

IPC分类号： G06F945

CPC分类号： G06F8/443 ,  G06F12/023 ,  G06F12/0253

摘要： Information is computed about the reachability relationships among objects and pointers to enable transformation of a computer program for optimizing the creation and destruction of objects, while strictly performing the semantics of the original program. An interprocedural analysis is used to determine whether an object that is allocated on the heap during the execution of a procedure is not reachable from any global variable, parameter, or the return value of the procedure after it returns. If so, that object can be allocated on the stack frame of the procedure in which it is otherwise heap-allocated. This simplifies the memory allocation and deallocation operations, as allocation on the stack can be done more efficiently than allocation on the heap, and objects allocated on the stack frame of a procedure are automatically deallocated when the procedure returns, without incurring the overhead of garbage collection. This, in turn, leads to faster programs which use fewer computer processor resources to execute. The interprocedural analysis of the program summarizes the effect of a procedure call succinctly for different calling contexts of the procedure using a single summary representation. The method handles exceptions in the programming language, while taking advantage of the information about the visibility of variables in the exception handler. Variants of the method show how one or several of the features of the method may be performed.

摘要翻译： 计算关于对象和指针之间的可达性关系的信息，以便在严格执行原始程序的语义的同时，实现用于优化对象的创建和销毁的计算机程序的转换。 过程间分析用于确定在执行过程期间在堆上分配的对象是否从任何全局变量，参数或过程返回后的返回值无法访问。 如果是这样，那么该对象可以分配给过程的堆栈帧，否则它将以堆分配。 这简化了内存分配和释放操作，因为堆栈上的分配可以比堆上的分配更有效地完成，并且当过程返回时，分配给过程的堆栈帧的对象将自动释放，而不会产生垃圾回收的开销 。 这反过来导致更快的程序，使用较少的计算机处理器资源来执行。 程序的程序间分析使用单个摘要表示简要地描述了对程序的不同调用上下文的简单过程调用的影响。 该方法处理编程语言中的异常，同时利用有关异常处理程序中变量可见性的信息。 该方法的变体显示了如何执行该方法的一个或多个特征。

公开(公告)号：US06973646B1

公开(公告)日：2005-12-06

申请号：US09621571

申请日：2000-07-21

申请人： Rajesh Bordawekar ,  Manish Gupta ,  Samuel Pratt Midkiff ,  Mauricio J. Serrano

发明人： Rajesh Bordawekar ,  Manish Gupta ,  Samuel Pratt Midkiff ,  Mauricio J. Serrano

IPC分类号： G06F9/45

CPC分类号： G06F9/45516

摘要： This invention describes a method and several variants for compiling programs or components of programs in a mixed static and dynamic environment, so as to reduce the amount of time and memory spent in run-time compilation, or to exercise greater control over testing of the executable code for the program, or both. The invention involves generating persistent code images prior to program execution based on static compilation or dynamic compilation from a previous run, and then, adapting those images during program execution. We describe a method for generating auxiliary information in addition to the executable code that is recorded in the persistent code image. Further, we describe a method for checking the validity of those code images, adapting those images to the new execution context, and generating new executable code to respond to dynamic events, during program execution. Our method allows global interprocedural optimizations to be performed on the program, even if the programming language supports, or requires, dynamic binding. Variants of the method show how one or several of the features of the method may be performed. The invention is particularly useful in the context of implementing Java Virtual Machines, although it can also be used in implementing other programming languages.

摘要翻译： 本发明描述了用于在混合静态和动态环境中编译程序或程序组件的方法和几个变体，以便减少在运行时编译中花费的时间和内存的量，或者更好地控制可执行程序的测试 程序的代码，或两者。 本发明涉及在基于来自先前运行的静态编译或动态编译之前，在程序执行之前生成持久代码图像，然后在程序执行期间对这些图像进行调整。 我们描述除了记录在持久代码图像中的可执行代码之外，还生成辅助信息的方法。 此外，我们描述了在程序执行期间检查这些代码图像的有效性，使这些图像适应新的执行上下文以及生成新的可执行代码以响应动态事件的方法。 我们的方法允许对程序执行全局过程间优化，即使编程语言支持或需要动态绑定。 该方法的变体显示了如何执行该方法的一个或多个特征。 本发明在实现Java虚拟机的上下文中是特别有用的，尽管它也可以用于实现其他编程语言。

公开(公告)号：US20090113135A1

公开(公告)日：2009-04-30

申请号：US11929771

申请日：2007-10-30

申请人： Harold W. Cain ,  Jong-Deok Choi ,  Pratak Pattnaik ,  Mauricio J. Serrano

发明人： Harold W. Cain ,  Jong-Deok Choi ,  Pratak Pattnaik ,  Mauricio J. Serrano

IPC分类号： G06F12/08

CPC分类号： G06F12/126

摘要： A system and method for cache replacement includes: augmenting each cache block in a cache region with a region hint indicating a temporal priority of the cache block; receiving an indication that a cache miss has occurred; and selecting for eviction the cache block comprising the region hint indicating a low temporal priority.

摘要翻译： 一种用于高速缓存替换的系统和方法包括：利用指示高速缓存块的时间优先级的区域提示来增强高速缓存区中的每个高速缓存块; 接收发生高速缓存未命中的指示; 以及选择驱逐包含指示低时间优先级的区域提示的高速缓存块。

公开(公告)号：US20090037708A1

公开(公告)日：2009-02-05

申请号：US12246282

申请日：2008-10-06

申请人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

发明人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

IPC分类号： G06F9/38

CPC分类号： G06F9/3806 ,  G06F9/322 ,  G06F9/3848

摘要： A system for predicting multiple targets for a single branch includes: a branch target buffer that includes a previous next address for an instruction and that receives an indirect instruction address to provide a first branch target prediction; a first branch table for capturing local past target information of an indirect branch in an encoded form; a second branch table which is a correlation table for storing potential branch targets based on a local branch history and which provides a second branch target prediction when the first branch target prediction is not successful; an exclusion predictor for inhibiting updates of inefficient entries; and a multiplexer to select the predicted target as output.

摘要翻译： 用于预测单个分支的多个目标的系统包括：分支目标缓冲器，其包括用于指令的先前的下一个地址并且接收间接指令地址以提供第一分支目标预测; 用于以编码形式捕获间接分支的当地过去目标信息的第一分支表; 第二分支表，其是基于本地分支历史存储潜在分支目标的相关表，并且当第一分支目标预测不成功时提供第二分支目标预测; 用于禁止更低效率条目的排除预测器; 以及选择预测目标作为输出的多路复用器。

公开(公告)号：US07900026B2

公开(公告)日：2011-03-01

申请号：US12246282

申请日：2008-10-06

申请人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

发明人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

IPC分类号： G06F9/32

CPC分类号： G06F9/3806 ,  G06F9/322 ,  G06F9/3848

摘要： A system for predicting multiple targets for a single branch includes: a branch target buffer that includes a previous next address for an instruction and that receives an indirect instruction address to provide a first branch target prediction; a first branch table for capturing local past target information of an indirect branch in an encoded form; a second branch table which is a correlation table for storing potential branch targets based on a local branch history and which provides a second branch target prediction when the first branch target prediction is not successful; an exclusion predictor for inhibiting updates of inefficient entries; and a multiplexer to select the predicted target as output.

摘要翻译： 用于预测单个分支的多个目标的系统包括：分支目标缓冲器，其包括用于指令的先前的下一个地址并且接收间接指令地址以提供第一分支目标预测; 用于以编码形式捕获间接分支的当地过去目标信息的第一分支表; 第二分支表，其是基于本地分支历史存储潜在分支目标的相关表，并且当第一分支目标预测不成功时提供第二分支目标预测; 用于禁止更低效率条目的排除预测器; 以及选择预测目标作为输出的多路复用器。

公开(公告)号：US07793049B2

公开(公告)日：2010-09-07

申请号：US11929771

申请日：2007-10-30

申请人： Harold W. Cain ,  Jong-Deok Choi ,  Pratak Pattnaik ,  Mauricio J. Serrano

发明人： Harold W. Cain ,  Jong-Deok Choi ,  Pratak Pattnaik ,  Mauricio J. Serrano

IPC分类号： G06F12/00

CPC分类号： G06F12/126

摘要： A system and method for cache replacement includes: augmenting each cache block in a cache region with a region hint indicating a temporal priority of the cache block; receiving an indication that a cache miss has occurred; and selecting for eviction the cache block comprising the region hint indicating a low temporal priority.

摘要翻译： 一种用于高速缓存替换的系统和方法包括：利用指示高速缓存块的时间优先级的区域提示来增强高速缓存区中的每个高速缓存块; 接收发生高速缓存未命中的指示; 以及选择驱逐包含指示低时间优先级的区域提示的高速缓存块。

公开(公告)号：US07921260B2

公开(公告)日：2011-04-05

申请号：US11923625

申请日：2007-10-24

申请人： Harold W. Cain, III ,  Jong-Deok Choi ,  Mauricio J. Serrano

发明人： Harold W. Cain, III ,  Jong-Deok Choi ,  Mauricio J. Serrano

IPC分类号： G06F12/12

CPC分类号： G06F12/127 ,  G06F2212/1021

摘要： A computer-implemented method of cache replacement includes steps of: determining whether each cache block in a cache memory is a read or a write block; augmenting metadata associated with each cache block with an indicator of the type of access; receiving an access request resulting in a cache miss, the cache miss indicating that a cache block will need to be replaced; examining the indicator in the metadata of each cache block for determining a probability that said cache block will be replaced; and selecting for replacement the cache block with the highest probability of replacement.

摘要翻译： 计算机实现的高速缓存替换方法包括以下步骤：确定高速缓冲存储器中的每个高速缓存块是读还是写块; 使用所述访问类型的指示符来增强与每个高速缓存块相关联的元数据; 接收导致高速缓存未命中的访问请求，指示高速缓存块将需要被替换的高速缓存未命中; 检查每个高速缓存块的元数据中的指示符，以确定所述高速缓存块将被替换的概率; 并以最高的替换概率选择替换高速缓存块。

公开(公告)号：US20090113132A1

公开(公告)日：2009-04-30

申请号：US11923625

申请日：2007-10-24

申请人： Harold Wade Cain, III ,  Jong-Deok Choi ,  Mauricio J. Serrano

发明人： Harold Wade Cain, III ,  Jong-Deok Choi ,  Mauricio J. Serrano

IPC分类号： G06F13/28

CPC分类号： G06F12/127 ,  G06F2212/1021

摘要： A computer-implemented method of cache replacement includes steps of: determining whether each cache block in a cache memory is a read or a write block; augmenting metadata associated with each cache block with an indicator of the type of access; receiving an access request resulting in a cache miss, the cache miss indicating that a cache block will need to be replaced; examining the indicator in the metadata of each cache block for determining a probability that said cache block will be replaced; and selecting for replacement the cache block with the highest probability of replacement.

摘要翻译： 计算机实现的高速缓存替换方法包括以下步骤：确定高速缓冲存储器中的每个高速缓存块是读还是写块; 使用所述访问类型的指示符来增强与每个高速缓存块相关联的元数据; 接收导致高速缓存未命中的访问请求，指示高速缓存块将需要被替换的高速缓存未命中; 检查每个高速缓存块的元数据中的指示符，以确定所述高速缓存块将被替换的概率; 并以最高的替换概率选择替换高速缓存块。

公开(公告)号：US07434037B2

公开(公告)日：2008-10-07

申请号：US11399979

申请日：2006-04-07

申请人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

发明人： Il Park ,  Mauricio J. Serrano ,  Jong-Deok Choi

IPC分类号： G06F9/32

CPC分类号： G06F9/3806 ,  G06F9/322 ,  G06F9/3848

摘要： An information processing system includes a branch target buffer (BTB) comprising the last next address for the instruction and for receiving an indirect instruction address and providing a BTB predicted target; and next branch target table (NBTT) for storing potential branch targets based on a history of the branch and for providing an NBTT when the a BTB predicted target is not successful. In another embodiment a system comprising a plurality of branch prediction resources dynamically predicts the best resource appropriate for a branch. The method includes predicting a target branch for an indirect instruction address using a resource chosen among the plurality of branch prediction resources; and selectively inhibiting updates of the branch prediction resources whose prediction accuracy does not meet a threshold.

摘要翻译： 信息处理系统包括分支目标缓冲器（BTB），其包括用于该指令的最后一个下一个地址，并且用于接收间接指令地址并提供BTB预测目标; 以及用于基于分支的历史存储潜在的分支目标并且当BTB预测目标不成功时提供NBTT的下一分支目标表（NBTT）。 在另一个实施例中，包括多个分支预测资源的系统动态地预测适合于分支的最佳资源。 该方法包括使用在多个分支预测资源中选择的资源来预测间接指令地址的目标分支; 并且选择性地禁止预测精度不满足阈值的分支预测资源的更新。