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

1. 发明授权

US09135178B2 Efficient non-blocking K-compare-single-swap operation 有权
标题翻译：高效无阻塞K比较 - 单互换操作
公开(公告)号：US09135178B2
公开(公告)日：2015-09-15
申请号：US13543267
申请日：2012-07-06
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F9/46 , G06F12/00 , G06F13/00 , G06F13/28 , G06F12/08 , G06F9/30 , G06F9/38 , G06F9/52
CPC分类号： G06F12/0844 , G06F9/30 , G06F9/3004 , G06F9/38 , G06F9/466 , G06F9/52 , G06F12/00 , G06F12/08 , G06F12/0815 , G06F12/084 , G06F12/0842 , G06F12/0846 , Y10S707/99942
摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
摘要翻译：使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。我们的实施是无障碍的。因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

2. 发明申请

US20130290583A1 System and Method for NUMA-Aware Locking Using Lock Cohorts 有权
标题翻译：使用锁定队列进行NUMA感知锁定的系统和方法
公开(公告)号：US20130290583A1
公开(公告)日：2013-10-31
申请号：US13458871
申请日：2012-04-27
申请人： David Dice , Virendra J. Marathe , Nir N. Shavit
发明人： David Dice , Virendra J. Marathe , Nir N. Shavit
IPC分类号： G06F13/14
CPC分类号： G06F9/526
摘要： The system and methods described herein may be used to implement NUMA-aware locks that employ lock cohorting. These lock cohorting techniques may reduce the rate of lock migration by relaxing the order in which the lock schedules the execution of critical code sections by various threads, allowing lock ownership to remain resident on a single NUMA node longer than under strict FIFO ordering, thus reducing coherence traffic and improving aggregate performance. A NUMA-aware cohort lock may include a global shared lock that is thread-oblivious, and multiple node-level locks that provide cohort detection. The lock may be constructed from non-NUMA-aware components (e.g., spin-locks or queue locks) that are modified to provide thread-obliviousness and/or cohort detection. Lock ownership may be passed from one thread that holds the lock to another thread executing on the same NUMA node without releasing the global shared lock.
摘要翻译：本文描述的系统和方法可以用于实现采用锁定队列的NUMA感知锁。这些锁定队列技术可以通过放松锁定通过各种线程调度关键代码段的执行顺序来降低锁定迁移速率，从而允许锁定所有权保持驻留在单个NUMA节点上比在严格FIFO排序之前更长时间，从而减少一致性流量和提高总体性能。 NUMA感知的群组锁可能包括线程忽略的全局共享锁和提供队列检测的多个节点级锁。锁可以由修改为提供线程忽略性和/或队列检测的非NUMA感知组件（例如，旋转锁或队列锁）构建。锁定所有权可以从保存锁的一个线程传递到在同一NUMA节点上执行的另一个线程，而不会释放全局共享锁。

3. 发明授权

US07793053B2 Efficient non-blocking k-compare-single-swap operation 有权
标题翻译：高效无阻塞k-比较 - 单互换操作
公开(公告)号：US07793053B2
公开(公告)日：2010-09-07
申请号：US11864574
申请日：2007-09-28
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
IPC分类号： G06F12/00 , G06F13/00
CPC分类号： G06F12/0844 , G06F9/30 , G06F9/3004 , G06F9/38 , G06F9/466 , G06F9/52 , G06F12/00 , G06F12/08 , G06F12/0815 , G06F12/084 , G06F12/0842 , G06F12/0846 , Y10S707/99942
摘要： The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
摘要翻译：使用单一位置同步原语（例如比较和交换（CAS））的非阻塞链接数据结构的设计是一种复杂的事情，通常需要对指针使用方式的严格限制。解决这个问题的一个方法是提供更强大的同步操作，例如，在同时验证其他内容的同时原子地修改一个存储器位置的同步操作。我们提供了这样一个操作的简单而高效的非阻塞实现：原子k字比较单交换操作（KCSS）。我们的实施是无障碍的。因此，在无争议的情况下效率高，依靠竞争管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

4. 发明授权

US07669015B2 Methods and apparatus to implement parallel transactions 有权
标题翻译：实现并行交易的方法和设备
公开(公告)号：US07669015B2
公开(公告)日：2010-02-23
申请号：US11475814
申请日：2006-06-27
申请人： David Dice , Ori Shalev , Nir N. Shavit
发明人： David Dice , Ori Shalev , Nir N. Shavit
IPC分类号： G06F12/00
CPC分类号： G06F12/0806 , G06F9/466 , G06F9/52 , G06F9/526 , G06F12/0815 , G06F12/0893
摘要： The present disclosure describes a unique way for each of multiple processes to operate in parallel using (e.g., reading, modifying, and writing to) the same shared data without causing corruption to the shared data. For example, each of multiple processes utilizes current and past data values associated with a global counter or clock for purposes of determining whether any shared variables used to produce a respective transaction outcome were modified (by another process) when executing a respective transaction. If a respective process detects that shared data used by respective process was modified during a transaction, the process can abort and retry the transaction rather than cause data corruption by storing locally maintained results associated with the transaction to a globally shared data space.
摘要翻译：本公开描述了使用（例如，读取，修改和写入）相同的共享数据而不会对共享数据造成损坏的多个进程中的每一个进行并行操作的独特方式。例如，当执行相应的交易时，多个过程中的每个利用与全局计数器或时钟相关联的当前和过去的数据值来确定用于产生相应的交易结果的任何共享变量（通过另一个进程）被修改。如果相应的进程检测到在处理期间修改了相应进程使用的共享数据，则该进程可以中止并重试事务，而不是通过将与事务相关联的本地维护的结果存储到全局共享的数据空间来导致数据损坏。

5. 发明授权

US07496716B2 Methods and apparatus to implement parallel transactions 有权
标题翻译：实现并行交易的方法和设备
公开(公告)号：US07496716B2
公开(公告)日：2009-02-24
申请号：US11488618
申请日：2006-07-18
申请人： David Dice , Nir N. Shavit
发明人： David Dice , Nir N. Shavit
IPC分类号： G06F12/00
CPC分类号： G06F12/0806 , G06F9/466 , G06F9/52 , G06F9/526 , G06F12/0815 , G06F12/0893
摘要： Cache logic associated with a respective one of multiple processing threads executing in parallel updates corresponding data fields of a cache to uniquely mark its contents. The marked contents represent a respective read set for a transaction. For example, at an outset of executing a transaction, a respective processing thread chooses a data value to mark contents of the cache used for producing a transaction outcome for the processing thread. Upon each read of shared data from main memory, the cache stores a copy of the data and marks it as being used during execution of the processing thread. If uniquely marked contents of a respective cache line happen to be displaced (e.g., overwritten) during execution of a processing thread, then the transaction is aborted (rather than being committed to main memory) because there is a possibility that another transaction overwrote a shared data value used during the respective transaction.
摘要翻译：与并行执行的多个处理线程中的相应一个相关联的缓存逻辑更新缓存的相应数据字段以唯一地标记其内容。标记的内容表示交易的相应读取集合。例如，在执行事务的开始时，相应的处理线程选择数据值来标记用于产生处理线程的事务结果的高速缓存的内容。每次从主存储器读取共享数据时，高速缓存存储数据的副本，并将其标记为在执行处理线程期间被使用。如果在执行处理线程期间相应的高速缓存线的唯一标记的内容恰好被移位（例如被重写），则事务被中止（而不是被提交到主存储器），因为存在另一个事务覆盖共享的可能性在相应交易期间使用的数据值。

6. 发明授权

US07346747B1 Exclusive lease instruction support for transient blocking synchronization 有权
标题翻译：独占租赁指令支持瞬态阻塞同步
公开(公告)号：US07346747B1
公开(公告)日：2008-03-18
申请号：US11078120
申请日：2005-03-11
申请人： Daniel S. Nussbaum , Mark S. Moir , Nir N. Shavit , Guy L. Steele
发明人： Daniel S. Nussbaum , Mark S. Moir , Nir N. Shavit , Guy L. Steele
IPC分类号： G06F12/00
CPC分类号： G06F12/0815
摘要： A computer system uses transient blocking synchronization for performing operations on shared memory. When performing operations on more than one memory location, the computer system obtains transient exclusive access to a first memory location. The computer system then obtains transient exclusive access to a second memory location, where the transient exclusive access to the second memory location does not expire prior to an expiration of the transient exclusive access to the first memory location or until explicitly unleased.
摘要翻译：计算机系统使用瞬态阻塞同步来对共享存储器执行操作。当在多个存储器位置上执行操作时，计算机系统获得对第一存储器位置的瞬时独占访问。计算机系统然后获得对第二存储器位置的瞬时独占访问，其中对第二存储器位置的瞬时独占访问在到对第一存储器位置的瞬时独占访问期满之前直到明确地未被释放为止。

7. 发明申请

US20070282838A1 Fine-locked transactional memory 有权
标题翻译：精细锁定事务记忆
公开(公告)号：US20070282838A1
公开(公告)日：2007-12-06
申请号：US11443234
申请日：2006-05-30
申请人： Nir N. Shavit , David Dice
发明人： Nir N. Shavit , David Dice
IPC分类号： G06F17/30
CPC分类号： G06F9/3004 , G06F9/30087 , G06F9/3834 , G06F9/467
摘要： A method comprises associating a plurality of locks with a data object accessed concurrently by a plurality of threads, where each lock corresponds to a respective partition of the object. The method includes using a first non-blocking transaction (such as a Hardware Transactional-Memory (HTM) transaction) to attempt to complete a programmer-specified transaction. The first non-blocking transaction may access one or more of the locks but may not actually acquire any of the locks. In response to an indication that the first non-blocking transaction failed to complete, the method may include acquiring a set of locks in another non-blocking transaction, where the set of locks corresponds to a set of partitions expected to be accessed in the programmer-specified transaction. If the set of locks is acquired, the method may include performing the memory access operations of the programmer-specified transaction, and releasing the set of locks.
摘要翻译：一种方法包括将多个锁与多个线程同时访问的数据对象相关联，其中每个锁对应于对象的相应分区。该方法包括使用第一非阻塞事务（例如硬件事务存储器（HTM）事务）来尝试完成编程器指定的事务。第一个非阻塞事务可以访问一个或多个锁，但实际上可能不会获取任何锁。响应于第一非阻塞事务未能完成的指示，该方法可以包括获取另一非阻塞事务中的一组锁，其中该组锁对应于预期在该程序器中被访问的一组分区指定交易。如果获取了一组锁，则该方法可以包括执行程序员指定的事务的存储器访问操作，以及释放一组锁。

8. 发明申请

US20070239943A1 Methods and apparatus to implement parallel transactions 有权
标题翻译：实现并行交易的方法和设备
公开(公告)号：US20070239943A1
公开(公告)日：2007-10-11
申请号：US11699802
申请日：2007-01-30
申请人： David Dice , Nir N. Shavit , Ori Shalev , Mark Moir
发明人： David Dice , Nir N. Shavit , Ori Shalev , Mark Moir
IPC分类号： G06F12/00
CPC分类号： G06F9/466
摘要： The present disclosure describes a unique way for each of multiple processes to operate in parallel and use the same shared data without causing corruption to the shared data. For example, during a commit phase, a corresponding transaction can attempt to increment a globally accessible version information variable and store a current value of the globally accessible version information variable for updating version information associated with modified data regardless of whether an associated attempt by the corresponding transaction to modify the globally accessible version information variable was successful. As an alternative mode, a corresponding transaction can merely read and store a current value of the globally accessible version information variable without attempting to update the globally accessible version information variable before such use. In yet another application, a parallel processing environment implements a combination of both aforementioned modes depending on a self-abort rate of the transaction.
摘要翻译：本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应修改全局可访问版本信息变量的事务成功。作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。

9. 发明授权

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的对应端执行的下一个推或者弹出操作的一部分。总体技术的一个重要方面是当处理器检测到列表中只有标记节点并且尝试从德克两端同时删除这些节点中的一个或多个时，删除操作的同步。

10. 发明授权

US06934741B2 Globally distributed load balancing 有权
标题翻译：全局分布式负载均衡
公开(公告)号：US06934741B2
公开(公告)日：2005-08-23
申请号：US09892813
申请日：2001-06-27
申请人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
发明人： Nir N. Shavit , Steven K. Heller , Christine H. Flood
IPC分类号： G06F9/44 , G06F15/167
CPC分类号： G06F9/4493
摘要： A garbage collector employs a plurality of task queues for a parallel-execution operation in a garbage-collection cycle. Each task queue is associated with a different ordered pair of the threads that perform the parallel-execution operation in parallel. One of the threads, referred to as that task queue's “enqueuer” thread, is the only one that can “push” onto that queue an identifier of a dynamically identified task. The other thread, referred to as that task queue's “dequeuer,” is the only one that can “pop” tasks from that task queue for execution. Since, for each task queue, there is only one thread that can “push” task identifiers on to it and only one thread that can “pop” task identifiers from it, the garbage collector can share dynamically identified tasks optimally among its threads without suffering the cost imposed by making combinations of otherwise separate machine instructions atomic.
摘要翻译：垃圾收集器采用多个任务队列进行垃圾回收循环中的并行执行操作。每个任务队列与并行执行并行执行操作的线程的不同有序对相关联。其中一个线程称为该任务队列的“入队”线程，是唯一能够将该队列推送到动态识别任务的标识符的线程。称为该任务队列的“dequeuer”的另一个线程是唯一可以从任务队列中“弹出”任务执行的线程。因为对于每个任务队列，只有一个线程可以将任务标识符“推”给它，并且只有一个线程可以从其中“弹出”任务标识符，垃圾收集器可以在其线程之间最佳地共享动态识别的任务，而不会遭受痛苦通过组合以其他方式分离的机器指令原子强加的成本。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式