|
III-BOB. Amaliy qism.
3.1. Ma'lumotlarni parallel ravishda qayta ishlash
Parallel ishlov berish printsipi
Hozirgacha ishlab chiqilgan deyarli barcha algoritmlar ketma-ketlikda. Masalan, a + b × c ifodasini baholaganda, avval ko'paytirishni amalga oshiring va shundan keyingina qo'shimchani bajaring. Agar elektron kompyuterlarda bir vaqtning o'zida ishlashi mumkin bo'lgan qo'shimcha va ayirish tugunlari bo'lsa, unda bu holda qo'shimcha tugun ko'payish tugunining ishlashi tugashini kutib turmasdan turadi. Berilgan algoritmni parallel ravishda qayta ishlaydigan dastgohni qurish mumkinligi haqidagi bayonni isbotlash mumkin.
Shu bilan bir vaqtda kompyuterning bir soatlik tsiklida kerakli natijani beradigan m protsessorlarini qurish mumkin.
Bunday "ko'p protsessor" mashinalari nazariy jihatdan har bir algoritm uchun qurilishi mumkin va algoritmlarning ketma-ketligini "chetlab o'tish" mumkin. Biroq, hamma narsa ham oddiy emas - cheksiz aniq algoritmlar mavjud, shuning uchun yuqorida ishlab chiqilgan mavhum mulohazalar amaliy ahamiyat bilan bevosita bog'liq emas. Ularning rivojlanishi parallelizatsiya qilish imkoniyatiga ishonch hosil qildi, cheksiz parallelizm kontseptsiyasining asosiga aylandi va ma'lum bir algoritmga dinamik ravishda sozlangan hisoblash muhitlari - ko'p protsessor tizimlarining amalga oshirilishini umumiy nuqtai nazardan ko'rib chiqishga imkon berdi.
3.2. Mavhum parallel hisoblash modellari
Qarama-qarshi hisoblash modeli turli xil dasturlarning bajarilish vaqtini xarakterlash va taqqoslashga yuqori darajadagi yondashuvni ta'minlaydi, shu bilan birga apparat va ijro tafsilotlaridan mavhum. Dastlabki muhim parallel hisoblash modeli Parallel Random Access Machine (PRAM) bo'lib, u umumiy xotira mashinasini qisqartirishni ta'minlaydi (PRAM - bu tasodifiy kirish tasodifiy kirish mashinasi modelining kengaytmasi, RAM - Random Access Machine). BSP (ommaviy sinxron parallel, ommaviy sinxron parallel) modeli ikkala umumiy va taqsimlangan xotiraning mavhumligini birlashtiradi. Barcha protsessorlar buyruqlarni sinxron ravishda bajaradi deb ishoniladi; bir xil buyruq bajarilgan bo'lsa, PRAM - mavhum SIMD mashinasi, (SIMD - bitta ko'rsatma oqimi / bir nechta ma'lumot oqimi - bir nechta ma'lumot oqimi bilan birga bitta ko'rsatma oqimi), ammo protsessorlar turli buyruqlarni bajarishi mumkin. Asosiy buyruqlar: xotiradan o'qish, xotiradan yozish va oddiy mantiqiy va arifmetik operatsiyalar.
PRAM modeli har bir protsessor istalgan vaqtda istalgan xotira joyiga kirish huquqiga ega bo'lishi uchun ideallashtiriladi (bitta protsessor tomonidan bajariladigan yozish operatsiyalari boshqa barcha protsessorlarga ular bajarilgan tartibda ko'rinishi mumkin, ammo har xil protsessorlar bajaradigan operatsiyalarni yozing. tasodifiy tartibda ko'rish mumkin). Masalan, PRAM-dagi har bir protsessor xotira xujayrasidan ma'lumotlarni o'qiydi yoki o'sha uyaga ma'lumotlarni yozadi. Albatta, bu haqiqiy parallel mashinalarda bo'lmaydi, chunki jismoniy darajadagi xotira modullari bir xil xotira xujayralariga kirishni osonlashtiradi. Bundan tashqari, haqiqiy mashinalarda xotiradan foydalanish vaqti keshlarning mavjudligi va xotira modullarining ierarxik tashkil etilishi tufayli bir xil emas.
Asosiy PRAM modeli parallel va parallel ravishda o'qish va yozishni qo'llab-quvvatlaydi. PRAM submodellari bir vaqtning o'zida bir nechta protsessorlarga umumiy xotiraga murojaat qilishda ziddiyatli vaziyatlardan qochish imkonini beradigan qoidalarni hisobga oladiganlar ma'lum.
Brent teoremasi parallel tasodifiy kirish mashinalari (PRAM) yordamida funktsional elementlarning zanjirlarini modellashtirishga imkon beradi. Funktsional elementlar 4 ta asosiy bo'lishi mumkin (mantiqiy operatsiyalar YO'Q, VA, YO'Q, XOR - rad qilish, mantiqiy VA, mantiqiy OR, va eksklyuziv OR, mos ravishda NAND va NOR (AND-NOT va OR-NOT), shuning uchun murakkabroq va har qanday murakkablik.
Bundan tashqari, kechikish (ya'ni, javob vaqti - kirish qiymatlarini o'rnatgandan keyin berilgan signal qiymatlari elementning chiqishida paydo bo'lgan vaqt) barcha funktsional elementlar uchun bir xil bo'ladi deb taxmin qilinadi.
Biz tsikllar shakllanmagan holda ulangan funktsional elementlarning zanjirini ko'rib chiqamiz (funktsional elementlar har qanday miqdordagi kirishlarga ega deb taxmin qilamiz, ammo aniq bitta chiqish - bir nechta chiqishi bo'lgan elementni bitta chiqish bilan bir necha element bilan almashtirish mumkin). Kirishlar soni elementning kirish darajasini va elementning chiqishi uning chiqish darajasiga bog'liq bo'lgan kirishlar sonini aniqlaydi. Odatda, ishlatilgan barcha elementlarning kirish darajalari yuqoridan cheklangan deb taxmin qilinadi, shu bilan birga chiqish darajalari har qanday bo'lishi mumkin. O'chirish hajmiga ko'ra undagi elementlarning soni tushuniladi, kontaktlarning zanglashidan elementning chiqishigacha bo'lgan yo'llardagi elementlarning eng ko'p miqdori ushbu elementning chuqurligi deb ataladi (pallaning chuqurligi uning tarkibiy elementlarining chuqurliklariga teng).
Do'stlaringiz bilan baham: |
