CS247 Lecture 23

I skipped this class, will update the notes. This lecture is not on the final.

• Last Time: Exception Safety
• This Time: Multithreading

This isa topic discussed in SE350, CS343.

Thread: A sequence of instructions to be executed. Typically: just the program.

Most CPUs in the modern day have more than one core.

This can sometimes allow extraction of extra efficiency.

Example: Matrix Multiplication

Typically, compute entries in order: $\overrightarrow{v_1}\times \overrightarrow{x_1,}\overrightarrow{v_2,}\times \vec{x}$

In a multithreaded program: Create separate threads to perform the computations simultaneously.

void multiplyRow(int row, const vector<vector<int>>& A, const vector<int>& x, vector<int>& output) {
	output[row] = 0;
	for (int i=0;i<A[row].size();i++) {
		output[row] += x[i] . A[row][i];
	}
}

This allows us to multiply each row for our product $A\vec{x}$.

vector<vector<int>> A {{1,2,3}, {4,5,6}, {7,8,9}};
vector<int> x {10,11,12};
vector<int> y{0,0,0};
 
vector<thread*> threads;
 
for (int i=0;i<A.size();i++) {
	threads.push_back(new thread{multiplyRow, i, std::cref(A), std::cref(x), stdd::ref(y)})
}
for (thread* t: threads) {
	t->join(); // waits, stalls the program until t has finished running.
	delete t;
}
// by this point, all threads have completed - we can now use y

Why do we need ref/cref, the thread constructor implicitly copies / moves its parameters.

cref, ref: create reference-wrapper object types, which can be copies / moved.

• distributed the workload. Each thread works independently on a separate part of the problem.

This is an example of an “embarrassingly parallelizable” problem.

What about synchronization? $A^2\vec{x}$. First: Compute $A\vec{x}=\vec{y}$. Then compute $A\vec{y}\to$ gives us $A^2\vec{x}$.

We need to compute $\vec{y}$ in entirety, before we may compute $A\vec{y}$.

Simply:

• Spawn threads for $A\vec{x}=\vec{y}$, join them.
• Spawn new threads for $A\vec{y}$, join them.

But: creating threads is expensive. What if we reuse the same threads?

Let’s do a barrier example: 2 functions -f1 and -f2: both must complete phase 1, then they can proceed to phase 2.

bool t1Ready = false, t2Ready = false;
void f1() {
	cout << "Thread 1 Phase 1" << endl;
	t1Ready = true;
	while (!t2Ready) {}
	cout << "Thread 1 Phase 2" << endl;
}
 
void  f2() {
	cout << "Thread2 Phase 1" << endl;
	t2Ready = true;
	while (!t1Ready) {}
	cout << "Thread 2 Phase 2" << endl;
}

Why are the outputs different?

You should run this yourself, sometimes the output will be differing. This is because << is actually a function call. Since the threads run simultaneously, you actually don’t have the guarantee that an entire line runs alone and prints together (because there are actually two function calls in that single line).

Is there a solution? Yes, use \n instead of endl.

Use std::atomic<bool> to prevent incorrect compiler optimizations with multithreaded code.

Conclusion, what was CS247 about?

This is not actually a course about C++. Purpose?

High-level Thinking:

1. How well do my programs accommodate changes?
2. How do I balance simplicity vs. abstraction?
3. Where is abstraction useful, and where it is cumbersome?

Low-level Thinking?

1. What is the compiler doing?
2. What are the efficiency tradeoffs in abstractions.
3. Do I have a clear understanding of what my language compiles.

Learning more program paradigms in detail will make you a better programmer.

THE END.

$\square$