SimpleBrokerDirector Class Reference

#include <SimpleBrokerDirector.hh>

Inheritance diagram for SimpleBrokerDirector:

Collaboration diagram for SimpleBrokerDirector:

Classes
struct	OriginalResources

Public Member Functions
	SimpleBrokerDirector (const TTAMachine::Machine &machine, AssignmentPlan &plan, unsigned int initiationInterval_)
virtual	~SimpleBrokerDirector ()
virtual bool	canAssign (int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
virtual bool	canTransportImmediate (const MoveNode &node, const TTAMachine::Bus *preAssignedBus) const
virtual void	assign (int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) override
virtual void	unassign (MoveNode &node) override
virtual int	earliestCycle (MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
virtual int	earliestCycle (int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
virtual int	latestCycle (MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
virtual int	latestCycle (int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const override
virtual bool	hasGuard (const MoveNode &node) const
virtual TTAProgram::Instruction *	instruction (int cycle) const override
virtual bool	supportsExternalAssignments () const override
virtual int	largestCycle () const override
virtual int	smallestCycle () const override
virtual void	loseInstructionOwnership (int cycle)
virtual std::shared_ptr< TTAProgram::TerminalImmediate >	immediateValue (const MoveNode &)
virtual int	immediateWriteCycle (const MoveNode &) const
virtual bool	isTemplateAvailable (int, std::shared_ptr< TTAProgram::Immediate >) const
void	setMaxCycle (unsigned int cycle)
void	clearOldResources ()
void	clear ()
void	setDDG (const DataDependenceGraph *ddg)
void	setCFG (const ControlFlowGraph *cfg)
void	setBBN (const BasicBlockNode *bbn)
Public Member Functions inherited from BrokerDirector
	BrokerDirector (const TTAMachine::Machine &machine, AssignmentPlan &plan)
virtual	~BrokerDirector ()
Public Member Functions inherited from ResourceManager
	ResourceManager (const TTAMachine::Machine &machine)
virtual	~ResourceManager ()
const TTAMachine::Machine &	machine () const

Private Member Functions
IUBroker &	immediateUnitBroker () const
ITemplateBroker &	instructionTemplateBroker () const
BusBroker &	busBroker () const
ExecutionPipelineBroker &	executionPipelineBroker () const
unsigned int	instructionIndex (unsigned int maxCycle) const

Private Attributes
std::map< const MoveNode *, OriginalResources *, MoveNode::Comparator >	origResMap_
int	knownMaxCycle_
int	knownMinCycle_
unsigned int	initiationInterval_
int	schedulingWindow_
	the number of instructions to look back in the schedule for a free slot
std::map< int, int >	moveCounts_
int	busCount_

Additional Inherited Members
Protected Attributes inherited from BrokerDirector
AssignmentPlan *	plan_
	Assignment plan.

Detailed Description

A simple broker director.

Definition at line 67 of file SimpleBrokerDirector.hh.

Constructor & Destructor Documentation

SimpleBrokerDirector()

SimpleBrokerDirector::SimpleBrokerDirector	(	const TTAMachine::Machine &	machine,
		AssignmentPlan &	plan,
		unsigned int	ii
	)

Constructor.

Parameters

machine	Target machine.
plan	Resource assignment plan.
ii	Initiation interval.

Definition at line 79 of file SimpleBrokerDirector.cc.

                    :
    BrokerDirector(machine, plan),
    initiationInterval_(ii), schedulingWindow_(140),
    busCount_(machine.busNavigator().count()) {
    knownMaxCycle_ = -1;
    knownMinCycle_ = INT_MAX;
 
    if (Application::cmdLineOptions() != NULL) {
        SchedulerCmdLineOptions* options =
            dynamic_cast<SchedulerCmdLineOptions*>(
                Application::cmdLineOptions());
        schedulingWindow_ = options->schedulingWindowSize();
    }
}

References Application::cmdLineOptions(), knownMaxCycle_, knownMinCycle_, options, and schedulingWindow_.

Here is the call graph for this function:

~SimpleBrokerDirector()

SimpleBrokerDirector::~SimpleBrokerDirector ( )

virtual

Destructor.

Definition at line 100 of file SimpleBrokerDirector.cc.

                                           {
    MapTools::deleteAllValues(origResMap_);
}

References MapTools::deleteAllValues(), and origResMap_.

Here is the call graph for this function:

Member Function Documentation

assign()

void SimpleBrokerDirector::assign ( int  cycle, MoveNode &  node, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  )

overridevirtual

Assign all resources needed by a given node starting from given cycle, and place the node in that cycle.

The manager keeps any pre-existing assignment and verifies that assigned resource is available. For all unassigned parts of the node, the resource manager looks for and then assigns the necessary resources. If the node is not fully assigned after the invocation of this operation, it means the assignment attempt failed.

Parameters

cycle	Cycle.
node	Node.

Exceptions

InvalidData

exception if given node is already placed in a cycle different from given cycle.

Implements ResourceManager.

Definition at line 236 of file SimpleBrokerDirector.cc.

                                              {
    if (cycle < 0) {
        throw InvalidData(__FILE__, __LINE__, __func__, 
                          "Negative cycles not supported by RM");
    }
    if (cycle == INT_MAX) {
        throw InvalidData(__FILE__, __LINE__, __func__, 
                          "INT_MAX cycle not supported by RM");
    }
 
    if (node.isPlaced() && node.cycle() != cycle) {
        string msg =
            "Node is already placed in a cycle different from given cycle.";
        throw InvalidData(__FILE__, __LINE__, __func__, msg);
    }
 
    if (node.isMove()) {
        OriginalResources* oldRes = new OriginalResources(
            node.move().source().copy(),
            node.move().destination().copy(),
            &node.move().bus(),
            NULL,
            false);
        if (node.move().isUnconditional()) {
            oldRes->isGuarded_ = false;
        } else {
            oldRes->isGuarded_ = true;
            oldRes->guard_ = node.move().guard().copy();
        }
        origResMap_.insert(
            std::pair<const MoveNode*, OriginalResources*>(&node, oldRes));
    }
 
    bool success = plan_->tryCachedAssignment(
        node, cycle, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
 
    plan_->setRequest(cycle, node, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
    assert( cycle != -1 );
 
    while (!success) {
        if (!plan_->isTestedAssignmentPossible()) {
            if (&plan_->currentBroker() == &plan_->firstBroker()) {
                string msg = "No resource assignment found for ";
                msg += node.toString() + "!\n" ;
                msg += "Instruction at cycle " + Conversion::toString(cycle);
                msg += " is: ";
                msg += POMDisassembler::disassemble(*instruction(cycle));
                throw ModuleRunTimeError(__FILE__, __LINE__, __func__, msg);
            } else {
                plan_->backtrack();
            }
 
        } else {
            plan_->tryNextAssignment();
            if (&plan_->currentBroker() == &plan_->lastBroker()) {
                success = true;
            } else {
                plan_->advance();
            }
        }
    }
    if (knownMaxCycle_ < cycle) {
        knownMaxCycle_ = cycle;
    }
    int guardSlack = std::max(0, node.guardLatency() -1);
    if (knownMinCycle_ > cycle - guardSlack) {
        knownMinCycle_ = std::max(cycle - guardSlack,0);
#ifdef DEBUG_RM
            std::cerr << "Set known min cycle to" << knownMinCycle_ << std::endl;
#endif
            assert(knownMinCycle_ >= 0);
    }
    if (node.isMove()) {
        int iwc = immediateWriteCycle(node);
        if (node.isSourceImmediateRegister() &&
            knownMinCycle_ > iwc && iwc >= 0) {
            knownMinCycle_ = iwc;
#ifdef DEBUG_RM
            std::cerr << "Set known min cycle(2) to" << knownMinCycle_ << std::endl;
#endif
            assert(knownMinCycle_ >= 0);
        }
        moveCounts_[instructionIndex(cycle)]++;
    }
}

References __func__, AssignmentPlan::advance(), assert, AssignmentPlan::backtrack(), TTAProgram::Move::bus(), TTAProgram::MoveGuard::copy(), TTAProgram::Terminal::copy(), AssignmentPlan::currentBroker(), MoveNode::cycle(), TTAProgram::Move::destination(), POMDisassembler::disassemble(), AssignmentPlan::firstBroker(), TTAProgram::Move::guard(), SimpleBrokerDirector::OriginalResources::guard_, MoveNode::guardLatency(), immediateWriteCycle(), instruction(), instructionIndex(), SimpleBrokerDirector::OriginalResources::isGuarded_, MoveNode::isMove(), MoveNode::isPlaced(), MoveNode::isSourceImmediateRegister(), AssignmentPlan::isTestedAssignmentPossible(), TTAProgram::Move::isUnconditional(), knownMaxCycle_, knownMinCycle_, AssignmentPlan::lastBroker(), MoveNode::move(), moveCounts_, origResMap_, BrokerDirector::plan_, AssignmentPlan::setRequest(), TTAProgram::Move::source(), MoveNode::toString(), Conversion::toString(), AssignmentPlan::tryCachedAssignment(), and AssignmentPlan::tryNextAssignment().

Referenced by SimpleResourceManager::assign().

Here is the call graph for this function:

busBroker()

BusBroker & SimpleBrokerDirector::busBroker ( ) const

private

Return the bus broker.

Returns

The bus broker.

Exceptions

InstanceNotFound

If bus broker is not found.

Definition at line 737 of file SimpleBrokerDirector.cc.

                                      {
    ResourceBroker* broker = NULL;
    for (int i = 0; i < plan_->brokerCount(); i++) {
        broker = &plan_->broker(i);
        if (broker->isBusBroker()) {
            return dynamic_cast<BusBroker&>(*broker);
        }
    }
    string msg = "Bus broker not found.";
    throw InstanceNotFound(__FILE__, __LINE__, __func__, msg);
}

References __func__, AssignmentPlan::broker(), AssignmentPlan::brokerCount(), ResourceBroker::isBusBroker(), and BrokerDirector::plan_.

Referenced by canTransportImmediate(), hasGuard(), setBBN(), and setCFG().

Here is the call graph for this function:

canAssign()

bool SimpleBrokerDirector::canAssign ( int  cycle, MoveNode &  node, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  ) const

overridevirtual

Return true if given node can be assigned without resource conflicts in given cycle.

For those parts of the node that have been already assigned to a resource, the manager simply keeps the assignment and verifies that the resource is available. For those parts that are not yet assigned, the resource manager looks for any compatible resource that could be assigned.

Parameters

cycle	Cycle.
node	Node.

Returns

True if given node can be assigned without resource conflicts in given cycle, false otherwise.

Implements ResourceManager.

Definition at line 120 of file SimpleBrokerDirector.cc.

                           {
 
#ifdef DEBUG_RM
    std::cerr << "testing canassign, cycle: " << cycle <<
        " node: " << node.toString() << std::endl;
#endif
 
    if (initiationInterval_ != 0 && cycle >= (int)(initiationInterval_ * 2)) {
        return false;
    }
 
    if (node.isScheduled()) {
        debugLogRM("isScheduled == true");
        return false;
    }
 
    // fast way to reject some cases. Makes scheduling faster
    // for bus-limited machines.
    std::map<int,int>::const_iterator i = moveCounts_.find(cycle);
    if (i != moveCounts_.end() && i->second >= busCount_) {
        debugLogRM("instruction full!");
        return false;
    }
 
    OriginalResources* oldRes = NULL;
    if (node.isMove()) {
        // Store original resources of node
        oldRes = new OriginalResources(
            node.move().source().copy(),
            node.move().destination().copy(),
            &node.move().bus(),
            NULL,
            false);
        if (node.move().isUnconditional()) {
            oldRes->isGuarded_ = false;
        } else {
            oldRes->isGuarded_ = true;
            oldRes->guard_ = node.move().guard().copy();
        }
    }
    int placedInCycle = -1;
    if (node.isPlaced()) {
        placedInCycle = node.cycle();
    }
    plan_->setRequest(
    cycle, node, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
 
    bool success = false;
    while (!success) {
#ifdef DEBUG_RM
            Application::logStream()
                << "current broker: "
                << typeid(plan_->currentBroker()).name()
                << std::endl;
#endif
        if (!plan_->isTestedAssignmentPossible()) {
            if (&plan_->currentBroker() == &plan_->firstBroker()) {
                plan_->resetAssignments();
                debugLogRM("no assignment found");
                success = false; // no assignment found
                break;
            } else {
                debugLogRM("backtracking");
                plan_->backtrack();
            }
        } else if (&plan_->currentBroker() == &plan_->lastBroker()) {
            plan_->resetAssignments();
            success = true;
        } else {
            plan_->tryNextAssignment();
            plan_->advance();
        }
    }
    if (node.isMove()) {
        // restore original resources of node
        node.move().setSource(oldRes->src_);
        oldRes->src_ = NULL;
 
        node.move().setDestination(oldRes->dst_);
        oldRes->dst_ = NULL;
        node.move().setBus(*oldRes->bus_);
        if (oldRes->isGuarded_) {
            node.move().setGuard(oldRes->guard_);
            oldRes->guard_ = NULL;
        }
        delete oldRes;
    }
    if (placedInCycle != -1) {
        node.setCycle(placedInCycle);
    }
    return success;
}

References AssignmentPlan::advance(), AssignmentPlan::backtrack(), TTAProgram::Move::bus(), SimpleBrokerDirector::OriginalResources::bus_, busCount_, TTAProgram::MoveGuard::copy(), TTAProgram::Terminal::copy(), AssignmentPlan::currentBroker(), MoveNode::cycle(), debugLogRM, TTAProgram::Move::destination(), SimpleBrokerDirector::OriginalResources::dst_, AssignmentPlan::firstBroker(), TTAProgram::Move::guard(), SimpleBrokerDirector::OriginalResources::guard_, initiationInterval_, SimpleBrokerDirector::OriginalResources::isGuarded_, MoveNode::isMove(), MoveNode::isPlaced(), MoveNode::isScheduled(), AssignmentPlan::isTestedAssignmentPossible(), TTAProgram::Move::isUnconditional(), AssignmentPlan::lastBroker(), Application::logStream(), MoveNode::move(), moveCounts_, BrokerDirector::plan_, AssignmentPlan::resetAssignments(), TTAProgram::Move::setBus(), MoveNode::setCycle(), TTAProgram::Move::setDestination(), TTAProgram::Move::setGuard(), AssignmentPlan::setRequest(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), SimpleBrokerDirector::OriginalResources::src_, MoveNode::toString(), and AssignmentPlan::tryNextAssignment().

Referenced by SimpleResourceManager::canAssign(), earliestCycle(), and latestCycle().

Here is the call graph for this function:

canTransportImmediate()

bool SimpleBrokerDirector::canTransportImmediate ( const MoveNode &  node, const TTAMachine::Bus *  preAssignedBus  ) const

virtual

Return true if immediate in given node can be transported by some bus in the machine.

Parameters

node	Node that contains immediate read.

Returns

True if immediate in given node can be transported by some bus in the machine.

Exceptions

ModuleRunTimeError

If required resource brokers are not found in assignment plan.

Definition at line 680 of file SimpleBrokerDirector.cc.

                                                                     {
    try {
        BusBroker& broker = busBroker();
        return broker.canTransportImmediate(node, preAssignedBus);
    } catch (const InstanceNotFound& e) {
        throw ModuleRunTimeError(
            __FILE__, __LINE__, __func__, e.errorMessage());
    }
}

References __func__, busBroker(), BusBroker::canTransportImmediate(), and Exception::errorMessage().

Referenced by SimpleResourceManager::canTransportImmediate().

Here is the call graph for this function:

clear()

void SimpleBrokerDirector::clear

(

)

Clears the bookkeeping so that the same RM can be reused for different BB.

After this call the state of the RM should be identical to a new RM.

Definition at line 944 of file SimpleBrokerDirector.cc.

                            {
    knownMaxCycle_ = -1;
    knownMinCycle_ = INT_MAX;
    moveCounts_.clear();
    plan_->clear();
}

References AssignmentPlan::clear(), knownMaxCycle_, knownMinCycle_, moveCounts_, and BrokerDirector::plan_.

Referenced by SimpleResourceManager::clear().

Here is the call graph for this function:

clearOldResources()

void SimpleBrokerDirector::clearOldResources

(

)

Clears bookkeeping which is needed for unassigning previously assigned moves. After this call these cannot be unassigned, but new moves which are assigned after this call can still be unassigned.

Definition at line 913 of file SimpleBrokerDirector.cc.

                                        {
    AssocTools::deleteAllValues(origResMap_);
    immediateUnitBroker().clearOldResources();
    instructionTemplateBroker().clearOldResources();
}

References ITemplateBroker::clearOldResources(), IUBroker::clearOldResources(), AssocTools::deleteAllValues(), immediateUnitBroker(), instructionTemplateBroker(), and origResMap_.

Referenced by SimpleResourceManager::clear(), and SimpleResourceManager::clearOldResources().

Here is the call graph for this function:

earliestCycle() [1/2]

int SimpleBrokerDirector::earliestCycle ( int  cycle, MoveNode &  node, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  ) const

overridevirtual

Return the earliest cycle starting from the given cycle in which required resources can be assigned to given node.

If the node is partially assigned, the manager keeps existing assignments. This means that a client can apply arbitrary constraints to resource allocation.

Parameters

cycle	Cycle to start from.
node	MoveNode.
bus	if not null, bus that has to be used.
srcFU	if not null, srcFu that has to be used.
dstFU	if not null, dstFU that has to be used.
immWriteCycle	if not -1 and src is imm, write cycle of limm.

Returns

The earliest cycle starting from the given cycle in which required resources can be assigned to given node. Returns -1 if assignment is not possible starting from given cycle.

Implements ResourceManager.

Definition at line 487 of file SimpleBrokerDirector.cc.

                                                           {
 
    // limit the scheduling window.
    // makes code for minimal.adf schedule in reasonable time
    if (cycle < knownMaxCycle_ - schedulingWindow_) {
        cycle = knownMaxCycle_ - schedulingWindow_;
    }
    // TODO: is there need for similar test for knownMinCycle as well?
 
    int minCycle = executionPipelineBroker().earliestCycle(
        cycle, node, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
 
    if (minCycle == -1) {
        // No assignment possible
        debugLogRM("No assignment possible from executionPipelineBroker");
        return -1;
    }
 
    minCycle = std::max(minCycle, cycle);
    int lastCycleToTest;
    if (initiationInterval_ != 0) {
        lastCycleToTest = cycle + initiationInterval_ - 2;
    } else {
        lastCycleToTest = largestCycle();
    }
 
    while (!canAssign(minCycle, node, bus, srcFU, dstFU, immWriteCycle, immu,
              immRegIndex)) {
        if (minCycle > lastCycleToTest + 1) {
            // Even on empty instruction it is not possible to assign
            debugLogRM(
                "A problem with ADF, cannot schedule even on "
                "an empty instruction.");
            return -1;
        }
        // find next cycle where exec pipeline could be free,
        // do not test every cycle with canassign.
        minCycle = executionPipelineBroker().earliestCycle(
            minCycle + 1, node, bus, srcFU, dstFU, immWriteCycle, immu,
        immRegIndex);
        if (minCycle == -1) {
            debugLogRM("No assignment possible due to executionPipelineBroker.");
            return -1;
        }
    }
    return minCycle;
}

References canAssign(), debugLogRM, ExecutionPipelineBroker::earliestCycle(), executionPipelineBroker(), initiationInterval_, knownMaxCycle_, largestCycle(), and schedulingWindow_.

Here is the call graph for this function:

earliestCycle() [2/2]

int SimpleBrokerDirector::earliestCycle ( MoveNode &  move, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  ) const

overridevirtual

Return the earliest cycle in the scope where all required resources can be assigned to the given node.

If the node is partially assigned, the manager keeps existing assignments. This means that a client can apply arbitrary constraints to resource allocation.

Parameters

move	The move.
bus	if not null, bus that has to be used.
srcFU	if not null, srcFu that has to be used.
dstFU	if not null, dstFU that has to be used.
immWriteCycle	if not -1 and src is imm, write cycle of limm.

Returns

The earliest cycle in the scope where all required resources can be assigned to the given node. Returns -1 if assignment is not possible starting from given cycle.

Implements ResourceManager.

Definition at line 457 of file SimpleBrokerDirector.cc.

                                                           {
    return earliestCycle(
    0, move, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
}

References earliestCycle().

Referenced by SimpleResourceManager::earliestCycle(), SimpleResourceManager::earliestCycle(), and earliestCycle().

Here is the call graph for this function:

executionPipelineBroker()

ExecutionPipelineBroker & SimpleBrokerDirector::executionPipelineBroker ( ) const

private

Return the execution pipeline broker.

Returns

The execution pipeline broker.

Exceptions

InstanceNotFound

If execution pipeline broker is not found.

Definition at line 756 of file SimpleBrokerDirector.cc.

{
    ResourceBroker* broker = NULL;
    for (int i = 0; i < plan_->brokerCount(); i++) {
        broker = &plan_->broker(i);
        if (broker->isExecutionPipelineBroker()) {
            return dynamic_cast<ExecutionPipelineBroker&>(*broker);
        }
    }
    string msg = "Execution Pipeline broker not found.";
    throw InstanceNotFound(__FILE__, __LINE__, __func__, msg);
}

References __func__, AssignmentPlan::broker(), AssignmentPlan::brokerCount(), ResourceBroker::isExecutionPipelineBroker(), and BrokerDirector::plan_.

Referenced by earliestCycle(), largestCycle(), latestCycle(), setDDG(), and setMaxCycle().

Here is the call graph for this function:

hasGuard()

bool SimpleBrokerDirector::hasGuard ( const MoveNode &  node ) const

virtual

Tests if any of a buses of machine supports guard needed by a node. Should always return true! Otherwise, scheduler generated code for different machine.

Parameters

node	MoveNode to test

Returns

true if any of buses supports guard needed by node, or if move is not conditional.

Definition at line 811 of file SimpleBrokerDirector.cc.

                                                         {
    Move& move = const_cast<MoveNode&>(node).move();
    if (move.isUnconditional()) {
        return true;
    }
    return busBroker().hasGuard(node);
}

References busBroker(), BusBroker::hasGuard(), and TTAProgram::Move::isUnconditional().

Referenced by SimpleResourceManager::hasGuard().

Here is the call graph for this function:

immediateUnitBroker()

IUBroker & SimpleBrokerDirector::immediateUnitBroker ( ) const

private

Return the immediate unit broker.

Returns

The immediate unit broker.

Exceptions

InstanceNotFound

If immediate unit broker is not found.

Definition at line 698 of file SimpleBrokerDirector.cc.

                                                {
    ResourceBroker* broker = NULL;
    for (int i = 0; i < plan_->brokerCount(); i++) {
        broker = &plan_->broker(i);
        if (broker->isIUBroker()) {
            return dynamic_cast<IUBroker&>(*broker);
        }
    }
    string msg = "Immediate unit broker not found.";
    throw InstanceNotFound(__FILE__, __LINE__, __func__, msg);
}

References __func__, AssignmentPlan::broker(), AssignmentPlan::brokerCount(), ResourceBroker::isIUBroker(), and BrokerDirector::plan_.

Referenced by clearOldResources(), immediateValue(), and immediateWriteCycle().

Here is the call graph for this function:

immediateValue()

std::shared_ptr< TTAProgram::TerminalImmediate > SimpleBrokerDirector::immediateValue ( const MoveNode &  node )

virtual

Finds the original terminal with value of immediate.

Parameters

node	node with immediate register source

Returns

terminal with immediate value

Definition at line 883 of file SimpleBrokerDirector.cc.

                                                         {
    return immediateUnitBroker().immediateValue(node);
}

References immediateUnitBroker(), and IUBroker::immediateValue().

Referenced by SimpleResourceManager::immediateValue().

Here is the call graph for this function:

immediateWriteCycle()

int SimpleBrokerDirector::immediateWriteCycle ( const MoveNode &  node ) const

virtual

Finds cycle in which the immediate that is read by node is written.

Parameters

node	with source immediate register

Returns

cycle in which immediate is written to register

Definition at line 894 of file SimpleBrokerDirector.cc.

                                                                    {
    return immediateUnitBroker().immediateWriteCycle(node);
}

References immediateUnitBroker(), and IUBroker::immediateWriteCycle().

Referenced by assign(), SimpleResourceManager::immediateWriteCycle(), and unassign().

Here is the call graph for this function:

instruction()

TTAProgram::Instruction * SimpleBrokerDirector::instruction ( int  cycle ) const

overridevirtual

Returns a copy of instruction that holds a moves for given cycle and has correct template set.

Parameters

cycle

Cycle for which to get instruction

Returns

the Instruction with moves and template assigned

Note

This method should be called when whole scope is scheduled

Implements ResourceManager.

Definition at line 827 of file SimpleBrokerDirector.cc.

                                                 {
    return instructionTemplateBroker().instruction(cycle);
}

References ITemplateBroker::instruction(), and instructionTemplateBroker().

Referenced by assign(), SimpleResourceManager::instruction(), and unassign().

Here is the call graph for this function:

instructionIndex()

unsigned int SimpleBrokerDirector::instructionIndex ( unsigned int  cycle ) const

private

Return the instruction index corresponding to cycle.

If modulo scheduling is not used (ie. initiation interval is 0), then index is equal to cycle.

Parameters

cycle

Cycle to get instruction index.

Returns

Return the instruction index for cycle.

Definition at line 929 of file SimpleBrokerDirector.cc.

                                                               {
 
    if (initiationInterval_ != 0) {
        return cycle % initiationInterval_;
    } else {
        return cycle;
    }
}

References initiationInterval_.

Referenced by assign(), and unassign().

instructionTemplateBroker()

ITemplateBroker & SimpleBrokerDirector::instructionTemplateBroker ( ) const

private

Return the instruction template broker.

Returns

The instruction template broker.

Exceptions

InstanceNotFound

If instruction template broker is not found.

Definition at line 717 of file SimpleBrokerDirector.cc.

                                                      {
 
    ResourceBroker* broker = NULL;
    for (int i = 0; i < plan_->brokerCount(); i++) {
        broker = &plan_->broker(i);
        if (broker->isITemplateBroker()) {
            return dynamic_cast<ITemplateBroker&>(*broker);
        }
    }
    string msg = "Instruction template broker not found.";
    throw InstanceNotFound(__FILE__, __LINE__, __func__, msg);
}

References __func__, AssignmentPlan::broker(), AssignmentPlan::brokerCount(), ResourceBroker::isITemplateBroker(), and BrokerDirector::plan_.

Referenced by clearOldResources(), instruction(), isTemplateAvailable(), and loseInstructionOwnership().

Here is the call graph for this function:

isTemplateAvailable()

bool SimpleBrokerDirector::isTemplateAvailable ( int  defCycle, std::shared_ptr< TTAProgram::Immediate >  immediate  ) const

virtual

Definition at line 899 of file SimpleBrokerDirector.cc.

                                                        {
 
    return instructionTemplateBroker().isTemplateAvailable(
        defCycle, immediate);
}

References instructionTemplateBroker(), and ITemplateBroker::isTemplateAvailable().

Referenced by SimpleResourceManager::isTemplateAvailable().

Here is the call graph for this function:

largestCycle()

int SimpleBrokerDirector::largestCycle ( ) const

overridevirtual

Returns largest cycle known to be used by any of the resources.

Returns

Largest cycle resource manager assigned any resource to.

Implements ResourceManager.

Definition at line 848 of file SimpleBrokerDirector.cc.

                                        {
    return std::max(knownMaxCycle_,
        executionPipelineBroker().highestKnownCycle());
}

References executionPipelineBroker(), and knownMaxCycle_.

Referenced by earliestCycle(), and SimpleResourceManager::largestCycle().

Here is the call graph for this function:

latestCycle() [1/2]

int SimpleBrokerDirector::latestCycle ( int  cycle, MoveNode &  node, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  ) const

overridevirtual

Return the latest cycle starting from the given cycle in which required resources can be assigned to given node.

If the node is partially assigned, the manager keeps existing assignments. This means that a client can apply arbitrary constraints to resource allocation.

Parameters

cycle	Cycle to start from.
node	Node.
bus	if not null, bus that has to be used.
srcFU	if not null, srcFu that has to be used.
dstFU	if not null, dstFU that has to be used.
immWriteCycle	if not -1 and src is imm, write cycle of limm.

Returns

The latest cycle starting from the given cycle in which required resources can be assigned to given node. In case assignment is not possible for given arguments returns -1. Returns INT_MAX if there is no upper boundary for assignment.

Implements ResourceManager.

Definition at line 591 of file SimpleBrokerDirector.cc.

                                                         {
 
#ifdef DEBUG_RM
    std::cerr << "\t\t\t\tLatest cycle called with cycle: " << cycle << std::endl;
#endif
    int maxCycle = executionPipelineBroker().latestCycle(
    cycle, node, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
#ifdef DEBUG_RM
    std::cerr << "\t\t\t\t\tmaxCycle from exec pipeline: " << maxCycle << std::endl;
#endif
    if (maxCycle == -1) {
        // Assignment not possible at all
        return maxCycle;
    }
    if (maxCycle == INT_MAX || maxCycle == INT_MAX - 1) {
        if (cycle == INT_MAX) {
            // There is no upper limit for assignment and it was not set
            // either
            return cycle;
        }
    }
    if (maxCycle > cycle) {
        maxCycle = cycle;
    }
    int lastCycleToTest = -1;
    lastCycleToTest =
        std::max(knownMaxCycle_,
            executionPipelineBroker().highestKnownCycle());
    if (lastCycleToTest == 0) {
        lastCycleToTest = cycle;
    }
#ifdef DEBUG_RM
    std::cerr << "\t\t\t\t\tLast cycle to test: " << lastCycleToTest << std::endl;
#endif
    // Define earliest cycle where to finish testing. If the move can not
    // be scheduled after this cycle, it can not be scheduled at all.            
 
    int knownMinCycle = knownMinCycle_ == INT_MAX ? cycle :
        std::min(cycle,knownMinCycle_);
    int earliestCycleLimit = 
        (knownMinCycle > executionPipelineBroker().longestLatency() + 1) ?
        knownMinCycle - executionPipelineBroker().longestLatency() : 0;
 
#ifdef DEBUG_RM
    std::cerr << "\tknown min cycle: " << knownMinCycle << std::endl;
    std::cerr << "\t\t\t\t\tEarlist limit: " << earliestCycleLimit << std::endl;
#endif
 
    if (maxCycle <= lastCycleToTest) {
        for (int i = maxCycle; i >= earliestCycleLimit; i--) {
            if (canAssign(i, node, bus, srcFU, dstFU, immWriteCycle, immu,
              immRegIndex)) {
                return i;
            }
        }
    } else {
        if (maxCycle > lastCycleToTest) {
            if (canAssign(maxCycle, node, bus, srcFU, dstFU, immWriteCycle,
              immu, immRegIndex)) {
                return maxCycle;
            }
        }        
        for (int i = lastCycleToTest; i >= earliestCycleLimit; i--) {
            if (canAssign(i, node, bus, srcFU, dstFU, immWriteCycle, immu,
              immRegIndex)) {
                return i;
            }
        }
    }
    return -1;
}

References canAssign(), executionPipelineBroker(), knownMaxCycle_, knownMinCycle_, ExecutionPipelineBroker::latestCycle(), and ExecutionPipelineBroker::longestLatency().

Here is the call graph for this function:

latestCycle() [2/2]

int SimpleBrokerDirector::latestCycle ( MoveNode &  node, const TTAMachine::Bus *  bus = nullptr, const TTAMachine::FunctionUnit *  srcFU = nullptr, const TTAMachine::FunctionUnit *  dstFU = nullptr, int  immWriteCycle = -1, const TTAMachine::ImmediateUnit *  immu = nullptr, int  immRegIndex = -1  ) const

overridevirtual

Return the latest cycle in the scope where all required resources can be assigned to the given node.

If the node is partially assigned, the manager keeps existing assignments. This means that a client can apply arbitrary constraints to resource allocation.

Parameters

node	Node.
bus	if not null, bus that has to be used.
srcFU	if not null, srcFu that has to be used.
dstFU	if not null, dstFU that has to be used.
immWriteCycle	if not -1 and src is imm, write cycle of limm.

Returns

The latest cycle in the scope where all required resources can be assigned to the given node. In case assignment is not possible for given arguments returns -1. Returns INT_MAX if there is no upper boundary for assignment.

Implements ResourceManager.

Definition at line 560 of file SimpleBrokerDirector.cc.

                                                         {
    return latestCycle(
    INT_MAX, node, bus, srcFU, dstFU, immWriteCycle, immu, immRegIndex);
}

References latestCycle().

Referenced by SimpleResourceManager::latestCycle(), SimpleResourceManager::latestCycle(), and latestCycle().

Here is the call graph for this function:

loseInstructionOwnership()

void SimpleBrokerDirector::loseInstructionOwnership ( int  cycle )

virtual

Transfer the instruction ownership away from this object.

If this method is called, resource manager does not delete it's instructions when it it destroyed.

Definition at line 872 of file SimpleBrokerDirector.cc.

                                                        {
    instructionTemplateBroker().loseInstructionOwnership(cycle);
}

References instructionTemplateBroker(), and ITemplateBroker::loseInstructionOwnership().

Referenced by SimpleResourceManager::loseInstructionOwnership().

Here is the call graph for this function:

setBBN()

void SimpleBrokerDirector::setBBN

(

const BasicBlockNode *

bbn

)

Definition at line 962 of file SimpleBrokerDirector.cc.

                                                      {
    busBroker().setBBN(bbn);
}

References busBroker(), and BusBroker::setBBN().

Referenced by SimpleResourceManager::setBBN().

Here is the call graph for this function:

setCFG()

void SimpleBrokerDirector::setCFG

(

const ControlFlowGraph *

cfg

)

Definition at line 957 of file SimpleBrokerDirector.cc.

                                                        {
    busBroker().setCFG(cfg);
}

References busBroker(), and BusBroker::setCFG().

Referenced by SimpleResourceManager::setCFG().

Here is the call graph for this function:

setDDG()

void SimpleBrokerDirector::setDDG

(

const DataDependenceGraph *

ddg

)

Definition at line 952 of file SimpleBrokerDirector.cc.

                                                           {
    executionPipelineBroker().setDDG(ddg);
}

References executionPipelineBroker(), and ExecutionPipelineBroker::setDDG().

Referenced by SimpleResourceManager::setDDG().

Here is the call graph for this function:

setMaxCycle()

void SimpleBrokerDirector::setMaxCycle

(

unsigned int

cycle

)

Definition at line 967 of file SimpleBrokerDirector.cc.

                                                       {
    executionPipelineBroker().setMaxCycle(maxCycle);
}

References executionPipelineBroker(), and ExecutionPipelineBroker::setMaxCycle().

Referenced by SimpleResourceManager::setMaxCycle().

Here is the call graph for this function:

smallestCycle()

int SimpleBrokerDirector::smallestCycle ( ) const

overridevirtual

Returns smallest cycle known to be used by any of the resources.

Returns

Smallest cycle resource manager assigned any resource to.

Implements ResourceManager.

Definition at line 859 of file SimpleBrokerDirector.cc.

                                         {
    // No need to check the execution pipeline resource here
    // since there are no negative pipelines
    return knownMinCycle_;
}

References knownMinCycle_.

Referenced by SimpleResourceManager::smallestCycle().

supportsExternalAssignments()

bool SimpleBrokerDirector::supportsExternalAssignments ( ) const

overridevirtual

Defines if Broker Director implementation supports node with resources pre assigned by clients.

Returns

For SimpleBrokerDirector allways false.

Implements ResourceManager.

Definition at line 838 of file SimpleBrokerDirector.cc.

                                                        {
    return false;
}

Referenced by SimpleResourceManager::supportsExternalAssignments().

unassign()

void SimpleBrokerDirector::unassign ( MoveNode &  node )

overridevirtual

Free all resource assignments of the given node.

If the node is only partially assigned, the resource manager ignores those parts of the node that are already unassigned.

Parameters

node	Node to unassign.

Exceptions

InvalidData

If the given node is not placed in any cycle. Assigned but not placed nodes are not considered by the resource manager.

Implements ResourceManager.

Definition at line 340 of file SimpleBrokerDirector.cc.

                                             {
 
    if (!node.isPlaced()) {
        string msg = "Node " + node.toString();
        msg += " is not placed in any cycle.";
        throw InvalidData(__FILE__, __LINE__, __func__, msg);
    }
 
    int nodeCycle = node.cycle();
 
    bool minCycleImmSrc = false;
    if (node.isMove()) {
        if (node.isSourceImmediateRegister() &&
            knownMinCycle_ == immediateWriteCycle(node)) {
            minCycleImmSrc = true;
        }
    }
 
    moveCounts_[instructionIndex(nodeCycle)]--;
 
    plan_->clearCache();
    plan_->resetAssignments(node);
 
    if (node.isMove()) {
        if (!MapTools::containsKey(origResMap_, &node)) {
            abortWithError("Original resources lost!");
        }
        OriginalResources* oldRes = MapTools::valueForKey<OriginalResources*>(
            origResMap_, &node);
    
        // restore original resources of node
        if (!node.move().source().isGPR()) {
            node.move().setSource(oldRes->src_);
        } else {
            delete oldRes->src_;
        }
        oldRes->src_ = NULL;
        if (!node.move().destination().isGPR()) {
            node.move().setDestination(oldRes->dst_);
        } else {
            delete oldRes->dst_;
        }
        oldRes->dst_ = NULL;
        node.move().setBus(*oldRes->bus_);
        if (oldRes->isGuarded_) {
            node.move().setGuard(oldRes->guard_);
            oldRes->guard_ = NULL;
        }
        delete oldRes;
        origResMap_.erase(&node);
    }
    // if unassigned move was known to be in highest cycle assigned so far
    // tries to decrease highest cycle checking for assigned moves and
    // immediates
    int cycleCounter = nodeCycle;
    if (cycleCounter == knownMaxCycle_) {
        while(cycleCounter >= knownMinCycle_) {
            // this may memory leak
            Instruction* tempIns = instruction(cycleCounter);
            if (tempIns->moveCount() == 0 && tempIns->immediateCount() == 0) {
                knownMaxCycle_--;
                cycleCounter--;
            } else {
                break;
            }
        }
        if (knownMaxCycle_ < knownMinCycle_) {
            knownMinCycle_ = INT_MAX;
            knownMaxCycle_ = -1;
        }
    }
    // if unassigned move was known to be in smallest cycle assigned so far
    // tries to increase smallest cycle checking for assigned moves and
    // immediates
    int guardSlack = std::max(0, node.guardLatency() -1);    
    cycleCounter = knownMinCycle_;
    if (cycleCounter == nodeCycle - guardSlack || minCycleImmSrc) {
        while(cycleCounter <= knownMaxCycle_) {
            // this may memory leak
            Instruction* tempIns = instruction(cycleCounter);
            if (tempIns->moveCount() == 0 && tempIns->immediateCount() == 0) {
                knownMinCycle_++;
                cycleCounter++;
            } else {
                for (int i = 0; i < tempIns->moveCount(); i++) {
                    int guardSlack = std::max(0, tempIns->move(i).guardLatency() -1);
                    if (cycleCounter - guardSlack < knownMinCycle_) {
                        knownMinCycle_ = cycleCounter - guardSlack;
#ifdef DEBUG_RM
                        std::cerr << "Set known min cycle(3) to" << knownMinCycle_ << std::endl;
#endif
                    }
                }
                break;
            }
        }
    }
}

References __func__, abortWithError, SimpleBrokerDirector::OriginalResources::bus_, AssignmentPlan::clearCache(), MapTools::containsKey(), MoveNode::cycle(), TTAProgram::Move::destination(), SimpleBrokerDirector::OriginalResources::dst_, SimpleBrokerDirector::OriginalResources::guard_, TTAProgram::Move::guardLatency(), MoveNode::guardLatency(), TTAProgram::Instruction::immediateCount(), immediateWriteCycle(), instruction(), instructionIndex(), TTAProgram::Terminal::isGPR(), SimpleBrokerDirector::OriginalResources::isGuarded_, MoveNode::isMove(), MoveNode::isPlaced(), MoveNode::isSourceImmediateRegister(), MapTools::keyForValue(), knownMaxCycle_, knownMinCycle_, MoveNode::move(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), moveCounts_, origResMap_, BrokerDirector::plan_, AssignmentPlan::resetAssignments(), TTAProgram::Move::setBus(), TTAProgram::Move::setDestination(), TTAProgram::Move::setGuard(), TTAProgram::Move::setSource(), TTAProgram::Move::source(), SimpleBrokerDirector::OriginalResources::src_, and MoveNode::toString().

Referenced by SimpleResourceManager::unassign().

Here is the call graph for this function:

Member Data Documentation

busCount_

int SimpleBrokerDirector::busCount_

private

Definition at line 181 of file SimpleBrokerDirector.hh.

Referenced by canAssign().

initiationInterval_

unsigned int SimpleBrokerDirector::initiationInterval_

private

Definition at line 173 of file SimpleBrokerDirector.hh.

Referenced by canAssign(), earliestCycle(), and instructionIndex().

knownMaxCycle_

int SimpleBrokerDirector::knownMaxCycle_

private

Definition at line 171 of file SimpleBrokerDirector.hh.

Referenced by assign(), clear(), earliestCycle(), largestCycle(), latestCycle(), SimpleBrokerDirector(), and unassign().

knownMinCycle_

int SimpleBrokerDirector::knownMinCycle_

private

Definition at line 172 of file SimpleBrokerDirector.hh.

Referenced by assign(), clear(), latestCycle(), SimpleBrokerDirector(), smallestCycle(), and unassign().

moveCounts_

std::map<int,int> SimpleBrokerDirector::moveCounts_

private

Definition at line 180 of file SimpleBrokerDirector.hh.

Referenced by assign(), canAssign(), clear(), and unassign().

origResMap_

std::map<const MoveNode*, OriginalResources*, MoveNode::Comparator> SimpleBrokerDirector::origResMap_

private

Definition at line 170 of file SimpleBrokerDirector.hh.

Referenced by assign(), clearOldResources(), unassign(), and ~SimpleBrokerDirector().

schedulingWindow_

int SimpleBrokerDirector::schedulingWindow_

private

the number of instructions to look back in the schedule for a free slot

Definition at line 177 of file SimpleBrokerDirector.hh.

Referenced by earliestCycle(), and SimpleBrokerDirector().

---

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

• SimpleBrokerDirector.hh
• SimpleBrokerDirector.cc