公开(公告)号：US20070198979A1

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

申请号：US11475716

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F9/46

CPC分类号： G06F12/0806 ,  G06F9/466 ,  G06F9/52 ,  G06F9/526 ,  G06F12/0815 ,  G06F12/0893

摘要： 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.

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

公开(公告)号：US20070198792A1

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

申请号：US11475262

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F12/14

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.

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

公开(公告)号：US20070198781A1

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

申请号：US11488618

申请日：2006-07-18

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F13/28 ,  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.

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

公开(公告)号：US20070198519A1

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

申请号：US11475814

申请日：2006-06-27

申请人： David Dice ,  Ori Shalev ,  Nir Shavit

发明人： David Dice ,  Ori Shalev ,  Nir Shavit

IPC分类号： G06F17/30

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.

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

公开(公告)号：US20070198978A1

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

申请号：US11475604

申请日：2006-06-27

申请人： David Dice ,  Nir Shavit

发明人： David Dice ,  Nir Shavit

IPC分类号： G06F9/46

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

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

公开(公告)号：US20120136271A1

公开(公告)日：2012-05-31

申请号：US13389092

申请日：2010-08-12

申请人： Nir Shavit

发明人： Nir Shavit

IPC分类号： A61B5/087

CPC分类号： A61B5/087 ,  A61B2505/09

摘要： Spirometer apparatus comprising main inhale-exhale tube having first end, main interior, and second open end, a plurality of smaller tubes intersecting said main-inhale exhale tube at first and second respective locations and having a plurality of smaller interiors respectively, the first location being closer to the first end than is the second location, wherein each of the smaller interiors are in fluid communication with the main interior solely via at least one aperture formed in each of the intersecting tubes at locations facing said second end, the intersecting tubes having first and second external cross-sections, the main tube having first and second internal cross-sections, wherein said first external cross-section is smaller than said first internal cross-section, said second external cross-section is smaller than said second internal cross-section, and wherein said second external cross-section is smaller than said first external cross-section, and a differential pressure sensor sensing the pressure drop.

摘要翻译： 肺活量计装置包括主吸入管，其具有第一端，主内部和第二开口端，多个较小的管在第一和第二相应位置与所述主吸入呼吸管相交，并且分别具有多个较小的内部，第一位置 比第二位置更靠近第一端，其中每个较小的内部仅通过在面对所述第二端的位置处形成在每个相交管中的至少一个孔与主内部流体连通，所述交叉管具有 第一和第二外部横截面，主管具有第一和第二内部横截面，其中所述第一外部横截面小于所述第一内部横截面，所述第二外部横截面小于所述第二内部横截面 并且其中所述第二外部横截面小于所述第一外部横截面，以及差压Se 感测压降的感觉。

公开(公告)号：US20050132374A1

公开(公告)日：2005-06-16

申请号：US10996508

申请日：2004-11-23

申请人： Christine Flood ,  David Detlefs ,  Nir Shavit ,  Xiaolan Zhang ,  Ole Agesen

发明人： Christine Flood ,  David Detlefs ,  Nir Shavit ,  Xiaolan Zhang ,  Ole Agesen

IPC分类号： G06F9/46 ,  G06F12/02 ,  G06F17/30

CPC分类号： G06F12/0276 ,  Y10S707/99953 ,  Y10S707/99957

摘要： A multiprocessor, multi-program, stop-the-world garbage collection program is described. The system initially over partitions the root sources, and then iteratively employs static and dynamic work balancing. Garbage collection threads compete dynamically for the initial partitions. Work stealing double-ended queues, where contention is reduced, are described to provide dynamic load balancing among the threads. Contention is resolved by using atomic instructions. The heap is broken into a young and an old generation where parallel semi-space copying is used to collect the young generation and parallel mark-compacting the old generation. Speed and efficiency of collection is enhanced by use of card tables and linking objects, and overflow conditions are efficiently handled by linking using class pointers. A garbage collection termination employs a global status word.

摘要翻译： 描述了一个多处理器，多程序，停止世界的垃圾收集程序。 系统最初对根源进行分区，然后迭代地采用静态和动态的工作平衡。 垃圾收集线程可以动态竞争初始分区。 被描述为在线程之间提供动态负载平衡的工作窃取双端队列，其中争用减少。 竞争通过使用原子指令来解决。 堆被打破成一个年轻和老一代，平行的半空间复制用于收集年轻一代和平行的标记压实老一代。 通过使用卡表和链接对象来增强收集的速度和效率，并且通过使用类指针进行链接来有效地处理溢出条件。 垃圾收集终端采用全局状态字。

公开(公告)号：US20060123156A1

公开(公告)日：2006-06-08

申请号：US11325150

申请日：2006-01-04

申请人： Mark Moir ,  Daniel Nussbaum ,  Ori Shalev ,  Nir Shavit

发明人： Mark Moir ,  Daniel Nussbaum ,  Ori Shalev ,  Nir Shavit

IPC分类号： G06F13/28

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，以指示该位置可用于由相同或不同的生产者进行将来的转移。 如果没有消费者拿起传输数据，生产者也可以监控传送位置和超时。

公开(公告)号：US5586321A

公开(公告)日：1996-12-17

申请号：US392009

申请日：1995-02-21

申请人： Nir Shavit ,  Asaph Zemach ,  Dan Touitou

发明人： Nir Shavit ,  Asaph Zemach ,  Dan Touitou

IPC分类号： G06F15/173 ,  G06F9/00 ,  G06F13/14

CPC分类号： G06F15/17393

摘要： A diffracting token router for executing a correctness invariant. The diffracting token router is connected to at least one producer of tokens and at least two consumers of tokens. The diffracting token router includes an array of inlet wires, an array of outlet wires, a diffracting prism connected to the array of inlet wires and the array of two outlet wires and a decision decider connected to the diffracting prism and the at least two outlet wires. The diffracting taken router has two operative modes. In its first operative mode, two or more tokens arrive at the diffracting prism in a diffracting collision manner according to the correctness invariant, and are thereafter routed to the array of output wires according to the correctness invariant. In its second operative made, one or more tokens arrive at the diffracting prism in a non-diffracting collision manner according to the correctness invariant, and are thereafter routed to the decision mechanism which routes them to the array of outlet wires according to the correctness invariant.

摘要翻译： 用于执行正确性不变量的衍射令牌路由器。 衍射令牌路由器连接至令牌的至少一个生成者和令牌的至少两个消费者。 衍射令牌路由器包括入口线阵列，出口线阵列，连接到入口线阵列的衍射棱镜和两个出口线的阵列以及连接到衍射棱镜和至少两个出射线的决定决定器 。 衍射路由器具有两种操作模式。 在其第一操作模式中，两个或多个令牌根据正确性不变量以衍射碰撞方式到达衍射棱镜，然后根据正确性不变量被传送到输出线阵列。 在其第二操作中，一个或多个令牌根据正确性不变量以非衍射碰撞方式到达衍射棱镜，然后被路由到根据正确性不变量将它们引导到出线的阵列的判定机构 。

公开(公告)号：US10070803B2

公开(公告)日：2018-09-11

申请号：US13389092

申请日：2010-08-12

申请人： Nir Shavit

发明人： Nir Shavit

IPC分类号： A61B5/08 ,  A61B5/087

CPC分类号： A61B5/087 ,  A61B2505/09

摘要： Spirometer apparatus comprising main inhale-exhale tube having first end, main interior, and second open end, a plurality of smaller tubes intersecting said main-inhale exhale tube at first and second respective locations and having a plurality of smaller interiors respectively, the first location being closer to the first end than is the second location, wherein each of the smaller interiors are in fluid communication with the main interior solely via at least one aperture formed in each of the intersecting tubes at locations facing said second end, the intersecting tubes having first and second external cross-sections, the main tube having first and second internal cross-sections, wherein said first external cross-section is smaller than said first internal cross-section, said second external cross-section is smaller than said second internal cross-section, and wherein said second external cross-section is smaller than said first external cross-section, and a differential pressure sensor sensing the pressure drop.