ResourceConstraintAnalyzer Class Reference

#include <ResourceConstraintAnalyzer.hh>

Collaboration diagram for ResourceConstraintAnalyzer:

Public Member Functions
	ResourceConstraintAnalyzer (DataDependenceGraph &ddg, SimpleResourceManager &rm, TCEString graphName)
virtual	~ResourceConstraintAnalyzer ()
void	analyzePreSchedule ()
bool	analyze ()

Private Types
typedef std::map< std::string, int >	RFCountMap
typedef std::map< std::string, int >	OperationCountMap

Private Member Functions
bool	analyzeRegisterAntideps (DataDependenceGraph &ddg, std::ostream &s)
bool	analyzeMoveNode (const MoveNode &node)
MoveNode *	findResourceConstrainedParent (MoveNode *child)
void	optimalScheduleResourceUsage (DataDependenceGraph &ddg, TCEString graphName)
void	memoryBoundScheduleResourceUsage (DataDependenceGraph &ddg, TCEString graphName)
void	dumpGraphWithStats (DataDependenceGraph &ddg, TCEString dotFileName, const std::map< int, std::list< MoveNode * > > &schedule)

Private Attributes
int	busConstrained_
int	operationConstrained_
int	rfWritePortConstrained_
int	rfReadPortConstrained_
int	minScheduleLength_
int	unknownConstrained_
RFCountMap	writePortConstrainedRfs_
RFCountMap	readPortConstrainedRfs_
OperationCountMap	operationConstrainedMoves_
DataDependenceGraph &	origDDG_
SimpleResourceManager &	rm_
std::set< MoveNode * >	foundMoves_
TCEString	graphName_

Detailed Description

A class that analyzes the most important resource constraints in the given scheduled basic block DDG.

Definition at line 49 of file ResourceConstraintAnalyzer.hh.

Member Typedef Documentation

OperationCountMap

typedef std::map<std::string, int> ResourceConstraintAnalyzer::OperationCountMap

private

Definition at line 80 of file ResourceConstraintAnalyzer.hh.

RFCountMap

typedef std::map<std::string, int> ResourceConstraintAnalyzer::RFCountMap

private

Definition at line 79 of file ResourceConstraintAnalyzer.hh.

Constructor & Destructor Documentation

ResourceConstraintAnalyzer()

ResourceConstraintAnalyzer::ResourceConstraintAnalyzer ( DataDependenceGraph &  ddg, SimpleResourceManager &  rm, TCEString  graphName  )

inline

Definition at line 51 of file ResourceConstraintAnalyzer.hh.

                             : 
        origDDG_(ddg), rm_(rm), graphName_(graphName) {}

~ResourceConstraintAnalyzer()

virtual ResourceConstraintAnalyzer::~ResourceConstraintAnalyzer ( )

inlinevirtual

Definition at line 56 of file ResourceConstraintAnalyzer.hh.

{}

Member Function Documentation

analyze()

bool ResourceConstraintAnalyzer::analyze

(

)

Analyzes the resource constraints in the schedule.

Returns

true in case at least one resource or dep constrained move found. Thus always true in case the schedule is "perfect".

Definition at line 62 of file ResourceConstraintAnalyzer.cc.

                                    {
 
    origDDG_.setProgramOperationNodes(true);
    optimalScheduleResourceUsage(origDDG_, graphName_);  
 
    origDDG_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    DataDependenceGraph* criticalPath = origDDG_.criticalPathGraph();
    criticalPath->setProgramOperationNodes(true);
    origDDG_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
    optimalScheduleResourceUsage(*criticalPath, graphName_ + ".critical_path");  
    delete criticalPath; criticalPath = NULL;
 
    DataDependenceGraph* memDeps = origDDG_.memoryDependenceGraph();
    memDeps->setProgramOperationNodes(true);
    memDeps->writeToDotFile(graphName_ + ".mem_deps.dot");
    delete memDeps; memDeps = NULL;
 
    return true;
#if 0
    // TODO: finish the more intelligent iterative search for resource bottlenecks
 
    busConstrained_ = 0;
    operationConstrained_ = 0;
    rfWritePortConstrained_ = 0;
    rfReadPortConstrained_ = 0;
    unknownConstrained_ = 0;
    writePortConstrainedRfs_.clear();
    readPortConstrainedRfs_.clear();
    operationConstrainedMoves_.clear();
    origDDG_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    // only sensible basic block with 1 cycle is one with only
    // reg moves or a store, ignore those
    minScheduleLength_ = std::max(origDDG__.height(), 2);
    origDDG_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
 
 
    const int cycleCount = ddg_.largestCycle() + 1;
    const int nodes = ddg_.nodeCount();
 
    /*
 
      Collect the resource constrained moves that are lengthening the 
      schedule over the critical path length.
 
      Picks up all moves in the instructions > critical path length and
      "climbs" up the dependency tree and collects the first resource
      constrained move found (we use top-down scheduling) that is 
      above the minimum schedule length.
    
      The idea is try to "lift the resource constrained DDG tree 
      upwards" to try to bring the late moves within the minimum 
      schedule length.
 
      What if there's no such move? If all the moves in the tree
      are after the minimum schedule? In that case some other path is
      limiting the schedule thus we should just ignore the move and look
      at other moves.
 
      Should we scan all cycles or just the first cycle after the min
      cycle? We might add too many resources in case the bottleneck is
      resolved at the first cycle. I guess we should scan until we find
      *one* such move? Solving its resource constraint could lead to
      removing a bottleneck so whenever we scan more than one move there's 
      a risk of adding extra resources that do not really contribute to the
      schedule length as the constraint might have been solved by the 
      single move's bottleneck. This leads to many evaluation iterations but
      I guess it's better than to waste resources. Might add some kind of
      parameter for controlling the maximum number of constrained moves 
      to find per iteration.
 
    */
    int maxMovesToFind = 4;
    foundMoves_.clear();
    resourceConstrained_ = 0;
    for (int cycle = minScheduleLength_;
         cycle < cycleCount && resourceConstrained_ < maxMovesToFind; ++cycle) {
        DataDependenceGraph::NodeSet moves = ddg_.movesAtCycle(cycle);
        for (DataDependenceGraph::NodeSet::iterator m = moves.begin(); 
             m != moves.end() && resourceConstrained_ < maxMovesToFind; ++m) {
            MoveNode* node = findResourceConstrainedParent(*m);
            if (node != NULL) {
                Application::logStream() 
                    << "found a schedule constraining move: " 
                    << node->move().toString() << " at cycle " 
                    << node->cycle() << " earliest DDG cycle " 
                    << ddg_.earliestCycle(*node) << std::endl;
                ++resourceConstrained_;
            }
        }
    }
 
    if (true || resourceConstrained_ > 0) {
 
#if 0
        ddg_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
 
        // print out the instructions
        for (int c = 0; c < cycleCount; ++c) {
            Application::logStream() << c << ": ";
            DataDependenceGraph::NodeSet moves = ddg_.movesAtCycle(c);
            for (DataDependenceGraph::NodeSet::iterator m = moves.begin(); 
                 m != moves.end(); ++m) {
                MoveNode& mn = **m;
//                if (!ddg_.isInCriticalPath(mn) && !mn.move().isJump())
//                    continue;
                Application::logStream() << mn.move().toString();
                Application::logStream() << " ";
            }
            Application::logStream() << std::endl;
        }
        ddg_.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
#endif
 
        Application::logStream() << "cycles: " << cycleCount << std::endl;
            
        Application::logStream() 
            << "minimum: " << minScheduleLength_ << " (from DDG longest path)"
            << std::endl;
 
        Application::logStream() 
            << "at least " 
            << resourceConstrained_ << " of " << nodes
            << " were resource constrained:" << std::endl;
        if (busConstrained_ > 0) {
            Application::logStream() 
                << busConstrained_ << " bus (move slot) constrained" 
                << std::endl;
        }
 
        if (rfReadPortConstrained_ > 0) {
            Application::logStream()             
                << rfReadPortConstrained_ << " RF read port constrained ";
            for (RFCountMap::const_iterator rfi = 
                     readPortConstrainedRfs_.begin(); 
                 rfi != readPortConstrainedRfs_.end(); ++rfi) {
                Application::logStream() 
                    << (*rfi).first << ": " << (*rfi).second << "  ";
            }
            Application::logStream() << std::endl;                
        }
 
        if (rfWritePortConstrained_ > 0) {
            Application::logStream() 
                << std::endl
                << rfWritePortConstrained_ << " RF write port constrained ";
            for (RFCountMap::const_iterator rfi = 
                     writePortConstrainedRfs_.begin(); 
                 rfi != writePortConstrainedRfs_.end(); ++rfi) {
                Application::logStream() 
                    << (*rfi).first << ": " << (*rfi).second << "  ";
            }
            Application::logStream() << std::endl;                
        }
 
        if (operationConstrained_ > 0) {
            Application::logStream() 
                << std::endl
                << operationConstrained_ 
                << " operation (FU) constrained ";
            for (OperationCountMap::const_iterator rfi = 
                     operationConstrainedMoves_.begin(); 
                 rfi != operationConstrainedMoves_.end(); ++rfi) {
                Application::logStream() 
                    << (*rfi).first << ": " << (*rfi).second << "  ";
            }
            Application::logStream() << std::endl;
        }
        Application::logStream() << std::endl;
        return true;
    }
 
    return regAntidepsFound;
#endif
}

References busConstrained_, DataDependenceGraph::criticalPathGraph(), MoveNode::cycle(), DataDependenceGraph::EWH_DEFAULT, DataDependenceGraph::EWH_REAL, findResourceConstrainedParent(), foundMoves_, graphName_, Application::logStream(), DataDependenceGraph::memoryDependenceGraph(), minScheduleLength_, MoveNode::move(), operationConstrained_, operationConstrainedMoves_, optimalScheduleResourceUsage(), origDDG_, readPortConstrainedRfs_, rfReadPortConstrained_, rfWritePortConstrained_, DataDependenceGraph::setEdgeWeightHeuristics(), DataDependenceGraph::setProgramOperationNodes(), TTAProgram::Move::toString(), unknownConstrained_, writePortConstrainedRfs_, and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by BBSchedulerController::executeDDGPass().

Here is the call graph for this function:

analyzeMoveNode()

bool ResourceConstraintAnalyzer::analyzeMoveNode ( const MoveNode &  node )

private

Analyzes the resource constraints of a single move in the schedule.

Returns

true in case the move is resource constrained.

Definition at line 717 of file ResourceConstraintAnalyzer.cc.

                                                                {
 
    // moves at cycle 0 cannot be scheduled earlier
    if (node.cycle() == 0)
        return false;
 
    int ddgEarliestCycle = origDDG_.earliestCycle(node);
    if (ddgEarliestCycle == node.cycle()) 
        return false;
 
    if (node.move().isJump()) {
        Application::logStream() 
            << "earliest cycle for JUMP: " << ddgEarliestCycle << std::endl;
        // JUMP cannot be scheduled earlier than the
        // schedule length - delay slots, they always have a fixed position
        // in the BB
        return false;
    }
 
    // operation latency
    // look for the triggering operand and see if it's less
    // than the latency away
    if (node.isSourceOperation()) {
        ProgramOperation& op = node.sourceOperation();
        MoveNode& trigger = *op.triggeringMove();
        MoveNode& opcodeSetting = op.opcodeSettingNode();
        int latency = 
            (dynamic_cast<TTAProgram::TerminalFUPort&>(
                opcodeSetting.move().destination())).hwOperation()->
            latency();
        if (node.cycle() == trigger.cycle() + latency) {
            return false;
        } 
    }
 
    const TTAMachine::Machine& targetMachine = origDDG_.machine();
 
    // check the instruction the move should have been scheduled at, 
    // resources permitting
    TTAProgram::Instruction* prevInstr = rm_.instruction(ddgEarliestCycle);
 
    const int busCount = targetMachine.busNavigator().count();
    // is it bus constrained? 
    if (prevInstr->moveCount() == busCount) {
        // it might be true or we just managed to find a different move 
        // to fill the unused slot later during scheduling
        ++busConstrained_;
        return true;
    }
 
    // RF read port constrained?
    if (node.move().source().isGPR()) {
        int readsFound = 0;
        for (int m = 0; m < prevInstr->moveCount(); ++m) {
            TTAProgram::Move& prevMove = prevInstr->move(m);
            if (prevMove.source().isGPR() && 
                &node.move().source().registerFile() ==
                &prevMove.source().registerFile()) {
                ++readsFound;
            }
        }
        if (readsFound == 
            node.move().source().registerFile().maxReads()) {
            ++rfReadPortConstrained_;
            readPortConstrainedRfs_[
                node.move().source().registerFile().name()]++;
            return true;
        }
    }
 
    // RF read port constrained?
    if (node.move().destination().isGPR()) {
        int writesFound = 0;
        for (int m = 0; m < prevInstr->moveCount(); ++m) {
            TTAProgram::Move& prevMove = prevInstr->move(m);
            if (prevMove.destination().isGPR() && 
                &node.move().destination().registerFile() ==
                &prevMove.destination().registerFile()) {
                ++writesFound;
            }
        }
        if (writesFound == 
            node.move().destination().registerFile().maxWrites()) {
            ++rfWritePortConstrained_;
            writePortConstrainedRfs_[
                node.move().destination().registerFile().name()]++;
            return true;
        }
    }
 
    // assume rest are FU constrained somehow (might be untrue in general,
    // but with a fully connected machine a good approximation)
    if (node.isDestinationOperation()) {
        // if it's a trigger node, it can be contrained by an operand move, 
        // a dependency which is not recorded by the DDG
        bool operandConstrained = false;
        if (node.move().isTriggering()) {
            ProgramOperation& po = node.destinationOperation();
            for (int input = 0; (input < po.inputMoveCount()) && 
                     !operandConstrained; ++input) {
                
                const MoveNode& operandMove = po.inputMove(input);
                
                if (&operandMove == &node)
                    continue;
 
                if (operandMove.cycle() == node.cycle()) {
                    operandConstrained = true;
                    break;
                }
            }
        }
 
        if (!operandConstrained) {
            ++operationConstrained_;
            TCEString opName = node.destinationOperation().operation().name();
#if 0
            Application::logStream()
                << opName << " constrained: "
                << node.move().toString() << std::endl;
#endif
            operationConstrainedMoves_[opName]++;
            return true;
        } else if (operandConstrained){
            return false; // operand depedency is constrained by the trigger
        }
    }
 
    unknownConstrained_++;
    Application::logStream()
        << std::endl
        << "resource set constrained move of unknown reason: " 
        << node.toString() << std::endl;
    if (node.isSourceOperation()) {
        ProgramOperation& op = node.sourceOperation();
        Application::logStream()
            << "ProgramOperation: " << op.toString() << std::endl;
    }
    Application::logStream() 
        << "earliest cycle: " << origDDG_.earliestCycle(node)
        << std::endl;
 
    
    for (int c = 3; c >= 0; --c) {
        int printCycle = node.cycle() - c;
        if (printCycle > 0) {
            Application::logStream()
                << printCycle << ": "
                << rm_.instruction(printCycle)->toString()
                << std::endl;
        }
    }
    return true;    
}

References busConstrained_, TTAMachine::Machine::busNavigator(), TTAMachine::Machine::Navigator< ComponentType >::count(), MoveNode::cycle(), TTAProgram::Move::destination(), MoveNode::destinationOperation(), DataDependenceGraph::earliestCycle(), ProgramOperation::inputMove(), ProgramOperation::inputMoveCount(), SimpleResourceManager::instruction(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isGPR(), TTAProgram::Move::isJump(), MoveNode::isSourceOperation(), TTAProgram::Move::isTriggering(), Application::logStream(), DataDependenceGraph::machine(), TTAMachine::RegisterFile::maxReads(), TTAMachine::RegisterFile::maxWrites(), MoveNode::move(), TTAProgram::Instruction::move(), TTAProgram::Instruction::moveCount(), TTAMachine::Component::name(), Operation::name(), ProgramOperation::opcodeSettingNode(), ProgramOperation::operation(), operationConstrained_, operationConstrainedMoves_, origDDG_, readPortConstrainedRfs_, TTAProgram::Terminal::registerFile(), rfReadPortConstrained_, rfWritePortConstrained_, rm_, TTAProgram::Move::source(), MoveNode::sourceOperation(), TTAProgram::Instruction::toString(), TTAProgram::Move::toString(), MoveNode::toString(), ProgramOperation::toString(), ProgramOperation::triggeringMove(), unknownConstrained_, and writePortConstrainedRfs_.

Referenced by findResourceConstrainedParent().

Here is the call graph for this function:

analyzePreSchedule()

void ResourceConstraintAnalyzer::analyzePreSchedule

(

)

Definition at line 50 of file ResourceConstraintAnalyzer.cc.

                                               {
    origDDG_.setProgramOperationNodes(true);
    memoryBoundScheduleResourceUsage(origDDG_, graphName_);  
}

References graphName_, memoryBoundScheduleResourceUsage(), origDDG_, and DataDependenceGraph::setProgramOperationNodes().

Referenced by BBSchedulerController::executeDDGPass().

Here is the call graph for this function:

analyzeRegisterAntideps()

bool ResourceConstraintAnalyzer::analyzeRegisterAntideps ( DataDependenceGraph &  ddg, std::ostream &  s  )

private

Analyzes the register antideps in the schedule.

Returns

true in case at least one move that was constrained by a register antidep which could be avoided with additional registers or better register assignment strategy was found.

Definition at line 560 of file ResourceConstraintAnalyzer.cc.

                                             {
 
    s << "schedule length: " << ddg.largestCycle() - ddg.smallestCycle() << std::endl;
   
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    s << "DDG height: " << ddg.height() << std::endl;
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
    DataDependenceGraph* trueDepGraph = ddg.trueDependenceGraph(false);
    trueDepGraph->setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    s << "DDG height without register antideps: " 
      << trueDepGraph->height() << std::endl;
 
    trueDepGraph->writeToDotFile((boost::format("%s.tddg_noreg.dot") % graphName_).str());
 
    DataDependenceGraph* trueDepGraph2 = ddg.trueDependenceGraph(true);
    trueDepGraph2->setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    s << "DDG height without any antideps: " 
      << trueDepGraph2->height() << std::endl;
 
    trueDepGraph2->writeToDotFile(
        (boost::format("%s.tddg_noantidep_.dot") % graphName_).str());
    delete trueDepGraph2; 
 
    DataDependenceGraph* trueDepGraph3 = ddg.trueDependenceGraph(true, true);
    trueDepGraph3->setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    s << "DDG height without any antideps and memory deps: " 
      << trueDepGraph3->height() << std::endl;
 
    trueDepGraph3->writeToDotFile(
        (boost::format("%s.tddg_noantidep_nonmemdep.dot") % graphName_).str());
 
    delete trueDepGraph3; 
 
    std::map<int, int> foundCounts;
 
    bool restrictingEdgeFound = false;
 
    for (int i = 0; i < ddg.nodeCount(); i++) {
        MoveNode& tail = ddg.node(i);
        for (int e = 0; e < ddg.outDegree(tail); ++e) {
            DataDependenceEdge& edge = ddg.outEdge(tail,e);
            // only consider non-loop register false deps here
            if (!edge.isFalseDep() ||
                edge.edgeReason() != DataDependenceEdge::EDGE_REGISTER ||
                edge.loopDepth() > 0)
                continue;
            MoveNode& head = ddg.headNode(edge);
            // if there is a *real* dependency path from the tail to head 
            // than the given antidep then it does not help if we rename 
            // the register
            if (trueDepGraph->hasPath(tail, head))
                continue;
 
            // TODO: figure out why the exception gets thrown (see trunk
            // Bug 517) and remove the try catch
            try {
 
            if (edge.dependenceType() == DataDependenceEdge::DEP_WAR) {
                if (tail.move().source().isGPR()) {
                    foundCounts[tail.move().source().registerFile().width()]++;
                } else if (dynamic_cast<const TTAMachine::RegisterGuard*>(
                               &tail.move().guard().guard())) {
                    const TTAMachine::RegisterGuard* g =
                        dynamic_cast<const TTAMachine::RegisterGuard*>(
                            &tail.move().guard().guard());
                    foundCounts[g->registerFile()->width()]++;
                } else {
                    Application::logStream() 
                        << "WARNING: not a GPR: " 
                        << tail.move().toString() << std::endl;
                }
            } else {
                if (tail.move().destination().isGPR()) {
                    foundCounts[tail.move().destination().registerFile().width()]++;
                } else {
                    Application::logStream() 
                        << "WARNING: not a GPR: " 
                        << tail.move().toString() << std::endl;
                }
            }
 
            s << "Limiting antidep: from " 
              << tail.toString() << " to " << head.toString() << " ("
              << edge.toString() << ")"
              << std::endl;
 
 
            } catch (const Exception& e) {
                // just skip this for now, have to take a look why
                // there are some extra R_G_war edges, example:
                // ERROR: Move is not predicated. Edge R_G_war:bool.0 
                // between moves: 32 -> add_sub_2.in1t.add eq_gt_gtu.out1 -> bool.0
                if (Application::verboseLevel() > 0) {
                    Application::logStream() 
                        << "ERROR: " << e.errorMessage() << " "
                        << "Edge " << edge.toString() << " between moves: "
                        << tail.move().toString() << " "
                        << head.move().toString() << std::endl;
                }
                continue;
                    
            }
        }
    }
    for (std::map<int, int>::iterator i = foundCounts.begin(); 
         i != foundCounts.end(); ++i) {
        int foundCount = (*i).second;
        int bitWidth = (*i).first;
        s << "found " << foundCount << " " << bitWidth << " bit "
          << " register antideps that restrict parallelism" << std::endl;
 
    }
    delete trueDepGraph; 
    return restrictingEdgeFound;
}

References DataDependenceEdge::DEP_WAR, DataDependenceEdge::dependenceType(), TTAProgram::Move::destination(), DataDependenceEdge::EDGE_REGISTER, DataDependenceEdge::edgeReason(), Exception::errorMessage(), DataDependenceGraph::EWH_DEFAULT, DataDependenceGraph::EWH_REAL, graphName_, TTAProgram::Move::guard(), TTAProgram::MoveGuard::guard(), BoostGraph< GraphNode, GraphEdge >::hasPath(), BoostGraph< GraphNode, GraphEdge >::headNode(), BoostGraph< GraphNode, GraphEdge >::height(), DataDependenceEdge::isFalseDep(), TTAProgram::Terminal::isGPR(), DataDependenceGraph::largestCycle(), Application::logStream(), DataDependenceEdge::loopDepth(), MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), TTAMachine::RegisterGuard::registerFile(), TTAProgram::Terminal::registerFile(), DataDependenceGraph::setEdgeWeightHeuristics(), DataDependenceGraph::smallestCycle(), TTAProgram::Move::source(), DataDependenceEdge::toString(), TTAProgram::Move::toString(), MoveNode::toString(), DataDependenceGraph::trueDependenceGraph(), Application::verboseLevel(), TTAMachine::BaseRegisterFile::width(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by dumpGraphWithStats().

Here is the call graph for this function:

dumpGraphWithStats()

void ResourceConstraintAnalyzer::dumpGraphWithStats ( DataDependenceGraph &  ddg, TCEString  dotFileName, const std::map< int, std::list< MoveNode * > > &  schedule  )

private

Definition at line 241 of file ResourceConstraintAnalyzer.cc.

                                                      {
 
    std::ofstream s(dotFileName.c_str());
 
    s << "digraph ddg {" << std::endl;
 
 
    s << "/*" << std::endl << "### dependence constraints: " << std::endl << std::endl;
 
    analyzeRegisterAntideps(ddg, s);
 
    int smallestCycle = (*schedule.begin()).first;
    int largestCycle = (*schedule.rbegin()).first;
 
    // record stats of operationA -> operationB bypasses to guide
    // IC customization
    typedef std::map<std::pair<TCEString, TCEString>, int> BypassMap;
 
    typedef std::map<TCEString, int> OpCountMap;
    OpCountMap maxParallelOps;
    // The operation mix. I.e., the static occurence of operations
    // in the code.
    OpCountMap operationMix;
    BypassMap bypasses;
 
    /* In the critical path DDGs, the trigger nodes might be
       missing. In that case we use the operand node to record
       the operation usage cycle. This set is used to ensure the
       same operation is not recorded more than once. */
    std::set<ProgramOperation*> recordedOps;
 
    for (int c = smallestCycle; c <= largestCycle; ++c) {
        if (schedule.find(c) == schedule.end()) continue;
        std::list<MoveNode*> moves = (*schedule.find(c)).second;
        if (moves.size() == 0) continue;
 
        std::map<TCEString, int> parallelOpsAtCycle;
        for (std::list<MoveNode*>::iterator i = moves.begin(); 
             i != moves.end(); ++i) {
            MoveNode& n = **i;        
            TCEString opName = "";
 
            if (n.isBypass()) {
                std::pair<TCEString, TCEString> key =
                    std::make_pair(
                        n.sourceOperation().operation().name(),
                        n.destinationOperation().operation().name());
                bypasses[key]++;
            }
 
            if (n.isDestinationOperation()) {
                ProgramOperation& op = n.destinationOperation();
                if (!AssocTools::containsKey(recordedOps, &op)) {
                    opName = op.operation().name();
                    operationMix[opName]++;
                    parallelOpsAtCycle[opName]++;
                    recordedOps.insert(&op);
                }
            }
        }
 
        for (OpCountMap::const_iterator i = parallelOpsAtCycle.begin();
             i != parallelOpsAtCycle.end(); ++i) {
            TCEString opName = (*i).first;
            int count = (*i).second;
            maxParallelOps[opName] = 
                std::max(maxParallelOps[opName], count);
        }
    }
 
    s << std::endl;
    s << "### resource statistics: " << std::endl << std::endl;
 
    const int COL_WIDTH = 14;
    // print statistics of the graph as a comment
    s << std::setw(COL_WIDTH) << std::right << "operation stats: ";
    s << std::endl << std::endl;
        
    for (OpCountMap::const_iterator i = maxParallelOps.begin();
         i != maxParallelOps.end(); ++i) {
        TCEString opName = (*i).first;
        int parCount = (*i).second;
        int total = operationMix[opName];
        s << std::setw(COL_WIDTH) << std::right 
          << opName + ": ";
        s << std::setw(COL_WIDTH) << std::right 
          << total;
        s << " total, " << std::setw(COL_WIDTH) << std::right 
          << parCount << " at most in parallel" << std::endl;
    }
 
    s << std::endl;
    // print statistics of the graph as a comment
    s << std::setw(COL_WIDTH) << std::right << "bypass stats: ";
    s << std::endl << std::endl;
    
    for (BypassMap::const_iterator i = bypasses.begin(); 
         i != bypasses.end(); ++i) {
        std::pair<TCEString, TCEString> opPair = (*i).first;
        int count = (*i).second;
        s << std::setw(COL_WIDTH) << std::right 
          << opPair.first + " -> " + opPair.second + ": ";
        s << std::setw(COL_WIDTH) << std::right 
          << count << std::endl;
    }
 
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
 
    s << std::endl << "### moves not at the earliest cycles:" << std::endl << std::endl;
    for (int i = 0; i < ddg.nodeCount(); ++i) {
        MoveNode& n = ddg.node(i);
        // Constant writes always report 0 for the src distance. 
        if (n.isSourceConstant()) continue; 
        int ddgEarliest = ddg.maxSourceDistance(n);
        if (n.cycle() > ddgEarliest)
            s << n.toString() << " (" << n.cycle() << " > " << ddgEarliest << ")" << std::endl;
    }
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
    s << std::endl << "*/" << std::endl << std::endl;
 
    // print the DDG itself
 
    // print the "time line" to visualize the schedule
    s << "\t{" << std::endl
      << "\t\tnode [shape=plaintext];" << std::endl
      << "\t\t";
    for (int c = smallestCycle; c <= largestCycle; ++c) {
        s << "\"cycle " << c << "\" -> ";
    }
    s << "\"cycle " << largestCycle + 1 << "\"; " 
      << std::endl << "\t}" << std::endl;
    
    // print the nodes
    for (int c = smallestCycle; c <= largestCycle; ++c) {
        if (schedule.find(c) == schedule.end()) continue;
        std::list<MoveNode*> moves = (*schedule.find(c)).second;
        if (moves.size() == 0) continue;
        s << "\t{ rank = same; \"cycle " << c << "\"; ";
        for (std::list<MoveNode*>::iterator i = moves.begin(); 
             i != moves.end(); ++i) {
            MoveNode& n = **i;        
            s << "n" << n.nodeID() << "; ";
        }
        s << "}" << std::endl;    
    }
 
    // first print all the nodes and their properties
    for (int i = 0; i < ddg.nodeCount(); ++i) {
        MoveNode& n = ddg.node(i);
        s << "\tn" << n.nodeID()
          << " [" << n.dotString() << "]; " 
          << std::endl;
    }
 
    // edges
    for (int count = ddg.edgeCount(), i = 0; i < count ; ++i) {
        DataDependenceEdge& e = ddg.edge(i);
        MoveNode& tail = ddg.tailNode(e);
        MoveNode& head = ddg.headNode(e);
 
        s << "\tn" << tail.nodeID() << " -> n" 
          << head.nodeID() << "[" 
          << e.dotString() << "];" << std::endl;
    }
 
    s << "}" << std::endl;   
 
    s.close();
}

References analyzeRegisterAntideps(), AssocTools::containsKey(), MoveNode::cycle(), MoveNode::destinationOperation(), GraphEdge::dotString(), MoveNode::dotString(), BoostGraph< GraphNode, GraphEdge >::edge(), BoostGraph< GraphNode, GraphEdge >::edgeCount(), DataDependenceGraph::EWH_DEFAULT, DataDependenceGraph::EWH_REAL, BoostGraph< GraphNode, GraphEdge >::headNode(), MoveNode::isBypass(), MoveNode::isDestinationOperation(), MoveNode::isSourceConstant(), BoostGraph< GraphNode, GraphEdge >::maxSourceDistance(), Operation::name(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), GraphNode::nodeID(), ProgramOperation::operation(), DataDependenceGraph::setEdgeWeightHeuristics(), MoveNode::sourceOperation(), BoostGraph< GraphNode, GraphEdge >::tailNode(), and MoveNode::toString().

Referenced by memoryBoundScheduleResourceUsage(), and optimalScheduleResourceUsage().

Here is the call graph for this function:

findResourceConstrainedParent()

MoveNode * ResourceConstraintAnalyzer::findResourceConstrainedParent ( MoveNode *  child )

private

Finds a move that is a (grand)parent of the given move (or the move itself) and constraints the schedule, that is, could be scheduled before the minimum schedule length in case a resource constraint was removed.

A recursive function.

Returns

a found parent or NULL if not found in that subtree.

Definition at line 688 of file ResourceConstraintAnalyzer.cc.

                                                                         {
 
 
    if (child == NULL || !child->isMove())
        return NULL;
 
    int ddgEarliestCycle = origDDG_.earliestCycle(*child);
    if (ddgEarliestCycle < minScheduleLength_ &&  
        foundMoves_.find(child) == foundMoves_.end() &&
        analyzeMoveNode(*child)) {
        return child;
    } else {
        DataDependenceGraph::NodeSet parents = origDDG_.predecessors(*child);
        for (DataDependenceGraph::NodeSet::const_iterator p = parents.begin();
             p != parents.end(); ++p) {
            MoveNode* mn = *p;
            if (findResourceConstrainedParent(mn) != NULL)
                return mn;
        }
    }
    return NULL;
}

References analyzeMoveNode(), DataDependenceGraph::earliestCycle(), findResourceConstrainedParent(), foundMoves_, MoveNode::isMove(), minScheduleLength_, origDDG_, and BoostGraph< GraphNode, GraphEdge >::predecessors().

Referenced by analyze(), and findResourceConstrainedParent().

Here is the call graph for this function:

memoryBoundScheduleResourceUsage()

void ResourceConstraintAnalyzer::memoryBoundScheduleResourceUsage ( DataDependenceGraph &  ddg, TCEString  graphName  )

private

Analyses the program based on a memory resource constrained schedule.

Produces statistics of maximum number of parallel operations that can be potentially utilized given that there's only a fixed number of parallel memory operations allowed.

Definition at line 466 of file ResourceConstraintAnalyzer.cc.

                                                   {
 
    TCEString dotFileName = graphName + ".memory_bound_optimal_schedule.dot";
 
    int maxMemOpsPerCycle = 2;
    std::map<int, std::list<MoveNode*> > schedule;
    std::map<int, std::list<ProgramOperationPtr> > operationSchedule;
 
    // Maximum number of parallel operations of the given name.    
    std::map<TCEString, unsigned> maxParallelOps;
 
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
 
    CriticalPathBBMoveNodeSelector selector(ddg, ddg.machine());
 
    Application::logStream()
        << "### analyzing " << graphName << std::endl;
 
    // Produce the "operation schedule" where we assume there are enough
    // interconnection and RF port resources to invoke the required operations
    // in parallel. 
    MoveNodeGroup cands = selector.candidates();
 
    while (cands.nodeCount() > 0) {
        if (cands.nodeCount() > 1) {
            ProgramOperationPtr po = cands.programOperationPtr();
            const Operation& op = po->operation();
            // Schedule the triggering move first and at the earliest position,
            // rest of the nodes can fall in to cycles based on the DDG. Assume
            // operand 1 is always the triggering. 
            for (auto mn : po->inputNode(1)) {
                int cycle = ddg.earliestCycle(
                    *mn, UINT_MAX, false, false, false, false, false, true);
                int memOpsInCycle = 0; 
                do {
                    if (!op.usesMemory()) break;
                    // Assuming placing the current mem OP to the cycle.
                    memOpsInCycle = 1;
                    // Count the number of memory operations already triggered 
                    // on the planned cycle.
                    for (auto otherOp : operationSchedule[cycle]) {
                        if (otherOp->operation().usesMemory())
                            memOpsInCycle++;
                    }
                    if (memOpsInCycle > maxMemOpsPerCycle) {
                        Application::logStream()
                            << "would get " << memOpsInCycle 
                            << " mem operations in cycle " << cycle 
                            << std::endl;
                        ++cycle;
                    }
                } while (memOpsInCycle > maxMemOpsPerCycle);
                mn->setCycle(cycle);
                schedule[cycle].push_back(mn);
                operationSchedule[cycle].push_back(po);
                Application::logStream() 
                    << "placed operation trigger " << mn->toString() << std::endl; 
                selector.notifyScheduled(*mn);
            }
        } 
        for (int n = 0; n < cands.nodeCount(); ++n) {
            MoveNode& mn = cands.node(n);
            if (mn.isPlaced()) continue;
            int cycle = ddg.earliestCycle(
                mn, UINT_MAX, false, false, false, false, false, true);
            mn.setCycle(cycle);
            schedule[cycle].push_back(&mn);
            Application::logStream() 
                << "placed mn " << mn.toString() << std::endl; 
            selector.notifyScheduled(mn);
        }
        
        cands = selector.candidates();
    }
    dumpGraphWithStats(ddg, dotFileName, schedule);
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
    // Unschedule the nodes so the actual scheduler that might be ran
    // after this analysis does not get confused.
    for (auto n : ddg.scheduledMoves()) {
        n->unsetCycle();
    }
}

References CriticalPathBBMoveNodeSelector::candidates(), dumpGraphWithStats(), DataDependenceGraph::earliestCycle(), DataDependenceGraph::EWH_DEFAULT, DataDependenceGraph::EWH_REAL, MoveNode::isPlaced(), Application::logStream(), DataDependenceGraph::machine(), MoveNodeGroup::node(), MoveNodeGroup::nodeCount(), CriticalPathBBMoveNodeSelector::notifyScheduled(), MoveNodeGroup::programOperationPtr(), DataDependenceGraph::scheduledMoves(), MoveNode::setCycle(), DataDependenceGraph::setEdgeWeightHeuristics(), MoveNode::toString(), and Operation::usesMemory().

Referenced by analyzePreSchedule().

Here is the call graph for this function:

optimalScheduleResourceUsage()

void ResourceConstraintAnalyzer::optimalScheduleResourceUsage ( DataDependenceGraph &  ddg, TCEString  graphName  )

private

Analyses the program based on a non-resource constrained schedule.

Produces statistics of maximum number of parallel operations that can be potentially utilized.

Todo:

this is incomplete as the operand to trigger edges are missing, thus the analysis results are likely to be false.

Definition at line 424 of file ResourceConstraintAnalyzer.cc.

                                                   {
 
    ddg.writeToDotFile(graphName + ".dot");
 
    TCEString dotFileName = graphName + ".optimal_schedule.dot";
    
    std::map<int, std::list<MoveNode*> > schedule;
 
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_REAL);
    for (int nc = 0; nc < ddg.nodeCount(); ++nc) {
        MoveNode& n = ddg.node(nc);
        int cycle = ddg.maxSourceDistance(n);
        // immediate operand moves always get cycle 0, fix this by
        // assuming the cycle is the same as the latest other operand
        // move (at least one of them must be a non-immediate move)
        if (n.isDestinationOperation() && 
            n.move().source().isImmediate()) {
            for (int input = 0; 
                 input < n.destinationOperation().inputMoveCount();
                 ++input) {
                MoveNode& inputMove = 
                    n.destinationOperation().inputMove(input);
                if (&inputMove == &n) continue;
                cycle = std::max(cycle, ddg.maxSourceDistance(inputMove));
            }
        }
        schedule[cycle].push_back(&n);
    }
    ddg.setEdgeWeightHeuristics(DataDependenceGraph::EWH_DEFAULT);
 
    dumpGraphWithStats(ddg, dotFileName, schedule);
}

References MoveNode::destinationOperation(), dumpGraphWithStats(), DataDependenceGraph::EWH_DEFAULT, DataDependenceGraph::EWH_REAL, ProgramOperation::inputMove(), MoveNode::isDestinationOperation(), TTAProgram::Terminal::isImmediate(), BoostGraph< GraphNode, GraphEdge >::maxSourceDistance(), MoveNode::move(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), DataDependenceGraph::setEdgeWeightHeuristics(), TTAProgram::Move::source(), and GraphBase< GraphNode, GraphEdge >::writeToDotFile().

Referenced by analyze().

Here is the call graph for this function:

Member Data Documentation

busConstrained_

int ResourceConstraintAnalyzer::busConstrained_

private

Definition at line 82 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

foundMoves_

std::set<MoveNode*> ResourceConstraintAnalyzer::foundMoves_

private

Definition at line 97 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and findResourceConstrainedParent().

graphName_

TCEString ResourceConstraintAnalyzer::graphName_

private

Definition at line 99 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), analyzePreSchedule(), and analyzeRegisterAntideps().

minScheduleLength_

int ResourceConstraintAnalyzer::minScheduleLength_

private

Definition at line 86 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and findResourceConstrainedParent().

operationConstrained_

int ResourceConstraintAnalyzer::operationConstrained_

private

Definition at line 83 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

operationConstrainedMoves_

OperationCountMap ResourceConstraintAnalyzer::operationConstrainedMoves_

private

Definition at line 92 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

origDDG_

DataDependenceGraph& ResourceConstraintAnalyzer::origDDG_

private

Definition at line 94 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), analyzeMoveNode(), analyzePreSchedule(), and findResourceConstrainedParent().

readPortConstrainedRfs_

RFCountMap ResourceConstraintAnalyzer::readPortConstrainedRfs_

private

Definition at line 90 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

rfReadPortConstrained_

int ResourceConstraintAnalyzer::rfReadPortConstrained_

private

Definition at line 85 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

rfWritePortConstrained_

int ResourceConstraintAnalyzer::rfWritePortConstrained_

private

Definition at line 84 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

rm_

SimpleResourceManager& ResourceConstraintAnalyzer::rm_

private

Definition at line 95 of file ResourceConstraintAnalyzer.hh.

Referenced by analyzeMoveNode().

unknownConstrained_

int ResourceConstraintAnalyzer::unknownConstrained_

private

Definition at line 87 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

writePortConstrainedRfs_

RFCountMap ResourceConstraintAnalyzer::writePortConstrainedRfs_

private

Definition at line 89 of file ResourceConstraintAnalyzer.hh.

Referenced by analyze(), and analyzeMoveNode().

---

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

• ResourceConstraintAnalyzer.hh
• ResourceConstraintAnalyzer.cc