Parallel Algorithms

Exam 1

What does Moore’s law say

Processing speed should double every 18 months

Is Moores law true

No, it failed around the 2000’s mark

What are the 5 reasons computing used to get faster

Smaller, better algorithms, wider busses, fewer bridges, more efficient manufacturing

What changed about the algorithms that allowed them to improe

Refined algorithmic ideas and leveraging of existing hardware

What were some of the algorithmic refinements done to improve them

Approximation, randomization, ammortization

How do we improve computing time now

More processors

What is blocking in MPI

Assining each process in a contigous chunk of data, reducing communication but risking load imbalances

What is striping in MPI

Assigning data in a round robin pattern across the processes to improve load balance at the cost of higher communication

What does MPI stand for

Message passing interface

What are the benefits of using striping over blocking

It is easier to handle different sized tasks easily in code and it might be more fair for the processors to compute

What are the cons of using striping over blocking

It is slower due to higher communication and the loss of data locality

What is the shared memory model

this is an approach where multiple processes can directly access an common region of memory on the same node. This model allows data to be exchanged through shared variables instead of message passing

What are the pros of the shared memory model

There is no data transfer

What are the cons of the shared memory model

It does not work well for complex algorithms, expensive, locality issues and instates a locking mechanism for the data

What is the distributed memory model

A parallel computing approach where each process has its own private memory space and data is only transferred through explicit message passing

What are the pros of a distributed memory model

You are able to use computers everywhere

What are the cons of the distributed memory model

Data transfer overload

What does PRAM model stand for

Parallel random access memory

What type of memory does the PRAM model use

Shared memory system

What are the four categories of PRAM

EREW, CREW, ERCW, CRCW

What are the four ways to deal with CW

Arbitrary, Priority, Common, and Majority

What happens in an Arbitrary CW

A random process wins the right to write

What happens in a Priority CW

A programmer assigns a priority list in advance for which processors should get the right to write first

What happens in a Common CW

Only allows a writes when all processors agree on what to write

What happens in a Majority CW

Only let a processor write if that is the majority value to write

What kind of model do we use when writing out code using MPI

Distributed Memory Model

What are the drawbacks of the PRAM model

This model does not help illuminate the dependence of the algorithm on the processeors. In essence, it does not show how much faster or slower a program would get given a different number of processors. Also writing all that code is tedous

What is the point of the Work-Depth mdoel

To count how many concurrent rounds are needed to solve the problem, rather than focusing on the time in each round

What is the relationship of T(n) to W(n)

T(n) >= (W(n))/p

What does W(n) represent

The optimal required work

What is a reduction

Translates a problem into another problem