Dalam hal ini, mereka biasanya melanjutkan dari gagasan bahwa paralelisasi tidak boleh mempengaruhi hasil eksekusi program. Ini adalah persyaratan yang sulit, tetapi adil dalam banyak kasus. Namun, jika kita mencoba untuk memparalelkan program yang melakukan perhitungan apa pun dengan metode numerik (kita melatih jaringan saraf, mensimulasikan dinamika fluida atau sistem molekuler, menyelesaikan persamaan diferensial biasa atau masalah pengoptimalan), maka hasilnya akan (dalam hal apa pun) memiliki beberapa kesalahan. Oleh karena itu, mengapa tidak menerapkan teknologi paralelisasi "berisiko", yang dapat menyebabkan kesalahan tambahan kecil dalam solusi matematika,tetapi memungkinkan Anda mendapatkan akselerasi tambahan lagi? Salah satu teknologi tersebut - pemisahan badan perulangan dengan memprediksi hasil antara dan memutar kembali jika prediksi tidak berhasil (pada kenyataannya, ini adalah kalkulasi "terlalu optimis" dalam memori transaksional sebagian) akan dibahas.
Ide paralelisasi
Misalkan kita memiliki sebuah siklus, yang tubuhnya terdiri dari dua bagian yang berurutan, dan bagian kedua bergantung pada yang pertama. Biarkan loop individu dari siklus bergantung satu sama lain. Misalnya:
for (int i = 0; i < N; i++) {
x = f(y);
y = g(x);
}
Sekilas, loop seperti itu tidak dapat diparalelkan. Bagaimanapun, kami akan mencoba. Mari kita coba mengeksekusi operator pertama dan kedua dari badan loop secara paralel. Masalahnya pada saat menghitung g (x) x harus diketahui, tetapi baru akan dihitung di akhir bagian pertama. Nah, mari kita perkenalkan beberapa skema, yang di awal bagian kedua akan mencoba memprediksi nilai baru x. Hal ini dapat dilakukan, misalnya, dengan bantuan prediksi linier, yang "belajar" memprediksi nilai baru x, berdasarkan "riwayat" perubahannya. Kemudian bagian kedua dapat dibaca secara paralel dengan bagian pertama (ini adalah "optimisme berlebihan"), dan jika keduanya dihitung, bandingkan nilai prediksi x dengan nilai nyata yang diperoleh di akhir bagian pertama. Jika kurang lebih sama, maka hasil kalkulasi kedua bagian dapat diterima (dan lanjutkan ke iterasi loop berikutnya).Dan jika keduanya sangat berbeda, maka hanya bagian kedua yang perlu diceritakan. Dengan skema ini, di beberapa bagian kasus, kita akan mendapatkan paralelisasi murni, sisanya - jumlah sekuensial aktual. Algoritme eksekusi loop adalah sebagai berikut:
for (int i = 0; i < N; i++) {
{
1 – x = f(y). x;
2 – x* y* = g(x*). x x*. , y = y* . , : y = g(x).
}
}
Algoritma dasarnya jelas. Secara teoritis percepatan adalah dua kali, tetapi dalam prakteknya tentu saja akan lebih sedikit, karena: a) sebagian waktu dihabiskan untuk prediksi dan koordinasi; b) tidak semua iterasi akan dijalankan secara paralel; c) bagian pertama dan kedua dari badan siklus dapat memiliki intensitas tenaga kerja yang berbeda (idealnya, diperlukan persamaan). Mari kita lanjutkan ke implementasinya.
Implementasi Paralelisasi - Komputasi Over-Optimistic
Karena algoritme paralelisasi berkaitan dengan pembatalan beberapa kalkulasi (jika terjadi kegagalan) dan mengeksekusinya kembali, jelas ada sesuatu dari gagasan bekerja dalam memori transaksional. Lebih baik - dalam sebagian transaksional, di mana variabel tertentu bekerja sesuai dengan skema memori transaksional, dan variabel lainnya bekerja seperti biasa. Transfer data dari bagian pertama ke bagian kedua dapat diatur menggunakan beberapa saluran khusus. Biarkan saluran ini bersifat prediktif: a) jika pada saat penerimaan data telah dikirim ke saluran, kemudian dibaca darinya, b) jika pada saat penerimaan data belum sampai di saluran, maka ia mencoba untuk memprediksi data ini dan mengembalikan hasil prediksi. Saluran ini akan bekerja sesuai dengan skema yang agak tidak biasa untuk memori transaksional konvensional:Jika pada akhir transaksi bagian kedua dari siklus tersebut terdapat ketidaksesuaian antara data yang diterima ke dalam saluran dan data yang diprediksi olehnya, maka transaksi pada bagian kedua dari siklus tersebut dibatalkan dan dijalankan kembali, dan bukan “prediksi” yang akan dibaca dari saluran tersebut, melainkan data yang benar-benar diterima. Siklusnya akan terlihat seperti:
for (int i = 0; i < N; i++) {
, {
1 ( 1):
x = f(y);
_.put(x);
2 ( 2):
_.get(x);
y = g(x);
}
}
Selesai. Saluran menangani prediksi data, sedangkan memori transaksi menangani pembatalan kalkulasi jika prediksi terlalu optimis.
Beberapa aplikasi yang berguna: jaringan saraf, metode partikel-dalam-sel
Skema untuk memparalelkan badan loop dapat digunakan dalam sejumlah algoritme matematika, misalnya, saat memodelkan lensa elektrostatis menggunakan metode partikel dalam sel, serta saat melatih jaringan saraf maju umpan menggunakan metode propagasi mundur. Tugas pertama sangat istimewa, jadi saya tidak akan membahasnya di sini, saya hanya akan mengatakan bahwa pendekatan paralelisasi yang dijelaskan memberikan percepatan 10-15%. Tetapi tugas kedua sudah lebih populer, jadi Anda hanya perlu mengatakan beberapa patah kata saja.
Siklus pelatihan jaringan saraf mencakup lintasan berurutan melalui pasangan pelatihan, dan untuk setiap pasangan, gerakan maju (penghitungan keluaran jaringan) dan gerakan mundur (koreksi bobot dan bias) dilakukan. Ini adalah dua bagian badan loop untuk pasangan pelatihan, dan untuk memparalelkannya, Anda dapat menerapkan pendekatan di atas (ngomong-ngomong, ini juga dapat diterapkan dengan paralel melewati pasangan pelatihan, dengan perubahan kecil). Hasilnya, pada tugas pelatihan jaringan saraf tipikal, saya mendapatkan peningkatan kinerja sebesar 50%.
Otomatisasi paralelisasi program C.
Gagasan komputasi super-optimis tidak terlalu sulit, sehingga program penerjemah khusus ditulis yang berhubungan dengan paralelisasi otomatis - ia menemukan loop dalam program C asli yang paralelisasi tersebut dapat memberikan hasil positif dan membagi tubuh mereka menjadi dua bagian, memasukkan arahan OpenMP yang diperlukan, menemukan variabel potensial untuk saluran, menghubungkan perpustakaan untuk bekerja dengan sebagian memori transaksional dan saluran prediksi dan, pada akhirnya, menghasilkan program keluaran yang diparalelkan.
Secara khusus, penerjemah semacam itu diterapkan pada program simulasi lensa elektrostatis. Saya akan memberikan kedua program - yang asli (yang mencakup arahan yang menunjukkan paralelisasi loop) dan yang diperoleh setelah terjemahan.
Program asli:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#pragma auto parallelize
#pragma auto pure(malloc,fabs,free,sizeof,omp_get_wtime)
#define theta 1.83
#define NX 40
#define NY 40
#define h 0.1
#define NP 15000
//
#define U1 200
#define U2 5000
#define e -1.5E-13
#define m 1E-11
#define e0 8.85E-12
#define V (h*h)
#define tau 0.000015
#define T 0.09
#define POISSON_EPS 0.01
#define TOL_EPS 0.25
int main() {
double * U = (double *)malloc(NY*NX*sizeof(double));
double * UU = (double *)malloc(NY*NX*sizeof(double));
double * EX = (double *)malloc(NY*NX*sizeof(double));
double * EY = (double *)malloc(NY*NX*sizeof(double));
double * PX = (double *)malloc(NP*sizeof(double));
double * PY = (double *)malloc(NP*sizeof(double));
int * X = (int *)malloc(NP*sizeof(int));
int * Y = (int *)malloc(NP*sizeof(int));
double ro[NY][NX];
split_private double t;
split_private double tm;
split_private int i, j;
for (i = 0; i < NY; i++)
for (j = 0; j < NX; j++) {
UU[i*NX+j] = j == NX-1 ? U2 : j == NX/2 && (i < NY/4 || i > 3*NY/4) ? U1 : 0.0;
EX[i*NX+j] = 0.0;
EY[i*NX+j] = 0.0;
}
for (i = 0; i < NP; i++) {
int x, y;
PX[i] = 0.5*NX*h*rand()/RAND_MAX;
PY[i] = NY*h*rand()/RAND_MAX;
x = PX[i]/h;
y = PY[i]/h;
if (x < 0) x = 0;
else if (x > NX-1) x = NX-1;
if (y < 0) y = 0;
else if (y > NY-1) y = NY-1;
X[i] = x;
Y[i] = y;
}
tm = omp_get_wtime();
for (t = 0.0; t < T; t += tau) {
unsigned int n[NY][NX] = { 0 };
double err;
int ptr = 0;
for (i = 0; i < NY; i++)
for (j = 0; j < NX; j++, ptr++)
U[ptr] = UU[ptr];
for (i = 1; i < NY - 1; i++)
for (j = 1; j < NX - 1; j++) {
EX[i*NX+j] = -(U[i*NX+j+1]-U[i*NX+j-1])/2.0/h;
EY[i*NX+j] = -(U[(i+1)*NX+j]-U[(i-1)*NX+j])/2.0/h;
}
for (i = 0; i < NP; i++) {
PX[i] += tau*e*EX[Y[i]*NX+X[i]]/m;
PY[i] += tau*e*EY[Y[i]*NX+X[i]]/m;
}
for (i = 0; i < NP; i++) {
int x = PX[i]/h;
int y = PY[i]/h;
if (x < 0) x = 0;
else if (x > NX-1) x = NX-1;
if (y < 0) y = 0;
else if (y > NY-1) y = NY-1;
Y[i] = y;
X[i] = x;
n[y][x]++;
}
for (i = 0; i < NY; i++)
for (j = 0; j < NX; j++)
ro[i][j] = n[i][j]*e/V;
do {
err = 0.0;
for (i = 1; i < NY - 1; i++)
for (j = 1+(i-1)%2; j < NX - 1; j+=2) {
int ptr = i*NX + j;
if (!(j == NX/2 && (i < NY/4 || i > 3*NY/4))) {
double _new = (1-theta)*UU[ptr] + theta/4.0*(UU[ptr-1]+UU[ptr+1]+UU[ptr+NX]+UU[ptr-NX]-h*h*ro[i][j]/e0);
double loc_err = fabs(UU[ptr] - _new);
if (loc_err > err) err = loc_err;
UU[ptr] = _new;
}
}
for (i = 1; i < NY - 1; i++)
for (j = 1+i%2; j < NX - 1; j+=2) {
int ptr = i*NX + j;
if (!(j == NX/2 && (i < NY/4 || i > 3*NY/4))) {
double _new = (1-theta)*UU[ptr] + theta/4.0*(UU[ptr-1]+UU[ptr+1]+UU[ptr+NX]+UU[ptr-NX]-h*h*ro[i][j]/e0);
double loc_err = fabs(UU[ptr] - _new);
if (loc_err > err) err = loc_err;
UU[ptr] = _new;
}
}
for (j = 0; j < NX; j++) {
UU[j] = UU[NX + j];
UU[(NY-1)*NX + j] = UU[(NY-2)*NX + j];
}
} while (err > POISSON_EPS);
}
for (i = 0; i < NY; i++) {
for (j = 0; j < NX; j++)
printf("%lf\t", UU[i*NX+j]);
printf("\n");
}
return 0;
}
Program paralel secara otomatis
#include "transact.h"
#define split_private /* split-private */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define theta 1.83
#define NX 40
#define NY 40
#define h 0.1
#define NP 15000
#define U1 200
#define U2 5000
#define e -1.5E-13
#define m 1E-11
#define e0 8.85E-12
#define V (h*h)
#define tau 0.000015
#define T 0.09
#define POISSON_EPS 0.01
#define TOL_EPS 0.25
int main( ){
double * U = (double *)malloc(NY*NX*sizeof(double));
double * UU = (double *)malloc(NY*NX*sizeof(double));
double * EX = (double *)malloc(NY*NX*sizeof(double));
double * EY = (double *)malloc(NY*NX*sizeof(double));
double * PX = (double *)malloc(NP*sizeof(double));
double * PY = (double *)malloc(NP*sizeof(double));
int * X = (int *)malloc(NP*sizeof(int));
int * Y = (int *)malloc(NP*sizeof(int));
double ro[NY][NX];
split_private double t;
split_private double tm;
split_private int i, j;
for ( i = 0; i < NY; i++ )
for ( j = 0; j < NX; j++ )
{
UU[i*NX+j] = j == NX-1 ? U2 : j == NX/2 && (i < NY/4 || i > 3*NY/4) ? U1 : 0.0;
EX[i*NX+j] = 0.0;
EY[i*NX+j] = 0.0;
}
for ( i = 0; i < NP; i++ )
{
int x, y;
PX[i] = 0.5*NX*h*rand()/RAND_MAX;
PY[i] = NY*h*rand()/RAND_MAX;
x = PX[i]/h;
y = PY[i]/h;
if ( x < 0 )
x = 0;
else
if ( x > NX-1 )
x = NX-1;
if ( y < 0 )
y = 0;
else
if ( y > NY-1 )
y = NY-1;
X[i] = x;
Y[i] = y;
}
tm = omp_get_wtime();
#pragma omp parallel num_threads(2) private(t,tm,i,j)
{
int __id__ = omp_get_thread_num();
TOut<double > * out_ro = __id__ == 0 ? new TOut<double >("ro63", (NY)*(NX), 2, 0.01, -1, "63") : NULL;
TIn<double > * in_ro = __id__ == 1 ? new TIn<double >("ro63", (NY)*(NX), 2, 0.01, -1, "63") : NULL;
for ( t = 0.0; t < T; t += tau )
{
unsigned int n[NY][NX] = { 0 };
double err;
int ptr = 0;
if ( __id__ == 0 )
{
for ( i = 0; i < NY; i++ )
for ( j = 0; j < NX; j++, ptr++ )
U[ptr] = UU[ptr];
}
transaction_atomic("63")
{
if ( __id__ == 0 )
{
for ( i = 1; i < NY - 1; i++ )
for ( j = 1; j < NX - 1; j++ )
{
EX[i*NX+j] = -(U[i*NX+j+1]-U[i*NX+j-1])/2.0/h;
EY[i*NX+j] = -(U[(i+1)*NX+j]-U[(i-1)*NX+j])/2.0/h;
}
for ( i = 0; i < NP; i++ )
{
PX[i] += tau*e*EX[Y[i]*NX+X[i]]/m;
PY[i] += tau*e*EY[Y[i]*NX+X[i]]/m;
}
for ( i = 0; i < NP; i++ )
{
int x = PX[i]/h;
int y = PY[i]/h;
if ( x < 0 )
x = 0;
else
if ( x > NX-1 )
x = NX-1;
if ( y < 0 )
y = 0;
else
if ( y > NY-1 )
y = NY-1;
Y[i] = y;
X[i] = x;
n[y][x]++;
}
for ( i = 0; i < NY; i++ )
for ( j = 0; j < NX; j++ )
ro[i][j] = n[i][j]*e/V;
out_ro->put((double *)ro);
}
else
{
double ro[NY][NX];
in_ro->get((double *)ro, 0);
do
{
err = 0.0;
for ( i = 1; i < NY - 1; i++ )
for ( j = 1+(i-1)%2; j < NX - 1; j+=2 )
{
int ptr = i*NX + j;
if ( !(j == NX/2 && (i < NY/4 || i > 3*NY/4)) )
{
double _new = (1-theta)*UU[ptr] + theta/4.0*(UU[ptr-1]+UU[ptr+1]+UU[ptr+NX]+UU[ptr-NX]-h*h*ro[i][j]/e0);
double loc_err = fabs(UU[ptr] - _new);
if ( loc_err > err )
err = loc_err;
UU[ptr] = _new;
}
}
for ( i = 1; i < NY - 1; i++ )
for ( j = 1+i%2; j < NX - 1; j+=2 )
{
int ptr = i*NX + j;
if ( !(j == NX/2 && (i < NY/4 || i > 3*NY/4)) )
{
double _new = (1-theta)*UU[ptr] + theta/4.0*(UU[ptr-1]+UU[ptr+1]+UU[ptr+NX]+UU[ptr-NX]-h*h*ro[i][j]/e0);
double loc_err = fabs(UU[ptr] - _new);
if ( loc_err > err )
err = loc_err;
UU[ptr] = _new;
}
}
for ( j = 0; j < NX; j++ )
{
UU[j] = UU[NX + j];
UU[(NY-1)*NX + j] = UU[(NY-2)*NX + j];
}
}
while ( err > POISSON_EPS )
;
}
}
}
delete in_ro;
delete out_ro;
}
for ( i = 0; i < NY; i++ )
{
for ( j = 0; j < NX; j++ )
printf("%lf\t", UU[i*NX+j]);
printf("\n");
}
return 0;
}
Hasil
Jadi, terkadang Anda dapat mencoba memparalelkan program bahkan dalam kasus yang terdiri dari fragmen berurutan ketat, dan bahkan mendapatkan hasil positif dalam percepatan (dalam percobaan saya, percepatan ditingkatkan dari 15 menjadi 50%). Semoga artikel singkat ini bermanfaat bagi seseorang.