MSTHeapCache Class Reference

A cache to maintain similarity/distance metrics to build a Minimum Spanning Tree (MST) using a heap. More...

#include <MSTHeapCache.h>

Inheritance diagram for MSTHeapCache:

[legend]

Collaboration diagram for MSTHeapCache:

[legend]

List of all members.

Public Member Functions
	MSTHeapCache (const int totalESTCount, const int startOwnESTidx, const int numOwnESTs, const ESTAnalyzer *analyzer, const bool repopulateCaches, const int maxCachePerEST)
	The constructor.
virtual	~MSTHeapCache ()
	The destructor.
virtual void	pruneCaches (const int estIdxAdded, std::vector< int > &repopulateList, const bool prefixListSize=true)
	Suggest to clear caches that contain entries for a newly added EST.
virtual void	mergeList (const int estIdx, const SMList &list)
	Add/merges a batch of new cache entries with the current entries in the cache for a given EST.
virtual void	getBestEntry (int &srcESTidx, int &destESTidx, float &metric, int &alignmentData, int &directionData) const
	Obtains the top-most similar entry from the MSTCache.
virtual void	displayStats (std::ostream &os, const int MyRank) const
	Display cache usage statistics.
Protected Member Functions
virtual void	popCache ()
	A simple wrapper method to handle popping the cache (removing the top element from the cache) and incrementing the number of pruned entries.
Private Member Functions
MSTHeapCache &	operator= (const MSTHeapCache &src)
	A dummy operator=.
Private Attributes
int	prunedEntries
	Number of entries that were pruned from the cache.
std::priority_queue < CachedESTInfo, std::vector < CachedESTInfo > , GreaterCachedESTInfo >	cache
	The actual heap of cache entries for various nodes.

Detailed Description

A cache to maintain similarity/distance metrics to build a Minimum Spanning Tree (MST) using a heap.

This class dervies off the MSTCache base class provides the functionality to manage a cache of metrics using a single large heap. The operations on a heap are fast. However, the current heap does not allow to rapidly prune unwanted entries right away. Consequently, pruning of entries is done on a "whenever-chance-arises" basis. This causes MSTHeapCache to have a much higher memory foot print when compared to MSTMultiListCache.

Definition at line 52 of file MSTHeapCache.h.

Constructor & Destructor Documentation

MSTHeapCache::MSTHeapCache	(	const int	totalESTCount,
		const int	startOwnESTidx,
		const int	numOwnESTs,
		const ESTAnalyzer *	analyzer,
		const bool	repopulateCaches,
		const int	maxCachePerEST
	)

The constructor.

This MST cache requires information about the number of ESTs in the system in order to effectively track the ESTs already added to the MST. These values must be passed in as the various parameters to this class. The constructor essentially passes off the parameters to the base class that saves the information (for future reference) in suitable instance variables.

Note:: This object is typically instantiated in the MSTClusterMaker::makeClusters() method.

Parameters:

`[in]`	totalESTCount	The total number of ESTs to be processed (that is, to be added to the MST).
`[in]`	startOwnESTidx	The starting index of the EST that is owned by the process that is using this cache. This value is used to internally normalize est index values to 0 for the first EST owned by this process.
`[in]`	numOwnESTs	The number of ESTs owned by the process that is using this cache. This information is used to reserve necessary space to hold SMLists for each EST owned by the manager/worker process.
`[in]`	analyzer	The analyzer to be used for EST comparisons, comparing metrics, and ordering entries in this cache depending on the type of EST analyzer (whether it is similarity based or distance metric based).
`[in]`	repopulateCaches	If this parameter is `true` then the MSTCache will request lists to be repopulated when needed. Repopulating lists guarantees that ultimately a MST will be developed. If repopulation is suppressed then the resulting spanning tree may not be a MST.
`[in]`	maxCachePerEST	This parameter suggests the maximum number of cached entries that must be maintained for a given EST. This parameter may not be really used by all dervied classes (this is only a suggestion).

Definition at line 39 of file MSTHeapCache.cpp.

virtual MSTHeapCache::~MSTHeapCache ( ) [inline, virtual]

The destructor.

The STL data structures used by this class manage all the memory operations for this class. Consequently, the destructor does not have any special tasks to perform. It here present merely to adhere to coding conventions.

Definition at line 107 of file MSTHeapCache.h.

Member Function Documentation

void MSTHeapCache::displayStats	(	std::ostream &	os,
		const int	MyRank
	)			const `[virtual]`

Display cache usage statistics.

This method currently displays the following information:

Total number of entries cached by this cache.
Current number of entries left in the cache.

Parameters:

`[out]`	os	The output stream to which statistics must be written.
`[in]`	MyRank	The MPI rank of the process to which this cache is assocaited. This information is used merely for displaying more informative statistics and does not influence the actual values displayed by this method.

Implements MSTCache.

Definition at line 101 of file MSTHeapCache.cpp.

References cache, and prunedEntries.

void MSTHeapCache::getBestEntry	(	int &	srcESTidx,
		int &	destESTidx,
		float &	metric,
		int &	alignmentData,
		int &	directionData
	)			const `[virtual]`

Obtains the top-most similar entry from the MSTCache.

This method simply uses the top-most entry in the heap and populates the parameters with the appropriate value. Note that the parameters are initialized to -1, -1, -1.0f, and -1 respectively.

Parameters:

`[out]`	srcESTidx	The source EST index from where the similarity metric is being measured. The srcESTidx is already present in the MST.
`[out]`	destESTidx	The destination EST index that is the best choice to be added to the MST (based on the local information).
`[out]`	metric	The similarity/distance metric between the srcESTidx and the destESTidx.
`[out]`	alignmentData	The alignment data associated with the srcESTidx and the destESTidx.
`[out]`	directionData	The direction data associated with the srcESTidx and the destESTidx.

Implements MSTCache.

Definition at line 82 of file MSTHeapCache.cpp.

References CachedESTInfo::alignmentData, MSTCache::analyzer, cache, CachedESTInfo::directionData, CachedESTInfo::estIdx, ESTAnalyzer::getInvalidMetric(), CachedESTInfo::metric, and CachedESTInfo::refESTidx.

Referenced by PMSTHeapCache::popBestEntry().

void MSTHeapCache::mergeList	(	const int	estIdx,
		const SMList &	list
	)			`[virtual]`

Add/merges a batch of new cache entries with the current entries in the cache for a given EST.

This method merges a given batch of new cache entries with existing cache entries in the cache. Caches are not trimmed to fit into the suggested maxCachePerEST size.

Parameters:

`[in]`	estIdx	The zero-based index of the reference EST against which the batch of cache entries in `list` were analyzed and generated.
`[in]`	list	A SMList containing the batch of new cache entries to be merged with any existing entries in the cache for the given EST (whose zero-based index is `estIdx`).

Implements MSTCache.

Definition at line 73 of file MSTHeapCache.cpp.

References cache.

Referenced by PMSTClusterMaker::mergeManager().

MSTHeapCache& MSTHeapCache::operator= ( const MSTHeapCache & src ) [private]

A dummy operator=.

The operator=() is supressed for this class as it has constant members whose value is set when the object is created. These values cannot be changed during the lifetime of this object.

Parameters:

[in] src The source object from where data is to be copied. Currently this value is ignored.

Returns:: Reference to this.

Reimplemented from MSTCache.

void MSTHeapCache::popCache ( ) [protected, virtual]

A simple wrapper method to handle popping the cache (removing the top element from the cache) and incrementing the number of pruned entries.

Definition at line 113 of file MSTHeapCache.cpp.

References cache, and prunedEntries.

Referenced by PMSTHeapCache::popBestEntry(), and pruneCaches().

void MSTHeapCache::pruneCaches	(	const int	estIdxAdded,
		std::vector< int > &	repopulateList,
		const bool	prefixListSize = `true`
	)			`[virtual]`

Suggest to clear caches that contain entries for a newly added EST.

This method can be used to suggest to the cache to prune entries corresponding to the estIdxAdded from the various data structures maintained by this cache. This method repeatedly removes entries at the top of the heap if the entries correspond to estIdx.

Parameters:

`[in]`	estIdxAdded	The index of the EST that has just been added to the MST.
`[out]`	repopulateList	The index values of ESTs whose cache needs to be repopulated. Currently, this method does not populate any entries into this list.
`[in]`	prefixListSize	If this parameter is set to `true`, then the number of entries added to the repopulateList is inserted at the beginning of the vector. This eases transmission of lists via MPI to the master process.

Implements MSTCache.

Definition at line 52 of file MSTHeapCache.cpp.

References cache, MSTCache::isESTinMST(), MSTCache::nodesAdded, and popCache().

Member Data Documentation

std::priority_queue<CachedESTInfo, std::vector<CachedESTInfo>, GreaterCachedESTInfo> MSTHeapCache::cache [private]

The actual heap of cache entries for various nodes.

This cache contains all the cached entries for each EST owned and managed by this MSTCache. Entries are added by the mergeList method and removed by the pruneCache method.

Definition at line 224 of file MSTHeapCache.h.

Referenced by displayStats(), getBestEntry(), mergeList(), popCache(), and pruneCaches().

int MSTHeapCache::prunedEntries [private]

Number of entries that were pruned from the cache.

This instance variable is used to track the number of entries that were removed from the cache by the pruneCache() method.

Definition at line 215 of file MSTHeapCache.h.

Referenced by displayStats(), and popCache().

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

MSTHeapCache Class Reference

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation