Pattern matching on GPU #719
Replies: 1 comment 3 replies
-
|
"Complimentary", but not "replacery" to original post: I have made some attempts to improve computation time using custom made functionality. Codeimport stumpy
from stumpy import config
from scipy import stats
import math
import numpy as np
import time
repeating_data = [219.14, 219.25, 219.15, 219.07, 219.28]
older_data = [218.24, 218.79, 218.69, 218.84, 219.21, 219.0, 218.93, 219.01, 219.0,
218.31, 218.89, 218.21, 218.47, 218.7, 218.52, 218.24, 218.03, 218.03, 218.04, 218.04, 218.21, 218.25,
218.54, 218.44, 218.29]
newer_data = [218.29, 218.42, 218.29, 218.51, 218.87, 218.56, 218.67, 218.58, 218.58, 218.79, 218.81, 218.81,
218.78, 218.84, 218.82, 218.82, 218.69, 218.75, 218.73, 218.98]
data = []
data += older_data
data += repeating_data
data += newer_data
data += repeating_data
m = 5
data_to_find = np.array(repeating_data)
data = np.array(data)
print('data_to_find length ', len(data_to_find))
print('data length ', len(data))
def start_timer():
return time.time()
def stop_timer(start_time, adder=''):
print(adder, "--- %s seconds ---" % (time.time() - start_time))
return start_timer()
def z_norm(a, axis=0):
std = np.std(a, axis, keepdims=True)
std[std == 0] = 1
return (a - np.mean(a, axis, keepdims=True)) / std
def rolling_window(a, window):
a = np.asarray(a)
shape = a.shape[:-1] + (a.shape[-1] - window + 1, window)
strides = a.strides + (a.strides[-1],)
return np.lib.stride_tricks.as_strided(a, shape=shape, strides=strides)
timer2 = start_timer()
distance_profile = stumpy.mass(data_to_find, data)
timer2 = stop_timer(timer2, '\nstumpy.mass ')
idx = np.argmin(distance_profile)
print(f"\tThe nearest neighbor to `Q_df` is located at index {idx} in `T_df`")
distances = np.linalg.norm(z_norm(rolling_window(data, m), 1) - z_norm(data_to_find), axis=1)
timer2 = stop_timer(timer2, '\nCustom ')
idx = np.argmin(distances)
print(f"\tThe nearest neighbor to `Q_df` is located at index {idx} in `T_df`")
print('\nComparing stumpy.mass and custom generated distances')
for i in range(len(distances)):
print('\tMass: ', distance_profile[i], ', Custom: ', distances[i], ', Diff: ', (distance_profile[i] - distances[i]))
print('Done')Output
Surprisingly, the distances are very very similar between the two results.. But we are still able to tell exactly where the match is, based on the distance... Pattern occurrence indices match perfectly. On another the positive side - the computation time is so neglectable, that I see the 0 second computation time! (it's about 0.0001 seconds or something similar) - a huge improvement over 1 second default time. Now, given the essentially same results, and a LOT smaller execution time - would this function not be of some use? I do not understand completely what I have done, but it looks like I have skipped some post-processing step from the original I would still like to see the GPU based function for pattern matching, but, in addition to that - maybe you could make use of this code above to create some kind of "less strict" version of the distance calculation function, that runs many times faster than the original function, even on CPU p.s. I ended up reusing most of the code from unit tests here Line 400 in e8a7dd4 p.p.s I understand that most of the functions are based on research papers from other people.. |
Beta Was this translation helpful? Give feedback.
-
|
@pavlexander Unfortunately, there is an important piece of information that is missing. In STUMPY, (nearly) all of our CPU functions use On my M2 Mac, Unfortunately, we are not currently able to add P.S. Rather than opening up an issue, I recommend opening up a new question in our Github Discussions if your question is more about the API. Much appreciated! |
Beta Was this translation helpful? Give feedback.
-
|
Ran some tests on my own data set and it's as you said.. The performance is top-notch when matching patterns against a big dataset.. It's the initialization that was the problem in my example above. However I have come across another very specific use-case. I have around The code looks like this: def calculate_distances(patterns, pattern):
result = []
for i in range(len(patterns)):
existing_pattern = patterns[i]
distance = stumpy.mass(pattern, existing_pattern)
result.append(distance[0])
return resultThis is not a huge problem when I have to do this just once ( @jit(nopython=True)
def calculate_distances2(preprocessed_patterns_z_norms, pattern):
result = []
z_norm_of_pattern = z_norm(pattern, 0)
for i in range(len(preprocessed_patterns_z_norms)):
existing_pattern_z_norm = preprocessed_patterns_z_norms[i]
distance = np.linalg.norm(existing_pattern_z_norm - z_norm_of_pattern)
result.append(distance)
return np.array(result)Therefore I wanted to ask if you know of the better way of doing this task without hacky solutions? :) |
Beta Was this translation helpful? Give feedback.
-
|
Unless query and time-series have the same length, The intended use case of MASS, is to find a short query sequence in a long time-series. If you have 10k truly independent search queries, then start 10k jobs and use joblib for multithreading. Furthermore you can concatenate the indiviual time series into a single time series corpus: Maybe you actually want an AB-Join where |
Beta Was this translation helpful? Give feedback.
-
Question
Is it possible to utilize GPU in pattern matching tasks?
I am interested in following 2 API's
stumpy.mass- returns distance profilesstumpy.match- returns matchesI get following test execution time measurements:
Conclusion: It takes twice as low amount of time (0.03 seconds) to generate the full matrix profile on GPU, than it is to find matches on CPU! Isn't pattern matching requires lower computational power than matrix profile computation?
The above tests were done on dataset where
n = 55, andm = 5. I am planning on running the pattern matching on a dataset withn =~ 500_000so the execution time will proportionally bump into unreasonably high numbers.. :)This makes me think that currently GPU is not being used for neither of the APIs (
stumpy.mass,stumpy.match)Therefore, my question is - is "pattern matching on GPU" feature planned or is present, and if not, could I propose it to be implemented/added to the agenda? :)
Thank You!
Code used in tests
Software and HW
Win x64, Ryzen 6 cores CPU, 1080 ti GPU
stumpyv1.11.1Beta Was this translation helpful? Give feedback.
All reactions