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

41. 发明授权

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）。我们的实施是无障碍的。因此，在无争议的情况下效率高，依靠竞争管理机制。它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。

42. 发明授权

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.
摘要翻译：计算机系统使用瞬态阻塞同步来对共享存储器执行操作。当在多个存储器位置上执行操作时，计算机系统获得对第一存储器位置的瞬时独占访问。计算机系统然后获得对第二存储器位置的瞬时独占访问，其中对第二存储器位置的瞬时独占访问在到对第一存储器位置的瞬时独占访问期满之前直到明确地未被释放为止。

43. 发明授权

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

44. 发明授权

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”的另一个线程是唯一可以从任务队列中“弹出”任务执行的线程。因为对于每个任务队列，只有一个线程可以将任务标识符“推”给它，并且只有一个线程可以从其中“弹出”任务标识符，垃圾收集器可以在其线程之间最佳地共享动态识别的任务，而不会遭受痛苦通过组合以其他方式分离的机器指令原子强加的成本。

45. 发明授权

US06718492B1 System and method for arranging bits of a data word in accordance with a mask 有权
标题翻译：根据掩码排列数据字的位的系统和方法
公开(公告)号：US06718492B1
公开(公告)日：2004-04-06
申请号：US09545019
申请日：2000-04-07
申请人： Nir N. Shavit , Guy L. Steele, Jr. , Steven K. Heller
发明人： Nir N. Shavit , Guy L. Steele, Jr. , Steven K. Heller
IPC分类号： G06F1100
CPC分类号： G06F9/30018 , G06F7/762 , G06F9/30032
摘要： A system is disclosed for providing, from an input data word comprising a plurality of input data units having an input arrangement and a mask word comprising a plurality of mask bits each associated with one of the data units, an output data word in which the data units are arranged according to the mask bits. The system includes a bit balancer module and a plurality of rearrangement modules. The bit balancer module is configured to divide the input data units comprising the input data word into a plurality of data word portions, each data unit being assigned to one of the data word portions based on a pattern of mask bits of the mask word relative to the mask bit associated with the respective data unit. Each rearrangement module is configured to provide, from one of the data word portions and associated mask bits, an output data word portion in which the data units are arranged according to the mask bits. The data units of the output data word portions provided by the rearrangement modules are interleaved to provide the output data word.
摘要翻译：公开了一种用于从包括具有输入布置的多个输入数据单元的输入数据字和包括与数据单元之一相关联的多个掩码位的掩码字的输入数据字提供的系统，其中数据单位根据掩码位排列。该系统包括位平衡器模块和多个重排模块。位平衡器模块被配置为将包括输入数据字的输入数据单元划分成多个数据字部分，每个数据单元基于掩模字的掩码位的图案相对于数据字部分中的一个分配给相对于与相应数据单元相关联的掩码位。每个重排模块被配置为从数据字部分和关联的掩码位之一提供根据掩码位数据单元排列的输出数据字部分。由重排模块提供的输出数据字部分的数据单元被交织以提供输出数据字。

46. 发明授权

US06304972B1 Secure software system and related techniques 失效
公开(公告)号：US06304972B1
公开(公告)日：2001-10-16
申请号：US09476557
申请日：2000-01-03
申请人： Nir N. Shavit
发明人： Nir N. Shavit
IPC分类号： G06F1100
CPC分类号： G06F21/125
摘要： A secure software system includes a transformation processor for transforming an original program capable of being executed on a lessee site into a vendor server program, a first program intended to be executed at the lessee site which lacks some of the functionality of the original program and a second program. The first program provides some of the computation of the original program but is unable to provide all of the functionality of the Original Program and requires cooperation with the second program which corresponds to an excised portion of the original program to provide the functionality of original program. The excised program is executed or otherwise utilized by a vendor server program which, in one embodiment, is generated by the transformation processor. With this arrangement, the lessee obtains the total functionality of the original program without having access to the original program code and the excised program is selected such that it would be relatively difficult to recreate the total functionality of the original program.

47. 发明授权

US10049127B1 Meta-transactional synchronization 有权
公开(公告)号：US10049127B1
公开(公告)日：2018-08-14
申请号：US10995885
申请日：2004-11-23
申请人： Nir N. Shavit , Maurice P. Herlihy
发明人： Nir N. Shavit , Maurice P. Herlihy
IPC分类号： G06F7/00 , G06F17/30
摘要： Efficiency with respect to traditional techniques is a key issue facing designers of software transactional synchronization mechanisms. Meta-transactional synchronization allows integration of transactional support into an object-oriented programming language, such as the Java language through the existing synchronization structure of the JVM. Meta-transactional synchronization provides source-level transactional operations that co-exist with synchronized operations. An implementation of a shared object in an object-oriented programming language tracks concurrently executing transactions attempting to access the shared object with at least one header word of the shared object.

48. 发明授权

US08060879B2 Predictive log synchronization 有权
标题翻译：预测日志同步
公开(公告)号：US08060879B2
公开(公告)日：2011-11-15
申请号：US11442870
申请日：2006-05-30
申请人： Nir N. Shavit , Ori Shalev
发明人： Nir N. Shavit , Ori Shalev
IPC分类号： G06F9/46
CPC分类号： G06F9/526
摘要： A method for coordinating shared access to data objects comprises applying modification operations to a data object from a first thread of a plurality of threads on behalf of all the other threads during a session in which the first thread owns a lock on the data object. Each modification operation corresponds to a respective entry recorded in a log associated with the data object by a respective thread. The method may further comprise predicting, for a second thread, a result of a particular operation requested by the second thread on the data object. The result may be predicted using log entries corresponding to modification operations that have not yet been applied to the data object. In addition, the method includes performing one or more other operations in a non-blocking manner from the second thread during the session, where at least one other operation is dependent on the predicted result.
摘要翻译：用于协调对数据对象的共享访问的方法包括在第一线程拥有数据对象上的锁定的会话期间，代表所有其他线程从多个线程的第一线程向数据对象应用修改操作。每个修改操作对应于通过相应线程记录在与数据对象相关联的日志中的相应条目。该方法还可以包括针对第二线程预测第二线程在数据对象上请求的特定操作的结果。可以使用对应于尚未应用于数据对象的修改操作的日志条目来预测结果。此外，该方法包括在会话期间以非阻塞方式从第二线程执行一个或多个其他操作，其中至少一个其他操作取决于预测结果。

49. 发明授权

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指令的同时执行的实例之间的死锁。其他实现方式将程序员的死锁责任推迟。

50. 发明授权

US07779165B2 Scalable method for producer and consumer elimination 有权
标题翻译：消除生产者和消费者的可扩展方法
公开(公告)号：US07779165B2
公开(公告)日：2010-08-17
申请号：US11325150
申请日：2006-01-04
申请人： Mark S. Moir , Daniel S. Nussbaum , Ori Shalev , Nir N. Shavit
发明人： Mark S. Moir , Daniel S. Nussbaum , Ori Shalev , Nir N. Shavit
IPC分类号： G06F3/00
CPC分类号： G06F9/526 , G06F9/466 , G06F2209/521
摘要： Producers and consumer processes may synchronize and transfer data using a shared data structure. After locating a potential transfer location that indicates an EMPTY status, a producer may store data to be transferred in the transfer location. A producer may use a compare-and-swap (CAS) operation to store the transfer data to the transfer location. A consumer may subsequently read the transfer data from the transfer location and store, such as by using a CAS operation, a DONE status indicator in the transfer location. The producer may notice the DONE indication and may then set the status location back to EMPTY to indicate that the location is available for future transfers, by the same or a different producer. The producer may also monitor the transfer location and time out if no consumer has picked up the transfer data.
摘要翻译：生产者和消费者流程可以使用共享数据结构来同步和传输数据。在找到指示EMPTY状态的潜在转移位置之后，生产者可以将要传送的数据存储在传送位置。生产者可以使用比较和交换（CAS）操作来将转移数据存储到传送位置。消费者随后可以从传送位置读取传送数据，例如通过使用CAS操作存储传送位置中的DONE状态指示符。生产者可以注意到DONE指示，然后可以将状态位置设置回EMPTY，以指示该位置可用于由相同或不同的生产者进行将来的转移。如果没有消费者拿起传输数据，生产者也可以监控传送位置和超时。

你已经成功收藏专利！

检索式保存成功!

IPRDB

热门服务

关于我们

友情链接

联系方式