Pattern matching on GPU

[pavlexander]

Question

Is it possible to utilize GPU in pattern matching tasks?

I am interested in following 2 API's

• stumpy.mass - returns distance profiles
• stumpy.match - returns matches

I get following test execution time measurements:

stumpy.mass --- 0.9919984340667725 seconds ---
stumpy.match --- 0.05500030517578125 seconds ---
stumpy.stump --- 6.415998935699463 seconds ---
stumpy.gpu_stump --- 0.030998945236206055 seconds ---

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, and m = 5. I am planning on running the pattern matching on a dataset with n =~ 500_000 so 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

import time
import stumpy
from stumpy import config
import numpy as np

def start_timer():
    return time.time()

def stop_timer(start_time, adder=''):
    print(adder, "--- %s seconds ---" % (time.time() - start_time))
    return start_timer()

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))

timer2 = start_timer()
distance_profile = stumpy.mass(data_to_find, data)
timer2 = stop_timer(timer2, 'Mass ') 

matches = stumpy.match(data_to_find, data)
timer2 = stop_timer(timer2, 'Match ') 

mp = stumpy.stump(data, m)
timer2 = stop_timer(timer2, 'CPU stomp ') 

mp = stumpy.gpu_stump(data, m)
timer2 = stop_timer(timer2, 'GPU stomp ') 

Software and HW

Win x64, Ryzen 6 cores CPU, 1080 ti GPU

stumpy v1.11.1

[pavlexander]

"Complimentary", but not "replacery" to original post: I have made some attempts to improve computation time using custom made functionality.

Code

import 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

stumpy.mass --- 0.9259753227233887 seconds ---
The nearest neighbor to Q_df is located at index 25 in T_df

Custom --- 0 seconds ---
The nearest neighbor to Q_df is located at index 25 in T_df

Comparing stumpy.mass and custom generated distances
Mass: 2.2105205844573215 , Custom: 2.210520585039989 , Diff: -5.826676918729845e-10
Mass: 3.8282502748376936 , Custom: 3.828250275047967 , Diff: -2.1027357632874555e-10
Mass: 3.4533746719581417 , Custom: 3.4533746718142164 , Diff: 1.4392531610951664e-10
Mass: 1.9113193715052448 , Custom: 1.9113193732141167 , Diff: -1.7088719328484103e-09
Mass: 3.458043570843686 , Custom: 3.458043571020999 , Diff: -1.7731283108446405e-10
Mass: 4.154752748228278 , Custom: 4.154752748523079 , Diff: -2.9480151653160647e-10
Mass: 1.8414238802224574 , Custom: 1.8414238819074986 , Diff: -1.6850412176694363e-09
Mass: 3.701514742892828 , Custom: 3.701514743304959 , Diff: -4.121307739524127e-10
Mass: 3.357192640386953 , Custom: 3.357192640174392 , Diff: 2.1256107984868322e-10
Mass: 1.7340022421510477 , Custom: 1.7340022425813102 , Diff: -4.302624923013809e-10
Mass: 4.025896930746229 , Custom: 4.025896931101078 , Diff: -3.5484948313069253e-10
Mass: 3.6908006445288866 , Custom: 3.6908006451267976 , Diff: -5.979110540010879e-10
Mass: 3.247382093375601 , Custom: 3.2473820937951627 , Diff: -4.195617187008338e-10
Mass: 3.101020367895569 , Custom: 3.101020368198151 , Diff: -3.025824035773894e-10
Mass: 3.2151523541440556 , Custom: 3.21515235502738 , Diff: -8.83324524636464e-10
Mass: 3.542604830177246 , Custom: 3.54260483306828 , Diff: -2.891034078800203e-09
Mass: 1.9202249779012381 , Custom: 1.9202249837287837 , Diff: -5.827545557224312e-09
Mass: 3.0104809717644745 , Custom: 3.010480971920461 , Diff: -1.559863349598345e-10
Mass: 2.5794214522067587 , Custom: 2.5794214531544806 , Diff: -9.477219009568216e-10
Mass: 3.3182572646681816 , Custom: 3.3182572649903617 , Diff: -3.221800604080727e-10
Mass: 3.850433587331335 , Custom: 3.8504335883242375 , Diff: -9.929026489885473e-10
Mass: 1.3154870358066373 , Custom: 1.315487036488339 , Diff: -6.817018061155977e-10
Mass: 3.0824902985267824 , Custom: 3.082490298938153 , Diff: -4.113704932251494e-10
Mass: 3.5960444037723738 , Custom: 3.5960444041766886 , Diff: -4.043148038590516e-10
Mass: 2.904488555396711 , Custom: 2.904488556126461 , Diff: -7.297500381753252e-10
Mass: 0.00010079352952945846 , Custom: 0.0 , Diff: 0.00010079352952945846
Mass: 4.16416120131542 , Custom: 4.164161201588881 , Diff: -2.7346036546305186e-10
Mass: 3.069263551540473 , Custom: 3.0692635513875994 , Diff: 1.528737136879954e-10
Mass: 2.8791877762763187 , Custom: 2.87918777661224 , Diff: -3.359210687392533e-10
Mass: 3.3649871025910105 , Custom: 3.364987102578873 , Diff: 1.2137402194412061e-11
Mass: 2.1328441196088974 , Custom: 2.1328441188015987 , Diff: 8.072986723561826e-10
Mass: 4.028530575737881 , Custom: 4.028530575299188 , Diff: 4.3869352595038436e-10
Mass: 2.956792368133736 , Custom: 2.956792367984455 , Diff: 1.492810319803084e-10
Mass: 2.655451909828746 , Custom: 2.6554519099073945 , Diff: -7.864864315365594e-11
Mass: 3.6576912140403177 , Custom: 3.6576912156040735 , Diff: -1.5637557915226807e-09
Mass: 1.1457593089109914 , Custom: 1.1457593076787576 , Diff: 1.2322338704962021e-09
Mass: 3.2703485305235573 , Custom: 3.2703485303642403 , Diff: 1.5931700403370996e-10
Mass: 3.4241058351283016 , Custom: 3.4241058365722243 , Diff: -1.4439227591367398e-09
Mass: 2.9566489570340115 , Custom: 2.9566489587835862 , Diff: -1.7495747073326129e-09
Mass: 1.0341935968089795 , Custom: 1.0341936093022772 , Diff: -1.2493297729676556e-08
Mass: 3.44291838472567 , Custom: 3.4429183952948716 , Diff: -1.0569201513987991e-08
Mass: 3.7506410276983564 , Custom: 3.7506410263700323 , Diff: 1.3283241173667193e-09
Mass: 3.8728677730397068 , Custom: 3.8728677713513258 , Diff: 1.6883809905721137e-09
Mass: 2.6735389665990144 , Custom: 2.6735389665005984 , Diff: 9.841594206250193e-11
Mass: 2.99521481673855 , Custom: 2.995214817101798 , Diff: -3.632480982673769e-10
Mass: 2.2901261143524523 , Custom: 2.290126113750003 , Diff: 6.024492016365457e-10
Mass: 2.7078183471280237 , Custom: 2.7078183479412936 , Diff: -8.132698958718265e-10
Mass: 3.1422797563859666 , Custom: 3.1422797575820334 , Diff: -1.1960668011568032e-09
Mass: 3.3126752260590555 , Custom: 3.3126752261699 , Diff: -1.1084466677857563e-10
Mass: 3.393349891753226 , Custom: 3.3933498928226915 , Diff: -1.0694654051235375e-09
Mass: 0.0001010852974836315 , Custom: 0.0 , Diff: 0.0001010852974836315
Done

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 stumpy.mass function, that makes the distances slightly different, and execution time many times slower. Please correct me if I am wrong.

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 https://github.com/TDAmeritrade/stumpy/blob/e8a7dd4566eb662fc1c49a2a3b692035f64f18c3/tests/test_core.py#L400

p.p.s I understand that most of the functions are based on research papers from other people..