الجلسة الثالثة - Eng . Rami Mahfoud

Report
‫البرمجة التفرعية‬
‫الجلسة الثالثة‬
‫‪Eng. rami mahfoud http://irami.im‬‬
‫‪Collective Communication‬‬
‫توابع االتصال الجماعية‬
‫• باإلضافة إلى توابع االتصال من النمط ‪ Point-To_Point‬السابقة‬
‫(‪ ،)Send, Receive‬تقدم الـ ‪ MPI‬مجموعة أخرى من توابع االتصاالت‬
‫الجماعية ‪.Collective Communication‬‬
‫‪‬هذه المجموعات تسمح بعمل سلسلة من توابع االتصال ‪ point-to point‬في‬
‫تعليمة واحدة‬
‫‪‬االتصال الجماعي غالبا ما يشترك فيه كل ال ‪ Processes‬الموجودة في بئية‬
‫االتصال ‪. communicatio‬‬
‫‪‬من أجل كل ‪ process‬ينتهي استدعاء التابع عندما تتم عملية نقل البيانات‬
‫‪‬إدراة ال ‪ tag‬في توابع االتصال هذه تتم بشكل شفاف وداخلي ضمن التوابع وال‬
‫داعي لتعريفها ضمن التابع‬
‫‪2‬‬
‫أنواع توابع االتصال الجماعي‬
‫هناك ثالثة أصناف من توابع االتصال الجماعي ‪:‬‬
‫❶التوابع التي تضمن التزامن العام )‪MPI_Barrier() : (global synchronizations‬‬
‫❷التوابع التي تقوم بنقل البيانات بين اإلجرائات ‪:‬‬
‫‪‬التوزيع العام للبيانات )(‪MPI_Bcast‬‬
‫‪‬التوزيع المحدد للبيانات أي تقسيم البيانات على اإلجرائيات ( ‪MPI_Scatter( ) : )Process‬‬
‫‪‬تجميع البيانات الموزعة ‪MPI_Gather( ) :‬‬
‫‪‬التجميع بواسطة جميع اإلجراءات التي تحوي البيانات الموزعة أي التجميع ضمن جميع اإلجرائيات ‪:‬‬
‫)(‪MPI_Allgather‬‬
‫‪‬توزيع محدد بواسطة جميع االجرائات التي تحوي بيانات مخصصة أي كل إجرائية تقوم بعمليه توزيع‬
‫للكل ‪MPI_Alltotal() :‬‬
‫❸التوابع التي باألضافة إلى إدارة االتصاالت تقوم بتنقيذ عمليات على البيانات التي تنقل وهي ‪:‬‬
‫‪‬توابع االخترال ( التخفيض ) (‪ ) reduction operations‬مثل ( الجمع – الضرب – القيمة العظمى‬
‫– القيمة الصغرى و غيرها من العمليات القياسية أو القيام بعمليات يعرفها المستخدم ) والتابع هو ‪:‬‬
‫)(‪MPI_Reduce‬‬
‫‪‬تابع يقوم باألضافة إلى االخترال بإرسال القيمة الناتجة إلى كل اإلجرائيات ‪ process‬أي هو فعليا‬
‫)(‪ MPI_Reduce‬ثم )(‪ MPI_Bcast‬والتابع هو )(‪MPI_Allreduce‬‬
‫‪ Broadcast‬البث العام‬
‫•‬
‫ابسط أنواع توابع مجموعات االتصال هو البث العام (‪ .) Broadcast‬في البث العام (‪) Broadcast‬‬
‫تقوم ‪ Process‬وحيدة بإرسال نسخة من نفس البيانات إلى كل ال ‪ Processes‬في مجال االتصال‬
‫‪.‬الصورة التالية توضح العملية ‪ .‬التابع الذي يحقق البث العم في ال ‪ MPI‬هو ) (‪. MPI_Bcast‬‬
‫‪ Broadcast‬البث العام‬
‫•‬
‫حيث أننا نالحظ انه بعد استدعاء التابع في االجرائية رقم ‪ 2‬تصبح القيمة ‪ A‬موجودة في جميع‬
‫ال (‪)Processes‬‬
‫‪ Broadcast‬البث العام‬
‫• الصيغة العامة للتابع )(‪MPI_Bcast‬‬
‫‪int MPI_Bcast(void *buf, / **** in / out ****/‬‬
‫‪int count, / *** in ***/‬‬
‫‪MPI_Datatype datatypem , /**** in ****/‬‬
‫‪int root, /***** in ****/‬‬
‫)‪MPI_Comm comm /**** in ****/‬‬
‫‪ : buf ‬موقع الذاكرة لبداية عناصر الرسالة المرسلة‬
‫‪ :coun ‬عدد عناصر الرسالة‬
‫‪ : datatypem ‬نمط بيانات عناصر الرسالة‬
‫‪ :root ‬رتبة اإلجرائية الجذر‬
‫‪ : comm ‬بنية الاتصال‬
‫‪ Broadcast‬البث العام‬
‫• الصيغة العامة للتابع )(‪MPI_Bcast‬‬
‫)‪int MPI_Bcast(void *buf, int count, MPI_Datatype ,datatypem int root, MPI_Comm comm‬‬
‫يقوم هذا التابع بإرسال البيانات املوجودة يف الـ ‪ buffer‬على الـ ‪ process‬ذات الـ ‪ rank‬املساوي للـ ‪ root‬يف‬
‫الـ ‪ communicator‬إىل كل إجرائية ‪ process‬يف ذلك الـ ‪.communicator‬‬
‫وال يتم االستقبال هنا بواسطة اإلجراء ‪ ،MPI_Recv‬وإمنا عن طريق استدعاء الروتني ‪ MPI_Bcast‬نفسه وبنفس قيم‬
‫البارامرتات‪ ،‬وعندها تتم معرفة العملية املرسلة من املستقبلة بواسطة مقارنة قيمة الـ ‪ rank‬للعملية اليت تنفذ مع البارامرت ‪ root‬فإذا كانا‬
‫متساويني تكون العملية يف حالة إرسال‪ ،‬وفيما عدا ذلك تكون يف حالة استقبال‪.‬‬
‫يعد استخدام روتني البث اجلماعي أكثر سرعة وفعالية من حيث اختزال النص الربجمي‪ ،‬ومن حيث الزمن املستغرق يف عملية االتصال‪.‬‬
‫كمثال على استخدام اإلجراء السابق‪ ،‬بفرض لدينا جمموعة من احلواسيب مربوطة بشبكة‪ ،‬كل من هذه احلواسيب تنفذ نفس العملية‪،‬‬
‫ستتوىل عملية رئيسية توزيع املدخالت على العمليات األخرى اليت ستقوم بإجناز العمل املطلوب‪.‬‬
‫‪ Broadcast‬البث العام‬
‫• مثال ‪ :‬الربنامج يقوم بتوليد مصفوفة من ‪ 5‬أعداد عشوائية بني ‪ 0‬و ‪ 999‬يف العقدة رقم ( ‪ ) 0‬مث يتم توزيع‬
‫هذه املصفوفة على مجيع اإلجرائيات يف بيئة االتصال مع طباعة املصفوفة املستقبلة يف كل إجرائية‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv)
{
int mynode,totalnodes;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&totalnodes);
MPI_Comm_rank(MPI_COMM_WORLD,&mynode);
int a[5];
cout<<"my rank is:"<<mynode<<endl;
if(mynode==0){
for(int i=0;i<5;i++){
a[i]=rand()%1000;
}
}
cout<<"before Bcast a is "<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
MPI_Bcast(a,5,MPI_INT,0,MPI_COMM_WORLD);
cout<<endl<<"after Bcast a is "<<endl;
for(int i=0;i<5;i++){
cout<<a[i]<<" ";
}
cout<<endl;
system("pause");
MPI_Finalize();
}
‫‪ Scatter‬البعثرة‬
‫• ترسل بيانات مختلفة من ال ‪ process‬الجذر نحو ال‬
‫‪ processes‬األخرى والتابع الذي يحقق هذا الشئ في ال‬
‫‪MPI‬هو )( ‪ MPI_Scatter‬وهي فعليا عملية تقسيم البيانات‬
‫من ال ‪ process‬الجذر نحو جميع ال ‪processes‬‬
‫‪ Scatter‬البعثرة‬
‫‪int MPI_Scatter( void* send_buffer,‬‬
‫‪int send_count,‬‬
‫‪MPI_Datatype send_type,‬‬
‫‪void* received_buffer,‬‬
‫‪int receive_count,‬‬
‫‪MPI_Datatype receive_type,‬‬
‫)‪int root, MPI_Comm comm‬‬
‫عند استدعاء اإلجراء السابق‪ ،‬تقوم الـ ‪ Process‬ذات الرتبة ‪ root‬بتوزيع حمتويات ال‬
‫ـ‪ send_buffer‬بني العمليات‪ .‬حيث يتم إرسال ‪ send_count‬عنصر إىل كل عملية (جيب أن‬
‫يكون الـ ‪ send_count‬عدد صحيح موجب)‪ .‬ونشري هنا إىل أن السطر األول من البارامرتات ذو‬
‫أمهية فقط من جهة الـ ‪.root‬تقوم كل عملية من العمليات املوجودة يف جمال االتصال احملدد‬
‫(‪ )comm‬باستقبال حصتها (املقدرة بـ ‪ )receive_count‬من املعطيات وختزينها يف الـ‬
‫‪.received_buffer‬‬
‫‪ Scatter‬البعثرة‬
‫مثال ‪:‬‬
‫يقوم الربنامج التايل بتعريف وهتيئة مصفوفة من األعداد الصحيحة‪ ،‬ومن مث توزيعها بالتساوي بني كافة‬
‫العمليات يف جمال االتصال‪:‬‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv)
{
int sendArray[12];
int receiveArray[12];
int processesNumber;
int currentProcess;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD,&processesNumber);
MPI_Comm_rank(MPI_COMM_WORLD,&currentProcess);
if((12%processesNumber)!=0)
{
MPI_Finalize();
return;
}
if(currentProcess==0){
for(int i=0;i<12;i++){
sendArray[i]=i+1;
}
}
MPI_Scatter(sendArray,12/processesNumber,MPI_INT,receiveArray,12/processesNumber,MPI_INT,0,MPI_COMM_WORLD);
cout<<"Process "<<currentProcess<<" has"<<endl;
for(int i=0;i<12/processesNumber;i++)
cout<<receiveArray[i]<<" ";
cout<<endl;
system("pause");
MPI_Finalize();
}
‫‪ Gatther‬التجميع‬
‫مثال ‪:‬‬
‫هنا يتم جتميع بيانات خمتلفة من ‪process‬خمتلفة وجتمعيها يف ال ‪ proess‬اجلذر كما يف الصورة التالية والتابع الذي يقوم هبذا الشئ يف‬
‫ال ‪ MPI‬هو ‪:‬‬
‫) (‪MPI_Gather‬‬
‫ التجميع‬Gatther
int MPI_Gather ( void* send_buffer,
int send_count,
MPI_Datatype send_type,
void* received_buffer,
int receive_count,
MPI_Datatype receive_type,
int root, MPI_Comm comm)
:‫ له الصيغة التالية‬MPI_Gather ‫اإلجراء‬
‫ يف جمال االتصال‬send_buffer‫ بإرسال حمتويات الـ‬process ‫ ستقوم كل‬، ‫عند تنفيذ هذا التابع‬
‫ ذات‬process ‫ وعندها تقوم الـ‬.root ‫ املساوي لـ‬rank ‫ ذات الـ‬process ‫ إىل الـ‬comm
.‫ للبيانات املستقبَلة برتتيب تصاعدي‬Concating ‫ بعملية وصل‬root ‫الرتتيب‬
MPI_Scatter ‫ اإلجراء العكس لإلجراء‬MPI_Gather ‫وميكن اعتبار اإلجراء‬
‫‪ Gatther‬التجميع‬
‫مثال ‪ :‬يقوم البرنامج التالي بتجميع عدة مصفوفات في مصفوفة واحدة‪:‬‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv)
{
int sendArray[12];
int receiveArray[12];
int processesNumber;
int currentProcess;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD,&processesNumber);
MPI_Comm_rank(MPI_COMM_WORLD,&currentProcess);
if((12%processesNumber)!=0)
{
MPI_Finalize();
return;
}
for(int i=0;i<12/processesNumber;i++)
sendArray[i]=(12/processesNumber)*currentProcess+i;
MPI_Gather(sendArray,12/processesNumber,MPI_INT,receiveArray,12/processesNumber,MPI_INT,0,M
PI_COMM_WORLD);
if(currentProcess==0)
{
for(int i=0;i<12;i++)
cout<<receiveArray[i]<<" ";
cout<<endl;
}
MPI_Finalize();
}
‫‪ Gatther‬التجميع‬
‫مثال‪ :‬يف مثال برنامج حساب األعداد األولية الذي أخذ مسبقا بدال من طباعة األعداد األولية يف كل إجرائية قم بإرسال األعداد األولية‬
‫اخلمسة أألوىل احملسوبة يف كل إجرائية إىل إجرائية واحدة وطباعتهم يف تلك اإلجرائية ويف حال كان العدد احملسوب أقل من ‪5‬متلىئ الرسالة‬
‫املرسلة ب ‪ 1-‬حىت تصبح حجم الرسالة املرسلة ‪5‬واجملال هنا هو ‪ 5000‬و ‪. 6000‬‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv){
int mynode, totalnodes;
int x=5000;
int y=6000;
int primeA[1000];
int primteN[5];
int countP=0;
int startval,endval;
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &totalnodes); // get totalnodes
MPI_Comm_rank(MPI_COMM_WORLD, &mynode);
// get mynode
int lin=y-x;
startval = (lin*(mynode))/totalnodes+x;
endval =(lin*(mynode+1))/totalnodes+x;
for(int i=startval;i<=endval;i++){
bool t=true;
for(int m=2;m<i;m++){
if(i%m==0){
t=false;
break;
}
}
if(countP==5) break;
if(t){
primteN[countP]=i;
countP++;
}
}
if(countP<5){
for(int j=countP;j<5;j++)
primteN[j]=-1;
}
cout<<"the 5 prime in process "<<mynode<<" is:"<<endl;
for(int i=0;i<5;i++)
cout<<primteN[i]<<" ";
cout<<endl;
MPI_Gather(primteN,5,MPI_INT,primeA,5,MPI_INT,0,MPI_COMM_WORLD);
if(mynode==0){
cout<<endl<<"Recevie array is "<<endl;
for(int u=0;u<totalnodes*5;u++){
cout<<primeA[u]<<" ";
}}
system("pause");
MPI_Finalize();
}
‫‪Gather-to-all : MPI_Allgather‬‬
‫هذا التابع يقوم أوال بتجميع البيانات في جميع اإلجرائيات بدال من تجـمعيها في الـ ‪ process‬الجذر أي فعليا هو يعادل‬
‫استدعاء ‪ MPI_gather‬ثم ‪ MPI_bcast‬أو ( استدعاء ‪ MPI_gather‬بعدد مرات ال ‪processes‬‬
‫ويكون مجال ‪ root process‬من ‪ 0 – n-1‬حيث ‪ n‬عدد ال ‪)processes‬‬
Gather-to-all : MPI_Allgather
‫الصيغة العامة للتابع‬
int MPI_Allgather(void *sendbuf ,
int sendcount ,
MPI_Datatype sendtype ,
void *recvbuf,
int recvcount ,
MPI_Datatype recvtype,
MPI_Comm comm(
‫ بإرسال حمتويات الـ‬process ‫ ستقوم كل‬، ‫عند تنفيذ هذا التابع‬
‫ وعندها‬. processe‫ إىل كل الـ‬comm ‫يف جمال االتصال‬send_buffer
‫ للبيانات املستقبَلة برتتيب‬Concating ‫ بعملية وصل‬process ‫تقوم كل‬
.‫تصاعدي‬
‫‪Gather-to-all : MPI_Allgather‬‬
‫مثال ‪ :‬البرنامج التالي يقوم بتوزيع قيم عشوائية بعدد اإلجرائيات على جميع اإلجرائيات حيث كل إجرائية تولد رقم‬
‫عشوائي ويتم إرسال إلى جميع اإلجرائيات‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv){
int mynode, totalnodes;
int myrand;
int a[100];
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &totalnodes); // get totalnodes
MPI_Comm_rank(MPI_COMM_WORLD, &mynode); // get mynode
myrand=rand()%100*(mynode+1);
MPI_Allgather(&myrand,1,MPI_INT,a,1,MPI_INT,MPI_COMM_WORLD);
cout<<"Processor "<<mynode<<" rand is "<<myrand<<endl;
for(int i=0;i<totalnodes;i++)
cout<<a[i]<<" ";
cout<<endl;
system("pause");
MPI_Finalize();
}
‫‪MPI_Alltoall‬‬
‫هذا التابع يقوم بنقل البيانات من كل ال ‪ process‬إلى كل ال ‪ process‬كما في المخطط التالي أي‬
‫فعليا يمكن القول أنه عبارة مجموعة توابع ‪ MPI_Scatter‬بحيث يكون قيم ‪ root‬من‬
‫‪ 0‬إلى ‪ n-1‬حيث ‪ n‬هو عدد اإلجرائيات‬
MPI_Alltoall
int MPI_Alltoall(void *sendbuf ,
int sendcount ,
MPI_Datatype sendtype ,
void *recvbuf,
int recvcount,
MPI_Datatype recvtype,
MPI_Comm comm(
process ( ‫ الموجود في كل‬sendbuf ‫ من كل‬sendcount ‫يتم هنا توزيع‬
‫ من كل‬recvcount ‫ تأخذ‬process ‫ حيث كل‬process ‫) إلى كل ال‬
‫ أكبر من حجم المصفوفة‬process ‫ وفي حال كان عدد ال‬porocess
‫ على‬process ‫الموزعة تحدث مشكلة حيث يؤدي ذلك إلى عدم حصول‬
‫حصتها من الرسالة المرسلة‬
MPI_Alltoall
int MPI_Alltoall(void *sendbuf ,
int sendcount,
MPI_Datatype sendtype ,
void *recvbuf,
int recvcount,
MPI_Datatype recvtype,
MPI_Comm comm(
‫ وليس عدد‬process ‫ هو عدد العناصر التي ترسل لكل‬: sendcount •
. sendbuf ‫العناصر الموجودة في ال‬
•
‫ وليس العدد‬process ‫ عدد العناصر المستقبلة من قبل كل‬:recvcount •
. ‫الكلي للعناصر السمتقبلة‬
‫• في جميع أمثلتنا‬
sendcount=recvcount, sendtype=recvtype
‫‪MPI_Alltoall‬‬
‫مثال ‪ :‬البرنامج التالي يقوم بتوزيع محتويات مصفوفة اسمها ‪ a‬موجودة في كل ‪process‬‬
‫على جميع ال ‪ processes‬األخرى بحيث تحوي المصفوفة خمسة عناصر تمثل مضاعفات‬
‫رتبة ( ‪ ) rank‬ال ‪ process‬وعدد اإلجرائيات هنا هو ‪5‬‬
#include<iostream>
#include<mpi.h>
using namespace std;
void main(int argc, char** argv){
int mynode, totalnodes;
int a[5];
int b[5000];
MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &totalnodes); // get
totalnodes
MPI_Comm_rank(MPI_COMM_WORLD, &mynode); // get mynode
for(int i=0;i<5;i++)
a[i]=mynode*(i+1);
MPI_Alltoall(a,1,MPI_INT,b,1,MPI_INT,MPI_COMM_WORLD);
cout<<"Processor "<<mynode<<" array is "<<endl;
for(int i=0;i<5;i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"Processor "<<mynode<<" Receve array is "<<endl;
for(int i=0;i<5;i++)
cout<<b[i]<<" ";
cout<<endl;
system("pause");
MPI_Finalize();
}
‫وظيفة‬
‫• اكتب برنامج تفرعي إلنجاز عملية البحث عن عدد داخل‬
‫مصفوفة من األعداد الصحيحة‪.‬‬

similar documents