Grid Locking Granularities

GRID: Introduction

For this assignment you will be experimenting with different granularities of locking on a data structure that is shared among many threads.

The data structure you will be experimenting with is a simple n x n array of numbers. The invariant is that the sum of all entrees in the grid remain the same.

n will range from 1 to 10.

You will have many threads executing in your program. 

The life cycle of each thread is:

	for i = 1 to NO_SWAPS
		cell1 = random cell
		cell2 = random cell
		swap(cell1, cell2)
	end for

In order to allow more than 1 thread to execute this code concurrently on the data structure, there must be some locking to prevent corruption of data.

Since this is a gridded data structure, it is natural to think of four different granularities of locking:

Program usage:

gridapp gridsize numthreads locking_granularity

Examples:

gridapp 8 3 -cell
- executes gridapp with an 8 x 8 array, 3 threads running, with cell level locking

gridapp 10 100 -grid
- 10 x 10 array, 100 threads running, grid level locking

gridapp 10 100 -row
10 x 10 array, 100 threads running, row level locking

gridapp 10 100 -none
10 x 10 array, 100 threads running, *** NO LOCKING *** this is for testing, and data should be corrupted at the end.

Program output:

The initial and final sums should match if there is no data corruption

(i.e. the synchronization code is correct).

GRID: Objectives

GRID: Steps for Your Assignment

  1. Examine the skeleton code we have provided: gridapp.c in gridapp.tar.gz
    Note that grid initialization, printing, and summing functions are provided.
    We have also provided the thread starting code and the thread's function body.
    Note the sleep(1) hidden in the middle of the swap operation. You will investigate this later in the assignment.
  2. Compile (note the -lpthread)and execute this code, examine results:
    gcc -o gridapp gridapp.c -lpthread
    ./gridapp 10 1 -none
  3. We have provided everything you need except for the locking data structures and locking code. (Don't forget threads_left!)
    You should be able to fill in the necessary code using pthread synchronization primitives like pthread_mutex_lock/pthread_mutex_unlock or pthread_cond_wait/pthread_cond_signal. You will need to decide how many locks to use and what each one protects.

    NOTE THAT YOU WILL NEED A DEADLOCK PREVENTION SCHEME. You can add code elsewhere if necessary like global variable declarations, etc.

  4. Verify that the concurrency is working correctly: 
      Run
  
	    ./gridapp 10 10 -cell
	    ./gridapp 10 10 -row
	    ./gridapp 10 10 -grid
    All of these should result in the same initial and final sum.
    There should also be significant differences in time elapsed. Note these results.
  5. Now, try running without locking again
    Run ./gridapp 10 10 -none
    The initial and final sum should be different.
    Also note how the elapsed time compares to the other cases.
  6. Experiment with different grid sizes, thread counts, and granularities of locking.
    1. At grid size 10, graph the time elapsed on the y axis and thread count from 1 to 10 on the x axis. Make this graph for all four types of granularity (-none, -cell, -row, -grid). The total tests are 40(10*4). Each test should be run 3 times and recorded. And calculate their means and variance, then use the means as the final results to put into the graph.

      (Experiment: What is the maximum number of threads you can create with pthread_create failing?)

    2. Now, leave the thread count at 10, graph the time elapsed on the y axis and the grid size from 2 to 10 on the x axis. Make this graph for all four types of granularity. The total tests are 36(9*4). Each test should be run three times and recorded, calculating its means and variance, then use the means as the final results to put into the graph.
    (Suggestions:)You could write your own Linux scripts to run each of 76 tests multiple times(say 3). Import those results into MS Excel spreadsheets. Use the Excel fomula function to calculate means and variance for each test. Then graph the results of those means in two separate graphs. Here are some example scripts that you can try.
  7. Answer the questions about:
    What can you conclude about how grid size, number of threads, and locking granularity affect performance?
    What general results can you conclude from this exercise? When does fine granularity locking have the biggest effect? What costs does it impose?
  8. Experiment with no locking. Without any modifcations, you shouldn't get any integrity violation with 1 thread. Why? With a big enough grid and few enough threads, you might avoid data integrity violations. Why?
  9. Note the sleep(1) command in the swapping code.
    • Why do you think it is there? Try commenting it out or moving it to a different location in the block of swapping code. Try moving it to just before the first line of the swapping code but after you have obtained your lock.
    • What effects does this have on performance and correctness of final sum? Try experimenting with all levels of granularity on a 10x10 grid with 10 threads.
    • Anything surprising?
    • What can you say about why this sleep(1) is there and where it is placed?
    • If we didn't have this sleep(1) there, how would this change the assignment?
    • What does this say about when multithreading and synchronization make sense?

GRID: Available Materials

GRID: Submission

What to submit:

Submit the following to Moodle, a single tar.gz file containing: