Go Back > Extra Stuff > Programming

Thread Tools
Old 2013-02-14, 13:47   #1
Feb 2013

1 Posts
Default GPU optimization over snappy compression

Hi all,

I am willing to perform GPU optimization over snappy compression in my project. Please suggest feasibility and challenges I may face for the same. Also references and ideas are most welcome.

Thanks in advance.

Rakesh Kumar Rakshit
ihavethepotenti is offline   Reply With Quote
Old 2013-02-14, 18:11   #2
garo's Avatar
Aug 2002
Termonfeckin, IE

ACC16 Posts
garo is offline   Reply With Quote
Old 2013-02-15, 00:20   #3
Ken_g6's Avatar
Jan 2005
Caught in a sieve

5·79 Posts

I have some experience in this area, at least on the CPU. First, let me say that I hope you're in a country that does not recognize software patents. Compression is an area that is highly patent-encumbered.

Your challenge appears to be to search your string for patterns of at least four characters that have occurred before. I used the inefficient Boyer-Moore search for the longest time, because, patents. I later found that this patent had expired, and used its search method (a hash of sets of, in your case, four characters). There are other methods, like search trees, out there, I'm sure.

Now, what can you do with the GPU? You can hash sets of four characters, but that's no great feat. The trick is to take each hash and link it to what the hash matched just before - easy in series but hard in parallel. I can think of an idea or two, but this is your challenge, not mine. You may want to search for alternative parallel string searching algorithms as well.

After doing that, I added an optimization, not in the patent, to ensure that the linked lists actually point to exact matches, rather than just inexact hash matches. I think it's commented out in the JSPack code, because, patents. This seems relatively more doable on the GPU.

Good luck!

P.S. Mods, might this be better in the Programming forum?
Ken_g6 is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Size optimization Sleepy Msieve 14 2011-10-20 10:27
NFS Optimization R.D. Silverman Factoring 91 2010-01-24 20:48
video compression chatter by jasong jasong jasong 24 2008-01-13 11:23
Compression program Prime95 LMH > 100M 1 2005-03-23 15:18
ASM Optimization Cyclamen Persicum Hardware 4 2004-05-26 07:51

All times are UTC. The time now is 01:05.

Thu Dec 2 01:05:39 UTC 2021 up 131 days, 19:34, 1 user, load averages: 1.06, 0.99, 0.89

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.