Parallel Computing Fundamentals: Models and Concepts
Core Concepts in Parallel Computing
This section addresses fundamental questions regarding parallel systems, architectures, and performance metrics.
Parallel System Components and Models
Which component is not typically considered a fundamental component of a parallel computation system?
Answer: A parallel random-access machine (PRAM) model. (PRAM is a theoretical model, not a physical component.)
Which parallel programming model requires message passing for communication between processes?
Answer: Distributed Memory.
Which of the following is not a standard parallel programming model?
Answer: Domain. (Domain decomposition is a technique, not a model.)
Which computer hardware component does not represent a multiple functional unit?
Answer: Main memory.
Which computing pioneer established the requirements for SISD (Single Instruction, Single Data) computer architectures?
Answer: John von Neumann.
A Beowulf cluster represents what type of parallel computer?
Answer: Network of Workstations (NOW).
Performance and Speedup Metrics
What is the expression used to compute observed speedup ($S_p$)?
Answer: $S_p = \frac{\text{Time}_{\text{Sequential}}}{\text{Time}_{\text{Parallel}}}$
Which statement is true regarding theoretical speedup in parallel computing?
Answer: Theoretical speedup is equivalent to the number of processors used for computation (assuming perfect parallelization).
Which of the following represents a speedup that is not attainable in standard theoretical models?
Answer: Superlinear. (Linear speedup is the ideal maximum.)
According to Amdahl’s law, what percentage of a sequential program must be parallelizable to approach a theoretical maximum speedup of 4, regardless of the number of processors used?
Answer: 75%.
True or False: Amdahl’s law implies that it is better to affect a smaller improvement on the portion of the program that represents the greatest amount of overall sequential execution.
Answer: False. (Amdahl’s law emphasizes improving the sequential bottleneck.)
Architecture and Taxonomy
What two dimensions define Flynn’s Taxonomy?
Answer: Instruction Stream and Data Stream.
Which Flynn’s Taxonomy classification has no widespread real-world implementation?
Answer: MISD (Multiple Instruction, Single Data).
Which statement is not true of MIMD (Multiple Instruction, Multiple Data) parallel computer architectures?
Answer: All processors execute their respective programs using the same data. (In MIMD, data streams are typically different.)
Which of the following represents a MIMD computer architecture?
Answer: Hypercubes.
Which memory strategy is commonly used by modern supercomputers?
Answer: Hybrid Distributed-Shared Memory.
True or False: Multiprocessor computers are essentially multiple von Neumann computers.
Answer: False.
True or False: Distributed computer architectures are essentially parallel computer architectures.
Answer: False. (While parallel, they are often loosely coupled.)
Programming and Granularity
Which statement is not true about parallel computing?
Answer: The individual parts of a program are executed in order sequentially. (This describes sequential computing.)
Which sentence describes the concept of embarrassingly parallel?
Answer: A computational task that can be divided into independent subtasks, allowing them to be executed simultaneously without the need for communication or coordination between the processes.
Which term describes the decomposition of a problem into a large number of small tasks?
Answer: Fine-grained parallelism/granularity.
The number of tasks into which a programming problem can be decomposed is referred to as what?
Answer: Granularity.
True or False: The Threads parallel programming model is a type of shared memory parallel programming model.
Answer: True.
Which of the following is not a reason for computational scientists to use parallel programming?
Answer: They are simpler to implement than sequential programming techniques. (Parallel programming is generally more complex.)
What type of graph should be created first when developing a parallel algorithm?
Answer: Task Dependency Graph.
Miscellaneous Facts
One (1) ExaFlop is equivalent to one thousand (1000) what?
Answer: PetaFlops.
Which statement is not true regarding the Parallel Random-Access Machine (PRAM) model?
Answer: The PRAM model eliminates the need for critical section synchronization. (Synchronization is often required depending on the PRAM variant.)
What data does the first line of the file marblesRGBA.txt typically contain?
Answer: Two integer numbers representing the width and height of the image in pixels.
Which industry would benefit most from parallel computing?
Answer: All industries will benefit from using parallel computations.