公开(公告)号：US08229918B2

公开(公告)日：2012-07-24

申请号：US13048024

申请日：2011-03-15

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCle or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

公开(公告)号：US20080189252A1

公开(公告)日：2008-08-07

申请号：US11895998

申请日：2007-08-27

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCIe or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

摘要翻译： 本发明的实施例提供了一种辅助主机数据库系统处理其查询的硬件加速器。 硬件加速器包括能够以机器码数据库指令的形式接收数据库查询/操作任务的专用处理元件，无需软件执行硬件，并将查询/运算结果返回主机系统。 例如，表和列描述符嵌入在机器码数据库指令中。 为了便于安装，硬件加速器采用标准互连，例如PCIe或HT互连。 处理元件实现了一种新颖的数据流设计和Inter Macro-Op Communication（IMC）数据结构来执行机器码数据库指令。 硬件加速器还可以包括相对大的存储器，以增强所请求的查询/操作任务的硬件执行。 硬件加速器使用硬件友好的存储器寻址，这允许仅仅基于行标识符从全局数据库虚拟地址算术推导物理地址。 硬件加速器通过保持大多数中间结果以流水线和并行方式流过IMC来最小化存储器读/写。 此外，硬件加速器可以采用任务流水线和预取流水线来增强其性能。

公开(公告)号：US07908259B2

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

申请号：US11895998

申请日：2007-08-27

申请人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

发明人： Jeremy Branscome ,  Michael Corwin ,  Liuxi Yang ,  Joseph I. Chamdani

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

CPC分类号： G06F17/30442

摘要： Embodiments of the present invention provide a hardware accelerator that assists a host database system in processing its queries. The hardware accelerator comprises special purpose processing elements that are capable of receiving database query/operation tasks in the form of machine code database instructions, execute them in hardware without software, and return the query/operation result back to the host system. For example, table and column descriptors are embedded in the machine code database instructions. For ease of installation, the hardware accelerators employ a standard interconnect, such as a PCIe or HT interconnect. The processing elements implement a novel dataflow design and Inter Macro-Op Communication (IMC) data structures to execute the machine code database instructions. The hardware accelerator may also comprise a relatively large memory to enhance the hardware execution of the query/operation tasks requested. The hardware accelerator utilizes hardware-friendly memory addressing, which allows for arithmetic derivation of a physical address from a global database virtual address simply based on a row identifier. The hardware accelerator minimizes memory reads/writes by keeping most intermediate results flowing through IMCs in pipelined and parallel fashion. Furthermore, the hardware accelerator may employ task pipelining and pre-fetch pipelining to enhance its performance.

摘要翻译： 本发明的实施例提供了一种辅助主机数据库系统处理其查询的硬件加速器。 硬件加速器包括能够以机器码数据库指令的形式接收数据库查询/操作任务的专用处理元件，无需软件执行硬件，并将查询/运算结果返回主机系统。 例如，表和列描述符嵌入在机器码数据库指令中。 为了便于安装，硬件加速器采用标准互连，例如PCIe或HT互连。 处理元件实现了一种新颖的数据流设计和Inter Macro-Op Communication（IMC）数据结构来执行机器码数据库指令。 硬件加速器还可以包括相对大的存储器，以增强所请求的查询/操作任务的硬件执行。 硬件加速器使用硬件友好的存储器寻址，这允许仅仅基于行标识符从全局数据库虚拟地址算术推导物理地址。 硬件加速器通过保持大多数中间结果以流水线和并行方式流过IMC来最小化存储器读/写。 此外，硬件加速器可以采用任务流水线和预取流水线来增强其性能。

公开(公告)号：US20100082895A1

公开(公告)日：2010-04-01

申请号：US12567624

申请日：2009-09-25

申请人： Jeremy Branscome ,  Michael Corwin

发明人： Jeremy Branscome ,  Michael Corwin

IPC分类号： G06F12/00

CPC分类号： G11C15/00

摘要： A multi-level content addressable memory (CAM) architecture compresses out much of the redundancy encountered in the search space of a single CAM, particularly for flow-based lookups in a network. Destination and source address may be associated with internal equivalence classes independently in one level of the multi-level CAM architecture, while flow-specific properties linking arbitrary classes of the destination and source addresses may be applied in a later level of the multi-level CAM.

摘要翻译： 多级内容可寻址存储器（CAM）架构压缩了单个CAM的搜索空间中遇到的冗余，特别是对于网络中的基于流的查找。 目的地址和源地址可以在多级CAM架构的一个级别中独立地与内部等价类相关联，而链接目的地址和源地址的任意类别的流特定属性可以应用于多级CAM的后一级 。

公开(公告)号：US20140089632A1

公开(公告)日：2014-03-27

申请号：US13626799

申请日：2012-09-25

申请人： Jeremy Branscome

发明人： Jeremy Branscome

IPC分类号： G06F12/06

CPC分类号： G06F12/0607 ,  G06F7/535 ,  G06F2207/5355 ,  G06F2207/5356

摘要： Divisions by numbers that are not divisible by two (2) can be performed in a computing system based on a summation that estimates and/or approximates the reciprocal of the dividing number or denominator value. By way of example, dividing by three (3) can be calculated based on a summation that approximates or estimates one third (⅓) represented as the sum of a selected group of the inverses of the powers of two (2) in a pattern, namely the sum of: ¼, 1/16, 1/64, 1/256, . . . ). Applications of the division techniques are virtually unlimited and include memory mapping of global memory addresses to memory channel addresses by dividing a global memory address into the number of memory channels, allowing memory mapping to be performed in an efficient manner even for large memory spaces using a number of memory channels that are not divisible by two, including prime numbers.

摘要翻译： 不能被二（2）除尽的数字的划分可以在计算系统中基于估计和/或近似分割数或分母值的倒数的求和来执行。 作为示例，可以基于近似或估计表示为模式中两（2）的幂的所选择的组的和的三分之一（1/3）的总和来计算除以三（3） 即：¼，1/16，1/64，1/256， 。 。 ）。 划分技术的应用实际上是无限制的，并且包括将全局存储器地址到存储器通道地址的存储器映射，通过将全局存储器地址划分为存储器通道的数量，允许以有效的方式执行存储器映射，即使对于使用 不能被2整除的内存通道数，包括素数。

公开(公告)号：US09213639B2

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

申请号：US13626799

申请日：2012-09-25

申请人： Jeremy Branscome

发明人： Jeremy Branscome

IPC分类号： G06F12/06 ,  G06F7/535

CPC分类号： G06F12/0607 ,  G06F7/535 ,  G06F2207/5355 ,  G06F2207/5356

摘要： Divisions by numbers that are not divisible by two (2) can be performed in a computing system based on a summation that estimates and/or approximates the reciprocal of the dividing number or denominator value. By way of example, dividing by three (3) can be calculated based on a summation that approximates or estimates one third (⅓) represented as the sum of a selected group of the inverses of the powers of two (2) in a pattern, namely the sum of: ¼, 1/16, 1/64, 1/256, . . . ). Applications of the division techniques are virtually unlimited and include memory mapping of global memory addresses to memory channel addresses by dividing a global memory address into the number of memory channels, allowing memory mapping to be performed in an efficient manner even for large memory spaces using a number of memory channels that are not divisible by two, including prime numbers.

摘要翻译： 不能被二（2）除尽的数字的划分可以在计算系统中基于估计和/或近似分割数或分母值的倒数的求和来执行。 作为示例，可以基于近似或估计表示为模式中两（2）的幂的所选择的组的和的三分之一（1/3）的总和来计算除以三（3） 即：¼，1/16，1/64，1/256， 。 。 ）。 划分技术的应用实际上是无限制的，并且包括将全局存储器地址到存储器通道地址的存储器映射，通过将全局存储器地址划分为存储器通道的数量，允许以有效的方式执行存储器映射，即使对于使用 不能被2整除的内存通道数，包括素数。

公开(公告)号：US07606968B2

公开(公告)日：2009-10-20

申请号：US11430389

申请日：2006-05-08

申请人： Jeremy Branscome ,  Michael Corwin

发明人： Jeremy Branscome ,  Michael Corwin

IPC分类号： G06F12/00

CPC分类号： G11C15/00

摘要： A multi-level content addressable memory (CAM) architecture compresses out much of the redundancy encountered in the search space of a single CAM, particularly for flow-based lookups in a network. Destination and source address may be associated with internal equivalence classes independently in one level of the multi-level CAM architecture, while flow-specific properties linking arbitrary classes of the destination and source addresses may be applied in a later level of the multi-level CAM.

摘要翻译： 多级内容可寻址存储器（CAM）架构压缩了单个CAM的搜索空间中遇到的冗余，特别是对于网络中的基于流的查找。 目的地址和源地址可以在多级CAM架构的一个级别中独立地与内部等价类相关联，而链接目的地址和源地址的任意类别的流特定属性可以应用于多级CAM的后一级 。

公开(公告)号：US20070260814A1

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

申请号：US11430389

申请日：2006-05-08

申请人： Jeremy Branscome ,  Michael Corwin

发明人： Jeremy Branscome ,  Michael Corwin

IPC分类号： G06F12/00

CPC分类号： G11C15/00

摘要： A multi-level content addressable memory (CAM) architecture compresses out much of the redundancy encountered in the search space of a single CAM, particularly for flow-based lookups in a network. Destination and source address may be associated with internal equivalence classes independently in one level of the multi-level CAM architecture, while flow-specific properties linking arbitrary classes of the destination and source addresses may be applied in a later level of the multi-level CAM.

摘要翻译： 多级内容可寻址存储器（CAM）架构压缩了单个CAM的搜索空间中遇到的冗余，特别是对于网络中的基于流的查找。 目的地址和源地址可以在多级CAM架构的一个级别中独立地与内部等价类相关联，而链接目的地址和源地址的任意类别的流特定属性可以应用于多级CAM的后一级 。