Concurrent Programming
COMP 409, Winter 2019
Assignment 4
Due date: Friday, April 12, 2019 6pm
All code should be well-commented, in a professional style, with appropriate variables names, indenting, etc. Your code must be clear and readable. Marks will be very generously deducted for bad style or lack of clarity.
All shared variable access must be properly protected by synchronization (no race conditions). Unless otherwise specified, your programs should aim to be efficient, and exhibit high parallelism, maximizing the ability of threads to execute concurrently. Please stick closely to the described input and output formats.
Note that the first question uses Java, while the second one required you use OpenMP. A simple example of an OpenMP program is provided to get you started.
1. Game maps can often be represented as 2D polygonal environments. An outer polygon defines the limits 20 of the space, and inner polygons represent obstacles. An organic random tree search can be constructed
on such a map beginning from an initial point (in our case randomly selected, and not within an obstacle).
The tree is then grown by expanding a randomly selected existing tree node, growing an edge out to a
new point. Such growth is possible if the edge connecting the new point to the tree does not intersect an obstacle (or go outside the map bounds). There are various constraints we can impose on how this is done; for this exercise we impose the condition that we only grow tree nodes that have b or fewer edges. The potential new node is chosen randomly within a radius of r from the existing node.
Develop a parallel solution to building such a search tree map using a (fixed size) thread pool. For this you will need to first generate a random game map. This is an area bounded by the unit square, and including 20 obstacles, each of which is a square of size 0.05 × 0.05. Obstacles should be located randomly (strictly) within this area, and it does not matter if they overlap with each other. Choose a random starting point for the tree, and verify it is not contained within any obstacle.
Now, use a pool of p threads to grow the tree in parallel. Seed the pool with a task to grow the initial node. If a task succeeds (growth is performed) a new task is generated for the newly added node. Whether or not the parent node is grown, it may result in a new task as well, if its connectivity still does not exceed b. Once the total number of nodes in the tree reaches n no further growth should be done.
Your program, q1.java, should accept the arguments, p > 0, n > 0, b ≥ 1, and r > 0. (in that order). As output your program should the total number of tasks processed.
Set b to 3 and r = 0.05, and choose an n such that with p = 1 it takes at least 500ms. Time the program (after map creation and excluding I/O), and in a separate document give timing data averaged over several runs for several values of p. What pool size works best? Provide some explanation for your results.
2. A simple representation of floating point numbers can be captured by the regular expression 25 (0|[1-9][0-9]*)\.[0-9]+
This regular expression can be applied efficiently by first converting it into a deterministic finite automa- ton, as so:
1
0.
0-9
.
1-9
0-9
We can then look for the longest match, greedily making transitions as we look at each character in sequence. Once we are unable to make a transition we either have found a floating point number (we are in the state with concentric circles), or the characters considered do not form a legal number.
Suppose you have a large text input, and you want to recognize and extract every legal, non-overlapping floating point value. Doing this kind of matching is normally done sequentially. The task here is to write an OpenMP in C/C++ for doing this with multiple threads.
First, your input string should be created and stored internally as an array prior to creating any threads. The string should then be divided among the threads for matching; each thread must convert any character that would not be be part of a longest match from a sequential search into a space character.
Unfortunately, dividing the work evenly among the threads is insufficient, as the boundary between rec- ognized floating point values may not occur at the boundaries used for thread partitioning. To address this, each thread other than the leftmost must compute speculatively. This works as follows:
Assume we have 1 normal thread, and n optimistic threads. We divide the input string into n + 1 pieces. The normal thread gets the first piece of the string, and performs normal matching.
The n optimistic threads each apply the regular expression to their own portion of the string, but since they are not sure what state the DFA should be in to start with, they simulate matching starting from every possible state simultaneously. For instance, in the above example, an optimistic thread would consider the processing of its fragment to start in any of the 5 states, and thus cannot be sure of how many characters match until it knows the initial state. Of course if/when all 5 possibilities converge, it may start normal, sequential recognition.
Once the normal thread reaches the end of its input fragment i, the thread handling the next fragment i+1 will know the starting state it should’ve started in, and can thus complete its recognition. This repeats until the matching process is completed for the entire string.
Implement and test this design in OpenMP on top of C/C++. Hard-code the example DFA shown above and include a function that generates a string consisting of randomly, characters uniformly chosen from the set {0,1,2,3,4,5,6,7,8,9,.,a}. Print out the string twice (separated by a newline): first before doing any processing, and second after all unrecognized characters have been blanked. The string should be long enough that your 1-threaded simulation runs for at least 500ms (not including I/O or string construc- tion).
Your simulation should accept a command-line parameter for controlling the number of optimistic threads. Time the matching (post-construction and non-I/O) part and run your test several times. Show timing data for 0–7 optimistic threads and explain your results in relation to the number of processors in your test hardware. Your solution must demonstrate speedup for some non-0 number of optimistic threads!
What to hand in
Submit your assignment to MyCourses. Note that clock accuracy varies, and late assignments will not be accepted without a medical note: do not wait until the last minute. Assignments must be submitted on the
2
0-9
due date before 6pm.
Where possible hand in only source code files containing code you write. Do not submit compiled binaries or .class files. For any written answer questions, submit either an ASCII text document or a .pdf file with all fonts embedded. Do not submit .doc or .docx files. Images (plots or scans) are acceptable in all common graphic file formats.
Note that for written answers you must show all intermediate work to receive full marks.
This assignment is worth 10% of your final grade.
45
3