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

Кафедра меңгерушісі ___________________ Джарасова Г.С.

ФМжАТ факультетінің оқу-әдістемелік кеңесімен мақұлданды 2014 ж. «_____»______________ №____хаттама

ОӘК төрағасы __________ Искакова А.Б. 2014 ж. «____»_____________

1 Оқу пәнінің паспорты
Пәннің атауы PV 4305 «Параллельдік есептеулер»
Кредиттер саны және оқу мерзімі

Барлығы – 2 кредит

Курс: 4

Семестр: 7

Аудиториялық сағаттар – 37,5 сағат (дәріс -15 сағат, практикалық сабақтар –7,5 сағат, зертханалық сабақтар – 15 сағат)

СӨЖ – 52,5 сағат (оның ішінде СӨОЖ – 15 сағат)
Бақылау формасы

Емтихан – 7 семестр

Алимова Жанар Сагидуллаевна

Информатика магистрі, аға оқытушы

Математика және информатика кафедрасы А корпуста (Ломов к-сі, 64) орналасқан, ауд. А-408, тел. 67-36-87 (ішкі 11-25)

«Параллельдік есептеулер» пәні есептеу жүйелерінің программалық жабдықтарының құрамын параллель өңдеу құралдарымен оқытуды ойластырып және де олар үшін арналған жоғары деңгейлі программа тілдерінің класстарын зерттейді.

Пәнді оқыту барысында параллелизмнің жетістікке жету тәсілдерінің қысқаша мінездемесі, ПЕЖ-нің мысалдары келтірілген. Сонымен бірге, параллель есептеулер жүйелерінің классификациясы келтірілген, ПЕЖ-де мәліметтерді берудің типтік топология жүйелері қарастырылған.

Пәннің мақсаты - компьютерлік құралдарды қолдана отырып параллельді программалау және мәліметтерді параллельді өңдеу негізінде білім алу және жұмысқа дағдылану.

Пәннің міндеттері - параллелизмнің жетістікке жетудің тәсілдерін меңгеру, ПЕЖ-нің мысалдарымен танысу, параллель есептеулер жүйелерінің классификациясы және ПЕЖ-де мәліметтерді берудің типтік топология жүйелері туралы ұғымдарын қалыптастыру.
4 Пререквизиттер және постреквизиттер

4.1 Пререквизиттер

Пәнді оқу барысында келесі пәндер бойынша қалыптасқан білік пен дағды қажет:

• 
  Алгоритмдер және алгоритмдік тілдер;
  
• 
  Жүйелік бағдарламалау;
  
• 
  Дербес компьютердің архитектурасы;
  
• 
  Компьютерлік желілер;
  
• 
  Сандық әдістер.
  

Пәнді оқу барысында қалыптасқан білім, білік және дағды алдағы уақытта

• 
  Объектілі бағытталған программалау;
  
• 
  Интернет үшін программалау пәндерін меңгеруде қажет.
  

Студент түсінуі керек:

• 
  есептеу жүйелерінің программалық жабдықтарының құрамын параллель өңдеу құралдарымен оқытуды;
  
• 
  жоғары деңгейлі программа тілдерінің класстарын;
  

• 
  параллельді компьютерлердің негізгі модельдері;
  

• 
  мәліметтерді параллель өңдеудің негіздері;
  

• 
  әр түрлі деңгейлерде программа құралдарының синхронизациясы;
  

• 
  мәліметтерді параллель өңдеудің негізгі алгоритмдері.
  

• 
  параллель алгоритмдерде қолданатын программалық жабдықтарды,
  
• 
  распараллельді программалау тілдерін,
  

• 
  компьютерлік құралдарды қолдана отырып параллельді программалауға
  
• 
  мәліметтерді параллельді өңдеуге.
  

• 
  MPI, OpenMP, PVM, MATLAB ортасында және де басқа технологиялар арқылы құрастыру мен программалау;
  

• 
  Кіріспе. Параллель есептеулер дамуының хронологиясы.
  
• 
  Параллель бағдарламалау бағытының дамуы.
  
• 
  Параллель компьютерлерге сұраныс
  

1. 
   Негізгі анықтамалар
   

Параллель бағдарлама дегеніміз - әрбір процесс оның өз процессорында орындалатын және сонымен бірге процесс параллель түрде орындалатын бағдарлама.

2. 
   Параллель бағдарламалау бағытының дамуы және параллель компьютерлерге сұраныс
   

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

Күнделікті тұрмыстағы қарапайым мысалдарды қарастырайық. Мысалы, көктемнің келуімен гүлдер ағаштарда да гүдейді, машиналардың өз жолы болады,бірақ олар жол үстінде бірге қозғалады. Майкл Куинн (Quinn, 1994) мысал ретінде оркестрді ұсынды: оркестрде бірнеше инструменттер барлығы бірге әдемі бір мелодияны ойнайды. Осыған ұқсас параллель процесті басқа да облыстардан көруге болады. Параллель коспьютерлер мен параллель есептеулерді қолданатын облыстарға шолу жасайық.

Күрделі жүйелерді сандық модельдеу: ауа-райын болжау, жаңалықтар, ағымдық космостық (полет) ұшу туралы жедел ақпарат. Ертеңгі ауа-райын болжайтын ауа-райы типті модельді есептеу уақыты 5 сағатта дайын болуы тиіс.

Бизнестегі коммерциялық қосымшалар: құрамына бейнеконференциялар, бірлескен жұмыс орталары, параллель деректер қоры, банк транзакциялары кіретін қосымшалар.

Техникадағы қосымшалар: медицинадағы автоматтандырылған диагноз, жер сілкінісін болжау және т.б.

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

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

Осының негізінде келесі мәселелер пайда болды:

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

Олар қалай шешілді? Компьютерлік жобалаушылар бір компьютрді түрлендіру үщін осы шектеулерді жоюға әртүрлі әдістерді пайдалана бастады:

• 
  конвейерлі өңдеу (бірнеше командалардың әртүрлі стадиялары бірмезгілде орындалады);
  
• 
  функционалдық модульдер жиыны (бірнеше көбейткіштер сумматорлар және т.б. жеке командалар ағынымен басқарылады);
  
• 
  әрқайсысының өзара байланысының (желінің) байланысқан логикасы, өз процессоры, жады бар бірнеше «компьютрлердің» бірігуі.
  

• 
  Параллелизм.
  
• 
  Деректер параллелизмі мен есептер параллелизмі.
  
• 
  Программалаудың негізгі параллель модельдері.
  

2.1. Деректер параллелизмі мен есептер параллелизмі

Қазіргі заманғы бірпроцессорлы машина бірнеше компоненттен тұратын белгілі.

Primary memory

CPU

2-сурет. Бірпроцессорлы машина.

● орталық процессор (CPU);

● алғашқы жады;

● бір және бірнеше деңгейдегі кэш-жады;

● екінші жады (дискідегі жады);

● әртүрлі сыртқы құрылғылар.

Программаның орындауына қатысты түйінді компоненттер: орталық процессор, кэш және жады.

Бірпроцессордың архитектурасын жақсартудың әртүрлі әдістері бар:

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

Параллелизм әр түрлі деңгейде топталуы мүмкін:

● тапсырма деңгейіндегі параллелизм;

● программа деңгейіндегі параллелизм;

● команда деңгейіндегі параллелизм;

● арифметикалық және биттік туралайтын параллелизм.

Тапсырма деңгейіндегі параллелизм – параллелизмнің жоғарғы деңгейі.

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

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

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

Программа деңгейіндегі параллелизмде пбір программа бөліктерге, оның құраушыларына бөлінеді.

Мысалы, матрицалардың көбейтіндісі: С=AxB матрицаларды квадраттарға бөлу жолымен есептеледі:

В11	В12
В21	В22

Жалпы, программа деңгейіндегі параллелизм екі әдіспен көрінеді:

● берілген программаның тәуелсіз бөліктердеге бөлу;

● итерациялар арасында ешқандай байланыс жоқ циклің жеке итерацияларын қолдану.

Параллелизмнің бұл түрін процессорлар жиынтығы немесе функциональды модулдер жиынтығын қолдануы мүмкін.

Программа деңегейіндегі параллелизмнің көруінуінің қарапайым мысалы: қосындыларын есептеу. Төменде екі массив элементтерінің қосындысын есептеу коды көрсетілген:

for (i=0; i

A[i]=B[i]+C[i]

Қосындылар тәуелсіз, яғни B[i]+C[i] есептеуі B[i]+C[i]-ге тәуелсіз, кез – келген j

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

Команда деңгейіндегі параллелизм

Программаның деңгейіндегі параллелизм – архетектураның төменгі деңгейі және компьютер ұйымдастыру саласына жатады. Параллелизмнің бұл түрін жүзеге асырудың жалпы әдісі – конвейерлер.

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

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

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

Мысалы, Cray фирмасының супен ЭЕМ-і вектордың ұзынығы – 64 бит немесе одан аз болғана неғұрлым тиімді және ұзын векторлардың кішкене бөліктеріне амалдар қолданатын қайта құру программалары жұмысты жақсарады.

Арифметикалық және биттік туралау параллелизм. Арифметикалық және биттік туралау параллелизмі – параллелизмнің ең төменгі деңгейі.

Параллелизмнің бұл деңгейі орталық процессордағы арифметикалық логикалық құрылғыға қатысты.

Мысалы, 64 битке қосынды екі түрлі әдісен есептелуі мүмкін:

1. 
   барлық 64 битті бірден қосу (неғұрлым маңызды биттерге тасымал кез-келген екі биттің қосындысының жылдамдығындай есептеуі және болжауы мүмкін);
   
2. 
   амалы 4 биттік бөлікке және 16 циклдағы толық қосындысын есептеуге болады.
   

Параллель программалық жасау үшін фундаментальды талаптар бар:

● параллелизм;

● масштабтылық (әр жақтылық);

● жергіліктілік;

● модульдік.

Параллелизм – көптеген амалдарды біруақытта орындауға қабілеттілік.

Әр жақтылық – процессорларды санын өсіруге «икемілік» қасиеті.

Жергіліктілік қашықтағы жадыға қатынаудың жергілікті жадыға қатынауына қатынастарының коэффициенттерінің жоғарылылығын білдіреді.

Модульдік – күрделі объектілердің қарапайым компоненттерге декомпозициясы.

0. 
   Программалау модельдері: параллель және тізбекті
   

Тізбекті модель.

Фон Нейман моделі:

● Командалар тізбегін орындауға қабілетті процессор;

● Команда берілген шаманың адресін анықтайды, орындалатын команданың немесе келесі команданың адресін жадыдан оқиды немесе жазады.

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

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

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

Параллель модель.

3-суретте қарапайым модель «есептер/каналдар» моделі көрсетілген.

3-сурет. Қарапайым параллель модель: «есептер/каналдар» моделі.

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

Есептер программа және жергілікті жадыны инкапсуяциялайды және ортамен өзара әрекеттесетін порттар жиынын анықтайды.

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

Параллель модельдерді қарастырғанда кейбір келісімдер мен абстракцияларды қабылдау қажет. Параллель программалық жасау үшін фундаментальдық шарттарды қолдану келесі абстракцияларды қабылдауға мәжбүр етеді:

● Параллель есептеу бір немесе бірнеше есептерді шешуден тұратын. Есептер бір уақытта орындалады. Есептер саны программаның орындалуы кезеңінде өзгеруі мүмкін.

● Есеп тізбекті программа және жергілікті жадыны инкапсуяциялайды. (шындығында, ұл Фон Нейманның виртуальды машинасы). Одан басқа, ішкі порттар (inports) және қашықтағы порттар (outports) жиынтығы оның оаға өзара әрекетін анықтайды.

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

● Outports/imports жұптары канадар деп аталатын хабарлар кезегімен байланысқан. Каналдар құрылуы және жойылуы мүмкін және каналдарға (порттарға) нұсқағыштар хабарға кіруі мүмкін, садған байланысты қамтамасыз ету динамикалық өзгеруі мүмкін.

● Есепер физикалық процессорларға әртүрлі әдіспен бейнеленуі мүмкін; қолданылатын бейнелеу программаның семантикасын қозғамайды. Дербес жағдайларда есептердің көптігі бірпроцессорлы компьютерлерге де жарамды.

Ары қарай, программалаудың негізгі параллель модельдерін қарастырамыз.

0. 
   Программалаудың негізгі параллель модельдері
   

Параллель программалаудың әр түрлі модельдері бар. Олар есептердің өзара әрекеттесу механизмдерімен есептерді талдап тексеру дәрежесімен, орналасуын қолдаумен, әржақтылық пен модельділігімен ерекшеленеді:

● Хабар беру.

● Деректер параллелизмі.

● Жалпықатынау жадысы.

Келесі лекцяларда оларға толығырақ тоқталамыз. Мұнда тек олардың әрбіреуінің негізгі принциптеріне тоқталамыз.

Хабар беру

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

Деректер параллелизмі

Деректер параллелизмі үлестірілген есептеулерді қолданады. Олар деректер құрылымының элементтер жиынына қолданылатын бір ғана амалдан және бір қосымшадан шыққан. Деректердің әрбір элементіне қолданыатын әрбір амалды тәуелсіз есеп деп қарастыруға болады.

Жалпықатынау жадысы

Жалпыанықтау жадысында модельді программалағанда есептер жалпы адрестік кеңістікті бірге қолданады, олар оны асинхронды оқиды және жазады. Сонымен қатар, жалпықатынау жадысына қатынауды басқару үшін әртүрлі механизмдер қолданылуы мүмкін.