Stxxl  1.4.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
Classes | Public Types | Public Member Functions | Protected Types | Protected Member Functions | Protected Attributes | Static Protected Attributes
stxxl::block_scheduler< SwappableBlockType > Class Template Reference

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

#include <block_scheduler.h>

Inheritance diagram for stxxl::block_scheduler< SwappableBlockType >:
Inheritance graph
[legend]
Collaboration diagram for stxxl::block_scheduler< SwappableBlockType >:
Collaboration graph
[legend]

List of all members.

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::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.
 ~block_scheduler ()
internal_block_typeacquire (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_typeget_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_typeget_prediction_sequence () const
 get the prediction_sequence
void flush ()

Protected Types

typedef int_type time_type

Protected Member Functions

internal_block_typeget_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_managerbm
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 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:
SwappableBlockTypeType of swappable_blocks to manage. Can be some specialized subclass.
Examples:
containers/test_matrix.cpp.

Definition at line 246 of file block_scheduler.h.


Member Typedef Documentation

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

Definition at line 257 of file block_scheduler.h.

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

Definition at line 256 of file block_scheduler.h.

template<class SwappableBlockType >
typedef std::deque<prediction_sequence_element> stxxl::block_scheduler< SwappableBlockType >::prediction_sequence_type

Definition at line 294 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 258 of file block_scheduler.h.

template<class SwappableBlockType >
typedef int_type stxxl::block_scheduler< SwappableBlockType >::time_type [protected]

Definition at line 253 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 271 of file block_scheduler.h.


Constructor & Destructor Documentation

template<class SwappableBlockType >
stxxl::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_memoryAmount of internal memory (in bytes) the scheduler is allowed to use for acquiring, prefetching and caching.

Definition at line 350 of file block_scheduler.h.

template<class SwappableBlockType >
stxxl::block_scheduler< SwappableBlockType >::~block_scheduler ( ) [inline]

Definition at line 357 of file block_scheduler.h.


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]
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 431 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 395 of file block_scheduler.h.

Referenced by stxxl::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 421 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:
sbididentifier to the swappable_block
Returns:
external_block a.k.a. bid

Definition at line 410 of file block_scheduler.h.

template<class SwappableBlockType >
void stxxl::block_scheduler< SwappableBlockType >::flush ( ) [inline]

Definition at line 479 of file block_scheduler.h.

References stxxl::request_ptr::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:
sblockTemporary swappable_block to free.

Definition at line 452 of file block_scheduler.h.

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

Definition at line 316 of file block_scheduler.h.

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:
sblockSwappable block to access.

Definition at line 426 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 476 of file block_scheduler.h.

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

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:
sbididentifier to the swappable_block
eblockexternal_block a.k.a. bid

Definition at line 403 of file block_scheduler.h.

template<class SwappableBlockType >
bool stxxl::block_scheduler< SwappableBlockType >::is_initialized ( const swappable_block_identifier_type  sbid) const [inline]
template<class SwappableBlockType >
bool stxxl::block_scheduler< SwappableBlockType >::is_simulating ( ) const [inline]
template<class SwappableBlockType >
void stxxl::block_scheduler< SwappableBlockType >::release ( const swappable_block_identifier_type  sbid,
const bool  dirty 
) [inline]
template<class SwappableBlockType >
void stxxl::block_scheduler< SwappableBlockType >::return_free_internal_block ( internal_block_type iblock) [inline, protected]

Return an internal_block to the freelist.

Definition at line 344 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_algoPointer 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 466 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 312 of file block_scheduler.h.

template<class SwappableBlockType >
block_manager* stxxl::block_scheduler< SwappableBlockType >::bm [protected]

Definition at line 311 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 305 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 310 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 303 of file block_scheduler.h.

template<class SwappableBlockType >
const int_type stxxl::block_scheduler< SwappableBlockType >::max_internal_blocks [protected]

Definition at line 300 of file block_scheduler.h.

template<class SwappableBlockType >
const int_type stxxl::block_scheduler< SwappableBlockType >::max_internal_blocks_alloc_at_once = 128 [static, protected]

Definition at line 251 of file block_scheduler.h.

template<class SwappableBlockType >
int_type stxxl::block_scheduler< SwappableBlockType >::remaining_internal_blocks [protected]

Definition at line 301 of file block_scheduler.h.

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

temporary blocks that will not be needed after algorithm termination

Definition at line 307 of file block_scheduler.h.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines