Архитектура В. С. Lab3. Моделирование буферной памяти систем и исследование её характеристик

Цель работы

Знакомство со структурой кэш-памяти и принципами ее функционирования. Оценка выигрыша от применения кэш-памяти в вычислительных системах.

Задание на лабораторную работу.

Реализовать на языке программирования модель работы системы с кэшем. Дать оценку эффективности работы кэша путем его тестирования (множество циклов записи и чтения с подсчетом статистики). Тестирование проводить при помощи какого-либо алгоритма (например, сортировки).

Подсказка. При реализации модели на языке высокого уровня, такого как Pascal или C можно поступить следующим образом. Основная память, кэш-память будут представлять из себя двухмерные массивы. Алгоритм тестирования будет “представлять” для себя основную память, как одномерный массив с известными границами. Но все обращения к этому массиву будут идти не через стандартные операторы выбора элемента массива, а через некоторые функции read и write. Вызовы этих функций будут направляться на обработку третьей функции — контроллеру кэш-памяти, которая и будет выполнять все операции, связанные с кэшированием. Подсчет статистики можно вести в функции-контроллере кэш-памяти.

Размер основной памяти, кэш-памяти, блока выбирается и обосновывается студентом. Механизм поиска адресов — ассоциативный. Стратегия замещения блоков – LRU и случайная. Способ записи – сквозная и обратная.

Параметры по которым будет оцениваться работа кэш-памяти определить самостоятельно (например, число кэш-промахов при числе операций чтения).

Текст программы:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>

const int BLOCK_SIZE=64;
typedef  int BLOCK[BLOCK_SIZE]; 
enum CHANGESTRATEGY{csLRU,csRANDOM};
enum WRITESTRATEGY{wsTHROUGH,wsBACK};

const int OZUBlockCount=128;
const int OZUSize=BLOCK_SIZE*OZUBlockCount;
const int CacheBlockCount=16;
const int CacheSize=CacheBlockCount*BLOCK_SIZE;

BLOCK * OZU=0,* Cache=0;
int CacheHandbook[CacheBlockCount];
int Oldness[CacheBlockCount];
CHANGESTRATEGY ChangeStrategy=csRANDOM;
WRITESTRATEGY WriteStrategy=wsTHROUGH;

////////////////////////////////////////////////////////////////////////////////
//Для подсчёта статистики
int GetCount=0;
int MissCount=0;
int CallCount=0;
///////////////////////////////////////////////// 
void Initialize();
void Deinitialize();
void Sort();
void WriteOZU(int Address,int Number);
int ReadOZU(int Address);
bool IsInCash(int addr, int * block);
void LoadBlock(int Address);
int Oldest();

int main(int argc, char *argv[])
{
	try{
		Initialize();
		Sort();
		printf("Get count: %i\n",GetCount);
		printf("Miss count: %i\n",MissCount);
		printf("Call count: %i\n",CallCount);
		Deinitialize();
		return 0;
	}
	catch(char *s)
	{
		fprintf(stderr,"Error: %s",s);
		Deinitialize(); 
		return 1;
	}
}

void Initialize()
{
	int n,m;
	OZU=new BLOCK[OZUBlockCount];
	Cache= new BLOCK[CacheBlockCount];
	memset((void*)CacheHandbook,-1,CacheBlockCount);
	memset((void*)CacheHandbook,0,CacheBlockCount);

	srand((unsigned )time(0)); 
	for (n=0;n<OZUBlockCount;n++)
	{
		for (m=0;m<BLOCK_SIZE;m++)
		{
			OZU[n][m]=rand();
		}
	}
	if ((!OZU)||(!Cache))
	{
		throw "Not enough memory.";
	}
}

void Deinitialize()
{
	if (OZU)
	{
		delete []OZU;
		OZU=0;
	}
	if (Cache)
	{
		delete []Cache;
		Cache=0;
	}
}

void Sort()
{
	int n,m,v1,v2,buff;
	const int First=0, End=BLOCK_SIZE*OZUBlockCount,Size=End-First;
	printf("Calculating. Please wait...");
	for (n=First;n<End;n++)
	{
		for (m=n+1;m<End;m++)
		{
			v1=ReadOZU(n);
			v2=ReadOZU(m);
			if (v1>v2)
			{
				buff=v2;
				WriteOZU(m,v1);
				WriteOZU(n,buff);
			}
		}
		printf("Progress: %3.2f\n",((float)n)/((float)Size-1.0)*100.0);
	}
}

void WriteOZU(int Address,int Number)
{
	int block;
	if (WriteStrategy == wsTHROUGH)
	{
		OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE]=Number;
		if (IsInCash(Address,&block))
		{
			Cache[block][Address%BLOCK_SIZE] = Number;
			
		}
	} 
	else
	{
		if (IsInCash(Address,&block))
		{
			Cache[block][Address%BLOCK_SIZE] = Number;
		}
		else
		{
			OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE]=Number;
		}
	}
}

int ReadOZU(int Address)
{
	int block,res;
	CallCount++;
	if (IsInCash(Address,&block)) 
	{	
	   res=Cache[block][Address%BLOCK_SIZE]; 
	   GetCount++;
	   Oldness[block]=0;
	   
	}
	else 
	{
		res=OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE];
		MissCount++;
		LoadBlock(Address);
		
	}
	return res;
}

bool IsInCash(int addr, int * block)
{
	bool flag=false;
	for (int i=0;i< CacheBlockCount;i++)
		if (CacheHandbook[i] == addr/BLOCK_SIZE) {*block=i;flag=true; break;};
	 return flag;
}

////////////////////////////////////////////////////////////////////////////////
//Загружает блок в КЭШ
////////////////////////////////////////////////////////////////////////////////
void LoadBlock(int Address)
{
	int Number=0;
	if (ChangeStrategy==csRANDOM)
	{
		Number = (rand()%CacheBlockCount);
	}
	else 
	{
		Number = Oldest();
		Oldness[Number]=0;
	}

	//Запись блока данных из кэш-памяти в оперативную (обновление данных);
	if (WriteStrategy == wsBACK)
	{
		if (CacheHandbook[Number]!=-1) for (int n=0;n<BLOCK_SIZE;n++)
			OZU[CacheHandbook[Number]][n]=Cache[Number][n];
	};
	
	CacheHandbook[Number]=Address/BLOCK_SIZE;
	for (int n=0;n<BLOCK_SIZE;n++) 
	Cache[Number][n]=OZU[Address/BLOCK_SIZE][n];

	if (ChangeStrategy==csLRU)
		for (n=0;n<CacheBlockCount;n++) Oldness[n]++;
}

////////////////////////////////////////////////////////////////////////////////
//Производит поиск блока в КЭШ, который не  использовался дольше всего
////////////////////////////////////////////////////////////////////////////////
int Oldest()
{
	int res = 0;
	for (int i=1;i<CacheBlockCount;i++) 
		if ((Oldness[i]>Oldness[res])/*&&(Assotiation[i]!=0xffffffff)*/) res = i;
	return res;
};

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <memory.h>

const int BLOCK_SIZE=64;

typedef int BLOCK[BLOCK_SIZE];

enum CHANGESTRATEGY{csLRU,csRANDOM};

enum WRITESTRATEGY{wsTHROUGH,wsBACK};

const int OZUBlockCount=128;

const int OZUSize=BLOCK_SIZE*OZUBlockCount;

const int CacheBlockCount=16;

const int CacheSize=CacheBlockCount*BLOCK_SIZE;

BLOCK * OZU=0,* Cache=0;

int CacheHandbook[CacheBlockCount];

int Oldness[CacheBlockCount];

CHANGESTRATEGY ChangeStrategy=csRANDOM;

WRITESTRATEGY WriteStrategy=wsTHROUGH;

////////////////////////////////////////////////////////////////////////////////

//Для подсчёта статистики

int GetCount=0;

int MissCount=0;

int CallCount=0;

/////////////////////////////////////////////////

void Initialize();

void Deinitialize();

void Sort();

void WriteOZU(int Address,int Number);

int ReadOZU(int Address);

bool IsInCash(int addr, int * block);

void LoadBlock(int Address);

int Oldest();

int main(int argc, char *argv[])

{

try{

Initialize();

Sort();

printf("Get count: %i\n",GetCount);

printf("Miss count: %i\n",MissCount);

printf("Call count: %i\n",CallCount);

Deinitialize();

return 0;

}

catch(char *s)

{

fprintf(stderr,"Error: %s",s);

Deinitialize();

return 1;

}

void Initialize()

{

int n,m;

OZU=new BLOCK[OZUBlockCount];

Cache= new BLOCK[CacheBlockCount];

memset((void*)CacheHandbook,-1,CacheBlockCount);

memset((void*)CacheHandbook,0,CacheBlockCount);

srand((unsigned )time(0));

for (n=0;n<OZUBlockCount;n++)

{

for (m=0;m<BLOCK_SIZE;m++)

{

OZU[n][m]=rand();

}

if ((!OZU)||(!Cache))

{

throw "Not enough memory.";

}

void Deinitialize()

{

if (OZU)

{

delete []OZU;

OZU=0;

}

if (Cache)

{

delete []Cache;

Cache=0;

}

void Sort()

{

int n,m,v1,v2,buff;

const int First=0, End=BLOCK_SIZE*OZUBlockCount,Size=End-First;

printf("Calculating. Please wait...");

for (n=First;n<End;n++)

{

for (m=n+1;m<End;m++)

{

v1=ReadOZU(n);

v2=ReadOZU(m);

if (v1>v2)

{

buff=v2;

WriteOZU(m,v1);

WriteOZU(n,buff);

}

printf("Progress: %3.2f\n",((float)n)/((float)Size-1.0)*100.0);

}

void WriteOZU(int Address,int Number)

{

int block;

if (WriteStrategy == wsTHROUGH)

{

OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE]=Number;

if (IsInCash(Address,&block))

{

Cache[block][Address%BLOCK_SIZE] = Number;

}

else

{

if (IsInCash(Address,&block))

{

Cache[block][Address%BLOCK_SIZE] = Number;

}

else

{

OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE]=Number;

}

int ReadOZU(int Address)

{

int block,res;

CallCount++;

if (IsInCash(Address,&block))

{

res=Cache[block][Address%BLOCK_SIZE];

GetCount++;

Oldness[block]=0;

}

else

{

res=OZU[Address/BLOCK_SIZE][Address%BLOCK_SIZE];

MissCount++;

LoadBlock(Address);

}

return res;

}

bool IsInCash(int addr, int * block)

{

bool flag=false;

for (int i=0;i< CacheBlockCount;i++)

if (CacheHandbook[i] == addr/BLOCK_SIZE) {*block=i;flag=true; break;};

return flag;

}

////////////////////////////////////////////////////////////////////////////////

//Загружает блок в КЭШ

////////////////////////////////////////////////////////////////////////////////

void LoadBlock(int Address)

{

int Number=0;

if (ChangeStrategy==csRANDOM)

{

Number = (rand()%CacheBlockCount);

}

else

{

Number = Oldest();

Oldness[Number]=0;

}

//Запись блока данных из кэш-памяти в оперативную (обновление данных);

if (WriteStrategy == wsBACK)

{

if (CacheHandbook[Number]!=-1) for (int n=0;n<BLOCK_SIZE;n++)

OZU[CacheHandbook[Number]][n]=Cache[Number][n];

};

CacheHandbook[Number]=Address/BLOCK_SIZE;

for (int n=0;n<BLOCK_SIZE;n++)

Cache[Number][n]=OZU[Address/BLOCK_SIZE][n];

if (ChangeStrategy==csLRU)

for (n=0;n<CacheBlockCount;n++) Oldness[n]++;

}

////////////////////////////////////////////////////////////////////////////////

//Производит поиск блока в КЭШ, который не использовался дольше всего

////////////////////////////////////////////////////////////////////////////////

int Oldest()

{

int res = 0;

for (int i=1;i<CacheBlockCount;i++)

if ((Oldness[i]>Oldness[res])/*&&(Assotiation[i]!=0xffffffff)*/) res = i;

return res;

};

Результаты теста (при размере ОЗУ 1024 блоков, размер блока 8 байт):

Количество промахов при различных размерах буферной памяти:

Алгоритм замены блоков	8	16	32	64
LRU	6.25	6.24	6.24	6.22
случайный	7.14	6.66	6.43	6.27

Следовательно, алгоритм замещения LRU позволяет повысить эффективность использования буферной памяти.

Результаты теста (при размере ОЗУ 1024 блоков, размер блока 16 байт):

	8	16	32	64
LRU	3,12	3,12	3,12	3,11
RANDOM	3,57	3,33	3,21	3,13

Вывод:
По результатам тестов были построены следующие графики:

Из них видно, что при увеличении количества блоков буферной памяти процент промахов для случайного алгоритма замены блоков уменьшается быстрее чем для алгоритма LRU. Это связано с тем, что при увеличении числа блоков, шанс заменить нужный блок уменьшается.

При увеличении размера блоков процент промахов уменьшается, так как увеличивается число успешных попаданий, а число промахов остаётся прежним.

Скачать архив с лабораторной работой и исходными кодами программ

Октябрь 2015
Пн	Вт	Ср	Чт	Пт	Сб	Вс
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

Добавить комментарий Отменить ответ