3-2 Parallel Computing, Models and their Performance

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/23

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

24 Terms

1
New cards

Bernsteins Conditions

Let P1 be Process 1 and P2 be Process 2

P1 || P2 if and only if all the all variables, registers and memory locations used by both processes are independent of each other

<p>Let P1 be Process 1 and P2 be Process 2</p><p>P1 || P2 if and only if all the all variables, registers and memory locations used by both processes are independent of each other</p><p></p>
2
New cards

Three Limits to Parallelism and Definitions:

Data Dependencies: one instruction needs the results of a previous instruction as input

Flow Dependencies: the outcome of a subsequent operation is directly affected by the result of a prior operation in the instruction sequence

Resource Dependencies: when two instructions or processes need the same hardware resources (such as memory) to execute

3
New cards

Three Data Dependencies and Definitions

Flow Dependency (RAW): a variable assigned in a statement is used in a later statement

Anti-dependency (WAR): a variable used in a statement is assigned in a subsequent statement

Output Dependency (WAW): a variable assigned in a statement is subsequently re-assigned

<p>Flow Dependency (RAW): a variable assigned in a statement is used in a later statement</p><p>Anti-dependency (WAR): a variable used in a statement is assigned in a subsequent statement</p><p>Output Dependency (WAW): a variable assigned in a statement is subsequently re-assigned</p>
4
New cards

Two Flow Dependencies and Definitions

Data Dependency: one instruction needs the results of a previous instruction as input

Control Dependency: one execution of an instruction depends on the result of a previous condition or decision point in the progam flow.

<p>Data Dependency: one instruction needs the results of a previous instruction as input</p><p>Control Dependency: one execution of an instruction depends on the result of a previous condition or decision point in the progam flow.</p>
5
New cards

Example of Resource Dependency

knowt flashcard image
6
New cards

Four Types of Flynn’s Taxonomy

SISD - single instruction, single data

ex: single core processors

SIMD - single instruction, multiple data

ex: GPUs

MISD - multiple instruction, single data

MIMD - multiple instruction, multiple data

ex: multi-core processor, supercomputers

7
New cards

Define Parallel Runtime

the time that elapses from the moment that a parallel computation starts to the moment that the last processor finishes execution

8
New cards

Define Seriel Runtime

the time that elapses from the moment the parallel computation starts to the moment that that the processor finishes execution (assuming the computation is being done on a single processor)

9
New cards

Define Speedup and Give Formula

the ratio of the serial runtime of the best sequential algorithm for solving a problem to the time taken by the parallel algorithm to solve the same problem on p processors

<p>the ratio of the serial runtime of the best sequential algorithm for solving a problem to the time taken by the parallel algorithm to solve the same problem on p processors</p>
10
New cards

What kind of speedup is desired?

knowt flashcard image
11
New cards

Define Efficiency and Give Formula

the ratio of speedup to the number of processors, measures the fraction of time for which a processor is usefully utilized

* perfect speedup means 100% efficiency

<p>the ratio of speedup to the number of processors, measures the fraction of time for which a processor is usefully utilized</p><p>* perfect speedup means 100% efficiency</p><p></p>
12
New cards

Define Cost and Give Formula

the product of runtime and the number of processors

13
New cards

Define Scalability

a measure of a parallel system’s capacity to increase speedup in porportion to the number of processors

14
New cards

Define Amdahl Law and Give Formula

provides a theoretical limit to the speedup that can be achieved with a parallel processing system

<p>provides a theoretical limit to the speedup that can be achieved with a parallel processing system</p>
15
New cards

Define Gustafson’s Law and Give Formula

in a parallel program the quantity of data to be processed increase, so compared with the parallel part the sequential part decreases

*less constraints than the Amdahl law

<p>in a parallel program the quantity of data to be processed increase, so compared with the parallel part the sequential part decreases</p><p>*less constraints than the Amdahl law</p><p></p>
16
New cards

Limitation of Amdahl and Gustafson Laws

define the limits without taking in account the properties of the computer

17
New cards

Define the three components of Bulk Synchronous Parallel (BSP)

Compute: components capable of computing or executing local memory transactions

Communication: a network routing messages between components

Synchronization: a support for synchronization on all or a sub-group of components

*each processor can access his own memory without overhead and have a uniform slow access to remote memory

18
New cards

Define Supersteps and Give Three Steps

a superstep is a sequence of operations that every processing unit in a distributed system executes as a part of a larger algorithm

applications are composed by supersteps separated by global synchronizations

Communication Step, Communication Step, Synchronization Step

19
New cards

Give Formula of Superstep

knowt flashcard image
20
New cards

Define LogP Model and List it Four Components

a more realistic model in comparison to BSP with paying attention to realistic characteristics of parallel networks

L: latency of.communication

o: message overhead

g: gap between messages

P: number of processors

21
New cards

Define the Four Elements of the LogP Model

Latency: small message across the network

Overhead: lost time in communication

Gap: between two consecutive messages

P: the number of processors

22
New cards

Give Formula for LopP Superstep

Note: the total time for a message to go from processor A to processor B is L + 2 * o

<p>Note: the total time for a message to go from processor A to processor B is L + 2 * o</p>
23
New cards

Define the CMM Model

transforms the BSP superstep framework to support high-level programming models

removes the requirement of global synchronization between supersteps, but combines the message exchanges and synchronization properties into the execution of a collective communication

24
New cards

Define Laplace’s Equation

knowt flashcard image