Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

This does something very similar to the example above: it forks a process to run the quickSort function on a different process, parallelizing the program.  There is also a need to be sure not to create too many forked processes because it will not only crash the program, but there is no way to close the once the program crashes, so a computer restart is required.  Also note: THIS DOES NOT WORK.  It took me a while to figure this out, but the fork cannot share variables outside of its scope, so it cannot return the updated list, which means this does not sort the list.  Testing is important, people!

There is much less control over forks in Ruby than over threads.  There is no list of threads that can be mapped and reused - the forks operate independently from this program so control over than is lost until they finish.  

I completed tasks 1 and 2 from part 1 in Ruby. 

For task 1, I experimented with whether it is faster to use threads or forks to parallelize quick sort.  To do this, I used a thread and a fork to call the recursive  quick sort algorithm from Project 4, as displayed in the images above.  With a list of 5,000 random numbers, the output was:

Image Removed

When the size of the list doubles, the forking method takes 0.003 seconds - a little less than twice as long.  Thus, in general, as the size of the list doubles the amount of time it takes approximately doubles as well. wrote a quick sort algorithm that breaks an array into the number of threads parts, then uses my quick sort algorithm from project 4 to sort each part.  Then I merge these sorted lists into an overall sorted list to get the whole sorted list using this loop:

Image Added

I experimented with this algorithm to see how the the time it takes to sort an array with 500,000 elements changes with the number of threads used:

Image Added

Since my computer has two cores, it can run two threads truly in parallel, so going from one to two threads sees the biggest speed up.  After that there is a small speed up when using 4 threads, and then the time actually increases with 8 and 16 threads. 

I then looked if I used two threads how the time changes with the number of items in the list.  This is what I found:

Image Added

Thus, as the number of items in the list doubles the time increases by about double and when the size increases by a factor of 5, the time increases by approximately a power of 5.  Thus, the time it takes is proportional to the number of items in the list.  

For task2, I first needed to determine how to modify images in Ruby at the pixel level. I found the pnm package of ruby, which reads in an image using its read function, then the object that it returns has a data field that contains an array of arrays for each pixel, which is an array with the red, green, blue and alpha values. I could loop over each pixel to change its rgb value similar to in colorize.c:

...