????? ?????????? ?????????????? ????????????? ???????????????? :
????? ?????????? ?????????????? ????????????? ???????????????? ????? ?????????? ???????????????? ? ??????????? ???????? ? ????????? ??????. ??????????a alfa-?????? ??????????? C++, ???????????? ?????????? ??????? ???????????? ? ???????????? ???????????????? ??? ?????? ? ????? ??????? (????????????????? ?/??? ???????????? ???????????) ??????? ?????????? ???????????? ????? ??????????? — ????????? ? ????????? ??????.
???????????? ????????? ????????????? ????? ?????? ???? ???????? ????????? ??????????, ???????? ? ?????????? ????? ?????? ????????? ????????????? ?????????????????? ?? ??????? ? ?????????????? ??????????? ?????????? ? ???????, ???? ??? ???.
???????? ???????? ??? ?????????? ???????????? ???????????? ??????????. ?????????
Slide 3:
?????????? ???????? ? ?????? ????? ???????? ?????? ????????? ??????????, ?????? ???????????? ?????? ????????? ???? ?????? «????» ? «???????», ? ??????????? ????. ????????? ????????? ????????? ??????????? ? 1,5-2 ????. ????????? ????????????? ???????????????? void _Out(TreeNode * Cur) {
list<TreeNode *> Queue = list<TreeNode *>();
int LevelNodes = 1;
int NextLevelNodes = 0;
Queue.push_back(Cur);
while (!Queue.empty()) {
Cur = Queue.front();
Queue.pop_front();
cout<<Cur->Data()<<" ";
if (Cur->Left) {
Queue.push_back(Cur->Left); NextLevelNodes++;
}
if (Cur->Right) {
Queue.push_back(Cur->Right); NextLevelNodes++;
}
if (--LevelNodes==0) {
cout<<"\n";
LevelNodes = NextLevelNodes; NextLevelNodes = 0;
}
}
} ????? ?????????? ?????????????? ????????????? ???????????????? int CurLevel = 1;
reenterable Out(TreeNode * Cur, int Level) {
if (Level!=CurLevel) {
CurLevel = Level;
cout<<"\n";
}
cout<<Cur->Data()<<" ";
if (Cur->Left)
plan_last(Cur->Left,Level+1);
if (Cur->Right)
plan_last(Cur->Right,Level+1);
} 10 ?????????? 19 ?????????? ??????. ???????????? ???????? ?????? ?????? ?? ??????? ????????
??????????
Slide 4:
????????? ???????????? ????? ????????? ? ??????????? ?? ?????????
? OpenMP 2.0. ?? ??????????? «?????????» ??????? ??????????? ??????????.
??????????? ??????? ?????????? ??????? ?????????? ??? ??? ?? ?????????? ???????????, ??? ? ??? ????????????? OpenMP 3.0 ????????? ??????????? ????????????? ???????????????? int NLOCK = 0;
#pragma omp parallel num_threads(2) private(i) shared(NLOCK)
switch (omp_get_thread_num()) {
case 0:
for (i=0; i<5; i++) {
R[i][0] = 0.0;
for (j=0; j<VEC_SIZE; j++)
R[i][0] += X2[i][j]*X3[i][j];
#pragma omp atomic
NLOCK++;
#pragma omp flush(NLOCK)
}
break;
case 1:
for (i=0; i<5; i++) {
while (NLOCK<i) _Yield();
for (j=VEC_SIZE-1; j>=0; j--)
R[i][j] = X1[i][j]+R[i][0];
}
} ????? ?????????? ?????????????? ????????????? ???????????????? chain Stage0(int N, double * V1, double * V2, double * V3, double * R) throw(double * V1, double MUL, double * R) {
for (int i=0; i<N; i++, V1+=VEC_SIZE, R+=VEC_SIZE) {
double MUL = 0.0;
for (int j=0; j<VEC_SIZE; j++)
MUL += (*V2++)*(*V3++);
throw_last(V1,MUL,R);
}
}
chain Stage1(double * V1, double MUL, double * R) {
for (int j=0; j<VEC_SIZE; j++)
R[j] = V1[j]+MUL;
}
…
plan_parallel_chain(0, Stage0(5,(double *)X1,(double *)X2,(double *)X3,(double *)R), Stage1(NULL,0,NULL)); 2 ??????????? 5 ??????????? ??????. ?????????????? ??????? ?????????? ????????? X1+X2*X3 ????????
??????????
Slide 5:
????????? ??????? ?? ??????? ????? (2*Opteron 270, 2 ???) ????? ?????????? ?????????????? ????????????? ???????????????? ???? ????????? ????????????? ??????????: ?????? «MOBI», 3/2009 ????? ???? ????????? ????????????? ??????????? ? ????????????????? ???? ??????????:
?????????? ??????? ?? ?? ????????????????.
??????????? ?????????? ? ????????? ???????????, ??????????? ??? ????????????????? ???????, ? ????????? ? OpenMP.
?????????? ?????????? ??????????? ???????????? ???????.
?????????? ????????? ????????????? ?????????? ??????, ????????? ? ????????????? ???? ?????? ?? ?????????
????? ?????????? ?????????????? ????????????? ???????????????? :
?????, ?????????????????? ?? ?????????? ???????????? ???????????;
??????????? ???????????? ???????????? ???????????;
??????? ??????, ??????????????? ?? ?????? ? ?????????????????? ?????????;
??????? ?????????. ???????? ???????? ????? ??????? ?? ????? ?????? ????????.
????????? ???????, ??????????? ?????????? ???????? ?????????????????:
T-??????????;
OpenMP (??????????? GNU, Microsoft);
DVM, HPC, MC#. ????? ?????????? ?????????????? ????????????? ???????????????? ??????????? ??????????????? ??????? (???????????? + ????????);
? ??????? ??? ???????????? ???????????????? ???????????? C++. ??????????? ?????????? ??????????
????? ?????????? ?????????????? ????????????? ???????????????? :
1. ????????????? ?????.
2. ???????? ?????. ?????????? ??????? ???????????? ?????????????.
3. ???? ?????????????? ??????. ?????????? ???????????? ????????? ????????????? ????? ????????????????, ??? ????? ????????? ?????????????? ????????????? ??????????? ??????? ? ????????????? ??????? ????????????. ????? ??????????? ? ???????? alfa-?????? ???????????.
?????????????? ?????????? ?????????? ? ????????????????? ???????????? ?????????? (???????? ??????????? ???????? ??? ?????????? ?????).
?????????? ?????????? (300 ???. ???) ??? ?????????? ??????????? ? ???????????? ???????????? ?????? ??????????? ? ?????????.
????? ??????? ?? ?????
????????????? ????????????
????????? ????????
??????? ? ?????????
?????????? ???????????????? ?????? ????????? ??????? ? ??????????? ????? ?????????? ?????????????? ????????????? ????????????????