-A A +A

CS2013-Ironman-PD-Parallel and Distributed Computing

Primary tabs

5 posts / 0 new
Last post
CS2013-Ironman-PD-Parallel and Distributed Computing
PDF icon CS2013-Ironman-v1.0-PD.pdf259.86 KB

Forum to comment on "PD-Parallel and Distributed Computing" Knowledge Area in the CS2013 Ironman report. We ask that comments related to specific text in the report please specify the line number(s) of the text being commented on. Line numbers are provided on the far left-hand side of the each page.

Comment for KA PD
Your rating: None

It can be recommended the Knowledge Unit (KU) “Parallel Algorithms, Analysis, and Programming” to split into two KUs (1) “Parallel Algorithms” and (2) “Parallel Programming”

PD/Parallelism Fundamentals
p. 124 add after the line 80 “ Needs of synchronization”
p. 124 add after the line 80 “ Possible non-deterministic execution of parallel programs”
p. 124 add after the line 84 “ Overview of reasons of reducing parallel computation efficiency
- Lockstep synchronization
- Excess synchronization (serialization)
- Workload unbalancing
- High communication intensity”

PD/Parallel Decomposition
p. 124 add after the line 107 “ Domain based (geometric) decomposition”

PD/Communication and Coordination
p. 125 add after the line 129 “- Basic communication operations (multicast, accumulation, all-to-all, etc,)”
Item “Mutual Exclusion” should be moved in the Section [Core-Tier1] after line 125.

PD/Parallel Algorithms, Analysis, and Programming
p. 126 the line 178 – I think that item “speed-up” should belong to Core-Tier 1.
p. 126 the line 178 should be spitted into two lines
“Speed-up (superlinear, linear, max possible speed up for a given problem, speed-up of a given parallel algorithm)
 Scalability and isoefficiency”
p. 126 add after the line 178 “ Redundancy”
p. 126 add in the line 180 “master-workers”
p. 126 add after the line 185 “ Parallel matrix computation”
p. 126 add after the line 186 “ Classic illustrative parallel problems (readers-writers, dining philosophers, sleeping barbarian, etc.)”
p.126 add after the line 186 “ Tools for development of parallel programs (”IDE, compilers, debuggers, parallel errors detectors, performance analyzers, libraries, etc)”
p. 127 add after the line 193 “Explain how calculate the performance of a sequential algorithm for evaluating speed-up of parallel computation (performance of sequential analog, performance of parallel algorithm execution on single processor, or performance of the best sequential algorithm of a given problem)”

PD/Parallel Architecture
p. 127 replace the line 215 “ Multicore and manycore processors”
p. 127 add after the line 215
“ Multiprocessors
 Multicomputers”
p. 127 add in the line 224 “Structure of MIMD class”
p. 127 the line 229 - I think that item “NUMA” should belong to Core-Tier 1.
p.127 add after the line 233 “ List Top500 of the most powerful supercomputers”

PD/Parallel Performance
p. 128 add after the line 252 “ Evaluation of communication overheads”

PD/Distributed Systems
p. 129 the line 277 – I think the term “wide guarantees” is not widely used. Can it be reformulated?

PD/Cloud Computing
PD/Formal Models and Semantics
p. 130 add after the line 349
“ Formal models for information dependencies analysis
 Equivalent transformation of parallel programs ”

Comments addressed in Ironman v1.0
Your rating: None

The comments above were reviewed and addressed in the Ironman v1.0 version of this knowledge area (which is now posted in this discussion forum).

Definition for speedup, P-complete algorithms, and graphs
Your rating: None

Line 33

There are a number of high-level definitions, but not for speedup (which is to me, the most important reason to consider parallel implementations). I would suggest adding the following:

* Speedup: the ratio of wall-time of the best possible serial implementation, to that of a parallel implementation completing the same task. The best possible serial implementation may be different than the parallel implementation running on a single processor.

My motivation for this suggestion is to reduce the frequency with which highly-scalable methods are mistaken for high performance. Many of the issues noted in Bailey's early "twelve ways" paper still occur, and being careful in the curriculum should help this situation.

Line 181

I would suggest adding consideration of non-scalable (P-complete) algorithms, as a contrast with embarassingly parallel algorithms. It would make sense to do this within the context of computational complexity; one can find a scalable parallel algorithm for nearly any task, but not necessarily an efficient scalable algorithm. This might be addressed by properly framing the discussion on parallel shortest path algorithms (see my comments below on Line 186).


Line 186

WRT parallel shortest path algorithms, I would like the curriculum to be very clear. To my knowledge, there are no scalable parallel shortest path algorithms that are competitive with Dijkstra's algorithm. While the Bellman-Ford algorithm is scalable, it has higher computational complexity than Dijkstra, and is thus slower for any meaningful problem. There are many places in the open literature where authors have mistaken the high scalability of B-F for high performance, leading to completely incorrect conclusions. The errors are not just at the margins of the computing field -- they occur in some of the most competitive venues available.

If the intention of Line 186 is to include discussion of something like the delta-stepping algorithm, it should be made clear that the scalability applies to only a restricted set of graph types (and not things like road maps, or other graphs one might encounter).

I would like parallel shortest path algorithms to be covered -- but as a cautionary tale, not as a recommended practice.

Your rating: None

Thank you for the comments on the PD knowledge area of CS2013. After discussion with the subcommittee on the PD area, here is our response.

* With regard to the definition of "speed-up", we do believe that's an important concept, but that's not something we'd define in the preamble of the PD section. It is a Core topic listed under the Parallel Algorithms, Analysis, and Programming subarea that we'd expect would be covered by an instructor. Our other definitions in the PD preamble are there to clarify for readers/instructors how we are using these terms in our document (not that we would expect all instructors to use these terms in the same way in their courses, since there is some discussion of these terms in the community).

* With regard to non-scalable algorithms, we have added "Examples of non-scalable parallel algorithms" as an elective topic in the section Parallel Algorithms, Analysis, and Programming. Thank you for the suggestion.

* With regard to the specific comment on parallel shortest path algorithms, we believe that this is subsumed by the new topic added above (as described in the previous bullet point) and it is in the purview of the instructor to determine exactly which non-scalable algorithms they would like to cover and in what way.

Log in or register to post comments