L2 - Concurrent Systems Parallelism

Sequential Processing

– They have one “thread” of execution

– One step follows another in sequence

– One processor is all that is needed to run the algorithm

sequential

All of the algorithms we’ve seen so far are ___________

one “thread”

algorithm have __________ of execution

one processor

How many processor is needed to run the algorithm?

Non-sequential

The burglar alarm is watching all of these “at once” (at the same time).

Concurrent Systems

Multiple tasks can be executed at the same time

Concurrent Systems

The tasks may be duplicates of each other, or distinct tasks

Concurrent Systems

The overall time to perform the series of tasks is reduced

true

tru or false? Concurrent processes can reduce duplication in code

runtime

The overall _______ of the algorithm can be significantly reduced.

Redundancy

can make systems more reliable.

false

tru or false? Runtime is always reduced, so careful planning is required

multiprocessor machines

Many computers today have more than one processor

Time slicing

allows many users to get CPU resources

true

tru or false? Concurrency can also be achieved on a computer with only one processor

false

tru or false? Tasks won’t be suspended while they wait for something, such as device I/O

Concurrency

is the execution of multiple tasks at the same time, regardless of the number of processors.

Parallelism

is the execution of multiple processors on the same task.

• Multiprogramming

• Multiprocessing

• Multitasking

• Distributed Systems

Types of Concurrent Systems

Multiprogramming

Share a single CPU among many users or tasks

Multiprogramming

May have a time-shared algorithm or a priority algorithm for determining which task to run next

Multiprogramming

Give the illusion of simultaneous processing through rapid swapping of tasks (interleaving).

Achieving Concurrency

Multiprogramming

Multiprocessing

Executes multiple tasks at the same time

Multiprocessing

Uses multiple processors to accomplish the tasks

shared memory

Multiprocessing has a ______ that is used by all the tasks

Multiprocessing

Multitasking

A single user can have multiple tasks running at the same time.

Multitasking

Can be done with one or more processors.

Multitasking

Used to be rare and for only expensive multiprocessing systems, but now most modern operating systems can do it

Multitasking

Distributed Systems

Multiple computers working together with no central program “in charge.”

Distributed Systems

Advantages of Distributed Systems

• No bottlenecks from sharing processors

• No central point of failure

• Processing can be localized for efficiency

Disadvantages of Distributed Systems

• Complexity

• Communication overhead

• Distributed control

Parallelism

Using multiple processors to solve a single task.

Parallelism

– Breaking the task into meaningful pieces

– Doing the work on many processors

– Coordinating and putting the pieces back together.

Parallelism

Pipeline Processing

Repeating a sequence of operations or pieces of a task.

pipeline

Allocating each piece to a separate processor and chaining them together produces a ________, completing tasks faster.

One Load

Three Loads

Pipelined task

3 & 4

which time is the busiest?

Task Queues

A supervisor processor maintains a queue of tasks to be performed in shared memory.

dequeues

Each processor queries the queue, _________ the next task and performs it

Parallel Bubblesort

We can use N/2 processors to do all the comparisons at once, “flopping” the pair-wise comparisons.

87 93 65 74 45 57 27 33

what’s next?

93 87 | 74 65 | 57 45 | 33 27

87 65 93 45 74 27 57 33

what’s next?

87 | 93 65 | 74 45 | 57 27 | 33

65 87 45 93 27 74 33 57

what’s next?

87 65 | 93 45 | 74 27 | 57 33

N² time

Sequential bubblesort finishes in

N time

Parallel bubblesort finishes in

O(N²)

Thus, the amount of work is still

Product complexity

is the amount of work per “time chunk” multiplied by the number of “time chunks” – the total work done.

true

tru or false? Parallelization can reduce time, but it cannot reduce work.

true

tru or false? The product complexity cannot change or improve.

O(N) time

Given an O(NLogN) algorithm and Log N processors, the algorithm will take at least ________

O(N²) time

Given an O(N³) algorithm and N processors, the algorithm will take at least

hardware

Processors are limited by

power of 2

Typically, the number of processors is a

constant factor, 2^K

Usually: The number of processors is a

x time

A program on one processor, runs in?

no more than X/2 time

Adding another processor runs in ?

X/2 + _Ɛ time

Realistically, it will run in _______ because of overhead

not free

overhead of parallelization is

controlled and coordinated

processors must be _________ and ________

special programming language

Often the program must be written in a ___________________ for parallel systems.

Tasks

• Relatively isolated units of computation

• Should be roughly equal in duration

• Duration of the unit of work must be much greater than overhead time

• Policy decisions and coordination required for shared data

• Simpler algorithm are the easiest to parallelize