公开(公告)号：US20100312801A1

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

申请号：US12479242

申请日：2009-06-05

Applicant: Igor Ostrovsky ,  John Duffy ,  Mike Liddell

Inventor： Igor Ostrovsky ,  John Duffy ,  Mike Liddell

IPC: G06F9/30 ,  G06F17/30

CPC classification number: G06F17/30516 ,  G06F17/30224

Abstract: A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, with each order key associated with one of the input data elements, includes processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements. The plurality of sets of output data elements is stored in a plurality of buffers, with each buffer associated with one of the worker units. An ordered output data stream is output while the input data stream is being processed by outputting selected output data elements from the buffers in an order that is based on the order keys.

Abstract translation: 一种并行处理有序输入数据流的方法，包括多个输入数据元素和相应的多个顺序密钥，用于指示输入数据元素的排序，其中每个订单密钥与输入数据元素之一相关联，包括处理 所述输入数据流与多个工作单元并行地进行，从而生成多组输出数据元素。 多组输出数据元素被存储在多个缓冲器中，每个缓冲器与其中一个工作单元相关联。 通过以基于订单密钥的顺序从缓冲器输出所选择的输出数据元素，输出数据流被处理时输出有序的输出数据流。

公开(公告)号：US20100257191A1

公开(公告)日：2010-10-07

申请号：US12418136

申请日：2009-04-03

Applicant: Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

Inventor： Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

IPC: G06F17/30

CPC classification number: G06F17/30445

Abstract: A method of analyzing a data parallel query includes receiving a user-specified data parallel query that includes a plurality of query operators. An operator type for each of the query operators is identified based on a type of parallel input data structure the operator operates on and a type of parallel output data structure the operator outputs. It is determined whether the query is a prohibited query based on the identified operator types.

Abstract translation: 分析数据并行查询的方法包括接收包括多个查询运算符的用户指定的数据并行查询。 基于操作员操作的并行输入数据结构的类型和操作员输出的并行输出数据结构的类型来识别每个查询运算符的运算符类型。 基于所识别的运算符类型来确定查询是否是禁止查询。

公开(公告)号：US20090300766A1

公开(公告)日：2009-12-03

申请号：US12131123

申请日：2008-06-02

Applicant: Stephen Toub ,  Joe Duffy ,  Samer El Baghdady ,  Emad Ali ,  Igor Ostrovsky

Inventor： Stephen Toub ,  Joe Duffy ,  Samer El Baghdady ,  Emad Ali ,  Igor Ostrovsky

IPC: G06F21/00

CPC classification number: G06F21/604 ,  G06F9/526 ,  G06F21/6218

Abstract: A membership interface provides procedure headings to add and remove elements of a data collection, without specifying the organizational structure of the data collection. A membership implementation associated with the membership interface provides thread-safe operations to implement the interface procedures. A blocking-bounding wrapper on the membership implementation provides blocking and bounding support separately from the thread-safety mechanism.

Abstract translation: 会员界面提供了用于添加和删除数据集合元素的过程标题，而不指定数据集合的组织结构。 与成员接口关联的成员资格实现提供线程安全操作来实现接口过程。 成员身份实现中的阻塞边界包装器与线程安全机制分开提供了阻塞和边界支持。

公开(公告)号：US09846628B2

公开(公告)日：2017-12-19

申请号：US12816165

申请日：2010-06-15

Applicant: Edward G. Essey ,  Igor Ostrovsky ,  Pooja Nagpal ,  Huseyin S. Yildiz ,  Hazim Shafi ,  William T. Colburn

Inventor： Edward G. Essey ,  Igor Ostrovsky ,  Pooja Nagpal ,  Huseyin S. Yildiz ,  Hazim Shafi ,  William T. Colburn

IPC: G06F9/44 ,  G06F3/048 ,  G06F11/32 ,  G06F11/34

CPC classification number: G06F11/323 ,  G06F11/3409 ,  G06F11/3476 ,  G06F2201/86

Abstract: The present invention extends to methods, systems, and computer program products for indicating parallel operations with user-visible events. Event markers can be used to indicate an abstracted outer layer of execution as well as expose internal specifics of parallel processing systems, including systems that provide data parallelism. Event markers can be used to show a variety of execution characteristics including higher-level markers to indicate the beginning and end of an execution program (e.g., a query). Inside the execution program (query) individual fork/join operations can be indicated with sub-levels of markers to expose their operations. Additional decisions made by an execution engine, such as, for example, when elements initially yield, when queries overlap or nest, when the query is cancelled, when the query bails to sequential operation, when premature merging or re-partitioning are needed can also be exposed.

公开(公告)号：US08290930B2

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

申请号：US12131765

申请日：2008-06-02

Applicant: Igor Ostrovsky ,  John Duffy

Inventor： Igor Ostrovsky ,  John Duffy

IPC: G06F17/30

CPC classification number: G06F17/30471

Abstract: A method includes receiving a query that identifies an input data source. A query category for a query operator in the received query is identified. A data source category for the input data source is also identified. A results object is generated based on the identified query category and the identified data source category. The results object supports at least one of random access and sequential access to results produced by the query operator.

Abstract translation: 一种方法包括接收识别输入数据源的查询。 识别接收到的查询中查询运算符的查询类别。 还识别输入数据源的数据源类别。 基于识别的查询类别和识别的数据源类别生成结果对象。 结果对象支持随机访问和对查询运算符生成的结果的顺序访问中的至少一个。

公开(公告)号：US20110185358A1

公开(公告)日：2011-07-28

申请号：US12695049

申请日：2010-01-27

Applicant: Igor Ostrovsky ,  John J. Duffy ,  Stephen Harris Toub

Inventor： Igor Ostrovsky ,  John J. Duffy ,  Stephen Harris Toub

IPC: G06F9/46

CPC classification number: G06F9/4881 ,  G06F2209/483

Abstract: Partitioning query execution work of a sequence including a plurality of elements. A method includes a worker core requesting work from a work queue. In response, the worker core receives a task from the work queue. The task is a replicable sequence-processing task including two distinct steps: scheduling a copy of the task on the scheduler queue and processing a sequence. The worker core processes the task by: creating a replica of the task and placing the replica of the task on the work queue, and beginning processing the sequence. The acts are repeated for one or more additional worker cores, where receiving a task from the work queue is performed by receiving one or more replicas of tasks placed on the task queue by earlier performances of creating a replica of the task and placing the replica of the task on the work queue by a different worker core.

Abstract translation: 分割包含多个元素的序列的查询执行工作。 一种方法包括从工作队列请求工作的工作者核心。 作为响应，工作核心从工作队列接收任务。 该任务是可重复的序列处理任务，其包括两个不同的步骤：在调度器队列上调度任务的副本并处理序列。 工作核心通过以下方式来处理任务：创建任务的副本并将任务的副本放在工作队列上，并开始处理序列。 对于一个或多个额外的工作核心重复执行动作，其中从工作队列接收任务通过接收一个或多个放置在任务队列上的任务的副本来执行，以通过较早的创建该任务副本的性能并将 工作队列中的任务由不同的工作人员核心。

公开(公告)号：US20110125805A1

公开(公告)日：2011-05-26

申请号：US12625379

申请日：2009-11-24

Applicant: Igor Ostrovsky

Inventor： Igor Ostrovsky

IPC: G06F17/30

CPC classification number: G06F9/5038 ,  G06F9/5066

Abstract: A concurrent grouping operation for execution on a multiple core processor is provided. The grouping operation is provided with a sequence or set of elements. In one phase, each worker receives a partition of a sequence of elements to be grouped. The elements of each partition are arranged into a data structure, which includes one or more keys where each key corresponds to a value list of one or more of the received elements associated with that key. In another phase, the data structures created by each worker are merged so that the keys and corresponding elements for the entire sequence of elements exist in one data structure. Recursive merging can be completed in a constant time, which is not proportional to the length of the sequence.

Abstract translation: 提供了用于在多核处理器上执行的并发分组操作。 分组操作具有序列或一组元素。 在一个阶段，每个工作人员接收要分组的元素序列的分区。 每个分区的元素被布置成数据结构，其包括一个或多个键，其中每个键对应于与该键相关联的一个或多个接收到的元素的值列表。 在另一个阶段，由每个工作者创建的数据结构被合并，使得整个元素序列的键和对应的元素存在于一个数据结构中。 递归合并可以在恒定时间内完成，这与序列的长度不成比例。

公开(公告)号：US20100250564A1

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

申请号：US12413780

申请日：2009-03-30

Applicant: Amit Agarwal ,  Igor Ostrovsky ,  John Duffy ,  Vivan Sewelson

Inventor： Amit Agarwal ,  Igor Ostrovsky ,  John Duffy ,  Vivan Sewelson

IPC: G06F17/30

CPC classification number: G06F8/41 ,  G06F8/30 ,  G06F16/24524 ,  G06F16/24532

Abstract: A method of translating a comprehension into executable code for execution on a SIMD (Single Instruction, Multiple Data stream) execution unit, includes receiving a user specified comprehension. The comprehension is compiled into a first set of executable code. An intermediate representation is generated based on the first set of executable code. The intermediate representation is translated into a second set of executable code that is configured to be executed by a SIMD execution unit.

Abstract translation: 将理解转换成可执行代码以在SIMD（单指令，多数据流）执行单元上执行的方法包括接收用户指定的理解。 理解被编译成第一组可执行代码。 基于第一组可执行代码生成中间表示。 中间表示被转换成被配置为由SIMD执行单元执行的第二组可执行代码。

公开(公告)号：US20100077384A1

公开(公告)日：2010-03-25

申请号：US12236210

申请日：2008-09-23

Applicant: Igor Ostrovsky ,  Stephen Toub ,  John Duffy ,  Joseph Hellerstein

Inventor： Igor Ostrovsky ,  Stephen Toub ,  John Duffy ,  Joseph Hellerstein

IPC: G06F9/44

CPC classification number: G06F8/456

Abstract: A method includes compiling an expression into executable code that is configured to create a data structure that represents the expression. The expression includes a plurality of sub-expressions. The code is executed to create the data structure. The data structure is evaluated using a plurality of concurrent threads, thereby processing the expression in a parallel manner.

Abstract translation: 一种方法包括将表达式编译成可配置为创建表示表达式的数据结构的可执行代码。 该表达式包括多个子表达式。 执行代码以创建数据结构。 使用多个并行线程来评估数据结构，从而以并行方式处理表达式。

公开(公告)号：US08606791B2

公开(公告)日：2013-12-10

申请号：US13163260

申请日：2011-06-17

Applicant: Igor Ostrovsky

Inventor： Igor Ostrovsky

IPC: G06F17/30

CPC classification number: G06F17/30949 ,  G06F17/30348

Abstract: A method of resizing a concurrently accessed hash table is disclosed. The method includes acquiring the locks in the hash table. The hash table, in a first state, is dynamically reconfigured in size into a second state. Additionally, the amount of locks is dynamically adjusted based on comparing the size of the hash table in the second state to the size of the hash table in the second state.

Abstract translation: 公开了一种调整并发访问的散列表的大小的方法。 该方法包括获取哈希表中的锁。 处于第一状态的哈希表在大小上被动态地重新配置成第二状态。 此外，基于将第二状态中的散列表的大小与第二状态中的散列表的大小进行比较，动态地调整锁的量。