Homework #2

Due Tuesday, October 19th, 2010 by Midnight

  1. Lambda Expressions and Captures

    For the following lambda expression examples, perform the following:

    1. Identify captured variables
    2. Identify all read and write accesses to captured variables
    3. State all possible outputs.
    1. class MyProgram { public static void Main(string[] args) { int[] array = {10,9,8,7,6,5,4,3,2}; var addToArrayAndSum = DynamicSum(array); Console.WriteLine("Sum = {0}", addToArrayAndSum(-1, -1)); Console.WriteLine("Sum = {0}", addToArrayAndSum( 2, 7)); Console.WriteLine("Sum = {0}", addToArrayAndSum( 4, 4)); Console.WriteLine("Sum = {0}", addToArrayAndSum(-2, 7)); Console.WriteLine("Sum = {0}", addToArrayAndSum( 0, 9)); } private static Func<int,int,int> DynamicSum (int[] array) { int sum = -1; Func<int> sumArray = () => { // First lambda expression if (sum == -1) { sum = 0; foreach(int i in array) { sum += i; } } return sum; }; Func<int,int,int> changeValueInArray = (idx, value) => { // Second lambda expression if (idx >= 0) { array[idx] = value; sum = -1; } return sumArray(); }; return changeValueInArray; } }

    2. public static void Main (string[] args) { int x = 5; int y = 12; int z = -3; Parallel.Invoke( () => { if ( x < 3 ) Console.WriteLine("x = {0}", x); else if ( y > 10 ) Console.WriteLine("y = {0}", y); else if ( z < 0 ) Console.WriteLine("z = {0}", z); }, () => { if ( x < 3 ) x -= 5; else if ( y > 10 ) y -= 5; else if ( z < 0 ) z -= 10; }); }

  2. Happens Before Graphs

    For the following code examples, draw a Happens Before Graph

    1. public static void Main (string[] args) { int[] array1 = {9,8,5,3,6,3,4}; int[] array2 = {5,4,3,6,6,7,5}; int c1 = 3; int c2 = -5; int[] array3 = new int[7]; Parallel.For(0, 7, i => { array3[i] = c1*array1[i] - c2*array2[i]; }); }

    2. private TimeSpan FrameUpdate(Particle[] particles) { Stopwatch stopwatch = new Stopwatch(); stopwatch.Start(); Parallel.ForEach(particles, particle => { Parallel.Invoke( () => { particle.y.UpdateVelocityFromAcceleration(-32); particle.y.UpdatePositionFromVelocity(); }, () => particle.x.UpdatePositionFromVelocity(), () => particle.y.UpdatePositionFromVelocity() ); particle.CollisionDetect(); }); RenderFrame(particles); stopwatch.Stop(); return stopwatch.Elapsed; }

  3. Determinism testing

    In the StudentLibrary project, we have provided sequential algorithms for smoothing an image and also to find the average color of an image in the GraphicsUtil.cs file. Also specified is the SmoothAndGetAverageColor_Sequential() method which will smooth the image and then return the average color in the smoothed image.

    1. Implement the stub for GraphicsUtil.SmoothAndGetAverageColor_Parallel() that performs the tasks in parallel using the Parallel class. It currently just calls the *_Sequential method. This method gives you plenty of options on how to parallelize all the tasks needed. Calling this method should be data race and deadlock free. Any ScheduleTestMethod or DataRaceTestMethod tests we create must pass.

    2. Create a seperate Alpaca project for your own unit/concurrency testing. Your code must be data race and deadlock free.

    3. In your project report, you should include at least one screenshot of a TaskoMeter graph (i.e. a ScheduleTestMethod) that shows timings of the original sequential algorithms compared to any parallel implementations you have created. You must have at least one specification for your final parallel version. It may help you to add TaskMeter intervals within any Action/Func delegates to help you see how the scheduler may be splitting your function onto different threads.

    4. Finally, in your report, you should include a diagram of your final algorithm and the happens before graph for it. Happens before graph for SmoothAndGetAverageColor_Sequential.

    Parallel constructs you may use: You may only use the methods on the System.Threading.Tasks.Parallel static class.

    Caution: When creating schedule or data race tests, know that the Parallel.ForEach<TSource, TLocal>(...) overloads are not currently instrumented. There will be an updated download of Alpaca that will include instrumentation of all the other overloaded methods on the Parallel class.

    Note on pointers: To use pointers in C# (as when using some of the API on the FastBitmap class) you need to enable unsafe code in your project. If you use pointers in your code, the compiler will tell you to set the /unsafe option for the project. To do this for a project, open up Properties -> Build -> check the "Allow unsafe code" option. The StudentLibrary project already has this option checked because the sequential implementation uses unsafe code.

  4. Data Races and Locks

    For this section, you must examine the two given programs, Dining Philosophers and TicketBuyer, and:

    1. TicketBuyer program
      1. Spot all reads and writes of shared data.
      2. Using the underlying Happens-Before graph, show if there is a possability of a data race. Circle any code snippets where these data races occur.
      3. Check this program for any deadlocks.
      4. Use fine-grain lock leveling to fix any correctness issues you previously found.

      public class TicketBuyer { static readonly int MAX_ROWS = 200; static readonly int MAX_SEATS_ROW = 100; private bool[,] ticketsSold = new bool[MAX_SEATS_ROW, MAX_ROWS]; public List<Ticket> BuyContiguousTickets(int count) { List <Ticket> Tickets = new List<Ticket>(); for (int row = 0; row < MAX_ROWS; ++row) { for (int seat = 0; seat < MAX_SEATS_ROW; ++seat) { if (seat + count > MAX_SEATS_ROW || ticketsSold[seat, row] == true){ foreach (Ticket t in Tickets) { ticketsSold[t.seat, t.row] = false; } Tickets.Clear(); if(seat + count > MAX_SEATS_ROW) break; //next row }else{ Tickets.Add(new Ticket(row, seat)); ticketsSold[seat, row] = true; if (Tickets.Count == count) { goto exit; } } } } exit: return Tickets; } public void StartBuyers() { //create multiple threads that will call TicketBuyer until an empty list is returned }

    2. Dining Philosophers
      1. Circle and identify any correctness issues.
      2. Correct any correctness issues that you previously found.

      public class DiningPhilosophers { static readonly int NUM_PHILOSOPHERS = 5; static readonly int NUM_MEALS = 1; static object[] locks = new object[NUM_PHILOSOPHERS]; static void RunPhilosopher(object id) { int i = (int)id; Random rand = new Random(); int meals = NUM_MEALS; while (meals-- > 0) { if (rand.Next(0, 1) == 0) {//left fork then right lock(locks[i]) { lock(locks[(i + 1) % NUM_PHILOSOPHERS]) { Console.WriteLine("Philosopher {0} ate", i); } } } else {//right fork then left lock (locks[(i + 1) % NUM_PHILOSOPHERS]) { lock(locks[i]) { Console.WriteLine("Philosopher {0} ate", i); } } } } } [ScheduleTestMethod] public void Test() { System.Threading.Thread[] t = new System.Threading.Thread[NUM_PHILOSOPHERS]; for (int l = 0; l < NUM_PHILOSOPHERS; ++l) locks[l] = new object(); for (int p = 0; p < NUM_PHILOSOPHERS; ++p) { t[p] = new System.Threading.Thread(RunPhilosopher); t[p].Start(p); } for (int p = 0; p < NUM_PHILOSOPHERS; ++p) { t[p].Join(); } } }

  5. Data Access Patterns

    For this problem, you are given three methods that are operating on some shared data and being called by multiple threads. You must label each one either Synchronized, Immutable or Isolated depending upon which style fits best.

    void DoWorkA(int[][] data) { for(int i = 0; i < data.GetLength(0) - 1; ++i) { for (int j = 0; j < data.GetLength(1); ++j) { lock (locks[i][j]) { lock (locks[i + 1][j]) { ProcessItem(data[i][j], data[i+1][j]); } } } } } void DoWorkB(int[][] data) { for (int i = 0; i < data.GetLength(0); ++i) { ProcessRow(data[i]); } } void DoWorkC(int[][] data) { int[][] copy = CloneItem(data); ProcessClone(copy); MergeWork(data, copy); }

DOWNLOAD

The code for this assignment is here

Handin Instructions

Zip up your work into a single file, and use the CADE's handin utility:

handin cs5955 hw2 [your zip file]

OR you may use the web utility here