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: ff750fdf461d
Choose a base ref
...
head repository: azonenberg/openfpga
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 210bd5bf9fe3
Choose a head ref
  • 2 commits
  • 5 files changed
  • 1 contributor

Commits on Jun 1, 2017

  1. Copy the full SHA
    d50942b View commit details
  2. Copy the full SHA
    210bd5b View commit details
Showing with 332 additions and 30 deletions.
  1. +1 −0 src/gp4tchar/CMakeLists.txt
  2. +2 −1 src/gp4tchar/main.cpp
  3. +64 −29 src/gp4tchar/measurements.cpp
  4. +188 −0 src/gp4tchar/solver.cpp
  5. +77 −0 src/gp4tchar/solver.h
1 change: 1 addition & 0 deletions src/gp4tchar/CMakeLists.txt
Original file line number Diff line number Diff line change
@@ -1,6 +1,7 @@
add_executable(gp4tchar
measurements.cpp
setup.cpp
solver.cpp

TimingData.cpp

3 changes: 2 additions & 1 deletion src/gp4tchar/main.cpp
Original file line number Diff line number Diff line change
@@ -74,7 +74,7 @@ int main(int argc, char* argv[])
}

//Set up logging
g_log_sinks.emplace(g_log_sinks.begin(), new STDLogSink(console_verbosity));
g_log_sinks.emplace(g_log_sinks.begin(), new ColoredSTDLogSink(console_verbosity));

//Connect to the server
if( (server == "") || (port == 0) )
@@ -124,6 +124,7 @@ int main(int argc, char* argv[])
//Measure delay through each element
if(!MeasurePinToPinDelays(sock, hdev))
return 1;

/*
if(!MeasureCrossConnectionDelays(sock, hdev))
return 1;
93 changes: 64 additions & 29 deletions src/gp4tchar/measurements.cpp
Original file line number Diff line number Diff line change
@@ -17,6 +17,7 @@
**********************************************************************************************************************/

#include "gp4tchar.h"
#include "solver.h"

using namespace std;

@@ -25,7 +26,7 @@ Greenpak4Device::GREENPAK4_PART part = Greenpak4Device::GREENPAK4_SLG46620;
Greenpak4IOB::PullDirection unused_pull = Greenpak4IOB::PULL_DOWN;
Greenpak4IOB::PullStrength unused_drive = Greenpak4IOB::PULL_1M;

bool PromptAndMeasureDelay(Socket& sock, int src, int dst, float& delay);
bool PromptAndMeasureDelay(Socket& sock, int src, int dst, float& value);
bool MeasureCrossConnectionDelay(Socket& sock, hdevice hdev, unsigned int matrix, unsigned int index, float& delay);

bool MeasurePinToPinDelay(
@@ -55,41 +56,70 @@ bool CalibrateTraceDelays(Socket& sock, hdevice hdev)
if(!IOSetup(hdev))
return false;

float delay_34;
float delay_35;
float delay_45;
//Set up the variables
KnapsackVariable p3("FPGA pin 3 to DUT rising");
KnapsackVariable p4("FPGA pin 4 to DUT rising");
KnapsackVariable p5("FPGA pin 5 to DUT rising");
KnapsackVariable p13("FPGA pin 13 to DUT rising");
KnapsackVariable p14("FPGA pin 14 to DUT rising");
KnapsackVariable p15("FPGA pin 15 to DUT rising");

float delay_1314;
float delay_1315;
float delay_1415;
//Measure each pair of pins individually
float delay;
if(!PromptAndMeasureDelay(sock, 3, 4, delay))
return false;
KnapsackEquation e1(delay);
e1.AddVariable(p3);
e1.AddVariable(p4);

//Measure A+B, A+C, B+C delays for one side of chip
if(!PromptAndMeasureDelay(sock, 3, 4, delay_34))
if(!PromptAndMeasureDelay(sock, 3, 5, delay))
return false;
if(!PromptAndMeasureDelay(sock, 3, 5, delay_35))
KnapsackEquation e2(delay);
e2.AddVariable(p3);
e2.AddVariable(p5);

if(!PromptAndMeasureDelay(sock, 4, 5, delay))
return false;
if(!PromptAndMeasureDelay(sock, 4, 5, delay_45))
KnapsackEquation e3(delay);
e3.AddVariable(p4);
e3.AddVariable(p5);

if(!PromptAndMeasureDelay(sock, 13, 14, delay))
return false;
KnapsackEquation e4(delay);
e4.AddVariable(p13);
e4.AddVariable(p14);

//and for the other side
if(!PromptAndMeasureDelay(sock, 13, 14, delay_1314))
if(!PromptAndMeasureDelay(sock, 13, 15, delay))
return false;
if(!PromptAndMeasureDelay(sock, 13, 15, delay_1315))
KnapsackEquation e5(delay);
e5.AddVariable(p13);
e5.AddVariable(p15);

if(!PromptAndMeasureDelay(sock, 14, 15, delay))
return false;
if(!PromptAndMeasureDelay(sock, 14, 15, delay_1415))
KnapsackEquation e6(delay);
e6.AddVariable(p14);
e6.AddVariable(p15);

//Solve the system
KnapsackProblem p;
p.AddEquation(e1);
p.AddEquation(e2);
p.AddEquation(e3);
p.AddEquation(e4);
p.AddEquation(e5);
p.AddEquation(e6);
if(!p.Solve())
return false;

//Pin 3 delay = A = ( (A+B) + (A+C) - (B+C) ) / 2 = (delay_34 + delay_35 - delay_45) / 2
g_devkitCal.pinDelays[3] = DelayPair((delay_34 + delay_35 - delay_45) / 2, -1);
g_devkitCal.pinDelays[4] = DelayPair(delay_34 - g_devkitCal.pinDelays[3].rising, -1);
g_devkitCal.pinDelays[5] = DelayPair(delay_35 - g_devkitCal.pinDelays[3].rising, -1);

//Repeat for other side
g_devkitCal.pinDelays[13] = DelayPair((delay_1314 + delay_1315 - delay_1415) / 2, -1);
g_devkitCal.pinDelays[14] = DelayPair(delay_1314 - g_devkitCal.pinDelays[13].rising, -1);
g_devkitCal.pinDelays[15] = DelayPair(delay_1315 - g_devkitCal.pinDelays[13].rising, -1);

//TODO: Falling edges
//Extract the values
g_devkitCal.pinDelays[3] = p3.m_value;
g_devkitCal.pinDelays[4] = p4.m_value;
g_devkitCal.pinDelays[5] = p5.m_value;
g_devkitCal.pinDelays[13] = p13.m_value;
g_devkitCal.pinDelays[14] = p14.m_value;
g_devkitCal.pinDelays[15] = p15.m_value;

//Print results
{
@@ -140,16 +170,16 @@ bool ReadTraceDelays()
return true;
}

bool PromptAndMeasureDelay(Socket& sock, int src, int dst, float& delay)
bool PromptAndMeasureDelay(Socket& sock, int src, int dst, float& value)
{
LogNotice("Use a jumper to short pins %d and %d on the ZIF header\n", src, dst);

LogIndenter li;

WaitForKeyPress();
if(!MeasureDelay(sock, src, dst, delay))
if(!MeasureDelay(sock, src, dst, value))
return false;
LogNotice("Measured pin-to-pin delay: %.3f ns\n", delay);
LogNotice("Measured pin-to-pin: %.3f ns\n", value);
return true;
}

@@ -297,6 +327,11 @@ bool MeasurePinToPinDelay(
//Get the delay
if(!ProgramAndMeasureDelay(sock, hdev, bitstream, src, dst, delay))
return false;

//Subtract the PCB trace delay at each end of the line
delay -= g_devkitCal.pinDelays[src].rising;
delay -= g_devkitCal.pinDelays[dst].rising;

return true;
}

188 changes: 188 additions & 0 deletions src/gp4tchar/solver.cpp
Original file line number Diff line number Diff line change
@@ -0,0 +1,188 @@
/***********************************************************************************************************************
* Copyright (C) 2016-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) *
* any later version. *
* *
* This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied *
* warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for *
* more details. *
* *
* You should have received a copy of the GNU Lesser General Public License along with this program; if not, you may *
* find one here: *
* https://www.gnu.org/licenses/old-licenses/lgpl-2.1.txt *
* or you may search the http://www.gnu.org website for the version 2.1 license, or you may write to the Free Software *
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA *
**********************************************************************************************************************/

#include "gp4tchar.h"
#include "solver.h"

using namespace std;

void PrintMatrix(float** rows, int numVars, int numEq);

bool KnapsackProblem::Solve()
{
//Create mapping of variables to column IDs
map<KnapsackVariable*, int> colmap;
map<int, string> nmap;
int numVars = 0;
for(auto e : m_equations)
{
for(auto v : e->m_variables)
{
//already have it
if(colmap.find(v) != colmap.end())
continue;

//nope, allocate new ID
nmap[numVars] = v->m_name;
colmap[v] = numVars;
numVars ++;

//LogNotice("Variable %d = %s\n", colmap[v], v->m_name.c_str());
}
}

//Sanity check
int numEq = m_equations.size();
if(numEq < numVars)
{
LogError("Cannot solve knapsack problem: more variables than equations\n");
return false;
}

//Create the matrix
//Column numVars is the sum
float** rows = new float*[numEq];
int j = 0;
for(auto e : m_equations)
{
//Clear coefficients to zero in case some are missing
float* row = new float[numVars + 1];
for(int i=0; i<numVars; i++)
row[i] = 0;

//Add variables (coefficient of 1 to start)
for(auto v : e->m_variables)
row[colmap[v]] = 1;

//Patch in the sum
row[numVars] = e->m_sum;

rows[j++] = row;
}

//Print out the matrix
//LogNotice("Solving system of %d equations in %d unknowns\n", numEq, numVars);
//PrintMatrix(rows, numEq, numVars);

//Do the actual Gaussian elimination to produce an upper triangle matrix
float epsilon = 0.000001f;
for(int nvar = 0; nvar < numVars; nvar ++)
{
//If we have a 0 at our diagonal location, look down until we find a row that has a nonzero value
if(rows[nvar][nvar] < epsilon)
{
bool found = false;
for(int row=nvar+1; row<numEq; row ++)
{
if(rows[row][nvar] > epsilon)
{
//LogNotice("Swapping rows %d and %d\n", row, nvar);
float* tmp = rows[nvar];
rows[nvar] = rows[row];
rows[row] = tmp;
found = true;
break;
}
}

if(!found)
{
LogError("Cannot solve for variable %d (%s)\n", nvar, nmap[nvar].c_str());
return false;
}
}

//If we don't have a 1 at our corner cell, divide everything by that
if( fabs(rows[nvar][nvar] - 1) > epsilon )
{
float scale = 1.0f / rows[nvar][nvar];
//LogNotice("Multiplying row %d by %.3f\n", nvar, scale);
for(int i=0; i<= numVars; i++)
rows[nvar][i] *= scale;
}

//Subtract us (multiplied, if necessary) from any rows below us
//in order to produce an upper triangle matrix
for(int row=nvar+1; row<numEq; row++)
{
//It's already zero, skip it
float rowval = rows[row][nvar];
if(fabs(rowval) < epsilon)
continue;

//Multiply us by that value, then subtract
//LogNotice("Subtracting %.3f * row %d from row %d\n", rowval, nvar, row);
for(int i=0; i <= numVars; i++)
rows[row][i] -= rows[nvar][i] * rowval;
}

//LogNotice("Variable %d done\n", nvar);
//PrintMatrix(rows, numVars, numEq);
}

//Back-substitute to solve the remaining variables
//Last row should already be in (x = y) form, so start one row above that
//LogNotice("Back-substitution\n");
for(int row = numVars - 2; row >= 0; row --)
{
//Remove all of the variables right of the diagonal
for(int nvar = row + 1; nvar < numVars; nvar ++)
{
float rowval = rows[row][nvar];
if(fabs(rowval) > epsilon)
{
//LogNotice("Subtracting %.3f * row %d from row %d\n", rowval, nvar, row);
for(int i=0; i <= numVars; i++)
rows[row][i] -= rows[nvar][i] * rowval;
}
}

//LogNotice("Variable %d done\n", row);
//PrintMatrix(rows, numVars, numEq);
}

//Print out final state
//LogNotice("Final state\n");
//PrintMatrix(rows, numVars, numEq);

//Export matrix to the rows
for(auto it : colmap)
it.first->m_value = rows[it.second][numVars];

//clean up
for(int i=0; i<numEq; i++)
delete[] rows[i];
delete[] rows;

return true;
}

void PrintMatrix(float** rows, int numVars, int numEq)
{
for(int row=0; row<numEq; row++)
{
LogNotice(" ");
for(int col=0; col <= numVars; col++)
{
if(col == numVars)
LogNotice(" | ");
LogNotice("%6.3f ", rows[row][col]);
}
LogNotice("\n");
}
}
Loading