Comprehensive Guide to Sequential, Distributed, and Parallel Computing Concepts

Sequential Computing

A computational model where operations are performed in order, one at a time.

The Instruction Cycle

Also known as the Fetch-Decode-Process Cycle.

CPU (Central Processing Unit)

The 'brain' that processes instructions in sequence.

Fetch-Decode-Process Steps

1. The next instruction is fetched. 2. The instruction is decoded. 3. The instruction is processed.

Sequential Rule

One instruction must finish completely before the next one in sequence is executed.

Moore's Law

The observation that processors are becoming denser and denser.

The Heat Constraint

Increasing processor speed generates heat from moving electrons, which can create a physical limit to sequential speed.

Distributed Computing

A model where multiple devices are used to run a program.

The 'Anthill' Analogy

Many ants moving one grain of dirt at a time can build a hill faster than one ant could; similarly, many computers move fragments of data to solve large problems quickly.

Scalability

Distributed computing is scalable. As workload grows, you can add more computers.

SETI@Home

A project launched in 1999 by UC Berkeley to search for signs of extraterrestrial intelligence using radio telescope data.

BOINC

(Berkeley Open Infrastructure for Network Computing) The software that allows users to donate 'idle' computer time to scientific research.

GIMPS

(Great Internet Mersenne Prime Search) A project that uses ~2 million computers to find Mersenne primes.

Mersenne Prime

A prime number that is one less than a power of two ($2^n - 1$). The largest known has over 24 million digits.

Botnets

Large collections of networked computers infected by malware (worms/viruses) and controlled remotely without the owner's knowledge.

Zombies

The name for individual infected computers within a botnet.

Malicious Uses of Botnets

Sending massive amounts of spam, launching DDoS (Distributed Denial of Service) attacks, hijacking processing cycles for Bitcoin mining.

Parallel Computing

A model where a program is broken into smaller sequential operations, some of which are performed simultaneously using two or more processors.

Structure of Parallel Computing

Parallel computing always consists of a parallel portion and a sequential portion.

Dependencies in Parallel Computing

The challenge of ensuring one set of instructions doesn't have to wait for another set to finish first.

Efficiency Analysis

Comparing the time it takes to complete a task using different systems.

Calculating Sequential Time

Add the time units of all instructions together ($2+1+4+3+5+2 = 17$).

Calculating Parallel Time

Add the time for sequential steps, then add the longest of the concurrent tasks.

Optimization

Rearranging independent instructions among processors to find the shortest possible 'longest path.'

Speedup Formula

$\text{Sequential Time} \div \text{Parallel Time}$.

The Hardware Limit

Eventually, adding more processors will NOT increase speed because of the sequential dependencies.