Студенттің орындайтын тапсырмалары:
Тапсырма 1: Сұрыптаудың қарастырылатын алгоритмдерін атаңыз және анықтама беріңіз.
Тапсырма 2: «Көпіршіктер» әдісімен сұрыптаудың тізбекті программасын құрыңыз.
Тапсырма 3: "Тақ-жұп орын ауыстыру" тізбектің программасын құрыңыз
Тапсырма 4: n-процессорлы сақинада орындалатын "тақ-жұр орын ауыстыру" тәсілінің параллельді программасын құрыңыз.
Тапсырма 5: Параллельді әдіске қысқаша сипаттама беріңіз.
Тапсырма 6: Сақинадағы процессорлар бір-біріне элементтерін қалай алмастырады.
Тапсырма 7: Процесс операцияның орындалу тізбегі.
ЖАУАПТАРЫ
1. Сұрыптаудың мынадай алгоритмдері қарастырылады.
1. Ранг әдісімен сұрыптау
2. салыстыру және алмасу сұрыптауы алгоритмдер:
✓ Салыстыру және алмастыру
✓ Көпіршіктер әдісімен сұрыптау (метод пузырка) және «тақ-жұп» сұрыптауы
✓ Біріктіру бойынша сұрыптау
✓ Тез сұрыптау
Салыстыру-және-алмастыру әдісімен сұрыптау. Көптеген программаларда сұрыптау кезінде ағымдағы санды басқа санмен орны бойынша алмастыру мақсатында уақытша сақтау үшін базалық айнымалылар пайдаланылады. Ал, параллельді есептеулерде ол сандарды сақтап қоюға процессорларды пайдаланады.
If (A>B)
temp=A; A=B; B=temp;
2. Көпіршіктер әдісімен сұрыпау.
(a1 , a2 , ...,an ) сандарының тізбегі берілсін . Сандарды өсу ретімен орналастыру керек, яғни i>j үшін ai
2жауап. Көпіршіктер әдісімен сұрыпау.
(a1 , a2 , ...,an ) сандарының тізбегі берілсін . Сандарды өсу ретімен орналастыру керек, яғни i>j үшін ai
Программа 1. «Көпіршіктер» әдісімен сұрыптаудың тізбекті алгоритмі.
1. procedure BUBBLE-SORT(n)
2. begin
3. for i:=n-1 downto 1 do
4. for j:=1 to i do
5. compare-exchange(aj,aj+1);
6. end BUBBLE-SORT
Бұл алгоритмде ішкі цикл итерациясы Q(n) уақытта орындалса және Q(n)
итерация жасалса, «көпіршіктер» әдісімен сұрыптауға кететін уақыт - Q(n 2). Бұл алгоритмді параллельділікке айналдыру үлкен қиындық келтіреді.
3жауап «Тақ-жұп орын ауыстыру» алгоритмі.
Бұл алгоритмде n элемент n фазада сұрыпталады. Бұл алгоритмнің жұп
және тақ фазалары кезектестіріледі. (a1 , a2 , ...,an) – тізбегін сұрыптау керек болсын. Тақ фаза кезінде тақ индексті элементтер оң жақтағы көрші элементпен салыстырылып, егер шарт орындалса, олар орындарын алмастырады, яғни (a1 , а 2 ), (a3 , a4 ), ..., (an-1 ,an ) жұптары салыстырылып алмастырылады. Сол сияқты жұп фаза кезінде, жұп индексті элементтер салыстырлып, егер шарт орындалса, олар орындарын алмастырады, яғни (а2, a3), (a4 , a5), ..., (an-2 ,an-1) жұптары алыстырылып алмастырылады. Сонда тақ-жұп ауыстыру n фазасынан кейін тізбек сұрыпталады. Әрбір алгоритмнің фазасында Q(n) салыстыру жасалса, барлығы n фаза болса, бұл алгоримтнің (sequential complexity) - Q(n 2 ).
Программа 2. "тақ-жұп орын ауыстыру" тізбекті алгоритмі.
1. procedure ODD-EVEN(n)
2. begin
3. for i:=1 to n do
4. begin
5. if i is odd then
6. for j:=0 to n/2-1 do
7. compare-exchange(a 2j+1 , a2j+2 )
8. if i is even then
9. for j:=1 to n/2-1 do
10. compare-exchange(a 2j ,a 2j+1 )
11. end for
12. end ODD-EVEN
Мысалы, n = 8 элементті «тақ-жұп орын ауыстыру» әдісімен сұрыптау керек. Әрбір фазада n = 8 элемент сұрыпталады.
4жауап. Программа 3. n-процессорлы сақинада орындалатын "тақ-жұп орын ауыстыру" тәсілінің параллельді алгоритмі.
1. procedure ODD-EVEN-PAR(n)
2. begin
3. id := processor's label
4. for i:= 1 to n do
5. begin
6. if i is odd then7. if id is odd then
7. compare-exchange_min(id+1);
8. else
9. compare-exchange_max(id-1);
10. if i is even then
11. if id is even then
12. compare-exchange_min(id+1);
13. else
14. compare-exchange_max(id-1);
15. end for
16. end ODD-EVEN_PAR
Әрбір фазада орындалатын қадамдарға Q(1) уақыт кетеді. Барлығы n фаза болса, параллельді алгоритмнің орындалуына Q(n) уақыт кетеді екен. Параллельді әдіске қысқаша сипаттама p – процессорлар саны, n – сұрыпталатын тізбектің ұзындығы, мұндағы p
Бастапқыда, әрбір процессор үшін n/p элементтен тұратын блок
тағайындалады, ол бұл элементтерден іштей Q((n/p)*log(n/p)) уақытта
сұрыптап шығады. Мұнан кейін процессорлар р фазыдан өтіп шығады (p/2 тақ
және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын орындайды.
Сақинадағы процессорлар бір-біріне элементтерін алмастырады.
Нәтижесінде әрбір процессорда өз элементтері және көрші процессордың
элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор
элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы –
екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң
тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p)
салыстыру орындалады және Q(n/p) уақыт жұмсалады.
5жауап. Параллель архитектуралы есептеу жүйелеріндегі үрдіс мүлдем басқаша. Мұнда әрбір уақыт мезетінде бір-біріне тәуелсіз бірнеше операциялар жиынтығы орындалуы мүмкін. Кезкелген параллель жүйеде бағдарлама және кіріс деректері сол жиынтықтардың құрамымен қатар, олардың ретін де бірмәнді анықтайды. Алайда, әртүрлі жүйелерде жиынтықтар мен олардың реттіліктері әртүрлі болуы мүмкін. Дегенмен бірмәнді нәтиже алуды кепілдендіру үшін барлық операциялар жиынының орындалу реті қандай да бір шартқа бағынуы тиіс.
6жауап. Сақинадағы процессорлар бір-біріне элементтерін алмастырады.
Нәтижесінде әрбір процессорда өз элементтері және көрші процессордың
элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор
элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы –
екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң
тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p)
салыстыру орындалады және Q(n/p) уақыт жұмсалады.
7жауап. Мультипрограммалауды қолдау үшін, операциялық жүйе процессор мен компьютердің басқа да ресурстарын өзара бөлісетін жұмыстың ішкі бірліктерін анықтап және нақтылап алуы керек. Қазіргі таңда операциялық жүйелердің көпшілігінде жұмыс бірлігінің екі түрі анықталған. Есептеу жүйесінің кез-келген жұмысы қандай да бір программаның орындалуы негізінде жүретіні белгілі. Сондықтан процесспен де, ағынмен де орындаушы модуль түріндегі белгілі бір программалық код байланыс орнатады. Бұл программалық код орындалу үшін, оны оперативті жадыға жүктеу керек. Сонымен бірге деректерді сақтау үшін дискіден орын бөлу немесе енгізу-шығару құрылғыларымен байланыс орнату қажеттілігі туындауы мүмкін. Тағы бір, ескеретін жағдай программаның орындалуы оған деген процессорлық уақыт бөлінбейінше мүмкін емес екендігі.
Процесстер мен ағындар қатар кездесетін операциялық жүйелерде процесс процессорлық уақыттан басқа барлық ресурстарға сұраныс ретінде қарастырылады. Ал ең маңызды ресурс болып табылатын процессорлық уақыт жұмыстың басқа бірліктері ағындармен анықталады.
Қарапайым жағдайда процесс тек бір ағыннан ғана тұрады. Мұндай кезде «ағын» ұығымы «процесс» ұғымымен толық жұтылады, яғни тек бір ғана жұмыс бірлігі – «процесс» ұғымы ғана болады.
Процесстер ресрурстарды үлестіруге араласпау және бір-бірінің кодтарын бүлдіріп алмауы үшін операциялық жүйенің негізгі міндетінің бірі оларды бір-бірінен изоляциялау болып табылады. Бұл үшін операциялық жүйе әр процесстің виртуалдық кеңістігін бөлек құрастырады. Сондықтан бір процесс басқа процесстің командалары мен деректеріне қол сұға алмайды.
Достарыңызбен бөлісу: |
