CSC352 Lecture 6

From CSclasswiki
Jump to: navigation, search

Lecture 6 on Thursday, February18th. Notes transcribed by Yang Li.

Python Q&A

  • Q: How to extract a few words before and a few words after a keyword in a line of text?

A: Given a string variable text and the keyword "love". Suppose we want to find all words that are 50 characters away from the first occurrence of "love". Let variable index be the index of the letter "l" in the first occurrence of "love". To avoid starting or ending in the middle of a word, we can use the following 1-line code:

" ".join(text[index-50:index+50].split()[1:-1])

Amdahl's Law

The problem

The following figure shows the execution timeline of a program.

  • parallel part (P): fragment of code that can run in parallel (e.g. loops )
  • serieal part (S): fragment of code that has to be done sequentially (e.g. I/O, beginning and end of a program)


Suppose we have a program with a serial section and a parallel segment. If we increases the number of processors, we expect total execution time to reduce consequentially. TimelineCompare.png

The speed up of using n processors is

S(N) = T(1)/T(2) = (S+P)/(S+P/N) --> (S+P)/S as N->Infinity

Suppose your program have 1% serial time and 99% parallel time, the speed up of using N processors is at most

S(N) = (1+99)/1 = 100

This demonstrates the Amdahl's Law: the proportion of serial code in a parallel program will limit the speed-up of using multiple processors.

Ways around Amdahl's Law

  • Increase the number of processors reduces the running time of serial portion of a program

i.e. More processors => more hardware => more memory => more caching => less serial time

  • Parallel processing reduce the complexity of algorithms, thus shorten the running time on the serial section

N-queens example: Suppose the complexity of our N-queen algorithm is O(n^3) in the serial case (n is length of the board). In the parallel case, if we use n processors, then the complexity is reduced to O(n^3)/n = O(n^2), which is one order of magnitude less.

In practice, parallel computing often reduce the complexity more than the factor of n. (See Gustafson-Barsis Law)

  • Today's applications have 0% serial code.

How to Read Technical Papers


Deadlock refers to the condition that the processors are unable unable to continue execution because of interlocked resources.

Two types of deadlocks

Circular lock

The following situation is considered a circular lock:

  1. 4 resources are shared between 4 processes.
  2. All processors acquire the resource next to it counter clockwise => all resources are locked
  3. All processors attempt to acquire the resource next to it clockwise =>all processors wait


Buffer lock

When two processors attempt to modify the same hash table. The following situation may occur:


Rules for avoiding deadlocks

  • Use timeout
  • If several locks are needed for a data structure, try acquire all of them at the same time.

If not successful, release all of them.