Parallel Programming 4CC3 Course Fall 2023
Parallel Programming 4CC3 Course Fall 2023
Question 1 - Parallel Alphabetical Sort of Names
A very common job in programming is to provide an alphabetized list. This project has a very simple description read the large file of people names (first name followed by given name) and sort this list by last name (first) and then by first name (for any repeated last names).
Your Challenge
Your code must implement the sort using a parallel sorting technique. You can use any sorting technique that you like but it must be a parallel sort and it must NOT use a .NET sorting function. I have provided a .NET sort as a baseline (shown below). See if your code can sort faster than the implementation that I have provided.
In order to simplify your implementation, you can (and should) use a method which will compare strings alphabetically. In C#, this looks like:
string.Compare(string A, string B)
This function returns -1 if string A is first in alphabetical order, 0 if the strings are the same, and 1 if string B is first in alphabetical order. Note that you will have to figure out how to perform the sort first by last names and then by first names if the last names are the same.
Your code must determine how long the sort takes in milliseconds and output that time to the screen. To do that you can use the stopwatch function:
Stopwatch stopwatch = Stopwatch.StartNew();
yourSortFunction();
stopwatch.Stop();
Console.WriteLine("Code took {0} milliseconds to execute", stopwatch.ElapsedMilliseconds);
Grading
This project is going to be graded in a relative way and will be broken down as follows:
70 % - submitted code that implements a parallel sort & write a paragraph about your implementation (8-10 lines max.)
20 % - code produces a valid time for the sort in milliseconds (i.e. it works)
A Very Simple Implementation
Using Linq in .Net, a very simple implementation is:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;
using System.Diagnostics;
namespace NameSort{
class name
{
public name(string fname, string lname)
{
this.firstName = fname; this.lastName = lname;
}
public string firstName { get; set; }
public string lastName { get; set; }
}
class Program
{
static void Main(string[] args)
{
List<name> Names = new List<name>();
// populate the list of names from a file
using (StreamReader sr = new StreamReader("names.txt"))
{
while (sr.Peek() >= 0)
{
string[] s = sr.ReadLine().Split(' ');
Names.Add(new name(s[0], s[1]));
}
}
Console.WriteLine("Sorting...");
// time the sort.
Stopwatch stopwatch = Stopwatch.StartNew();
List<name> sortedNames = Names.OrderBy(s => s.lastName).ThenBy(s => s.firstName).ToList();
stopwatch.Stop();
Console.WriteLine("Code took {0} milliseconds to execute", stopwatch.ElapsedMilliseconds);
Console.WriteLine("Press Return to exit");
Console.ReadLine();
}
}
}
This implementation takes about 50 milliseconds to run on my laptop in release mode.
Question 2 Petersons Lock
Your goal is to implement Petersons lock (for 2 threads) in Python. You can (and should)
use the reference code that I reviewed in class.
Your implementation MUST accomplish the same outcome in the same way as the reference code.
In other words, your code must start 2 threads called IncrementValueT1 and IncrementValueT2 as
functions. Do NOT use a thread pool or other way of creating threads. Your implementation can be object oriented if you wish or you can use static functions.
Petersons lock must be implemented as 2 functions (lock() and unlock()). Again, these can be static or
bound to an object if you wish to use an OOP approach.
In the main portion of your code, start the 2 threads and wait for both of them to finish.
Run your implementation and provide a short discussion of whether your lock works(4-5 lines max.)
