Parallel and Distributed Computing

Question 1

Distributed Computing System example

Answer 1

the cs lab, supercomputers, email, file servers, printer access

Question 2

Parallel Computing system example

Answer 2

Stampede here on campus

Question 3

Distributed System

Answer 3

A set of physically separate processors connected by one or more communication links

Question 4

Parallel Computing

Answer 4

-Tightly-coupled systems-processors share clock, memory, and run one OS-frequent communication-processors connected via a network (typically a bus)-network is connected to single shared memory

Question 5

Distributed Computing

Answer 5

-loosely-coupled systems-Each processor has its own memory-each processor runs an independent OS-communication is very expensive-collection of computers (nodes) connected by a network

Question 6

Parallel computing communicates through:

Answer 6

shared memory (typically)-read and write accesses to shared memory locations

Question 7

Two forms of parallel computing architecture:

Answer 7

-SMP (Symmetric Multiprocessor)-Multicore-can also combine the two (ex. Stampede)

Question 8

Distributed computing communicates through:

Answer 8

message passing

Question 9

The architecture of distributed computing

Answer 9

-Nodes are connected by a network-Massively Parallel Machines

Question 10

SMP (Symmetric Multiprocessor)

Answer 10

-Multiprocessor: two or more processors have a common RAM-Symmetric refers to the OS (one OS for all processors and any processor can run it)

Question 11

Multicore:

Answer 11

multiprocessors on the same chip

Question 12

Massively Parallel Machines

Answer 12

-nodes are greatly simplified and include only memory, processor(s), network card-augmented with fast network interface

Question 13

Clusters

Answer 13

-Networks workstations with a fast-built of Common off-the-shelf (COTS) parts-less specialized

Question 14

Very Distributed Computing

Answer 14

-grid computing-cloud computing

Question 15

Parallel programming involves:

Answer 15

-decomposing an algorithm into parts-Distributing the parts as tasks which re worked on by multiple processors simultaneously-Coordinating work and communication of those processors (synchronization)

Question 16

Parallel programming considerations:

Answer 16

-type of parallel architecture being used-type of processor communications used

Question 17

Shared memory Programming Model

Answer 17

-interprocess communication is implicit-synchronization is explicit-assume processes/threads can read & write a set of shared memory locations-difficult to provide across machine boundaries-programs/threads communicate/cooperate via loads/stores to memory locations they share-communication is therefore at memory access speed (very fast) and is implicit-cooperating pieces must all execute on the same system (computer)-OS services and/or libraries used for creating tasks (processes/threads) and coordination (semaphores/barriers/locks)

Question 18

message passing Programming Model

Answer 18

“-interprocess communication is explicit-Synchronization is implicit-extensible to communication in distributed systems-““shared”” data is communicated using send/receive services (across an external network)-shared data must be formatted into message chunks for distribution-coordination is also via sending/receiving messages-program components can be run on the same or different systems, so can use many of processes-standard libraries exist to encapsulate messages”

Question 19

when do send/receive operations terminate?

Answer 19

“-Blocking (synchronous): sender waits until its message is received; receiver waits if no message is available-Non-blocking (asynchronous): send operation ““immediately”” returns; receive operation returns if message is available or not (polling)-partially blocking/non-blocking: send/receive with timeout”

Question 20

Limitations of message passing

Answer 20

-easy for OS, hard for programmer-programmer must code communication-programmer may have to code format conversions, flow control, error control-no dynamic resource discovery

Question 21

Event Ordering

Answer 21

-Coordination of requests (especially in a fair way) requires events (requests) to be ordered-stand alone systems: shared clock/memory-distributed systems: no global clock; each clock runs at different speeds (clock drift)

Question 22

Event ordering for distributed systems

Answer 22

“-through message passing-a message must be sent before it can be received-send/receives can thus ““synchronize”” the clocks”

Question 23

Happened-Before Relation

Answer 23

1. If A and B are events in the same process, and A executed before B, then A->B2. If A is a message send and B is when the message is received, then A->B3. A->B, and B->C, then A->C (transitivity)

Question 24

Atomicity

Answer 24

either something happens or it doesn’t- don’t want partial things to happen

Question 25

The Generals’ Paradox

Answer 25

Problem:-Two generals are on two separate mountains-can communicate only via messengers; but messengers can get lost or captured by enemy-goal is to coordinate their attack

Question 26

Distributed Consensus with Link Failures

Answer 26

Problem:-Take any exchange of messages that solves the general’s- Take the last message mn . Since mn might be lost, but the algorithm still succeeds, it must not be necessary.- Repeat until no messages are exchanged.- No messages exchanged can’t be a solution, so our assumption that we have an algorithm to solve the problem must be wrong.

Question 27

Distributed Transactions

Answer 27

-two machines agree to do something, or not do it, atomically-two-phase commit protocol allows coordination under reasonable operating conditions-uses log on each machine to track whether commit happened

Question 28

Two-phase Commit Protocol: phase 1

Answer 28

Phase 1: Coordinator requests a transaction-Coordinator sends a request to all participants for that transaction-on receiving request, participants perform these actions: execute the transaction; write VOTE_COMMIT or VOTE_ABORT to local logs; send VOTE_COMMIT or VOTE_ABORT to coordinator

Question 29

Two-Phase Commit Protocol: Phase 2

Answer 29

Phase 2: Coordinator commits or aborts the transaction -coordinator decides: -Case 1: coordinator receives VOTE_ABORT or times out -Case 2: Coordinator receives VOTE_COMMIT from all participants

Question 30

Bully Algorithm

Answer 30

“• Assumptions:-Processes are numbered (otherwise impossible).-Using process numbers does not cause unfairness.•Algorithm concept:-If leader is not heard from in a while, assume s/he crashed.-Leader will be remaining process with highest rank.-Processes who think they are leader-worthy will broadcast that information.-During this ““election campaign”” processes who are near the top see if the process trying to grab power crashes (as evidenced by lack of message in timeout interval).-At end of time interval, if alpha-process has not heard from rivals, assumes s/he has won.-If former alpha-process arises from dead, s/he bullies their way to the top. (Invariant: highest # process rules)”