Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: azonenberg/openfpga
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: a224e5c22968
Choose a base ref
...
head repository: azonenberg/openfpga
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: be7a0da92cc5
Choose a head ref
  • 3 commits
  • 3 files changed
  • 1 contributor

Commits on May 21, 2017

  1. Added a large scoring penalty to designs which are unroutable because…

    … of excessive cross-connection usage
    azonenberg committed May 21, 2017
    Copy the full SHA
    adb46fb View commit details
  2. Copy the full SHA
    a941d48 View commit details
  3. xbpar: Now correctly revert to older, better placements after we spen…

    …d a while barking up the wrong tree. Fixes #23.
    azonenberg committed May 21, 2017
    Copy the full SHA
    be7a0da View commit details
Showing with 83 additions and 19 deletions.
  1. +6 −3 src/gp4par/Greenpak4PAREngine.cpp
  2. +70 −15 src/xbpar/PAREngine.cpp
  3. +7 −1 src/xbpar/PAREngine.h
9 changes: 6 additions & 3 deletions src/gp4par/Greenpak4PAREngine.cpp
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/***********************************************************************************************************************
* Copyright (C) 2016 Andrew Zonenberg and contributors *
* Copyright (C) 2017 Andrew Zonenberg and contributors *
* *
* This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General *
* Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) *
@@ -199,8 +199,11 @@ uint32_t Greenpak4PAREngine::ComputeCongestionCost()
}

//Squaring each half makes minimizing the larger one more important
//vs if we just summed
return sqrt(costs[0]*costs[0] + costs[1]*costs[1]);
//vs if we just summed. Also add in a fixed penalty if we are using >100% resources
uint32_t cost = sqrt(costs[0]*costs[0] + costs[1]*costs[1]);
if( (costs[0] > 10) || (costs[1] > 10) )
cost += 20;
return cost;
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
85 changes: 70 additions & 15 deletions src/xbpar/PAREngine.cpp
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/***********************************************************************************************************************
* Copyright (C) 2016 Andrew Zonenberg and contributors *
* Copyright (C) 2017 Andrew Zonenberg and contributors *
* *
* This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General *
* Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) *
@@ -48,7 +48,7 @@ PAREngine::~PAREngine()
bool PAREngine::PlaceAndRoute(map<uint32_t, string> label_names, uint32_t seed)
{
LogVerbose("\nXBPAR initializing...\n");
m_temperature = 100;
m_temperature = 250;

//TODO: glibc rand sucks, replace with something a bit more random
//(this may not make a difference for a device this tiny though)
@@ -68,33 +68,49 @@ bool PAREngine::PlaceAndRoute(map<uint32_t, string> label_names, uint32_t seed)

uint32_t iteration = 0;
vector<PARGraphEdge*> unroutes;
uint32_t best_cost = 1000000;
uint32_t best_cost = 0xffffffff;
uint32_t time_since_best_cost = 0;
bool made_change = true;
uint32_t newcost = 0;
while(m_temperature > 0)
while(m_temperature > 1)
{
//Cool the system down
//TODO: Decide on a good rate for this?
m_temperature --;

//Figure out how good we are now.
//Don't recompute the cost if we didn't accept the last iteration's changes
if(made_change)
newcost = ComputeAndPrintScore(unroutes, iteration);
time_since_best_cost ++;
iteration ++;

//If cost is zero, stop now - we found a satisfactory placement!
if(newcost == 0)
break;
LogIndenter li;

//If the new placement is better than our previous record, make a note of that
if(newcost < best_cost)
{
best_cost = newcost;
time_since_best_cost = 0;
SaveNewBestPlacement();
}

//If we failed to improve placement after ten iterations it's hopeless, give up
//if(time_since_best_cost > 10)
// break;
//If cost is zero, stop now - we found a satisfactory placement!
if(newcost == 0)
break;

//If we failed to improve placement after a long while we might be stuck in a local minimum
//Revert to the best score found to date
const int false_path_max = 25;
if(time_since_best_cost > false_path_max)
{
LogVerbose("No improvements for %d iterations on current path, restarting from previous best\n",
false_path_max);
RestorePreviousBestPlacement();
time_since_best_cost = 0;
made_change = true;
continue;
}

//Find the set of nodes in the netlist that we can optimize
//If none were found, give up
@@ -105,10 +121,21 @@ bool PAREngine::PlaceAndRoute(map<uint32_t, string> label_names, uint32_t seed)

//Try to optimize the placement more
made_change = OptimizePlacement(badnodes, label_names);
}

//Cool the system down
//TODO: Decide on a good rate for this?
m_temperature --;
//If the current score is worse than the previous best, revert to the optimal placement
if(newcost > best_cost)
{
RestorePreviousBestPlacement();

//Sanity check that the score was changed
newcost = ComputeCost();
LogVerbose("Final placement score is %d\n", newcost);
if(newcost != best_cost)
{
LogError("Revert failed (new cost doesn't match previous best)\n");
return false;
}
}

//Check for any remaining unroutable nets
@@ -238,9 +265,39 @@ bool PAREngine::InitialPlacement(map<uint32_t, string>& label_names)
}
}

//We haven't done anything, so the current placement must be the best we've found to date
SaveNewBestPlacement();

return true;
}

/**
@brief Saves the current placement as the best placement yet
*/
void PAREngine::SaveNewBestPlacement()
{
uint32_t n = m_netlist->GetNumNodes();
for(uint32_t i=0; i<n; i++)
{
auto node = m_netlist->GetNodeByIndex(i);
m_bestPlacementFound[node] = node->GetMate();
}
LogVerbose("Found new optimal placement\n");
}

void PAREngine::RestorePreviousBestPlacement()
{
LogVerbose("Restoring previous optimal placement\n");

//Apply the new placement
uint32_t n = m_netlist->GetNumNodes();
for(uint32_t i=0; i<n; i++)
{
auto node = m_netlist->GetNodeByIndex(i);
node->MateWith(m_bestPlacementFound[node]);
}
}

/**
@brief Iteratively refine the placement until we can't get any better.
@@ -252,8 +309,6 @@ bool PAREngine::OptimizePlacement(
vector<PARGraphNode*>& badnodes,
map<uint32_t, string>& label_names)
{
LogIndenter li;

//Pick one of the nodes at random as our pivot node
PARGraphNode* pivot = badnodes[rand() % badnodes.size()];

8 changes: 7 additions & 1 deletion src/xbpar/PAREngine.h
Original file line number Diff line number Diff line change
@@ -1,5 +1,5 @@
/***********************************************************************************************************************
* Copyright (C) 2016 Andrew Zonenberg and contributors *
* Copyright (C) 2017 Andrew Zonenberg and contributors *
* *
* This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General *
* Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) *
@@ -66,6 +66,12 @@ class PAREngine
PARGraph* m_netlist;
PARGraph* m_device;

//Best solution found so far
std::map<PARGraphNode*, PARGraphNode*> m_bestPlacementFound;

void SaveNewBestPlacement();
void RestorePreviousBestPlacement();

uint32_t m_temperature;
};