Parallel Calculations

Содержание и основные понятия

Back to the table of contents
Alterna · Chapter 7 · page 7.1
Parallel Calculations
One processor is good. Two is better. And a thousand? We're going to figure out how to speed up the computation by dividing the work between the cores, and why we can't continue to accelerate.
Parallel Calculations
- it's when the task is broken down, and each part is performed simultaneously on its own processor.
Modern processors have 4–16 cores, video cards have thousands, but parallelism is not a panacea: part of the code is always consistent, and this limits acceleration.
GEF · Basic
EGE No. 22
01
Why parallel?
Moore's law slows down, the frequency doesn't grow, the cores grow.
Frequency limit
Up to 2005, processors accelerated by increasing
Tactical frequency
(Hz) But above ~4 GHz the chip has overheated.
increase in number of kernels
.
Two types of parallelism
📊
Data parallelism
data parallelism
One operation applies to many data simultaneously. Example: Apply the filter to all image pixels.
🔀
Parallelity of tasks
task parallelism
Different kernels perform different tasks at the same time. Example: one core rendezvous the video, the other one compresses the file.
Relationship to Chapter 2
In chapter 2 (PC), we've seen multi-nuclear processors on a mother's fee, and now we're going to figure out how they work together.
02
Amdal Law
Why the infinite number of kernels does not provide infinite acceleration
Formula
Gene Amdal (1967) removed the formula for maximum acceleration in dispersing:
S = 1 / ((1 − p) + p / N)
p is the fraction of parallel code (0-1), N is the number of kernels
Example
Program: 80 per cent can be decoupled (p = 0.8) 20 per cent in strict sequence. 4 kernels:
S = 1 / (0.2 + 0.8/4) = 1 / (0.2 + 0.2) = 1 / 0.4 =
2.5
Acceleration
2.5 times
4. Consequently 20 per cent, the "bottle throat".
Amdal limit
At N ♪ ♪:
S_max = 1 / (1 − p)
For p = 0.9: maximum 10×. for p =0.99: maximum 100×.
EEG trap
Acceleration
Never.
does not exceed
1/(1-p)
If p = 0.5, the maximum is 2×, even with a million kernels.
03
Flynn classification
Four types of architecture by number of command and data flows
Michael Flynn (1966) divided all computers into four classes by number of flows
Commands
(Instruction) and
Data
(Data):
Grade
Commands
Data
Example
SISD
1
1
Normal single-nuclear processor
SIMD
1
many
GPU, vector instructions (SE/AVX)
MISD
many
1
Theoretical (nearly not used)
MIMD
many
many
Multi-nuclear CPUs, clusters, supercomputers
Remember
SISD
- your old PC.
SIMD
- The video card.
MIMD
- A modern multi-nuclear processor or supercomputer.
04
Conveyer handling
Breaking a team at the stage is like an assembly at a factory.
The idea of a conveyor
Each processor team goes through several stages. Instead of waiting for the completion of one command, the processor begins the following while it is still on the conveyor:
Tact 1
IF (com.1)
Tact 2
ID (com.1)
IF (com2)
Tact 3
EX (com.1)
ID (com2)
IF (com.3)
Tact 4
WB (com.1)
EX (com 2)
ID (com.3)
IF (com.4)
IF - uploading
ID - Decoding
EX — Implementation
WB - Recording
Figure 1.
4-stage conveyor: After filling, each command ends at 1 stroke
Conveyer formula
For
k
Stages and
n
Commands:
T = k + (n − 1)
Tacts.
Without the conveyor:
T = k × n
II. Winner: around
k
I don't know if it's a big n.
Example
4 stages, 100 commands: conveyor = 4 + 99 =
103
Tacta. No conveyor = 4 x 100 =
400
Tacti. acceleration ~ 3.9×.
05
Multi-accuracy and sync
Flows, mutecs, deadlock — How not to break parallel program
Vs Flow Process
Process
Flow (thread)
Memory
Its own (insulated)
Shared with other process flows
Creation
Slow (fork)
Quick.
Data exchange
Through IPC (tubes, scoets)
Directly through common memory
Security
High (isolation)
Low
Parallelism issues
🏁
Race Condition
Status of the race
Two streams read and write one variable at the same time. The result is unpredictable.
🔒
Deadlock
Interlocking
Flow A awaits resource B, stream B waits for resource A. Both wait forever.
⏳
Livelock
living blockage
Flows aren't blocked, but they're endlessly giving in to each other without progress.
Synchronization mechanisms
Mechanism
Appointment
Mutex
Interceptive lock: Only one stream can own a resource
Semaphorus
Combination of mutex: Allows N flows simultaneously
Barriers
All streams wait until the last one reaches the barrier.
Atomic operation
Operation performed in whole or not at all
4 deadlock conditions
1. Interference (resources occupied by one): 2. Retention and waiting (hold one, wait another). 3. No compulsory exemption. 4. Ring waiting (A
Relationship to the EGE No. 23, 26
Understanding Gant's parallel processes and diagrams helps in the tasks of EGE No. 23 (calculation of trajectory - branch = parallel tracks) and No. 26 (data processing with priorities and time - planning as OS).
📐
Amdal Law Calculator
Move the sliders · See acceleration
Interactor
Change the fraction of the parallel code (p) and the number of kernels (N) — the calculator will show acceleration, efficiency and theoretical limit.
Parallel code (p)
80%
Number of kernels (N)
4
2.50
Acceleration (S)
62.5%
Efficiency (S/N)
5.00
Limit (N:)
🏷️
Flynn classification
click on card · details
Interactor
Press the class to see the description, the examples, and the SVG diagram.
SISD
Single Instruction, Single Data
One team, one data.
The classic single-nuclear processor Von Neyman. Commands are strictly consistent.
Examples: Intel 8086, early PCs, now found in microcontrollers.
SIMD
Single Instruction, Multiple Data
One team, lots of data.
One instruction applies to many elements simultaneously.
Examples: GPU (thousands of kernels process pixels), SSE/AVX in CPU (vector operations). Perfect for graphics, neuronets, signal processing.
MISD
Multiple Instruction, Single Data
Lots of teams, just data.
Different processors apply different operations to the same data.
It's almost not used. Sometimes it's how you describe the conveyor (the different stages are different operations over one team).
MIMD
Multiple Instruction, Multiple Data
Lots of teams, lots of data.
Each processor carries out its own program over its own data.
Examples are: Intel Core i7, AMD Ryzen, clusters, supercomputers, the most common class of modern systems.
🏭
Conveyer: Visualization
Set the stage and command settings · compare to the un-conveyer.
Interactor
Change the number of stages of the conveyor and teams -- you see the tactics of performance and the winnings.
Conveyer stages (k)
4
Commands (n)
6
9
Conveyer (tacts)
24
Without a conveyor
2.67×
Acceleration
📊
You're the OS planner.
Ganta diagram · move the processes to the time scale
Interactor
Three processes with different execution times are given. Place them on a time scale for one CPU kernel. Try first in sequence, then with I/O-waiting (the process goes to WAITING, releasing CPU).
P1: Calculations
3 Tacts
I/O: 0 strokes
P2: File Reading
2 CPU beats
I/O: 3 strokes (after CPU)
P3: Network
1 stroke CPU
I/O: 2 strokes (after CPU)
CPU
P2 I/O
P3 I/O
Total time:
—
Loading CPU:
—
Average waitin