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

1. 发明授权

US07805467B2 Code preparation technique employing lock-free pointer operations 有权
标题翻译：采用无锁指针操作的代码准备技术
公开(公告)号：US07805467B2
公开(公告)日：2010-09-28
申请号：US11343678
申请日：2006-01-30
申请人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
发明人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F12/00
CPC分类号： G06F12/0261 , G06F9/46 , G06F9/526
摘要： A methodology has been discovered for transforming garbage collection-dependent algorithms, shared object implementations and/or concurrent software mechanisms into a form that does not presume the existence of an independent, or execution environment provided, garbage collector. Algorithms, shared object implementations and/or mechanisms designed or transformed using techniques described herein provide explicit reclamation of storage using lock-free pointer operations. Transformations can be applied to lock-free algorithms and shared object implementations and preserve lock-freedom of such algorithms and implementations. As a result, existing and future lock-free algorithms and shared object implementations that depend on a garbage-collected execution environment can be exploited in environments that do not provide garbage collection. Furthermore, algorithms and shared object implementations that employ explicit reclamation of storage using lock-free pointer operations such as described herein may be employed in the implementation of a garbage collector itself.
摘要翻译：已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。

2. 发明授权

US07424477B1 Shared synchronized skip-list data structure and technique employing linearizable operations 有权
标题翻译：共享同步跳过列表数据结构和采用线性化操作的技术
公开(公告)号：US07424477B1
公开(公告)日：2008-09-09
申请号：US10653828
申请日：2003-09-03
申请人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
发明人： Paul A. Martin , Guy L. Steele, Jr. , Nir N. Shavit , Steven K. Heller , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F17/00 , G06F7/00
CPC分类号： G06F9/524 , Y10S707/99938 , Y10S707/99942 , Y10S707/99943
摘要： A set of structures and techniques are described herein whereby an exemplary concurrent shared object, namely a shared skip list, can be implemented in a lock-free manner. Indeed, we have developed a number of interesting variants of a lock-free shared skip-list, including variants that may be employed to provide a lock-free shared dictionary. In some variants, a key-value dictionary is implemented.
摘要翻译：本文描述了一组结构和技术，由此可以以无锁的方式实现示例性并发共享对象，即共享跳过列表。实际上，我们已经开发出了一些无锁共享的跳过列表的许多有趣的变体，包括可用于提供无锁共享字典的变体。在一些变型中，实现了键值字典。

3. 发明授权

US06826757B2 Lock-free implementation of concurrent shared object with dynamic node allocation and distinguishing pointer value 有权
标题翻译：并行共享对象的锁定实现与动态节点分配和区分指针值
公开(公告)号：US06826757B2
公开(公告)日：2004-11-30
申请号：US09837670
申请日：2001-04-18
申请人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
发明人： Guy L. Steele, Jr. , Alexander T. Garthwaite , Paul A. Martin , Nir N. Shavit , Mark S. Moir , David L. Detlefs
IPC分类号： G06F946
CPC分类号： G06F9/52
摘要： A novel linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, non-blocking completion of access operations is achieved without restricting concurrency in accessing the deque's two ends. In various realizations in accordance with the present invention, the set of values that may be pushed onto a shared object is not constrained by use of distinguishing values. In addition, an explicit reclamation embodiment facilitates use in environments or applications where automatic reclamation of storage is unavailable or impractical.
摘要翻译：已经开发了一种基于链表的并行共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在底层技术应用于deque时，实现访问操作的非阻塞完成，而不会限制访问deque的两端的并发性。在根据本发明的各种实现中，可以推送到共享对象上的值集合不受使用区分值的约束。此外，显式的回收实施例有利于在存储器的自动回收不可用或不切实际的环境或应用中使用。

4. 发明授权

US06993770B1 Lock free reference counting 有权
标题翻译：锁定自由引用计数
公开(公告)号：US06993770B1
公开(公告)日：2006-01-31
申请号：US09837671
申请日：2001-04-18
申请人： David L. Detlefs , Paul A. Martin , Mark S. Moir , Guy L. Steele, Jr.
发明人： David L. Detlefs , Paul A. Martin , Mark S. Moir , Guy L. Steele, Jr.
IPC分类号： G06F9/54
CPC分类号： G06F9/526 , G06F12/0261 , Y10S707/99944 , Y10S707/99947
摘要： We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
摘要翻译：我们提出一种方法，用于将依赖于垃圾回收的并行数据结构实现转换为不具有相同的实现。假设垃圾收集的存在使得设计并发数据结构的实现变得更加容易，特别是因为它消除了众所周知的ABA问题。然而，这个假设限制了它们的适用性。我们的研究结果表明，对于重要的数据结构类，设计人员可以首先解决实现依赖于垃圾回收的更容易的问题，然后应用我们的方法来实现与垃圾回收无关的实现。我们的方法是基于众所周知的参考计数技术，并采用双重比较和交换操作。

5. 发明授权

US07017160B2 Concurrent shared object implemented using a linked-list with amortized node allocation 有权
标题翻译：使用具有摊销节点分配的链接列表实现的并发共享对象
公开(公告)号：US07017160B2
公开(公告)日：2006-03-21
申请号：US09837669
申请日：2001-04-18
申请人： Paul A. Martin , David L. Detlefs , Alexander T. Garthwaite , Guy L. Steele, Jr. , Mark S. Moir
发明人： Paul A. Martin , David L. Detlefs , Alexander T. Garthwaite , Guy L. Steele, Jr. , Mark S. Moir
IPC分类号： G06F9/44 , G06F9/54
CPC分类号： G06F7/785 , G06F9/30032 , G06F9/526 , G06F9/544 , G06F2205/064 , G06F2209/521
摘要： The Hat Trick deque requires only a single DCAS for most pushes and pops. The left and right ends do not interfere with each other until there is one or fewer items in the queue, and then a DCAS adjudicates between competing pops. By choosing a granularity greater than a single node, the user can amortize the costs of adding additional storage over multiple push (and pop) operations that employ the added storage. A suitable removal strategy can provide similar amortization advantages. The technique of leaving spare nodes linked in the structure allows an indefinite number of pushes and pops at a given deque end to proceed without the need to invoke memory allocation or reclamation so long as the difference between the number of pushes and the number of pops remains within given bounds. Both garbage collection dependent and explicit reclamation implementations are described.
摘要翻译：帽子技巧deque只需要一个单一的DCAS大多数按钮和弹出。在队列中有一个或多个项目之前，左右两端不会相互干扰，然后DCAS在竞争弹出之间进行裁决。通过选择大于单个节点的粒度，用户可以通过使用添加的存储的多个推送（和弹出）操作来分摊添加附加存储的成本。合适的清除策略可以提供类似的摊销优势。在结构中链接的备用节点的技术允许在给定的deque端的无限数量的推送和弹出进行，而不需要调用内存分配或回收，只要推送次数和流量数之间的差异保持不变在给定范围内。描述垃圾收集相关和显式回收实现。

6. 发明授权

US07539849B1 Maintaining a double-ended queue in a contiguous array with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权
标题翻译：在具有并发的非阻塞插入和删除操作的连续数组中维护双端口队列，使用双重比较和交换原语
公开(公告)号：US07539849B1
公开(公告)日：2009-05-26
申请号：US09547288
申请日：2000-04-11
申请人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Ole Agesen , David L. Detlefs , Christine H. Flood , Alexander T. Garthwaite , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F7/06
CPC分类号： G06F9/52 , G06F9/544 , Y10S707/99942
摘要： An array-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.
摘要翻译：已经开发了一种基于数组的并发共享对象实现，它提供对并发共享对象的非阻塞和线性化访问。在将Deck的基础技术应用于deque时，基于阵列的算法允许对deque两端进行不间断的并发访问，同时在deque为空或满时在边界情况下返回适当的异常。并发deque实现的一个有趣的特征是，处理器可以检测这些边界情况，例如，确定阵列是空还是满，而不检查原子操作中两个终端指针的相对位置。

7. 发明授权

US07000234B1 Maintaining a double-ended queue as a linked-list with sentinel nodes and delete flags with concurrent non-blocking insert and remove operations using a double compare-and-swap primitive 有权
标题翻译：将双端队列作为链接列表维护，并使用哨兵节点和删除标志，并发使用并发的非阻塞插入和删除操作，使用双重比较和交换原语
公开(公告)号：US07000234B1
公开(公告)日：2006-02-14
申请号：US09547290
申请日：2000-04-11
申请人： Nir N. Shavit , Paul A. Martin , Guy L. Steele, Jr.
发明人： Nir N. Shavit , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F9/54
CPC分类号： G06F7/785 , G06F5/10 , G06F2205/064
摘要： A linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the linked-list-based algorithm allows non-blocking completion of access operations without restricting concurrency in accessing the deque's two ends. The new implementation is based at least in part on a new technique for splitting a pop operation into two steps, marking that a node is about to be deleted, and then deleting it. Once marked, the node logically deleted, and the actual deletion from the list can be deferred. In one realization, actual deletion is performed as part of a next push or pop operation performed at the corresponding end of the deque. An important aspect of the overall technique is synchronization of delete operations when processors detect that there are only marked nodes in the list and attempt to delete one or more of these nodes concurrently from both ends of the deque.
摘要翻译：已经开发了基于链接列表的并发共享对象实现，其提供对并发共享对象的非阻塞和线性化访问。在基于deque的基础技术的应用中，基于链表的算法允许非阻塞地完成访问操作，而不会限制访问deque两端的并发性。新的实现至少部分地基于用于将弹出操作分成两个步骤的新技术，标记节点即将被删除，然后删除它。一旦标记，节点将被逻辑删除，并且可以推迟从列表中实际删除。在一个实现中，实际删除被执行为在deque的对应端执行的下一个推或者弹出操作的一部分。总体技术的一个重要方面是当处理器检测到列表中只有标记节点并且尝试从德克两端同时删除这些节点中的一个或多个时，删除操作的同步。

8. 发明授权

US07890722B1 Sequentially performed compound compare-and-swap 有权
标题翻译：顺序执行的复合比较和交换
公开(公告)号：US07890722B1
公开(公告)日：2011-02-15
申请号：US11099720
申请日：2005-04-06
申请人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
发明人： Guy L. Steele, Jr. , Ole Agesen , Nir N. Shavit
IPC分类号： G06F12/14
CPC分类号： G06F9/524 , G06F9/30021 , G06F9/3004 , G06F9/30087
摘要： A sequentially performed implementation of a compound compare-and-swap (nCAS) operation has been developed. In one implementation, a double compare-and-swap (DCAS) operation does not result in a fault, interrupt, or trap in the situation where memory address A2 is invalid and the contents of memory address A1 are unequal to C1. In some realizations, memory locations addressed by a sequentially performed nCAS or DCAS instruction are reserved (e.g., locked) in a predefined order in accordance with a fixed total order of memory locations. In this way, deadlock between concurrently executed instances of sequentially performed nCAS instructions can be avoided. Other realizations defer responsibility for deadlock avoidance to the programmer.
摘要翻译：已经开发了顺序执行的复合比较和交换（nCAS）操作。在一个实现中，在存储器地址A2无效并且存储器地址A1的内容不等于C1的情况下，双重比较和交换（DCAS）操作不会导致故障，中断或陷阱。在一些实现中，依次执行的nCAS或DCAS指令寻址的存储器单元根据存储单元的固定总顺序以预定义的顺序被保留（例如锁定）。以这种方式，可以避免顺序执行的nCAS指令的同时执行的实例之间的死锁。其他实现方式将程序员的死锁责任推迟。

9. 发明授权

US07395297B2 Floating point system that represents status flag information within a floating point operand 有权
标题翻译：表示浮点运算符中的状态标志信息的浮点系统
公开(公告)号：US07395297B2
公开(公告)日：2008-07-01
申请号：US10035747
申请日：2001-12-28
申请人： Guy L. Steele, Jr.
发明人： Guy L. Steele, Jr.
IPC分类号： G06F7/00
CPC分类号： G06F7/483 , G06F5/012 , G06F5/015 , G06F7/4873 , G06F7/4876 , G06F7/49905 , G06F7/49942 , G06F9/30014 , G06F9/30094 , G06F9/3861 , G06F9/3885
摘要： A floating point unit generates results in which status information generated for an operation is encoded within the resulting operand, instead of requiring a separate floating point status register for the status information. In one embodiment, a floating point operand data structure includes a first portion having floating point operand data and a second portion having embedded status information associated with at least one status condition of the operand data. The status condition may be determined from only the embedded status information. The status condition may also be associated with at least one floating point operation that generated the operand data structure. The outcome of a conditional floating point instruction may be based on the embedded status information without regard to contents of the floating point status register. The second portion of the data structure may also have at least one bit indicative of the status condition, such as an invalid operation status, an overflow status, an underflow status, a division by zero status, an infinity status, and an inexact status.
摘要翻译：浮点单元产生结果，其中为操作生成的状态信息在结果操作数内被编码，而不是为状态信息需要单独的浮点状态寄存器。在一个实施例中，浮点运算数据结构包括具有浮点运算数据的第一部分和具有与操作数数据的至少一个状态条件相关联的嵌入状态信息的第二部分。状态条件可以仅从嵌入状态信息确定。状态条件也可以与产生操作数数据结构的至少一个浮点运算相关联。条件浮点指令的结果可以基于嵌入状态信息而不考虑浮点状态寄存器的内容。数据结构的第二部分还可以具有指示状态条件的至少一个比特，例如无效操作状态，溢出状态，下溢状态，由零状态划分，无穷大状态和不精确状态。

10. 发明授权

US06993549B2 System and method for performing gloating point operations involving extended exponents 有权
标题翻译：执行包括扩展指数的小球点操作的系统和方法
公开(公告)号：US06993549B2
公开(公告)日：2006-01-31
申请号：US10035581
申请日：2001-12-28
申请人： Guy L. Steele, Jr.
发明人： Guy L. Steele, Jr.
IPC分类号： G06F5/01 , G06F7/52
CPC分类号： G06F7/4876 , G06F7/4873 , G06F7/49905 , G06F9/30014 , G06F9/30094 , G06F9/3822 , G06F9/3861 , G06F9/3885
摘要： An extended exponent floating point unit performs an extended exponent floating point operation on a plurality of operands to produce a product of the plurality of operands. The extended exponent floating point unit groups the plurality of operands into at least one group, determines a plurality of scale factors for the plurality of operands, respectively, and provides a running sum of the plurality of scale factors. The extended exponent floating point unit further scales the plurality of operands to obtain a plurality of scaled operands, multiplies the plurality of scaled operands to obtain a group product, and scales the group product to obtain a scaled group product. The scaled group product is adjusted based on the running sum. The plurality of operands are grouped such that when all the plurality of scaled operands in the at least one group are multiplied an overflow or underflow will not occur.
摘要翻译：扩展指数浮点单元对多个操作数执行扩展指数浮点运算，以产生多个操作数的乘积。扩展指数浮点单元将多个操作数分组为至少一个组，分别确定多个操作数的多个比例因子，并提供多个比例因子的运行和。扩展指数浮点单元进一步缩放多个操作数以获得多个缩放的操作数，将多个缩放的操作数相乘以获得组积，并对组乘积进行缩放以获得缩放的组积。根据运行总和调整缩放组合产品。多个操作数被分组，使得当至少一个组中的所有多个缩放的操作数相乘时，不会发生溢出或下溢。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式