Concurrent Programming

Concurrent Programming

COMP 409, Fall 2014

Assignment 3

Due date: Wednesday, November 12, 2014

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 programs should include demonstrative, but not excessive, output.

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.

1. In this question you will need to evaluate and tune the performance of a lock-free stack.

First, implement a lock-free stack. Your stack needs to support two operations, PUSH and POP. Your 25

stack must be capable of reusing nodes/data (re-PUSH-ing after POP-ing), and it should not be possible to

lose data or otherwise corrupt the stack.

Next, implement an elimination stack based on an elimination array, as described in the textbook. It

should resort to your lock-free stack implementation if an exchange fails. The size of the elimination

array and the timeout used to wait for an elimination partner should be parameters.

Stacks are tested by starting p threads that then repeatedly perform PUSH or POP operations on the stack,

randomly choosing one operation or the other with equal probability. A thread should retain the last 10

items it popped, and when performing a PUSH, 50% of the time it should randomly select a previously

popped node to re-push (if it has any). After each push/pop operation, a thread sleeps for a random time

between 0ms and dms. Each thread should also keep track of how many pushes it does and how many

pops successfully returned actual data.

Your program should be invoked with 5 integer arguments as:

java EliminationStack p d n t e

Where p > 1 represents the number of threads to use, d > 0 represents the upper bound for the random

delay between each thread operation, n the total number of operations each thread attempts to do, t ≥ 0 represents the timeout factor used in the elimination stack, and e > 0 is the size of the elimination array.

All times are in milliseconds. Choose an n > 1000 and a relatively brief d, such that execution takes at

least several seconds for t = 0.

As output, your program should (single-threadedly) emit a time in milliseconds measuring the entire

concurrent simulation on one line. A second line of output contains three numbers separated by spaces:

the first value should be the total number of pushes done by all threads, and the second should be the

total number of successful pops done by all threads, and the third the total number of number of nodes

remaining in the stack.

For each of p ∈ 2, 4, 8, 16 what values/combination(s) of e and t usually works best? Note that you do not need to test all combinations(!), but you do need to provide a clear, numerical justification for

your answer, including performance graph(s) as appropriate, and your textual argument/explanation (as

a separate file).

2. In order to match a regular expression (RE), it may first be converted into a deterministic finite automaton 25

(DFA). Matching the RE to an input string is then a matter of processing each character of the input string,

making state transitions according to the character. If the DFA is at an accept state once at the end of the

string is reached, then the RE matched.

1

For example, the regular expression ˆ(a+b+(c|d)+)+$ can be represented by the following automa-

ton, assuming a string alphabet of {a, b, c, d}.

The matching process is inherently sequential, since we need to process the string one character at a time.

It may be parallelized, however, through the use of an optimistic approach.

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 matching as above.

The n optimistic threads each perform matching on their own portion of the string, but since they are

not sure what state the DFA will be in to start with, they simulate matching from every possible state

simultaneously. For instance, in the above example, an optimistic thread would be checking its fragment

4 times, assuming it started in state 0, 1, 2, or 3 (you do not really need to model starting in the reject

state, as reject has no transitions out). In effect, each optimistic thread computes a mapping from each

possible state of the DFA to the resulting state for the associated input fragment. Note that this means

the optimistic threads might do more work than the normal thread, even on the same size input string

fragment.

Once the normal thread reaches the end of its input fragment i, it looks at the mapping produced by the

thread handling the next fragment i + 1. It knows the the ending state of i in the DFA, and so can use the

optimistic map to compute the resulting ending DFA state of the i + 1 fragment. 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 (you do not need to do any RE→DFA conversion), and include a function that generates a (very long) string that would match; an example code fragment is provided. Your simulation should accept a

command-line parameter for controlling the number of optimistic threads, and should run your test 10

times, timing the total matching time (excluding the string construction time). Show data for 0–3 op-

timistic 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

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. 50

2