Paralelizare pentru programarea procesoarelor multi-core

Mai întâi permiteți-mi să citez două citate din alte subiecte.

Dacă nu se poate programa pe nimic, altele decât BASIC, și nu știu cum să paraleliza procesele de calcul, aceasta nu înseamnă că alții nu știu și nu știu cum. Și dacă programați corect bustul, opțiunile sunt destul de sub puterea personalului modern obișnuit și va face totul pentru un timp acceptabil.


[mesajul îmi este adresat]

Acum, programul meu nu utilizează multi-core, adică Puteți rula numai mai multe programe pe numărul de nuclee ale procesorului fără a crește timpul de funcționare.

Este evident că în ambele citate este o problemă de paralelizare a procesului de calcul în programele destinate execuției pe computere cu procesoare multi-core.

Cine poate încerca?

Nataly-Mak
Și eu am puțină cunoștință.
Primul lucru pe care îl spun va fi distins prin trei nivele de paralelizare.
1) Între computere
2) Între nuclee
3) paralelism la nivel de comandă.

Pentru fiecare nivel, ei folosesc propriile instrumente.

1) Între calculatoare. Poate cel mai simplu mod de a analiza datele. Să presupunem că aveți o rețea conectată la o clasă de calculatoare. Tocmai copiați datele și programul dvs. pe computere și rulați-l pentru execuție. După ce obțineți rezultatul. Pentru a planifica astfel de lucrări, există o mare de programe. Dacă doriți un cluster pe Internet. Apoi trebuie să rezolve încă sarcina de a proteja datele și sistemul. Și, de asemenea, computerele de pe Internet sunt diferite.
2) Paralelismul dintre nuclee. Într-un computer, un număr mare de unități de calcul sunt cele mai mari procesoare (CPU / CPU) și procesoare grafice (GPU / GPU). Fiecare procesor conține unul sau mai multe nuclee. Kernel-ul poate fi privit ca un dispozitiv separat pe care puteți începe propriul flux de comandă. De obicei, nu împărtășesc multiprocesor și multi-core.

Diferența este prezența unei magistrale comune pentru a accesa memoria partajată.
Există două tipuri de sisteme SMP și NUMA.
Symmetric Multiprocessing (SMP) este arhitectura computerelor multiprocesoare în care două sau mai multe procesoare identice sunt conectate la memoria partajată. Când accesați memoria partajată, întreaga magistrală este blocată de această citire sau scriere simultană, nu este posibilă.

NUMA (Acces nelimitat în memorie - "Acces neuniform în memorie" sau arhitectură de memorie neuniformă - "Arhitectură cu memorie neuniformă".
Arhitectura în care accesul la diferite părți ale memoriei are o viteză diferită. Acest lucru se datorează alocării inteligente a memoriei, atunci când accesul la memoria sa merge fără blocare și accesul la partajat cu blocarea.

Dacă luăm în considerare procesorul. Pentru paralelizare, codul este de obicei rezolvat scriind cod paralel pentru un kernel și creând mai multe fire. De obicei, există un astfel de cod. Acest lucru este decis la nivelul limbii.
CreatThead (Thead);
Thead.Do (funcție);
funcția - o subrutină care va fi executată în mai multe fire.
Aceasta este cea mai primitivă. Există lucruri mai avansate, cum ar fi OpenMP, care facilitează scrierea.
Nu este nimic complicat. Doar trebuie să practice pentru a învăța să gândești în paralel.
Dar programatorul trebuie să aibă grijă de accesul la memorie și la încuietori.


GPU-ul este un dispozitiv de calcul puternic. Modern GP este mult mai productiv decât CPU. Prin urmare, este interesant să-l folosiți pentru calcule. Este chiar mai interesant să rulați un singur cod în același timp pe CPU și GPU. CUDA și ATIStreem și altele sunt utilizate în acest scop.
Dezvoltarea CUDA a NVIDIA și dezvoltarea ATI de ATIStreem. Este dificil să rulați același cod pe carduri de la diferiți producători. Este necesar să rescrieți. Cu toate acestea, nu știu despre cele mai recente inovații.


3) paralelism la nivel de comandă.
Procesoarele moderne au o arhitectură multiscalară. Fiecare nucleu are, de obicei, mai multe ALU (Arithmetic Logic Device). Cu o anumită organizație de date și comenzi, kernelul poate executa mai multe comenzi în paralel. Încă există un astfel de lucru ca SIMD.
SIMD (instrucțiunea unică în limba engleză, date multiple) este un principiu al calculelor computerizate care permite paralelismul la nivel de date. Când datele sunt grupate în două, patru, opt. Și o comandă efectuează o operație pe date, folosind 2,4,8 ALU.

Și ce, puteți crește timpul de execuție de mai multe ori (total cu două nuclee ale procesorului)?

Da, puteți. Există o formulă bine cunoscută a legii lui Amdahl dacă procentul costurilor este mic, atunci câștigul poate fi obținut la un nivel mare. Deoarece CPU conține de obicei 2-4 nuclee și fiecare nucleu conține 8.16. ALU. Procesorul grafic are zeci, sute și mii de unități superioare. În GPU, ALU sunt grupate în mod convențional în 4 mai puțin de 8 nuclee.

Dacă știi pascal. Și vei scrie în Pascal / Delphi.


Vai! Acum nu știu. Timp de mult timp, când am lucrat, Pascal a știut și a scris programe despre el.
Acum, după o pauză lungă, știu doar BASIC (a se vedea primul citat)
Scriu pe QBASIC. Colegul meu svb a găsit un compilator foarte bun pb5 pentru mine (înainte de care am lucrat cu interpretul).
Am scris zeci de programe pentru a construi diferite pătrate magice sub acest compilator, nimic, pătrate sunt în mod normal construite

// Tipuri de date utilizabile
const mx = 43;
tip
PNumbers = ^ TNumbers;
TNumbers = array [0..mx * mx-1] din int64;
TMatrix = array [0..mx-1, 0..mx-1] din int64;

tip
TAInteger = matrice de numere întregi;

procedura ViewSquare # 40; k: integer; ms: TMatrix; S: int64; p: boolean = fals; a: boolean = false # 41 ;; suprasarcină;
procedura ViewSquare # 40; var F: TextFile; k: întreg; ms: TMatrix; S: int64; p: boolean = fals; a: boolean = false # 41 ;; suprasarcină;
procedure ViewNumbers # 40; k: integer; S: int64; A: TNumbers # 41 ;;
procedura ViewMatrix # 40; k: integer; A: TNumbers # 41 ;;

funcția GetCnk # 40; n, k: integer # 41 ;: int64;
procedură SetA # 40; var A: TNumbers; b: array de int64 # 41 ;;
procedura SetM # 40; n: integer; var M: TMatrix; b: array de int64 # 41 ;; suprasarcină;
procedura SetM # 40; n: integer; var M: TMatrix; b: matricea întregului # 41; suprasarcină;
funcțiaMatrix # 40; n: integer; A: TNumbers # 41 ;: TMatrix;
funcția CheckMS # 40; n: integer; m: TMatrix; var S: int64; var p, a: boolean # 41 ;: boolean;
procedura ToMatrixRosser # 40; n: integer; A: TNumbers; var M: TMatrix # 41 ;;
este funcțiaMagic # 40; n: integer; M: TMatrix; var S: int64; var p: boolean # 41 ;: boolean;
funcția isPMagic # 40; n: integer; M: TMatrix; S: int64 # 41 ;: boolean;
procedura RosserToMatrix # 40; n: integer; M: TMatrix; var A: TNumbers # 41 ;;
funcția este Different # 40; n: integer; M: TMatrix # 41 ;: boolean;
procedura SetAInteger # 40; a: matrice de integer; var ls: TAInteger # 41 ;;

procedură SetA # 40; var A: TNumbers; b: array de int64 # 41 ;;
var i: întreg;
începe
umplutura # 40; A, dimensiunea A; 41; 0 # 41 ;;
pentru i: = low # 40; b # 41; la mare # 40; b # 41; începeți
A [i]: = b [i];
se încheie;
se încheie;

procedura ViewSquare # 40; k: integer; ms: TMatrix; S: int64; p: boolean = fals; a: boolean = false # 41 ;;
var i, j. întreg;
începe
scrie # 40; k, ': [' # 41 ;;
dacă p scrie apoi # 40; 'p' # 41 ;;
dacă o scrie apoi # 40; 'a' # 41 ;;
scrie # 40; ':', S, ':' # 41 ;;
pentru i: = 0 până la k-1
pentru j: = 0 până la k-1 începe
scrie ms # [i, j] # 41 ;;
dacă # I; se încheie;
writeln;
se încheie;

procedura ViewSquare # 40; var F: TextFile; k: întreg; ms: TMatrix; S: int64; p: boolean = fals; a: boolean = false # 41 ;;
var i, j. întreg;
începe
scrie F, k, ': [' # 41 ;;
dacă p scrie "F", "p" # 41 ;;
dacă o scrie apoi # 40; F, 'a' # 41 ;;
scrie "F; ']:', S, ':' # 41 ;;
pentru i: = 0 până la k-1
pentru j: = 0 până la k-1 începe
scrie f, ms [i, j] # 41 ;;
dacă # I; se încheie;
writeln # 40; F # 41 ;;
se încheie;

procedure ViewNumbers # 40; k: integer; S: int64; A: TNumbers # 41 ;;
var i. întreg;
începe
scrie # 40; k, ':' # 41 ;;
scrie # 40; S, ':' # 41 ;;
pentru i: = 0 până la k-1 începe
scrie # 40; A [i] # 41 ;;
dacă # I; se încheie;
writeln;
se încheie;

// Returnează numărul de combinații de n cu k
// # 40; fără a ține seama de ordinul # 41;
// Cnk = n! / # 40; k! * # 40; n-k # 41 ;! # 41;
funcția GetCnk # 40; n, k: integer # 41 ;: int64;
var d: întreg;
începe
d: = n-k;
rezultat: = 1;
în timp ce n> d nu începe
rezultat: = rezultat * n;
dec # 40; n # 41 ;;
se încheie;
în timp ce k> 1 începe
rezultat: = rezultat div k;
dec # 40; k # 41 ;;
se încheie;
se încheie;

funcțiaMatrix # 40; n: integer; A: TNumbers # 41 ;: TMatrix;
var i, j: întreg;
începe
rezultatul rezultat, dimensiunea rezultatului # 41; 0 # 41 ;;
pentru i: = 0 până la n-1 nu începe
pentru j: = 0 până la n-1 nu începe
rezultatul [i, j]: = A [i * n + j];
se încheie;
se încheie;
se încheie;

// Verificați MS
funcția CheckMS # 40; n: integer; m: TMatrix; var S: int64; var p, a: boolean # 41 ;: boolean;
var i, j, l1, l2. întreg;
S1: întreg;
K: int64;
începe
p: = false;
rezultat: = adevărat;
// Citiți constanta
S: = 0;
pentru j: = 0 până la n-1 nu S: = S + m [0, j];

// Verificați pe rânduri
pentru i: = 0 până la n-1 nu începe
S1: = 0;
pentru j: = 0 până la n-1 nu S1: = S1 + m [i, j];
dacă S1 <> S începe apoi
rezultat: = false;
ieșire;
se încheie;
se încheie;

// Verificați pe coloane
pentru i: = 0 până la n-1 nu începe
S1: = 0;
pentru j: = 0 până la n-1 până la S1: = S1 + m [j, i];
dacă S1 <> S începe apoi
rezultat: = false;
ieșire;
se încheie;
se încheie;

// Verificați cele două diagonale
S1: = 0;
pentru j: = 0 până la n-1 până la S1: = S1 + m [j, j];
dacă S1 <> S începe apoi
rezultat: = false;
ieșire;
se încheie;

S1: = 0;
pentru j: = 0 până la n-1 până la S1: = S1 + m [j, n-1-j];
dacă S1 <> S începe apoi
rezultat: = false;
ieșire;
se încheie;

// Verificarea pandianității
p: = adevărat;

pentru j: = 1 până la n-1 începe
S1: = 0;
pentru i: = 0 până la n-1 până la S1: = S1 + m [i, # 40; j + i # 41; mod n];
dacă S1 <> S începe apoi
p: = false;
pauză;
se încheie;
se încheie;

dacă p începe apoi
pentru j: = n la 2 * n-1 începe
S1: = 0;
pentru i: = 0 până la n-1 până la S1: = S1 + m [i, # 40; j-i # 41; mod n];
dacă S1 <> S începe apoi
p: = false;
pauză;
se încheie;
se încheie;
se încheie;

// Verificați asociativitatea
K: = m [0,0] + m [n-1, n-1];
a: = adevărat;
ll: = # 40; n-1 # 41; div 2;
pentru i: = 0 până la l1 începe
l2: = # 40; n-1 # 41; div 2;
dacă n mod 2 <> 0 apoi dec # 40; 12 # 41 ;;

pentru j: = 0 până la 12 începe
S1: = m [i, j] + m [n-1-i, n-1-j];
dacă S1 <> K începe apoi
a: = false;
pauză;
se încheie;
se încheie;
se încheie;
se încheie;

este funcțiaMagic # 40; n: integer; M: TMatrix; var S: int64; var p: boolean # 41 ;: boolean;
var i, j: întreg;
S1: int64;
începe
rezultat: = false;

// Calculați suma
S: = 0;
pentru i: = 0 până la n-1 nu face S: = S + M [0, i];

// Verificarea corzilor
pentru i: = 0 până la n-1 nu începe
S1: = 0;
pentru j: = 0 până la n-1 nu începe
S1: = S1 + M [i, j];
se încheie;
dacă S1 <> S apoi ieșiți;
se încheie;

// Verificați coloanele
pentru i: = 0 până la n-1 nu începe
S1: = 0;
pentru j: = 0 până la n-1 nu începe
S1: = S1 + M [j, i];
se încheie;
dacă S1 <> S apoi ieșiți;
se încheie;

// Verificați cele două diagonale
S1: = 0;
pentru j: = 0 până la n-1 nu începe
S1: = S1 + M [j, j];
se încheie;
dacă S1 <> S apoi ieșiți;

S1: = 0;
pentru j: = 0 până la n-1 nu începe
S1: = S1 + M [j, n-1-j];
se încheie;
dacă S1 <> S apoi ieșiți;

p: = isPMagic # 40; n, M, S # 41 ;;
se încheie;

funcția isPMagic # 40; n: integer; M: TMatrix; S: int64 # 41 ;: boolean;
var k, i: întreg;
S1. Int64;
începe
rezultat: = false;

pentru k: = 0 până la n-1 nu începe
S1: = 0;
pentru i: = 0 până la n-1 nu începe
S1: = S1 + M [i, # 40; k + i # 41; mod n];
se încheie;
dacă S1 <> S apoi ieșiți;
se încheie;

pentru k: = n la 2 * n-1 începe
S1: = 0;
pentru i: = 0 până la n-1 nu începe
S1: = S1 + M [i, K-i # 41; mod n];
se încheie;
dacă S1 <> S apoi ieșiți;
se încheie;

procedura ToMatrixRosser # 40; n: integer; A: TNumbers; var M: TMatrix # 41 ;;
var i, j, k, l. întreg;
începe
pentru i: = 0 până la n-1 nu începe
pentru j: = 0 până la n-1 nu începe
k: = # 3; i + 2 * j # 41; mod n;
l: = # 40; 2 * i + j # 41; mod n;

procedura RosserToMatrix # 40; n: integer; M: TMatrix; var A: TNumbers # 41 ;;
var i, j, k, l. întreg;
începe
pentru i: = 0 până la n-1 nu începe
pentru j: = 0 până la n-1 nu începe
k: = # 3; i + 2 * j # 41; mod n;
l: = # 40; 2 * i + j # 41; mod n;

procedura SetM # 40; n: integer; var M: TMatrix; b: array de int64 # 41 ;;
var i, j: întreg;
începe
pentru i: = 0 până la n-1
pentru j: = 0 până la n-1 nu începe
M [i, j]: = b [i * n + j];
se încheie;
se încheie;

procedura SetM # 40; n: integer; var M: TMatrix; b: matricea întregului # 41;
var i, j: întreg;
începe
pentru i: = 0 până la n-1
pentru j: = 0 până la n-1 nu începe
M [i, j]: = b [i * n + j];
se încheie;
se încheie;

procedura ViewMatrix # 40; k: integer; A: TNumbers # 41 ;;
var i, j: întreg;
începe
pentru i: = 0 până la k-1 începe
pentru j: = 0 până la k-1 începe
scrie: A [i * k + j], '' # 41 ;;
se încheie;
writeln;
se încheie;
se încheie;

// Verificați toate numerele de matrice
// returnează adevărat dacă toate numerele sunt diferite
funcția este Different # 40; n: integer; M: TMatrix # 41 ;: boolean;
var i, j, k, l, c: întreg;
D: int64;
începe
rezultat: = adevărat;

pentru i: = 0 până la n-1 nu începe
pentru j: = 0 până la n-1 nu începe

D: = m [i, j]; c: = 0;
pentru k: = 0 până la n-1 nu începe
pentru l: = 0 până la n-1 nu începe
dacă m [k, l] = D atunci începe
inc. # 41 ;;
dacă c> 1 începe apoi
writeln # 41; D # 41 ;;
rezultat: = false;
ieșire;
se încheie;
se încheie;
se încheie;
se încheie;
se încheie;
se încheie;
se încheie;

// a -> ls
procedura SetAInteger # 40; a: matrice de integer; var ls: TAInteger # 41 ;;
var i: întreg;
începe
SetLength # 40; # 40; # 41; + 1 # 41 ;;
pentru i: = 0 până la lungimea # 40; ls # 41; - 1 pentru ls [i]: = a [i];
se încheie;

Acest program nu utilizează procesor multi-core.
Întrebarea este: este posibil și cât de dificil este introducerea paralelizării întregului proces de calcul în acest program?
Așa cum am scris deja, am doar două nuclee în procesor. Colegul meu svb are un procesor quad-core. Un tovarăș de la alt forum are un procesor cu opt nuclee și este gata să ajute la executarea programului, însă el nu poate paraleli codul finit însuși.

Sau poate să folosim multi-core, trebuie să scriem un nou cod? Codul scris pentru un procesor cu un singur nucleu nu este suficient de bun, este greu sau imposibil să îl convertiți într-un procesor multicore (?)
Aceasta este întreaga întrebare!