Шексіз параллелділік концепциясы

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

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

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

Параллель есептеу жүйелерін құру, параллель алгоритмдерді тұрғызудың математикалық концепцияларын құрастыруды талап етті, яғни осы сияқты жүйелерде іске асырылуға бейімделген алгоритмдерді. Бұл концепциялар өткен ғасырдың 50-ші жылдарының аяғы және 60-шы жылдарының басында дами бастады. Ол уақытта параллель есептеу жүйелерінің құрылымы және оның даму жолдары, бағыттары бойынша мәліметтер аз болатын (тек осындай жүйелерде көптеген құрылғылар бір мезгілде жұмыс істей алады дегені болмаса). Осыған орай элементтік базаның қарқындап дамуы, жақын арада бұл құрылғылардың саны тез өсетінінен хабардар етті. Бұл концепция - «шексіз параллельділік концепциялары» деген атқа ие болды. Бұның негізінде айқын немесе айқын емес болжам жатыр десе болады, яғни алгоритм ешқандай шектеу қоймайтын параллель есептеу жүйесінде іске асырылады. Мұнда барлығы әмбебап синхронды режимде жұмыс істейтін және ортақ жадылы көптеген процессорлар болуы мүмкін және ақпаратты кезкелген түрде жіберу еш кедергісіз және дер кезінде орындалады деп есептелді. Алдыңғы параграфтағы терминдермен айтатын болсақ, бұл дегеніміз шексіз параллелділік концепциясының негізгі мақсаты - биіктігі минимальды болатын алгоритмдерді тұрғызу. Себебі, осындай есептеу моделінде алгоритмдердің іске асырылу уақытын биіктік анықтайды.

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

Бір есепті шешу үшін әртүрлі параллель күрделілігі болатын алгоритмдерді қолдануға болады. Олардың ішінде биіктігі ең кіші алгоритмдер де болуы мүмкін. Биіктігі төмен алгоритмдерді құрастыруда үлкен роль атқаратын идея көрініп тұратын а₁, а₂,..., a_n, сандарының көбейтіндісін есептеу мысалын қарастырып көрейік.

n = 8 болсын. Тізбекті көбейту процесін іске асыратын дәстүрлі схема келесі түрде болады:

Деректер а₁ а₂ а₃ а₄ a₅ а₆ а₇ a₈

1-ші ярус а₁ а₂

2-ші ярус (a₁ a₂)a₃

3-ші ярус (а₁ а₂ а₃) а₄

4-ші ярус (а₁ а₂ а₃ а₄) a₅

5-ші ярус (а₁ а₂ а₃ а₄ а₅) а₆

6-ші ярус (а₁ а₂ а₃ а₄ a₅ а₆) а₇

7-ші ярус (а₁ а₂ а₃ а₄ a₅ а₆ а₇) a₈

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

Деректер а₁ а₂ а₃ а₄ a₅ а₆ а₇ a₈

1-ші ярус а₁а₂ а₃а₄ a₅а₆ а₇a₈

2-ші ярус (a₁a₂)(a₃а₄) (a₅а₆)(а₇a₈)

3-ші ярус (a₁a₂a₃а₄) (a₅а₆а₇a₈)

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

Соңғы схема п – нің кез-келген мәні үшін жалғасын табады. Оны іске асыру үшін әрбір яруста, алдыңғы ярустан алынған қиылыспайтын сандар жұптары көбейтінділерінің максималды мүмкін санын алу қажет. Жалпы жағдайда параллель форманың биіктігі [log₂ n ] тең. Бұл параллельдік форма п/2 процессорларда іске асырылады, бірақ бұнда процессорлардың жүктелінуі ярустан ярусқа көшкен сайын азаяды. Жасалған схема бойынша әрбір яруста сандарды тұрғызу процесі екіеселену процесі деп аталады. Бұл екіеселену процесінің көмегімен, сандарды көбейту операциясын көпқайтара қолдану үшін ғана емес, сонымен қатар кез келген ассоциативті операцияларды орындау үшін де (мысалы, сандарды қосу, матрицаларды көбейту және т.б.) логарифмдік биіктігімен алгоритмдерді құрастыруға болады. Назар аударатын болсақ, операцияларды тізбектей қолдану алгоритмі және екіеселену алгоритмі - бұлар негізінде әртүрлі алгоритмдер болып табылады. Бірақ әртүрлі алгоритм болғанымен өздерінің іске асуы үшін бірдей операция санының орындалуын талап етеді. Оларға тек қана әртүрлі процессорлар саны емес, сонымен қатар әртүрлі коммуникациялық желі де қажет. Сонымен қатар бұл алгоритмдерге дөңгелектеу қателіктерінің әсері әр түрлі беріледі және бұл алгоритмдерге бағдарламалар әртүрде жазылады. Жалпы жағдайда, оларда алгоритм графынан бастап бәрі әртүрлі болып келеді. 36-суретте n= 8 болғандағы екі граф келтірілген, жоғарғысы операцияны тізбектей қолдану графы, төменгісі екіеселену қағидасы үшін граф. Бастапқа түйіндер деректердің кірісін көрсетеді.

36 сурет. Тізбектелген және екіеселенген графтар.

Қарастырылған мысал әдістемелік жағынан өте маңызды бір қорытынды шығаруға мүмкіндік береді.

Дата добавления: 2015-10-29