Mavzu: Parallel xisoblash tizimlari

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.