Block scheduling algorithm caching via the least recently used policy (offline), and prefetching in addition. More...

#include <block_scheduler.h>

Inheritance diagram for stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >:

Collaboration diagram for stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >:

Classes
struct	read_after_write
struct	scheduled_block_meta
struct	write_read_request
Public Member Functions
	block_scheduler_algorithm_offline_lru_prefetching (block_scheduler_type &bs)
	block_scheduler_algorithm_offline_lru_prefetching (block_scheduler_algorithm_type *old)
virtual	~block_scheduler_algorithm_offline_lru_prefetching ()
virtual bool	evictable_blocks_empty ()
virtual swappable_block_identifier_type	evictable_blocks_pop ()
virtual internal_block_type &	acquire (const swappable_block_identifier_type sbid, const bool uninitialized=false)
virtual void	release (swappable_block_identifier_type sbid, const bool dirty)
virtual void	deinitialize (swappable_block_identifier_type sbid)
virtual void	initialize (swappable_block_identifier_type sbid, external_block_type eblock)
virtual external_block_type	extract_external_block (swappable_block_identifier_type sbid)
Protected Types
typedef block_scheduler < SwappableBlockType >	block_scheduler_type
typedef block_scheduler_algorithm < SwappableBlockType >	block_scheduler_algorithm_type
typedef block_scheduler_type::internal_block_type	internal_block_type
typedef block_scheduler_type::external_block_type	external_block_type
typedef block_scheduler_type::swappable_block_identifier_type	swappable_block_identifier_type
typedef block_scheduler_algorithm_type::time_type	time_type
typedef block_scheduler_type::prediction_sequence_type	prediction_sequence_type
typedef block_scheduler_type::block_scheduler_operation	block_scheduler_operation
typedef std::vector < SwappableBlockType > ::iterator	swappable_blocks_iterator
typedef std::map < swappable_block_identifier_type, scheduled_block_meta >	scheduled_blocks_type
typedef scheduled_blocks_type::iterator	scheduled_blocks_iterator
typedef scheduled_blocks_type::reference	scheduled_blocks_reference
typedef std::map < swappable_block_identifier_type, write_read_request * >	write_scheduled_blocks_type
typedef write_scheduled_blocks_type::iterator	write_scheduled_blocks_iterator
typedef write_scheduled_blocks_type::reference	write_scheduled_blocks_reference
Protected Member Functions
write_read_request *	schedule_write (const swappable_block_identifier_type sbid)
	Schedule an internal, possibly dirty swappable_block to write.
bool	try_interrupt_read (const write_scheduled_blocks_iterator &writing_block)
	try to interrupt a read scheduled in a write_read_request
void	schedule_read (scheduled_blocks_iterator block_to_read)
	Schedule an internal and external block to read.
void	wait_on_write (const write_scheduled_blocks_iterator &writing_block)
	wait for the write to finish
void	wait_on_write (const swappable_block_identifier_type &writing_block)
	wait for the write to finish
void	wait_on_write (const scheduled_blocks_iterator &schedule_meta)
	wait for the write of the giver to finish
void	wait_on_read (const scheduled_blocks_iterator &schedule_meta)
	wait for the read to finish
internal_block_type *	get_ready_block (const scheduled_blocks_iterator &schedule_meta)
	wait for the write of the giver to finish and return reserved internal_block
bool	shall_keep_internal_block (const scheduled_blocks_iterator &schedule_meta, const bool ignore_first=true) const
bool	shall_be_cleaned (const scheduled_blocks_iterator &schedule_meta) const
bool	shall_be_read (const scheduled_blocks_iterator &schedule_meta, const bool ignore_first=true) const
void	operation_done (scheduled_blocks_iterator &schedule_meta)
block_scheduler_algorithm_type *	give_up (std::string err_msg="detected some error in the prediction sequence")
void	return_free_internal_block (internal_block_type *iblock)
void	schedule_next_operations ()
void	init (block_scheduler_algorithm_type *old_algo)
void	deinit ()
Protected Attributes
std::set < swappable_block_identifier_type >	free_evictable_blocks
	Holds swappable blocks, whose internal block can be freed, i.e. that are internal but unacquired.
std::set < swappable_block_identifier_type >	scheduled_evictable_blocks
scheduled_blocks_type	scheduled_blocks
	Holds not internal swappable_blocks, whose next access has already been scheduled.
write_scheduled_blocks_type	write_scheduled_blocks
	Holds swappable_blocks, whose internal block has been taken away but the clean did not finish yet.
prediction_sequence_type::iterator	next_op_to_schedule

Detailed Description

template<class SwappableBlockType>
class stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >

Block scheduling algorithm caching via the least recently used policy (offline), and prefetching in addition.

Definition at line 1091 of file block_scheduler.h.

Member Typedef Documentation

template<class SwappableBlockType >

typedef block_scheduler_algorithm<SwappableBlockType> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::block_scheduler_algorithm_type [protected]

Definition at line 1098 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_type::block_scheduler_operation stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::block_scheduler_operation [protected]

Definition at line 1104 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler<SwappableBlockType> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::block_scheduler_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1095 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_type::external_block_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::external_block_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1100 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_type::internal_block_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::internal_block_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1099 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_type::prediction_sequence_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::prediction_sequence_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1103 of file block_scheduler.h.

template<class SwappableBlockType >

typedef scheduled_blocks_type::iterator stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::scheduled_blocks_iterator [protected]

Definition at line 1108 of file block_scheduler.h.

template<class SwappableBlockType >

typedef scheduled_blocks_type::reference stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::scheduled_blocks_reference [protected]

Definition at line 1109 of file block_scheduler.h.

template<class SwappableBlockType >

typedef std::map<swappable_block_identifier_type, scheduled_block_meta> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::scheduled_blocks_type [protected]

Definition at line 1107 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_type::swappable_block_identifier_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::swappable_block_identifier_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1101 of file block_scheduler.h.

template<class SwappableBlockType >

typedef std::vector<SwappableBlockType>::iterator stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::swappable_blocks_iterator [protected]

Definition at line 1105 of file block_scheduler.h.

template<class SwappableBlockType >

typedef block_scheduler_algorithm_type::time_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::time_type [protected]

Reimplemented from stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1102 of file block_scheduler.h.

template<class SwappableBlockType >

typedef write_scheduled_blocks_type::iterator stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_scheduled_blocks_iterator [protected]

Definition at line 1111 of file block_scheduler.h.

template<class SwappableBlockType >

typedef write_scheduled_blocks_type::reference stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_scheduled_blocks_reference [protected]

Definition at line 1112 of file block_scheduler.h.

template<class SwappableBlockType >

typedef std::map<swappable_block_identifier_type, write_read_request *> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_scheduled_blocks_type [protected]

Definition at line 1110 of file block_scheduler.h.

Constructor & Destructor Documentation

template<class SwappableBlockType >

stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::block_scheduler_algorithm_offline_lru_prefetching ( block_scheduler_type & bs ) [inline]

Definition at line 1585 of file block_scheduler.h.

References init().

template<class SwappableBlockType >

stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::block_scheduler_algorithm_offline_lru_prefetching ( block_scheduler_algorithm_type * old ) [inline]

Definition at line 1590 of file block_scheduler.h.

References init().

template<class SwappableBlockType >

virtual stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::~block_scheduler_algorithm_offline_lru_prefetching ( ) [inline, virtual]

Definition at line 1594 of file block_scheduler.h.

References stxxl::pop_begin().

Member Function Documentation

template<class SwappableBlockType >

virtual internal_block_type& stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::acquire	(	const swappable_block_identifier_type	sbid,
		const bool	uninitialized = `false`
	)		`[inline, virtual]`

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1616 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::deinit ( ) [inline, protected]

Definition at line 1555 of file block_scheduler.h.

References STXXL_MSG.

template<class SwappableBlockType >

virtual void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::deinitialize ( swappable_block_identifier_type sbid ) [inline, virtual]

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1716 of file block_scheduler.h.

template<class SwappableBlockType >

virtual bool stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::evictable_blocks_empty ( ) [inline, virtual]

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1607 of file block_scheduler.h.

template<class SwappableBlockType >

virtual swappable_block_identifier_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::evictable_blocks_pop ( ) [inline, virtual]

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1613 of file block_scheduler.h.

References stxxl::pop_begin().

template<class SwappableBlockType >

virtual external_block_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::extract_external_block ( swappable_block_identifier_type sbid ) [inline, virtual]

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1780 of file block_scheduler.h.

template<class SwappableBlockType >

internal_block_type* stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::get_ready_block ( const scheduled_blocks_iterator & schedule_meta ) [inline, protected]

wait for the write of the giver to finish and return reserved internal_block

side-effect: erases entry for the write of the giver from write_scheduled_blocks

Definition at line 1377 of file block_scheduler.h.

template<class SwappableBlockType >

block_scheduler_algorithm_type* stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::give_up ( std::string err_msg = "detected some error in the prediction sequence" ) [inline, protected]

Definition at line 1449 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::init ( block_scheduler_algorithm_type * old_algo ) [inline, protected]

Definition at line 1543 of file block_scheduler.h.

References stxxl::block_scheduler_algorithm< SwappableBlockType >::get_prediction_sequence().

template<class SwappableBlockType >

virtual void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::initialize	(	swappable_block_identifier_type	sbid,
		external_block_type	eblock
	)		`[inline, virtual]`

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1758 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::operation_done ( scheduled_blocks_iterator & schedule_meta ) [inline, protected]

Definition at line 1439 of file block_scheduler.h.

template<class SwappableBlockType >

virtual void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::release	(	swappable_block_identifier_type	sbid,
		const bool	dirty
	)		`[inline, virtual]`

Implements stxxl::block_scheduler_algorithm< SwappableBlockType >.

Definition at line 1660 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::return_free_internal_block ( internal_block_type * iblock ) [inline, protected]

Definition at line 1460 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::schedule_next_operations ( ) [inline, protected]

Definition at line 1463 of file block_scheduler.h.

References stxxl::pop_begin(), and stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_read_request::taker.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::schedule_read ( scheduled_blocks_iterator block_to_read ) [inline, protected]

Schedule an internal and external block to read.

If the giver is still writing, schedule read via its write_read_request.

Definition at line 1222 of file block_scheduler.h.

References std::swap().

template<class SwappableBlockType >

write_read_request* stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::schedule_write ( const swappable_block_identifier_type sbid ) [inline, protected]

Schedule an internal, possibly dirty swappable_block to write.

The block becomes not dirty. if it was dirty, an entry in write_scheduled_blocks is made referencing the write_read_request.

Parameters:

sbid	block to write

Returns:: pointer to the write_read_request

Definition at line 1177 of file block_scheduler.h.

References stxxl::request_ptr::valid(), and stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_read_request::write_req.

template<class SwappableBlockType >

bool stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::shall_be_cleaned ( const scheduled_blocks_iterator & schedule_meta ) const [inline, protected]

Definition at line 1409 of file block_scheduler.h.

template<class SwappableBlockType >

bool stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::shall_be_read	(	const scheduled_blocks_iterator &	schedule_meta,
		const bool	ignore_first = `true`
	)		const `[inline, protected]`

Definition at line 1431 of file block_scheduler.h.

template<class SwappableBlockType >

bool stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::shall_keep_internal_block	(	const scheduled_blocks_iterator &	schedule_meta,
		const bool	ignore_first = `true`
	)		const `[inline, protected]`

Definition at line 1385 of file block_scheduler.h.

template<class SwappableBlockType >

bool stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::try_interrupt_read ( const write_scheduled_blocks_iterator & writing_block ) [inline, protected]

try to interrupt a read scheduled in a write_read_request

side-effect: possibly erases entry from write_scheduled_blocks, so the iterator writing_block may become invalid

Returns:: if successful

Definition at line 1199 of file block_scheduler.h.

References stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_read_request::shall_read.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::wait_on_read ( const scheduled_blocks_iterator & schedule_meta ) [inline, protected]

wait for the read to finish

side-effect: erases entry for the write of the giver from write_scheduled_blocks

Definition at line 1364 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::wait_on_write ( const write_scheduled_blocks_iterator & writing_block ) [inline, protected]

wait for the write to finish

side-effect: erases entry from write_scheduled_blocks

Definition at line 1332 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::wait_on_write ( const swappable_block_identifier_type & writing_block ) [inline, protected]

wait for the write to finish

side-effect: erases entry from write_scheduled_blocks

Definition at line 1342 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::wait_on_write ( const scheduled_blocks_iterator & schedule_meta ) [inline, protected]

wait for the write of the giver to finish

side-effect: erases entry from write_scheduled_blocks

Definition at line 1352 of file block_scheduler.h.

Member Data Documentation

template<class SwappableBlockType >

std::set<swappable_block_identifier_type> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::free_evictable_blocks [protected]

Holds swappable blocks, whose internal block can be freed, i.e. that are internal but unacquired.

Definition at line 1164 of file block_scheduler.h.

template<class SwappableBlockType >

prediction_sequence_type::iterator stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::next_op_to_schedule [protected]

Definition at line 1170 of file block_scheduler.h.

template<class SwappableBlockType >

scheduled_blocks_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::scheduled_blocks [protected]

Holds not internal swappable_blocks, whose next access has already been scheduled.

Definition at line 1167 of file block_scheduler.h.

template<class SwappableBlockType >

std::set<swappable_block_identifier_type> stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::scheduled_evictable_blocks [protected]

Definition at line 1165 of file block_scheduler.h.

template<class SwappableBlockType >

write_scheduled_blocks_type stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::write_scheduled_blocks [protected]

Holds swappable_blocks, whose internal block has been taken away but the clean did not finish yet.

Definition at line 1169 of file block_scheduler.h.

The documentation for this class was generated from the following file:

include/stxxl/bits/mng/block_scheduler.h

Classes

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class SwappableBlockType> class stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class SwappableBlockType>
class stxxl::block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >