ParaCode

From CDOT Wiki
Jump to: navigation, search


GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

Team Members

  1. Qiliang Chen
  2. Xuan Dinh Truong

Email All

Progress

Assignment 1

Project: LZW Compress

Introduction:

LZW stand for "Lempel–Ziv–Welch". It is a universal lossless data compression algorithm which is widely use in compressing software. It is widely used in image compress and Unix file compress. Here is a project example of LZW compressing written by c++. Here's the link for more details: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm

Basic Compile Command:(Linux)

 g++ -std=c++0x lzw.c -o lzw

To Execute Projet

  • Compress file:
 ./lzw -c file.txt
  • Decopress file:
 ./lzw -d file.txt


Profile

We have compress and profile for 3 different size files. The runtime for each is shown below:
Screen Shot 2018-02-23 at 12.55.32 AM.png

To see runtime for each function, see below:
Screen Shot 2018-02-23 at 1.02.40 AM.png

Here is graphic:
Screen Shot 2018-02-23 at 12.42.51 AM.png

Float profile:

Here is the float profile sample for compressing file which has size 54.3MB, float profile is changed to .txt and is simplified)
Screen Shot 2018-02-23 at 1.20.32 AM.png

Project: Grep - Count Keyword in File

Introduction:

On the Linux system, we are very familiar with the Grep command. This is a similar project to that. But this one is more simple. It just counts how many times the keyword appears in the file. After compile the program, we run it as a command like this:
Screen Shot 2018-04-03 at 10.00.32 PM.png

Here, it counts how many 'is' are there in file 'sample.txt'.

Profile: We've make three different sizes of files to profile the program. The runtime of them show below:
Screen Shot 2018-04-03 at 10.11.02 PM.png

To see runtime for functions, see below:
Screen Shot 2018-04-03 at 10.27.19 PM.png

See graphic:
Screen Shot 2018-04-03 at 10.26.29 PM.png

Profile via Visual Studio Sample: NoPara 4023k.JPG

Assignment 2

We are going to work on 'Grep' project.

Through the profile, we can see that the most cost of the runtime is 'grep()' and 'convert_char_to_string()' functions.


Basic Variables

Let's go and see the basic variables in code:
BasicVar.JPG

First, I look at function 'convert_char_to_string()'. I think it's no necessary to use this function, so I remove it.
StringremoveJPG.JPG


Serial grep method

Then, we start working in grep function. As file size growing up, which means more characters in file, the runtime of 'grep()' grows much more faster than the other functions. So we are going to work on 'grep()' function.

Let's going through grep() function:
Screen Shot 2018-04-03 at 10.42.41 PM.png

We can see, there're two for loop in grep() function. In loop is inside another. Which mean it's kind of O(n^m) runtime function. That's why it cost a lot of time to run.

The idea of grep is very simple. The inside loop make a temporary string from input string with the length of keyword length. Then it compare the temp string to keyword. If they equal, means this temp string is the same as keyword string. It increases the counter by 1.
GrepIdea.JPG

Simple? But to parallel it is not that simple...


Parallel grep idea

If we put the character array to CUDA kernel to run, those characters will run individually in different threads. It will look like this:
LineInThreads.JPG

Also, if we put keyword character array in kernel, the characters will run in individual thread as well:
Keyword.JPG

It's impossible to compare the string keyword to the file input string cause all characters are individual in threads. That make us spend a huge time to figure out the solution.

Although we cannot compare a whole string, it is possible to compare by one character. For example, it is possible to find just 'h' in input string.
FindH.JPG

With the same idea, we can find 'a':
FindA.JPG

What's next??

We create an integer array. The size of this array is the same as input's size. This array is to record the characters exist in that position. If characcter exist, we mark it as specific number. Wecall this array as band.

First, we initialize all integers as '0'. This means all characters in keyword are not found in that position in input.
Initial.JPG

Then, we start to find keyword's characters in input string. For example, we want to find 'h'. As 'h' is the first character in keyword, we will mark it '1' in the integer array 'band'. Like this:
Mark1.JPG

With the same idea, we find out the second character 'a'. As 'a' is the second character in keyword, we mark it '2'.
Mark2.JPG

After all characters in keyword are found, we will count how many numbers are connected in sequence.
NumInSequence.JPG

This is our main idea to parallel the grep function. Yes, it still have some loops. But those loops are not as large as that in serial grep function. So we start to design the code foe it.


Parallel grep code

Here are part of parallel grep code:

Main grep parallel:
ParaGrep.JPG

Initial integer arrar kernel:
InitialBandFunc.JPG

Grep character kernel:
GrepKernel.JPG

Two grep:
GrepCompare.JPG

Run and result:
Result22.JPG

Yes. The grep of parallel's result is the same as serial's result! It works!

Profile

Sample of profile:
ProfilePara.JPG

Run and record time data for serial program and parallel program. We got the time for each:
TimeCompareTwoPart.JPG

Generate the graphics:
Total time compare:
TotalCompare.JPG

Time compare for function grep() and grepPara():
TimecompareFunction.JPG

We got it!

Assignment 3

Next, we optimize the code so that it runs faster.

Use shared memory

We change global memory to shared memory in kernel grepx(). The code is:
SharedMem.JPG


Profile

We get the data like this:
SharedData.JPG


' ntpb

We also try different ntpb and see if it effect runtime.
NtpbDiff.JPG

According to the data, the number of ntpb is not an important factor affecting time.

End

That's all for our assignment.


Resources

You can see my code here: https://gist.github.com/KignorChan/764c71d9d96561e4101d9830e0bc5e69

Idea from LZW compress program: https://codereview.stackexchange.com/questions/86543/simple-lzw-compression-algorithm