Ўзбекистон республикаси ахборот технологиялари ва коммуникацияларини ривожлантириш вазирлиги муҳаммад ал-хоразмий номидаги


BILIMLAR BAZASI HOSIL QILISHDA PETRI TARMOQLARI YORDAMIDA



Download 7,61 Mb.
Pdf ko'rish
bet37/321
Sana10.07.2022
Hajmi7,61 Mb.
#768599
1   ...   33   34   35   36   37   38   39   40   ...   321
Bog'liq
591c3149ad5ef

BILIMLAR BAZASI HOSIL QILISHDA PETRI TARMOQLARI YORDAMIDA 
HISOBLASH GRAFLARINI MODELLASHTIRISH 
 
E.D.Umarov. (TATU Samarqand filiali, assistent) 
Parallel hisoblashlarning dastlabki modellaridan biri hisoblash graflari modeli hisoblanadi. 
Uni arifmetik ifodalarni hisoblovchi parallel bajaruvchi dasturlarni ifodalash uchun asosiy shakl 
sifatida taqdim etiladi. 
G
hisoblash grafi 
G=(V,A)
yo`naltirilgan graf kabi aniqlanadi, bu yerda 
V={v
1
,v
2
,…,v
n

– tugunlar to`plami; 
A={a
1
,a
2
,…,a
m
}
– yoylar to`plami. 


53 
Har bir 
a
i
є

yoylar 
v
j
dan 
v
k
gacha yoyni ifodalovchi 
(v
j
,v
k
)
tugunlarning tartiblangan 
juftliklari mavjud. Har bir 
a
i
=(v
j
,v
k
) yoyga (I
j,k
, V
j,k
, W
j,k
, T
j,k
)
to`rtlik mos qo`yilgan. Har bir yoy 
v

tugunda prosessordan olingan va 
v
k
tugunda prosessorda foydalaniladigan ma’lumotlar 
elementlari 
navbatini
ifodalaydi. 
I
j,k
v
j
dan 
v
k
gacha yoyga mos navbatning birinchi boshida 
turuvchi ma’lumotlarning elementlar sonini bildiradi. Agar har bir 
v

tugunlardan 
v

tugunga 
yo`naltirilgan har bir yoylarda ma’lumotlarning 
T
j,k
dan kam bo`lmagan elementlari ishtirok etsa 
v

tugun tayyorlangan bo`ladi. 
T
j,k 
porogli (bo`sag’aviy) qiymat deb ataladi. 
v

tugunga mos 
operatsiyalarni bajarishda 
v

ga yo`naltirilgan mos yoydagi navbatlardan 
W
j,k 
ma’lumotlar 
elementlari olib tashlanadi. Qachonki 
v

ga mos operatsiya tugallansa, u holda u 
v

tugundan 
v
r
 
tugunga yo`naltirilgan har bir 
(v
k
,v
r

yoylarga mos navbatlarda 
V
k,r 
ma’lumotlar elementlarida 
joylashadi. 
 
1.1-rasm.
 Hisoblash graflari 
1.1-rasmda hisoblash graflariga misol tasvirlangan. Boshlang’ich holatda 
v

tugun 
tayyorlanganki, u bitta kirishga ega va bu kirish navbatida ma’lumotning 3 ta elementi ishtirok 
etadi. 
v

ning bajarilishida u navbatlardagi ma’lumotning bitta elementini olib tashlaydi va 
operatsiya tugallanishida ma’lumot elementlaridan biri 
v

dan 
v

dagi yoyda, yana biri 
v

dan 
v

dagi yoyda joylashadi. Ushbu yangi holatda yoki
v
1
,
yoki
v

huddi ikalasi ham porogli shartni 
qanoatlantirishi uchun kirish navbatlaridagi ma’lumotlarning yetarlicha elementlariga ega 
bo`lganidek bajarilishi mumkin. 
1.2-rasm.
 1.1-rasmda tasvirlangan hisoblash graflariga ekvivalent Petri tarmoqlari 


54 
Hisoblash graflari Petri tarmoqlarida oson modellashtiriladi. Har bir yoy vaziyatlarni ifodalaydi, 
hisoblash graflarning har bir tuguni esa o`tishlarni shakllantiradi. 
v

tugunga mos o`tishlar
 v
j
dan 
v
k
gacha yoylarni ifodalaydigan vaziyatlarning 
T
j,k
kirish yoyiga ega bo`ladi. Bu qachonki porogli 
shart bajarilgandagina o`tishlarning tayyorlanganligini kafolatlaydi. Biroq, o`tishlar yuklanganda 
u faqatgina 
W
j,k 
toshchani olib tashlashi mumkin, shuning uchun 
T
j,k
 – W
j,k
yoyi
 v

o`tishlardan 
v
j
dan 
v
k
gacha yoylarni ifodalaydigan vaziyatlarga teskari yo`naltiriladi. Bundan tashqari, 
V
k,r 
belgi 
v
j
dan 
v
k
gacha yoylarni ifodalaydigan vaziyatlarda joylashadi. Boshlang’ich belgilash 
I
j,k
qiymati 
bilan aniqlanadi. 
Yuqorida ifodalangan usullar asosida qurilgan 1.1-rasmdagi hisoblashlar grafi uchun 1.2-
rasmda Petri tarmoqlari tasvirlangan.
Markerlangan graflarning barcha 
v
j
va 
v
k
tugunlada
 T
j,k
 = W
j,k
uchun hisoblash graflarni 
modellashtirishining mumkinligini osongina ko`rsatish mumkin. Biroq, hisoblash graflari 
T
j,k

W
j,k 
holatli vaziyatlarni modellashtirish imkoniyatiga ko`ra markerlangan graflardan quvvatliroq 
vosita hisoblanadi.
1.3- rasm. 
Modellar ierarxiyasiga hisoblash graflarning qo`shilishi
Boshqa tomondan esa, hisoblash graflari va chekli avtomatlar markerlangan graflar hamda 
chekli avtomatlar kabi solishtirilmaydi. Hisoblash graflari qaror qabul qilish yoki shartli bajarishni 
modellashtira olmaydi, bu cheklanish markerlangan graflar uchun ham o`rinli. Shunday qilib, 
model iyerarxiyasi 1.3-rasmda ko`rsatilgan ko`rinishga ega bo`ladi. 
Karp va Miller hisoblash graflarini, ayniqsa, faollik va xavfsizlik masalalarida atroflicha 
tadqiq qilishgan. Haqiqatda esa ularni hisoblash graflarining tugallanganlik shartlar(ya’ni 
nofaollik shartlari)ni ta’minlash va aniqlash masalasi qiziqtirgan. Ma’lumotlar navbati yoylar 
(vaziyatlar) kabi ifodalangan holatda Karp va Miller tomonidan o`tkazilgan cheklanishlar 
tadqiqotlari navbatni maksimal uzunligini aniqlashga yo`naltirilgan edi. Belgilashlardagi va 
maqsaddagi bunday farqlar hamda hisoblash graflari va markerlangan graflar orasidagi modellarni 
aniqlashdagi tafovutlar – hisoblash graflarining markerlangan graflar bo`yicha Karp va Miller 
natijalari va algoritmlari biror kishining urunishlari yaqinlashmaganligining sababi bo`lib xizmat 
qiladi.

Download 7,61 Mb.

Do'stlaringiz bilan baham:
1   ...   33   34   35   36   37   38   39   40   ...   321




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish