perf_basic.txt

What is the best known worst case sequential complexity for searching in an ordered array ?;\(\Theta (log n)\);performance objectives complexity
What is the best known worst case sequential complexity for matrix-vector multiplication ?;\(O (n^2)\);performance objectives complexity
What is the best known worst case sequential complexity for matrix-matrix multiplication ?;\(O (n^3)\);performance objectives complexity
What is the best known worst case sequential complexity for comparison-based sorting ?;\(\Theta (n\ log\ n)\);performance objectives complexity
What is the best known worst case sequential complexity for maximum finding in an unordered sequence (or sum of elements in array, all prefix-sums in an array) ?;\(\Theta (n)\);performance objectives complexity
What is the best known worst case sequential complexity for merging two ordered sequences of length n and m (or graph search (DFS, BFS)) ?;\(O (n\ log\ n + m)\);performance objectives complexity
The absolute speed-up of a parallel algorithm Par over a sequential algorithm Seq is defined as:;The ratio of sequential to parallel runnning time \[S_p(n)=\frac{T_{\text{seq}}(n)}{T_{\text{par}}(p,n)}\] with input size \(O(n)\) and p processor-cores.;performance objectives absolute speed-up
The best possible parallel algorithm Par for the problem solved by sequential algorithm Seq cannot run faster than:;\(T_{\text{seq}}(n) / p\);performance objectives speed-up
Is it sensible to always use all processor-cores available for every parallel algorithm Par?;No, putting in more processor-cores than there is actual work to be done makes no sense, and some processors would sit idle.;performance objectives speed-up processor-cores
\(\textbf{Work-optimal}\) algorithms that are not \(\textbf{cost-optimal}\) can have linear speed-up. Explain how:;Construct a better, cost-optimal algorithm (optimize) with the same amount of work that runs on fewer processor-cores. (Too many processors were used, some of which idled for too long.);performance objectives optimal speed-up linear cost work
The relative speed-up of a parallel algorithm Par is defined as:;The ratio of the parallel running time with one processor-core to the parallel running time with p processor-cores. \[SRel_p(n) = \frac{T_{\text{par}}(1,n)}{T_{\text{par}}(p,n)}\];performance objectives speed-up relative processor-cores
Name three factors that could cause overhead at a parallel algorithm:;<ul><li>communication and coordination</li><li>synchronization</li><li>algorithmic overheads (extra or redundant work compared to a sequential algorithm)</li></ul>;performance objectives overhead
A parallel computation in which communication and synchronization occurs rarely is called:;coarse grained;performance objectives granularity synchronization
A parallel computation in which communication and synchronization occurs frequently is called:;fine grained;performance objectives granularity synchronization
Name the two sub-categories of static load balancing and briefly explain them:;<ul><li>oblivious, static load-balancing (the problem can be divided over the processors based on the input size and structure alone, but regardless of the actual input)</li><li>adaptive, problem-dependent, static load-balancing (the input itself is needed to divide the work, and some preprocessing may be required)</li></ul>;performance objectives load-balancing work
Typical victims of Amdahl's Law are:;<ul><li>Input/output (For linear work algorithms, reading the input and writing the output will take \(\Omega (n)\), and thus be a constant fraction of \(O(n)\)</li><li>Sequential preprocessing</li><li>Maintaining sequential data structures (in particular sequential initialization)</li><li>Hard-to-parallelize parts (that are done sequentially)</li><li>Long chains of dependent operations (not necessarily at the same processor-core)</li></ul>;performance objectives parallelizable
Amdahl's Law says that the parallelized algorithm Par can achieve a maximum speed-up over Seq of:;\(\frac{1}{s} \text{ for } p \rightarrow \infty\) where s is a strictly sequential fraction \(0 < s \le 1\), independent of n, that cannot be parallelized at all, and \(r = 1 - s\) that can be perfectly parallelized;performance objectives Amdahl speed-up
In a good parallel algorithm, not falling victim to Amdahl’s Law, the sequential part s(n) will:;not be a constant fraction of the total work, but depend on, and decrease with n. (Amdahl’s Law does not apply. A good speed-up can be achieved with large enough inputs.);performance objectives Amdahl speed-up
The efficiency \(E_p(n)\) of Par compared to Seq is defined as (formula):;\[E_p(n) = \frac{T_{\text{seq} }(n)}{p*T_{\text{par} }(p,n)} = \frac{S_p(n)}{p}\];performance objectives efficiency
If an algorithm does not have constant efficiency (and speed-up independent of n), we can aim to maintain some desired, constant e efficiency by:;instead increasing the problem size n with the number of processors p. (This is the notion of iso-efficiency.);performance objectives efficiency speed-up
(2) A parallel algorithm Par is said to be weakly scaling relative to sequential algorithm Seq if by:;keeping the average work per processor \(T_{\text{seq} }(n) / p\) constant at w, the running time of the parallel algorithm \(T_{\text{par} }(p,n)\) remains constant. (The input size scaling function is \(g(p) = T_{\text{seq} }^{-1}(pw)\).);performance objectives weakly_scaling speed-up
(1) A parallel algorithm Par is said to be weakly scaling relative to sequential algorithm Seq if for a:;desired, constant efficiency e there is a slowly growing function \(f(p)\) such that the efficiency is \(E_p(n) = e\) for n in \(\Omega (f(p))\). (The function \(f(p)\) is called the iso-efficiency function.);performance objectives weakly_scaling speed-up
How is the growth of the iso-efficiency function \(f(p)\) compaired to the input size scaling function \(g(p)\)?;\[f(p) \text{ should be } O(g(p))\];performance objectives iso-efficiency efficiency
When is a algorithm strongly scalable?;If the parallel time decreases proportionally to p (linear speed-up), while keeping n constant.;performance objectives strongly_scaling speed-up
When is a algorithm weakly scalable?;If the parallel running time remains constant, while keeping the average work per processor constant and increasing n.;performance objectives weakly_scaling speed-up