公开(公告)号：US20070198519A1

公开(公告)日：2007-08-23

申请号：US11475814

申请日：2006-06-27

Applicant: David Dice ,  Ori Shalev ,  Nir Shavit

Inventor： David Dice ,  Ori Shalev ,  Nir Shavit

IPC: G06F17/30

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: 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.

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

公开(公告)号：US20070198979A1

公开(公告)日：2007-08-23

申请号：US11475716

申请日：2006-06-27

Applicant: David Dice ,  Nir Shavit

Inventor： David Dice ,  Nir Shavit

IPC: G06F9/46

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: For each of multiple processes executing in parallel, as long as corresponding version information associated with a respective set of one or more shared variables used for computational purposes has not changed during execution of a respective transaction, results of the respective transaction can be globally committed to memory without causing data corruption. If version information associated with one or more respective shared variables (used to produce the transaction results) happens to change during a process of generating respective results, then a respective process can identify that another process modified the one or more respective shared variables during execution and that its transaction results should not be committed to memory. In this latter case, the transaction repeats itself until it is able to commit respective results without causing data corruption.

Abstract translation: 对于并行执行的多个进程中的每一个，只要在用于计算目的的一个或多个共享变量的相应集合相关联的对应版本信息在相应事务的执行期间没有改变时，相应的事务的结果可以被全局地承诺 内存而不会导致数据损坏。 如果与一个或多个相应的共享变量（用于产生交易结果）相关联的版本信息在生成相应结果的过程中发生变化，则相应过程可以识别另一个进程在执行期间修改了一个或多个相应的共享变量，并且 它的交易结果不应该被提交到内存。 在后一种情况下，事务重复，直到它能够提交相应的结果而不会导致数据损坏。

公开(公告)号：US20070198792A1

公开(公告)日：2007-08-23

申请号：US11475262

申请日：2006-06-27

Applicant: David Dice ,  Nir Shavit

Inventor： David Dice ,  Nir Shavit

IPC: G06F12/14

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: 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.

Abstract translation: 计算机系统包括并行执行的多个处理线程。 多个处理线程可以访问包括不同类型的元数据的全局环境，使得处理线程可以根据当前选择的锁定模式类型执行同时执行。 监视处理线程的模式控制器根据当前操作条件（例如多个处理线程之间的争用量）来启动从一种类型的锁定模式切换到另一种类型的锁模式以修改共享数据。 模式控制器可以从一种锁定模式切换，而不管多个进程中的任何一个是否在执行相应的事务中。 可以选择最有效的锁定模式来执行并行事务。 在某些情况下，切换锁定模式会使一个或多个处理线程根据新模式中止并重试相应的事务。

公开(公告)号：US20070198781A1

公开(公告)日：2007-08-23

申请号：US11488618

申请日：2006-07-18

Applicant: David Dice ,  Nir Shavit

Inventor： David Dice ,  Nir Shavit

IPC: G06F13/28 ,  G06F12/00

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: 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.

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

公开(公告)号：US20070198978A1

公开(公告)日：2007-08-23

申请号：US11475604

申请日：2006-06-27

Applicant: David Dice ,  Nir Shavit

Inventor： David Dice ,  Nir Shavit

IPC: G06F9/46

CPC classification number: G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

Abstract: A computer system includes multiple processing threads that execute in parallel. The multiple processing threads have access to a global environment including i) shared data utilized by the multiple processing threads, ii) a globally accessible register or buffer of version information that changes each time a respective one of the multiple processing threads modifies the shared data, and iii) respective lock information indicating whether one of the multiple processing threads has locked the shared data preventing other processing threads from modifying the shared data. To prevent data corruption, each of the processing threads aborts if a given processing thread detects a change in the version information or another processing thread has a lock on the shared data. This technique is well suited for use in applications such as processing threads that support a high number of reads with a corresponding number of fewer respective writes to shared data.

Abstract translation: 计算机系统包括并行执行的多个处理线程。 所述多个处理线程可以访问全球环境，包括i）所述多个处理线程使用的共享数据，ii）版本信息的全局可访问寄存器或缓冲器，每当所述多个处理线程的相应一个线程修改所述共享数据时， 以及iii）相应的锁定信息，指示多个处理线程中的一个是否锁定了共享数据，防止其他处理线程修改共享数据。 为了防止数据损坏，如果给定的处理线程检测到版本信息的更改或另一个处理线程对共享数据有锁定，则每个处理线程中止。 该技术非常适用于诸如处理支持大量读取的线程的应用程序，其中相应数量的对共享数据的相应数量较少。

公开(公告)号：US09367363B2

公开(公告)日：2016-06-14

申请号：US12238172

申请日：2008-09-25

Applicant: Mark S. Moir ,  David Dice

Inventor： Mark S. Moir ,  David Dice

IPC: G06F9/46 ,  G06F9/52

CPC classification number: G06F9/52 ,  G06F9/467

Abstract: Systems and methods for integrating multiple best effort hardware transactional support mechanisms, such as Read Set Monitoring (RSM) and Best Effort Hardware Transactional Memory (BEHTM), in a single transactional memory implementation are described. The best effort mechanisms may be integrated such that the overhead associated with support of multiple mechanisms may be reduced and/or the performance of the resulting transactional memory implementations may be improved over those that include any one of the mechanisms, or an un-integrated collection of multiple such mechanisms. Two or more of the mechanisms may be employed concurrently or serially in a single attempt to execute a transaction, without aborting or retrying the transaction. State maintained or used by a first mechanism may be shared with or transferred to another mechanism for use in execution of the transaction. This transfer may be performed automatically by the integrated mechanisms (e.g., without user, programmer, or software intervention).

Abstract translation: 描述了在单个事务存储器实现中集成多个尽力而为的硬件事务支持机制（诸如读集监视（RSM）和最佳努力硬件事务存储器（BEHTM））的系统和方法。 可以集成尽力而为的机制，使得可以减少与多个机制的支持相关联的开销，和/或可以提高所产生的事务存储器实现的性能，而不是包括机构中的任何一个或非集成集合 的多个这样的机制。 可以在不中止或重试事务的情况下，单次尝试同时执行或连续执行两个或多个机制来执行事务。 由第一机制维护或使用的状态可以与另一机制共享或转移以用于执行交易。 该传送可以由集成机制（例如，没有用户，程序员或软件干预）自动执行。

公开(公告)号：US09158596B2

公开(公告)日：2015-10-13

申请号：US13051877

申请日：2011-03-18

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/46 ,  G06F9/52

CPC classification number: G06F9/526 ,  G06F2209/522

Abstract: A partitioned ticket lock may control access to a shared resource, and may include a single ticket value field and multiple grant value fields. Each grant value may be the sole occupant of a respective cache line, an event count or sequencer instance, or a sub-lock. The number of grant values may be configurable and/or adaptable during runtime. To acquire the lock, a thread may obtain a value from the ticket value field using a fetch-and-increment type operation, and generate an identifier of a particular grant value field by applying a mathematical or logical function to the obtained ticket value. The thread may be granted the lock when the value of that grant value field matches the obtained ticket value. Releasing the lock may include computing a new ticket value, generating an identifier of another grant value field, and storing the new ticket value in the other grant value field.

Abstract translation: 分区票锁可以控制对共享资源的访问，并且可以包括单个票证值字段和多个授权值字段。 每个授权值可以是相应的高速缓存行，事件计数或定序器实例或子锁的唯一占用者。 许可值的数量可以在运行时间内配置和/或适应。 为了获取锁，线程可以使用获取和增量类型操作从票值字段获得值，并且通过对获得的票值应用数学或逻辑函数来生成特定授权值字段的标识符。 当该授权值字段的值与获得的票值匹配时，线程可以被授予锁定。 释放锁可以包括计算新的票值，生成另一授​​权值字段的标识符，并将新的票值存储在另一授权值字段中。

公开(公告)号：US08826249B2

公开(公告)日：2014-09-02

申请号：US12708014

申请日：2010-02-18

Applicant: David Dice ,  Virendra J. Marathe ,  Mark S. Moir

Inventor： David Dice ,  Virendra J. Marathe ,  Mark S. Moir

IPC: G06F9/45 ,  G06F9/455

CPC classification number: G06F9/45516 ,  G06F8/456

Abstract: In modern multi-threaded environments, threads often work cooperatively toward providing collective or aggregate throughput for an application as a whole. Optimizing in the small for “thread local” common path latency is often but not always the best approach for a concurrent system composed of multiple cooperating threads. Some embodiments provide a technique for augmenting traditional code emission with thread-aware policies and optimization strategies for a multi-threaded application. During operation, the system obtains information about resource contention between executing threads of the multi-threaded application. The system analyzes the resource contention information to identify regions of the code to be optimized. The system recompiles these identified regions to produce optimized code, which is then stored for subsequent execution.

Abstract translation: 在现代多线程环境中，线程通常协同工作，为整个应用程序提供集体或聚合吞吐量。 对于“线程本地”公共路径延迟的优化通常并不总是对由多个协作线程组成的并发系统的最佳方法。 一些实施例提供了一种用于针对多线程应用程序的线程感知策略和优化策略来增加传统代码排放的技术。 在运行期间，系统获取有关多线程应用程序的执行线程之间资源争用的信息。 系统分析资源争用信息以识别要优化的代码区域。 系统重新编译这些识别的区域以产生优化的代码，然后将其存储用于随后的执行。

公开(公告)号：US20120311606A1

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

申请号：US13152079

申请日：2011-06-02

Applicant: Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

Inventor： Virendra J. Marathe ,  Nir N. Shavit ,  David Dice

IPC: G06F9/46

CPC classification number: G06F9/526

Abstract: 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.

Abstract translation: 本文描述的系统和方法可以用于使用平坦组合来实现可扩展的，分级的基于队列的锁。 在共享内存的核心集群中的处理器核心上执行的线程可以使用非原子操作来发布用于获取集群的发布列表的节点中的共享锁定的请求。 组合线程可以构建一个有序（逻辑）本地请求队列，其包括其自己的节点和包含锁定请求的其他线程（在集群中）的节点。 组合器线程可以将本地请求队列拼接成用于共享锁的（逻辑）全局请求队列作为子队列。 已经将其请求已经发布在已经组合到本地子队列中并被拼接到全局请求队列中的节点的线程可以旋转其节点中的所有权所有者指示符，直到被授予共享锁为止。

公开(公告)号：US20120089803A1

公开(公告)日：2012-04-12

申请号：US12899493

申请日：2010-10-06

Applicant: David Dice

Inventor： David Dice

IPC: G06F12/02

CPC classification number: G06F12/0223 ,  G06F12/023 ,  G06F12/0802 ,  G06F12/10 ,  G06F2212/653 ,  G06F2212/657

Abstract: A method for managing a memory, including obtaining a number of indices and a cache line size of a cache memory, computing a cache page size by multiplying the number of indices by the cache line size, calculating a greatest common denominator (GCD) of the cache page size and a first size class, incrementing, in response to the GCD of the cache page size and the first size class exceeding the cache line size, the first size class to generate an updated first size class, calculating a GCD of the cache page size and the updated first size class, creating, in response to the GCD of the cache page size and the updated first size class being less than the cache line size, a first superblock in the memory including a first plurality of blocks of the updated first size class, and creating a second superblock in the memory.

Abstract translation: 一种用于管理存储器的方法，包括获得多个索引和高速缓存存储器的高速缓存行大小，通过将索引数乘以高速缓存行大小来计算高速缓存页大小，计算最大公分母（GCD） 缓存页面大小和第一大小类别，响应于高速缓存页大小的GCD和超过高速缓存行大小的第一大小类而递增，生成更新的第一大小类的第一大小类，计算高速缓存的GCD 页面大小和更新的第一大小类别，响应于缓存页面大小的GCD和更新的第一大小类别小于高速缓存行大小，创建存储器中的第一超级块，其包括更新的第一大小块 第一大小类，并在内存中创建第二个超级块。