Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011
жүктеу/скачать 2,81 Mb. Pdf көрінісі
|
duisembiev-parallel-esep
- Бұл бет үшін навигация:
- Бекітілім 1.2.1
| G= (V, E), мұндағы V - шыңдар жиыны, E - G графының доғаларының
жиыны. Сонымен, алгоритмнің әрбір мазмұнын (сипаттамасын) бағытталған циклсіз мультиграф тудырады. Керісінше де дұрыс. Егер бағытталған циклсіз мультиграф берілсе, онда оны әркез белгілі бір алгоритмнің графы ретінде қарастыруға болады. Ол үшін әрбір шыңға, сәйкесінше, қанша доға кірсе сонша аргументі бар кезкелген бірмәнді операцияны қою керек. Сол себепті алгоритмдер және қарастырылып жатқан графтардың арасында белгілі бір ӛзара сәйкестік бар. Бекітілім 1.2.1 n шыңы бар бағытталған циклсіз граф берілді делік. Графтың барлық шыңдарын 1,2,...., s сияқты индекстердің бірімен белгілеуге болатын s < n саны бар болады, егер доға i индексі бар шыңнан шығып j индексі бар шыңға келсе, онда i < j Графтан ӛзіне дейін болмаған кезкелген шыңдар санын алайық та, оларды 1 индексімен белгілейік. Одан белгіленген шыңдар мен оған қатыстырылған иіндерді ӛшіреміз. Қалған граф та циклсіз болады. Ондағы ӛзіне дейін болмаған шыңдар санын алып, оларды 2 индексімен белгілейміз. Осы үрдісті жалғастыра отырып, ең соңында бүкіл графты қамтимыз. Әрбір қадам сайын біреуден кем емес шың белгіленіп отырғандықтан, түрлі индекстер саны граф шыңдарының санынан аспайды. Осыдан шығатын қорытынды, бір индекспен белгіленген ешқандай екі шың доғамен байланыспаған. Графтың барлық шыңдарын белгілеуге болатын индекстердің ең кіші саны оның критикалық жолының ұзындығынан 1-ге үлкенірек болады. Сонымен, шыңдардың жалпы санынан аспайтын, бірақ критикалық жол ұзындығынан үлкен болып келетін кезкелген бүтін s саны үшін, осындай барлық s индекстері пайдаланылатын граф шыңдарының осындай белгілеуі болады. 1.2.1 бекітіліміне сай белгіленген граф – графтың қатаң параллельді түрі деп аталады. Егер параллельді түрде қандай да бір шың к индексімен белгіленген болса, онда бұл осы шыңда аяқталатын барлық жолдардың ұзындығы к-дан кіші дегенді білдіреді. Индексі к болатын шыңда аяқталатын жолдардың ұзындықтарының максималды мәні к-1 тең, қатаң параллельді түрі де бар. Бұл берілген параллель түр үшін қолданыстағы индекстер саны графтың критикалық жолының ұзындығынан 1-ге үлкен. Осыған ұқсас параллельді түрлердің ішінде барлық кіру шыңдары мәні 1-ге тең бір индексті топта орналасқаны да болады. Бұл қатаң параллельді түр – канондық деп аталады. Берілген граф үшін оның канондық параллельді түрі 114 жалқы (единственна), яғни біреу ғана болып табылады. Бірдей индекстері бар шыңдар тобы – параллельді түрдің ярусы деп, ал топтағы шыңдар саны – ярустың ені деп аталады. Параллельді түрдегі ярустар саны – оның биіктігі деп, ал ярустардың максималды ені – оның ені деп аталады. Минималды биіктіктің параллельді түрі – максималды деп аталады. Мұнда максималды сӛзі – осы параллельді түрде ярустарда белгілі бір мағынада шыңдардың максималды саны бар дегенді білдіреді. Барлық канондық параллельді түрлер максималды болып табылады. Егер i < j теңсіздігін i ≤ j теңсіздігіне ауыстыратын болсақ, 4.1 бекітілімінің мазмұны ӛз күшінде қалатынын байқаймыз. Бірақ салдарлардың ешқайсысы да орындалмайтын болады. Осы тәсілмен белгіленген граф- жалпыланған параллельді түр деп аталады. Осыған сәйкес жалпыланған ярус, жалпыланған ярустың ені және т.б. ұғымдар енгізіледі. Параллельді түрлермен байланысты зерттеулерде жалпыланған параллельді түрлер қатаң параллельді түрлер жиынын тұйықтаушы рӛлін атқарады. Енді алгоритм «кәдімгі» немесе параллельді, синхронды компьютерде жүзеге асырылуда делік. Оңай болу үшін барлық операциялар 1-ге тең бір ғана уақыт мезетінде орындалсын. Барлық ӛзге уақыт ысыраптарын есепке алмай-ақ, қалай аргументтері дайын болған кезден бастап, еш тоқтаусыз операциялар бірден орындала бастайды деп есептейік. Алгоритм уақыттың нӛлдік кезеңінде жүзеге аса бастайды деп пайымдаймыз. Сонда әр операцияға ӛзінің орындалып біткен кезеңіне тең индекс беруге болады. Егер осы индекстерді сәйкес алгоритм графының шыңдарына ауыстырсақ, онда оның қатаң параллельді түрін алатынымыз белгілі. Мұндағы ярус нӛмірі ӛзіне сәйкес операциялардың орындалып бітіп жатқан уақыт кезеңін білдіреді. Бір ярустың барлық операциялары бір-біріне тәуелсіз орындалып жатады, ал бұл операциялар саны ярустың еніне сәйкес келеді. Параллель түрдің биіктігі - алгоритм орындалуының ұзақтығы және т.б. болып табылады. Алгоритмнің түрлі синхронды орындалуы және оның графының түрлі қатаң параллельді түрлерінің арасындағы байланыс ӛте анық кӛрінеді. Дербес жағдайда, егер алгоритм «кәдімгі» компьютерде орындалып жатса, онда бұған барлық ярустарының ені 1-ге тең болатын параллельді түр сәйкес келеді. Бұл жағдайда параллельді түр сызықтық деп аталып, граф сызықты реттелген делінеді. Егер абсцисса ӛсін уақыт ӛсі деп есептеп, ал шыңдарын операциялардың орындалып біткен уақытына сәйкес ордината ӛсіне қойып отырсақ, алгоритм графының параллельді түрлерін қағазға түсіру ӛте ыңғайлы. Егер синхронды немесе асинхронды кез келген нақты немесе гиротетикалық компьютерге арналған тура осы сияқты сызба жүргізілсе, онда осы айтылған пайымдауларда кӛп нәрсе ӛзгерусіз қалатыны анық. Тек параллельді түрдің ярустары ғана мезгіл бойынша ӛзгеріске ұшырайды. Алайда олар қаншалықты ӛзгергенімен, шыңдары мен шыңдарға сәйкес доғаларды абсцисса ӛсіне параллель жылжыту арқылы оларды қашан да операцияларды орындаудың бірлік уақытымен синхронды түріне 115 айналдыруға болады. Бұл үшін операциялар орындалуының тек аяқталған кезеңін ғана емес, сонымен қатар басталған кезеңін де белгілейміз. Параллельді түрдің ярустарын келесі тәсілмен тұрғызамыз. Кіру доғалары жоқ және орындалуының мезгілдік интервалының бос емес қиылысуы бар операцияларына сәйкес келетін шыңдардың максималды санын бірінші ярусқа біріктіреміз. Бұл шыңдар алдын ала бір-бірімен ешқандай доғалармен байланыспаған. Алгоритм графынан бірінші ярус шыңдары мен оларға қатысты доғаларды алып тастаймыз. Графтың қалған бӛлігіне ұқсас келетін шыңдар тобын бӛлеміз де, оны параллель түрдің екінші ярусы деп санайтын боламыз және т.б. Сонымен, әртүрлі компьютерлерде бір ғана алгоритмнің түрлі жолмен орындалуы және алгоритм графының әртүрлі параллельді түрлерінің арасында белгілі бір ӛзара сәйкестік бар екені кӛрінеді. Алгоритм графы және оның параллельді түрлерін біле отырып, алгоритмдегі параллельділік қорының қаншалықты екенін және оны параллельді архитектуралы нақты бір компьютерде қалай жақсы іске асыруға болатынын түсінуге болады. Міне, сол себепті де біз алгоритм графының тұрғызылуына және оның параллельді түрлерін табуға кӛп кӛңіл бӛлудеміз. Әрі қарай, алгоритмнің параллельді формасы, алгоритм ярустары, алгоритмнің параллельді түрінің биіктігі туралы айта отырып, алгоритм графының параллельді түрлеріне қатысты терминологияны алгоритмнің ӛзіне де жиі қолданып отыратын боламыз. Алгоритмнің параллельді түрлерінің минималды биіктігін - алгоритм биіктігі деп атайтын боламыз және т.б. Басқаша айтқанда, бірден алгоритмнің операцияларын-граф шыңдары деп, ал операциялар арасындағы жартылай реттілік қатынастарын – иіндер (доғалар) деп санайтын боламыз. Бұл негізінен ешқандай жаңа білім бермейді, дегенмен «алгоритм графының шыңдарының мынадай жиынтығына сәйкес келетін операциялар жиынтығы» деген сияқты кӛп құрамды ұзақ сӛздер тізбегін алып тастау арқылы шытырман фразалардан құтылуға мүмкіндік береді. Алгоритм графының қарапайым түрін түрлі-түсті суреттер мен сызбаларда қолданған әлдеқайда ыңғайлы. Ал енді, компьютерде алгоритмнің қай параллельді түрі орындалып жатқанына қарамастан, орындалу нәтижесі бәрібір бірдей болатынын кӛрсетейік. жүктеу/скачать 2,81 Mb. Достарыңызбен бөлісу:
|