Take the 2-minute tour ×

I have a list of two-word sequences as shown below:

word1 word2

word4 word7

word5 word2

word5 word6

word7 word2


Now, for a given word, say wi, I need to find |{wi-1: wi-1wi exists in the list}|. For example, for word2, the answer will be 3 as word1, word5, and word7 appear before word2. 2 questions:

  1. Is there a data structure in CUDA that helps me organize the list such that I can find the answer to the above really fast.
  2. Is there an algorithm that can help me find the answer ?
share|improve this question
Do you want a unique count, or can there be duplicates (say if wi is bar), and "foo bar" appears multiple times, do you only want to count it once? Because if not, you could just count the number of occurences of wi in the second position. –  harrism Jul 9 '12 at 2:31
@harrism: A particular two word seqeunce will just occur once in the list so there can be no duplicates. Yes, I can count the number of occurences of wi in the second positions, but I was wondering what is the fastest way to do this? Can we pre process this list in a manner such that for any wi, we can quicly return the results USING the GPU –  Programmer Jul 9 '12 at 3:42
The only reason I can see to preprocess is because you need to access the counts many times (e.g. over time, or by many threads in parallel). What is your use case? What you do depends on how you intend to use it. –  harrism Jul 9 '12 at 4:02
I need to access each value only once. I think atomic operations seems like the way to go. –  Programmer Jul 9 '12 at 6:06
Write your initial prototype using just atomicInc to build a histogram for all values of wi. Then, depending on which GPU arch you are targeting, you may decide to optimize further using parallel reduction combined with atomics (for example). On Kepler, for example, atomics are likely to be plenty fast enough. And if this kernel isn't your bottleneck, they may be fast enough on other GPUs too. –  harrism Jul 9 '12 at 12:09
add comment


Your Answer



Browse other questions tagged or ask your own question.