C++ To Cuda Conversion/String Generation And Comparison

Question

So I am in a basic High School coding class. We had to think up one of our semester projects. I chose to base mine on ideas and applications that arn't used in traditional code. This brought up the idea for use of CUDA. One of the best ways I would know to compare speed of traditional methods versus unconventional is string generation and comparison. One could demonstrate the generation and matching speed of traditional CPU generation with timers and output. And then you could show the increase(or decrease) in speed and output of GPU Processing.

I wrote this C++ code to generate random characters that are input into a character array and then match that array to a predetermined string. However like most CPU programming it is incredibly slow comparatively to GPU programming. I've looked over CUDA API and could not find something that would possibly lead me in the right direction for what I'm looking to do.

Below is the code I have written in C++, if anyone could point me in the direction of such things as a random number generator that I can convert to chars using ASCII codes, that would be excellent.

#include <iostream>
#include <string>
#include <cstdlib>

using namespace std;

int sLength = 0;
int count = 0;
int stop = 0;
int maxValue = 0;
string inString = "aB1@";
static const char alphanum[] =
"0123456789"
"!@#$%^&*"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";

int stringLength = sizeof(alphanum) - 1;

char genRandom()
{
    return alphanum[rand() % stringLength];
}

int main()
{
    cout << "Length of string to match?" << endl;
    cin >> sLength;
    string sMatch(sLength, ' ');
    while(true)
    {
        for (int x = 0; x < sLength; x++)
        {
            sMatch[x] = genRandom();
            //cout << sMatch[x];
            count++;
            if (count == 2147000000)
            {
                count == 0;
                maxValue++;
            }
        }
        if (sMatch == inString)
        {
            cout << "It took " << count + (maxValue*2147000000) << " randomly generated characters to match the strings." << endl;
            cin >> stop;
        }
        //cout << endl;
    }

}

score 2 · Accepted Answer · edited May 23 '17 at 12:05

If you want to implement a pseudorandom number generator using CUDA, have a look over here. If you want to generate chars from a predetermined set of characters, you can just put all possible chars into that array and create a random index (just as you are doing it right now).

But I think it might be more valuable comparison might be one that uses brute force. Therefore, you could adapt your program to try not random strings, but try one string after another in any meaningful order.

Then, on the other hand, you could implement the brute-force stuff on the GPU using CUDA. This can be tricky since you might want to stop all CUDA threads as soon as one of them finds a solution. I could imagine the brute force process using CUDA the following way: One thread tries aa as first two letters and brute-forces all following digits, the next thread tries ab as first two letters and brute-forces all following digits, the next thread tries ac as first two letters and brute-forces all following digits, and so on. All these threads run in parallel. Of course, you could vary the number of predetermined chars such that e.g. the first thread tries aaaa, the second aaab. Then, you could compare different input values.

Any way, if you have never dealt with CUDA, I recommend the vector addition sample, a very basic CUDA example, that serves very well for getting a basic understanding of what's going on with CUDA. Moreover, you should read the CUDA programming guide to make yourself familiar with CUDAs concept of a grid of thread-blocks containing a grid of threads. Once you understand this, I think it becomes clearer how CUDA organizes stuff. To be short, in CUDA, you should replace loops with a kernel, that is executed multiple times at once.

This seems to be what I was looking for. And I was under the impression that this was basically a brute force method but under different implementation. Any idea as to how I could better this code to implement true BF methodoloy? — Cistoran, Feb 23 '11 at 17:47

score 0 · Answer 2 · answered Feb 23 '11 at 17:10

First off, I am not sure what your actual question is? Do you need a faster random number generator or one with a greater period? In that case I would recommend boost::random, the "Mersenne Twister" is generally considered state of the art. It is a little hard to get started, but boost is a great library so worth the effort.

I think the method you arer using should be fairly efficient. Be aware that it could take up to (#characters)^(length of string) draws to get to the target string (here 70^4 = 24010000). GPU should be at an advantage here since this process is a Monte Carlo simulation and trivially parallelizable.

Have you compiled the code with optimizations?

My question is asking about a random generator in CUDA that I can use to convert to chars to compare against a string. — Cistoran, Feb 23 '11 at 17:39

C++ To Cuda Conversion/String Generation And Comparison

2 Answers2