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

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
є
A 
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
j 
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
j 
tugunlardan 
v
k 
tugunga 
yo`naltirilgan har bir yoylarda ma’lumotlarning 
T
j,k
dan kam bo`lmagan elementlari ishtirok etsa 
v
k 
tugun tayyorlangan bo`ladi. 
T
j,k 
porogli (bo`sag’aviy) qiymat deb ataladi. 
v
k 
tugunga mos 
operatsiyalarni bajarishda 
v
k 
ga yo`naltirilgan mos yoydagi navbatlardan 
W
j,k 
ma’lumotlar 
elementlari olib tashlanadi. Qachonki 
v
k 
ga mos operatsiya tugallansa, u holda u 
v
k 
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
1 
tugun 
tayyorlanganki, u bitta kirishga ega va bu kirish navbatida ma’lumotning 3 ta elementi ishtirok 
etadi. 
v
1 
ning bajarilishida u navbatlardagi ma’lumotning bitta elementini olib tashlaydi va 
operatsiya tugallanishida ma’lumot elementlaridan biri 
v
1 
dan 
v
2 
dagi yoyda, yana biri 
v
1 
dan 
v
8 
dagi yoyda joylashadi. Ushbu yangi holatda yoki
v
1
,
yoki
v
2 
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
k 
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
k 
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.