This is the second part of the Parallel execution for contests series. For your convenience you can find other parts in the table of contents in Part 1 — Powershell
Hello! Today we continue working on parallel codes for contests. Let’s go.
Table of Contents
Test cases
Last time we saw how to execute multiple instances of program at once. However, sometimes it is not enough to just run multiple applications, especially when we are solving problems from a single input file. Fortunately, usually there are multiple test cases in each file.
Most of the contests’ tasks are joined in batches. Authors of the task do it in order to rule out programs which try to guess the answer or to avoid possibility of solving a task by hand. Usually, in the first line of the input there is a number indicating total number of test cases stored in the file.
To achieve greater performance we can use similar approach as in previous part of this series. This time we will run every test case using different thread. However, we need to take care of reading input and writing output.
Let’s say that our input file looks like this:
|
1 2 3 4 |
3 Test case 1 Test case 2 Test case 3 |
Ideally we would like to calculate every test case using different thread. However, we cannot start second thread before the first one ends reading input since we cannot mix the data. Of course, reading from the console is usually synchronized internally, however, we usually cannot read all required data with one simple call to API. We need to execute multiple ReadLines to obtain and parse the input.
There are different approaches. First, we might want to use one thread to read input, parse it, and dispatch to other threads. This would look like follows:
|
1 2 3 4 5 6 |
Thread 1 reads whole input Thread 1 prepares array of input data: [test 1, test 2, test 3] Thread 1 starts three threads and passes them different test data Thread 2, 3, and 4 calculates their results on their own Thread 1 gathers results from other threads Thread 1 prints out the results |
This approach is pretty straightforward, however, it requires parsing the whole input, storing it in memory, and passing only the relevant part to the worker threads. Since we would like to run our algorithm with minimal changes, this might be unacceptable.
We also might use three lambdas:
|
1 2 3 |
For every test case we define three functions: reading function, calculating function, and writing function Thread 1 executes reading functions serialized. When each of them finishes, thread 1 gathers the parsed input and passes it to calculating function. When calculating function is done, thread 1 gathers the output and passes it to writing function. |
This approach is very similar to the previous one and has almost the same drawbacks. This time it might be easier to divide our algorithm in three separated parts, however, we still need to store all input data in memory.
This is why we are going to use different approach.
Serializing with events
We are going to use ManualResetEvent to keep threads in order. We use it in the following way:
|
1 2 3 |
Thread 1 creates six ManualResetEvents, three of them for reading, three of them for writing. Thread 1 creates three threads and gives each of them two reading ManualResetEvents and two writing ManualResetEvents. First reading event and first writing event are already signaled, rest of them are not signaled. Every thread first awaits on first reading event, next reads all the input, and then sets second reading event. When thread wants to write, it first awaits on the first writing event, next it writs its output, finally it sets its second writing event |
With this approach we don’t need to store data and pass it between lambdas. Of course it would be great if we would be able to encapsulate events logic in nice functions so we don’t need to remember all the details.
Implementation
We start with the following implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
using System; using System.Collections.Generic; using System.Threading; using System.Threading.Tasks; namespace ParallelExecution { public static class CSharpParallelExecution { public static void RunInOrder(int taskCount, Action< Action, Action, int > work) { var tasks = new List < Task>(); ManualResetEvent currentRead = new ManualResetEvent(false); ManualResetEvent currentWrite = new ManualResetEvent(false); { bool firstDoneReading = false; bool firstDoneWriting = false; ManualResetEvent read = currentRead; ManualResetEvent write = currentWrite; tasks.Add(Task.Factory.StartNew(() => { work(() => { if (!firstDoneReading) { firstDoneReading = true; return; } read.Set(); }, () => { if (!firstDoneWriting) { firstDoneWriting = true; return; } write.Set(); }, 1); })); } for (int i = 2; i < taskCount; ++i) { int id = i; ManualResetEvent oldRead = currentRead; ManualResetEvent oldWrite = currentWrite; ManualResetEvent newRead = new ManualResetEvent(false); ManualResetEvent newWrite = new ManualResetEvent(false); bool nextDoneReading = false; bool nextDoneWriting = false; tasks.Add(Task.Factory.StartNew(() => { work(() => { if (!nextDoneReading) { oldRead.WaitOne(); nextDoneReading = true; return; } newRead.Set(); }, () => { if (!nextDoneWriting) { oldWrite.WaitOne(); nextDoneWriting = true; return; } newWrite.Set(); }, id); })); currentRead = newRead; currentWrite = newWrite; } if (taskCount > 1) { bool lastDoneReading = false; bool lastDoneWriting = false; tasks.Add(Task.Factory.StartNew(() => { work(() => { if (!lastDoneReading) { currentRead.WaitOne(); lastDoneReading = true; } }, () => { if (!lastDoneWriting) { currentWrite.WaitOne(); lastDoneWriting = true; } }, taskCount); })); } Task.WaitAll(tasks.ToArray()); } } } |
In line 10 we define a function with two parameters: first parameter indicating numer of tasks to run (number of test cases), second parameter is a lambda which accepts two lambdas and one integer. First lambda is lambda to indicate reading, second lambda is for writing, integer is an id of the task.
In line 12 we create a collection for executed tasks. Next, we define two events which will be used throughout the work.
In lines 16-42 we start a task. We pass it two lambdas. They do nothing on first invocation, however, on the second invocation they set an events. This is because first task is always allowed to read or write so it doesn’t need to wait for anyone.
In lines 44-80 we start other tasks. They as well get two lambdas, but this time they (lambdas) need to wait on an event on first invocation.
In lines 82-105 we create last task. Lambdas for this task only needs to wait for an event on first invocation.
We use this code in the following way:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
[Test] public void RunInOrder_MultipleTasks_CorrectOrder() { CSharpParallelExecution.RunInOrder(10, Worker); Assert.Pass(); } public static void Worker(Action signalRead, Action signalWrite, int id) { // I want to read signalRead(); // I am reading // ... // I finished reading signalRead(); // I am done with reading // I work on my task // ... // I am done with calculating // I want to write signalWrite(); // I am writing // ... // I finished writing signalWrite(); // I am done with writing } |
So our worker function only needs to invoke two functions in correct order and we have all serialization done out of the box.
Summary
We are now able to run multiple instances of our application and solve multiple test cases in parallel with almost no changes in algorithm. Next time we are going to examine C++ implementation since most of contests algorithms are written in C++.