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

1. 发明申请

US20120311606A1 System and Method for Implementing Hierarchical Queue-Based Locks Using Flat Combining 有权
标题翻译：使用平面组合实现层次化基于队列的锁的系统和方法
公开(公告)号：US20120311606A1
公开(公告)日：2012-12-06
申请号：US13152079
申请日：2011-06-02
申请人： Virendra J. Marathe , Nir N. Shavit , David Dice
发明人： Virendra J. Marathe , Nir N. Shavit , David Dice
IPC分类号： G06F9/46
CPC分类号： G06F9/526
摘要： The system and methods described herein may be used to implement a scalable, hierarchal, queue-based lock using flat combining. A thread executing on a processor core in a cluster of cores that share a memory may post a request to acquire a shared lock in a node of a publication list for the cluster using a non-atomic operation. A combiner thread may build an ordered (logical) local request queue that includes its own node and nodes of other threads (in the cluster) that include lock requests. The combiner thread may splice the local request queue into a (logical) global request queue for the shared lock as a sub-queue. A thread whose request has been posted in a node that has been combined into a local sub-queue and spliced into the global request queue may spin on a lock ownership indicator in its node until it is granted the shared lock.
摘要翻译：本文描述的系统和方法可以用于使用平坦组合来实现可扩展的，分级的基于队列的锁。在共享内存的核心集群中的处理器核心上执行的线程可以使用非原子操作来发布用于获取集群的发布列表的节点中的共享锁定的请求。组合线程可以构建一个有序（逻辑）本地请求队列，其包括其自己的节点和包含锁定请求的其他线程（在集群中）的节点。组合器线程可以将本地请求队列拼接成用于共享锁的（逻辑）全局请求队列作为子队列。已经将其请求已经发布在已经组合到本地子队列中并被拼接到全局请求队列中的节点的线程可以旋转其节点中的所有权所有者指示符，直到被授予共享锁为止。

2. 发明授权

US08103838B2 System and method for transactional locking using reader-lists 有权
标题翻译：使用阅读器列表进行事务锁定的系统和方法
公开(公告)号：US08103838B2
公开(公告)日：2012-01-24
申请号：US12350792
申请日：2009-01-08
申请人： David Dice , Nir N. Shavit
发明人： David Dice , Nir N. Shavit
IPC分类号： G06F12/16
CPC分类号： G06F9/52
摘要： In traditional transactional locking systems, such as Transactional Locking with Read-Write locks (TLRW), threads may frequently update lock metadata, causing system performance degradation. A system and method for implementing transactional locking using reader-lists (TLRL) may associate a respective reader-list with each stripe of data in a shared memory system. Before reading a given stripe as part of a transaction, a thread may add itself to the stripe's reader-list, if the thread is not already on the reader-list. A thread may leave itself on a reader-list after finishing the transaction. Before a thread modifies a stripe, the modifying thread may acquire a write-lock for the stripe. The writer thread may indicate to each reader thread on the stripe's reader-list that if the reader thread is executing a transaction, the reader thread should abort. The indication may include setting an invalidation flag for the reader. The writer thread may clear the reader-list of a stripe it modified.
摘要翻译：在传统的事务锁定系统中，例如使用读写锁定（TLRW）的事务锁定，线程可能会频繁更新锁元数据，从而导致系统性能下降。用于使用读取器列表（TLRL）实现事务锁定的系统和方法可将相应的读取器列表与共享存储器系统中的每条数据条相关联。在作为事务的一部分读取给定的条带之前，线程可能会将自身添加到条带的读取器列表中，如果该线程尚未在读取器列表中。完成交易后，线程可能会在读取器列表上留下。在线程修改条带之前，修改线程可以获取条带的写锁定。作者线程可能会在条形码读取器列表上向每个读取器线程指示如果读取器线程正在执行事务，则读取器线程应该中止。该指示可以包括设置读取器的无效标志。作者线程可以清除其修改的条带的阅读器列表。

3. 发明授权

US08065499B2 Methods and apparatus to implement parallel transactions 有权
标题翻译：实现并行交易的方法和设备
公开(公告)号：US08065499B2
公开(公告)日：2011-11-22
申请号：US11475262
申请日：2006-06-27
申请人： David Dice , Nir N. Shavit
发明人： David Dice , Nir N. Shavit
IPC分类号： G06F12/08
CPC分类号： G06F12/0806 , G06F9/466 , G06F9/52 , G06F9/526 , G06F12/0815 , G06F12/0893
摘要： A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including different types of metadata enabling the processing threads to carry out simultaneous execution depending on a currently selected type of lock mode. A mode controller monitoring the processing threads initiates switching from one type of lock mode to another depending on current operating conditions such as an amount of contention amongst the multiple processing threads to modify the shared data. The mode controller can switch from one lock mode another regardless of whether any of the multiple processes are in the midst of executing a respective transaction. A most efficient lock mode can be selected to carry out the parallel transactions. In certain cases, switching of lock modes causes one or more of the processing threads to abort and retry a respective transaction according to the new mode.
摘要翻译：计算机系统包括并行执行的多个处理线程。多个处理线程可以访问包括不同类型的元数据的全局环境，使得处理线程可以根据当前选择的锁定模式类型执行同时执行。监视处理线程的模式控制器根据当前操作条件（例如多个处理线程之间的争用量）来启动从一种类型的锁定模式切换到另一种类型的锁模式以修改共享数据。模式控制器可以从一种锁定模式切换，而不管多个进程中的任何一个是否在执行相应的事务中。可以选择最有效的锁定模式来执行并行事务。在某些情况下，切换锁定模式会使一个或多个处理线程根据新模式中止并重试相应的事务。

4. 发明申请

US20100332770A1 Concurrency Control Using Slotted Read-Write Locks 有权
标题翻译：使用开槽读写锁的并发控制
公开(公告)号：US20100332770A1
公开(公告)日：2010-12-30
申请号：US12492613
申请日：2009-06-26
申请人： David Dice , Nir N. Shavit
发明人： David Dice , Nir N. Shavit
IPC分类号： G06F12/10
CPC分类号： G06F9/526 , G06F2209/523
摘要： A system and method for concurrency control may use slotted read-write locks. A slotted read-write lock is a lock data structure associated with a shared memory area, wherein the slotted read-write lock indicates whether any thread has a read-lock and/or a write-lock for the shared memory area. Multiple threads may concurrently have the read-lock but only one thread can have the write-lock at any given time. The slotted read-write lock comprises multiple slots, each associated with a single thread. To acquire the slotted read-write lock for reading, a thread assigned to a slot performs a store operation to the slot and then attempts to determine that no other thread holds the slotted read-write lock for writing. To acquire the slotted read-write lock for writing, a thread assigned to a slot sets its write-bit and then attempts to determine that the write-lock is not held.
摘要翻译：用于并发控制的系统和方法可以使用时隙读写锁。时隙读写锁是与共享存储器区域相关联的锁定数据结构，其中，时隙读写锁定指示任何线程是否具有针对共享存储器区域的读锁定和/或写锁定。多个线程可以同时具有读锁定，但只有一个线程可以在任何给定时间具有写锁定。时隙读写锁定包括多个时隙，每个时隙与单个线程相关联。为了获取读取时隙读写锁，分配给时隙的线程对该时隙执行存储操作，然后尝试确定没有其他线程保持用于写入的时隙读写锁。要获取用于写入的时隙读写锁，分配给时隙的线程设置其写入位，然后尝试确定写锁定不被保持。

5. 发明授权

US07640402B2 Methods and apparatus to implement parallel transactions 有权
公开(公告)号：US07640402B2
公开(公告)日：2009-12-29
申请号：US11699802
申请日：2007-01-30
申请人： David Dice , Nir N. Shavit , Ori Shalev , Mark Moir
发明人： David Dice , Nir N. Shavit , Ori Shalev , Mark Moir
IPC分类号： G06F13/00
摘要： 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.

6. 发明申请

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节点上执行的另一个线程，而不会释放全局共享锁。

7. 发明授权

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.
摘要翻译：本公开描述了使用（例如，读取，修改和写入）相同的共享数据而不会对共享数据造成损坏的多个进程中的每一个进行并行操作的独特方式。例如，当执行相应的交易时，多个过程中的每个利用与全局计数器或时钟相关联的当前和过去的数据值来确定用于产生相应的交易结果的任何共享变量（通过另一个进程）被修改。如果相应的进程检测到在处理期间修改了相应进程使用的共享数据，则该进程可以中止并重试事务，而不是通过将与事务相关联的本地维护的结果存储到全局共享的数据空间来导致数据损坏。

8. 发明授权

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.
摘要翻译：与并行执行的多个处理线程中的相应一个相关联的缓存逻辑更新缓存的相应数据字段以唯一地标记其内容。标记的内容表示交易的相应读取集合。例如，在执行事务的开始时，相应的处理线程选择数据值来标记用于产生处理线程的事务结果的高速缓存的内容。每次从主存储器读取共享数据时，高速缓存存储数据的副本，并将其标记为在执行处理线程期间被使用。如果在执行处理线程期间相应的高速缓存线的唯一标记的内容恰好被移位（例如被重写），则事务被中止（而不是被提交到主存储器），因为存在另一个事务覆盖共享的可能性在相应交易期间使用的数据值。

9. 发明申请

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）事务）来尝试完成编程器指定的事务。第一个非阻塞事务可以访问一个或多个锁，但实际上可能不会获取任何锁。响应于第一非阻塞事务未能完成的指示，该方法可以包括获取另一非阻塞事务中的一组锁，其中该组锁对应于预期在该程序器中被访问的一组分区指定交易。如果获取了一组锁，则该方法可以包括执行程序员指定的事务的存储器访问操作，以及释放一组锁。

10. 发明申请

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.
摘要翻译：本公开描述了多个进程中的每一个并行操作并使用相同的共享数据而不会对共享数据造成损坏的唯一方式。例如，在提交阶段期间，相应的事务可以尝试增加全局可访问的版本信息变量并存储全局可访问版本信息变量的当前值，用于更新与经修改的数据相关联的版本信息，而不管相关联的尝试是否相应修改全局可访问版本信息变量的事务成功。作为替代模式，相应的事务只能读取和存储全局可访问版本信息变量的当前值，而不尝试在此类使用之前更新全局可访问版本信息变量。在另一个应用中，并行处理环境根据交易的自我中止率实现两种上述模式的组合。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式