是否有可能使用GPU加速（动态）LINQ查询？

Question

我已经搜索了几天，想找到有关使用GPU加速LINQ查询的可靠信息。

到目前为止，我已经“调查”过以下技术：

• Microsoft Accelerator
• Cudafy
• Brahma

简单来说，是否有可能在GPU上进行内存中的对象过滤呢?

假设我们有一个对象列表，我们想要筛选出一些东西:

var result = myList.Where(x => x.SomeProperty == SomeValue);

有关这个问题，您有什么指点吗？

先感谢您！

更新

我会尽量更具体地说明我的目标 :)

目标是使用任何技术，在绝对最快的方式下筛选一个对象列表（范围从约50,000到约2,000,000）。

当筛选完成后，我对数据执行的操作（求和、最小值、最大值等）使用内置LINQ方法来完成，已经足够快，所以这不是问题。

瓶颈“只是”数据筛选。

更新

只想补充一下，我已经测试了大约15个数据库，包括MySQL（检查可能的集群方法/ memcached解决方案）、H2、HSQLDB、VelocityDB（目前正在进一步调查）、SQLite、MongoDB等，但没有一个在过滤数据的速度（当然，No-SQL解决方案不像SQL解决方案那样提供此功能，但您明白我的意思）和/或实际数据的返回方面足够好。

为了概括一下我们需要的：

一个能够在不到100毫秒的时间内对格式为200列、大约250,000行的数据进行排序的数据库。

我目前有一个并行化的LINQ解决方案（在特定机器上），可以仅花费纳秒时间来筛选和处理结果！

因此，我们需要每行子纳秒级别的筛选。

1. 为什么似乎只有内存中的LINQ能够提供这个功能？
2. 这为什么是不可能的？

日志文件中的一些数字：

Total tid för 1164 frågor: 2579

这是瑞典语，翻译为：

Total time for 1164 queries: 2579

在这种情况下，查询是指如下的查询：

WHERE SomeProperty = SomeValue

同时这些查询在 225639 行数据上并行执行。

所以，大约需要 2.5 秒就可以在内存中筛选出 225639 行数据 1164 次。

这意味着每行数据的用时为 9,5185952917007032597107300413827e-9 秒，但是这个时间也包括了数字的实际处理！我们对筛选出的行进行 Count （非空），总计数，Sum，Min，Max，Avg，Median 等 7 项操作。

因此，我们可以说它比我们尝试过的数据库快 7 倍，因为在那些情况下我们不会进行任何聚合操作！

总之，为什么与内存中的 LINQ 筛选相比，数据库在数据筛选方面表现如此差？微软是否真的做得那么好，无法与其竞争？ :)

不过，在内存中进行筛选应该更快，但我不只是想要一种感觉它更快。我想要知道什么更快，如果可能的话，为什么更快。

- Imperatorn

---

我不知道，但是这个想法很好。我期待答案。 - Jodrell

请关注 https://github.com/palladin/LinqOptimizer/tree/gpu - Mauricio Scheffer

Answer 1

由于这是我的图书馆，所以我可以明确回答关于Brahma的问题，但它可能也适用于其他方法。GPU不知道对象。它的内存也大多完全与CPU内存分离。

如果您有一组大量的对象并希望处理它们，您只能将要处理的数据打包到适合您使用的GPU/API的缓冲区中，并将其发送进行处理。

请注意，这将在CPU-GPU内存接口上进行两次往返，因此，如果您在GPU上没有做足够的工作使其值得，那么您将比起一开始就使用CPU（例如上面的示例）更慢。

希望这可以帮到您。

- Ani

---

谢谢！我喜欢你的库，已经用它做了其他事情，而不是我上面问的！实际上，我想做的就是非常快速地过滤对象 :)继续用Brahma做好工作！ - Imperatorn

@Ani，我在哪里可以找到有关Brahma的信息？是否有任何教程和/或示例可用？ - Alex Sanséau

@AlexSanséau 抱歉，我已经多年没有积极开发这个项目了。你可以在这里查看 F# 版本 (https://github.com/gsvgit/Brahma.FSharp)。 - Ani

Answer 2

GPU并不适合所有的通用计算目的，特别是在像这样的面向对象设计中，过滤任意数据集可能并不是一个合适的选择。

GPU计算非常适合在大型数据集上执行相同操作的任务，这就是为什么矩阵操作和变换等任务非常有效。在这种情况下，数据复制的成本可以被GPU的快速计算能力所抵消...

但在这种情况下，您需要将所有数据复制到GPU中才能使其正常工作，并将其重构为GPU能够理解的某种形式，这很可能比直接在软件中执行过滤操作更加昂贵。

相反，我建议使用PLINQ来加速此类查询。如果您的过滤器是线程安全的（对于任何与GPU相关的工作都必须如此...），那么这可能是一种更好的通用查询优化选项，因为它不需要复制数据的内存。 PLINQ会将您的查询重写为：

var result = myList.AsParallel().Where(x => x.SomeProperty == SomeValue);

如果谓词是一个耗时操作，或者集合非常大（且易于分区），与标准的LINQ to Objects相比，这可以显著提高整体性能。

- Reed Copsey

---

谢谢回答！然而，这是我们今天正在使用的方法。它几乎足够了，但很快我们将会有更多的行，嗯...即使是目前我们拥有的16核机器也不再足够了:( - Imperatorn

@Johan 在某个时候，使用数据库和技术，使过滤在查询端加速（如EF），将使这种类型的操作在大型数据集上更快，特别是当过滤器是简单属性检查时...将数据复制到GPU的成本对于这种类型的操作来说是难以承受的。你实际上在做什么？这是什么类型的数据？ - Reed Copsey

这是一个对象列表，它来自一个表（我正在使用Dapper获取数据）。该表有许多列（出于性能原因未进行规范化），但目前行数不是很多（约为250,000）。然而，到目前为止，我尝试过的所有“数据库”都比内存过滤要慢得多。您知道任何极快的“where-optimized”数据获取技术吗？ :) - Imperatorn

@ Johan，即使你在SomeProperty上有索引？ - Jodrell

@Johan 这真的很大程度上取决于你的查询在做什么。对于大型数据集，存储通常是关键...但适当的存储取决于你将如何访问数据以及你对其进行的操作。 - Reed Copsey

Answer 3

GpuLinq

GpuLinq的主要任务是通过LINQ使GPGPU编程民主化。其主要思想是将查询表示为表达式树，在进行各种转换和优化后，将其编译为快速的OpenCL内核代码。此外，我们提供了一个非常易于使用的API，无需深入研究OpenCL API的细节。

https://github.com/nessos/GpuLinq

- user1760527

Answer 4

select *
from table1  -- contains 100k rows
left join table2 -- contains 1M rows
on table1.id1=table2.id2 -- this would run for ~100G times 
                         -- unless they are cached on sql side
where table1.id between 1 and 100000 -- but this optimizes things (depends)

可以转换为。

select id1 from table1 -- 400k bytes if id1 is 32 bit 
-- no need to order

存储在内存中

select id2 from table2 -- 4Mbytes if id2 is 32 bit
-- no need to order

两个数组存储在内存中，并使用像下面这样的 GPU 内核（CUDA，OpenCL）将它们发送到 GPU。

int i=get_global_id(0); // to select an id2, we need a thread id
int selectedID2=id2[i];
summary__=-1;
for(int j=0;j<id1Length;j++)
{
      int selectedID1=id1[j];
      summary__=(selectedID2==selectedID1?j:summary__); // no branching
}
summary[i]=j; // accumulates target indexings of 
"on table1.id1=table2.id2" part.

在主机端，您可以进行以下操作：

 select * from table1 --- query3

并且

 select * from table2 --- query4

然后使用来自GPU的ID列表选择数据。

 // x is table1 ' s data
 myList.AsParallel().ForEach(x=>query3.leftjoindata=query4[summary[index]]);

具备常量内存、全局广播能力和数千个核心的GPU代码执行时间不应该超过50毫秒。

如果使用任何三角函数进行过滤，性能将快速下降。同时，当左联接表的行数使得它的复杂度为O(m*n)时，例如百万对百万的情况会变得更加缓慢。GPU内存带宽在这里非常重要。

编辑：在我的hd7870（1280个核心）和R7-240（320个核心）上，使用“产品表（64k行）”和“类别表（64k行）”（左连接过滤器）进行一次gpu.findIdToJoin(table1,table2,"id1","id2")操作，未经优化的内核花费了48毫秒。

Ado.Net的“nosql”风格linq-join在仅有44k个产品和4k个类别表时需要2000毫秒以上的时间。

编辑-2：

当表的大小增长到每个表都至少有数百个字符的1000个行时，带有字符串搜索条件的左连接在GPU上可以快速达到50到200倍。

- huseyin tugrul buyukisik

Answer 5

针对您的使用情况，简单的答案是不行。

1）即使在原始的 Linq to Object 中也没有解决这种工作负载的方案，更不用说替换数据库了。

2）即使您愿意一次性加载整个数据集（这需要时间），它仍然会慢得多，因为 GPU 具有高吞吐量，但其访问具有高延迟性。因此，如果您正在寻找“非常”快速的解决方案，GPGPU 通常不是答案，因为准备/发送工作负载并获取结果将很慢，并且在您的情况下可能需要分批完成。

- Ronan Thibaudau