od Angwin » 6. 6. 2007 01:08
Zavedeme funkci f(d, s), ktera bude vracet max. pocet stranek zabranych pomoci "d" bytu, pricemz velikost jedne stranky je "s" bytu.
Pr.:
f(1, 1024) = 1
f(2, 1024) = 2
f(3, 1024) = 2
f(1025, 1024) = 2
f(1026, 1024) = 3
atd.
Toto je nejlepsi si nakreslit pomoci prihradek.
Dale definujeme funkci g_m(d, s) takto:
g_1(d, s) = f(d, s)
g_2(d, s) = f(f(d, s), s)
g_3(d, s) = f(f(f(d, s), s), s)
atd.
A ted k vypoctu v uloze. Znaceni:
Velikost dat: d
Velikost stranky: s
Velikost instrukce: i
Pocet zaznamu v tabulce: #z
Pocet urovni: #u
Vypocet rozdelime na dve casti
1. pocet vypadku na nacteni instrukce
2. pocet vypadku na presun dat
ad 1.
A = f(i, s) + g_1(f(i, s), #z) + g_2(f(i, s), #z) + ... + g_m(f(i, s), #z)
kde m = #u - 1
ad 2.
B = 2 * [ f(d, s) + g_1(f(d, s), #z) + g_2(f(d, s), #z) + ... + g_m(f(d, s), #z) ]
kde m = #u - 1 (stejne jako v 1. akorat misto "i" je "d" a bere se vsechno dvakrat)
Vysledek: A+B
Po vhodne graficke uprave pri rozepisovani vzorcu to jde docela rychle (linearne k poctu urovni)
-----------------------------------------------------------------------------------------
Priklad:
Velikost dat: d = 8kB
Velikost stranky: s = 4kB
Velikost instrukce: i = 2B
Pocet zaznamu v tabulce: #z = 1024
Pocet urovni: #u = 3
Instrukce:
A = f(2B, 4kB) + f(f(2B, 4kB), 1024) + f(f(f(2B, 4kB), 1024), 1024) =
= 2 + f(2, 1024) + f(f(2, 1024), 1024) =
= 2 + 2 + 2
= 6
Data:
A = 2 * [f(8kB, 4kB) + f(f(8kB, 4kB), 1024) + f(f(f(8kB, 4kB), 1024), 1024) ] =
= 2 * [3 + f(3, 1024) + f(f(3, 1024), 1024) ] =
= 2 * [3 + 2 + 2 ]
= 14
Vysledek: A + B = 20
Pozn.: Vsechny kB jsou behem postupu prepocitavany na B. Uz jsem to tak podrobne nerozepisoval.
Zavedeme funkci f(d, s), ktera bude vracet max. pocet stranek zabranych pomoci "d" bytu, pricemz velikost jedne stranky je "s" bytu.
Pr.:
f(1, 1024) = 1
f(2, 1024) = 2
f(3, 1024) = 2
f(1025, 1024) = 2
f(1026, 1024) = 3
atd.
Toto je nejlepsi si nakreslit pomoci prihradek.
Dale definujeme funkci g_m(d, s) takto:
g_1(d, s) = f(d, s)
g_2(d, s) = f(f(d, s), s)
g_3(d, s) = f(f(f(d, s), s), s)
atd.
A ted k vypoctu v uloze. Znaceni:
Velikost dat: d
Velikost stranky: s
Velikost instrukce: i
Pocet zaznamu v tabulce: #z
Pocet urovni: #u
Vypocet rozdelime na dve casti
1. pocet vypadku na nacteni instrukce
2. pocet vypadku na presun dat
ad 1.
A = f(i, s) + g_1(f(i, s), #z) + g_2(f(i, s), #z) + ... + g_m(f(i, s), #z)
kde m = #u - 1
ad 2.
B = 2 * [ f(d, s) + g_1(f(d, s), #z) + g_2(f(d, s), #z) + ... + g_m(f(d, s), #z) ]
kde m = #u - 1 (stejne jako v 1. akorat misto "i" je "d" a bere se vsechno dvakrat)
Vysledek: A+B
Po vhodne graficke uprave pri rozepisovani vzorcu to jde docela rychle (linearne k poctu urovni)
-----------------------------------------------------------------------------------------
Priklad:
Velikost dat: d = 8kB
Velikost stranky: s = 4kB
Velikost instrukce: i = 2B
Pocet zaznamu v tabulce: #z = 1024
Pocet urovni: #u = 3
Instrukce:
A = f(2B, 4kB) + f(f(2B, 4kB), 1024) + f(f(f(2B, 4kB), 1024), 1024) =
= 2 + f(2, 1024) + f(f(2, 1024), 1024) =
= 2 + 2 + 2
= 6
Data:
A = 2 * [f(8kB, 4kB) + f(f(8kB, 4kB), 1024) + f(f(f(8kB, 4kB), 1024), 1024) ] =
= 2 * [3 + f(3, 1024) + f(f(3, 1024), 1024) ] =
= 2 * [3 + 2 + 2 ]
= 14
Vysledek: A + B = 20
Pozn.: Vsechny kB jsou behem postupu prepocitavany na B. Uz jsem to tak podrobne nerozepisoval.