«параллельді есептеулер» ПӘнінің ОҚУ-Әдістемелік кешені

Семей

1. Кіріспе. Параллель программалаудың дамуы.

2. Параллель компьютерге сұраныс

3. Параллельді есептеулер туралы негізгі түсініктер.

Жоғарғы өндіруші техникалар қазірде мынадай: Векторлы-конвейерлі компьютерлер, үлестірімділі-жадылы массивті-параллельді компьютерлер, ортақ жадылы параллель компьютерлер, кластер архитектуралы компьютерлер бағыттарда дамуда. Олар деректерді параллель өңдеу және параллель алгоритмдерді өңдеуді қолдануға негізделеді. Арнаулы программалы жасақпен жұмыс жасай білу үшін және параллель алгоритмін құрып және программалаудың параллельділік тәсілін меңгеру үшін сәйкес білім мен біліктілік қажет.

Бұл пәннің мақсаты – параллельді есептеудің негізін қалыптастыру, параллельді алгоритмдерді талдау. Пәнде үш мәселе қарастырылады: аппараттық жабдықталуы, программалау, алгоритмдер.
2.Параллель компьютерлерге сұраныс және параллель программалаудың даму кезеңдері

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

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

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

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

Параллельді компьютерлер мен параллельді есептеулер қолданылатын облыстарға тоқталсақ:

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

- бизнесте, коммерциялық салада: видеоконференциялар, параллель мәліметтер қоры, банктік транзакция, т.б.

- техникада: медицина саласында, автоматты түрде диагноз қою, жер сілкінуді болжау, айналадағы ортаның ластануын анализдеу, дәрі-дәрмек препараттарын жасау, т.б.

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

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

- конвейерлі өңдеу (бірнеше команданың әртүрлі стадиялары бір мезгілде орындалады);

- функционалдық модулдер жиынын кірістіру (бірнеше көбейткіштер, сумматорлар, және т.б. жеке командалар ағынымен басқарылады),

- жеке процессоры, жадысы және логикалы өзара байланысты(желімен) «компьютерлер жиынының бірігуі».

Pentium III компьютерін 70 жылдардағы компьютерлермен салыстырғанда суперкомпьютер болып есептелетін еді, қазір ол атау мұндай компьютерлерге сай емес. Суперкомпьютерлердің өнімділігі жоғары және жедел жады мен дискілік жады көлемі үлкен болады. Қазірде дүние жүзінде 500 ең қуатты компьютерлердің арасында 1-ші орын алып отырған компьютер – ASCI WHITE. Оның архитектурасы – 8192 процессорлы, жедел жадысы 4 терабайт, өнімділігі – секундына 12 триллион операция жасайды.

Әрине, бұл компьютерлердің құны да арзан емес, бірнеше миллион доллар тұрады. Осыншама қымбат компьютерлерді пайдаланатындай бізде қандай күрделі есептер бар? Ол есептер соншама маңызды ма? Осы сұрақтарға жауап беру үшін мынадай бір мысал қарастырайық.

3. Мұнай өндіретін процесті қарастырайық. Жер асты резервуарлары қазылған скважиналардан тұрады, біреуінен мұнай сорылса, екіншісінен су төменге айдалады. Бізге мынадай есеп қойылады: осы резервуардан алынатын мұнайдың запасын анықтау керек немесе бізге қаншама қосымша скважина керек, осыны есептеу үшін біз схеманы қарапайым елестетейік. Резервуарды куб деп қарастырайық. Куб көлемі - 100х100х100 нүктелерден тұрады. Әрбір нүктеде орындалатын функциялар – жылдамдық, қысым, температура, компоненттің концентрациясы (су, газ, мұнай, т.б.). Барлығы 5-20 функция (орташа-10). Бұл функциялар сызықты емес. Сондықтан оларды есептеу үшін 200-1000 операция орындалу керек (орташа -500).

Жүріп жатқан процестер стандартты емес, сондықтан қадамдар саны 100-1000 (орташа-500). Сонда куб ішінде орындалатын арифметикалық операциялар саны:

10⁶ (нүктелер)*10 (функция)*500 (операция)*500 (қадам)=2.5*10¹², яғни 2500 млрд. арифметикалық операция. Әрине, мұндай операцияларды қарапайым компьютерлермен орындасақ қаншама уақыт кетер еді.

1. 
   Параллель компьютерлер дегеніміз не?
   
2. 
   Параллель есептеулер қандай салларда қолданылады.
   
3. 
   Суперкомпьютерлер дегеніміз не?
   
4. 
   Суперкомпьютерлердің қандай түрлері бар?
   

1. 
   Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002
   
2. 
   Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003
   
3. 
   Акжалова А.Ж. Параллельные вычисления (учебное пособие). – Алматы, 2004
   
4. 
   Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002
   

таныстыру.

1. 
   Параллельділік
   
2. 
   Программалау модельдері
   
3. 
   Параллель компьютерлердің аппараттық жабдықталуы
   

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

Жалғыз процессорлы компьютерлер архитектурасын дамыту үшін мынадай әр түрлі тәсілдерді қолдануға болады:

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

• 
  тапсырма деңгейінің параллельдігі;
  
• 
  программа деңгейінің параллельдігі;
  
• 
  командалар деңгейінің параллельдігі;
  
• 
  арифметикалық және биттік туралау параллельдігі;
  

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

2. 
   Программа деңгейінің параллельдігі - бір программа оны құраушы бөліктеріне бөлініп орындалатын процесс. Параллельділіктің бұл типі процессордың жиынымен іске асады. Бұл көп процессорлары машина барлық берілген есептеулерді бір мезгілде орындай алады.
   
3. 
   Командалар деңгейінің параллельдігі - бұл типті іске асыратын негізгі тәсіл – конвейерлер. Бұл жағдайда не жеке командалар қалқаланады, не берілген команда бағыныңқы операцияларға жіктеледі. Олар да өз кезегінде қалқалану жағдайына келтіріледі.
   
4. 
   Арифметикалық және биттік туралау параллельдігі - параллельдігінің ең төменгі деңгейі. Бұл деңгей - орталық процессордағы арифметика-логикалық құрылғыға жатқызылады.
   

2. Есептелу тиімділігі.

3. Есептелу құны.

4. Есептелу көлемі.

Есептелудің тиімділігі мына шамамен анықталады:

Есептелу құнының пайдалы бағасы – параллельді есептелетін уақыттың процессорлар санына көбейтіндісін айтамыз.



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

Мынадай есеп қойылсын: Қарама-қарсы бұрыштарының координаттары берілген тіктөртбұрыштың ауданын есептеудің алгоритмін граф түрінде көрсетейік.


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

n- қосындылардың саны.

Бұл есепті шешудің параллельді әдісін бастамас бұрын алдымен қарапайым жағдайды қарастырамыз, яғни

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

S=0,

S=S+x₁,...

Мұндағы итерациялардың саны: k=log₂n,

Ал, қосу операцияларының саны K_сонғы=n/2+n/4+...+1=n–1

1. Параллельді программалық жабдықтау.

2. Параллельді компьютерлердің типі.
Енді соларды қарастырайық.
3. Параллельді программалық жабдықтау үшін мынадай талаптар орындалу керек:

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

Әрбір компьютерлердің өзі процессоры, жергілікті жадысы болады, бірақ басқа процессормен байланыс жасай алмайды. Жалпы жады барлық компьютерге үлестірілген. Әрбір компьютердің өзіндік адрестік кеңістігі бар. Процессорлар арасындағы өзара байланыс бір-бірінен хабар алып не жіберулмен жүзеге асады. Хабарда басқа процессорың есептеулеріне керек болатын мәліметтер болуы мүмкін.

1. 
   Параллельділік дегеніміз не?
   
2. 
   Программалаудың қандай модельдері бар?
   
3. 
   Тізбектелген модель дегеніміз не?
   
1. 
   Параллель модель дегеніміз не?
   

1. 
   Воеводин Вл. Параллельные вычисления. Санкт-Петербург, 2002
   
2. 
   Грегори Р. Эндрюс. Основы многопоточного, параллельного и распределенного программирования. Пер. с. англ. –М.: Издательский дом «Вильямс», 2003. – 512с.
   
3. 
   Акжалова А.Ж. Параллельные вычисления (учебное пособие). – Алматы, 2004
   
4. 
   Немнюгин С.А., Стесик О.Л. Параллельное программирование для высокопроизводительных многопроцессорных систем – СПб., 2002
   

1. 
   Параллель компьютерлер түрлері.
   
2. 
   Хабарламаларды беру мультикомпьютері немесе үлестірілімді жадылы мультикомпьютер
   
3. 
   Флинн таксономиясы
   

Жады келесі ерекшеліктермен шектеледі:

1. 
   Өлшемімен – қолданушыларға көп жағдайда жады жетіспейді,
   

2. 
   Жадының өткізу қабілеттілігі (latency) және иерархиясымен.
   
3. 
   Жадының өткізу қабілеттілігі (bandwidth) – жадыға жазылатын немесе жадыдан оқылатын мәліметтер көлемі.
   
4. 
   Жадыны қорғау – көптеген архитектуралар программалық қамсыздандыруды модификациядан не жүйелік жадыдан немесе басқа программаларды қолданғандағы жадыдан қорғауды қосады.
   

Физикалық адрес жадыдағы нақты орынға ену үшін қолданылады. Виртуал және физикалық адрес арасында TLB (Translation Lookaside Buffer) адрестерді түрлендіру көмегімен автоматты түрде ауысу жүргізіледі.

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

Жұмыс станцияларының жиынынан тұратын желілік жүйе – жалпы жұмыс станциясының желісі (NOW – network of workstations) немесе жұмыс станциясының кластері (COW – cluster of workstation) д.а. Барлық жұмыс станциялары бір-бірімен байланысқан бір немесе бірнеше қосымшаларды орындайды. Үлестірілімді жадылы қымбат емес мультипроцессорды құрудың ең кең таралған әдісі – ол Beowulf машинасын құрастыру. Ол базалық аппараттық қамсыздандырудан және Pentium процессорының чипы, желілік карта, дисктер және Linux операциялық желісі сияқты ақысыз программалардан тұрады.
3. Флинн таксономиясы.

1. SIMD SISD MIMD MISD құрылымдары.

SIMD құрылымы.



МІМD номері көптеген өзара байланысты процестерден тұрады, олардың әр қайсысының жеке басқару блогы бар.

Процесстердің өздерінің жеке командалары мен жеке мәліметтерін етеді. Әр түрлі процестердің орындаған жұмысы (есебі) әртүрлі уақытта басталады, әртүрлі уақытта бітуі мүмкін. Яғни, олар «аяқтарын бірге баспайды» асихронды орындайды.

МІМD құрылымды компьютерде жолды не үлестірілген, не барлығына жететін (обще доступный) болуы мүмкін.

Мысалы:

Cray X - MP;

IBM 370/168 MP, IPSC

Мұнда да процесстің жиыны жұмыс жолы, бірақ барлығы 1 – ғана мәліметтер ағынына әсер етеді.

Мұндай құрылымды 1 космпьютер белгілі. Ол, C. mmp, Carnegie – Mellon университетінде жасалған.

Бұл компьютер басқа режимде де (SIMP, MISD, MIMD)жұмыс жасай алады. Параметрлерді программалауды тиімділігін бағалау.

Ол мына функцияларға байланысты:

• 
  Орындалу уақытына
  
• 
  Жады конфигурациясына және орындалуға кететін шығынға
  
• 
  Қызмет көрсету және ақысына, тағы басқалары;
  

ЭЕМ өнімділігін қалай арттыруға болады?

1949 жылы шыққан компьютерлердің тактілік уақыты 2 микросекунд (2*10^-6 сек), яғни орташа 100 арифметикалық операцияны 1 секундта орындайды.

Қазіргі заманғы компьютерлердің тактілік уақыты 1,8 наносекунд (1,8*10^-9 сек), яғни 1 секундта 77 млрд.арифметикалық операция орындалады. Жарты ғасырда компьютер өнімділігі 700 млн. есе өскен, яғни 2 микросекундтан 1,8 наносекундқа дейін өскен. Бұл компьютер архитектурасы жаңаша құрылған деген сөз. Мәліметтерді параллель өңдеуді бір уақытта бірнеше әрекет жасалатындығымен түсіндіруге болады. Бұны былайша түсіндіруге болады. 1 құрылғы 1 операцияны 1 бірлік уақытта орындайды, осы құрылғы 100 операцияны 100 бірлік уақытта орындайды. Егер осындай 5 құрылғы бір мезгілде жұмыс жасаса, онда кететін уақыт 200 бірлікке тең болар еді, яғни N құрылғы 1/N уақыт бірлігінде жұмысты орындап шығады. Тағы бір мысал, 1 солдат жерді 10 сағатта қазса, рота (50 солдат) бірдей күшпен, бірдей уақытта 12 минутта қазып шығады екен. Міне, параллельділік принципі осыдан шыққан!