Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
block_scheduler< SwappableBlockType > Class Template Reference

Detailed Description

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

Definition at line 265 of file block_scheduler.hpp.

+ Collaboration diagram for block_scheduler< SwappableBlockType >:

#include <block_scheduler.hpp>

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
}
 
using external_block_type = typename SwappableBlockType::external_block_type
 
using internal_block_type = typename SwappableBlockType::internal_block_type
 
using prediction_sequence_type = std::list< prediction_sequence_element >
 
using swappable_block_identifier_type = typename std::vector< SwappableBlockType >::size_type
 

Public Member Functions

 block_scheduler (const size_t max_internal_memory)
 
 block_scheduler (const block_scheduler &)=delete
 non-copyable: delete copy-constructor More...
 
 ~block_scheduler ()
 
internal_block_typeacquire (const swappable_block_identifier_type sbid, const bool uninitialized=false)
 
swappable_block_identifier_type allocate_swappable_block ()
 
void deinitialize (const swappable_block_identifier_type sbid)
 Drop all data in the given block, freeing in- and external memory. More...
 
void explicit_timestep ()
 
external_block_type extract_external_block (const swappable_block_identifier_type sbid)
 
void flush ()
 
void free_swappable_block (const swappable_block_identifier_type sbid)
 
block_scheduler_algorithm
< SwappableBlockType > * 
get_current_algorithm () const
 Return the current algorithm. More...
 
internal_block_typeget_internal_block (const swappable_block_identifier_type sbid) const
 
const prediction_sequence_typeget_prediction_sequence () const
 
void initialize (const swappable_block_identifier_type sbid, external_block_type eblock)
 
bool is_initialized (const swappable_block_identifier_type sbid) const
 
bool is_simulating () const
 
block_scheduleroperator= (const block_scheduler &)=delete
 non-copyable: delete assignment operator More...
 
void release (const swappable_block_identifier_type sbid, const bool dirty)
 
block_scheduler_algorithm
< SwappableBlockType > * 
switch_algorithm_to (block_scheduler_algorithm< SwappableBlockType > *new_algo)
 

Protected Types

using time_type = size_t
 

Protected Member Functions

internal_block_typeget_free_internal_block ()
 
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_managerbm
 
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 size_t max_internal_blocks
 
size_t remaining_internal_blocks
 
std::vector< SwappableBlockType > swappable_blocks
 temporary blocks that will not be needed after algorithm termination. More...
 

Static Protected Attributes

static const size_t max_internal_blocks_alloc_at_once = 128
 

Static Private Attributes

static constexpr bool debug = false
 

Member Typedef Documentation

using external_block_type = typename SwappableBlockType::external_block_type

Definition at line 278 of file block_scheduler.hpp.

using internal_block_type = typename SwappableBlockType::internal_block_type

Definition at line 277 of file block_scheduler.hpp.

Definition at line 314 of file block_scheduler.hpp.

using swappable_block_identifier_type = typename std::vector<SwappableBlockType>::size_type

Definition at line 279 of file block_scheduler.hpp.

using time_type = size_t
protected

Definition at line 274 of file block_scheduler.hpp.

Member Enumeration Documentation

Enumerator
op_acquire 
op_acquire_uninitialized 
op_release 
op_release_dirty 
op_deinitialize 
op_initialize 
op_extract_external_block 

Definition at line 292 of file block_scheduler.hpp.

Constructor & Destructor Documentation

block_scheduler ( const size_t  max_internal_memory)
inlineexplicit

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 371 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

block_scheduler ( const block_scheduler< SwappableBlockType > &  )
delete

non-copyable: delete copy-constructor

Member Function Documentation

internal_block_type& 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 417 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

swappable_block_identifier_type allocate_swappable_block ( )
inline
void deinitialize ( const swappable_block_identifier_type  sbid)
inline

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

Definition at line 428 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

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

void 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 455 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

external_block_type 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 444 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

void free_swappable_block ( const swappable_block_identifier_type  sbid)
inline

Free given no longer used temporary swappable_block.

Parameters
sbidTemporary swappable_block to free.

Definition at line 486 of file block_scheduler.hpp.

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

block_scheduler_algorithm<SwappableBlockType>* get_current_algorithm ( ) const
inline

Return the current algorithm.

Definition at line 509 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

internal_block_type& 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
sbidSwappable block to access.

Definition at line 460 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::swappable_blocks.

const prediction_sequence_type& get_prediction_sequence ( ) const
inline

Get the prediction_sequence.

Returns
reference to the prediction_sequence

Definition at line 516 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

void 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 437 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

bool is_initialized ( const swappable_block_identifier_type  sbid) const
inline

check if the swappable_block is initialized.

Parameters
sbididentifier to the swappable_block
Returns
if the swappable_block is initialized

Definition at line 450 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

bool 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 494 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

block_scheduler& operator= ( const block_scheduler< SwappableBlockType > &  )
delete

non-copyable: delete assignment operator

void 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
sbidSwappable block to release.
dirtyIf the data has been changed, invalidating possible data in external storage.

Definition at line 424 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo.

void return_free_internal_block ( internal_block_type iblock)
inlineprotected
block_scheduler_algorithm<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 500 of file block_scheduler.hpp.

References block_scheduler< SwappableBlockType >::algo, and block_scheduler_algorithm< SwappableBlockType >::bs.

Referenced by block_scheduler_algorithm_offline_lru_prefetching< SwappableBlockType >::give_up(), and block_scheduler_algorithm_offline_lfd< SwappableBlockType >::release().

Member Data Documentation

block_manager* bm
protected

Definition at line 332 of file block_scheduler.hpp.

constexpr bool debug = false
staticprivate

Definition at line 267 of file block_scheduler.hpp.

std::priority_queue<swappable_block_identifier_type, std::vector<swappable_block_identifier_type>, std::greater<swappable_block_identifier_type> > free_swappable_blocks
protected
std::stack<internal_block_type*> internal_blocks_blocks
protected

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

Definition at line 324 of file block_scheduler.hpp.

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

const size_t max_internal_blocks
protected
const size_t max_internal_blocks_alloc_at_once = 128
staticprotected
size_t remaining_internal_blocks
protected
std::vector<SwappableBlockType> swappable_blocks
mutableprotected

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