Оқулық Қазақстан Республикасы Білім және ғылым министрлігі бекіткен Алматы, 2011
жүктеу/скачать 2,81 Mb. Pdf көрінісі
|
duisembiev-parallel-esep
|
(2.12) Тағы да операцияны тиімсіз қарапайым қайта нӛмірлеу. Алгоритм графын тұрғызу үшін тік бұрышты тор қарастырамыз және оның түйіндерінің (тораптары) координаталары i, к бүтінсанды деп алайық. Тордың барлық түйіндеріне 1 ≤ i ≤ n, 1 ≤ к ≤ m үшін граф тӛбелерін орналастырамыз және оларды (2.12) операцияларына сәйкес келеді деп санаймыз. Кіріс деректерімен және кейбір аргументтердің нӛлдік мәндерімен жабдықтайтын тӛбелерді кӛрсетпейміз. (2.11) ӛрнегін талдай келе, координатасы i, k болатын тӛбеге координаталары i - 1, k және i, k - 1 болатын тӛбелер сәйкес келетін операциялардың орындалу нәтижелері берілетініне кӛз жеткізу қиын емес. Координаталары i, k болатын операцияны іске асыруға қажетті қалған барлық деректер кіріс деректері болады және тек осы операцияны жүргізу үшін ғана 132 керек. Бұл алгоритм графында (2.5) алгоритміндегі сияқты кіріс деректерін кӛптеп жіберу жоқ. n = 5, m = 9 болған жағдайдағы алгоритм графы 40-шы суретте кӛрсетілген. Одан алгоритм графы ӛте жақсы параллельденетінін кӛреміз. Максималды параллель форманың ярустары пунктирлі сызықтармен белгіленген. Кіріс деректерінің енгізілуін ескермеген кездегі алгоритмнің биіктігі m+n+1, алгоритмнің ені min(m, n). 41-суретте осы графтың тӛбелері пунктирлі сызықтармен біріктірілген. Осындай әрбір топ (бӛлік) 39-шы суретте келтірілген графтың бір тӛбесіне сәйкес. Олар жалпыланған паралллель форманың ярустары болып табылады. Осы суреттерден жақсы параллельденетін алгоритмнің ӛзі операцияларды сәтсіз үлкейткенде қалай параллельденбеуі мүмкін екені кӛрініп тұр. 40 сурет. Блокты-екідиагоналды жүйеге арналған граф 41 сурет. Жалпыланған пралллель форманың ярустары Мысал 3. Бірӛлшемді жылу ӛткізгіштік теңдеуі үшін шектік есебін шешу жолын қарастырайық. Бізден u (у, z) шешімін табу талап етілсін, мұндағы ). ( ) 1 , ( ), ( ) 0 , ( ), ( ) , 0 ( , 0 , 0 , 1 0 2 2 y u y u y u y u z z u T y z z u y u жүктеу/скачать 2,81 Mb. Достарыңызбен бөлісу:
|