CSC352 Lecture 6
Lecture 6 on Thursday, February18th. Notes transcribed by Yang Li.
- 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:
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)
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
- Hand out
- Sample reading: You, Too, Can Soon Be Like Tom Cruise in ‘Minority Report’
Deadlock refers to the condition that the processors are unable unable to continue execution because of interlocked resources.
Two types of deadlocks
The following situation is considered a circular lock:
- 4 resources are shared between 4 processes.
- All processors acquire the resource next to it counter clockwise => all resources are locked
- All processors attempt to acquire the resource next to it clockwise =>all processors wait
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.