公开(公告)号：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: 一种方法包括将表达式编译成可配置为创建表示表达式的数据结构的可执行代码。 该表达式包括多个子表达式。 执行代码以创建数据结构。 使用多个并行线程来评估数据结构，从而以并行方式处理表达式。

公开(公告)号：US09354932B2

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

申请号：US13165421

申请日：2011-06-21

Applicant: Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

Inventor： Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

IPC: G06F9/46 ,  G06F9/50

CPC classification number: G06F12/023 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0631 ,  G06F3/0673 ,  G06F9/5016 ,  G06F2212/1016 ,  G06F2212/1044

Abstract: Dynamically allocated thread storage in a computing device is disclosed. The dynamically allocated thread storage is configured to work with a process including two or more threads. Each thread includes a statically allocated thread-local slot configured to store a table. Each table is configured to include a table slot corresponding with a dynamically allocated thread-local value. A dynamically allocated thread-local instance corresponds with the table slot.

Abstract translation: 公开了在计算设备中动态分配的线程存储。 动态分配的线程存储被配置为使用包括两个或更多个线程的进程。 每个线程包括一个静态分配的线程本地插槽，用于存储一个表。 每个表被配置为包括与动态分配的线程本地值相对应的表时隙。 动态分配的线程本地实例对应于表槽。

公开(公告)号：US08806168B2

公开(公告)日：2014-08-12

申请号：US13230833

申请日：2011-09-12

Applicant: Igor Ostrovsky ,  Stephen H. Toub

Inventor： Igor Ostrovsky ,  Stephen H. Toub

IPC: G06F12/02

CPC classification number: G06F12/02 ,  G06F9/544 ,  G06F2209/548

Abstract: A method includes producing values with a producer thread, and providing a queue data structure including a first array of storage locations for storing the values. The first array has a first tail pointer and a first linking pointer. If a number of values stored in the first array is less than a capacity of the first array, an enqueue operation writes a new value at a storage location pointed to by the first tail pointer and advances the first tail pointer. If the number of values stored in the first array is equal to the capacity of the first array, a second array of storage locations is allocated in the queue. The second array has a second tail pointer. The first array is linked to the second array with the first linking pointer. An enqueue operation writes the new value at a storage location pointed to by the second tail pointer and advances the second tail pointer.

Abstract translation: 一种方法包括使用生产者线程生成值，并提供包括用于存储值的存储位置的第一阵列的队列数据结构。 第一个数组有一个第一个尾部指针和一个第一个链接指针。 如果存储在第一阵列中的多个值小于第一阵列的容量，则入队操作将新值写入由第一尾指针指向的存储位置并且前进第一尾指针。 如果存储在第一个阵列中的值的数量等于第一个阵列的容量，则在队列中分配第二个存储位置阵列。 第二个数组有一个第二个尾部指针。 第一个数组用第一个链接指针链接到第二个数组。 排队操作将新值写入由第二个尾部指针指向的存储位置，并推进第二个尾部指针。

公开(公告)号：US08707320B2

公开(公告)日：2014-04-22

申请号：US12712986

申请日：2010-02-25

Applicant: Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

Inventor： Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

IPC: G06F9/46

CPC classification number: G06F9/505

Abstract: Dynamic data partitioning is disclosed for use with a multiple node processing system that consumes items from a data stream of any length and independent of whether the length is undeclared. Dynamic data partitioning takes items from the data stream when a thread is idle and assigns the taken items to an idle thread, and it varies the size of data chunks taken from the stream and assigned to a thread to efficiently distribute work loads among the nodes. In one example, data chunk sizes taken from the beginning of the data stream are relatively smaller than data chunk sizes taken towards the middle or end of the data stream. Dynamic data partitioning employs a growth function where chunks have a size related to single aligned cache lines and efficiently increases the size of the data chunks to occasionally double the amount of data assigned to concurrent threads.

Abstract translation: 公开了与多节点处理系统一起使用的动态数据分区，其从任何长度的数据流消耗项目，并且与长度是否未声明无关。 动态数据分区在线程空闲时从数据流中获取项目，并将所获取的项目分配给空闲线程，并且将从流中分配给分配给线程的数据块的大小变化，从而有效地在节点之间分配工作负载。 在一个示例中，从数据流的开头获取的数据块大小相对于数据流的中间或结尾所采取的数据块大小相对较小。 动态数据分区使用增长函数，其中块与单个对齐的高速缓存行相关联，并有效地增加数据块的大小，以偶尔将分配给并发线程的数据量加倍。

公开(公告)号：US08631279B2

公开(公告)日：2014-01-14

申请号：US13155263

申请日：2011-06-07

Applicant: Huseyin Serkan Yildiz ,  Massimo Mascaro ,  Joseph E. Hoag ,  Igor Ostrovsky

Inventor： Huseyin Serkan Yildiz ,  Massimo Mascaro ,  Joseph E. Hoag ,  Igor Ostrovsky

IPC: G06F11/07

CPC classification number: G06F11/0784

Abstract: The present invention extends to methods, systems, and computer program products for propagating unhandled exceptions in distributed execution environments, such as clusters. A job (e.g., a query) can include a series of computation steps that are executed on multiple compute nodes each processing parts of a distributed data set. Unhandled exceptions can be caught while computations are running on data partitions of different compute nodes. Unhandled exception objects can be stored in a serialized format in a compute node's local storage (or an alternate central location) along with auxiliary details such as the data partition being processed at the time. Stored serialized exception objects for a job can be harvested and aggregated in a single container object. The single container object can be passed back to the client.

Abstract translation: 本发明扩展到方法，系统和计算机程序产品，用于在分布式执行环境（如群集）中传播未处理的异常。 作业（例如，查询）可以包括在多个计算节点上执行的一系列计算步骤，每个处理分布式数据集的各个部分。 在不同计算节点的数据分区上运行计算时可以捕获未处理的异常。 未处理的异常对象可以以计算节点的本地存储（或备用中心位置）中的序列化格式以及当时正在处理的数据分区等辅助细节存储。 存储作业的序列化异常对象可以在单个容器对象中进行收集和聚合。 单个容器对象可以传回客户端。

公开(公告)号：US08290917B2

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

申请号：US12131761

申请日：2008-06-02

Applicant: Igor Ostrovsky ,  John Duffy

Inventor： Igor Ostrovsky ,  John Duffy

IPC: G06F17/30

CPC classification number: G06F17/30486

Abstract: A query that identifies an input data source is received. The input data source is partitioned into a plurality of partitions. Each of the partitions includes a set of data elements with an associated set of indices for indicating an ordering of the data elements. A query type for a query operator in the received query is identified. It is determined whether a reordering of data elements will be performed based on the identified query type. The data elements in at least one of the partitions are reordered when it is determined based on the identified query type that reordering will be performed.

Abstract translation: 接收到识别输入数据源的查询。 输入数据源被分割成多个分区。 每个分区包括一组具有指示数据元素的排序的相关索引组的数据元素。 识别接收到的查询中的查询运算符的查询类型。 确定是否将基于所识别的查询类型执行数据元素的重新排序。 当基于识别的查询类型确定将要执行重新排序时，至少一个分区中的数据元素被重新排序。

公开(公告)号：US08266172B2

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

申请号：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: G06F7/00

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