Можно ли ускорить (динамические) запросы LINQ с помощью графического процессора?

Question

Я несколько дней искал надежную информацию о возможности ускорения запросов LINQ с помощью графического процессора.

Технологии, которые я "исследовал" до сих пор:

• Microsoft Accelerator
• Cudafy
• Брахма

Короче говоря, возможно ли вообще выполнять фильтрацию объектов в памяти GPU?

Допустим, у нас есть список некоторых объектов, и мы хотим отфильтровать что-то вроде:

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

Есть какие-нибудь указатели на это?

Заранее спасибо!

UPDATE

Я попытаюсь быть более точным в отношении того, чего я пытаюсь достичь:)

Цель состоит в том, чтобы использовать любую технологию, которая способна фильтровать список объектов (от ~ 50 000 до ~ 2 000 000) абсолютно быстрым способом.

Операции, которые я выполняю с данными, когда фильтрация выполнена (сумма, мин, макс и т. Д.) Выполняются с использованием встроенных LINQ-методов и уже достаточно быстры для нашего приложения, так что это не проблема.

Узким местом является "просто" фильтрация данных.

UPDATE

Просто хотел добавить, что я протестировал около 15 баз данных, включая MySQL (проверка возможного кластерного подхода / решение memcached), H2, HSQLDB, VelocityDB (в настоящее время ведутся дальнейшие исследования), SQLite, MongoDB и т. Д., И NONE достаточно хорош, когда он приходит к скорости фильтрации данных (конечно, решения NO-sql не предлагают это как SQL, но вы поняли идею) и / или возврат фактических данных.

Просто подведем итог, что мне / нам нужно:

База данных, которая может сортировать данные в формате 200 столбцов и около 250 000 строк менее чем за 100 мс.

В настоящее время у меня есть решение с параллельным LINQ, которое способно (на определенной машине) тратить только nano -секунд на каждую строку при фильтрации AND на обработку результата!

Итак, нам нужна суб- nano -секундная фильтрация для каждой строки.

1. Почему кажется, что только LINQ в памяти может обеспечить это?
2. Почему это было бы невозможно?

Некоторые цифры из лог-файла:

Total tid för 1164 frågor: 2579

Это шведский и переводится:

Total time for 1164 queries: 2579

Где запросы в этом случае являются запросами вроде:

WHERE SomeProperty = SomeValue

И все эти запросы выполняются параллельно в 225639 строках.

Итак, 225639 строк фильтруются в памяти 1164 раза за 2,5 секунды.

Это 9,5185952917007032597107300413827e-9 секунд / строка, НО , что также включает фактическую обработку чисел! Мы делаем Count (не ноль), Total Count, Sum, Min, Max, Avg, Median. Итак, у нас есть 7 операций над этими отфильтрованными строками.

Таким образом, мы можем сказать, что на самом деле * в 1079 * 7 раз быстрее , чем в тех базах данных, которые мы пробовали, поскольку мы НЕ делаем агрегацию в таких случаях!

Итак, в заключение, почему базы данных так плохо фильтруют данные по сравнению с фильтрацией в памяти LINQ? Действительно ли Microsoft проделала такую ​​хорошую работу, что с ней невозможно конкурировать? :)

Хотя имеет смысл, что фильтрация в памяти должна быть быстрее, но я не хочу ощущать , что она быстрее. Я хочу, чтобы знал , что быстрее, и если это возможно , почему .

Answer 1

Я отвечу однозначно о Брахме, поскольку это моя библиотека, но, вероятно, это относится и к другим подходам. GPU не знает объектов. Его память также в основном полностью отделена от памяти процессора.

Если у вас есть БОЛЬШОЙ набор объектов и вы хотите работать с ними, вы можете только упаковать данные, с которыми вы хотите работать, в буфер, подходящий для используемого вами графического процессора / API, и отправить их для обработки. ,

Обратите внимание, что при этом будет выполнено два приема по интерфейсу памяти CPU-GPU, поэтому, если вы не выполняете достаточно работы на GPU, чтобы сделать ее полезной, вы будете работать медленнее, чем если бы вы просто использовали CPU в первое место (как образец выше).

Надеюсь, это поможет.

Answer 2

Графический процессор на самом деле не предназначен для всех вычислительных целей общего назначения, особенно с такими объектно-ориентированными проектами, и фильтрация произвольного набора данных, подобного этому, на самом деле не будет подходящей вещью.

Вычисления на GPU отлично подходят для тех случаев, когда вы выполняете ту же операцию с большим набором данных, поэтому такие вещи, как операции с матрицами и преобразования, могут быть очень хорошими. Там копирование данных может быть перевешено невероятно быстрыми вычислительными возможностями на GPU ....

В этом случае вам придется скопировать все данные в графический процессор, чтобы выполнить эту работу, и реструктурировать их в какую-то форму, понятную графическому процессору, что, вероятно, будет стоить дороже, чем просто выполнить фильтрацию в программном обеспечении в первое место.

Вместо этого я бы порекомендовал использовать PLINQ для ускорения запросов такого рода. При условии, что ваш фильтр является поточно-ориентированным (что должно быть для любой работы, связанной с GPU ...), это, вероятно, лучший вариант для оптимизации запросов общего назначения, поскольку он не потребует копирования ваших данных в память. PLINQ будет работать, переписав ваш запрос как:

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

Если предикат является дорогостоящей операцией или коллекция очень большая (и легко разбиваемая), это может значительно улучшить общую производительность по сравнению со стандартным LINQ to Objects.

Answer 3

GpuLinq

Основная задача GpuLinq - демократизация программирования GPGPU через LINQ.Основная идея заключается в том, что мы представляем запрос в виде дерева выражений, а после различных преобразований-оптимизаций мы компилируем его в быстрый код ядра OpenCL.Кроме того, мы предоставляем очень простой в использовании API, не требуя при этом дополнительной информации об API OpenCL.

https://github.com/nessos/GpuLinq

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), как показано ниже

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 для выбора данных

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

Код графического процессора не должен быть медленнее 50 мс для графического процессора с постоянной памятью, возможностью глобальной широковещательной передачи и несколькими тысячами ядер.

Если для фильтрации используется какая-либо тригонометрическая функция, производительность будет быстро падать. Также, когда количество строк в левой объединенной таблице усложняет задачу O (m * n), миллионы против миллионов будут намного медленнее. Здесь важна пропускная способность памяти графического процессора.

Edit: Одна операция gpu.findIdToJoin (table1, table2, "id1", "id2") на моих hd7870 (1280 ядер) и R7-240 (320 ядер) с "таблицей продуктов (строки 64k)" и таблицей категорий "( 64 тыс. Строк) "(фильтр левого соединения) занял 48 миллисекунд с неоптимизированным ядром.

Linq-join в стиле «nosql» от Ado.Net занял более 2000 мс, имея только 44 000 продуктов и таблицу категорий 4 000.

Edit-2:

При левом соединении с условием поиска строки в gpu скорость возрастает в 50–200 раз, когда таблицы растут до 1000 строк, каждая из которых содержит не менее сотен символов.

Answer 5

Простой ответ для вашего варианта использования - нет.

1) Нет решения для такой рабочей нагрузки даже в raw linq для объекта, а тем более в том, что заменит вашу базу данных.

2) Даже если у вас все в порядке с загрузкой всего набора данных одновременно (это занимает много времени), это все равно будет намного медленнее, поскольку у GPU высокая пропускная способность, но у них высокий уровень задержки, так что если вы смотрите " очень «быстрые решения» GPGPU часто не является ответом, так как просто подготовка / отправка рабочей нагрузки и получение результатов будут медленными, и в вашем случае, вероятно, придется делать это также частями.