公开(公告)号：US09846628B2

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

申请号：US12816165

申请日：2010-06-15

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

发明人： 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分类号： G06F11/323 ,  G06F11/3409 ,  G06F11/3476 ,  G06F2201/86

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

公开(公告)号：US20110307905A1

公开(公告)日：2011-12-15

申请号：US12816165

申请日：2010-06-15

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

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

IPC分类号： G06F9/44 ,  G06F3/048

CPC分类号： G06F11/323 ,  G06F11/3409 ,  G06F11/3476 ,  G06F2201/86

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

摘要翻译： 本发明扩展到用于指示与用户可见事件并行操作的方法，系统和计算机程序产品。 事件标记可用于指示抽象的外层执行，以及公开并行处理系统的内部细节，包括提供数据并行性的系统。 事件标记可用于显示各种执行特征，包括用于指示执行程序（例如，查询）的开始和结束的更高级标记。 在执行程序（查询）中，可以使用子级别的标记来显示单独的fork / join操作，以显示其操作。 执行引擎做出的其他决定，例如当元素最初产生时，当查询重叠或嵌套时，当查询被取消时，当查询需要顺序操作时，当需要提前合并或重新分区时也可以 被暴露

公开(公告)号：US08266172B2

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

申请号：US12418136

申请日：2009-04-03

申请人： Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

发明人： Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

IPC分类号： G06F7/00

CPC分类号： G06F17/30445

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

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

公开(公告)号：US20100257191A1

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

申请号：US12418136

申请日：2009-04-03

申请人： Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

发明人： Igor Ostrovsky ,  John Duffy ,  Mike Liddell ,  Edward G. Essey ,  Stephen H. Toub

IPC分类号： G06F17/30

CPC分类号： G06F17/30445

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

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

公开(公告)号：US08707275B2

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

申请号：US12882163

申请日：2010-09-14

申请人： Massimo Mascaro ,  Igor Ostrovsky ,  Emad A. Omara

发明人： Massimo Mascaro ,  Igor Ostrovsky ,  Emad A. Omara

IPC分类号： G06F9/44

CPC分类号： G06F11/3664 ,  G06F8/20 ,  G06F8/443 ,  G06F9/4881 ,  G06F9/5066 ,  G06Q10/06315

摘要： A scheduler receives a job graph which includes a graph of computational vertices that are designed to be executed on multiple distributed computer systems. The scheduler queries a graph manager to determine which computational vertices of the job graph are ready for execution in a local execution environment. The scheduler queries a cluster manager to determine the organizational topology of the distributed computer systems to simulate the determined topology in the local execution environment. The scheduler queries a data manager to determine data storage locations for each of the computational vertices indicated as being ready for execution in the local execution environment. The scheduler also indicates to a vertex spawner that an instance of each computational vertex is to be spawned in the local execution environment based on the organizational topology and indicated data storage locations, and indicates to the local execution environment that the spawned vertices are to be executed.

摘要翻译： 调度器接收作业图，该作业图包括被设计为在多个分布式计算机系统上执行的计算顶点的图形。 调度程序查询图表管理器以确定作业图的哪些计算顶点准备好在本地执行环境中执行。 调度程序查询集群管理器以确定分布式计算机系统的组织拓扑，以模拟本地执行环境中确定的拓扑。 调度器查询数据管理器以确定指示为准备在本地执行环境中执行的每个计算顶点的数据存储位置。 调度器还向顶点指示器根据组织拓扑和指示的数据存储位置，在本地执行环境中产生每个计算顶点的实例，并向本地执行环境指示要执行所产生的顶点 。

公开(公告)号：US08521721B2

公开(公告)日：2013-08-27

申请号：US12882168

申请日：2010-09-14

申请人： Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

发明人： Stephen Harris Toub ,  Igor Ostrovsky ,  Mike Liddell

IPC分类号： G06F7/00 ,  G06F17/30

CPC分类号： G06F17/30445

摘要： Embodiments are directed to implementing custom operators in a query for a parallel query engine and to generating a partitioned representation of a sequence of query operators in a parallel query engine. A computer system receives a portion of partitioned input data at a parallel query engine, where the parallel query engine is configured to process data queries in parallel, and where the queries include a sequence of built-in operators. The computer system incorporates a custom operator into the sequence of built-in operators for a query and accesses the sequence of operators to determine how the partitioned input data is to be processed. The custom operator is accessed in the same manner as the built-in operators. The computer system also processes the sequence of operators including both the built-in operators and at least one custom operator according to the determination indicating how the data is to be processed.

摘要翻译： 实施例涉及在并行查询引擎的查询中实现自定义运算符并且在并行查询引擎中生成查询运算符序列的分区表示。 计算机系统在并行查询引擎处接收分割的输入数据的一部分，其中并行查询引擎被配置为并行处理数据查询，并且查询包括一系列内置运算符。 计算机系统将定制运算符合并到用于查询的内置运算符序列中，并访问运算符序列以确定如何处理分区输入数据。 以与内置运算符相同的方式访问定制运算符。 计算机系统还根据指示如何处理数据的确定来处理包括内置运算符和至少一个定制运算符的运算符序列。

公开(公告)号：US08276154B2

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

申请号：US12642233

申请日：2009-12-18

申请人： Stephen H. Toub ,  Igor Ostrovsky

发明人： Stephen H. Toub ,  Igor Ostrovsky

IPC分类号： G06F9/46

CPC分类号： G06F9/5033 ,  G06F2209/5018

摘要： The present invention extends to methods, systems, and computer program products for partitioning streaming data. Embodiments of the invention can be used to hash partition a stream of data and thus avoids unnecessary memory usage (e.g., associated with buffering). Hash partitioning can be used to split an input sequence (e.g., a data stream) into multiple partitions that can be processed independently. Other embodiments of the invention can be used to hash repartition a plurality of streams of data. Hash repartitioning converts a set of partitions into another set of partitions with the hash partitioned property. Partitioning and repartitioning can be done in a streaming manner at runtime by exchanging values between worker threads responsible for different partitions.

摘要翻译： 本发明扩展到用于划分流数据的方法，系统和计算机程序产品。 本发明的实施例可用于对数据流进行散列分区，从而避免不必要的存储器使用（例如，与缓冲相关联）。 散列分区可用于将输入序列（例如，数据流）拆分成可独立处理的多个分区。 本发明的其他实施例可用于对多个数据流重新分区。 哈希重新分区将一组分区转换为具有哈希分区属性的另一组分区。 在运行时可以通过在负责不同分区的工作线程之间交换值来进行分区和重新分区。

公开(公告)号：US09354932B2

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

申请号：US13165421

申请日：2011-06-21

申请人： Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

发明人： Igor Ostrovsky ,  Joseph E. Hoag ,  Stephen H. Toub ,  Mike Liddell

IPC分类号： G06F9/46 ,  G06F9/50

CPC分类号： G06F12/023 ,  G06F3/0608 ,  G06F3/061 ,  G06F3/0631 ,  G06F3/0673 ,  G06F9/5016 ,  G06F2212/1016 ,  G06F2212/1044

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

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

公开(公告)号：US08806168B2

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

申请号：US13230833

申请日：2011-09-12

申请人： Igor Ostrovsky ,  Stephen H. Toub

发明人： Igor Ostrovsky ,  Stephen H. Toub

IPC分类号： G06F12/02

CPC分类号： G06F12/02 ,  G06F9/544 ,  G06F2209/548

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

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

公开(公告)号：US08707320B2

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

申请号：US12712986

申请日：2010-02-25

申请人： Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

发明人： Michael Liddell ,  Igor Ostrovsky ,  Stephen Toub

IPC分类号： G06F9/46

CPC分类号： G06F9/505

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

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