CLevel2Search Class Reference

Level 2 search. More...

#include <Level2Search.h>

Inheritance diagram for CLevel2Search:

Public Member Functions
	CLevel2Search ()
	Constructor. More...
const std::vector< CMatching > &	GetMatchings () const
	Get matching vector. More...
void	Save () const
	Save results to log file for debugging purposes. More...

Private Member Functions
size_t	Permute (CMatching &, const size_t)
	Permute the matching. More...
size_t	GetIndex (CMatching &)
	Get the index of a matching. More...
const size_t	GetNumMatchings (const size_t) const
	Number of matchings. More...

Private Attributes
std::set< size_t >	m_stlUsed
	Set of indices of used matchings. More...
std::vector< CMatching >	m_stlResults
	Results. More...

Additional Inherited Members
Static Public Member Functions inherited from CSettings
static void	SetWidth (const size_t)
	Set width. More...
static void	SetDepth (const size_t)
	Set depth. More...
Static Protected Attributes inherited from CSettings
static size_t	m_nWidth = 9
	Comparator network width. More...
static size_t	m_nDepth = 6
	Comparator network depth. More...

Detailed Description

Search for a collection of canonical matchings for level 2 of a first normal form sorting network. That is, out of all candidates for level 2 generated by permuting the channels in pairs, so that the comparator network stays in first normal form, choose the lexicographically first one.

Consider the sorting network in the figure below (left). We can construct a new sorting network by swapping the pair of green channels with the pair of blue channels. The resulting sorting network on the right has both the min-max comparators that we have used so far (which put the maximum on the bottom channel and the minimum on the top channel), and max-min comparators, which put the maximum on the top channel and the minimum on the bottom channel. See also C1NF1. In the figure below (right) the arrows on the comparators point in the direction taken by the maximum. Notice that we have created four max-min comparators and a twist at the end of the channel to keep the outputs in sorted order.

We flip the first max-min comparator and the green and blue channels to the right of it (below, left) and make the corresponding twist at the end (below, right).

We flip the second max-min comparator and the green and blue channels to the right of it (below, left) and make the corresponding twist at the end (below, right).

We flip the third max-min comparator and the green and blue channels to the right of it (below, left) and make the corresponding twist at the end (below, right).

We flip the fourth max-min comparator and the green and blue channels to the right of it (below, left) and make the corresponding twist at the end (below, right). Notice that the twists have cancelled out leaving us with a new sorting network that has a different second level than the one we started with.

Our search therefore needs to include only one of the second level candidates that can be obtained by permuting pairs of channels. In our example above, only one of the two second levels in the figure below need appear in the search. Notice that the comparator networks remain in first normal form.

This speeds up the search by not having to iterate through all possibilities for the second level.

Definition at line 80 of file Level2Search.h.

Constructor & Destructor Documentation

CLevel2Search()

CLevel2Search::CLevel2Search

(

)

Perform a search for level 2 matchings and store them in lexicographic order in m_stlResults. Print information to the console and the log file.

Definition at line 35 of file Level2Search.cpp.

Member Function Documentation

GetIndex()

size_t CLevel2Search::GetIndex ( CMatching &  matching )

private

Given a matching, find the order in which it is generated by the matching generation algorithm.

Parameters

matching

A perfect matching.

Returns

Order in which it is generated.

Definition at line 72 of file Level2Search.cpp.

GetMatchings()

const std::vector< CMatching > & CLevel2Search::GetMatchings

(

)

const

Reader function for the resulting vector of matchings.

Returns

Reference to m_stlResults.

Definition at line 143 of file Level2Search.cpp.

GetNumMatchings()

const size_t CLevel2Search::GetNumMatchings ( const size_t  n ) const

private

Get number of matchings on \(n\) channels, that is,

\[ \prod_{i=1}^{\lfloor (n-1)/2\rfloor} (2i + 1). \]

Note that the result will fit into a 32-bit word for \(n \leq 15\), which is probably larger than any sorting network width that could sensibly be used by this program in the forseeable future.

Parameters

n	Number of channels.

Returns

Number of matchings on n channels.

Definition at line 157 of file Level2Search.cpp.

Permute()

size_t CLevel2Search::Permute ( CMatching &  matching, const size_t  n  )

private

Find the minimum index over all permutations of pairs of channels in a matching.

Parameters

matching	A matching.
n	Size of permutation.

Returns

Smallest matching index from all permuted matchings.

Definition at line 124 of file Level2Search.cpp.

Save()

void CLevel2Search::Save

(

)

const

Save results to file for debugging purposes. The file name is hard-coded as level2-x.txt where x is the number of channels m_nWidth.

Definition at line 169 of file Level2Search.cpp.

Member Data Documentation

m_stlResults

std::vector<CMatching> CLevel2Search::m_stlResults

private

Definition at line 83 of file Level2Search.h.

m_stlUsed

std::set<size_t> CLevel2Search::m_stlUsed

private

Definition at line 82 of file Level2Search.h.