Prefetcher.cc (10466:73b7549d979e) Prefetcher.cc (11025:4872dbdea907)
1/*
2 * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;

--- 28 unchanged lines hidden (view full) ---

37 return new Prefetcher(this);
38}
39
40Prefetcher::Prefetcher(const Params *p)
41 : SimObject(p), m_num_streams(p->num_streams),
42 m_array(p->num_streams), m_train_misses(p->train_misses),
43 m_num_startup_pfs(p->num_startup_pfs), m_num_unit_filters(p->unit_filter),
44 m_num_nonunit_filters(p->nonunit_filter),
1/*
2 * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;

--- 28 unchanged lines hidden (view full) ---

37 return new Prefetcher(this);
38}
39
40Prefetcher::Prefetcher(const Params *p)
41 : SimObject(p), m_num_streams(p->num_streams),
42 m_array(p->num_streams), m_train_misses(p->train_misses),
43 m_num_startup_pfs(p->num_startup_pfs), m_num_unit_filters(p->unit_filter),
44 m_num_nonunit_filters(p->nonunit_filter),
45 m_unit_filter(p->unit_filter, Address(0)),
46 m_negative_filter(p->unit_filter, Address(0)),
47 m_nonunit_filter(p->nonunit_filter, Address(0)),
45 m_unit_filter(p->unit_filter, 0),
46 m_negative_filter(p->unit_filter, 0),
47 m_nonunit_filter(p->nonunit_filter, 0),
48 m_prefetch_cross_pages(p->cross_page),
49 m_page_shift(p->sys->getPageShift())
50{
51 assert(m_num_streams > 0);
52 assert(m_num_startup_pfs <= MAX_PF_INFLIGHT);
53
54 // create +1 stride filter
55 m_unit_filter_index = 0;

--- 72 unchanged lines hidden (view full) ---

128
129 numMissedPrefetchedBlocks
130 .name(name() + ".misses_on_prefetched_blocks")
131 .desc("number of misses for blocks that were prefetched, yet missed")
132 ;
133}
134
135void
48 m_prefetch_cross_pages(p->cross_page),
49 m_page_shift(p->sys->getPageShift())
50{
51 assert(m_num_streams > 0);
52 assert(m_num_startup_pfs <= MAX_PF_INFLIGHT);
53
54 // create +1 stride filter
55 m_unit_filter_index = 0;

--- 72 unchanged lines hidden (view full) ---

128
129 numMissedPrefetchedBlocks
130 .name(name() + ".misses_on_prefetched_blocks")
131 .desc("number of misses for blocks that were prefetched, yet missed")
132 ;
133}
134
135void
136Prefetcher::observeMiss(const Address& address, const RubyRequestType& type)
136Prefetcher::observeMiss(Addr address, const RubyRequestType& type)
137{
138 DPRINTF(RubyPrefetcher, "Observed miss for %s\n", address);
137{
138 DPRINTF(RubyPrefetcher, "Observed miss for %s\n", address);
139 Address line_addr = line_address(address);
139 Addr line_addr = makeLineAddress(address);
140 numMissObserved++;
141
142 // check to see if we have already issued a prefetch for this block
143 uint32_t index = 0;
144 PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
145 if (pfEntry != NULL) {
146 if (pfEntry->requestIssued[index]) {
147 if (pfEntry->requestCompleted[index]) {

--- 48 unchanged lines hidden (view full) ---

196 }
197 if (hit) {
198 DPRINTF(RubyPrefetcher, " *** hit in non-unit stride buffer\n");
199 return;
200 }
201}
202
203void
140 numMissObserved++;
141
142 // check to see if we have already issued a prefetch for this block
143 uint32_t index = 0;
144 PrefetchEntry *pfEntry = getPrefetchEntry(line_addr, index);
145 if (pfEntry != NULL) {
146 if (pfEntry->requestIssued[index]) {
147 if (pfEntry->requestCompleted[index]) {

--- 48 unchanged lines hidden (view full) ---

196 }
197 if (hit) {
198 DPRINTF(RubyPrefetcher, " *** hit in non-unit stride buffer\n");
199 return;
200 }
201}
202
203void
204Prefetcher::observePfMiss(const Address& address)
204Prefetcher::observePfMiss(Addr address)
205{
206 numPartialHits++;
207 DPRINTF(RubyPrefetcher, "Observed partial hit for %s\n", address);
208 issueNextPrefetch(address, NULL);
209}
210
211void
205{
206 numPartialHits++;
207 DPRINTF(RubyPrefetcher, "Observed partial hit for %s\n", address);
208 issueNextPrefetch(address, NULL);
209}
210
211void
212Prefetcher::observePfHit(const Address& address)
212Prefetcher::observePfHit(Addr address)
213{
214 numHits++;
215 DPRINTF(RubyPrefetcher, "Observed hit for %s\n", address);
216 issueNextPrefetch(address, NULL);
217}
218
219void
213{
214 numHits++;
215 DPRINTF(RubyPrefetcher, "Observed hit for %s\n", address);
216 issueNextPrefetch(address, NULL);
217}
218
219void
220Prefetcher::issueNextPrefetch(const Address &address, PrefetchEntry *stream)
220Prefetcher::issueNextPrefetch(Addr address, PrefetchEntry *stream)
221{
222 // get our corresponding stream fetcher
223 if (stream == NULL) {
224 uint32_t index = 0;
225 stream = getPrefetchEntry(address, index);
226 }
227
228 // if (for some reason), this stream is unallocated, return.
229 if (stream == NULL) {
230 DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
231 return;
232 }
233
234 // extend this prefetching stream by 1 (or more)
221{
222 // get our corresponding stream fetcher
223 if (stream == NULL) {
224 uint32_t index = 0;
225 stream = getPrefetchEntry(address, index);
226 }
227
228 // if (for some reason), this stream is unallocated, return.
229 if (stream == NULL) {
230 DPRINTF(RubyPrefetcher, "Unallocated stream, returning\n");
231 return;
232 }
233
234 // extend this prefetching stream by 1 (or more)
235 Address page_addr = pageAddress(stream->m_address);
236 Address line_addr = next_stride_address(stream->m_address,
237 stream->m_stride);
235 Addr page_addr = pageAddress(stream->m_address);
236 Addr line_addr = makeNextStrideAddress(stream->m_address,
237 stream->m_stride);
238
239 // possibly stop prefetching at page boundaries
240 if (page_addr != pageAddress(line_addr)) {
241 numPagesCrossed++;
242 if (!m_prefetch_cross_pages) {
243 // Deallocate the stream since we are not prefetching
244 // across page boundries
245 stream->m_is_valid = false;

--- 25 unchanged lines hidden (view full) ---

271 }
272
273 return lru_index;
274}
275
276void
277Prefetcher::clearNonunitEntry(uint32_t index)
278{
238
239 // possibly stop prefetching at page boundaries
240 if (page_addr != pageAddress(line_addr)) {
241 numPagesCrossed++;
242 if (!m_prefetch_cross_pages) {
243 // Deallocate the stream since we are not prefetching
244 // across page boundries
245 stream->m_is_valid = false;

--- 25 unchanged lines hidden (view full) ---

271 }
272
273 return lru_index;
274}
275
276void
277Prefetcher::clearNonunitEntry(uint32_t index)
278{
279 m_nonunit_filter[index].setAddress(0);
279 m_nonunit_filter[index] = 0;
280 m_nonunit_stride[index] = 0;
281 m_nonunit_hit[index] = 0;
282}
283
284void
280 m_nonunit_stride[index] = 0;
281 m_nonunit_hit[index] = 0;
282}
283
284void
285Prefetcher::initializeStream(const Address& address, int stride,
285Prefetcher::initializeStream(Addr address, int stride,
286 uint32_t index, const RubyRequestType& type)
287{
288 numAllocatedStreams++;
289
290 // initialize the stream prefetcher
291 PrefetchEntry *mystream = &(m_array[index]);
286 uint32_t index, const RubyRequestType& type)
287{
288 numAllocatedStreams++;
289
290 // initialize the stream prefetcher
291 PrefetchEntry *mystream = &(m_array[index]);
292 mystream->m_address = line_address(address);
292 mystream->m_address = makeLineAddress(address);
293 mystream->m_stride = stride;
294 mystream->m_use_time = m_controller->curCycle();
295 mystream->m_is_valid = true;
296 mystream->m_type = type;
297
298 // create a number of initial prefetches for this stream
293 mystream->m_stride = stride;
294 mystream->m_use_time = m_controller->curCycle();
295 mystream->m_is_valid = true;
296 mystream->m_type = type;
297
298 // create a number of initial prefetches for this stream
299 Address page_addr = pageAddress(mystream->m_address);
300 Address line_addr = line_address(mystream->m_address);
301 Address prev_addr = line_addr;
299 Addr page_addr = pageAddress(mystream->m_address);
300 Addr line_addr = makeLineAddress(mystream->m_address);
302
303 // insert a number of prefetches into the prefetch table
304 for (int k = 0; k < m_num_startup_pfs; k++) {
301
302 // insert a number of prefetches into the prefetch table
303 for (int k = 0; k < m_num_startup_pfs; k++) {
305 line_addr = next_stride_address(line_addr, stride);
304 line_addr = makeNextStrideAddress(line_addr, stride);
306 // possibly stop prefetching at page boundaries
307 if (page_addr != pageAddress(line_addr)) {
308 numPagesCrossed++;
309 if (!m_prefetch_cross_pages) {
310 // deallocate this stream prefetcher
311 mystream->m_is_valid = false;
312 return;
313 }
314 }
315
316 // launch prefetch
317 numPrefetchRequested++;
318 DPRINTF(RubyPrefetcher, "Requesting prefetch for %s\n", line_addr);
319 m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
305 // possibly stop prefetching at page boundaries
306 if (page_addr != pageAddress(line_addr)) {
307 numPagesCrossed++;
308 if (!m_prefetch_cross_pages) {
309 // deallocate this stream prefetcher
310 mystream->m_is_valid = false;
311 return;
312 }
313 }
314
315 // launch prefetch
316 numPrefetchRequested++;
317 DPRINTF(RubyPrefetcher, "Requesting prefetch for %s\n", line_addr);
318 m_controller->enqueuePrefetch(line_addr, m_array[index].m_type);
320 prev_addr = line_addr;
321 }
322
323 // update the address to be the last address prefetched
324 mystream->m_address = line_addr;
325}
326
327PrefetchEntry *
319 }
320
321 // update the address to be the last address prefetched
322 mystream->m_address = line_addr;
323}
324
325PrefetchEntry *
328Prefetcher::getPrefetchEntry(const Address &address, uint32_t &index)
326Prefetcher::getPrefetchEntry(Addr address, uint32_t &index)
329{
330 // search all streams for a match
331 for (int i = 0; i < m_num_streams; i++) {
332 // search all the outstanding prefetches for this stream
333 if (m_array[i].m_is_valid) {
334 for (int j = 0; j < m_num_startup_pfs; j++) {
327{
328 // search all streams for a match
329 for (int i = 0; i < m_num_streams; i++) {
330 // search all the outstanding prefetches for this stream
331 if (m_array[i].m_is_valid) {
332 for (int j = 0; j < m_num_startup_pfs; j++) {
335 if (next_stride_address(m_array[i].m_address,
333 if (makeNextStrideAddress(m_array[i].m_address,
336 -(m_array[i].m_stride*j)) == address) {
337 return &(m_array[i]);
338 }
339 }
340 }
341 }
342 return NULL;
343}
344
345bool
334 -(m_array[i].m_stride*j)) == address) {
335 return &(m_array[i]);
336 }
337 }
338 }
339 }
340 return NULL;
341}
342
343bool
346Prefetcher::accessUnitFilter(std::vector<Address>& filter_table,
347 uint32_t *filter_hit, uint32_t &index, const Address &address,
344Prefetcher::accessUnitFilter(std::vector& filter_table,
345 uint32_t *filter_hit, uint32_t &index, Addr address,
348 int stride, bool &alloc)
349{
350 //reset the alloc flag
351 alloc = false;
352
346 int stride, bool &alloc)
347{
348 //reset the alloc flag
349 alloc = false;
350
353 Address line_addr = line_address(address);
351 Addr line_addr = makeLineAddress(address);
354 for (int i = 0; i < m_num_unit_filters; i++) {
355 if (filter_table[i] == line_addr) {
352 for (int i = 0; i < m_num_unit_filters; i++) {
353 if (filter_table[i] == line_addr) {
356 filter_table[i] = next_stride_address(filter_table[i], stride);
354 filter_table[i] = makeNextStrideAddress(filter_table[i], stride);
357 filter_hit[i]++;
358 if (filter_hit[i] >= m_train_misses) {
359 alloc = true;
360 }
361 return true;
362 }
363 }
364
365 // enter this address in the table
366 int local_index = index;
355 filter_hit[i]++;
356 if (filter_hit[i] >= m_train_misses) {
357 alloc = true;
358 }
359 return true;
360 }
361 }
362
363 // enter this address in the table
364 int local_index = index;
367 filter_table[local_index] = next_stride_address(line_addr, stride);
365 filter_table[local_index] = makeNextStrideAddress(line_addr, stride);
368 filter_hit[local_index] = 0;
369 local_index = local_index + 1;
370 if (local_index >= m_num_unit_filters) {
371 local_index = 0;
372 }
373
374 index = local_index;
375 return false;
376}
377
378bool
366 filter_hit[local_index] = 0;
367 local_index = local_index + 1;
368 if (local_index >= m_num_unit_filters) {
369 local_index = 0;
370 }
371
372 index = local_index;
373 return false;
374}
375
376bool
379Prefetcher::accessNonunitFilter(const Address& address, int *stride,
377Prefetcher::accessNonunitFilter(Addr address, int *stride,
380 bool &alloc)
381{
382 //reset the alloc flag
383 alloc = false;
384
385 /// look for non-unit strides based on a (user-defined) page size
378 bool &alloc)
379{
380 //reset the alloc flag
381 alloc = false;
382
383 /// look for non-unit strides based on a (user-defined) page size
386 Address page_addr = pageAddress(address);
387 Address line_addr = line_address(address);
384 Addr page_addr = pageAddress(address);
385 Addr line_addr = makeLineAddress(address);
388
389 for (uint32_t i = 0; i < m_num_nonunit_filters; i++) {
390 if (pageAddress(m_nonunit_filter[i]) == page_addr) {
391 // hit in the non-unit filter
392 // compute the actual stride (for this reference)
386
387 for (uint32_t i = 0; i < m_num_nonunit_filters; i++) {
388 if (pageAddress(m_nonunit_filter[i]) == page_addr) {
389 // hit in the non-unit filter
390 // compute the actual stride (for this reference)
393 int delta = line_addr.getAddress() - m_nonunit_filter[i].getAddress();
391 int delta = line_addr - m_nonunit_filter[i];
394
395 if (delta != 0) {
396 // no zero stride prefetches
397 // check that the stride matches (for the last N times)
398 if (delta == m_nonunit_stride[i]) {
399 // -> stride hit
400 // increment count (if > 2) allocate stream
401 m_nonunit_hit[i]++;
402 if (m_nonunit_hit[i] > m_train_misses) {
392
393 if (delta != 0) {
394 // no zero stride prefetches
395 // check that the stride matches (for the last N times)
396 if (delta == m_nonunit_stride[i]) {
397 // -> stride hit
398 // increment count (if > 2) allocate stream
399 m_nonunit_hit[i]++;
400 if (m_nonunit_hit[i] > m_train_misses) {
403 //This stride HAS to be the multiplicative constant of
404 //dataBlockBytes (bc next_stride_address is calculated based
405 //on this multiplicative constant!)
406 *stride = m_nonunit_stride[i]/RubySystem::getBlockSizeBytes();
401 // This stride HAS to be the multiplicative constant of
402 // dataBlockBytes (bc makeNextStrideAddress is
403 // calculated based on this multiplicative constant!)
404 *stride = m_nonunit_stride[i] /
405 RubySystem::getBlockSizeBytes();
407
408 // clear this filter entry
409 clearNonunitEntry(i);
410 alloc = true;
411 }
412 } else {
406
407 // clear this filter entry
408 clearNonunitEntry(i);
409 alloc = true;
410 }
411 } else {
413 // delta didn't match ... reset m_nonunit_hit count for this entry
412 // delta didn't match ... reset m_nonunit_hit count for
413 // this entry
414 m_nonunit_hit[i] = 0;
415 }
416
417 // update the last address seen & the stride
418 m_nonunit_stride[i] = delta;
419 m_nonunit_filter[i] = line_addr;
420 return true;
421 } else {

--- 42 unchanged lines hidden (view full) ---

464 for (int i = 0; i < m_num_streams; i++) {
465 out << m_array[i].m_address << " "
466 << m_array[i].m_stride << " "
467 << m_array[i].m_is_valid << " "
468 << m_array[i].m_use_time << std::endl;
469 }
470}
471
414 m_nonunit_hit[i] = 0;
415 }
416
417 // update the last address seen & the stride
418 m_nonunit_stride[i] = delta;
419 m_nonunit_filter[i] = line_addr;
420 return true;
421 } else {

--- 42 unchanged lines hidden (view full) ---

464 for (int i = 0; i < m_num_streams; i++) {
465 out << m_array[i].m_address << " "
466 << m_array[i].m_stride << " "
467 << m_array[i].m_is_valid << " "
468 << m_array[i].m_use_time << std::endl;
469 }
470}
471
472Address
473Prefetcher::pageAddress(const Address& addr) const
472Addr
473Prefetcher::pageAddress(Addr addr) const
474{
474{
475 Address temp = addr;
476 temp.maskLowOrderBits(m_page_shift);
477 return temp;
475 return maskLowOrderBits(addr, m_page_shift);
478}
476}