G‘afarov, A. F. Galimyanov parallel hisobiyotlar qo'llanma Qozon

Ma'lumotlar parallelligi bilan bog'liq muammolarda dekompozitsiya



Hisob-kitoblarni mustaqil qismlarga bo'lish usuli bog'liq

jihatidan yechiluvchi masala qanchalik to'liq parchalanish xususiyatiga ega

berilgan tasnifdagi algoritmning o'rni bilan belgilanadigan ma'lumotlar

4.1-bo'lim. Muammo bilan algoritmlar sinfida amalga oshirishni qabul qilsa

ma'lumotlarni taqsimlash (Ma'lumotlarni qismlarga ajratish), pastki vazifalarga parallellashtirish

ancha osonlashtiriladi. Bunday holda, bitta operatsiya yoki to'plam

operatsiyalar ma'lumotlar massivining barcha elementlarida va vazifada bajariladi

boshlang'ich ma'lumotlar massivini bo'laklarga bo'lish, qayta ishlashga qisqartiriladi

turli protsessorlarda mustaqil ishlaydi. Shu bilan birga, odatda

ta'minlash talab qilinadi:

o ajratilgan kichik vazifalardagi hisob-kitoblarning taxminan teng miqdori;

o'rtasida ma'lumotlarning minimal almashinuvi

protsessorlar.

Keling, ushbu talablarning turli sharoitlarda bajarilishini ko'rib chiqaylik.

46
Machine Translated by Google
Tashkilot nuqtai nazaridan eng oddiy va eng qulay
parallel hisoblash, vazifaning dastlabki ma'lumotlarining butun maydoni bo'lganda
har qanday o'lchamdagi bir-birining ustiga chiqmaydigan hududlarga bo'linishi mumkin va har bir sohada hisob-kitoblar mustaqil ravishda amalga oshirilishi mumkin. Bunda aniq Bunday holda, parchalanish vazifasi juda oddiy: sizga butun domen kerak
soni mavjud protsessorlar soniga teng bo'lgan subregionlarga bo'linadi va subregionlarning o'lchamlarini ularning bir xilligini ta'minlash uchun tanlang
har birining ish faoliyatini hisobga olgan holda ish yuki.

Hisob-kitoblarni tashkil qilish nuqtai nazaridan, odatda, qulayroqdir

hududlarga bo'linish, to'g'ri chiziqlar va tekisliklar ko'rinishidagi chegaralar bilan. Yoniq guruch. 4.2 eng ko'p ishlatiladigan muntazam misollar keltirilgan
ma'lumotlar bo'yicha parchalanishda asosiy pastki vazifalarning tuzilmalari.

Guruch. 4.2 Asosiyning muntazam bir, ikki va uch o'lchovli tuzilmalari

ma'lumotlar parchalanishidan keyin pastki vazifalar

Ma'lumotlarni parchalashda ko'pgina amaliy muammolar uchun

Har bir domendagi hisob-kitoblar butunlay mustaqil bo'lishi mumkin emas. DA xususan, har bir iteratsiyadan keyin (barcha nuqtalarda hisob-kitoblar maydoni) hisob-kitoblar natijalarini chegaralarda almashish zarurati tug'iladi qo'shni hududlar. Bu, masalan, ko'pchilik panjara uchun odatiy hisoblanadi ba'zi bir tugundagi funktsiya qiymatini hisoblash usullari
uning qiymatlari bir nechta qo'shni tugunlarda qo'llaniladi. Ushbu holatda yuqoridagi talablarga javob berish: yukni muvozanatlash
protsessorlari va axborot almashinuvini minimallashtirish nafaqat bog'liq

subdomenlarning o'lchamlari, balki ularning shakli bo'yicha ham.

Machine Translated by Google

Guruch. 4.3 Ma'lumotlarni hududlarga ajratish: a - lenta sxemasi, b - blok

sxema
Misol uchun, ikki o'lchovli muammo bo'lsa, ko'pincha bittasi ishlatiladi ikki turdagi parchalanish: bir maydon alohida bo'linishi mumkin
qatorlar (yoki ketma-ket qatorlar guruhlari) - lenta sxemasi deb ataladi

ma'lumotlarni ajratish yoki elementlarning to'rtburchaklar to'plamiga - blok diagrammasi ma'lumotlarni ajratish (4.3-rasmga qarang). Tabiiy savol tug'iladi: ulardan qaysi biri parchalanish sxemalari "yaxshiroq"?

Ushbu parchalanish sxemalaridan birini tanlash talab bilan belgilanadi

protsessorlar o'rtasida ma'lumotlar uzatishni minimallashtirish. Ushbu muammoni ko'rib chiqing ikki o'lchovli holat uchun. Hududlar shaklda berilgan deb taxmin qilamiz

to'rtburchaklar yoki kvadratlar, chegaralar yaqinidagi ma'lumotlar diapazonlarining kengligi,

protsessorlar orasidagi chegaralar yo'nalishiga bog'liq emas

fragmentlar va uzatilgan ma'lumotlarning miqdori konjugatsiya uzunligi bilan belgilanadi parcha chegaralari. Keling, ikki o'lchovli parchalanishga oddiy misol keltiraylik

o'lchamlari × bo'lgan maydon
, ÿ. Ma'lumotlar maydonini parchalashda

to'rtta kichik sohalarga (protsessorlarga) uzatilgan ma'lumotlarning umumiy miqdori qachon ma'lumotlarni lenta ajratish (L tomoni bo'ylab ) 3L proportsional bo'ladi , va qachon

blok (teng to'rtburchaklar ichiga) - H + L.

Juftliklar o'rtasida protsessorlararo ma'lumotlar almashinuvining maksimal miqdori qo'shni hududlarni qayta ishlash protsessorlari, mos ravishda, L va bo'ladi

Machine Translated by Google
H/ 2. Bir xil umumiy va maksimal interprotsessorni payqash oson
almashinuvi H=2L da sodir bo'ladi. Agar H<2L bo'lsa, bloklarni parchalash foydaliroq bo'ladi,
H>2L da - lenta. Turli xil miqdordagi protsessorlar (subregionlar) uchun ekanligi aniq.

natijalar boshqacha bo'lishi mumkin.

Agar blokning parchalanishi foydaliroq ekanligi ma'lum bo'lsa, keyingisi Muhim masala - blok o'lchamlarini tanlash. Minimallashtirish nuqtai nazaridan chegara hududlari uzunligining ularning maydoniga nisbati (proportsional protsessorlararo almashinuv hajmining berilgandagi hisob-kitoblar hajmiga nisbati subdomainlar) ko'rinishidan, subdomenlar shakli shaklda olinishi kerak kvadratchalar yoki kvadratlarga yaqin to'rtburchaklar. Biroq, ayni paytda

yana bir muammo yuzaga keladi.

Dastlabki ma'lumotlarni qayta ishlash maydonini kvadratlarga bo'lishda chegaralarda joylashgan fragmentlar uchun bir xil o'lcham

parchalanadigan maydon, qo'shni bilan bog'liq chegaralarning uzunligi fragmentlar va, demak, uzatiladigan ma'lumotlarning miqdori kamroq bo'ladi.
Ma'lumot uzatish vaqtidagi bu farq ta'sir qilishi mumkin
protsessordan foydalanish samaradorligiga sezilarli ta'sir ko'rsatadi, agar ma'lumotlarni uzatish tezligi past. Samarasizlikdan foydalaning protsessorlar kirgan hududlar soni ko'proq seziladi
tasvir kichik.

Protsessordan foydalanish samaradorligini oshirish mumkin chegaralarida va ichida joylashgan hududlar hajmini oshirish orqali erishiladi

tasvirning burchaklari. Keyingi bo'limda bu masala haqida batafsil ma'lumot beriladi. blokning parchalanishi holati uchun ko'rib chiqiladi.

5.