Schedules swapping of blocks and provides blocks for temporary storage. More...

#include <block_scheduler.h>

Inherits noncopyable.

Collaboration diagram for block_scheduler< SwappableBlockType >:

Public Types
enum	block_scheduler_operation { op_acquire, op_acquire_uninitialized, op_release, op_release_dirty, op_deinitialize, op_initialize, op_extract_external_block }
typedef SwappableBlockType::internal_block_type	internal_block_type
typedef SwappableBlockType::external_block_type	external_block_type
typedef std::vector < SwappableBlockType > ::size_type	swappable_block_identifier_type
typedef std::deque < prediction_sequence_element >	prediction_sequence_type
Public Member Functions
	block_scheduler (const int_type max_internal_memory)
	create a block_scheduler with empty prediction sequence in simple mode.
internal_block_type &	acquire (const swappable_block_identifier_type sbid, const bool uninitialized=false)
	Acquire the given block. Has to be in pairs with release. Pairs may be nested and interleaved.
void	release (const swappable_block_identifier_type sbid, const bool dirty)
	Release the given block. Has to be in pairs with acquire. Pairs may be nested and interleaved.
void	deinitialize (const swappable_block_identifier_type sbid)
	Drop all data in the given block, freeing in- and external memory.
void	initialize (const swappable_block_identifier_type sbid, external_block_type eblock)
	Initialize the swappable_block with the given external_block.
external_block_type	extract_external_block (const swappable_block_identifier_type sbid)
	deinitialize the swappable_block and return it's contents in an external_block.
bool	is_initialized (const swappable_block_identifier_type sbid) const
	check if the swappable_block is initialized
void	explicit_timestep ()
	Record a timestep in the prediction sequence to seperate consecutive acquire rsp. release-operations. Has an effect only in simulation mode.
internal_block_type &	get_internal_block (const swappable_block_identifier_type sbid) const
	Get a const reference to given block's data. Block has to be already acquired.
swappable_block_identifier_type	allocate_swappable_block ()
	Allocate an uninitialized swappable_block.
void	free_swappable_block (const swappable_block_identifier_type sbid)
	Free given no longer used temporary swappable_block.
bool	is_simulating () const
	Returns if simulation mode is on, i.e. if a prediction sequence is being recorded.
block_scheduler_algorithm < SwappableBlockType > *	switch_algorithm_to (block_scheduler_algorithm< SwappableBlockType > *new_algo)
	Switch the used algorithm, e.g. to simulation etc..
const prediction_sequence_type &	get_prediction_sequence () const
	get the prediction_sequence
void	flush ()
Protected Types
typedef int_type	time_type
Protected Member Functions
internal_block_type *	get_free_internal_block ()
	Get an internal_block from the freelist or a newly allocated one if available.
void	return_free_internal_block (internal_block_type *iblock)
	Return an internal_block to the freelist.
Protected Attributes
const int_type	max_internal_blocks
int_type	remaining_internal_blocks
std::stack< internal_block_type * >	internal_blocks_blocks
	Stores pointers to arrays of internal_blocks. Used to deallocate them only.
std::stack< internal_block_type * >	free_internal_blocks
	holds free internal_blocks with attributes reset
std::vector< SwappableBlockType >	swappable_blocks
	temporary blocks that will not be needed after algorithm termination
std::priority_queue < swappable_block_identifier_type, std::vector < swappable_block_identifier_type > , std::greater < swappable_block_identifier_type > >	free_swappable_blocks
	holds indices of free swappable_blocks with attributes reset
block_manager *	bm
block_scheduler_algorithm < SwappableBlockType > *	algo
Static Protected Attributes
static const int_type	max_internal_blocks_alloc_at_once = 128

Detailed Description

template<class SwappableBlockType>
class block_scheduler< SwappableBlockType >

Schedules swapping of blocks and provides blocks for temporary storage.

In simple mode, it tries to save I/Os through caching only. In simulation mode, it records access patterns into a prediction sequence. The prediction sequence can then be used for prefetching in the (offline) execute mode. This will only work for algorithms with deterministic, data oblivious access patterns. In simulation mode, no I/O is performed; the data provided is accessible but undefined. In execute mode, it does caching, prefetching, and possibly other optimizations.

Template Parameters:

SwappableBlockType

Type of swappable_blocks to manage. Can be some specialized subclass.

Examples:: containers/test_matrix.cpp.

Constructor & Destructor Documentation

template<class SwappableBlockType >

block_scheduler< SwappableBlockType >::block_scheduler ( const int_type max_internal_memory ) [inline, explicit]

create a block_scheduler with empty prediction sequence in simple mode.

Parameters:

max_internal_memory

Amount of internal memory (in bytes) the scheduler is allowed to use for acquiring, prefetching and caching.

Member Function Documentation

template<class SwappableBlockType >

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

Acquire the given block. Has to be in pairs with release. Pairs may be nested and interleaved.

Returns:: Reference to the block's data.

Parameters:

sblock

Swappable block to acquire.

template<class SwappableBlockType >

swappable_block_identifier_type block_scheduler< SwappableBlockType >::allocate_swappable_block ( ) [inline]

Allocate an uninitialized swappable_block.

Returns:: An identifier of the block.

References block_scheduler< SwappableBlockType >::free_swappable_blocks, and block_scheduler< SwappableBlockType >::swappable_blocks.

Referenced by swappable_block_matrix< ValueType, BlockSideLength >::swappable_block_matrix().

template<class SwappableBlockType >

void block_scheduler< SwappableBlockType >::deinitialize ( const swappable_block_identifier_type sbid ) [inline]

Drop all data in the given block, freeing in- and external memory.

Referenced by block_scheduler< SwappableBlockType >::free_swappable_block().

template<class SwappableBlockType >

void block_scheduler< SwappableBlockType >::explicit_timestep ( ) [inline]

Record a timestep in the prediction sequence to seperate consecutive acquire rsp. release-operations. Has an effect only in simulation mode.

template<class SwappableBlockType >

external_block_type block_scheduler< SwappableBlockType >::extract_external_block ( const swappable_block_identifier_type sbid ) [inline]

deinitialize the swappable_block and return it's contents in an external_block.

Parameters:

sbid

identifier to the swappable_block

Returns:: external_block a.k.a. bid

template<class SwappableBlockType >

void block_scheduler< SwappableBlockType >::free_swappable_block ( const swappable_block_identifier_type sbid ) [inline]

Free given no longer used temporary swappable_block.

Parameters:

sblock

Temporary swappable_block to free.

References block_scheduler< SwappableBlockType >::deinitialize(), and block_scheduler< SwappableBlockType >::free_swappable_blocks.

template<class SwappableBlockType >

internal_block_type* block_scheduler< SwappableBlockType >::get_free_internal_block ( ) [inline, protected]

Get an internal_block from the freelist or a newly allocated one if available.

Returns:: Pointer to the internal_block. NULL if none available.

References block_scheduler< SwappableBlockType >::free_internal_blocks, and block_scheduler< SwappableBlockType >::internal_blocks_blocks.

Referenced by block_scheduler_algorithm< SwappableBlockType >::get_free_internal_block_from_block_scheduler().

template<class SwappableBlockType >

internal_block_type& block_scheduler< SwappableBlockType >::get_internal_block ( const swappable_block_identifier_type sbid ) const [inline]

Get a const reference to given block's data. Block has to be already acquired.

Parameters:

sblock

Swappable block to access.

References block_scheduler< SwappableBlockType >::swappable_blocks.

template<class SwappableBlockType >

const prediction_sequence_type& block_scheduler< SwappableBlockType >::get_prediction_sequence ( ) const [inline]

get the prediction_sequence

Returns:: reference to the prediction_sequence

template<class SwappableBlockType >

void block_scheduler< SwappableBlockType >::initialize	(	const swappable_block_identifier_type	sbid,
		external_block_type	eblock
	)			`[inline]`

Initialize the swappable_block with the given external_block.

It will use the the external_block for swapping and take care about it's deallocation. Has to be uninitialized.

Parameters:

	sbid	identifier to the swappable_block
	eblock	external_block a.k.a. bid

template<class SwappableBlockType >

bool block_scheduler< SwappableBlockType >::is_initialized ( const swappable_block_identifier_type sbid ) const [inline]

check if the swappable_block is initialized

Parameters:

sbid

identifier to the swappable_block

Returns:: if the swappable_block is initialized

template<class SwappableBlockType >

bool block_scheduler< SwappableBlockType >::is_simulating ( ) const [inline]

Returns if simulation mode is on, i.e. if a prediction sequence is being recorded.

Returns:: If simulation mode is on.

template<class SwappableBlockType >

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

Release the given block. Has to be in pairs with acquire. Pairs may be nested and interleaved.

Parameters:

	sblock	Swappable block to release.
	dirty	If the data has been changed, invalidating possible data in external storage.

template<class SwappableBlockType >

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

Return an internal_block to the freelist.

References block_scheduler< SwappableBlockType >::free_internal_blocks.

Referenced by block_scheduler_algorithm< SwappableBlockType >::return_free_internal_block_to_block_scheduler().

template<class SwappableBlockType >

block_scheduler_algorithm<SwappableBlockType>* block_scheduler< SwappableBlockType >::switch_algorithm_to ( block_scheduler_algorithm< SwappableBlockType > * new_algo ) [inline]

Switch the used algorithm, e.g. to simulation etc..

Parameters:

new_algo

Pointer to the new algorithm object. Has to be instantiated to the block scheduler (or the old algorithm object).

Returns:: Pointer to the old algorithm object.

Member Data Documentation

template<class SwappableBlockType >

std::stack<internal_block_type * > block_scheduler< SwappableBlockType >::free_internal_blocks [protected]

holds free internal_blocks with attributes reset

Referenced by block_scheduler< SwappableBlockType >::get_free_internal_block(), and block_scheduler< SwappableBlockType >::return_free_internal_block().

template<class SwappableBlockType >

std::priority_queue<swappable_block_identifier_type, std::vector<swappable_block_identifier_type>, std::greater<swappable_block_identifier_type> > block_scheduler< SwappableBlockType >::free_swappable_blocks [protected]

holds indices of free swappable_blocks with attributes reset

Referenced by block_scheduler< SwappableBlockType >::allocate_swappable_block(), and block_scheduler< SwappableBlockType >::free_swappable_block().

template<class SwappableBlockType >

std::stack<internal_block_type *> block_scheduler< SwappableBlockType >::internal_blocks_blocks [protected]

Stores pointers to arrays of internal_blocks. Used to deallocate them only.

Referenced by block_scheduler< SwappableBlockType >::get_free_internal_block().

template<class SwappableBlockType >

std::vector<SwappableBlockType> block_scheduler< SwappableBlockType >::swappable_blocks [mutable, protected]

temporary blocks that will not be needed after algorithm termination

Referenced by block_scheduler< SwappableBlockType >::allocate_swappable_block(), and block_scheduler< SwappableBlockType >::get_internal_block().

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