compare-exchange_max(id-1);

End for

End ODD-EVEN_PAR

Әрбір фазада орындалатын қадамдарға Q(1) уақыт кетеді. Барлығы n фаза болса, параллельді алгоритмнің орындалуына Q(n) уақыт кетеді екен.

Параллельді әдіске қысқаша сипаттама

p – процессорлар саны, n – сұрыпталатын тізбектің ұзындығы, мұндағы p<n. Бастапқыда, әрбір процессор үшін n/p элементтен тұратын блок тағайындалады, ол бұл элементтерден іштей Q((n/p)*log(n/p)) уақытта сұрыптап шығады. Мұнан кейін процессорлар р фазыдан өтіп шығады (p/2 тақ және p/2 жұп), яғни «салыстыру-бөлу» (compare-split) операциясын орындайды. Сақинадағы процессорлар бір-біріне элементтерін алмастырады. Нәтижесніде әрбір процессорда өз элементтері және көрші процессордың элементтері сұрыпталады да, қайта бөлінеді: сол жақтағы көрші процессор элементтердің бірінші жартысын (кіші элементтерді), оң жақтағы – екінші жартысын (үлкен элементтерді) бөліп алады. Осы фазалар өткен соң тізбек сұрыпталады. Әрбір фаза кезінде екі блокты біріктіру үшін Q(n/p) салыстыру орындалады және Q(n/p) уақыт жұмсалады.

12-13- дәріс

Тақырыбы: Параллель программалау. Ағындар және мәліметтерді өңдеу. Параллель программалау тілдері: HPF және C++ тілінің кеңеймелері, Fortran 90. PVM, MPI, OpenMP қолданып, үлестірілген мәліметтерге енуді құру.

Жоспары:

1. PVM – параллель виртуал машинасы;

2. MPI - хабарламаларды беру интерфейсі;

3. Тез әсер ететін Fortran (HPF).

1. Автопараллелизациялау циклдің өзімен шектеледі, қайта реттелген цикл болуы мүмкін, бұл кезде мәліметтерден тәуелділік мәселесі туындауы мүмкін, соның ішінде ішкі программаға сұраныстардан. Параллель программалау кезінде тізбекті архитектураны қоса, платформааралық мобильділікті қостайтын коментарий ретіндегі компилятор дерективалары қолданылады. Сонымен қатар, кітапханалар, қажет тізбектелген тілдер кеңеймесі: PVM, MPI қолданылады. Хабарламаларды беру моделіне жататын PVM – нің (Parallel Virtual Machine) қарастырайық.

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

PVM – нің қызмет атқаруы онда орындалып жатқан есептер арасындағы ақпаратпен алмасу мүмкіндігіне сүйенеді.

PVM – ді қолданудың негізгі мақсаты – есептеу жылдамдығын олардың параллель орындалуы есебінен арттыру.

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

2. МРІ – хабарламаларды беру интерфейсі.

МРІ (Message Passing Interface) параллель программалаудың ең ерте шыққан құралы болып есептеледі. МРІ кітапханасын қолдaну кезінде үлестірілген программалар процесстері С және Fortran тізбектелген тілдерінде жазылады. Процесстердің өзара байланысы мен олардың синхронизациясы МРІ кітапханасының процедураларын шақыру көмегімен беріледі.

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

МРІ кітапханасын қолданатын программа SPMD стилінен тұрады (Флинн таксономиясын қараңыз). Мүнда әрбір процесс бір программаның көшірмелерін орындайды. Программаның әрбір экземпляры өзіндік экземплярды анықтай алады. Демек, әртүрлі әрекеттер жасай алады.

3. Тез әсер ететін Fortran (HPF).

Тез әсер ететін Фортран (High Perfomance Fortran) – бұл Фортранға негізделген тілдер тобының ең жаңа мүшесі. HPF-тің ең алғашқы нұсқасы 1992 жылы жасалды. Екінші нұсқасы 1997 жылдың басында жарияланды. Бірнеше компиляторлары қазіргі кезде де бар, ал HPF – программалар тез әрекет ете алатын машиналардың қазіргі түрлерінде де орындала алады.

HPF - бұл мәліметтер бойынша параллель тіл. Ол массивтер және олардың бөліктерінің бірнеше амалдарын қолдайтын Фортран 90 тілінің кеңеймесі болып табылады. HPF проектісіне, мәліметтер бойынша параллель Фортранның ерте диалектісі Фортран 90 тілі әсер еттті.

HPF – тің негізгі компоненттері: массивтерді меншіктеудің мәліметтерінің параллельділігі, мәліметтерді үлестіруді басқарудың компиляторы және параллель циклдарды синхронизациялау және жазу операторлары.

14- дәріс

Тақырыбы: Ғылыми есептерді шешудің параллель алгоритмдерінің қосымшалары.

Жоспары:

1. N – дененің гравитациялық есебі

2. N – дененің гравитациялық есебінің тізбектелген коды

1. N – дененің гравитациялық есебі

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

N – денелердің гравитациялық есебі. Бұл берілген есептің мақсаты- Ньютон физикасы заңына бағынатын басқа денелердің гравитациялық күшінен тәуелді кеңістіктегі денелердің қозғалысы мен позициясын табу. Массалары m_a және m_bболатын денелер арасындағы гравитациялық күш сәйкесінше келесі формуламен берілген:

F=(G m_a m_b) / r².

мұндағы G – гравитациялық тұрақты, r-денелер арасындағы ара- қашықтық. Көріп отырғанымыздай, дене жұптары арасындағы күш пропорционал. 1/ r².

Ньютонның екінші заңы бойынша

F=ma

мұндағы m – дене массасы, F – оған әсер ететін күш, ал а- үдеу нәтижесі. Нақты сандық сипаттамасын беру үшін дифференциалдық теңдеуді қолданған жөн:

F=mdv/dt

және

v=dx/dt.

мұндағы v – жылдамдық.

Үшөлшемді кеңістік.

Дене үшөлшемді кеңістікте болғандықтан, барлық вектор- мәндер үш бағытта x,y және z есептелуі керек. (x,y, z) координаталы үшөлшемді кеңістікте (x_а, y_а, z_а) және (x_b,y_b, z_b) болғандағы денелер арасындағы ара –қашықтық келесі формуламен берілген:

Күш осы үш бағытта есептеледі:

F_x=((G m_a m_b) / r²)((x_b-x_a) /r),

F_x=((G m_a m_b) / r²)((y_b-y_a) /r),

F_x=((G m_a m_b) / r²)((z_b-z_a) /r).

2. Тізбектелген коды:

N- денелер гравитациясының барлық есептеулері келесі алгоритммен сипатталуы мүмкін

For (t=0; t<tmax; t++)

For (i=0; i<N; i++)

{

F= Force_routine(i);

V[i]=v[i]+F*dt;

}

For (i=0; i<nmax; i++)

{

X[i]=x[i];

V[i]=v[i];

}

Параллель коды

Алгоритмнің тізбектелген кодын параллельдеу үшін әрбір процессорге арналған денелер тобын қолдануы мүмкін. Алгоритм шамамен процессорлардың О(N²) әрекетін алады.

Есептеу уақыты келесі бақылауды қолданғандықтан аяаюы мүмкін: N-дене кластері кластер массасының ортасында орналасқан толық массалы жеке қашықтықтағыдай жуықталуы мүмкін.

Барнс және Нат алгоритмі

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

Екі өлшемді есеп үшін, әрбір рекурсивті бөлім төрт ішкі облыстан тұрады да, шаршыағаш құрады.

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

15-дәріс.

Тақырыбы: Кескіндерді өңдеу. Төменгі, ортаңғы және жоғарғы деңгейлерде кескіндерді өңдеу түрлері. Фурье түрлендіруі және Фурье алгортимдері

Жоспары:

1. Кескіндерді өңдеудің төменгң деңгейі

2. Кескіндерді өңдеудің Фурье түрлендіруі

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

Біз сақталған кескін сол жақ жоғары бұрыштан басталтын қарапайым координаталар жүйесін қолданады деп болжаймыз. Кескін пиксельдері екі өлшемді массивте сақталады да, оның элементтерін p[i][j] деп белгілеп аламыз және әрбір пиксельдің интенсивтілігі берілген массивтен табылады.

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

Кей кездері пиксельдер идентификацияланатын тік сызықтар немесе қисықтармен ассоцияцияланады. Идентификацияның ең тиімді тәсілі Hough түрлендіруін қолдану. Hough түрлендіруі пиксель координаталарын сызық теңдеуіне жақын тәуелділік теңдеуін анықтау үшін қолданылады.

Есептерге қойылатын талаптар.

Әректтің басында өңдеудің төменгі деңгейінде параллель өңдеуді қолданудың маңыздылығын айта кеткен жөн. Айталық, кескін 1024×1024 пиксельден тұрады делік, мүндай пиксельдер картасымен және пиксельге 8 битпен сақтау өте өажет.

Ең критикалық фактор – есептеу жылдамдығы. Айталық, әрқайсысы тек бір рет қана өңделеді делік. Онда тек қаңқасының өзіне ғана 2¹⁰ операциялар қажет. Қазіргі кезде барлық компьютерлер мүндай әрекет жасай алмайды. Нақты уақыт режимінде қосымшалар үшін есептеу шамамен секундына 60-85 каркас болуы керек. Чиптерді сигналды өңдейтін арнайы аппараттық қамсыздандыру ойлап табылды. Бірақ мұндай жүйелер параллель компьютерлер сияқты икемді емес.

Теңдеуі

Берілген өңдеудің бір деңгейінде қандай да порогты пиксельдер мәні сақталады, ал оден төмен басқалары 0 мәнін қабылдайды. Мысалыға, х мәнді пиксель берілсін, онда пиксельге орындалатын амал:

If (x< threshold) x=0; else x=1;

Контрастпен жұмыс

Берілген жағдайда сұр түстің мәндері деңгейінің диапазоны кескіннің кейбір детальдары көрнсін деп кеңейеді.

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

Сұр түс деңгейін азайту.

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

Параллель орындалуы.

Айталық бір процессор бір пиксельге тіркелген делік. Тура параллель орындалу әрбір процессорден бір уақытта орындалып жатқан әрбір процессорден 9 қадам орындауды талап етер еді. Мұнда барлық хабарлау тек оқу болғандықтан мәліметтер ену қарама – қайшылығы болмайды. Нүкте мәндерін орталандырудың параллель нұсқасы төрт қадамнан тұрады:

Қадам1. Әрбір процессор өзінің сол жағындағы пиксельдер санын алып, мәндерді өзі сақатап жатқан пиксельдер санына қосады.

Қадам 2. Әрбір процессор өзінің оң жағындағы пиксельдер мәнін алады да, жиналып жатқан сомаға қосады.

Қадам 3. Әрбір процессор төменнен жиналған мәндер жиынын екінші қадамдағыдан алып тастап, осы мәнді өзінің жиналған мәндеріне қосады. Ол сонымен қатар, келесі қадам үшін жиналған соманың ағымдағы мәнін сақтап қалу керек.

Қадам 4. Әрбір процессор үстінен жиналған мәндер жиынын екінші қадамдағыдан алып тастап, осы мәнді өзінің жиналған мәндеріне қосады.

Және, ақырында, әрбір процессор жиналған мәндерін ортақ мәнді табу үшін 9-ға бөледі. Сонда әәрбір процессорда төрт қосу байланысы және бір бөлу болады.

2. Кескіндерді өңдеудің Фурье түрлендіруі.

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

H(j,k)=G(j,k)xF(j,k)

мұндағы F(j,k) – бұл f(j,k) Фурье функциясының түрлендірілуі, ал G(j,k) – (g(j,k) Фурье функциясының түрлендірілуі. (j,k – х пикселінің координаталары ).

Фурьенің дискретті түрлендірілу функциясы:

Х_к=1/N∑х_je^-2^π^(jk/n)

мұндағы х_i N пиксельдер мәні, i- комплестік сан.

және Фурьенің кері түрлендіруі

х_к=1/N∑Х_je^-2^π^(jk/n).

Практикада көбіне формуланы 1/N көпмүшесіз қолданады.

Сондықтан, әрі қарай біз бұл көпмшені түсіріп тастаймыз.

w=e^-2^π^i/N

деп белгілейік.

Сонда формула мына түрде болады:

Х_к=∑х_jw^jk)

болады.

Берілген формуланы жүзеге асырудың тізбектелген коды келесі түрде болады:

For (k=0; k<N; k++)

{ X[k]=0

For (j+0; j<N; j++)

X[k]=X[k]+a*X[j];

a=a*pow(w,k);

}