Берілген тарудағы 1-бөліммінде біз әртүрлі сұрыптау алгоритмдерін қарастырамыз:
- Аттап өту сұрыптамасы (ранг әдісі)
- Салыстыру және ауыстыру сұрыптау алгоритмі.
- Салыстыру және ауыстыру
- Көпірші әдісмен сұрыптау және «тақ-жұп» сұрыптау.
- Бірігу сұрыптауы
- Жылдам сұрыптау
екінші бөлімді – параллельдеудің сандық әдістері: матрицаларды көбейту; сызықтық теңдеулер жүйесін шешудің тура және итерациялық әдістері.
5.1. Ранг әдісімен сұрыптау
сұрыптаудың бұл түрінің екінші атауы – атап өту сұрыптауы. (Wilkinson6 B. and Allen6 M., 1999). Бұл сұрыптаудың негізгі идеясы: берілген сандардың ішінен таңдалғаннан аз сандарды санаймыз. Бұл санау тізімдегі таңдалған санның позиция нөмерін қамтамасыз етеді, яғни тізімдегі таңдалған санның позиция нөмерін қамтамасыз етеді, яғни тізімдегі оның «рангін» табамыз.
a[0],a[1],…, a[n-1] массивіндегі сақталған n саны берілген деп есептейік. Ал нәтижелері сұрыпталған b[0], b[1], … , b[n-1] массивінде сақталған. Тізбекті коды келесі түрде сипатталуы мүмкін.
For (i=0; i<n; i++) // әрбір санға
{
x=0
For (i=0; j<n; i++) // считают число из списка чисел меньшее чем выбранное
If (a[i]>a[j]) x++;
B[x]=a[i]; // копирует номер в провильное место
}
Сұрақ: Қандай жағдайда берілген код сәтсіз болады? Талданған жағдайды ескере отырып программа жаз.
Осы кодты n процессор үшін қайта жазуға тырысамыз.
n процессор бар деп есептейік. Әрбір процессор бір санға бекітілген. Бұл жағдайда әрбір процессор сандардың біреуінің соңғы индексін О(n) қадамға яғни time complexity=O(n) табу.
Мұнда біз forall операторын қолданамыз, мұндағы i-процессор нөмері.
Forall (i=0; i<n; i++) //әрбір санға бір уақытқа (параллельдік)
{x=0;
for (j=0; j<n; j++) if (a[i]>a[j]) x++;
b[x]=a[i];
}
көптеген программаларда, дербес жағдайда, сұрыптау орындайтын программада ағымдағы сандарды уақытша қажетті қосымша айнымалыға орын бөлінеді, келешекте басқа санмен позициясын алмастыруды жүзеге асыратын әдістеме қарастырылады.
Төмендегі осы уақытша айнымалыларды қолданбайтын әдісті қарастырамыз.
5.2. Салыстыру-және-ауыстыру
А және В екі сан бар деп есептейміз.
Салыстыр және ауыстыр амалы тізбекті кодта төменде көрсетілген:
If (A>B)
{temp=A; A=B; B=temp;}
берілген ситуация хабар беру жүйесі үшін келеді.
Р1 және Р2 екі процессоры бар деп есептейік. Р1 А-дан Р2. В-дан тұрады. 18-суретте мүмкін салыстыру және ауыстыру схемасының бірі келтірілген:
Салыстыру және ауыстыру 1-ші схемасы.
Бұл схеманың коды төмендегідей:
| Р1 Процессор
Send(&A6P2); Recv(&A,P2); {send(&B,P1); B=A;} Else Send(&A,P1); |
Р2 Процессор
Recv(&A6P1); if(A>B) |
Салыстыру және ауыстыру 2-ші схемасыIf A>B load (B) ifA>B load (A)
Бұл схема коды төмендегідей:
| Р1 Процессі
Send(&A,P2); Recv(&B,P2) If (A>B) A=B6 |
Р2 Процессор
Recv(&A,P1); Send(&B6P1); If (A>B) B=A; |
5.2.1 деректерді бөлу
p процессор және n саны делік. n/p сандардың тізімі әрбір процессорге бекітілген (Wikinson, B. And Allen, M., 199). Схема 1 және схема 2 сандарды әдісімен сұрыптау үшінЕкі ішкі тізімді біріктіру. Схема 1
|
|
|
Екі ішкі схеманы біріктіру. Схемасы 2.
Сонымен, екі ішкі тізімді жалпы әдісі төмендегідей:
Әрбір процедурада сұрыпталған тізімді сақтау керек және енгізу тізімі бар сақталған тізімі.
5.2.2. Жылдам сұрыптау
Гиперкубтағыжылдам сұрыптау
Біз саннан тұратын тізім бар деп есептейміз, ол алғашында d өлшемді гиперкуб торабының біреуіне орналастырылған. әрбір тораптың сәйкес номері бар.
P0
| 4 | 2 | 7 | 8 | 5 | 1 | 3 | 6 |
|
|
| 3 | 2 | 7 | 4 |
| 5 | 7 | 8 | 6 |
| 8 | 6 |
| 5 |
|
|
|
|
|
| 8 |
| 7 |
|
6
Pivo
Жылдам сұрыптау.
Жоғарыда сипатталған жылдам сұрыптау алгоритмінің процесі келесі схемада сәйкес көрсетіледі:
1-қадам: 000001 (числа, большие чем pivot, идут на Р1)2-қадам: 000010 (числа, большие чем pivot, идут на Р2)
001 011 (числа, большие чем pivot, идут на Р3)
3-қадам: 000100 (числа, большие чем pivot, идут на Р4)
001 101 (числа, большие чем pivot, идут на Р5)
010 110 (числа, большие чем pivot, идут на Р6)
011 111 (числа, большие чем pivot, идут на Р7)
Соңында осы бөліктер тізбекті алгоритмді қолдана отырып сұрыпталуы мүмкін, ал бәрі бірге параллель.