strfind on gpu

Hi there, When I try to use strfind on data which is on the gpu it gives me an error. It seems strfind cannot work on data which is on the gpu. Is there a work around?.

[Daniel Shub]

Can you post a simple example of what you are trying to do. Specifically the code to create the arrays and how you are calling strfind on the GPU.

[Mate 2u]

A is a very large string!

tic;

n=8;

for i =1:10000000

ZZ= strfind(A,A(i:i+n-1));

end

toc;

So when I put A on the gpu it gives an error

[Daniel Shub]

How do you "put" A on the GPU?

[Mate 2u]

Hi Daniel,

I have raw prices going down:

A = diff(prices);

A=rot90(A);

[Jan]

@Mate 2u, "string" means a [1 x N] CHAR vector. It is hard to give a meaningful advice, if the problem description is confusing.

I suggest to post the input, the wanted output, the current solution and an the required speedup.

[Daniel Shub]

@Jan the STRFIND function also "works" for numeric inputs, although with the obvious problems associated with floating point comparisons.

[Mate 2u]

Hi Jan, the input is a 1x10,000,000 matrix. Inputs are something like... '0 -9.99999999999890e-05 -9.99999999999890e-05 -9.99999999999890e-05 -0.000200000000000089 -0.000199999999999978'

(6 element sample above).

n=6;

for i =1:1,000,000

ZZ= strfind(A,A(i:i+n-1));

end

want to speed this up. Output is irrelevant as this part of the code is the most time consuming.

Answer 1

[Daniel Shub]

The STRFIND function is fast to find the occurrences of a sequence. The problem is that you are calling it for all possible sequences, even though I think you are only interested in using it on sequences that repeat. It is easy and quick to find repeated sequences:

First create some data that I can run quickly on my laptop

M = 1e6; 
N = 6;
k = 100;
x = randi(k, 1, M);

 First you need to reshape the data to get every N element sequence

y = zeros(M-N, N);
for ii = 1:(M-N)
  y(ii, :) = x((0:(N-1))+ii);
end

Then find all the unique N element sequences.

[a, b, c] = unique(y, 'rows');

Some of these sequences will occur only once and we want to remove these

temp = c;
temp(b) = [];
a = a(unique(temp));

then instead of looping over every possible sequence you can do

for ii =1:size(a, 1)
  strfind(x, a(ii, :));
end

I am not even sure this last step is needed since the information may already be available in "c".

I have no idea if this is faster.

Answer 2

[Jill Reese]

gpuArray currently only supports full, numeric types, so you cannot store a string on the GPU. How are you trying to call strfind?

[Mate 2u]

Hi I currently have data (numbers) and rotating it horizontally to search for strings within a string. I search many so its time consuming. Any tips?

Answer 3

[Daniel Shub]

I think I lead you to use STRFIND in my answer to this question where I pointed to Loren's blog. If you look at that blog post again, she states that strfind is not the fastest solution when the arrays get big. You might be better off using another one of her solutions because they are faster and at first glance seem to be GPU compatible.

[Mate 2u]

strfind is faster than fastPattern2 even with 20 million elements for me. Now I am trying to doing strfind but another way so I can speed up using gpu.

[Mate 2u]

It seems strfind is actually quite fast!

Answer 4

[Mate 2u]

Any advice anybody? I want to speed up strfind......with or without gpu....note (findPattern2 and findpattern both are very slow for my application).

All the best

[Jan]

Without knowing you application, an advice requires too much guessing.

I assume a C-mex woduld be helpful.

[Mate 2u]

Jan, consider I have a 1x10 million string......if n =6, I would want to do a rolling strfind of all substrings of size 6 in the string of 10 million "prices" (financial application)

[Daniel Shub]

From some of your other questions it is not clear to me if in the real application the "prices" are binary (or small integers) or if they are doubles.

[Mate 2u]

Hi, the string is Diff of prices....so are all in decimals...eg 0.0012 0.0001 -0.0002 etc

Answer 5

[Daniel Shub]

Based on your comment "the string is Diff of prices....so are all in decimals...eg 0.0012 0.0001 -0.0002 etc" I would point out that using STRFIND on floating point number is a BAD IDEA. See FAQ:6.1 as to why comparing floating point numbers is in general a bad idea.

[Mate 2u]

Hi Daniel, I will read that, but I still need to do something. Also read above on how I made "A"

Answer 6

[Jon Lareau]

If you want to run on a GPU you can convert your strings to matrix of uint8 char values. You will need to build your GPU compiant processing function to work with the integer ASCII representation of the chars in the string.

A = uint8(char(my_string_array));

result = some_gpu_enabled_function(gpuArray(A));

[Walter Roberson]

This is not wrong, but in context it is not relevant.

strfind() allows numeric inputs. For example

mask = A(:)>2;
strfind([0;mask].', [0 1 1 1])

would search A looking for each place that a run of at least 3 values in a row are greater than 2.

The question was not about characters, it was about using a pattern matching function that happens to have "str" at the beginning of its name.