Флинна таксономиясы. МISD, МIMD архитектуралары. По Флинну принято классифицировать все возможные архитектуры компьютеров на четыре категории:
По Флинну принято классифицировать все возможные архитектуры компьютеров на четыре категории:
SISD (Single Instruction Stream - Single Data Stream) – одинпотоккомандиодинпотокданных;
SIMD (Single Instruction Stream –Multiple Data Stream) – одинпотоккомандимножествопотоковданных;
MISD (Multiple Instruction Stream –Single Data Stream) – множествопотоковкомандиодинпотокданных;
MIMD (Multiple Instruction Stream –Multiple Data Stream) –множествопотоковкомандимножествопотоковданных
MISD компьютеры
Вычислительных машин такого класса практически нет и трудно привести пример их успешной реализации. Один из немногих – систолический массив процессоров, в котором процессоры находятся в узлах регулярной решетки, роль ребер которой играют межпроцессорные соединения. Все процессорные элементы управляются общим тактовым генератором. В каждом цикле работы каждый процессорный элемент получает данные от своих соседей, выполняет одну команду и передает результат соседям
MIMD компьютеры
Эта категория архитектур вычислительных машин наиболее богата, если иметь в виду примеры ее успешных реализаций. В нее попадают симметричные параллельные вычислительные системы, рабочие станции с несколькими процессорами, кластеры рабочих станций и т.д. Уже довольно давно появились компьютеры с несколькими независимыми процессорами, но вначале на таких компьютерах был реализован только параллелизм заданий, то есть на разных процессорах одновременно выполнялись разные и независимые программы.
2.MPI программасын компиляциялау, жинау және орындау.
Поскольку MPI является библиотекой, то при компиляции программы необходимо соответствующие библиотечные модули. Это можно сделать в командной строке или воспользоваться предусмотренными в большинстве систем командами или скриптами mpicc(для программ на языке СИ), mpic++(для программ на языке С++ ), и mpif77/mpif90(для программ на языке Фортран 77/90). Опция компилятора «-oname» позволяет задать имя name для получаемого выполнимого файла, по умолчанию выполнимый файл называется a.out, например: mpif77 –oprogramprogram.f
После получения выполнимого файла необходимо запустить его на требуемом количестве процессов. Для этого обычно предоставляется команда запуска MPI –приложения mpirun,mpiexec, например :
mpirun –npN<программа с аргументами>
mpiexec –npN<программа с аргументами>
где N-число процессов ,которое должно быть не более разрешенного в данной системе числа процессов для одной задачи. После запуска одна и та же программа будет выполняться всеми запущенными процессами, результат выполнения в зависимости от системы будет выдаваться на терминал или записываться в файл предопределенным именем.
3.Гаусс-Зейдель тәсілінің параллельді түрі. 2 өлшемді Лаплас теңдеуін 1 өлшемді декомпозициялау (Параллельді Гаусс-Зейдель тәсілі).
constint N=100;
float P[N][N],
h=0.01, //шаг сетки
eps=0.01, //точность
max, //норма
**p, //текущая итерация
**pp, //предыдущая итерация
a[N],b[N]; //вспомогательные векторы
inti,j,
c, //кол-во строк матрицы на каждом процессоре
stop = 1; //условие заверщения цикла
intrank,size;
MPI_Init(&argc,&argv);
MPI_Status status;
MPI_Comm_rank(MPI_COMM_WORLD,&rank);
MPI_Comm_size(MPI_COMM_WORLD,&size);
if(rank<N%size)
{
c=N/size+1;
}else
{
c=N/size;
}
p=newfloat*[c];
pp=newfloat*[c];
for(i=0;i<c;i++)
{
p[i]=newfloat[N];
pp[i]=newfloat[N];
p[i][0]=1;
pp[i][0]=1;
for(int j=1;j<N;j++)
{
p[i][j]=0;
pp[i][j]=0;
}
}
if(rank==0) {
do {
if(size>1) {
MPI_Send(&p[c-1][0],N,MPI_FLOAT,rank+1,
0,MPI_COMM_WORLD);
MPI_Recv(a,N,MPI_FLOAT,rank+1,size,
MPI_COMM_WORLD, &status);
}max=0.0;
for(i=1;i<c-1;i++) {
for(j=1;j<N-1;j++) {
p[i][j]=(pp[i+1][j]+p[i-1][j]+pp[i][j+1]+p[i][j-1])/4;
if(max<fabs(p[i][j]-pp[i][j])) {
max=fabs(p[i][j]-pp[i][j]); }}}
if(size>1) {
for(j=1;j<N-1;j++) {
p[c-1][j]=(p[c-2][j]+a[j]+pp[c-1][j+1]+p[c-1][j-1])/4;
if(max<fabs(p[c-1][j]-pp[c-1][j])) {
max=fabs(p[c-1][j]-pp[c-1][j]); } }
Float maxx;
for(i=1;i<size;i++) {
MPI_Recv(&maxx,1,MPI_FLOAT,i,2*size,MPI_COMM_WORLD,&status);
if(maxx>max) {
max=maxx; } } }
if(max<=eps) {
stop=0; }
if(size>1) {
for(i=1;i<size;i++) {
MPI_Send(&stop,1,MPI_INT,i,3*size,MPI_COMM_WORLD); } }
for(i=0;i<c;i++) {
for(j=0;j<N;j++) {
pp[i][j]=p[i][j]; } }}
while(stop==1);
for(i=0;i<c;i++) {
for(int j=0;j<N;j++) {
P[i][j]=p[i][j]; } }
if(size>1) {
intjj=c-1;
for(i=1;i<size;i++) {
MPI_Recv(&c,1,MPI_INT,i,4*size,MPI_COMM_WORLD,&status);
for(j=0;j<c;j++) {
jj++; MPI_Recv(&P[jj][0],100,MPI_FLOAT,i,5*size,MPI_COMM_WORLD,&status); } } }
ofstream out("result.txt");
for(i=0;i<N;i++){
for(int j=0;j<N;j++){
out<<P[i][j]<<'\t'; //вывожу в результаты в фаил
} out<<'\n'; }}
if(rank==size-1&&size>1) {
do {
MPI_Recv(b,N,MPI_FLOAT,rank-1,0,MPI_COMM_WORLD,&status);
MPI_Send(&p[0][0],N,MPI_FLOAT,rank-1,size,MPI_COMM_WORLD); max=0;
for(i=1;i<c-1;i++) {
for(j=1;j<N-1;j++) {
p[i][j]=(pp[i+1][j]+p[i-1][j]+pp[i][j+1]+p[i][j-1])/4;
if(max<fabs(pp[i][j]-p[i][j])) {
max=fabs(pp[i][j]-p[i][j]); } } }
for(j=1;j<N-1;j++) {
p[0][j]=(pp[1][j]+b[j]+pp[0][j+1]+p[0][j-1])/4;
if(max<fabs(pp[0][j]-p[0][j])) {
max=fabs(pp[0][j]-p[0][j]); } }
MPI_Send(&max,1,MPI_FLOAT,0,2*size,MPI_COMM_WORLD);
for(i=0;i<c;i++) {
for(j=0;j<N;j++) {
pp[i][j]=p[i][j]; } }
MPI_Recv(&stop,1,MPI_INT,0,3*size,MPI_COMM_WORLD,&status);
}while(stop==1);
MPI_Send(&c,1,MPI_INT,0,4*size,MPI_COMM_WORLD);
for(i=0;i<c;i++) {
MPI_Send(&p[i][0],N,MPI_FLOAT,0,5*size,MPI_COMM_WORLD); } }
if(rank>0&&rank<size-1) {
do {
MPI_Recv(b,N,MPI_FLOAT,rank-1,0,MPI_COMM_WORLD,&status);
MPI_Send(&p[c-1][0],N,MPI_FLOAT,rank+1,0,MPI_COMM_WORLD);
MPI_Recv(a,N,MPI_FLOAT,rank+1,size,MPI_COMM_WORLD,&status);
MPI_Send(&p[0][0],N,MPI_FLOAT,rank-1,size,MPI_COMM_WORLD);
max=0; int ii;
if(rank<N%size||100%size==0) {
ii=rank*c; }
if(rank>N%size&&100%size!=0) {
ii=(N%size)*(c+1)+(rank-N%size)*c; }
for(i=1;i<c-1;i++) {
for(j=1;j<N-1;j++) {
p[i][j]=(pp[i+1][j]+p[i-1][j]+pp[i][j+1]+p[i][j-1])/4;
if(max<fabs(pp[i][j]-p[i][j])) {
max=fabs(pp[i][j]-p[i][j]); } } }
for(j=1;j<N-1;j++) {
p[0][j]=(pp[1][j]+b[j]+pp[0][j+1]+p[0][j-1])/4;
if(max<fabs(pp[0][j]-p[0][j])) 1111{
max=fabs(pp[0][j]-p[0][j]); }
p[c-1][j]=(p[c-2][j]+a[j]+pp[c-1][j+1]+p[c-1][j-1])/4;
if(max<fabs(pp[c-1][j]-p[c-1][j])) {
max=fabs(pp[c-1][j]-p[c-1][j]); } }
MPI_Send(&max,1,MPI_FLOAT,0,2*size,MPI_COMM_WORLD);
for(i=0;i<c;i++) {
for(j=0;j<N;j++) { pp[i][j]=p[i][j]; } }
MPI_Recv(&stop,1,MPI_INT,0,3*size,MPI_COMM_WORLD,&status);
}while(stop==1);
MPI_Send(&c,1,MPI_INT,0,4*size,MPI_COMM_WORLD);
for(i=0;i<c;i++) {
MPI_Send(&p[i][0],N,MPI_FLOAT,0,5*size,MPI_COMM_WORLD);} }
Сурак
1.Процесс дегеніміз не? Ағын дегеніміз не? Прцесс пен ағын айырмашылығы.
Программы MPI состоят из автономных процессов, выполняющих собственный код, написанный в стиле MIMD. Коды, выполняемые каждым процессом, не обязательно идентичны. Процессы взаимодействуют через вызовы коммуникационных примитивов MPI. Обычно каждый процесс выполняется в его собственном адресном пространстве, хотя возможны реализации MPI с разделяемой памятью. Этот документ описывает поведение параллельной программы в предположении, что для обмена используются только вызовы MPI. MPI не описывает модель исполнения для каждого процесса. Процесс может быть последовательным или многопоточным. В последнем случае необходимо обеспечить ``потоковую безопасность'' (``thread-safe''). Желаемое взаимодействие MPI с потоками должно состоять в том, чтобы разрешить конкурирующим потокам выполнять вызовы MPI, и вызовы должны быть реентерабельными; блокирующие вызовы MPI должны блокировать только вызываемый поток, не препятствуя планированию другого потока. MPI не обеспечивает механизмы для начального распределения процессов по физическим процессорам. Ожидается, что эти механизмы для этапа загрузки или исполнения обеспечат поставщики. Такие механизмы позволят описывать начальное число требуемых процессов; код, который должен исполняться каждым начальным процессом; размещение процессов по процессорам. Однако, существующее определение MPI не обеспечивает динамического создания или удаления процессов во время исполнения программ (общее число процессов фиксировано), хотя такое расширение предусматривается. Наконец, процесс всегда идентифицируется согласно его относительному номеру в группе, т. е. последовательными целыми числами в диапазоне 0, ..., groupsize-1.
2.MPI-да ағындардысинхронизациялау. MPI_Barrier() функциясы.
В операциях коллективного взаимодействия процессов участвуют все процессы коммуникатора. Как и для блокирующих процедур, возврат означает то, что разрешен свободный доступ к буферу приема или посылки. Сообщения, вызванные коллективными операциями, не пересекутся с другими сообщениями.
Нельзя рассчитывать на синхронизацию процессов с помощью коллективных операций. Если какой-то процесс завершил свое участие в коллективной операции, то это не означает ни того, что данная операция завершена другими процессами коммуникатора, ни даже того, что она ими начата (если это возможно по смыслу операции) =>intMPI_Barrier(MPI_Commcomm) - работа процессов блокируется до тех пор, пока все оставшиеся процессы коммуникатора comm не выполнят эту процедуру. Все процессы должны вызвать MPI_Barrier, хотя реально исполненные вызовы различными процессами коммуникатора могут быть расположены в разных местах программы. Синхронизация с помощью барьеров используется, например, для завершения всеми процессами некоторого этапа решения задачи, результаты которого будут использоваться на следующем этапе. Использование барьера гарантирует, что ни один из процессов не приступит раньше времени к выполнению следующего этапа, пока результат работы предыдущего не будет окончательно сформирован. Неявную синхронизацию процессов выполняет любая коллективная функция.
3.3 өлшемді Лаплас теңдеуін 3-өлшемді декомпозиция тәсілімен программалау.
enum {UP,DOWN,LEFT,RIGHT,FRONT,BACK};
int main( intargc, char *argv[])
{
intrank,size;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Status status;
intndims=3, reorder=0;
int dims[3]={0,0,0}, periods[3]={0,0,0},coords[3] ,nbrs[6];
MPI_Dims_create(size, ndims, dims);
MPI_Commcartcomm;
MPI_Cart_create(MPI_COMM_WORLD,ndims,dims,periods,reorder,&cartcomm);
MPI_Comm_rank(cartcomm, &rank);
MPI_Cart_coords(cartcomm, rank, 3, coords);
MPI_Cart_shift(cartcomm,0,1,&nbrs[LEFT], &nbrs[RIGHT]);
MPI_Cart_shift(cartcomm,1,1,&nbrs[DOWN], &nbrs[UP]);
MPI_Cart_shift(cartcomm,2,1,&nbrs[FRONT], &nbrs[BACK]);
inta,b,c,i,j,k,it,nit=100,n=12;
a=n/dims[0]+2;
b=n/dims[1]+2;
c=n/dims[2]+2;
float u1[a][b][c],u0[a][b][c];
float h=1.0/n,x,y,z;
for (i=0; i<a; i++) { for (j=0; j<b; j++) { for (k=0; k<c; k++) { u0[i][j][k]=0; u1[i][j][k]=0; if (nbrs[RIGHT]==-1) {u0[a-2][j][k]=1;} } } }
for (it=0; it<nit; it++)
{
for (i=1; i<a-1; i++) { for (j=1; j<b-1; j++) { for (k=1; k<c-1; k++) {
u1[i][j][k]=(u0[i-1][j][k]+u0[i+1][j][k]+u0[i][j-1][k]+u0[i][j+1][k]+u0[i][j][k-1]+u0[i][j][k+1])/6.0; } } }
MPI_Datatype UD;
MPI_Type_vector(a-2,c-2,b*c,MPI_FLOAT,&UD);
MPI_Type_commit(&UD);
MPI_Send(&u1[1][1][1],1,UD,nbrs[UP],1,MPI_COMM_WORLD);
MPI_Recv(&u1[1][b-1][1],1,UD,nbrs[DOWN],1,MPI_COMM_WORLD, &status);
MPI_Send(&u1[1][b-2][1],1,UD,nbrs[DOWN],2,MPI_COMM_WORLD);
MPI_Recv(&u1[1][0][1],1,UD,nbrs[UP],2,MPI_COMM_WORLD, &status);
MPI_Type_free (&UD);
int count=(b-2)*(a-2),p;
intaob[count],aod[count];
for (j=0; j<count; j++) {aob[j]=1; p=j/(b-2); aod[j]=c*(j+2*p); }
MPI_Datatype FB;
MPI_Type_indexed(count,aob,aod,MPI_FLOAT,&FB);
MPI_Type_commit(&FB);
MPI_Send(&u1[1][1][1],1,FB,nbrs[FRONT],3,MPI_COMM_WORLD);
MPI_Recv(&u1[1][1][c-1],1,FB,nbrs[BACK],3,MPI_COMM_WORLD, &status);
MPI_Send(&u1[1][1][c-2],1,FB,nbrs[BACK],4,MPI_COMM_WORLD);
MPI_Recv(&u1[1][1][0],1,FB,nbrs[FRONT],4,MPI_COMM_WORLD, &status);
MPI_Type_free (&FB);
MPI_Datatype LR;
MPI_Type_vector(b-2,c-2,c,MPI_FLOAT,&LR);
MPI_Type_commit(&LR);
MPI_Send(&u1[1][1][1],1,LR,nbrs[LEFT],5,MPI_COMM_WORLD);
MPI_Recv(&u1[a-1][1][1],1,LR,nbrs[RIGHT],5,MPI_COMM_WORLD, &status);
MPI_Send(&u1[a-2][1][1],1,LR,nbrs[RIGHT],6,MPI_COMM_WORLD);
MPI_Recv(&u1[0][1][1],1,LR,nbrs[LEFT],6,MPI_COMM_WORLD, &status);
MPI_Type_free (&LR);
for (i=0; i<a; i++) { for (j=0; j<b; j++) { for (k=0; k<c; k++) {
u0[i][j][k]=u1[i][j][k]; } } }
if (nbrs[FRONT]==-1)
{ for (i=1; i<a-1; i++) { for (j=1; j<b-1; j++) { u0[i][j][0]=0; u0[i][j][1]=0; } } }
if (nbrs[BACK]==-1)
{ for (i=1; i<a-1; i++) { for (j=1; j<b-1; j++) { u0[i][j][c-1]=0; u0[i][j][c-2]=0; } } }
if (nbrs[DOWN]==-1)
{ for (i=1; i<a-1; i++) { for (k=1; k<c-1; k++) { u0[i][b-1][k]=0; u0[i][b-2][k]=0; } } }
if (nbrs[UP]==-1)
{ for (i=1; i<a-1; i++) { for (k=1; k<c-1; k++) { u0[i][0][k]=0; u0[i][1][k]=0; } } }
if (nbrs[LEFT]==-1)
{ for (j=1; j<b-1; j++) { for (k=1; k<c-1; k++) { u0[0][j][k]=0; u0[1][j][k]=0; } } }
if (nbrs[RIGHT]==-1)
{ for (j=1; j<b-1; j++) { for (k=1; k<c-1; k++) { u0[a-1][j][k]=0; u0[a-2][j][k]=1; } } }
}
if (rank==0)
{ for (i=1; i<a-1; i++) { for (j=1; j<b-1; j++) { for (k=1; k<c-1; k++) {
x=float(coords[0])/float(dims[0])+(i-1)*h;
y=float(coords[1])/float(dims[1])+(b-2-j)*h;
z=float(coords[2])/float(dims[2])+(k-1)*h;
printf("u[%i][%i][%i] = %f\tx = %f\ty = %f\tz = %f\n",i,j,k,u0[i][j][k],x,y,z); } } } }
FILE *file;
int count=(a-2)*(b-2)*(c-2);
char s[count];
sprintf(s, "a%i.dat\0", rank);
file = fopen(s, "w+");
fprintf(file, "ZONE I=%i,J=%i,K=%i,F=POINT\n",a-2,b-2,c-2);
for(i=1;i<a-1;i++) { for(j=b-2;j>0;j--) { for (k=1; k<c-1; k++) {
x=float(coords[0])/float(dims[0])+(i-1)*h;
y=float(coords[1])/float(dims[1])+(b-2-j)*h;
z=float(coords[2])/float(dims[2])+(k-1)*h;
fprintf(file,"%f\t%f\t%f\t%f\n",x,y,z,u0[i][j][k]); } } }
fclose(file);
Сурак
1.В каких случаях эффективно использование параллельных методик программирования ?
В последнее время, чтобы получить возможность задействовать на практике ту дополнительную вычислительную мощность, стало необходимо задействовать параллельные вычисления. Сейчас по разным причинам производители процессоров предпочитают многоядерные архитектуры, и для получения всей выгоды от возросшей производительности ЦП программы должны переписываться в соответствующей манере. В итоге происходит неуклонное возрастание потребности в ресурсоемких расчетах, которые в ряде случаев можно выполнить только на базе высокопроизводительной техники с помощью методов параллельных вычислений. Параллельные вычисления применяются в:
1) системах поддержки проектирования (CAD – Computer Aided Design). В таких системах необходимость осуществлять моделирование в реальном масштабе времени предъявляет высокие требования к производительности программного обеспечения. 2) инженерных приложениях. К этому классу относятся разнообразные задачи из области прочностного моделирования, моделирование аварийных ситуаций и многие другие; 3) математическом моделировании физических процессов. В этот широкий класс входят задачи динамики жидкости и газа, электромагнитные и ядерные взаимодействия, процессы горения и т.п. Такие процессы, как правило, описываются системами уравнений в частных производных. 4) моделирование глобальных процессов в науках о Земле. В первую очередь, это – задачи прогноза изменения климата, предсказание природных катаклизмов. 5) вычислительной химии. Разнообразные задачи этой области направлены на изучение свойств вещества в различных состояниях. 6) бизнес-приложениях. К этой категории относятся задачи, связанные с анализом финансовых рынков и прогнозирования курсов валют. Также распространены оптимизационные задачи, по формированию наилучшего варианта использования финансовых или иных ресурсов, построения оптимальных транспортных и телекоммуникационных сетей, размещения предприятий в регионе и многие другие задачи.
2.Как можно вычислить время, которое тратится на расчет определенного участка кода в MPI?
DOUBLE PRECISION MPI_WTIME
Эта функция возвращает на вызвавшем процессе астрономическое время в секундах, прошедшее с некоторого момента в прошлом. Если некоторый участок программы окружить вызовами данной функции, то разность возвращаемых значений покажет время работы данного участка.
Пример:
int main (int argc, char **argv)
{
int rank, size,wtime;
double startwtime=0, endwtime; - началоиконецотсчёта
double s=0;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
startwtime=MPI_Wtime(); //вызываемwtime дляначала
printf ("hello world %d, size %d\n", rank, size);
endwtime=MPI_Wtime(); // вызываем wtime для завершения
printf ("time %d\n",(endwtime-startwtime)*size); //вывод времени работы данного участка
MPI_Finalize();}