stxxl::block_scheduler< SwappableBlockType > Class Template Reference

Detailed Description

template<class SwappableBlockType>
class stxxl::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:

examples/containers/matrix1.cpp.

Definition at line 250 of file block_scheduler.h.

Inheritance diagram for stxxl::block_scheduler< SwappableBlockType >:

Collaboration diagram for stxxl::block_scheduler< SwappableBlockType >:

Classes
struct	prediction_sequence_element

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::external_block_type	external_block_type
typedef SwappableBlockType::internal_block_type	internal_block_type
typedef std::list < prediction_sequence_element >	prediction_sequence_type
typedef std::vector < SwappableBlockType > ::size_type	swappable_block_identifier_type

Public Member Functions
	block_scheduler (const int_type max_internal_memory)
	Create a block_scheduler with empty prediction sequence in simple mode. More...
	~block_scheduler ()
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. More...
swappable_block_identifier_type	allocate_swappable_block ()
	Allocate an uninitialized swappable_block. More...
void	deinitialize (const swappable_block_identifier_type sbid)
	Drop all data in the given block, freeing in- and external memory. More...
void	explicit_timestep ()
	Record a timestep in the prediction sequence to seperate consecutive acquire rsp. release-operations. Has an effect only in simulation mode. More...
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. More...
void	flush ()
void	free_swappable_block (const swappable_block_identifier_type sbid)
	Free given no longer used temporary swappable_block. More...
block_scheduler_algorithm < SwappableBlockType > *	get_current_algorithm () const
	Return the current algorithm. More...
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. More...
const prediction_sequence_type &	get_prediction_sequence () const
	Get the prediction_sequence. More...
void	initialize (const swappable_block_identifier_type sbid, external_block_type eblock)
	Initialize the swappable_block with the given external_block. More...
bool	is_initialized (const swappable_block_identifier_type sbid) const
	check if the swappable_block is initialized. More...
bool	is_simulating () const
	Returns if simulation mode is on, i.e. if a prediction sequence is being recorded. More...
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. More...
block_scheduler_algorithm < SwappableBlockType > *	switch_algorithm_to (block_scheduler_algorithm< SwappableBlockType > *new_algo)
	Switch the used algorithm, e.g. to simulation etc.. More...

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. More...
void	return_free_internal_block (internal_block_type *iblock)
	Return an internal_block to the freelist. More...

Protected Attributes
block_scheduler_algorithm < SwappableBlockType > *	algo
block_manager *	bm
std::stack< internal_block_type * >	free_internal_blocks
	holds free internal_blocks with attributes reset. More...
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. More...
std::stack< internal_block_type * >	internal_blocks_blocks
	Stores pointers to arrays of internal_blocks. Used to deallocate them only. More...
const int_type	max_internal_blocks
int_type	remaining_internal_blocks
std::vector< SwappableBlockType >	swappable_blocks
	temporary blocks that will not be needed after algorithm termination. More...

Static Protected Attributes
static const int_type	max_internal_blocks_alloc_at_once = 128

Additional Inherited Members
Private Member Functions inherited from stxxl::noncopyable
	noncopyable ()

Member Typedef Documentation

template<class SwappableBlockType >

typedef SwappableBlockType::external_block_type stxxl::block_scheduler< SwappableBlockType >::external_block_type

Definition at line 261 of file block_scheduler.h.

template<class SwappableBlockType >

typedef SwappableBlockType::internal_block_type stxxl::block_scheduler< SwappableBlockType >::internal_block_type

Definition at line 260 of file block_scheduler.h.

template<class SwappableBlockType >

typedef std::list<prediction_sequence_element> stxxl::block_scheduler< SwappableBlockType >::prediction_sequence_type

Definition at line 297 of file block_scheduler.h.

template<class SwappableBlockType >

typedef std::vector<SwappableBlockType>::size_type stxxl::block_scheduler< SwappableBlockType >::swappable_block_identifier_type

Definition at line 262 of file block_scheduler.h.

template<class SwappableBlockType >

typedef int_type stxxl::block_scheduler< SwappableBlockType >::time_type

protected

Definition at line 257 of file block_scheduler.h.

Member Enumeration Documentation

template<class SwappableBlockType >

enum stxxl::block_scheduler::block_scheduler_operation

Enumerator
op_acquire
op_acquire_uninitialized
op_release
op_release_dirty
op_deinitialize
op_initialize
op_extract_external_block

Definition at line 275 of file block_scheduler.h.

Constructor & Destructor Documentation

template<class SwappableBlockType >

stxxl::block_scheduler< SwappableBlockType >::block_scheduler ( const int_type  max_internal_memory )

inlineexplicit

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.

Definition at line 354 of file block_scheduler.h.

template<class SwappableBlockType >

stxxl::block_scheduler< SwappableBlockType >::~block_scheduler ( )

inline

Definition at line 363 of file block_scheduler.h.

References STXXL_ERRMSG.

Member Function Documentation

template<class SwappableBlockType >

internal_block_type& stxxl::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. param sbid Swappable block to acquire.

Definition at line 395 of file block_scheduler.h.

Referenced by stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::element_op_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_col_vector_multiply_and_add_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_from_vectors_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_row_vector_multiply_and_add_swappable_block(), and stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::multiply_and_add_swappable_block().

template<class SwappableBlockType >

swappable_block_identifier_type stxxl::block_scheduler< SwappableBlockType >::allocate_swappable_block ( )

inline

Allocate an uninitialized swappable_block.

Returns

An identifier of the block.

Definition at line 443 of file block_scheduler.h.

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

template<class SwappableBlockType >

void stxxl::block_scheduler< SwappableBlockType >::deinitialize ( const swappable_block_identifier_type  sbid )

inline

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

Definition at line 406 of file block_scheduler.h.

Referenced by stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::element_op_swappable_block().

template<class SwappableBlockType >

void stxxl::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.

Definition at line 433 of file block_scheduler.h.

template<class SwappableBlockType >

external_block_type stxxl::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

Definition at line 422 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::block_scheduler< SwappableBlockType >::flush ( )

inline

Definition at line 497 of file block_scheduler.h.

References stxxl::counting_ptr< Type >::valid().

template<class SwappableBlockType >

void stxxl::block_scheduler< SwappableBlockType >::free_swappable_block ( const swappable_block_identifier_type  sbid )

inline

Free given no longer used temporary swappable_block.

Parameters

sbid	Temporary swappable_block to free.

Definition at line 464 of file block_scheduler.h.

template<class SwappableBlockType >

block_scheduler_algorithm<SwappableBlockType>* stxxl::block_scheduler< SwappableBlockType >::get_current_algorithm ( ) const

inline

Return the current algorithm.

Definition at line 487 of file block_scheduler.h.

template<class SwappableBlockType >

internal_block_type* stxxl::block_scheduler< SwappableBlockType >::get_free_internal_block ( )

inlineprotected

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

Returns

Pointer to the internal_block. NULL if none available.

Definition at line 320 of file block_scheduler.h.

References min().

template<class SwappableBlockType >

internal_block_type& stxxl::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

sbid	Swappable block to access.

Definition at line 438 of file block_scheduler.h.

template<class SwappableBlockType >

const prediction_sequence_type& stxxl::block_scheduler< SwappableBlockType >::get_prediction_sequence ( ) const

inline

Get the prediction_sequence.

Returns

reference to the prediction_sequence

Definition at line 494 of file block_scheduler.h.

template<class SwappableBlockType >

void stxxl::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

Definition at line 415 of file block_scheduler.h.

template<class SwappableBlockType >

bool stxxl::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

Definition at line 428 of file block_scheduler.h.

Referenced by stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::element_op_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_col_vector_multiply_and_add_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_row_vector_multiply_and_add_swappable_block(), and stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::multiply_and_add_swappable_block().

template<class SwappableBlockType >

bool stxxl::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.

Definition at line 472 of file block_scheduler.h.

Referenced by stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::element_op_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_col_vector_multiply_and_add_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_from_vectors_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_row_vector_multiply_and_add_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::multiply_and_add_swappable_block(), and stxxl::matrix< ValueType, BlockSideLength >::multiply_internal().

template<class SwappableBlockType >

void stxxl::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

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

Definition at line 402 of file block_scheduler.h.

Referenced by stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::element_op_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_col_vector_multiply_and_add_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_from_vectors_swappable_block(), stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::matrix_row_vector_multiply_and_add_swappable_block(), and stxxl::matrix_local::matrix_operations< ValueType, BlockSideLength >::multiply_and_add_swappable_block().

template<class SwappableBlockType >

void stxxl::block_scheduler< SwappableBlockType >::return_free_internal_block ( internal_block_type *  iblock )

inlineprotected

Return an internal_block to the freelist.

Definition at line 348 of file block_scheduler.h.

template<class SwappableBlockType >

block_scheduler_algorithm<SwappableBlockType>* stxxl::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.

Definition at line 478 of file block_scheduler.h.

References stxxl::block_scheduler_algorithm< SwappableBlockType >::bs.

Member Data Documentation

template<class SwappableBlockType >

block_scheduler_algorithm<SwappableBlockType>* stxxl::block_scheduler< SwappableBlockType >::algo

protected

Definition at line 316 of file block_scheduler.h.

template<class SwappableBlockType >

block_manager* stxxl::block_scheduler< SwappableBlockType >::bm

protected

Definition at line 315 of file block_scheduler.h.

template<class SwappableBlockType >

std::stack<internal_block_type*> stxxl::block_scheduler< SwappableBlockType >::free_internal_blocks

protected

holds free internal_blocks with attributes reset.

Definition at line 309 of file block_scheduler.h.

template<class SwappableBlockType >

std::priority_queue<swappable_block_identifier_type, std::vector<swappable_block_identifier_type>, std::greater<swappable_block_identifier_type> > stxxl::block_scheduler< SwappableBlockType >::free_swappable_blocks

protected

holds indices of free swappable_blocks with attributes reset.

Definition at line 314 of file block_scheduler.h.

template<class SwappableBlockType >

std::stack<internal_block_type*> stxxl::block_scheduler< SwappableBlockType >::internal_blocks_blocks

protected

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

Definition at line 307 of file block_scheduler.h.

template<class SwappableBlockType >

const int_type stxxl::block_scheduler< SwappableBlockType >::max_internal_blocks

protected

Definition at line 304 of file block_scheduler.h.

template<class SwappableBlockType >

const int_type stxxl::block_scheduler< SwappableBlockType >::max_internal_blocks_alloc_at_once = 128

staticprotected

Definition at line 255 of file block_scheduler.h.

template<class SwappableBlockType >

int_type stxxl::block_scheduler< SwappableBlockType >::remaining_internal_blocks

protected

Definition at line 305 of file block_scheduler.h.

template<class SwappableBlockType >

std::vector<SwappableBlockType> stxxl::block_scheduler< SwappableBlockType >::swappable_blocks

mutableprotected

temporary blocks that will not be needed after algorithm termination.

Definition at line 311 of file block_scheduler.h.

---

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

• include/stxxl/bits/mng/block_scheduler.h