-
公开(公告)号：US06993770B1
公开(公告)日：2006-01-31
申请号：US09837671
申请日：2001-04-18
IPC分类号： G06F9/54
CPC分类号： G06F9/526 , G06F12/0261 , Y10S707/99944 , Y10S707/99947
摘要： We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
摘要翻译： 我们提出一种方法，用于将依赖于垃圾回收的并行数据结构实现转换为不具有相同的实现。 假设垃圾收集的存在使得设计并发数据结构的实现变得更加容易，特别是因为它消除了众所周知的ABA问题。 然而，这个假设限制了它们的适用性。 我们的研究结果表明，对于重要的数据结构类，设计人员可以首先解决实现依赖于垃圾回收的更容易的问题，然后应用我们的方法来实现与垃圾回收无关的实现。 我们的方法是基于众所周知的参考计数技术，并采用双重比较和交换操作。
-
72.发明授权System and method for performing memory management using hardware transactions 有权使用硬件事务执行内存管理的系统和方法公开(公告)号：US09043363B2
公开(公告)日：2015-05-26
申请号：US13167606
申请日：2011-06-23
CPC分类号： G06F9/467 , G06F12/0261 , G06F12/0815
摘要： The systems and methods described herein may be used to implement a shared dynamic-sized data structure using hardware transactional memory to simplify and/or improve memory management of the data structure. An application (or thread thereof) may indicate (or register) the intended use of an element of the data structure and may initialize the value of the data structure element. Thereafter, another thread or application may use hardware transactions to access the data structure element while confirming that the data structure element is still part of the dynamic data structure and/or that memory allocated to the data structure element has not been freed. Various indicators may be used determine whether memory allocated to the element can be freed.
摘要翻译： 本文描述的系统和方法可以用于使用硬件事务存储器实现共享的动态大小的数据结构，以简化和/或改善数据结构的存储器管理。 应用程序（或其线程）可以指示（或注册）数据结构的元素的预期用途，并且可以初始化数据结构元素的值。 此后，另一个线程或应用程序可以使用硬件事务来访问数据结构元素，同时确认数据结构元素仍然是动态数据结构的一部分，和/或分配给数据结构元素的存储器尚未被释放。 可以使用各种指标来确定分配给元素的内存是否可以被释放。
-
73.发明授权System and method for performing dynamic mixed mode read validation in a software transactional memory 有权用于在软件事务存储器中执行动态混合模式读取验证的系统和方法公开(公告)号：US08595446B2
公开(公告)日：2013-11-26
申请号：US12626333
申请日：2009-11-25
申请人： Yosef Lev , Marek K. Olszewski , Mark S. Moir
发明人： Yosef Lev , Marek K. Olszewski , Mark S. Moir
CPC分类号： G06F9/467 , G06F9/5016 , G06F9/526
摘要： The transactional memory system described herein may apply a mix of read validation techniques to validate read operations (e.g., invisible reads and/or semi-visible reads) in different transactions, or to validate different read operations within a single transaction (including reads of the same location). The system may include mechanisms to dynamically determine that a read validation technique should be replaced by a different technique for reads of particular locations or for all subsequent reads, and/or to dynamically adjust the balance between different read validation techniques to manage costs. Some of the read validation techniques may be supported by hardware transactional memory (HTM). The system may delay acquisition of ownership records for reading, and may acquire two or more ownership records back-to-back (e.g., within a single hardware transaction). The user code of a software transaction may be divided into multiple segments, some of which may be executed within a hardware transaction.
摘要翻译： 本文描述的事务存储器系统可以应用读取验证技术的混合来验证不同事务中的读取操作（例如，不可见的读取和/或半可见读取），或验证单个事务中的不同读取操作（包括 相同的位置）。 该系统可以包括动态地确定读取验证技术应该被用于读取特定位置或所有后续读取的不同技术所替代的机制，和/或动态地调整不同读取验证技术之间的平衡来管理成本。 一些读取验证技术可能由硬件事务存储器（HTM）支持。 系统可能会延迟获取所有权记录以进行读取，并可能背靠背获取两个或多个所有权记录（例如，在单个硬件事务中）。 软件事务的用户代码可以被划分成多个段，其中一些可以在硬件事务中执行。
-
74.发明申请System and Method for Providing Locale-Based Optimizations In a Transactional Memory 有权在事务性存储器中提供基于区域的优化的系统和方法公开(公告)号：US20110246724A1
公开(公告)日：2011-10-06
申请号：US12750884
申请日：2010-03-31
申请人： Virendra J. Marathe , Mark S. Moir
发明人： Virendra J. Marathe , Mark S. Moir
CPC分类号： G06F9/467
摘要： The system and methods described herein may reduce read/write fence latencies and cache pressure related to STM metadata accesses. These techniques may leverage locality information (as reflected by the value of a respective locale guard) associated with each of a plurality of data partitions (locales) in a shared memory to elide various operations in transactional read/write fences when transactions access data in locales owned by their threads. The locale state may be disabled, free, exclusive, or shared. For a given memory access operation of an atomic transaction targeting an object in the shared memory, the system may implement the memory access operation using a contention mediation mechanism selected based on the value of the locale guard associated with the locale in which the target object resides. For example, a traditional read/write fence may be employed in some memory access operations, while other access operations may employ an optimized read/write fence.
摘要翻译： 本文描述的系统和方法可以减少与STM元数据访问相关的读/写栅栏延迟和高速缓存压力。 这些技术可以利用与共享存储器中的多个数据分区（区域设置）中的每一个相关联的局部性信息（由相应的区域保护的值反映），以便当事务访问区域中的数据时，去除事务读/写栅栏中的各种操作 由他们的线程拥有。 可以禁用，免费，排他或共享地区状态。 对于针对共享存储器中的对象的原子事务的给定存储器访问操作，系统可以使用基于与目标对象所在的区域设置相关联的区域保护的值来选择的争用中介机制来实现存储器访问操作 。 例如，在一些存储器访问操作中可以采用传统的读/写栅栏，而其他访问操作可以采用优化的读/写栅栏。
-
公开(公告)号：US08019785B2
公开(公告)日：2011-09-13
申请号：US12130635
申请日：2008-05-30
IPC分类号： G06F7/00
CPC分类号： G06F9/524 , G06F9/526 , Y10S707/99944 , Y10S707/99947
摘要： We explore techniques for designing nonblocking algorithms that do not require advance knowledge of the number of processes that participate, whose time complexity and space consumption both adapt to various measures, rather than being based on predefined worst-case scenarios, and that cannot be prevented from future memory reclamation by process failures. These techniques can be implemented using widely available hardware synchronization primitives. We present our techniques in the context of solutions to the well-known Collect problem. We also explain how our techniques can be exploited to achieve other results with similar properties; these include long-lived renaming and dynamic memory management for nonblocking data structures.
摘要翻译： 我们探索设计非阻塞算法的技术，这些算法不需要提前了解参与过程的数量，其时间复杂度和空间消耗都适应于各种测量，而不是基于预定义的最坏情况，并且不能防止 未来内存回收过程失败。 可以使用广泛可用的硬件同步原语来实现这些技术。 我们在众所周知的收集问题的解决方案的背景下介绍我们的技术。 我们还解释了如何利用我们的技术来实现具有相似属性的其他结果; 这些包括用于非阻塞数据结构的长期重命名和动态内存管理。
-
76.发明授权Method and apparatus for emulating linked-load/store-conditional synchronization 有权用于模拟链接加载/存储条件同步的方法和装置公开(公告)号：US07870344B2
公开(公告)日：2011-01-11
申请号：US11864649
申请日：2007-09-28
申请人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
发明人： Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
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）。 我们的实施是无障碍的。 因此，在无争议的情况下是高效的，并且依赖于竞争案件中的争用管理机制。 它允许链接的数据结构操作，而不需要其他解决方案的复杂性和限制。 此外，作为我们技术的一些实现的构建块，我们开发了第一个不会严重限制字大小的无负载连接/存储条件的非阻塞软件实现。
-
公开(公告)号：US07805467B2
公开(公告)日：2010-09-28
申请号：US11343678
申请日：2006-01-30
申请人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
发明人： Mark S. Moir , David L. Detlefs , Simon Doherty , Maurice P. Herlihy , Victor M. Luchangco , Paul A. Martin , Guy L. Steele, Jr.
IPC分类号： G06F12/00
CPC分类号： G06F12/0261 , G06F9/46 , G06F9/526
摘要： A methodology has been discovered for transforming garbage collection-dependent algorithms, shared object implementations and/or concurrent software mechanisms into a form that does not presume the existence of an independent, or execution environment provided, garbage collector. Algorithms, shared object implementations and/or mechanisms designed or transformed using techniques described herein provide explicit reclamation of storage using lock-free pointer operations. Transformations can be applied to lock-free algorithms and shared object implementations and preserve lock-freedom of such algorithms and implementations. As a result, existing and future lock-free algorithms and shared object implementations that depend on a garbage-collected execution environment can be exploited in environments that do not provide garbage collection. Furthermore, algorithms and shared object implementations that employ explicit reclamation of storage using lock-free pointer operations such as described herein may be employed in the implementation of a garbage collector itself.
摘要翻译： 已经发现了一种方法，用于将垃圾回收依赖算法，共享对象实现和/或并发软件机制转换为不假定存在独立或执行环境（垃圾收集器）的形式。 使用本文描述的技术设计或变换的算法，共享对象实现和/或机制使用无锁指针操作来提供存储的显式回收。 转换可以应用于无锁算法和共享对象实现，并保持这种算法和实现的锁定自由度。 因此，依赖于垃圾回收执行环境的现有和将来的无锁算法和共享对象实现可以在不提供垃圾回收的环境中被利用。 此外，使用如本文所述的无锁定指针操作的使用显式回收存储的算法和共享对象实现可以用于实现垃圾收集器本身。
-
公开(公告)号：US07788242B2
公开(公告)日：2010-08-31
申请号：US11508762
申请日：2006-08-23
CPC分类号： G06F17/30362 , G06F17/30958
摘要： A method for inserting an object into a concurrent set including obtaining a key associated with the object, traversing the concurrent set using a first thread containing the key, identifying a first insertion point while traversing the concurrent set, where the first insertion point is before a current node and after a predecessor node, obtaining a first lock for the predecessor node after identifying the first insertion point, validating the predecessor node and the current node after obtaining the lock, inserting a new node into the concurrent set after validating, where the new node is associated with the object, and releasing the first lock after inserting the new node.
摘要翻译： 一种用于将对象插入到并发集合中的方法，包括获得与对象相关联的密钥，使用包含密钥的第一线程遍历并发集合，在遍历并发集合的同时识别第一插入点，其中第一插入点在 当前节点，并且在前导节点之后，在识别出第一插入点之后为先前节点获得第一锁定，在获得锁定之后验证前导节点和当前节点，在验证之后将新节点插入并发集合，其中新的 节点与对象相关联，并在插入新节点后释放第一个锁。
-
公开(公告)号：US07620850B2
公开(公告)日：2009-11-17
申请号：US11552884
申请日：2006-10-25
申请人： Yosef Lev , Mark S. Moir
发明人： Yosef Lev , Mark S. Moir
IPC分类号： G06F11/00
CPC分类号： G06F11/362
摘要： Transactional programming promises to substantially simplify the development and maintenance of correct, scalable, and efficient concurrent programs. Designs for supporting transactional programming using transactional memory implemented in hardware, software, and a mixture of the two have emerged recently. However, certain features and capabilities that would be desirable for debugging programs executed using transactional memory are absent from conventional debuggers. Breakpointing is one example of a capability not well supported when conventional debugging technology is applied to transactional memory. We describe techniques by which a debugger may instrument code (or by which a TM library may provide functionality) to direct execution of an atomic block to a code path that facilitates breakpoint handling.
摘要翻译： 事务性规划将大大简化正确，可扩展和高效并发程序的开发和维护。 最近出现了使用在硬件，软件和两者的混合中实现的事务性存储来支持事务性编程的设计。 然而，对于使用事务性存储器执行的调试程序来说，期望的某些功能和功能在常规调试器中不存在。 断点是传统调试技术应用于事务性存储器时不能很好支持的功能的一个例子。 我们描述了一种调试器可以通过调试器来实现代码（或TM库可以提供功能）的技术，以将原子块的执行指导到便于断点处理的代码路径。
-
80.发明授权Conditional synchronization mechanisms allowing multiple store operations to become visible while a flagged memory location is owned and remains unchanged 有权条件同步机制允许多个存储操作在标记的存储器位置被拥有并保持不变时变得可见公开(公告)号：US07480771B2
公开(公告)日：2009-01-20
申请号：US11465376
申请日：2006-08-17
IPC分类号： G06F12/00
CPC分类号： G06F12/0864 , G06F9/3004 , G06F9/30072 , G06F9/30087 , G06F12/0804 , G06F12/0815 , G06F12/0846
摘要： We propose a class of mechanisms to support a new style of synchronization that offers simple and efficient solutions to several existing problems for which existing solutions are complicated, expensive, and/or otherwise inadequate. In general, the proposed mechanisms allow a program to read from a first memory location (called the “flagged” location), and to then continue execution, storing values to zero or more other memory locations such that these stores take effect (i.e., become visible in the memory system) only while the flagged memory location does not change. In some embodiments, the mechanisms further allow the program to determine when the first memory location has changed. We call the proposed mechanisms conditional multi-store synchronization mechanisms.
摘要翻译： 我们提出一类机制来支持新的同步风格，为现有解决方案复杂，昂贵和/或其他不足的现有问题提供简单而有效的解决方案。 通常，所提出的机制允许程序从第一存储器位置（称为“标记的”位置）读取，然后继续执行，将值存储到零个或多个其他存储器位置，使得这些存储器生效（即，变为 只有当标记的存储器位置不改变时，才能在存储器系统中可见） 在一些实施例中，机制还允许程序确定第一存储器位置何时改变。 我们称提出的机制是条件多存储同步机制。
-
-
-
-
-
-
-
-
-
搜索结果
116 条记录 (耗时 0.04 秒)
