ALKALMAZOTT MATEMATIKAI LAPOK 3. KÖTET (A MTA Matematikai és Fizikai Tudományok Osztályának Közleményei, 1977)

1977 / 1-2. sz. - Iványi Antal és Kátai Imre: Átfedéses memóriájú számítógépek teljesítményéről

2 IVÁNYI A. ÉS KÁTAI ), az egylépéses átmeneti valószínűségek mátrixa pedig (1,2)­­ = [ptj]i,j=i azaz nti=j) = Pj­, P(et+1-j\et = i) = pij, (t = 1,2,...). Legyen pd) = P(Q,+k=j\^, = i), (t= 1,2,...;­­ = 1,2,...). A következő jól ismert állítás MARKOV nevéhez fűződik. (Ezt, megfordításával együtt, ergodicitási tételnek is nevezik.) 1.1. LEMMA. Legyen (/=1,2, ...) olyan Markov-lánc, melyre található olyan j és k, hogy minden szóbajövő /-re (i=l, ..., n) fennáll. Ekkor minden i-re és j-re fennáll kim p}p = Xj, továbbá (1.3) I ptp-Xj\*C›f, ahol g és a konstansok (0 ̋ p›l, 0,C). Legyen­­ az {1, ..., x} halmazon definiált függvény. Jelölje Maf{c,­ az /(£,) várható értékét, feltételezve, hogy 0, kezdeti eloszlása n. Tekintsünk egy másik Markov-láncot, melynek kezdeti eloszlása x = (xx, ..., x}), és az egylépéses átmenetvalószínűségek mátrixa (1.2) szerinti. Nyilvánvaló, hogy ez a Markov-lánc stacionárius, következésképpen minden /-re P(0,=h) = P(1.1=h), és így Mxf(Cl)=Mxf(£1). Továbbá, (1.3)-ból könnyen következik, hogy (1.4) ^./(O-WisCit', ahol Q és Cj alkalmas konstansok (0=p­ l, Cj·0). 2. A számítógép matematikai modellje A Vulchman-féle modell [9] szerint a számítógép központi processzorból (KP) és operatív memóriából (OM) áll. Az operatív memória n darab modulból áll: N={vb­ ..., v‡}. Minden modulhoz tartozik egy egyszavas regiszter (vrhez gt, i=l, ..., i). A programok futását coT=r1 ... rT (r,C_N, t— 1,..., T) hivatkozási sorozatokkal modellezzük. Legyen Nr az összes T-hosszúságú hivatkozási sorozat halmaza. A Vulchman-féle modell szerint а т[юг] futási idő a következőképpen számítható ki. Az r,— Vj hivatkozás feldolgozása két részből áll: az operatív memória Amem (vj megfelelő rekeszéből való kiolvasás és ^-be­töltés), a központi processzor pedig Aproc (Vj-ből való kiolvasás és a művelet elvégzése) idő alatt dolgozza fel r,-t. A processzor szekvenciálisan, a memória modulok párhuzamosan (a hivatko­zási sorozat folytatását ismerve) végzik a feldolgozást. Az egyszerűség kedvéért legyen // = {1, ..., n}. Jelöljük T,-vel (/=1, ...) azt az időpontot, amikor rx feldolgozása befejeződik. Alkalmazott Matematikai Lapok 3 (1977)

Next