Главная страница
Контакты

    Басты бет


БАҒдарламасы ( Syllabus ) Павлодар, 2014ж Пән бағдарламасы (Syllabus) ф фсо пгу 18. 4/19 бекітемін фмжат факультетінің деканы Н. А. Испулов

жүктеу 1.28 Mb.



жүктеу 1.28 Mb.
бет3/6
Дата05.04.2017
өлшемі1.28 Mb.

БАҒдарламасы ( Syllabus ) Павлодар, 2014ж Пән бағдарламасы (Syllabus) ф фсо пгу 18. 4/19 бекітемін фмжат факультетінің деканы Н. А. Испулов


1   2   3   4   5   6

Бөлінбейтін әрекеттер және күту операторлары

Жоғарыда ескертілгендей, параллель программаның орындалуын және процесстердің орындайтын бөлінбейтін әрекеттерінің алмасуы деп қарастыруға болады. Процесстердің өзара әрекеттестігі үшін барлық алмасулар үшін рұқсат барлық алмасулар үшін рұқсат жоқ. Синхрондау мақсаты – ұнамсыз алмастыруды болдырмау. Оны жүзеге асыру бөлінбейтін ұсақ модульды амалдарды ірі модульды (құрама) әрекеттерге біріктіру немесе белгілі бір предикатты қанағаттандыратын программаның қалып-күйіне жеткенше процесс орындалуының кідірісі жолымен жүзеге асырылады.

Синхрондаудың бірінші формасы-өзара тізімнен шығару деп атайды, екіншісі-шартты синхрондау.

Ұсақ модульдық бөлінбеушілік.

Бөлінбейтін әрекет қалып-күйді бөлмей түрлендіреді. Бұл осы әрекетті орындау барысында пайда болатын кез-келген аралық қалып-күй басқа процесстер үшін көрінбейтін болуы керек. Ұсақмодульды бөлінбейтін әрекет-программа орындалатын тікелей аппараттық жасаудың әрекеті.

Тізбекті программада меншіктеу операторы бөлінбейді, өйткені оның орындалуы барысында программаға көрінетін аралық қалып-күйлер болмайды ( аппараттық жасау анықтайтын қателерді санамағанда). Бірақ параллельпрограммада меншіктеу операторлары бөлінбейтін амал болмайды, өйткені ол ұсақ иодульдымашиналық инструкциялар тізбегі ретінде келесі программаны қарастырайық және ұсақмодульды бөлінбейтін амал – айнымалыларды оқу және жазу.

Int y=0; z=0;

Parallel: x=e z; //y=1; z=2; end parallel;

Егер x=y z y-ң мәнін регистрге жүктеу және келесі мәндері z-ті қоса отырып алынса, онда х айнымалысының 0,1,2 және 3. Бұлайша болатын себебі біз екінші процесстің орындалу дәрежесіне байланысты у және z-тің алғашқы мәндерімен қоса, олардың соңғы мәндерін немесе комбинациясын аламыз. Келтірілген программаның тағы бір ерекшелігі, х-тің соңғы мәні болуы мүмкін, бірақ программаны тоқтатып у z қосындысының мәні 2 болатын қалып-күйді көре аламыз. Машиналар келесі сипаттамаларға ие болады деп есептеледі:


  • Бөлінбейтін амалдармен оқылатын және жазылатын базалық типтің мәндері (мысалы, Int) жады элементтерінде (мысалы сөздерде) сақталады.

  • Мәндер былай өңделеді: оларды регистрлерге орналастырады, онда оған амалдар қолданады және нәтижені қайтадан жадыға жазады.

  • Әрбір процесстің өзінің регистрлер жиыны болады. Бұл әрбір процесске және регистрлер жиынын беру жолымен немесе әртүрлі процесстерді орындағанда регистрлер мәнін қайта қалпына келтіру жолымен жасалады. (Бұл регистрлер процессті орындау контекстін құрғандықтан контексті ауыстыру деп атайды.)

  • Күрделі өрнектерді есептегенде пайда болатын кез-келегн аралық нәтижелер орындалатын процесстің регистрлері немесе жады облыстарында сақталады, мысалы, оның стегінде.

Машинаның бұл моделінде, гер бір процесстегі е өрнегі басқа процесс өзгерткен айнымалыға айналмаса, бірнеше ұсақмодульды әрекеттерді орындау қажет болса да өрнекті есептеу әрқашанда бөлінбейтін амал болады. Бұл е өрнегін есептеген е-ге тәуелді бірде бір мән өзінің мәнін өзгертпейді және өрнекті есептегендегі құрылатын уақытша мәнді бірде-бір процесс көрмейді. Сол сияқты, егер x=е меншіктеуі бір процессте басқа процесс өзгертетін айнымалыға нұсқамаса (мысал, тек жергілікті айнымалыларға нұсқаса), онда меншіктеуді орындау бөлінбейтін амал.

Параллель программадағы көптеген операторлар осы қиылыспаушылық шартын қанағаттандырмайды. Бірақ та жиірек жұмсақ шарттар орындалады.

« Бірден аспайтын» шарты.

Сын нұсқағыш өрнектегі басқа процесстер өзгертетін айнымалыға нұсқайды. Кез-келген сын секциясы-жады элементінде сақталатын қарапайым айнымалыға нұсқайды және автоматты түрде оқылады және жазылады деп есептейік. x=е меншіктеу операторы егер немесе е бірден аспайтын сын нұсқағыштан тұрса, ал х айнымалысы басқа процесспен оқылмайтын болса, немесе е өрнегі сын секцияларынан тұрмаса, ал басқа процесстер х айнымалысын оқымаса «бірден аспайтын» шартын қанағаттандырады.

Бұл шарт «бірден аспайтын» шарты деп аталады, себебі осы жағдайда ғана бір бөлінбейтін айнымалы болуы мүмкін және оны бірден артық рет шақырмайды.Осы сияқты анықтама меншіктеу операторы болмайтын өрнектерге қолданылады. Осындай өрнектер «бірден аспайтын» шартын қанағаттандырады егер ол бірден аспайтын сын нұсқағыштан тұрса.

Егер меншіктеу операторы «бірден аспайтын» шартын қанағаттандырса, онда меншіктеу операторының орындалуы бөлінбейтін амал болып көрінеді, өйткені өрнектегі бір ғана бөлінбейтін айнымалы бір ақ рет оқылады немесе жазылады. Мысалы, егер е өрнегі сын секцияларынан тұрмаса, ал х айнымалысы басқа процесстер оқитын қарапайым болса, онда олар өрнек бөлінбей есептеле ме тани алады. Сол сияқты, егер е бір сын секциясынан тұрса, онда меншіктеуді орындайын процесс айнымалының мәні қалай өзгергенін айыра алмайды: ол тек соңғы мәнді ғана көре алады.

« Бірден аспайтын» шартын түсіндіру үшін бірнеше мысал келтірейік. Келесі программада екі меншіктеу де осы шартты қанағаттандырады.

Int x=0; y=0;

Parallel: x=x 1; //y=y 1;

Мұнда бір де бір процесске сын нұсқау жоқ, сондықтан х-тің де, у-ң де соңғы мәні бір болады.

Келесі программада екі меншіктеу де осы шартты қанағаттандырады.

Int x=0; y=0;

Parallel: x=x 1; //y=y 1;

Бірінші процесс у-ке нұсқайды (бір сын нұсқағыш), бірақ х айнымалысы екінші процесспен оқылмайды, және екінші процессте сын нұсқағыш жоқ. Х айнымалысының соңғы мәні немесе 1 немесе 2, ал у-тің соңғы мәні 1. Бірінші процесс у айнымалысын немесе оны өсіру алдында, немесе өсіргеннен кейін көреді, бірақ параллель программада программаның орындалу реті детерминделмегендіктен ол қай мәндерді көргендігін ешқашан білмейді.

Келесі прораммада бір де бір меншіктеу «бірден артық емес» шартына сәйкес келмейді.

Int x=0; y=0;

Parallel: x=x 1; //y=y 1;

Әрбір процессте өрнекте сын нұсқағыш болады және әрбір процесс оқыған айнымалы мәнін мәншіктейді. Шындығында х және у айнымалыларының соңғы мәндері 1 және 2, 2 және 1 немесе 1 және 1 болуы мүмкін (егер процесстер х және у айнымалысының мәндерін оларға мән меншіктегенге дейін оқыса.) Бірақ, әрбір меншіктеу басқа процесс өзгертетін бір ғана айнымалыға бір ғана рет нұсқағандықтан, белгілі бір қалып күйде шындығында болған мәндер соңғы болады. Бұл алдында келтірілген у 2 өрнегі басқа процесс өзгертетін екі айнымалыға нұсқағыш мысалдан өзгеше.

Жалпы жағдайда, егер өрнек немесе меншіктеу операторы «бірден артық емес» шартын қанағаттандырмаса, бірақ оны бөлінбейтін етіп орындау керек болса бір бөлінбейтін әрекетте операторлар тізбегін орындау керек. Кез –келген жағдайда, ірімодульды бөлінбейтін амалдарды – бөлінбейтін болып көрінетін ұсақмодульды бөлінбейтін амалдардың тізбегін беретін синхрондау механизмі қажет.

Нақты мысал ретінде деректер қоры х және у екі мәнінен тұрады, олар әрқашанда бірдей болуы керек, яғни деректер қорын қолданатын бірде бір процесс х және у өзгеше болатын қалып күйді көрмеуі тиіс. Яғни, егер процесс х-ті өзгертсе, ол сол бөлінбейтін әрекетте у-ті де өзгертуі керек.

Тағы да бір мысал: бір процесс байланысқан тізімдермен өрнектелген кезекке элементпен қоссын. Ал екінші процесс тізімде сол элемент болса, соны жоятын болсын. Бір айнымалы тізім басын, ал екіншісі – тізім сонын көрсетсін. Элементтерді қосу және жою екі мәнді өңдеуді қажет етеді. Мысалы, элементті қосу үшін алғашқы элементтің нұсқағышын және тізім соңының нұсқағышын жаңа элементке нұсқайтындай жағын өзгерту керек. Егер тізімде бір ғана элемент болса, бір уақытта қою және жою қайшылыққа алып келуі және тізімді қолдануға келмейтін қалып-күйге алып келуі мүмкін. Сонымен элементті қосу және жою бөлінбейтін әрекеттер болуы керек. Егер тізім бос болса, жою операциясын орындауды, тізімге элемент қосылғанға дейін қоя тұруы керек.

Бөлінбейтін амалдар үшбұрышты жақшалар < және > көмегімен беріледі. Мысалы, <е> - е өрнегі бөлінбей есептелетінін көрсетеді.

Синхрондау await операторы көмегімен анықталады:

< await (B)S>;

В бульдік айнымалы кідіріс шартын береді, ал S – аяқталуға кепілдігі бар операторлар тізбегінің тізімі ( мысалы, меншіктеу операторының тізбегі). Операторы бөлінбейтін әрекет ретінде орындалатындығын көрсету үшін үшбұрыш жақшаға алынады. Дербес жағдайда S орындала бастағанда және S тегі ешбір аралық қалып-күй басқа процесстерге көрінбейтін болса В өрнегі «ақиқат» мәніне ие болады. Мысалы,



0) S=S-1;> кодының орындалуы S-тің мәні оң болғанша кейінге қалдырылады, одан кейін ол 1-ге кемиді. Азайтқанға дейін S-тің мәні оң болатындығына кепілдік бар.

Await операторы кез-келген бөлінбейтін әрекеті бар ірімодульды анықтау үшін қолдануы мүмкін. Сондай-ақ тиімді.

Мысалы, жоғарыдағы келтірілген соңғы await операторы е семафорына Р операциясының дербес жағдайы.

Await операторының жалпы түрі - өзара алып тастау мен шарт бойынша синхрондауды анықтайды. Тек қана өзара алып тастауды анықтау үшін await операторының қысқа түрі қолданылады:



Мысалы, келесі операторда х және у-ң мәндері бөлінбейтін әрекетте өсіріледі:



Х-тің мәні 1-ге өскенде, ал у-әлі өсиегендегі аралық қалып-күй анықтама бойынша х және у айнымалыларына нұсқайтын басқа процесстер үшін көрінбейді.

Егер S тізбегі бірдің артық емес шартына қанағаттандыратын жалғыз меншіктеу операторы болса, немесе егер S бір машиналық инструкциямен жүзеге асырылса, онда бөлінбей орындалады; яғни «S; » дәл S сияқты болады.

Тек шартты синхрондауды беру үшін операторын қарастырайық;



Мысалы, процесстің келесі операторымен орындалуы айнымалысының мәні оң болғанға дейін қалдырылады.



0);>

Егер В берілген мысалдағыдай бірден артық емес шартын қанағаттандырса, онда «await (B); » өрнегі while (not B); ретінде жүзеге асырылады.

Бұл күту циклының мысалы while операторының денесі бос, сондықтан В-ның мәні жалған болғанға дейін циклданады.

Шартсыз бөлінбейтін әрекет –денесінде В кідіріс шарты болмайтын әрекет. Мұндай әрекет оның орындалуыныңбөлінбейтін шартына сәйкес бірден орындалуы мүмкін. Ұшбұрыш жағшадағы өрнектер және шарты жазылмаған немесе ақиқат мәнді қабылдайтын маппаратта жасалатын (ұсақ модульды) әрекеттер шартсыз бөлінбейтін әрекет болады.

Шартты бөлінбейтін амалдар – В шарты бар операторы.

Мұндай шарт В шарт ақиқат болғанша орындалмауы мүмкін. Егер В жалған болса, ол басқа процесстер әрекетінің нәтижесінде ақиқат болуы мүмкін. Егер В жалған болса процесстер әрекетінің нәтижесінде ақиқат болуы мүмкін. Сонымен шартты бөлінбей әрекеттің орындалуын күтетін процесс ұзақ кідірісте болуы мүмкін.


7 Лекция. Программалау тілдерінің синхрондау деңгейі.

    • Синхрондау типтері. “Өндіруші –пайдаланушы” типті синхрондау.

    • Философтардың түскі асы туралы есеп.

“Өндіруші –пайдаланушы” типті синхрондау, мысалы, өндіруші процесс және пайдаланушы процессті қолданатын файлдағы шаблонды іздеу есебінде қолданады.

Файл (ағылш. File) - дерек сақтаудың негізгі бірлігі болып табылады.
Пайдаланушы (Пользователь; user, subscriber) - 1) асқа жүйенің ресурстарын пайдаланатын программа немесе жүйе; 2) терминал(пернетақта мен экран) арқылы электрондық машинамен бірлесіп әрекет жасайтын адам.
Өндіруші әрқашан енгізу жолдарын оқиды, олародың қайсысында ізделінді шаблон бар екендігін анықтайды, және оны пайдаланушы процесске береді. Одан кейін пайдаланушы өндірушіден алған жолдарды шығарады. Өндіруші мен пайдаланушы арасындағы өзара әрекеттестік бөлінетін айнымалы көмегімен қамтамасыз етіледі.

“Өндіруші –пайдаланушы” типті басқа есеп: өндірушіден пайдаланушыға массивтің барлық элементтерін көшіреді.

Екі процесс: Producer (өндіруші) және consumer (пайдаланушы) берілген.

Producer процесс бүтін сандардан тұратын а[n] consumer b[n] жергілікті массив берілсін. А массиві инициалданған деп есептейміз. Мақсат- оның құрамын в массивіне көшіру.

Процесстер массивті бөлмейтіндіктен, олардың өзара әрекеттесуі үшін бөлінетін айнымалылар керек.

buf aйнымалысы- өзара әрекет буфері болатын жалғыз бүтін айнымалы.

Producer және consumer процесстері buf айнымалысына кезекпен қатынау керек. Алдымен producer а массивінің бірінші элементін buf айнымалысына орналастырады, одан кейін оны алады да, айнымалысына а массивінің келесі элементін орналастырады және т.с.с

Р және с бөлінетін айнымалылар орналастырылған және алынған сандардың сәйкес санауыштары болсын. Олардың алғашқы мәндері =0. Онда Producer және consumer процесстің асинхрондау шарты төмендегідей жазылуы мүмкін:

Pc: c<=p<=c 1

С және р айнымалыларыныңмәндері 1-ге айырмашылығы болады: бұл Producer буферге максимальды артық элемент орналастырды, Consumer алғаннан осы екі процесстің коды төменде келтірілген:

Int buf.p=0,c=0

Process Producer{

While(p

{

buf=a[p];

p=p 1;

} }


Process Consumer{

Intb[n]


While(c{

{



b[c]=buf:

c=c 1;} }


Producer және consumer процесстері р және с айнымалыларын buf буферіне қатынауды синхрондау үшін қолданылады. Await!!!!!!!!!!!!!!!!!!!!!!!

жұмыс істейтін кодтың критикалық емес секцияларын орындайды. Өзінің сын секциясында болатын әрбір процеске бөлінетін ресурсқа өзара шығарып тастайтын қатынау керек.

Семафорлар сын секцияларының есептерін шешуді жеңілдету үшін ойлап табылған. Төменде бұғаттау үшін айнымалыларды қолданатын шешім келтірілген. Мұнда lock айнымалысы бірде бір процесс өзінің сын секциясында болмаса «ақиқат» мәніне ие, басқа жағдайда бірде бір процесс өзінің секциясында болмаса мәні «жалған». «Ақиқат» мәні 1 арқылы өрнектелсе, ал «жалған» - 0 болса. Онда процесс сын секциясына кірмес бұрын lock айнымалысының мәні 1-ге тең болғанша күту керек және оған 0 мәнін меншіктеу керек. Сын секциясынан шыққанда процесс lock айнымалысына 1 мәнін меншіктеу керек. Осы амалдар семафорлармен қолданылады.

Сонымен, синхрондаудың екі есебі жеке шешіледі – алдымен бір өндіруші мен бір қолданушы арасында. Нәтижесінде есептің толық шешімін алу үшін екі ішкі есептің шешулерін жеңіл біріктіруге болады. Мұндай идея 4.3. тарауда оқушылар мен жазушылар есебінде қолданылады.

Жазушы (кейде литератор) - қоғамдық пайдалануға арналған, сөздерден құралған туынды жасайтын адам. Жазушы деп әдетте аталмыш іс негізгі кәсібі, немесе негізгі кәсіптерінің бірі саналатын адамды айтады.
Сонымен, бірнеше типті синхрондау болған жерде оларды жеке орындап кейін шешулерін біріктіру қажет.



Философтардың түскі асы туралы есеп.

Түскі ас ішкен философтар есебінің шешімі процесстердің арасындағы өзара шығарып тастауды жүзеге асырып, бөлінетін айнымалылардың қиылысатын жиындарына қатынасуға бәсекелесетін. Түскі ас ішкен философтардың есебі синхрондаудың әртүрлі механизмдерін көрсету және салыстыру үшін жиі қолданылады.

Философтардың түскі асы туралы есеп. 5 философ дөңгелек столда отыр. Олар тамақ ішу мен ойлауды кезектестіріп өмір сүруде. Столдың ортасында спагетти салған үлкен табақ. Спагетти ұзын және шатысқандықтан философтар оны жеу үшін екі айыр шанышқы қолдануы керек.

Шанышқы - сап пен бір ұшында бірнеше жіңішке тісшелерден (әдетте екіден төртке дейін) тұратын асханалық құрал.
Өкінішке орай философтарға бес қана шанышқы берілген. Әрбір екі философ арасында бір шанышқы, сондықтан олардың әрбіреуі тек қасында жатқан шанышқынықолданады деп келіскен (сол жағындағы және оң жағындағы). Есеп – философтардың іс-әрекетін модельдейтінпрограмма құру керек. Программа сәтсіз емем жағдайлардан қашқақтау керек, яғни барлық философтар аш, бірақ олардың бірде біреуі екі шанышқыны ала алмайды – мысалы, олардың әрбіреуі бір шанышқыдан ұстап оны бергісі келмейді.

Есеп 17 суретте бейнеленген. Қатар отырған екі философ біруақытта жей алмайды. Сондай – ақ шанышқы 5-у болғандықтан біруақытта екі философ ас іше алады.












17- сурет. Философтардың түскі асы туралы есеп.

Ойлау уақыты мен тамақ ішу аралығы әр түрлі болсын делік - оларды имитация жасау үшін кездейсоқ сандар генераторын қолдануға болады. Философтардың тәртібін төмендегідей деп имитациялайық:

process Philosopher [ i = 0 to 4 ]{

while ( true) {

поразмыслить;

взять вилки;

поесть;

отдать вилки;



}}

Есепті шешу үшін "шанышқыны алу" және "шанышқыны беру" амалдарын программалау қажет. Шанышқылар бөлінетін ресурстар, сондықтан оны алу және босатуға көңіл бөлейік.

Ресурстар (французша ressourse - құрал-жабдық, мүмкіндік), босалқы қорлар - табыс, ақшалай және басқа қаражат, құндылықтар мен олардың көздері.
Әрбір шанышқы сын секцияны бүғаттауға ұқсайды; кез-келген уақытта тек бір ғана философ ие. Сондықтан, шанышқыларды 1 деген мәнмен инициализацияланған семафорлар массиві түрінде көрсетуге болады. Шанышқыны алу сәйкес семафор үшін р амалымен, ал босату – v амалымен имитацияланады.

Процесстер ұқсас, сондықтан олар бірдей амалдарды орындайды деп санауға болады.Мысалы, әрбір процесс алдымен Семафор типін дұрыс емес таңдап немесе сын секцияларының барлығын қорғауы мүмкін емес. Семафорлар басқа процестерге қатысты кең ауқымды, сондықтан семафордың немесе басқа да бөлінетін айнымаларды қалай қолданылатынын түсіну үшін бүкіл программаны қарау керек. Ең соңында, семафорларды қолданғанда өзара шығарып тастау және шартты синхрондау бір ғана қарапайым жұбымен программаланады. Осы үшін берілген семаформен басқа амалдарды көрмей нақты р және v неге қажет екендігін түсіну қиын. Өзара шығарып тастау және шартты синхрондау әр түрлі ұғымдар, сондықтан оны әр түрлі әдіспен программалаған дұрыс.

Мониторлар – семафорларға қарағанда үлкен құрылымды қамтамасыз ететін тиімді түрде жүзеге асыратын программалық модульдер. Ең алдымен, мониторлар деректер абстракциясының механизмі. Монитор абстракциялы объектіні өрнектеуді инкапсуляциялайды және тек солардың көмегімен өңделетін амалдар жиынтығын қамтамасыз етеді. Монитор объектінің қалып – күйін сақтайтын айнымалылардан және оларға қолданылатын амалдарды жүзеге асыратын процедуралардан тұрады. Процесс осы монитор процедурасын шақыру жолымен монитордағы айнымалыларға қатынауды алады. Өзара шығарып тастаулар бір монитордағы процедуралар параллель орындала алмайтындай айқын емес қамтамасыз етіледі. Бұл await операторлары кепілдік беретін айқын емес өзара шығарып тастауларға ұқсас. Мониторлардағы шартты синхрондау шартты айнымалылар көмегімен айқын қамтамасыз етіледі. Олар семафорларға ұқсас, бірақ анықтамасында ерекше айырмашылықтары болады, және сондықтан сигналдау үшін қолдануда.

Өзара әрекеттесу және синхрондау үшін мониторларды қолданатын параллель программаның екі типті модулі болады: активті процесстер және пассивті мониторлар. Барлық бөлінетін айнымалылар монитордың ішінде деген шарт бойынша екі процесс бір ғана монитордың процедурасын шақыра отырып өзара әрекеттеседі. Алынатын модульдік екі маңызды артықшылығы бар.

Біріншісі – монитор процедурасын шақырушы процес процедураның нақты іске асуы туралы білм еуі мүмкін.

Екіншісі – мониторлық программисті монитор процедуралары қайда және қашан қолданылатындығы туралы қам жемесе де болады және көрінетін процедураларды және оның жұмысының нәтижесін өзгертпей оның жұмысын еркін өзгертуге болады. Осы ерекшеліктері процесстер мен мониторлпрды құрады, параллель программаларды тәуелсіз құру мен түсінуді жеңілдетеді.

Өзінің пайдалылығы мен тиімділігіне сай мониторлар бірнеше программалау тілдерінде қоодалынады, мысалы Java. Мониторлардың синхрондау механизмі негізінде сондай-ақ unix операциялық жүйесіде жасалған.

Монитор бөлінетін ресурстарды (кластарды) өрнектеу мен жасауды топтастыру үшін қолданылады. Ол интерфейстер мен денеден тұрды. Иетерфейс ресурстар берген амалдарды анықтайды. Дене ресурс қалып-күйін көрсететін айнымалылардан, және интерфейс амалдарын жасайтын процедуралардан тұрады.

Интерфейс (Interface-inter-өзара, і face-бет жағы) - 1) программалаушылардың кәсіптік тілінде - өзара әрекеттесу "жазықтығы", пайдаланушы мен компьютердің қарым-қатынасы, яғни екі жүйенің немесе адам мен компьютердің өзара мәліметтер алмасуын жасақтайтын аппараттық-программалық құралдардың жиынтығы; 2) есептеуіш жүйе құрылғыларының не (немесе) программалардың өзара әсерлесуін жасақтайтын құралдар мен ережелер жиынтығы; есептеуіш жүйедегі құрылғыларды үйлестіру немесе жүйелер арасында үйлестіруге пайдаланылатын үйлестіргіш техникалық және программалық құралдар жиынтығы; жүйелердің, құрылғылардың немесе программалардың екі арасын бөлу шекарасы; екі қызметтік құрылғының және олардың қосылу, алмасу сигналдары және т.б. сипаттамаларымен анықталған шекарасы; 3) ішкі программаға басқаруды беру мен бастапқы программаға қайту процедурасы туралы сипаттамалар мен келісімдер жиынтығы.

Мониторлар әр түрлі программалау тілдерінде әртүрлі хабарланады. Және құрылады. Қарапайымдылық үшін, монитор статистикалық объект деп, ал дене мен интерфейс төмендегідей сипатталған деп есептейік:

Monitor mname{

объявления постоянных переменных

операторы инициализации

процедуры}


Процедуралар көрінетін амалдарды іске қосады. Тұрақты айнымалылар монитор денесінің барлық процедурасына бөлінеді. Олар тұрақты деп аталады, себебі мониторлар болғанға дейін болады және өзінің мәнін сақтайды. Процедуралар, әдеттегідей, көшірмелері әрбір функцияны шақырған сайын сақталатын жергілікті айнмалыларды қолдануға болады.

Монитор деректердің абстррактілі типінің өкілі ретінде үш қасиетке ие.

Біріншіден,монитордан тыс проседура атаулары ғана көрінеді- олар мониторды хабарлаудың жалғыз ғана «қабырғадағы терезні» көрсетеді.Сонымен,тұрақты айнымалылармен көрсететін ресурстың қалып-күйін өзгерту үшін прцесс монитордың бір прцедурасын шақыру керек. Процедураны шақыру келесі түрде болады:

Call mname.opname(arguments)

Мұндағы mname – монитор атауы, opname -аргумннттері шақыратын олардың бір амалдарының атауы. Егер opname атауы прцесс прцедурасын шақыратын көріну аймағнда ерекше болса,онда прцедура шақырундағы “mname.” бөлігі міндетті емес.

Екіншіден,монитордың ішіндегі операторлар (хабарлау мен процедуралардағы) монитордан тыс хабарланған айнымалылырды шақыра алмайды.

Үщіншіден,тұрақты айнымалылар оның прцедкралары шақырылғанша инициализацияланады. Бұл мониторды құру кезінде инициализацияланатын операторларды орындау жолымен жсалған,және сондықтан оның прцедурасы шақырылғанға дейін.

Монитор ниварианты-тұрақты айнымалылардың «сапалы» прцесстердің оны шақырмайтын қалып-күйін құру керек, ал әрбір процедра оны қолдауы керек (монитор инварианты кең ауқымды инвариантқа ұқсас, бірақ бір мониторлы айнымалылар үшін). Инвариант жолы # # символы мен басталады.

Символ (грекше symbolon - танымдық белгі, таңба, рәміз, пернелеу) лингвистика, логика, математика ғылымдарында таңба ұғымын береді; өнерде, философияда нәрсенің, құбылыстың қасиетін, сыр-сипатын бейнелеп, астарлап білдіретін әмбебап эстетикалық категория.
Инвариант (лат. invarians,ілік тұлғада invariants өзгермейтін) - тіл бірліктерінің нақты нұсқаларынан (варианттарынан) дерексізденген тіл жүйесіндегі абстракты элемент.

Тізбекті программалау тіліндегі деректер абстракциясының механизмі мен монитордың айырмашылығы, прцесстердің параллель опындауларын бірге қолданады. Сондықтан, мониторларда орындалатын процесстердегі өзара шығарып тастаулар, ал белгілі бір шарт орындалғанға дейін жұмысты тоқтата тұру үшін- шартты синхронау қажет болуы мүмкін.

Синхрондауды прграммалауда өзара шығарып тастаулар мен синхрондауды әр түрлі әдіспен орындау қажет. Ең дұрысы өзара ықпал ету автаматты турде алынғаннан көрі өзара шығарып тастау айқын емес болғаны дұрыс. Шартты синхрондауды айқын программалау керек, өйткені әр түрлі пргроммалар әртүрлі шартты синхрондауды қажет етеді.

Сұрақтар мен жаттығулар

1 Келесі программаны қарастырыңдар:

Intx=0, y=0;

Parallel:x=x 1; x=x 2;

//y=x 2; y=y-x;

а) әрбір меншіктеу опероторы бір машиналық инструкциясымен жасалады, және сондықтан бөлінбейді деп есептейік. Қанша мүмкін тарих бар? х және у айнымалыларының мүмкін соңғы мәндері қандай?

б) әрбір меншіктеу операторы үш бөлінбейтін амалдарымен жасалады, регистрлерді жүктейді, регистрлердегі мәндерді қосады және азайтады, ал одан жүктейтін нәтижесін сақтайды. Қазір неше мүмкін тарихы бар? х және у айнымалыларының мүмкін соңғы мәндері қандай ?

2. Келесі программаны қарастыр:

int u=0, v=1,w=2,x;

Parallel: х=u v w;

// u=3;

// v=4;


// w=5;

Жеке айнымалыларды оқу және жазу бөлінбейтін әрекеттер делік:

а) егер u v w өрнегінің мәні солдан, оңға қарай есептелсе х айнымалысының қортынды мәндері қандай?

б) егер u v w өрнегінің мәні кезкелген ретпен есептелсе х айнымалысының қортынды мәндері қандай?

3. Келесі программаны қарастыр:

Int x=2, y=3;

Parallel: //

а) х және н айнымалысының қортынды мәндері қандай?

б) үшбұрыш жақшалар алып тасталған, ал әрбір меншіктеу операторы үш бөлінбейтін амалмен жүзеге асырылады : айнымалыларды оқу, қосу немесе айнымалыға жазу. Енді х және у айнымалыларының қортынды мәндері қандай?

4. Бөлінбейтін жіберулер. Бір өндіруші процесс пен п қолданушы процесс ортақ буферді бөледі делік. Өндіруші буферге орналастырған әрбір хабарын барлық п қолданушы алнуы керек, және тек содан кейін ғана өндіруші буферге келесі хабарды орналастырады:

а) осы есептің шешуін синхрондау үшін семафорды қолданып құр;

б) буфер в ұяшықтан тұрады делік. Өндіруші тек бос ұяшықтарға ғана хабар орналастырады, және әрбір хабарды барлық қолданушылар ұяшық қайта қолданылғанша хабарды алуы керек. Одан басқа қолданушылар хабарды буферге орналасқан реті бойынша алу қажет. Бірақ қолданушылар хабарды әр түрлі уақытта алуы мүмкін. Мысалы алынған хабарлар жылдам және бояу қолдануы арасындағы айырма в-ға жету мүмкін. а) пунктте жауапты толықтыр, жалпы есепті шешу үшін жауапты толықтыр.

5. Философтардың түскі асы туралы есеп вилкаға емес философтар күйіне негізгі назар аударып шығарыңдар. Логикалық айнымалылар массив; егер философ ас ішсе, онда элементі ақиқат, әйтпесе жалған.

а) кең ауқымды инвариант құр, үлкен модульді шешім құр, одан кейін синхрондау үшін кіші модульдысемаформен бірге. Шешімде өзара бұғаттаулар болмауы керек, бірақ жеке философ шексіз ашығуы мүмкін.

б) философтар шексіз ашықпайтында, яғни егер философ ас ішкісі келсе, онда ақыр аяғында ішетіндей а) пунктіне жауапты өзгерт.

6. философтардың түскі асы туралы есепті , орталық басқару процессін қолданып шығар. Философ ас ішкісі келсе, ол басқарушыға хабарлайды және шешімін күтеді (яғни, оған екі вилка береді деп күтеді). Синхрондау үшін семафорды күтеді.Шешімде өзара бұғаттаулар болмауы керек және философтар шексіз ашықпауы керек.

7. Философтардың түскі асы есебінде, философ қай вилканы алғаны туралы жеребе тастайды.

а) осы есептің толық симметриялық шешімін құр.

Симметрия (гр. symmetrіa - мөлшерлес) - Жиі кездесетін математикалық ұғымдардың бірі, центрге немесе өс жазықтығын қатысты алғанда бірдей пішінді.фигуралардың орналасуы.
Барлық философтар бір алгоритим бойынша жұмыс істеуі керек. Синхрондау үшін активті күту, семафорлар немесеғ екеуін де қолданыңдар. өзара бұғаттаулар болмауы керек, бірақ жеке философ шексіз ұзақ ашығуы мүмкін, аз ықтималдықпен (егер екінші вилканы қатынау болмаса, философ бірінші вилканы қойып және қайта жеребе тастайды);

б) шексіз ашығуы болдырмау .үшін а) пунктіне жауапты кеңейт. Өз шешіміңді түсіндір.( Нұсқау бір философ қасындағы көршісі ас ішпегенде екінші рет қатарынан ас ішпеуі үшін қосымша айнымалылар енгіз).
8 Лекция. Параллель алгоритмдер.

Берілген тараудағы 1-бөлімінде біз әртүрлі сұрыптау алгоритмдерін қарастырамыз:



  1. Аттап өту сұрыптамасы (ранг әдісі)

  2. Салыстыру және ауыстыру сұрыптау алгоритмі.

● Салыстыру және ауыстыру

● Көпірші әдісмен сұрыптау және «тақ-жұп» сұрыптау.

● Бірігу сұрыптауы

● Жылдам сұрыптау

екінші бөлімде – параллельдеудің сандық әдістері: матрицаларды көбейту; сызықтық теңдеулер жүйесін шешудің тура және итерациялық әдістері.

5.1. Ранг әдісімен сұрыптау

сұрыптаудың бұл түрінің екінші атауы – аттап өту сұрыптауы. (Wilkinson6 B. and Allen6 M., 1999). Бұл сұрыптаудың негізгі идеясы: берілген сандардың ішінен таңдалғаннан аз сандарды санаймыз. Бұл санау тізімдегі таңдалған санның позиция нөмерін қамтамасыз етеді, яғни тізімдегі оның «рангін» табамыз.

Позиция (лат. posіtіo - орны, жағдайы, орналасқан жері) - Қандай да бір нәрсенің орны, орналасуы (мысалы, шахмат тақтасындағы фигуралардың позициясы); Шекті музыкалық аспаптың мойнындағы сол қолдың бір жерде тұрып, дыбыстардың белгілі бір кезектігін орындайтын орны; Классикалық бидегі қолды ұстап тұру мен аяқтарды қоюдың бұлжымас ережелері.

a[0],a[1],…, a[n-1] массивіндегі сақталған n саны берілген деп есептейік. Ал нәтижелері сұрыпталған b[0], b[1], … , b[n-1] массивінде сақталған. Тізбекті коды келесі түрде сипатталуы мүмкін.
For (i=0; i

{

x=0



For (i=0; j

If (a[i]>a[j]) x ;

B[x]=a[i]; // копирует номер в провильное место

}

Сұрақ: Қандай жағдайда берілген код сәтсіз болады? Талданған жағдайды ескере отырып программа жаз.

Осы кодты n процессор үшін қайта жазуға тырысамыз.

n процессор бар деп есептейік. Әрбір процессор бір санға бекітілген. Бұл жағдайда әрбір процессор сандардың біреуінің соңғы индексін О(n) қадамға яғни time complexity=O(n) табу.

Мұнда біз forall операторын қолданамыз, мұндағы i-процессор нөмері.

Forall (i=0; i

{x=0;

for (j=0; ja[j]) x ;



b[x]=a[i];

}
көптеген программаларда, дербес жағдайда, сұрыптау орындайтын программада ағымдағы сандарды уақытша қажетті қосымша айнымалыға орын бөлінеді, келешекте басқа санмен позициясын алмастыруды жүзеге асыратын әдістеме қарастырылады.

Төмендегі осы уақытша айнымалыларды қолданбайтын әдісті қарастырамыз.
5.2. Салыстыру-және-ауыстыру

А және В екі сан бар деп есептейміз.

Салыстыр және ауыстыр амалы тізбекті кодта төменде көрсетілген:

If (A>B)


{temp=A; A=B; B=temp;}

берілген ситуация хабар беру жүйесі үшін келеді.

Р1 және Р2 екі процессоры бар деп есептейік. Р1 А-дан Р2. В-дан тұрады. 18-суретте мүмкін салыстыру және ауыстыру схемасының бірі келтірілген:
Последовательность шагов
Последовательность шагов





Send(A)












If A>B send (B)

Else send(A)

If A>B load(B)

Else load(A)
18-сурет. Салыстыру және ауыстыру 1-ші схемасы.

Бұл схеманың коды төмендегідей:



Р1 Процессор

Send(&A6P2);

Recv(&A,P2);

{send(&B,P1);

B=A;}

Else


Send(&A,P1);

Р2 Процессор

Recv(&A6P1);

if(A>B)


Келтірілген схеманың әдісі мына түрде болады:

Келтірілген схеманың әдісі мына түрде болады:


Р1

Send(A)










Send(B)


If A>B load (B) if A>B load (A)

19-сурет. Салыстыру және ауыстыру 2-ші схемасы
Бұл схема коды төмендегідей:


Р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
88

50

28

25


процессор және n саны делік. n/p сандардың тізімі әрбір процессорге бекітілген (Wikinson, B. And Allen, M., 199). Схема 1 және схема 2 сандарды әдісімен сұрыптау үшін


Слияние


88

50



28

25



98

88

80



50

43

42



28

25


Хранит большие числа

98

80



43

42

Хранит меньшие числа

қ
43

42

28

25


олданамыз:

20-сурет. Екі ішкі тізімді біріктіру. Схема 1.





98

88

80



50

----


43

42

28



25

Исходные числа

Слияние

98

80



43

42


98

88

80



50

43

42



28

25


Хранит большие числа (конечные числа)

98

80



43

42







88

50

28

55



88

50

28



25





Исходные числа



Хранит большие числа (конечные числа)

21-сурет. Екі ішкі схеманы біріктіру. Схемасы 2.

Сонымен, екі ішкі тізімді жалпы әдісі төмендегідей:

Әрбір процедурада сұрыпталған тізімді сақтау керек және енгізу тізімі бар сақталған тізімі.



5.2.2. Жылдам сұрыптау

Гиперкубтағы жылдам сұрыптау

Біз саннан тұратын тізім бар деп есептейміз, ол алғашында d өлшемді гиперкуб торабының біреуіне орналастырылған. әрбір тораптың сәйкес номері бар.

P0


4

2

7

8

5

1

3

6


P0

P4



3

2

7

4


























5

7

8

6

8

6

5

7

P0

P2


P4

P6


8

7






P0

P1


P6

P8











6

















Pivot


22-сурет. Жылдам сұрыптау.

Жоғарыда сипатталған жылдам сұрыптау алгоритмінің процесі келесі схемада сәйкес көрсетіледі:

1-қадам: 000 001 (числа, большие чем pivot, идут на Р1)

2-қадам: 000 010 (числа, большие чем pivot, идут на Р2)



001 011 (числа, большие чем pivot, идут на Р3)

3-қадам: 000 100 (числа, большие чем pivot, идут на Р4)



001 101 (числа, большие чем pivot, идут на Р5)

010 110 (числа, большие чем pivot, идут на Р6)

011 111 (числа, большие чем pivot, идут на Р7)

Соңында осы бөліктер тізбекті алгоритмді қолдана отырып сұрыпталуы мүмкін, ал бәрі бірге параллель.


9 Лекция. Сандық әдістерді параллельдеу.

Матрицаларды блокпен көбейту

Каннон алгоритмі

Страссен алгоритмі

Гаусс әдісі

Якобидің итерациялық әдісі


Матрицаларды көбейту

AxВ матрицаларды көбейтудің тізбекті коды былай болуы мүмкін:

For (i=0; i

For (i=0; j
{

c[i][j]=0

For (k=0; k

C[i][j]=c[i][j] a[i][k]b[k][j];

}
Берілген алгоритм n алгоритмді қажет етеді, яғни тізбекті орындалу уақыты О(n).

Матрицаларды блокпен көбейту

әрбір берілген матрицаны ішкі матрица деп аталатын элементтер блогына бөлеміз (Ananth Gama, Anshul Fupta and George Karypis6 Vipin Kumar,2003). Біздің жағдайымызда біз s ішкі матрица аламыз (s көлденең, s төмен).

әрбір ішкі матрицаның х элементтері болады (n/s-ті m деп белгілейміз).

Сонымен, А - ішкі матрица, мұндағы р-жолдар номері, ал q-бағандар номері.

Матрицаларды көбейтудің паралель коды келесі түрде анықталуы мүмкін. (23-сурет):

C11 C12

C21 C22


B11 B12

B21 B22


A11 A12

A21 A22

= X



23-сурет. Матрицаларды блокпен көбейту

берілген алгоритмнің орындалу уақытын бағалайық:

?

Каннон алгоритмі

p процессорлар торус типті желімен байланысқан делік..

А,В,С – рхр блокты матрица, әрбір квадрат блок n/p дәрежелі (I,j) блокты (I,j) процесске орналастырайық әрбір процесс келесі схемамен жұмыс істейді:

Қадам 1.


● А матрицасындағы менің блогымды I орынға батысқа жылжытамыз.

● В матрицасындағы менің блогымды j орынға солтүстікке жылжытамыз.

● менің С блогымды оған А және В-ң менің жаңа блоктарымен көбейтіндісін қосу арқылы түрлендір.

Қадам k,k=2,3, …, p.

● А матрицасындағы менің блогымды бір орынға шығысқа жылжытамыз.

● В матрицасындағы менің блогымды бір орынға оңтүстікке жылжытамыз.

● менің С блогымды оған А және В-ң менің жаңа блоктарымның көбейтіндісін қосу арқылы түрлендір.

Сұрақ: каннон алгоритмінің орындалуы қандай?

Страссен алгоритмі

А,В және С-ны 2х2 блоктар матрицасына бөлейік. Әдеттегі алгоритм матрицалардың 8 көбейтіндісінен тұрады (және 4 қосу амалы). Старссен алгоритмі келесі қадамдардан тұрады:

Анықтаңдар
?

Сонымен, матрицаларды көбейтудің жалпы саны =7 (және 18 қосу амалы).


Сызықтық алгебралық теңдеулер жүйесін шешу

Бұл пунктте біз сызықтық теңдеулер жүйесін шешудің тура әдісімен қарастырамыз: белгісіздерді шығарып тастау – Гаус әдісі және итерациялық әдіс Якоби әдісі.

Алгебралық теңдеу - екі алгебралық өрнекті теңестіруден шығатын теңдеу.

Гаусс әдісі

Ах=b сызықтық алгебралық теңдеулер жүйесін шешу қажет болсын.

Мұндағы

А – берілген коэффициенттер матрицасы

b- берілген вектор

х-белгісіз вектор

белгісіздерді шығару әдісі – Гаус әдісі А матрицасын көбейткіштерге жіктеуден тұрады:

PA=LU


Мұндағы

L – төменгі үшбұрыш матрица

U – жоғарғы үшбұрыш матрица

Р-ауыстыру матрицасы, яғни Р – А сияқты матрица, бірақ оның жолдары ауыстырылған.

Сонымен, біз үшбұрыштың теңдеулер жүйесін шешеміз:

Ly=Pb және Ux=y

Алдымен у-ті, одан кейін х-ті табамыз.

PA=LU


Көбейткіштерге жіктеуі жылжымалы нүктесі бар ең үлкен амалдар санына тұрады, 2n/3 O(n).

А матрицасының жолдарын Р-ға реттеуді pivoting (беру) деп аталады. Бұл сандық орнықтылық үшін қажет.

Біз жартылай бұрудың стандарт схемасын қолданамыз: бұл L оның диагоналлінде 1-лер бар және басқа элементтері модуль бойынша 1-мен шектелген деген сөз.

Гаусс әдісінің қарапайым нұсқасы – бас элементті таңдау. Ол А матрицасының бір жолдарын басқа жолдарға қосып, диагональ астындағы элементтерін 0-ге айналдыру керек. Сонда Гаусстың алгоритмінің тізбекті коды мынадай:

?

Ары қарай біз A(I,j,k,l) белгілеуін қолданамыз, бұл i-ден j-ге дей3н жолдары ж2не к-дан 1-ге дейінгі бағандары бар ішкі матрица деген сөз.



Сонда берілген алгоритмнің параллель кодын былай жазуға болады (Ananth Gama6 Anshul Fupta and George Karypis6 Vipin Kumar6 2003):

?

Бір қатарын түрлендіру ең үлкен жұмыс, түрлендіру өзінен кейін (n-k)x(n-k) өлшемді A(k 1:n,k 1:n) ішкі матрицасын алып жүреді, олардың әрбіреуі паралель жаңартылуы мүмкін.



Процессорлер конвейерлік онфитгурацияға қайта құрылуы мүмкін.

?

хабар беру бір қадамда жасауы мүмкін деп санайық, n-1 хабар беру болады,олар тізбекті орындалу керек, өйткені жолдар әрбір хабар беру аралығында өзгереді, I – ші хабар беру n-i 1 элементтен тұрады.



Сонымен, өзарабайланысты қажетті уақыт:

tcomm= (n-i 1)t=

= (n-1)t t

жол жіберілген кейін, әрбір pi процессорынан жоғары pi процессоры хабар алады, оның көбейткішін есептейді, және берілген жолдың n-j 2 элементіне әсер етеді. Көбейткіштерді есептеуді ескермей n-j 2 көбейтінді және n-j 2 айырыма жасау қажет.

Сонымен, жалпы есептеу уақыты:


tcomp=2
Якоби итерациялық әдісі

a[][] және b[] теңдеу тұрақтыларынан тұратын белгісіздерден тұратын x[] массиві берілген, сондай-ақ қажетті итерациялар санын (limit) таптық деп есептейік, сонда Якоби алгоритмінің тізбекті коды келесі түрде көрсетіледі.

For (i=; i

{x[i]=b[i];

for (it=0; it

{for (i=0; i

{ sum=0;

for (j=0; j

if (i!=j) sum=sum a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];}

for (i=0; iОсы кодты паралельдейміз. Кез келген белгісіз үшін бір процесс белілген және әрбір итерацияда жақын арада есептелінген белгісіздер саны басқа барлық процесстерге берілуі керек.

Паралель кодта біз нақты бір барьер қосылуы керек, pi процессі төмендегі түрде болады:

x[i]=b[i];

for()it=0;it

{ for()j=0;j

sum=sum a[i][j]*x[j];

new_x[i]=(b[i]-sum/a[i][j];

broadcast_receive(&new_x[i]);

global_barrier();}

Хабар беру шаблоны - broadcast_receive(), жақын арада есептелген x[i] мәнін процесінен басқа кез-келген процеске жібереді және басқа процесінен жіберген деректерді жинайды.

Сонымен, broadcast_receive() n хабар беруден тұруы керек, олардың әрбіреуі белгілі бір параметрмен.

Біз теңдеу n және p процессоры бар делік. Процессор n/р белгісіздерін амал орындайды. - итерациялар саны. Бір итерацияда есептеу фазасы және байланыс фазасы бар.

Сонда есептеу уақыты:
t=n/p(2n 4)

Ал байланыс уақыты:




10-12 Лекция. Параллель программалау. Программалау тілдері.

Берілген тарауда программалау құралдары қарастырылады, дербес жағдайда хабар беруді және процесстерді синхрондауды ұйымдастыру үшін кітапханалар дәлірек сипатталады: PVM, MPI,BSP,OpenMP.
Кітапхана - мәдени-ағартушылық мекеме. Кітапхана баспасөз шығармаларын жинау, сақтау, насихаттаумен, оқырмандарға баспасөз шығармаларын берумен, мәдени-ағарту және ғылыми-көпшілік жұмыстарын ұйымдастырумен шұғылданады.
сондай-ақ параллель программалау тілдері:Occam, HPF

PVM-Параллель виртуальды машина

Автопараллельдеу циклдың өзімен, циклды қайта реттеу мүмкіндігімен жиі шектеледі, әсіресе көмекші программаларды сұрыптауларға тәуелді программалар тууы мүмкін.

Параллель программалауда түсініктемелер түрінде өрнектелген платформа аралық жылжуды, тізбекті архитектураны қоса компилятор директиваларын жиі қолданады.

Платформа (фр. plate – жайпақ, forme - форма) - геологияда қозғалмалығы біршама аз, жазық немесе үстірт тәрізді бедерлі, екі жікқабатты құрылымдық қабаттан – іргетастан және шөгінді тыстан тұратын жер қыртысының кең ауқымды атырабы.
Сондай-ақ PVM, MPI кітапханаларын қажет ететін тізбекті тілдердің кеңейтулерін қолданады.

Хабар беру моделіне кіретін PVM параллель моделін қарастырайық.

Параллель виртуальды машинаны жалпы есептеу нәтижесін алуға қатысатын көптеген есептерді орындауға арналған нақты есептеу комплексінің құралының (процессор, жады, сыртқы құрылғылар және т.б.)бір бөлігі деп анықтауға болады. жалпы жағдайда есептер саны PVM-ге (http:/www.netlib.org/pvm3/pvm3.4.beta4.Win32.zip қара) кіретін процессорлар асып кетуі мүмкін. параллель виртуальды машинасы ретінде жеке алынған дербес компьютер, сондай-ақ параллель архитектурасы бар суперкомпьютері бар жергілікті желі, универсал ЭЕМ, графикалық жұмыс станциялары және дербес компьютерлер бола алады. Осы программалық жасау негізінде қолданушы көптеген есептер параллель орындалу мүмкіндегі бар бір ғана есептеу машинасымен сұхбаттасады деп есептеуге болады.

PVM-нің жұмыс істеуі онда орындалатын есептер арасындағы хабар алмасу мүмкіндігіне сүйенеді. мұндай жағдайда PVM-ді виртуальды машинаға бірнеше процессор және жалпы немесе жеке ЖСҚ-жедел сақтау құрылғысын-ОЗУ (шартқа байланысты) бөліп көппроцессорлы есептеу комплексінде жасаған ыңғайлы. бұл жағдайда,PVM-дегі есептер арасындағы жылдам ақпарат алмасу мәселелері жеңілдейді, сондай-ақ әртүрлі процессорлар орындайтын есептер арасындағы деректерді өрнектеу форматтарын мақұлдау мәселелері жеңілдейді.

Формат (фр. format - формаға келтіру) полиграфияда дайын басылымның мөлшері (мысалы 170 • 260 мм) немесе баспа қағазының мөлшері (60x90 см); полиграфияда теру форматы терілген жолдың ұзындығы мен биіктігі; басу қағазының форматы - қағаз рулонының ені немесе парақ қағаздың ені мен ұзындығы.

PVM-ді қолданудың басты мақсаты- есептеулер жылдамдығын оларды параллель орындау арасында арттыру. Тиімділіктің жоғарғы шекарасы қарапайым бағаланады- егер есептеуүшін бір процессор орнына N біртипті процессорларды қолданса есептеу уақыты N рет кемиді. Нақты ұтыс есептің ерекшелігіне және есептеу программасында есептің ерекшелігі және PVM-нің аппараттық және программалық сипаттамасы қаншалықты ескерілгеніне байланысты.

PVM мен қатар берілген моделідің графикалық интерфейсі- XPVM. XPVM процестердің жүктеу уақытын, күту уақытын, хабар жіберу уақыттарын көруге мүмкіндік береді.

PVM-3 жүйесіндегі белгілі бір процессордан жіберілген әрбір есеп бүтін санмен анықталады, оны есеп идентификаторы деп атайды. Және мағынасы жағынан Linux операциялық жүйесіндегі процесс идентификаторына ұқсас. Мұнда, PVM-нің N процессінде параллель жіберілген бір орындау файлының көшірмесі әртүрлі TID бар N есеп құрады.

PVM-дегі есептердің өзара әрекеттесуіндегі берілген модельде бір PVM-дегі кез келген есеп кез келген басқа есепке хабар бере алады, және осындай хабар өлшемі мен саны шектелмеген. Буферлік құрылғыларының толып кетуін және массивтерді бақылау тек жеке операциялық жүйелерді енгізуге келіп тіреледі.

Бақылау - зерттеу не тексеру әдісі. Бақылау арнайы жоспар бойынша жүргізіледі. Жоспарда Бақылаудың мақсаты мен міндеттері, объектісі (сабақ, саяхат, лабораториядағы, шеберханадағы, оқу-тәжірибе учаскесіндегі оқушылардың жұмыстары), жүргізу әдісі мен жолдары дұрыс көрсетілуі тиіс.

Есеп аралық ақпарат алмасудың тиімділігін арттыру үшін бірнеше алгоритмдерді қолдану керек. Жеке жағдайда буғатталған хабар жіберу алгоритмін қолдануға болады, "хабар беру " функциясы мәнін қайтарады (яғни жұмыс аяқталады). Мұндай жеткізілгендігі туралы хабарды күтетін хабар беру алгоритмі ұзын хабар бірнеше бөліктерге жіберілгенде, сондай-ақ орындау реті уақыт бойынша қатаң бекітілген командалар алмасуы кезінде қолданылған дұрыс.

Хабар беру және қабылдаудың блокты емес алгоритмін қолданғанда "әңгімелесушінің"жауабын күту кезіндегі процессорлар тоқтап қалуын азайтады. Әсіресе бұл қабылдаушы жағында хабардың келу уақыты белгісіз болғанда аса тиімді. Қабылдау процессорының жұмысын, тек арасында қабылдау буферін сұрай отырып, хабар күту кезінде ағымдағы жұмысты орындайтындай етіп ұйымдастыруға болады.

Берілген модель гетерогенді компьютер жиынын бір жоғары тиімді параллель машина ретінде жұмыс істеуге мүмкіндік береді. Берілген модельді қолдануда деректер форматындағы өзгешелікткрі мен тораптар жылдамдығындағы өзгешеліктерді түсіну маңызды.

Жіберуші және қабылдаушы жақтарындағы буферлік массивтер үшін жады динамикалық бөлінеді, яғни хабарлардың максимальды көлемі қатынау жадысының көлемімен шектелген. егер PVM-де жіберілген бір есеп, басқа есептермен сұхбаттасу үшін қажетті жадыны ала алмаса, онда ол қолданушыға сәйкес есептер бұл оқиға туралы хабар береді, бірақ басқа есептер бұл оқиға туралы хабардар болмайды және оған хабар жіберуді жалғастыра береді.

Тораптар, басқа қолданушылармен бөліну үшін қажет, сондықтан жоғары тиімді желі қажет болады.

PVM- функциональды сұраныстар.

Процессті құру және хабар беру функциясы C/C /Fortran програмаларынан шақырылады. Негізгі функцияларды қарастырамыз:

pvm spawn-процесс тудырады

pvm send- белгіленген процесске асинхронды хабар береді.

pvm recv-белгіленген процесстен немесе басқа кез келген процесстен бұғатталған қабылдау

pvm nrecv-бұғатталмаған қабылдау

pvm mcast-белгіленген процесстерге дерек жіберу.

Келесі функцияларды қолданып буферге/буферден буып түйеді/шешеді:

pvm pkint- бүтін сандарды(бір немесе одан көп) буып түйеді

pvm upkint- бүтін сандарды(бір немее одан көп) шешеді

pvm spawn функциясын толығырақ қарастырайық:

pvm spawn (char*task, char**argv,

int flag, char*where,

int ntask,int*tids);

task- туындалатын есеп атауы;

argv- соңында нольдік символы бар есептер параметрі

flag- нұсқалар(0 есептерді қай жерде туындалатынын анықтау

PVM-ге беріледі )

where- есептің қайда туындалатынын анықтайды

ntask-туындалатын есептердің көшірме саны;

tids- туындалатын есептер идентификаторы, int туындалған есептер санын қайтарады.

буып-түюі/шешуімен қатар хабарды жіберу немесе алу үшін буферге келесі функцияларды қолданып орналастыру керек:

pvm initsend, pvm mkbuf, pvm setsbuf

pvm initsend(int encoding)-хабар беру үшін келісім бойынша ағымдағы буферді инициалдайды; әдетте кодтау үшін PvmdatdDefault-ны қолданады.

pvm mkbuf(int encoding)- жіберу үшін жаңа буфер құрады және идентификаторды қайтарады;

pvm setsbuf(int bufіd)- буферге жіберіп/алу үшін ағымдағы буферді bufіd атауымен орнатады;

pvm send (int tid, int msgtag)

tid- хабар жіберуші идентификаторы;

msgtag- осы хабар тегі

pvm send топтық нұсқау tid пен идентификацияланған барлық есептерге хабар жібереді.



PVM-ге даярлау

Pvm spawn() функциясы үшін орындалатын фуекция белгілі бір каталогта болады. Linux-те есеп $PVM ROOT/bin/$PVM ARCH/ және $HOME/PVM/bin/$PVM ARCH каталогтарынан 3зделед37

PVM ROOT/usr/local/pvm/current жиынтығы.



Pvm -ді орындау үшін master және slave-ті компиляциялап және байланыстыру үшін aimk қолдану керек.

Pvm -ді жіберу үшін pvmd.exe - даменін қолдану керек. Жаңа компьютерлерді қосу керек: addhost<хост атауы>. Тапсырманы орындау үшін spawn->
1   2   3   4   5   6

  • 7 Лекция. Программалау тілдерінің синхрондау деңгейі. Синхрондау типтері. “Өндіруші –пайдаланушы” типті синхрондау.
  • Инвариант
  • 8 Лекция. Параллель алгоритмдер.
  • 5.1. Ранг әдісімен сұрыптау
  • 5.2. Салыстыру-және-ауыстыру
  • 9 Лекция. Сандық әдістерді параллельдеу. ● Матрицаларды блокпен көбейту
  • Якобидің итерациялық әдісі Матрицаларды көбейту
  • Сызықтық алгебралық теңдеулер
  • 10-12 Лекция. Параллель программалау. Программалау тілдері. PVM-Параллель виртуальды машина MPI – хабар беру интерфейсі
  • PVM-Параллель виртуальды машина

  • жүктеу 1.28 Mb.