#include <FUFiniteStateAutomaton.hh>

Inheritance diagram for FUFiniteStateAutomaton:

Collaboration diagram for FUFiniteStateAutomaton:

Public Types
typedef FSAStateTransitionIndex	OperationID

Public Types inherited from FiniteStateAutomaton
typedef int	FSAStateTransitionIndex
	Type used for indexing the transitions.

typedef int	FSAStateIndex
	Type used for indexing the states.

typedef std::set< FSAStateIndex >	FSAStateIndexSet
	Type for a set of state indices.

Public Member Functions
	FUFiniteStateAutomaton (const TTAMachine::FunctionUnit &fu, bool lazyBuilding=true)

virtual	~FUFiniteStateAutomaton ()

FSAStateIndex	joinState (FSAStateIndexSet sourceStates)

CollisionMatrix &	operationCollisionMatrix (const std::string operationName)

virtual FSAStateIndex	destinationState (FSAStateIndex source, FSAStateTransitionIndex transition)

virtual bool	isLegalTransition (FSAStateIndex source, FSAStateTransitionIndex transition)

virtual std::string	stateName (FSAStateIndex state) const

bool	conflictsWith (OperationID operation) const
	Inline functions for fast access in the compiled simulator.

void	issueOperation (OperationID operation)

void	advanceCycle ()

void	buildStateMachine ()

Public Member Functions inherited from FiniteStateAutomaton
	FiniteStateAutomaton (FSAStateTransitionIndex defaultState=ILLEGAL_STATE, int transitionCount=0)

virtual	~FiniteStateAutomaton ()

virtual const std::string &	transitionName (FSAStateTransitionIndex transition) const

virtual FSAStateTransitionIndex	transitionIndex (const std::string &transitionName) const

virtual FSAStateIndex	addState ()

virtual FSAStateTransitionIndex	addTransitionType (const std::string &name)

virtual void	setTransitionName (FSAStateTransitionIndex transition, const std::string &name)

virtual void	setTransition (FSAStateIndex source, FSAStateIndex destination, FSAStateTransitionIndex transition)

virtual std::string	toDotString () const

virtual FSAStateIndex	startState () const

Private Types
typedef std::map< FSAStateIndex, CollisionMatrix * >	StateCollisionMatrixIndex
	Index for collision matrices of states (key is the state index).

typedef std::map< CollisionMatrix, FSAStateIndex >	CollisionMatrixStateIndex
	Index for finding the state for a collision matrix.

Private Member Functions
void	addCollisionMatrixForState (FSAStateIndex state, CollisionMatrix *matrix)

FiniteStateAutomaton::FSAStateIndex	resolveState (FiniteStateAutomaton::FSAStateIndex source, FiniteStateAutomaton::FSAStateTransitionIndex transition)

Private Attributes
FUCollisionMatrixIndex	operationCollisionMatrices_
	Collision matrices of operations are stored here.

StateCollisionMatrixIndex	stateCollisionMatrices_
	The collision matrices of each state.

CollisionMatrixStateIndex	collisionMatrixStates_
	An index for quickly finding the state of a collision matrix.

FSAStateTransitionIndex	nopTransition_
	The number of the NOP transition.

Friends
class	FSAFUResourceConflictDetector
	Friend due to highly optimized compiled simulation versions of the conflict detection functions.

Additional Inherited Members
Static Public Attributes inherited from FiniteStateAutomaton
static const FSAStateIndex	ILLEGAL_STATE = -1
	A state id which denotes an illegal state.

static const FSAStateIndex	UNKNOWN_STATE = -2
	A state id which denotes an unknown (unresolved) state. Used for lazy construction of states.

Protected Types inherited from FiniteStateAutomaton
typedef std::vector< FSAStateIndex >	TransitionVector
	Vector which stores the target states of for each transition type.

typedef std::vector< TransitionVector >	TransitionMap
	Type for storing the transitions of each state. The vector stores for each state (indexed from 0) a vector with elements as many there are transitions. The value of the element is the target state to which the transition leads to, or ILLEGAL_STATE_INDEX if there is no transition for that transition type from that state. Using this structure it's possible to find the target state using two table (vector) lookups.

Protected Attributes inherited from FiniteStateAutomaton
TransitionMap	transitions_
	The state transitions. In protected to allow fast access from derived classes.

Detailed Description

Finite state automaton (FSA) used to model function unit pipeline resources.

Includes support for lazily initializing the states when needed.

Definition at line 55 of file FUFiniteStateAutomaton.hh.

Member Typedef Documentation

◆ CollisionMatrixStateIndex

typedef std::map<CollisionMatrix, FSAStateIndex> FUFiniteStateAutomaton::CollisionMatrixStateIndex

private

Index for finding the state for a collision matrix.

Definition at line 104 of file FUFiniteStateAutomaton.hh.

◆ OperationID

typedef FSAStateTransitionIndex FUFiniteStateAutomaton::OperationID

Definition at line 61 of file FUFiniteStateAutomaton.hh.

◆ StateCollisionMatrixIndex

typedef std::map<FSAStateIndex, CollisionMatrix*> FUFiniteStateAutomaton::StateCollisionMatrixIndex

private

Index for collision matrices of states (key is the state index).

Definition at line 100 of file FUFiniteStateAutomaton.hh.

Constructor & Destructor Documentation

◆ FUFiniteStateAutomaton()

FUFiniteStateAutomaton::FUFiniteStateAutomaton	(	const TTAMachine::FunctionUnit &	fu,
		bool	lazyBuilding = `true`
	)

Initializes the FSA from the given FU.

This version is to be used in fast compiled simulation that needs to minimize all function call overheads. To allow figuring out the state ids statically, they are assigned according to the operation's order in the FU when fetched with FunctionUnit::operation().

The last state id (id FunctionUnit::operationCount()) is reserved for NOP. This way compiled simulator may access the state array with a constant index when issuing an operation or checking for a conflict without runtime overhead for figuring out the state id first for each operation.

Parameters

fu	The function unit to build the FSA from.
lazyBuilding	True in case states should be built lazily the first time they are visited. Should improve startup time for larger FSAs.

Definition at line 61 of file FUFiniteStateAutomaton.cc.

                                                         :
    FiniteStateAutomaton(UNKNOWN_STATE, fu.operationCount() + 1), 
    operationCollisionMatrices_(fu) {
 
    // remove this loop from the benchmark
    for (int i = 0; i < fu.operationCount(); ++i) {
        const std::string opName = 
            StringTools::stringToUpper(fu.operation(i)->name());
 
        // each operation is a transition type in the state machine
        setTransitionName(i, opName);    
    }
    setTransitionName(fu.operationCount(), "[NOP]");
    nopTransition_ = fu.operationCount();
 
    // create S0
    addState();
 
    // the initial state's collision matrix is an all zeros conflict matrix, 
    // copy the NOP matrix
    addCollisionMatrixForState(
        0, 
        new CollisionMatrix(operationCollisionMatrices_.at(nopTransition_)));
 
    if (!lazyBuilding)
        buildStateMachine();
}

References addCollisionMatrixForState(), FiniteStateAutomaton::addState(), FUCollisionMatrixIndex::at(), buildStateMachine(), TTAMachine::HWOperation::name(), nopTransition_, TTAMachine::FunctionUnit::operation(), operationCollisionMatrices_, TTAMachine::FunctionUnit::operationCount(), FiniteStateAutomaton::setTransitionName(), and StringTools::stringToUpper().

Here is the call graph for this function:

◆ ~FUFiniteStateAutomaton()

FUFiniteStateAutomaton::~FUFiniteStateAutomaton ( )

virtual

Destructor.

Definition at line 93 of file FUFiniteStateAutomaton.cc.

                                                {
    AssocTools::deleteAllValues(stateCollisionMatrices_);
}

References AssocTools::deleteAllValues(), and stateCollisionMatrices_.

Here is the call graph for this function:

Member Function Documentation

◆ addCollisionMatrixForState()

void FUFiniteStateAutomaton::addCollisionMatrixForState	(	FSAStateIndex	state,
		CollisionMatrix *	matrix
	)

private

Connects a state and a collision matrix.

Parameters

state	The state index.
matrix	The collision matrix (becomes owned by the index).

Definition at line 162 of file FUFiniteStateAutomaton.cc.

                                                  {
 
    stateCollisionMatrices_[state] = matrix;
    collisionMatrixStates_[*matrix] = state;
}

References collisionMatrixStates_, and stateCollisionMatrices_.

Referenced by FUFiniteStateAutomaton(), and resolveState().

◆ advanceCycle()

void FUFiniteStateAutomaton::advanceCycle ( )

◆ buildStateMachine()

void FUFiniteStateAutomaton::buildStateMachine ( )

Builds all states and state transitions.

This might take very long time if there are lots of states to build. That is, if the FU pipeline resource usage patterns are long and complicated.

Definition at line 176 of file FUFiniteStateAutomaton.cc.

                                          {
 
    hash_set<FSAStateIndex> handledStates;
    hash_set<FSAStateIndex> unfinishedStatesList;
    unfinishedStatesList.insert(0); // start from the start state
 
    while (!unfinishedStatesList.empty()) {
        const FSAStateIndex state = *unfinishedStatesList.begin();
        unfinishedStatesList.erase(state);
        // go through all operations (transitions), the NOP is included
        // and resolve their target state from the current state
        for (int i = 0; i < operationCollisionMatrices_.size(); ++i) {
            FSAStateIndex resolvedState = resolveState(state, i);
            if (resolvedState != ILLEGAL_STATE && 
                handledStates.find(resolvedState) == handledStates.end() &&
                resolvedState != state)
                unfinishedStatesList.insert(resolvedState);            
        }
        handledStates.insert(state);
    }
}

References FiniteStateAutomaton::ILLEGAL_STATE, operationCollisionMatrices_, resolveState(), and FUCollisionMatrixIndex::size().

Referenced by FUFiniteStateAutomaton(), and FSAFUResourceConflictDetector::initializeAllStates().

Here is the call graph for this function:

◆ conflictsWith()

bool FUFiniteStateAutomaton::conflictsWith ( OperationID operation ) const

Inline functions for fast access in the compiled simulator.

◆ destinationState()

FUFiniteStateAutomaton::FSAStateIndex FUFiniteStateAutomaton::destinationState	(	FSAStateIndex	source,
		FSAStateTransitionIndex	transition
	)

virtual

Returns the index of the state resulting from the given transition from the given source state.

This method is called often, thus should be as fast as possible. Therefore, all range checking etc. is disabled. This implementation supports lazy initialization, i.e., it is capable of building missing states when requested.

Parameters

source	The source state.
transition	The transition.

Returns: The index of the destination state.

Reimplemented from FiniteStateAutomaton.

Definition at line 225 of file FUFiniteStateAutomaton.cc.

                                                              {
    if (transitions_[source][transition] == UNKNOWN_STATE)
        return resolveState(source, transition);
    return transitions_[source][transition];
}

References resolveState(), FiniteStateAutomaton::transitions_, and FiniteStateAutomaton::UNKNOWN_STATE.

Referenced by isLegalTransition().

Here is the call graph for this function:

◆ isLegalTransition()

bool FUFiniteStateAutomaton::isLegalTransition	(	FSAStateIndex	source,
		FSAStateTransitionIndex	transition
	)

virtual

Returns true in case the given transition is legal (accepted by the state machine) from the given state.

This method is called often, thus should be as fast as possible. Therefore, all range checking etc. is disabled. This implementation supports lazy initialization, i.e., it is capable of building missing states when requested.

Parameters

source	The source state.
transition	The transition.

Returns: True in case the transition is legal.

Reimplemented from FiniteStateAutomaton.

Definition at line 246 of file FUFiniteStateAutomaton.cc.

                                        {
    return destinationState(source, transition) != ILLEGAL_STATE;
}

References destinationState(), and FiniteStateAutomaton::ILLEGAL_STATE.

Here is the call graph for this function:

◆ issueOperation()

void FUFiniteStateAutomaton::issueOperation ( OperationID operation )

◆ joinState()

FiniteStateAutomaton::FSAStateIndex FUFiniteStateAutomaton::joinState ( FSAStateIndexSet sourceStates )

Returns a join state which is created by ORin the conflict vectors of the given source states.

If the state already exists, returns it, creates a new state otherwise.

Parameters

sourceStates The set of source states which are joined.

Returns: Index to the join state.

Definition at line 262 of file FUFiniteStateAutomaton.cc.

                                                  {
    abortWithError("Not implemented.");
    return -1;
}

References abortWithError.

◆ operationCollisionMatrix()

CollisionMatrix & FUFiniteStateAutomaton::operationCollisionMatrix ( const std::string operationName )

Returns the collision matrix for the given operation.

Parameters

operationName Name of the operation.

Returns: The collision matrix.

Definition at line 205 of file FUFiniteStateAutomaton.cc.

                                   {
    return operationCollisionMatrices_.at(
        transitionIndex(StringTools::stringToUpper(operationName)));
}

References FUCollisionMatrixIndex::at(), operationCollisionMatrices_, StringTools::stringToUpper(), and FiniteStateAutomaton::transitionIndex().

Referenced by resolveState().

Here is the call graph for this function:

◆ resolveState()

FiniteStateAutomaton::FSAStateIndex FUFiniteStateAutomaton::resolveState	(	FiniteStateAutomaton::FSAStateIndex	source,
		FiniteStateAutomaton::FSAStateTransitionIndex	transition
	)

private

Initializes the given state transition entry.

The transition target state is resolved and built if necessary.

Returns: The index of the target state.

Definition at line 105 of file FUFiniteStateAutomaton.cc.

                                                            {
 
    const CollisionMatrix& operationCollisionMatrix = 
        operationCollisionMatrices_.at(transition);
 
    const CollisionMatrix& stateMatrix = *stateCollisionMatrices_[source];
    // Check whether the transition is legal, that is, the conflict
    // matrix has a 0 in the column 1 (representing the next cycle) in
    // the row representing the operation. The column 0 is for
    // starting the operation at the same clock cycle, which cannot
    // be done in case of our TTA FU. Thus, all states are cycle
    // advancing.
    if (transition == nopTransition_ || 
        !stateMatrix.isCollision(transition, 1)) {
 
        // transition is legal, create the target state's collision
        // matrix (all states considered cycle advancing) by shifting
        // the source conflict matrix to left and ORing the operation's
        // conflict matrix
        CollisionMatrix* newMatrix = new CollisionMatrix(stateMatrix);
        newMatrix->shiftLeft();
        newMatrix->orWith(operationCollisionMatrix);
 
        // check if we already have a state with the created collision matrix
        FSAStateIndex targetState = ILLEGAL_STATE;
        CollisionMatrixStateIndex::const_iterator foundState =
            collisionMatrixStates_.find(*newMatrix);
        if (foundState != collisionMatrixStates_.end()) {
 
            // found an old state with the wanted collision matrix, 
            // set the transition target to the old state
            targetState = (*foundState).second;
 
            delete newMatrix;
            newMatrix = NULL;
        } else {
            // no state with the wanted collision matrix exists, 
            targetState = addState();
            addCollisionMatrixForState(targetState, newMatrix);
        }
        setTransition(source, targetState, transition);
        return targetState;
    } else {
        setTransition(source, ILLEGAL_STATE, transition);
        return ILLEGAL_STATE;
    }
}

References addCollisionMatrixForState(), FiniteStateAutomaton::addState(), FUCollisionMatrixIndex::at(), collisionMatrixStates_, FiniteStateAutomaton::ILLEGAL_STATE, CollisionMatrix::isCollision(), nopTransition_, operationCollisionMatrices_, operationCollisionMatrix(), BitMatrix::orWith(), FiniteStateAutomaton::setTransition(), BitMatrix::shiftLeft(), and stateCollisionMatrices_.

Referenced by FSAFUResourceConflictDetector::advanceCycleLazyInline(), buildStateMachine(), destinationState(), and FSAFUResourceConflictDetector::issueOperationLazyInline().

Here is the call graph for this function:

◆ stateName()

std::string FUFiniteStateAutomaton::stateName ( FSAStateIndex state ) const

virtual

Returns the textual description of the state at the given index.

Parameters

state The index of the state of which name to return.

Returns: The name of the state.

Reimplemented from FiniteStateAutomaton.

Definition at line 274 of file FUFiniteStateAutomaton.cc.

                                                           {
    StateCollisionMatrixIndex::const_iterator i = 
        stateCollisionMatrices_.find(state);
 
    if (i == stateCollisionMatrices_.end())
        throw OutOfRange(
            __FILE__, __LINE__, __func__, "No such state.");
 
    return (*i).second->toDotString();
}

References __func__, and stateCollisionMatrices_.

Friends And Related Symbol Documentation

◆ FSAFUResourceConflictDetector

friend class FSAFUResourceConflictDetector

friend

Friend due to highly optimized compiled simulation versions of the conflict detection functions.

Definition at line 59 of file FUFiniteStateAutomaton.hh.

Member Data Documentation

◆ collisionMatrixStates_

CollisionMatrixStateIndex FUFiniteStateAutomaton::collisionMatrixStates_

private

An index for quickly finding the state of a collision matrix.

Definition at line 111 of file FUFiniteStateAutomaton.hh.

Referenced by addCollisionMatrixForState(), and resolveState().

◆ nopTransition_

FSAStateTransitionIndex FUFiniteStateAutomaton::nopTransition_

private

The number of the NOP transition.

Definition at line 113 of file FUFiniteStateAutomaton.hh.

Referenced by FUFiniteStateAutomaton(), and resolveState().

◆ operationCollisionMatrices_

FUCollisionMatrixIndex FUFiniteStateAutomaton::operationCollisionMatrices_

private

Collision matrices of operations are stored here.

Definition at line 107 of file FUFiniteStateAutomaton.hh.

Referenced by buildStateMachine(), FUFiniteStateAutomaton(), operationCollisionMatrix(), and resolveState().

◆ stateCollisionMatrices_

StateCollisionMatrixIndex FUFiniteStateAutomaton::stateCollisionMatrices_

private

The collision matrices of each state.

Definition at line 109 of file FUFiniteStateAutomaton.hh.

Referenced by addCollisionMatrixForState(), resolveState(), stateName(), and ~FUFiniteStateAutomaton().

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

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CollisionMatrixStateIndex

◆ OperationID

◆ StateCollisionMatrixIndex

Constructor & Destructor Documentation

◆ FUFiniteStateAutomaton()

◆ ~FUFiniteStateAutomaton()

Member Function Documentation

◆ addCollisionMatrixForState()

◆ advanceCycle()

◆ buildStateMachine()

◆ conflictsWith()

◆ destinationState()

◆ isLegalTransition()

◆ issueOperation()

◆ joinState()

◆ operationCollisionMatrix()

◆ resolveState()

◆ stateName()

Friends And Related Symbol Documentation

◆ FSAFUResourceConflictDetector

Member Data Documentation

◆ collisionMatrixStates_

◆ nopTransition_

◆ operationCollisionMatrices_

◆ stateCollisionMatrices_