modules/glshared/glsCalibration.cpp

   1 /*-------------------------------------------------------------------------
   2  * drawElements Quality Program OpenGL (ES) Module
   3  * -----------------------------------------------
   4  *
   5  * Copyright 2014 The Android Open Source Project
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  *//*!
  20  * \file
  21  * \brief Calibration tools.
  22  *//*--------------------------------------------------------------------*/
  23
  24 #include "glsCalibration.hpp"
  25 #include "tcuTestLog.hpp"
  26 #include "tcuVectorUtil.hpp"
  27 #include "deStringUtil.hpp"
  28 #include "deMath.h"
  29 #include "deClock.h"
  30
  31 #include <algorithm>
  32 #include <limits>
  33
  34 using std::string;
  35 using std::vector;
  36 using tcu::Vec2;
  37 using tcu::TestLog;
  38 using tcu::TestNode;
  39 using namespace glu;
  40
  41 namespace deqp
  42 {
  43 namespace gls
  44 {
  45
  46 // Reorders input arbitrarily, linear complexity and no allocations
  47 template<typename T>
  48 float destructiveMedian (vector<T>& data)
  49 {
  50         const typename vector<T>::iterator mid = data.begin()+data.size()/2;
  51
  52         std::nth_element(data.begin(), mid, data.end());
  53
  54         if (data.size()%2 == 0) // Even number of elements, need average of two centermost elements
  55                 return (*mid + *std::max_element(data.begin(), mid))*0.5f; // Data is partially sorted around mid, mid is half an item after center
  56         else
  57                 return *mid;
  58 }
  59
  60 LineParameters theilSenLinearRegression (const std::vector<tcu::Vec2>& dataPoints)
  61 {
  62         const float             epsilon                                 = 1e-6f;
  63
  64         const int               numDataPoints                   = (int)dataPoints.size();
  65         vector<float>   pairwiseCoefficients;
  66         vector<float>   pointwiseOffsets;
  67         LineParameters  result                                  (0.0f, 0.0f);
  68
  69         // Compute the pairwise coefficients.
  70         for (int i = 0; i < numDataPoints; i++)
  71         {
  72                 const Vec2& ptA = dataPoints[i];
  73
  74                 for (int j = 0; j < i; j++)
  75                 {
  76                         const Vec2& ptB = dataPoints[j];
  77
  78                         if (de::abs(ptA.x() - ptB.x()) > epsilon)
  79                                 pairwiseCoefficients.push_back((ptA.y() - ptB.y()) / (ptA.x() - ptB.x()));
  80                 }
  81         }
  82
  83         // Find the median of the pairwise coefficients.
  84         // \note If there are no data point pairs with differing x values, the coefficient variable will stay zero as initialized.
  85         if (!pairwiseCoefficients.empty())
  86                 result.coefficient = destructiveMedian(pairwiseCoefficients);
  87
  88         // Compute the offsets corresponding to the median coefficient, for all data points.
  89         for (int i = 0; i < numDataPoints; i++)
  90                 pointwiseOffsets.push_back(dataPoints[i].y() - result.coefficient*dataPoints[i].x());
  91
  92         // Find the median of the offsets.
  93         // \note If there are no data points, the offset variable will stay zero as initialized.
  94         if (!pointwiseOffsets.empty())
  95                 result.offset = destructiveMedian(pointwiseOffsets);
  96
  97         return result;
  98 }
  99
 100 // Sample from given values using linear interpolation at a given position as if values were laid to range [0, 1]
 101 template <typename T>
 102 static float linearSample (const std::vector<T>& values, float position)
 103 {
 104         DE_ASSERT(position >= 0.0f);
 105         DE_ASSERT(position <= 1.0f);
 106
 107         const int       maxNdx                          = (int)values.size() - 1;
 108         const float     floatNdx                        = (float)maxNdx * position;
 109         const int       lowerNdx                        = (int)deFloatFloor(floatNdx);
 110         const int       higherNdx                       = lowerNdx + (lowerNdx == maxNdx ? 0 : 1); // Use only last element if position is 1.0
 111         const float     interpolationFactor = floatNdx - (float)lowerNdx;
 112
 113         DE_ASSERT(lowerNdx >= 0 && lowerNdx < (int)values.size());
 114         DE_ASSERT(higherNdx >= 0 && higherNdx < (int)values.size());
 115         DE_ASSERT(interpolationFactor >= 0 && interpolationFactor < 1.0f);
 116
 117         return tcu::mix((float)values[lowerNdx], (float)values[higherNdx], interpolationFactor);
 118 }
 119
 120 LineParametersWithConfidence theilSenSiegelLinearRegression (const std::vector<tcu::Vec2>& dataPoints, float reportedConfidence)
 121 {
 122         DE_ASSERT(!dataPoints.empty());
 123
 124         // Siegel's variation
 125
 126         const float                                             epsilon                         = 1e-6f;
 127         const int                                               numDataPoints           = (int)dataPoints.size();
 128         std::vector<float>                              medianSlopes;
 129         std::vector<float>                              pointwiseOffsets;
 130         LineParametersWithConfidence    result;
 131
 132         // Compute the median slope via each element
 133         for (int i = 0; i < numDataPoints; i++)
 134         {
 135                 const tcu::Vec2&        ptA             = dataPoints[i];
 136                 std::vector<float>      slopes;
 137
 138                 slopes.reserve(numDataPoints);
 139
 140                 for (int j = 0; j < numDataPoints; j++)
 141                 {
 142                         const tcu::Vec2& ptB = dataPoints[j];
 143
 144                         if (de::abs(ptA.x() - ptB.x()) > epsilon)
 145                                 slopes.push_back((ptA.y() - ptB.y()) / (ptA.x() - ptB.x()));
 146                 }
 147
 148                 // Add median of slopes through point i
 149                 medianSlopes.push_back(destructiveMedian(slopes));
 150         }
 151
 152         DE_ASSERT(!medianSlopes.empty());
 153
 154         // Find the median of the pairwise coefficients.
 155         std::sort(medianSlopes.begin(), medianSlopes.end());
 156         result.coefficient = linearSample(medianSlopes, 0.5f);
 157
 158         // Compute the offsets corresponding to the median coefficient, for all data points.
 159         for (int i = 0; i < numDataPoints; i++)
 160                 pointwiseOffsets.push_back(dataPoints[i].y() - result.coefficient*dataPoints[i].x());
 161
 162         // Find the median of the offsets.
 163         std::sort(pointwiseOffsets.begin(), pointwiseOffsets.end());
 164         result.offset = linearSample(pointwiseOffsets, 0.5f);
 165
 166         // calculate confidence intervals
 167         result.coefficientConfidenceLower = linearSample(medianSlopes, 0.5f - reportedConfidence*0.5f);
 168         result.coefficientConfidenceUpper = linearSample(medianSlopes, 0.5f + reportedConfidence*0.5f);
 169
 170         result.offsetConfidenceLower = linearSample(pointwiseOffsets, 0.5f - reportedConfidence*0.5f);
 171         result.offsetConfidenceUpper = linearSample(pointwiseOffsets, 0.5f + reportedConfidence*0.5f);
 172
 173         result.confidence = reportedConfidence;
 174
 175         return result;
 176 }
 177
 178 bool MeasureState::isDone (void) const
 179 {
 180         return (int)frameTimes.size() >= maxNumFrames || (frameTimes.size() >= 2 &&
 181                                                                                                           frameTimes[frameTimes.size()-2] >= (deUint64)frameShortcutTime &&
 182                                                                                                           frameTimes[frameTimes.size()-1] >= (deUint64)frameShortcutTime);
 183 }
 184
 185 deUint64 MeasureState::getTotalTime (void) const
 186 {
 187         deUint64 time = 0;
 188         for (int i = 0; i < (int)frameTimes.size(); i++)
 189                 time += frameTimes[i];
 190         return time;
 191 }
 192
 193 void MeasureState::clear (void)
 194 {
 195         maxNumFrames            = 0;
 196         frameShortcutTime       = std::numeric_limits<float>::infinity();
 197         numDrawCalls            = 0;
 198         frameTimes.clear();
 199 }
 200
 201 void MeasureState::start (int maxNumFrames_, float frameShortcutTime_, int numDrawCalls_)
 202 {
 203         frameTimes.clear();
 204         frameTimes.reserve(maxNumFrames_);
 205         maxNumFrames            = maxNumFrames_;
 206         frameShortcutTime       = frameShortcutTime_;
 207         numDrawCalls            = numDrawCalls_;
 208 }
 209
 210 TheilSenCalibrator::TheilSenCalibrator (void)
 211         : m_params      (1 /* initial calls */, 10 /* calibrate iter frames */, 2000.0f /* calibrate iter shortcut threshold */, 31 /* max calibration iterations */,
 212                                  1000.0f/30.0f /* target frame time */, 1000.0f/60.0f /* frame time cap */, 1000.0f /* target measure duration */)
 213         , m_state       (INTERNALSTATE_LAST)
 214 {
 215         clear();
 216 }
 217
 218 TheilSenCalibrator::TheilSenCalibrator (const CalibratorParameters& params)
 219         : m_params      (params)
 220         , m_state       (INTERNALSTATE_LAST)
 221 {
 222         clear();
 223 }
 224
 225 TheilSenCalibrator::~TheilSenCalibrator()
 226 {
 227 }
 228
 229 void TheilSenCalibrator::clear (void)
 230 {
 231         m_measureState.clear();
 232         m_calibrateIterations.clear();
 233         m_state = INTERNALSTATE_CALIBRATING;
 234 }
 235
 236 void TheilSenCalibrator::clear (const CalibratorParameters& params)
 237 {
 238         m_params = params;
 239         clear();
 240 }
 241
 242 TheilSenCalibrator::State TheilSenCalibrator::getState (void) const
 243 {
 244         if (m_state == INTERNALSTATE_FINISHED)
 245                 return STATE_FINISHED;
 246         else
 247         {
 248                 DE_ASSERT(m_state == INTERNALSTATE_CALIBRATING || !m_measureState.isDone());
 249                 return m_measureState.isDone() ? STATE_RECOMPUTE_PARAMS : STATE_MEASURE;
 250         }
 251 }
 252
 253 void TheilSenCalibrator::recordIteration (deUint64 iterationTime)
 254 {
 255         DE_ASSERT((m_state == INTERNALSTATE_CALIBRATING || m_state == INTERNALSTATE_RUNNING) && !m_measureState.isDone());
 256         m_measureState.frameTimes.push_back(iterationTime);
 257
 258         if (m_state == INTERNALSTATE_RUNNING && m_measureState.isDone())
 259                 m_state = INTERNALSTATE_FINISHED;
 260 }
 261
 262 void TheilSenCalibrator::recomputeParameters (void)
 263 {
 264         DE_ASSERT(m_state == INTERNALSTATE_CALIBRATING);
 265         DE_ASSERT(m_measureState.isDone());
 266
 267         // Minimum and maximum acceptable frame times.
 268         const float             minGoodFrameTimeUs      = m_params.targetFrameTimeUs * 0.95f;
 269         const float             maxGoodFrameTimeUs      = m_params.targetFrameTimeUs * 1.15f;
 270
 271         const int               numIterations           = (int)m_calibrateIterations.size();
 272
 273         // Record frame time.
 274         if (numIterations > 0)
 275         {
 276                 m_calibrateIterations.back().frameTime = (float)((double)m_measureState.getTotalTime() / (double)m_measureState.frameTimes.size());
 277
 278                 // Check if we're good enough to stop calibrating.
 279                 {
 280                         bool endCalibration = false;
 281
 282                         // Is the maximum calibration iteration limit reached?
 283                         endCalibration = endCalibration || (int)m_calibrateIterations.size() >= m_params.maxCalibrateIterations;
 284
 285                         // Do a few past iterations have frame time in acceptable range?
 286                         {
 287                                 const int numRelevantPastIterations = 2;
 288
 289                                 if (!endCalibration && (int)m_calibrateIterations.size() >= numRelevantPastIterations)
 290                                 {
 291                                         const CalibrateIteration* const         past                    = &m_calibrateIterations[m_calibrateIterations.size() - numRelevantPastIterations];
 292                                         bool                                                            allInGoodRange  = true;
 293
 294                                         for (int i = 0; i < numRelevantPastIterations && allInGoodRange; i++)
 295                                         {
 296                                                 const float frameTimeUs = past[i].frameTime;
 297                                                 if (!de::inRange(frameTimeUs, minGoodFrameTimeUs, maxGoodFrameTimeUs))
 298                                                         allInGoodRange = false;
 299                                         }
 300
 301                                         endCalibration = endCalibration || allInGoodRange;
 302                                 }
 303                         }
 304
 305                         // Do a few past iterations have similar-enough call counts?
 306                         {
 307                                 const int numRelevantPastIterations = 3;
 308                                 if (!endCalibration && (int)m_calibrateIterations.size() >= numRelevantPastIterations)
 309                                 {
 310                                         const CalibrateIteration* const         past                    = &m_calibrateIterations[m_calibrateIterations.size() - numRelevantPastIterations];
 311                                         int                                                                     minCallCount    = std::numeric_limits<int>::max();
 312                                         int                                                                     maxCallCount    = std::numeric_limits<int>::min();
 313
 314                                         for (int i = 0; i < numRelevantPastIterations; i++)
 315                                         {
 316                                                 minCallCount = de::min(minCallCount, past[i].numDrawCalls);
 317                                                 maxCallCount = de::max(maxCallCount, past[i].numDrawCalls);
 318                                         }
 319
 320                                         if ((float)(maxCallCount - minCallCount) <= (float)minCallCount * 0.1f)
 321                                                 endCalibration = true;
 322                                 }
 323                         }
 324
 325                         // Is call count just 1, and frame time still way too high?
 326                         endCalibration = endCalibration || (m_calibrateIterations.back().numDrawCalls == 1 && m_calibrateIterations.back().frameTime > m_params.targetFrameTimeUs*2.0f);
 327
 328                         if (endCalibration)
 329                         {
 330                                 const int       minFrames                       = 10;
 331                                 const int       maxFrames                       = 60;
 332                                 int                     numMeasureFrames        = deClamp32(deRoundFloatToInt32(m_params.targetMeasureDurationUs / m_calibrateIterations.back().frameTime), minFrames, maxFrames);
 333
 334                                 m_state = INTERNALSTATE_RUNNING;
 335                                 m_measureState.start(numMeasureFrames, m_params.calibrateIterationShortcutThreshold, m_calibrateIterations.back().numDrawCalls);
 336                                 return;
 337                         }
 338                 }
 339         }
 340
 341         DE_ASSERT(m_state == INTERNALSTATE_CALIBRATING);
 342
 343         // Estimate new call count.
 344         {
 345                 int newCallCount;
 346
 347                 if (numIterations == 0)
 348                         newCallCount = m_params.numInitialCalls;
 349                 else
 350                 {
 351                         vector<Vec2> dataPoints;
 352                         for (int i = 0; i < numIterations; i++)
 353                         {
 354                                 if (m_calibrateIterations[i].numDrawCalls == 1 || m_calibrateIterations[i].frameTime > m_params.frameTimeCapUs*1.05f) // Only account for measurements not too near the cap.
 355                                         dataPoints.push_back(Vec2((float)m_calibrateIterations[i].numDrawCalls, m_calibrateIterations[i].frameTime));
 356                         }
 357
 358                         if (numIterations == 1)
 359                                 dataPoints.push_back(Vec2(0.0f, 0.0f)); // If there's just one measurement so far, this will help in getting the next estimate.
 360
 361                         {
 362                                 const float                             targetFrameTimeUs       = m_params.targetFrameTimeUs;
 363                                 const float                             coeffEpsilon            = 0.001f; // Coefficient must be large enough (and positive) to be considered sensible.
 364
 365                                 const LineParameters    estimatorLine           = theilSenLinearRegression(dataPoints);
 366
 367                                 int                                             prevMaxCalls            = 0;
 368
 369                                 // Find the maximum of the past call counts.
 370                                 for (int i = 0; i < numIterations; i++)
 371                                         prevMaxCalls = de::max(prevMaxCalls, m_calibrateIterations[i].numDrawCalls);
 372
 373                                 if (estimatorLine.coefficient < coeffEpsilon) // Coefficient not good for sensible estimation; increase call count enough to get a reasonably different value.
 374                                         newCallCount = 2*prevMaxCalls;
 375                                 else
 376                                 {
 377                                         // Solve newCallCount such that approximately targetFrameTime = offset + coefficient*newCallCount.
 378                                         newCallCount = (int)((targetFrameTimeUs - estimatorLine.offset) / estimatorLine.coefficient + 0.5f);
 379
 380                                         // We should generally prefer FPS counts below the target rather than above (i.e. higher frame times rather than lower).
 381                                         if (estimatorLine.offset + estimatorLine.coefficient*(float)newCallCount < minGoodFrameTimeUs)
 382                                                 newCallCount++;
 383                                 }
 384
 385                                 // Make sure we have at least minimum amount of calls, and don't allow increasing call count too much in one iteration.
 386                                 newCallCount = de::clamp(newCallCount, 1, prevMaxCalls*10);
 387                         }
 388                 }
 389
 390                 m_measureState.start(m_params.maxCalibrateIterationFrames, m_params.calibrateIterationShortcutThreshold, newCallCount);
 391                 m_calibrateIterations.push_back(CalibrateIteration(newCallCount, 0.0f));
 392         }
 393 }
 394
 395 void logCalibrationInfo (tcu::TestLog& log, const TheilSenCalibrator& calibrator)
 396 {
 397         const CalibratorParameters&                             params                          = calibrator.getParameters();
 398         const std::vector<CalibrateIteration>&  calibrateIterations     = calibrator.getCalibrationInfo();
 399
 400         // Write out default calibration info.
 401
 402         log << TestLog::Section("CalibrationInfo", "Calibration Info")
 403                 << TestLog::Message  << "Target frame time: " << params.targetFrameTimeUs << " us (" << 1000000 / params.targetFrameTimeUs << " fps)" << TestLog::EndMessage;
 404
 405         for (int iterNdx = 0; iterNdx < (int)calibrateIterations.size(); iterNdx++)
 406         {
 407                 log << TestLog::Message << "  iteration " << iterNdx << ": " << calibrateIterations[iterNdx].numDrawCalls << " calls => "
 408                                                                 << de::floatToString(calibrateIterations[iterNdx].frameTime, 2) << " us ("
 409                                                                 << de::floatToString(1000000.0f / calibrateIterations[iterNdx].frameTime, 2) << " fps)" << TestLog::EndMessage;
 410         }
 411         log << TestLog::Integer("CallCount",    "Calibrated call count",        "",     QP_KEY_TAG_NONE, calibrator.getMeasureState().numDrawCalls)
 412                 << TestLog::Integer("FrameCount",       "Calibrated frame count",       "", QP_KEY_TAG_NONE, (int)calibrator.getMeasureState().frameTimes.size());
 413         log << TestLog::EndSection;
 414 }
 415
 416 } // gls
 417 } // deqp