Amaliy mashg’ulot №1

Amaliy mashg’ulot №1

Mavzu: Parallel xisoblash tizimlari.

Ishdan maqsad: Parallel xisoblash tizimlari, ularning qurilish prinsipi, ishlash tamoyillarini o’rganish.

NAZARIY QISM

Parallel xisoblash— dasturlar o’zaro parallel (bir vaqtda) xarakatlanadigan xisoblash jarayonlarini qayta ishlovchi to’plami sifatida kompyuterli xisoblashni tashkillash usuli xisoblanadi. Bu ibora dasturlashdagi parallellizm muammolari yig’indisi, shuningdek, samarali faoliyat yurituvchi qurilmalarni tadbiq etish xususiyatlarini o’z ichiga qamrab oladi. Parallel xisoblash nazariyasi amaliy algoritmlar nazariyasini yaratilishiga olib keldi.

Parallel xisoblashni tadbiq etishning turli usullari mavjud. Masalan, xar bir xisoblash tizimi operatsin tizim jarayoni ko’rinishida tadbiq etilishi yoki xisoblash jarayonlari operatsion tizimning birgina jarayoninig o’zida bajaruvchilar oqimi to’plamini aks ettirishi mumkin. Parallel dasturlar fizik nuqtai nazardan yagona protsessorda – xar bir xisoblash jarayoni qadamlarini navbatma-navbat ketma-ketlikda bajarilishi yoki belgilangan xar bir xisoblash jarayonini parallel aniqlab, bir yoki bir nechta protsessorlar (yonma-yon joylashgan yoki kompyuter tarmoqlarida taqsimlangan) yordamida amalga oshirilishi mumkin.

Parallel dasturlarni loyixalashdagi asosiy murakkablik shundan iboratki, turli xisoblash tizimlari bilan o’zaro aloqasini, shuningdek, jarayonlar o’rtasida taqsimlanadigan resurslar koordinatsiyasini to’g’ri ketma-ketlikda xarakatlanishini ta’minlash xisoblanadi.

Bir necha amallarni bir vaqtda bajarish g’oyasidan iborat bo’lgan ma’lumotlarni parallel xisoblash ikki xil ko’rinishi mavjud. Bular: Parallel va konveyer. Agar biror qurilma bitta amalni vaqt birligida bajarsa, u holda mingta amalni ming vaqt birligida bajaradi. Agar xuddi shunday bir vaqtda ishlay oladigan va bir–biriga mustaqil beshta qurilma mavjud deb qaralsa, u holda ular yuqoridagi mingta amalni mingta vaqt birligida emas, balki ikki yuzta vaqt birligida bajaradi. Xuddi shunday N ta qurilmadan iborat tizim 1000 ta amalni 1000/N vaqt birligida bajarida. Unga o’xshash holatlarni hayotdan ham keltirish mumkin. Masalan, agar bitta askar polizga 10 soatda ishlov bersa, u xolda 50 askardan iborat rota bir vaqtda ishlab polizga 12 minutda ishlov beradi. Bu parallel amallar printsipi hisoblanadi.

Parallel tizim arxitektura kategoriyalari

Kompyuter sistemalarini to’rtta asosiy kategoriyaga ajratish mumkin. Bu uchun qanday ishlashi haqidagi ko’rsatmani birmuncha almashtiramiz. Markaziy protssessor nuqtai nazaridandastur rasshifrovka qilish va bajarish kerak bo’lgan qoidalar oqimidir. Ma’lumotlarni ham oqim ko’rinishida kiruvchi deb hisoblash mumkin.

Dasturlash modeli – abstrakt kompyuter arxitekturasiga javob beradigan dasturlash usullari majmuasi bo’lib, ma’lum algoritmlar sinfini amalga oshirish uchun mo’ljallangan. Dasturlash modellari kompyuter va uning arxitekturasini mantiqiy tashkillash haqida aniq tasavvurga ega bo’lishi uchun xizmat qiladi.

Arxitekturalarning xar xil turlari mavjud bo’lib ulardan birinchi bo’lib “FLINN taksonomiyasi” xisoblanadi. Arxitekturaning bu turi kompyuterning buyruqlar va ma’lumotlar oqimi bilan ishlash xususiyatlarga asoslanadi. Biz tahlil qiladigan to’rtta kategoriya ma’lumot va qoidalarning bitta oqimga kirish-kirmasligi bilan aniqlanadi. Ushbu arxitektura turlariga qisqacha to’xtalib o’tamiz.

SISD (Single Instruction Single Data) bir oqim buyruq, bir oqim ma’lumotlar.



1.1-rasm SISD arxitekturasi

Bitta oqim buyruq, bitta oqim ma’lumotlar (SISD) modeli o’zida bitta protssesorli klassik modelni ko’rsatadi. Unga eski avlod kompyuterlari bilan bir qatorda ko’pgina zamonaviy kompyuterlar ham misol bo’ladi. Bunday kompyuter protsessori har qanday vaqt momentida faqatgina bitta qoidani bajarishga qodir va faqat bitta ma’lumotlar to’plami bilan ishlay oladi.

SIMD (Single Instruction Multical Data) bir oqim buyruq, bir necha oqim ma’lumotlar.



1.2-rasm SIMD arxitekturasi

Bitta oqim buyruq, bir nechta oqim ma’lumotlar bo’lgan komyuterlarda (SIMD) bir xil operatsiyani turli xil ma’lumotlar bilan ishlovchi bir nechta protssessorlar mavjud. SIMD - mashinalar ba’zan vektorli protsessorlar deb ham ataladi, chunki ular vektorlar ustida amal bajarish uchun juda qulay. Bunda har qaysi protssesorga bitta vector koordinasi beriladi va amal bajarilgandan so’ng natija vektor kelib chiqadi.

MISD (Multical Instruction Single Data) bir necha oqim buyruq, bir oqim ma’lumotlar.



1.3-rasm MISD arxitekturasi

Bir vaqtda faqat bir xil ma’lumotlar ustida amal bajarish avval g’alati tuyulishi mumkin, chunki qndaydir bir sonni kvadratga ko’tarish, ikkiga ko’paytirish, o’nga bo’lish kabi dasturlar kamdan-kam uchraydi. Lekin bu holatga boshqa nuqtai-nazardan qarasak, bunday tipdagi mashinalarda sonning tub yoki murakkabligini tekshirishni takomillashtish mumkinligini ko’ramiz. MISD – mashina orqali bitta operatsiyada tekshirishimiz mumkin. Agar X son murakkab bo’lsa, unda ga to’g’ri kelmaydigan bo’luvchisi bo’lishi kerak.

MIMD (Multical Instruction Multical Data) bir necha oqim buyruq, bir necha oqim ma’lumotlar.



1.4-rasm MIMD arxitekturasi

Bu kategoriya kategoriyalar orasida ancha murakkabidir. MIMD –sistemalar holatida biz o’z qoidasini amalga oshira oladigan bir nechta protsessor bilan ish ko’ramiz. Bundan tashqari, bir nechta bir nechta ma’lumotlar oqimi ham mavjud va har qaysi protsessor o’z ma’lumotlar to’plami bilan ishlay oladi.

Parallel arxitekturalar

Parallel kompyuterlar tizimlari arxitekturasida 2 ta jihat asosiy rol o’ynaydi:

• 
  Protesssorlar va ularning xotiralari o’zaro qanday bog’langanligi;
  
• 
  Protsessorlarning qanday o’zaro ta’sir qilishi.
  

Parallel algoritmlarni muhokama qilganda biz ana shu jihatlar haqida gapiramiz. Negaki u yoki bu yechimlar turli masalalar uchun turli samaradorlikka ega bo’lishi mumkin. Parallel arxitekturada protsessorlarni ulashning bundan boshqa imkoniyatlari ham mavjud. Bularga daraxtsimon tarmoqlar (protsessorlar bironta daraxtni hosil qiladi) va ikki o’lchovli chambaraksimon umumlashtiradigan giperkublarni misol qilish mumkin.

Parallel xisoblash tizimlari

Parallel xisoblash tizimlari quyidagi belgilarga qarab tavsiflanadi:

1. 
   Xisoblash tizimining markaziy qismi va belgilar oqimi turlariga ko’ra;
   
2. 
   Axborotlarni protsessorida usuliga ko’ra;
   
3. 
   Xisoblash tizimlari komponentalarining bir jinsligini yoki bog’lanish darajasiga ko’ra.
   

Xisoblash tizimlarini parallel tashkil qilish birinchi ikkita belgiga qarab aniqlanadi. OKOD bittalab oqimli belgilar bir protsessorli ketma-ket EXM lardan iborat.

MKMD ya’ni ko’plab oqimlari komandalar ko’plab oqimlari belgilanganlar ustida amallar bajaradi. Bunday MBS larni protsessorlar BK lariga ega bo’lib o’zaro assinxron rejimida ishlaydi.

OKMD tipli tizimda umumiy BK mavjudligi barcha protsessorlarda bitta umumiy komanda bajarilishini ta’minlaydi.

Bu xol esa tizimida ixtiyoriy vaqtda fanda bitta dasturda bajarilishini tasdiqlaydi. Tizim BK sining ishdan chiqishi xoli uchun butkul ishdan chiqishga olib keladi. Shu tizimdagi ixtiyoriy protsessorning yoki unga mos axborotlar OX ning ishdan chiqishi xam xisoblash jarayonini to’xtatishga olib keladi. Uni ishga tushirish uchun maxsus qayta translyatsiya turlarini amalga oshirishni talab qiladi.

Parallel ilovalarni ishlab chiqishda dasturchidan quyidagilar talab qilinadi:

1. 
   Translyatorga parallel yoki vektorli optimalliklarni kiritish;
   
2. 
   Parallel xisoblash uchun mo’ljallangan maxsus dasturini tiplari, kutubxona qism dasturlari aniq arxitekturadagi maxsus ishlab chiqilgan kompyuterlar va bu arxitekturalar uchun optimalliklarini qo’llash;
   
3. 
   Parallel kompilyatsiyalar direktivini kiritish kabilar.
   

Parallel sistemalaning muammolaridan biri ma’lumotlarni xotiradan o’qish va xotiraga yozishdir. Masalan, agar ikkita protsessor ma’lumotlarni umumiy xotiraning aynan bitta joyiga yozishga urinsa nima bo’ladi?

Ilgari biz ko’rgan algoritmlarda bu algoritmni amalga oshiradigan mashina ilgaridan berilgan xotira yacheykasi (RAM) ga to’g’ridan- to’g’ri kirish imkoniyatiga ega. Hozir biz qaraydigan algoritmlar bunday mashinalarning parallel varianti (PRAM) ga asoslangan. Bizning PRAM mashinalarning protsessorlari o’zaro chambarchas bog’langan va umumiy xotira blokidan foydalanadi. Har bir protsessorda uncha katta hajmda bo’lmagan ma’lumotlarni saqlash imkoniyatiga ega bo’lgan bir nechta registrlar mavjud, ma’lumotlarning asosiy qismi esa umumiy xotirada saqlanadi.

Parallel protsessorlar

Parallel protsessorlar bilan ishlashda bizni ikki tushuncha qiziqtiradi:

1. 
   Tezlanish koeffitsiyenti
   
2. 
   Qiymati
   

Parallel protsessorlar tezlanish koeffitsiyenti optimal ketma-ket protsessorning qanchalik tez ishlashini ko’rsatadi. Ma’lumki optimal tartiblash algoritmi O (Nlog N) ta operatsiyani talab qiladi. O (N) murakkablikdagi parallel tartiblash algoritmining tezlanish koeffitsiyenti O(log N) ni tashkil qiladi. Protsessorlar orasidagi chambarchas bog’liqlikdan tashqari biz yana ular hammasi xotiradan ma’lumotlarni o’qish, ular ustida operatsiya bajarish va natijani xotiraga yozishdan iborat bo’lgan bir xil siklni amalga oshiradi deb faraz qilamiz. Bu barcha protsessorlar bir vaqtda xotirani o’qishini, bir vaqtda o’qilgan ma’lumot larni qayta ishlashini, bir vaqtda yozuvni ham bajarishini anglatadi.

Bu ishda ikki vazifa – algoritmlarning dastur effektivligiga qanday ta’sir etishi va turli xil algoritmlarning analizini o’rganishdir. Ba’zi bir zamonaviy dasturiy ta’minotlarga e’tibor qilsak, ularning ayrim tuzuvchilari na dasturning ishlash effektivligiga va na xotiraning aql bilan ishlatilishiga e’tibor qilishadi. Ularning fikricha, dastur ko’p joy olsa, foydalanuvchi qo’shimcha xotira sotib olishga majbur bo’ladi yoki yangi tezroq ishlaydigan kompyuter sotib oladi. Lekin kompyuterlarning tezligi cheksiz kattalashmaydi. U simli kabelda elektronlarning harakat tezligi bilan, optik kabellarda yorug’likning tarqalish tezligi bilan va hisoblashda qatnashadigan kompyuterlar orasidagi aloqa kanallarining komutativlik tezligi bilan chegaralanadi. Boshqa cheklovlar kompyuter imkoniyatlari bilan bog’liq emas, balki qo’yilgan masalaning murakkablik darajasiga bog’liq. Shunday masalalar mavjudki, ularni yechish uchun eng tez ishlaydigan algoritmlar qo’llanilganda ham odam umri yetmaydi. Bu masalalar orasida yaqinroq javob olish uchun algoritmlar kerak bo’ladigan, juda zarurlari ham mavjud. Bu kurs ishida biz parallel dasturlashda ishlatiladigan asosiy tushunchalarni keltiramiz. Avvalo, ishni kompyuterning ma’lumotlarni qayta ishlash tushunchasini keltirishdan boshlaymiz. So’ngra kompyuter sistemalarining arxitekturasiga o’tamiz. Oxirda parallel algoritmlarning analizida ishlatiladigan prinsiplarni tahlil qilamiz.

Kompyuter sistemalarining kategoriyalari. Komyuter sistemalarini 4ta asosiy kategoriyaga ajratish mumkin. Bu uchun qanday ishlashi haqidagi ko’rsatmani birmuncha almashtiramiz. Markaziy protssessor nuqtai nazaridan dastur rasshifrovka qilish va bajarish kerak bo’lgan qoidalar oqimidir. Ma’lumotlarni ham oqim ko’rinishida kiruvchi deb hisoblash mumkin. Biz tahlil qiladigan to’rtta kategoriya ma’lumot va qoidalarning bitta oqimga kirish-kirmasligi bilan aniqlanadi. Bitta qoida bitta ma’lumotlar oqimi. Bitta qoida bitta ma’lumotlar oqimi (SISD) modeli o’zida bitta protssesorli klassik modelni ko’rsatadi. Unga eski avlod kompyuterlari bilan bir qatorda ko’pgina zamonaviy kompyuterlar ham misol bo’ladi. Bunday kompyuter protsessori har qanday vaqt momentida faqatgina bitta qoidani bajarishga qodir va faqat bitta ma’lumotlar to’plami bilan ishlay oladi. Bu kabi ketma-ket sistemalarda boshqa kategoriyalardan farqli ravishda hech qanday parallellik yo’q. Bitta qoida bir nechta ma’lumotlar oqimi. Bitta qoida bir nechta ma’lumotlar oqimibo’lgan komyuterlarda (SIMD) bir xil operatsiyani turli xil ma’lumotlar bilan ishlovchi bir nechta protssessorlar mavjud. SIMD - mashinalar ba’zan vektorli protsessorlar deb ham ataladi, chunki ular vektorlar ustida amal bajarish uchun juda qulay. Bunda har qaysi protssesorga bitta vector koordinasi beriladi va amal bajarilgandan so’ng natija vektor kelib chiqadi. Masalan, vektorlarni qo’shish – koordinatalar orqali bajariladigan amal. Vektorlar yig’indisining birinchi koordinatasi – qo’shiluvchi vektorlar birinchi koordinatalarining yig’indisi, ikkinchi koordinata – ikkinchi koordinalar yig’indisi va hokazo.

Bizning SIMD mashinada har qaysi protssesor kiritiluvchi vektorlarning ikkita koordinatasini haqida qoidasi oladi. Bu yagona qoidani bajargandan so’ng natija to’liq hisoblanadi. E’tibor bersak, N ta elementdan iborat vektorni yechishga SISD mashinaga N ta iteratsion siklni bajarish kerak bo’lsa, protsessorlar soni N tadan kam bo’lmagan SIMD – mashinaga bitta amalning o’zi yetarli. Bir nechta qoida bitta ma’lumotlar oqimi Bir vaqtda faqat bir xil ma’lumotlar ustida amal bajarish avval g’alati tuyulishi mumkin, chunki qndaydir bir sonni kvadratga ko’tarish, ikkiga ko’paytirish, o’nga bo’lish kabi dasturlar kamdan-kam uchraydi. Lekin bu holatga boshqa nuqtai-nazardan qarasak, bunday tipdagi mashinalarda sonning tub yoki murakkabligini tekshirishni takomillashtish mumkinligini ko’ramiz. Agar protsessorlar soni N ta bo’lsa, unda biz ixtiyoriy N₁ va N₂ orasidagi sonlarning tub yoki murakkabligini MISD – mashina orqali bitta operatsiyada tekshirishi miz mumkin. Agar X son murakkab bo’lsa, unda ga to’g’ri kelmaydigan bo’luvchisi bo’lishi kerak.

Protsessorlar orasidagi chambarchas bog’liqlikdan tashqari biz yana ular hammasi xotiradan ma’lumotlarni o’qish, ular ustida operatsiya bajarish va natijani xotiraga yozishdan iborat bo’lgan bir xil siklni amalga oshiradi deb faraz qilamiz. Bu barcha protsessorlar bir vaqtda xotirani o’qishini, bir vaqtda o’qilgan ma’lumotlarni qayta ishlashini, bir vaqtda yozuvni ham bajarishini anglatadi. Xotira yacheykalari ustidagi bahs nafaqat ma’lumotlarni o’qishda, balki natijani yozishda ham kelib chiqadi. Uch qadamli siklning shartlari agar Y protsessor xotira yacheykasidagi ma’lumotlarni o’zgartirgan vaqtda, X protses sor hozirgina o’qilgan ma’lumotlarni qayta ishlashi natijasida biz nima bo’lishi haqida qayg’urmasak ham bo’lishini anglatadi. Bundan tashqari, bitta protsessor xotiradan ma’lumotlarni o’qiyotgan vaqtda, ikkinchisi unga biron ma’lumot yozishga urinishi kabi vaziyatlar ham yuzaga kelmaydi.

Bahslarga faqatgina xotiraga kirishga raqobatli yoki maxsus huquq berish orqali ruxsat berish mumkin. Raqobatli kirishda xotiraning aynan bitta yacheykasiga bir vaqtda bir nechta protsessor murojaat qilishi mumkin. Maxsus kirishda esa berilgan xotira yacheykasiga aniq momentda faqat bittagina protsessor murojaat qila oladi, bir vaqtdagi ikkita murojaat qilishga urinish esa xatolik haqidagi xabarning paydo bo’lishiga olib keladi. Raqobatli kirish o’qish vaqtida muammo keltirib chiqarmaydi. Bundan tashqari bizga maxsus o’qish huquqi bilan ishlaydigan algoritmlar ham kerak. Maxsus o’qish huquqiga ega bo’lgan bir nechta protsessor bir vaqtda bitta xotira yacheykasiga murojaat qilsa xatolik paydo bo’ladi.

Bundan tashqari yozuv vaqtida maxsus va raqobatli kirishlarni tanlashda ham muammo mavjud. Maxsus kirishda har qaysi xotira yacheykasiga yozuv huquqi faqat bitta protsessorga beriladi, bir necha protsessorlar yozishga harakat qilsa, xatolik paydo bo’ladi. Lekin ikkita protsessor ikkita xotira yacheykasiga bir vaqtda yoza oladi. Raqobatli kirishda esa masala birmuncha murakkab, ya’ni kelib chiqadigan konfliktlarga ruxsat bera olish kerak. Darajaga ega modelda har bir protsessorga daraja beriladi va yozuv huquqi kattaroq darajali protsessorga beriladi.

Modelning soddalashtirilgan protsessor darajasi uning nomeriga to’g’ri keladi, ya’ni nomer qancha kichik bo’lsa, daraja shuncha katta bo’ladi. Agar, masalan, bitta xotira yacheykasiga 4- va 7- nomerli protsessorlar yozishga urinsa, huquq 4-nomerli protsessorga beriladi.

Ixtiyoriy kirishli modelda raqobat qiladigan protsessorlardan ixtiyoriy biri olinishi mumkin. Oddiy modelda esa faqatgina yoziluvchi ma’lumotlar ustma-ust tushgandagina bir vaqtda yozishga ruxsat beriladi. Kombinatsiyali modelda yoziluvchi ma’lumotlar ustida sistema bir qancha amallarni bajaradi. Masalan, ularning yig’indisi, ko’paytmasi, eng katta yoki eng kichik elementi yoki mantiqiy operatsiya natijasi (va, yoki) yozilgan bo’lishi mumkin. Turli holatlarda bu imkoniyatlardan har biri foydali bo’lishi mumkin.

Bundan kelib chiqadiki, bizda yozish va o’qish imkoniyatlarining 4 xil kombinatsiyasi mavjud:

1. 
   Raqobatli o’qish / raqobatli yozish (CRCW);
   
2. 
   Raqobatli o’qish / maxsus yozish (CREW);
   
3. 
   Maxsus o’qish / raqobatli yozish (ERCW);
   
4. 
   Maxsus o’qish / maxsus yozish (EREW);
   

Oddiy parallel operatsiyalar. Endi ikkita elementar operatsiyani ko’ramiz:

1. 
   Kiruvchi ma’lumotlarni protsessorlarga taqsimlash;
   
2. 
   Ro’yxatning eng katta va eng kichik elementini aniqlash;
   

Quyida biz i - protsessorni Pi, protsessorlar sonini p, kiruvchi ro’yxatdagi elementlar sonini N, j- xotira yacheykasini Mj bilan belgilaymiz. Bajariladigan parallel operatsiyalar qavsda Parallel Start va Parallel End kabi yoziladi. Agar boshida bitta blok operatsiyasi, undan keyin ikkinchisi parallel bajarilsa, ular alohida qavslar juftiga kiritiladi.

ISHNI BAJARISH TARTIBI

1. 
   Yuqorida keltirilgan nazariy qism va adabiyotlar bilan tanishib chiqish.
   
2. 
   Chizmaviy misollarni ko’rib chiqish.
   
3. 
   O’qituvchidan bajariladigan ish variantlarini olish.
   

TOPSHIRIQLAR VARIANTLARI

1. 
   Ishlab chiqarish korxonalarining hisoblash tizimlarini modellashtiring. (Sxema)
   
2. 
   Parallel protsessorlarni hisoblash tizimlarini modellashtiring. (Sxema)
   
3. 
   Parallel protsessorlar tavsifini tushuntiring.
   
4. 
   Korxona hisoblash tizimlarini modellashtiring. (Sxema)
   
5. 
   Parallel hisoblash tizimlarini modellashtiring. (Sxema)
   

NAZORAT SAVOLLARI

1. 
   Hisoblash tizimlari nima va u nima uchun ishlatiladi?
   
2. 
   Hisoblash tizimlarini tashkil etish g’oyasi nimalardan tashkil topgan?
   
3. 
   Parallel hisoblash tizimlarida ma’lumotlar qay tarzda beriladi?
   
4. 
   Parallel tizim elementlar bog’liqligi, tarkibi o’rtasida chegaralanish mavjudmi?
   

Parallel tizimlarni guruxlashda munosabatlar operatorlar sifatida qanday munosabatlar keltiriladi?