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

SwappableBlockType Type 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_type &	acquire (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_type &	get_internal_block (const swappable_block_identifier_type sbid) const

const prediction_sequence_type &	get_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_scheduler &	operator= (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_type *	get_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_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 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

◆ external_block_type

using external_block_type = typename SwappableBlockType::external_block_type

Definition at line 278 of file block_scheduler.hpp.

◆ internal_block_type

using internal_block_type = typename SwappableBlockType::internal_block_type

Definition at line 277 of file block_scheduler.hpp.

◆ prediction_sequence_type

using prediction_sequence_type = std::list<prediction_sequence_element>

Definition at line 314 of file block_scheduler.hpp.

◆ swappable_block_identifier_type

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

Definition at line 279 of file block_scheduler.hpp.

◆ time_type

using time_type = size_t

protected

Definition at line 274 of file block_scheduler.hpp.

Member Enumeration Documentation

◆ block_scheduler_operation

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

Constructor & Destructor Documentation

◆ block_scheduler() [1/2]

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

◆ block_scheduler() [2/2]

block_scheduler ( const block_scheduler< SwappableBlockType > & )

delete

non-copyable: delete copy-constructor

◆ ~block_scheduler()

~block_scheduler ( )

inline

Definition at line 385 of file block_scheduler.hpp.

References TLX_LOG1.

Member Function Documentation

◆ acquire()

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_algorithm< SwappableBlockType >::acquire().

◆ allocate_swappable_block()

swappable_block_identifier_type allocate_swappable_block ( )

inline

Allocate an uninitialized swappable_block.

Returns: An identifier of the block.

Definition at line 465 of file block_scheduler.hpp.

References block_scheduler_algorithm< SwappableBlockType >::swappable_blocks_resize().

◆ deinitialize()

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_algorithm< SwappableBlockType >::deinitialize().

◆ explicit_timestep()

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_algorithm< SwappableBlockType >::explicit_timestep().

◆ extract_external_block()

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

sbid	identifier to the swappable_block

Returns: external_block a.k.a. bid

Definition at line 444 of file block_scheduler.hpp.

References block_scheduler_algorithm< SwappableBlockType >::extract_external_block().

◆ flush()

void flush ( )

inline

Definition at line 519 of file block_scheduler.hpp.

References swappable_block< ValueType, BlockSize >::detach_internal_block(), block_scheduler_algorithm< SwappableBlockType >::evictable_blocks_empty(), block_scheduler_algorithm< SwappableBlockType >::evictable_blocks_pop(), and CountingPtr< Type, Deleter >::valid().

◆ free_swappable_block()

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

References swappable_block< ValueType, BlockSize >::deinitialize().

◆ get_current_algorithm()

block_scheduler_algorithm<SwappableBlockType>* get_current_algorithm ( ) const

inline

Return the current algorithm.

Definition at line 509 of file block_scheduler.hpp.

◆ get_free_internal_block()

internal_block_type* 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. nullptr if none available.

Definition at line 337 of file block_scheduler.hpp.

References min().

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

◆ get_internal_block()

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

sbid	Swappable block to access.

Definition at line 460 of file block_scheduler.hpp.

◆ get_prediction_sequence()

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_algorithm< SwappableBlockType >::get_prediction_sequence().

◆ initialize()

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

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

Definition at line 437 of file block_scheduler.hpp.

References block_scheduler_algorithm< SwappableBlockType >::initialize().

◆ is_initialized()

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

References block_scheduler_algorithm< SwappableBlockType >::is_initialized().

◆ is_simulating()

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_algorithm< SwappableBlockType >::is_simulating().

◆ operator=()

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

delete

non-copyable: delete assignment operator

◆ release()

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

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

Definition at line 424 of file block_scheduler.hpp.

References block_scheduler_algorithm< SwappableBlockType >::release().

◆ return_free_internal_block()

void return_free_internal_block ( internal_block_type * iblock )

inlineprotected

Return an internal_block to the freelist.

Definition at line 365 of file block_scheduler.hpp.

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

◆ switch_algorithm_to()

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

References block_scheduler_algorithm< SwappableBlockType >::bs.

Member Data Documentation

◆ algo

block_scheduler_algorithm<SwappableBlockType>* algo

protected

Definition at line 333 of file block_scheduler.hpp.

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

◆ bm

block_manager* bm

protected

Definition at line 332 of file block_scheduler.hpp.

◆ debug

constexpr bool debug = false

staticprivate

Definition at line 267 of file block_scheduler.hpp.

◆ free_internal_blocks

std::stack<internal_block_type*> free_internal_blocks

protected

holds free internal_blocks with attributes reset.

Definition at line 326 of file block_scheduler.hpp.

◆ free_swappable_blocks

std::priority_queue<swappable_block_identifier_type, std::vector<swappable_block_identifier_type>, std::greater<swappable_block_identifier_type> > free_swappable_blocks

protected

holds indices of free swappable_blocks with attributes reset.

Definition at line 331 of file block_scheduler.hpp.

◆ internal_blocks_blocks

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.

◆ max_internal_blocks

const size_t max_internal_blocks

protected

Definition at line 321 of file block_scheduler.hpp.

◆ max_internal_blocks_alloc_at_once

const size_t max_internal_blocks_alloc_at_once = 128

staticprotected

Definition at line 272 of file block_scheduler.hpp.

◆ remaining_internal_blocks

size_t remaining_internal_blocks

protected

Definition at line 322 of file block_scheduler.hpp.

◆ swappable_blocks

std::vector<SwappableBlockType> swappable_blocks

mutableprotected

temporary blocks that will not be needed after algorithm termination.

Definition at line 328 of file block_scheduler.hpp.

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

extlib/foxxll/foxxll/mng/block_scheduler.hpp

Detailed Description

template<class SwappableBlockType> class foxxll::block_scheduler< SwappableBlockType >

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Static Private Attributes

Member Typedef Documentation

◆ external_block_type

◆ internal_block_type

◆ prediction_sequence_type

◆ swappable_block_identifier_type

◆ time_type

Member Enumeration Documentation

◆ block_scheduler_operation

Constructor & Destructor Documentation

◆ block_scheduler() [1/2]

◆ block_scheduler() [2/2]

◆ ~block_scheduler()

Member Function Documentation

◆ acquire()

◆ allocate_swappable_block()

◆ deinitialize()

◆ explicit_timestep()

◆ extract_external_block()

◆ flush()

◆ free_swappable_block()

◆ get_current_algorithm()

◆ get_free_internal_block()

◆ get_internal_block()

◆ get_prediction_sequence()

◆ initialize()

◆ is_initialized()

◆ is_simulating()

◆ operator=()

◆ release()

◆ return_free_internal_block()

◆ switch_algorithm_to()

Member Data Documentation

◆ algo

◆ bm

◆ debug

◆ free_internal_blocks

◆ free_swappable_blocks

◆ internal_blocks_blocks

◆ max_internal_blocks

◆ max_internal_blocks_alloc_at_once

◆ remaining_internal_blocks

◆ swappable_blocks

template<class SwappableBlockType>
class foxxll::block_scheduler< SwappableBlockType >