公开(公告)号：US07882505B2

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

申请号：US11090398

申请日：2005-03-25

Applicant: Alexander Garthwaite ,  David Dice ,  Derek R. White

Inventor： Alexander Garthwaite ,  David Dice ,  Derek R. White

IPC: G06F9/46 ,  G06F13/00

CPC classification number: G06F9/5016 ,  G06F2209/507

Abstract: In a multi-processor multi-threaded computer system, resources are dynamically assigned during program operation to either threads or processors in such a manner that resource usage is maximized. In one embodiment, the choice of whether to assign resources to threads or processors is dependent on the number of threads versus the number of processors. In another embodiment, when the system is operating in one assignment mode, the amount of wasted resources is measured and when this measured amount exceeds a predetermined threshold based on the maximum resources that could be wasted were the system operating in the other assignment mode, the assignment is switched to the other assignment mode.

Abstract translation: 在多处理器多线程计算机系统中，在程序操作期间以资源使用最大化的方式将资源动态地分配给线程或处理器。 在一个实施例中，是否向线程或处理器分配资源的选择取决于线程的数量与处理器的数量。 在另一个实施例中，当系统在一个分配模式下操作时，测量浪费的资源量，并且当系统以另一分配模式运行时，基于可浪费的最大资源，该测量量超过预定阈值时， 分配切换到其他分配模式。

公开(公告)号：US20100333095A1

公开(公告)日：2010-12-30

申请号：US12492627

申请日：2009-06-26

Applicant: Nir N. Shavit ,  David Dice

Inventor： Nir N. Shavit ,  David Dice

IPC: G06F9/46 ,  G06F12/14

CPC classification number: G06F9/3004 ,  G06F9/30087 ,  G06F9/467 ,  G06F2209/523

Abstract: A method and system for acquiring multiple software locks in bulk is disclosed. When multiple locks need to be acquired, such as for atomic transactions in transactional memory systems, the disclosed techniques may be applied to consolidate computationally expensive memory barrier operations across the lock acquisitions. A system may acquire multiple locks in bulk, at least in part, by modifying values in one or more fields of multiple locks and by then performing a memory barrier operation to ensure that the modified values in the multiple locks are visible to other application threads. The technique may be repeated for locks that the system fails to acquire during earlier iterations until all required locks are acquired. The described technique may be applied to various scenarios including static and/or dynamic transactional locking protocols.

Abstract translation: 公开了一种用于批量获取多个软件锁的方法和系统。 当需要获取多个锁定时，诸如在事务存储器系统中的原子事务时，所公开的技术可以被应用于整合锁获取的计算上昂贵的存储器屏障操作。 系统可以批量获取多个锁，至少部分地通过修改多个锁的一个或多个字段中的值，然后执行存储器障碍操作来确保多个锁中的修改值对于其他应用程序线程是可见的。 对于在早期迭代期间系统无法获取的锁，可以重复该技术，直到获取所有所需的锁。 所描述的技术可以应用于各种场景，包括静态和/或动态事务锁定协议。

公开(公告)号：US07844973B1

公开(公告)日：2010-11-30

申请号：US11008500

申请日：2004-12-09

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/46 ,  G06F3/00 ,  G06F5/00 ,  G06F12/00 ,  G06F12/14 ,  G06F7/00 ,  G06F17/30

CPC classification number: G06F9/52

Abstract: A system to control access to a resource by a group of threads requiring access to the resource provides exclusive access to the resource within a computerized device on behalf of a first thread by allowing the first thread exclusive access of a monitor associated with the resource. An entry list of threads is maintained that are awaiting access to the monitor using block-free list joining mechanisms including a thread chaining technique, a push/pop technique, and a detach, modify, reattach technique to allow threads to join the entry list of threads without blocking operation of the threads. Upon completion of access to the resource by the first thread, the system operates the first thread to manipulate the entry list of threads to identify a successor thread as being a candidate thread to obtain exclusive access of the monitor to gain exclusive access to the resource.

Abstract translation: 通过允许访问资源的线程组来控制对资源的访问的系统通过允许与资源相关联的监视器的第一线程独占访问来代表第一线程提供对计算机化设备内的资源的独占访问。 维护线程的条目列表，其等待使用无块列表连接机制访问监视器，包括线程链接技术，推/弹技术以及分离，修改，重新连接技术，以允许线程加入条目列表 线程无阻塞线程操作。 在完成由第一线程对资源的访问之后，系统操作第一线程以操纵线程的入口列表，以将后续线程标识为候选线程，以获得监视器的独占访问以获得对资源的独占访问。

公开(公告)号：US07747996B1

公开(公告)日：2010-06-29

申请号：US11420354

申请日：2006-05-25

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/44

CPC classification number: G06F9/526 ,  G06F8/72

Abstract: A method to enabling interoperability of a locking synchronization method with a lock-free synchronization method in a multi-threaded environment is presented. The method examines a class file for mutable fields contained in critical code sections. The mutable fields are transferred to a shadow record and a pointer is substituted in the class field for each transferred mutable field. Code is altered so that the lock-free synchronization method is used if a lock is not held on the object. Atomic compare and swap operations are employed after mutable fields are updated during execution of the lock-free synchronization method.

Abstract translation: 提出了一种在多线程环境中实现锁定同步方法与无锁定同步方法的互操作性的方法。 该方法检查关键代码段中包含的可变字段的类文件。 可变字段被转移到阴影记录，并且在每个传输的可变字段的类字段中替换指针。 代码被更改，以便如果对象上没有锁定，则使用无锁同步方法。 在执行无锁同步方法的可变字段更新之后，采用原子比较和交换操作。

公开(公告)号：US07644409B2

公开(公告)日：2010-01-05

申请号：US10861795

申请日：2004-06-04

Applicant: David Dice ,  Hui Huang ,  Mingyao Yang

Inventor： David Dice ,  Hui Huang ,  Mingyao Yang

IPC: G06F9/46 ,  G06F12/00 ,  G06F9/44 ,  G06F9/45

CPC classification number: G06F9/52

Abstract: A technique for accessing a shared resource of a computerized system involves running a first portion of a first thread within the computerized system, the first portion (i) requesting a lock on the shared resource and (ii) directing the computerized system to make operations of a second thread visible in a correct order. The technique further involves making operations of the second thread visible in the correct order in response to the first portion of the first thread running within the computerized system, and running a second portion of the first thread within the computerized system to determine whether the first thread has obtained the lock on the shared resource. Such a technique alleviates the need for using a MEMBAR instruction in the second thread.

Abstract translation: 用于访问计算机化系统的共享资源的技术包括运行计算机化系统内的第一线程的第一部分，第一部分（i）请求锁定共享资源，以及（ii）引导计算机化系统使 第二个线程以正确的顺序可见。 该技术还涉及使第二线程的操作响应于在计算机化系统内运行的第一线程的第一部分以正确的顺序可见，并且在计算机化系统内运行第一线程的第二部分以确定第一线程 已获得共享资源上的锁定。 这种技术减轻了在第二线程中使用MEMBAR指令的需要。

公开(公告)号：US07496918B1

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

申请号：US10857811

申请日：2004-06-01

Applicant: David Dice ,  Mandy L. Chung

Inventor： David Dice ,  Mandy L. Chung

IPC: G06F9/46 ,  G06F15/173

CPC classification number: G06F9/524

Abstract: A lightweight, concurrent detection mechanism avoids global thread suspension by operating during runtime with threads under examination. A particular configuration combines a dependency (“waits for”) snapshot with a progression check to determine advancement of purportedly deadlocked threads. Thread blocking is enumerated in a table or graph which denotes dependencies of threads and the corresponding resources. For identified circular dependencies, a successive transition, or progression check ratifies the potential deadlock. A transition counter corresponding to each thread is analyzed in the progression check. The transition counter is indicative of a change in state for the process in question, hence is indicative of instruction execution, an activity not performed by a blocked process. Deadlock is therefore ratified if the transition counters associated with the threads in the potential deadlock have not advanced.

Abstract translation: 轻量级的并发检测机制通过在运行时通过在线检查来避免全局线程挂起。 特定配置将依赖关系（“等待”）快照​​与进度检查相结合，以确定据称是死锁线程的进展。 在表或图中列举了线程阻塞，这表示线程和相应资源的依赖关系。 对于识别的循环依赖关系，连续的过渡或进度检查会批准潜在的死锁。 在进度检查中分析对应于每个线程的转换计数器。 转移计数器表示所讨论的过程的状态变化，因此表示指令执行，未被阻塞进程执行的活动。 如果与潜在死锁中的线程相关联的转接计数器未提前，则死锁将被批准。

公开(公告)号：US07475397B1

公开(公告)日：2009-01-06

申请号：US10900636

申请日：2004-07-28

Applicant: Alexander T. Garthwaite ,  David Dice

Inventor： Alexander T. Garthwaite ,  David Dice

IPC: G06F9/46 ,  G06F9/30

CPC classification number: G06F9/52 ,  G06F9/30087 ,  G06F9/3009 ,  G06F9/522

Abstract: A technique provides a remote serialization guarantee within a computerized system. The technique involves (i) receiving a serialization command from a first thread running on a first processor of the computerized system; (ii) running, on a second processor, a second thread up to a serialization point; and (iii) outputting a serialization result to the first thread in response to the serialization command. The serialization result indicates that the second thread has run up to the serialization point. Such operation enables the first and second threads to robustly coordinate access to a shared resource by the first thread incurring both the burden of employing a MEMBAR instruction and the burden of providing the remote serialization command when attempting to access the shared resource, and the second thread not running any MEMBAR instruction when attempting to access the shared resource to enable the second thread to run more efficiently.

Abstract translation: 一种技术在计算机化系统中提供远程串行化保证。 该技术涉及（i）从在计算机化系统的第一处理器上运行的第一线程接收序列化命令; （ii）在第二处理器上运行直到序列化点的第二线程; 和（iii）响应于序列化命令向第一线程输出序列化结果。 序列化结果表明第二个线程已经运行到序列化点。 这样的操作使得第一和第二线程能够稳健地协调由第一线程访问共享资源，同时引起使用MEMBAR指令的负担和在尝试访问共享资源时提供远程串行化命令的负担，第二线程 尝试访问共享资源时不运行任何MEMBAR指令，以使第二个线程更有效地运行。

公开(公告)号：US20080256074A1

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

申请号：US12101316

申请日：2008-04-11

Applicant: Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

Inventor： Yosef Lev ,  Nir N. Shavit ,  David Dice ,  Mark A. Moir

IPC: G06F17/30

CPC classification number: G06F9/466 ,  G06F9/526

Abstract: Apparatus, methods, and program products are disclosed that provide a technology that implicitly isolates a portion of a transactional memory that is shared between multiple threads for exclusive use by an isolating thread without the possibility of other transactions modifying the isolated portion of the transactional memory.

Abstract translation: 公开了装置，方法和程序产品，其提供隐含地隔离在多个线程之间共享的事务存储器的一部分以供隔离线程独占使用的技术，而不会有其他事务修改事务存储器的隔离部分的可能性。

公开(公告)号：US06877088B2

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

申请号：US10039368

申请日：2002-01-03

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/318 ,  G06F9/38 ,  G06F12/10 ,  G06F12/00

CPC classification number: G06F9/383 ,  G06F9/3834 ,  G06F9/3842 ,  G06F12/1072 ,  Y02D10/13

Abstract: Mechanisms and techniques operate in a computerized device to enable or disable speculative execution of instructions such as reordering of load and store instructions a multiprocessing computerized device. The mechanisms and techniques provide a speculative execution controller that can detect a multiaccess memory condition between the first and second processors, such as concurrent access to shared data pages via page table entries. This can be done by monitoring page table entry accesses by other processors. The speculative execution controller sets a value of a speculation indicator in the memory system based on the multiaccess memory condition. If the value of the speculation indicator indicates that speculative execution of instructions is allowed in the computerized device, the speculative execution controller allows speculative execution of instructions in at least one of the first and second processors in the computerized device. If the value of the speculation indicator indicates that speculative execution of instructions is not allowed in the computerized device, the speculative execution controller does not allow speculative execution of instructions.

Abstract translation: 机制和技术在计算机化设备中操作以启用或禁用诸如重新排序负载和存储指令的指令的推测性执行多处理计算机化设备。 这些机制和技术提供了可以检测第一和第二处理器之间的多处理存储器条件的推测性执行控制器，诸如通过页表条目对共享数据页的并发访问。 这可以通过监视其他处理器的页表输入访问来完成。 推测执行控制器基于多路访问存储器条件设置存储器系统中的推测指示符的值。 如果推测指示符的值指示在计算机化设备中允许推测执行指令，则推测执行控制器允许在计算机化设备中的第一和第二处理器中的至少一个处理器中推测执行指令。 如果推测指标的值表示在计算机化设备中不允许推测执行指令，则推测性执行控制器不允许推测执行指令。

公开(公告)号：US06854048B1

公开(公告)日：2005-02-08

申请号：US09924891

申请日：2001-08-08

Applicant: David Dice

Inventor： David Dice

IPC: G06F9/318 ,  G06F9/38 ,  G06F12/10 ,  G06F9/312

CPC classification number: G06F9/3834 ,  G06F9/30181 ,  G06F9/3826 ,  G06F9/3842 ,  G06F12/1072

Abstract: Mechanisms and techniques operate in a computerized device to enable or disable speculative execution of instructions such as load instructions on one or more processors in the computerized device. The mechanisms and techniques can execute a set of instructions on a processor in the computerized device and can detect a value of a speculation indicator. If the value of the speculation indicator indicates that speculative execution of load instructions is allowed in the computerized device, the mechanisms and techniques allow speculative execution of load instructions in the processor, whereas if the value of the speculation indicator indicates that speculative execution of load instructions is not allowed in the computerized device, the mechanisms and techniques do not allow speculative execution of load instructions in the processor. An instruction in code can turn on and off the speculation indicator, which can be one or more bits in a control register or in page table entries associated with pages of memory. Under certain conditions, speculative execution correction mechanisms can be enabled, disabled or removed from a processor.

Abstract translation: 机构和技术在计算机化设备中操作以启用或禁用诸如计算机化设备中的一个或多个处理器上的指令的推测性执行。 机构和技术可以在计算机化设备中的处理器上执行一组指令，并且可以检测推测指示符的值。 如果推测指标的值表示在计算机化设备中允许推测执行加载指令，则机制和技术允许在处理器中推测执行加载指令，而如果推测指示符的值表示加载指令的推测性执行 在计算机化设备中不允许，机制和技术不允许在处理器中推测执行加载指令。 代码中的指令可以打开和关闭推测指示器，该指示器可以是控制寄存器中的一个或多个位或与存储器页面相关联的页表项。 在某些条件下，可以启用，禁用或从处理器中删除推测执行校正机制。