Mavzu: Dinamik parallel hisoblashlar uchun parallel jarayonlarni tashkillash Mundarija

1.4. MPI xabarini uzatish interfeysi

  Xabarlarni uzatish interfeysi (MPI) - bu bitta vazifani bajaradigan jarayonlarga xabar almashish imkonini beradigan ma'lumotlarni uzatish uchun dasturlash interfeysi. Uilyam Group va Evin Lask tomonidan ishlab chiqilgan.MPI - bu parallel hisoblashni tashkil qilish uchun eng keng tarqalgan ma'lumotlar almashinuvi interfeysi standarti; ko'p sonli kompyuter platformalari uchun uning dasturlari mavjud. Ushbu standart klasterlar va superkompyuterlar uchun dasturlarni ishlab chiqishda ham qo'llaniladi. MPI standarti ham platforma, ham foydalanuvchi dasturi tomonidan qo'llab-quvvatlanadigan xabar almashish interfeysini tavsiflaydi. Hozirgi vaqtda juda ko'p miqdordagi bepul va tijorat MPI dasturlari mavjud. Fortran 77/90, C va C ++ uchun dasturlar mavjud. MPI standarti ma'lumotlar uzatish xarajatlari yuqori bo'lganda tarqatilgan xotira tizimlariga, OrepMP esa umumiy xotira tizimlariga (umumiy kesh xotirasi bo'lgan ko'p yadroli protsessorlar uchun) qaratilgan. Ikkala texnologiyadan ham bir xil klasterda ko'p yadroli tizimlardan foydalanishni optimallashtirish uchun foydalanish mumkin.

MPI ning birinchi versiyasi 1993 yilda ishlab chiqilgan. Ko'pgina zamonaviy MPI dasturlari 1.1 versiyasini qo'llab-quvvatlaydi. MPI 2.0 standarti aksariyat zamonaviy dasturlar tomonidan qo'llab-quvvatlanadi, ammo hali ham barcha funktsiyalar "to'g'ri bajarilmagan". MPI 1.1 (1995 yil 12 iyunda nashr etilgan, birinchi dastur 2002 yilda paydo bo'lgan) quyidagi xususiyatlarni qo'llab-quvvatlaydi:

• 
   jarayonlar o'rtasida xabarlarni yuborish va qabul qilish;
  
• 
   jarayonlarning jamoaviy o'zaro ta'siri;
  
• 
   jarayon guruhlaridagi o'zaro aloqalar;
  
• 
   bir qator jarayon topologiyalarini amalga oshirish.
  

MPI 2.0 (1997 yil 18-iyulda nashr etilgan) qo'shimcha ravishda quyidagi funktsiyalarni qo'llab-quvvatlaydi:

• 
   jarayonlarni dinamik yaratish va jarayonni boshqarish;
  
• 
   bir tomonlama aloqa (Get / Put);
  
• 
   parallel kirish va chiqish;
  
• 
   kengaytirilgan jamoaviy operatsiyalar (jarayonlar nafaqat bitta vazifa doirasida, balki bir nechta vazifalar doirasida ham kollektiv operatsiyalarni bajarishi mumkin). 2008 yil sentyabr oyining boshida MPI 2.1 chiqarildi.
  

Parallel jarayonlar muammoni echishda qancha ko'p ishtirok etsa, deterministik avtomatning tepalari shunchalik ko'p bo'ladi. 12 ta holatni o'z ichiga olgan ikkita parallel shoxli NDA dan olingan deterministik avtomat (4-rasm) (2-rasmga qarang), Markov jarayonlari nazariyasining qoidalarini qo'llash mumkin. U 20 ta tepalikni o'z ichiga oladi. Olingan avtomatning o'tish ehtimollarini aniqlab, uni Kronecker tizimidan foydalangan holda murakkabligi bo'yicha tahlil qilish mumkin. Umumiy holda, parallel dasturni m holatlarining parallel bo'lmagan boshlang'ich qismi, n parallel shoxlarini o'z ichiga olgan parallel qismi va / holatlarning cheklangan parallel bo'lmagan qismini o'z ichiga olgan grafik bilan ko'rsatish mumkin Unda "H" - bu boshlang'ich tepalik, "K" - yakunlovchi, "-" - ajratuvchi, "+" - ulagich, "YX; x> - bu jarayonning ba'zi holatlari (R0.x - parallel bo'lmagan qism) va soni filiallar har xil bo'lishi mumkin, bu erda x - bu filial raqami. Parallel qismdan chiqish faqat ulagich orqali amalga oshiriladi. Ulagich, shuningdek, konjunktiv deb hisoblanadi, ya'ni dastur barcha filiallar tugallangandagina o'tib ketadi. Har qanday murakkab jarayonni bir nechta sodda jarayonlarga bo'lish mumkin, ularning har biri alohida-alohida tahlil qilinishi mumkin, shuning uchun Markov jarayonlari nazariyasini qo'llash uchun dasturning parallel va parallel bo'lmagan qismlarini alohida ko'rib chiqish kerak.Umumiy holda, algoritmni turli xil kirish ma'lumotlari, turli xil filiallar soni va boshqalar bilan amalga oshirish uchun. O'tishlar ko'plab omillarga bog'liq bo'lishi mumkin va faqat empirik tarzda aniqlanishi mumkin, shuning uchun ularni ehtimollik deb hisoblash mumkin, xususan, o'tish ehtimoli dastur algoritmi bilan aniqlanadigan aniq sonlarga kamaytirilishi mumkin. Algoritmning asosiy qismini tahlil qilish uchun parallel qismni ba'zi bir "P" holatiga almashtirish kerak, natijada olingan grafaga ko'ra siz o'tish ehtimoli matritsasini tuzishingiz mumkin:

va uning asosida - har bir holatdagi hisoblash jarayonining xitlari sonini aniqlaydigan Kronecker tizimi va u birlamchi va oxirgi holatlarga bir marta kiradi deb hisoblanadi: Algoritmning murakkabligi Kronecker tizimi asosida aniqlanadi. Mehnat intensivligi deganda vaqtning murakkabligi tushuniladi, ya'ni zarur operatsiyalar majmuasini bajarishga sarflangan vaqt yoki davlatdan chiqarib tashlangan elementar operatsiyalar soni. 0 formulasi bo'yicha hisoblanadi, => GDe K - berilgan tepada shartli operatsiyalar soni, va n1 - mos ravishda, Kroneker tizimidan berilgan tepaga urish soni. Parallel algoritmning alohida tarmoqlari uchun ham shunga o'xshash hisob-kitob qilish kerak, shundan so'ng tahlil sharoitlariga qarab eng yuqori, o'rtacha yoki eng kam mehnat talab qiladigan filialni tanlash kerak. Tanlangan tarmoq uchun tizimlar parallel holatdagi qism uchun tizimdagi P holatining tenglamasi bilan almashtiriladi, bu tizimga algoritmni to'liq tahlil qilishga imkon beradi. Agar algoritm tarmoqlari turli xil ishlash tugunlarida bajarilgan bo'lsa, normallashtirish koeffitsientini joriy qilish kerak - bu ishlashning normallashtiruvchi koeffitsienti, bu zarur algoritmlar sinfidan ba'zi test masalalaridan aniqlanishi mumkin. Bu mashina haqiqiy ishlashining maksimal ishlashga nisbati sifatida hisoblanadi. "Ko'pincha parallel dasturni tushunish qiyinroq bo'ladi, ... va shuning uchun xatolar soni ham ko'payadi" degan tezis, yumshoq qilib aytganda, ziddiyatli. Ha, parallel dastur algoritmini tushunish ancha qiyin bo'lishi mumkin, ammo agar nazariya mavjud bo'lsa, uni komponentlarning algoritmlaridan rasmiy ravishda "hisoblash" mumkin. Va loyihalash, amalga oshirish va texnik xizmat ko'rsatish nuqtai nazaridan komponentlarning algoritmlari umuman tizim algoritmiga qaraganda ancha sodda. Oddiy tarkibiy qismlarni loyihalashda biz tizimni bitta qismga loyihalashdan ko'ra kamroq xatolarga yo'l qo'yamiz. Bundan tashqari, disk raskadrovka qilingan komponentlar boshqa tizimlarning bir qismi bo'lishi mumkin, bu murakkablikni kamaytiradi, ishonchliligini oshiradi va dizayndagi xarajatlarni minimallashtiradi.