في هذه الحالة ، ينطلقون عادةً من فكرة أن الموازاة يجب ألا تؤثر بطريقة ما على نتائج تنفيذ البرنامج. هذا مطلب صعب ولكنه عادل في كثير من الحالات. ومع ذلك ، إذا حاولنا موازنة برنامج يقوم ببعض العمليات الحسابية بالطرق العددية (نقوم بتدريب شبكة عصبية ، أو محاكاة ديناميكيات مائع أو نظام جزيئي ، أو حل المعادلات التفاضلية العادية أو مشاكل التحسين) ، فستكون النتيجة (على أي حال) بعض الأخطاء. لذلك ، لماذا لا يتم تطبيق تقنيات موازية "محفوفة بالمخاطر" ، والتي يمكن أن تؤدي إلى خطأ إضافي صغير في الحل الرياضي ،ولكن هل تسمح لك بالحصول على مزيد من التسارع الإضافي؟ ستتم مناقشة إحدى هذه التقنيات - تقسيم أجسام الحلقة مع التنبؤ بالنتائج الوسيطة والتراجع في حالة التنبؤ غير الناجح (في الواقع ، هذه حسابات "مفرطة التفاؤل" في ذاكرة المعاملات جزئيًا).
فكرة الموازية
لنفترض أن لدينا دورة ، يتكون جسمها من جزأين متتاليين ، والجزء الثاني يعتمد على الأول. دع الحلقات الفردية للدورة تعتمد على بعضها البعض. على سبيل المثال:
for (int i = 0; i < N; i++) {
x = f(y);
y = g(x);
}
للوهلة الأولى ، لا يمكن موازاة مثل هذه الحلقة. ومع ذلك ، سنحاول. دعنا نحاول تنفيذ العاملين الأول والثاني لجسم الحلقة بالتوازي. تكمن المشكلة في أنه في وقت حساب g (x) x يجب أن تكون معروفة ، ولكن سيتم حسابها فقط في نهاية الجزء الأول. حسنًا ، دعنا نقدم مخططًا سيحاول في بداية الجزء الثاني التنبؤ بقيمة x الجديدة. يمكن القيام بذلك ، على سبيل المثال ، بمساعدة التنبؤ الخطي ، الذي "يتعلم" التنبؤ بقيمة جديدة لـ x ، بناءً على "تاريخ" التغيير. ثم يمكن قراءة الجزء الثاني بالتوازي مع الجزء الأول (هذا هو "المبالغة في التفاؤل") ، وعندما يتم حساب كلاهما ، قارن القيمة المتوقعة لـ x بالقيمة الحقيقية التي تم الحصول عليها في نهاية الجزء الأول. إذا كانت متساوية تقريبًا ، فيمكن قبول نتيجة الحسابات لكلا الجزأين (وانتقل إلى التكرار التالي للحلقة).وإذا كانت مختلفة تمامًا ، فلن يلزم إعادة سرد سوى الجزء الثاني. مع هذا المخطط ، في بعض الحالات ، سنحصل على موازاة خالصة ، في الباقي - العدد المتسلسل الفعلي. خوارزمية تنفيذ الحلقة هي كما يلي:
for (int i = 0; i < N; i++) {
{
1 – x = f(y). x;
2 – x* y* = g(x*). x x*. , y = y* . , : y = g(x).
}
}
الخوارزمية الأساسية واضحة. يكون التسارع النظري مرتين ، ولكنه في الممارسة سيكون أقل بالطبع ، لأن: أ) يتم تخصيص جزء من الوقت للتنبؤات والتنسيق ؛ ب) لن يتم تنفيذ جميع التكرارات بشكل متوازٍ ؛ ج) يمكن أن يكون للجزء الأول والثاني من جسم الدورة كثافة عمالة مختلفة (من الناحية المثالية ، مطلوب المساواة). دعنا ننتقل إلى التنفيذ.
تنفيذ التوازي - حوسبة مفرطة في التفاؤل
بما أن خوارزمية الموازاة تتعامل مع إلغاء بعض الحسابات (في حالة الفشل) وإعادة تنفيذها ، فمن الواضح أن هناك شيئًا من فكرة العمل في ذاكرة المعاملات. أفضل - في المعاملات الجزئية ، حيث تعمل بعض المتغيرات وفقًا لنظام ذاكرة المعاملات ، وتعمل بقية المتغيرات كالمعتاد. يمكن تنظيم نقل البيانات من الجزء الأول إلى الجزء الثاني باستخدام بعض القنوات الخاصة. اجعل هذه القناة تنبؤية: أ) إذا كانت البيانات قد تم إرسالها بالفعل إلى القناة في وقت الاستقبال ، ثم تتم قراءتها منها ، ب) إذا لم تكن البيانات قد وصلت إلى القناة في وقت الاستقبال ، فإنها تحاول التنبؤ بهذه البيانات وإرجاع نتيجة التنبؤ. ستعمل هذه القناة وفقًا لمخطط غير معتاد إلى حد ما لذاكرة المعاملات التقليدية:إذا كان هناك في نهاية معاملة الجزء الثاني من الدورة تناقض بين البيانات المستلمة في القناة والبيانات التي تنبأت بها ، عندئذٍ يتم إلغاء معاملة الجزء الثاني من الدورة وإعادة تنفيذها ، ولن تتم قراءة "التنبؤات" من القناة ، ولكن يتم تلقي البيانات بالفعل. ستبدو الدورة كما يلي:
for (int i = 0; i < N; i++) {
, {
1 ( 1):
x = f(y);
_.put(x);
2 ( 2):
_.get(x);
y = g(x);
}
}
منجز. اهتمت القناة بتنبؤ البيانات ، في حين اهتمت ذاكرة المعاملات جزئيًا بإلغاء الحسابات في حالة التنبؤ المفرط في التفاؤل.
بعض التطبيقات المفيدة: الشبكات العصبية ، طريقة الجسيمات في الخلية
يمكن استخدام مثل هذا المخطط لموازنة جسم الحلقة في عدد من الخوارزميات الرياضية ، على سبيل المثال ، عند نمذجة عدسة كهروستاتيكية باستخدام طريقة الجسيمات في الخلية ، وكذلك عند تدريب شبكة عصبية تلقائية باستخدام طريقة الانتشار العكسي. المهمة الأولى خاصة جدًا ، لذا لن أناقشها هنا ، سأقول فقط إن النهج الموصوف للتوازي أعطى تسارعًا بنسبة 10-15٪. لكن المهمة الثانية أصبحت أكثر شيوعًا بالفعل ، لذلك من الضروري ببساطة قول بضع كلمات عنها.
تتضمن الدورة التدريبية للشبكة العصبية تمريرة متسلسلة من خلال أزواج التدريب ، ولكل زوج ، يتم إجراء تحرك للأمام (حساب ناتج الشبكة) وحركة عكسية (تصحيح الأوزان والتحيزات). هذان هما الجزءان من جسم الحلقة لأزواج التدريب ، وللموازنة بينهما ، يمكنك تطبيق النهج أعلاه (بالمناسبة ، يمكن أيضًا تطبيقه بتمريرة متوازية من خلال أزواج التدريب ، مع تغييرات طفيفة). نتيجة لذلك ، في مهمة تدريب شبكة عصبية نموذجية ، حصلت على مكاسب بنسبة 50٪ في الأداء.
أتمتة موازاة برامج C
إن فكرة الحسابات فائقة التفاؤل ليست صعبة للغاية ، لذلك تمت كتابة برنامج مترجم خاص يتعامل مع الموازاة التلقائية - فهو يجد حلقات في برنامج C الأصلي يمكن لمثل هذا التوازي أن يعطي نتيجة إيجابية ويقسم أجسامهم إلى جزأين ، وإدخال توجيهات OpenMP الضرورية ، وإيجاد المتغيرات المحتملة للقنوات ، وربط مكتبة للعمل مع ذاكرة المعاملات جزئيًا والقنوات التنبؤية ، وفي النهاية ، إنشاء برنامج إخراج متوازي.
على وجه الخصوص ، تم تطبيق مثل هذا المترجم على برنامج محاكاة العدسة الكهروستاتيكية. سأقدم كلا البرنامجين - البرنامج الأصلي (الذي يتضمن توجيهًا يشير إلى موازاة الحلقات) والآخر الذي تم الحصول عليه بعد الترجمة.
البرنامج الأصلي:
#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;
}
برنامج موازٍ تلقائيًا
#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;
}
النتيجة
لذلك ، في بعض الأحيان يمكنك محاولة مواءمة البرنامج حتى في الحالات التي يتكون فيها من أجزاء متسلسلة بدقة ، وحتى الحصول على نتائج إيجابية في التسريع (في تجاربي ، تمت زيادة السرعة من 15 إلى 50٪). آمل أن تكون هذه المقالة القصيرة مفيدة لشخص ما.