hillclimbing.cpp

C语言库函数的原型,有用的拿去

    /// <param name="newControlSetting">
    ///     The control setting to be established.
    /// </param>
    /// <returns>
    ///     New control setting to be used.
    /// </returns>
    unsigned int HillClimbing::RecommendControlSetting(unsigned int newControlSetting)
    {
        //
        // Make sure that the new setting is within the biggest individual move bounds.
        //
        unsigned int minimumSetting = m_pSchedulerProxy->MinHWThreads();
        unsigned int maximumSetting = m_pSchedulerProxy->DesiredHWThreads();

        newControlSetting = min(m_currentControlSetting + m_maxControlSettingChange, newControlSetting);

        if (m_currentControlSetting > m_maxControlSettingChange)
        {
            newControlSetting = max(m_currentControlSetting - m_maxControlSettingChange, newControlSetting);
        }

        if (newControlSetting == m_currentControlSetting)  // Can't draw a line with a single point
        {
            if (newControlSetting > minimumSetting)
            {
                newControlSetting--;
            }
            else
            {
                newControlSetting++;
            }
        }

        //
        // Make sure that the new setting is within the min and max bounds of the scheduler proxy.
        //
        newControlSetting = max(minimumSetting, newControlSetting);
        newControlSetting = min(maximumSetting, newControlSetting);

        if (AlwaysIncrease == 0 && newControlSetting != m_currentControlSetting)
        {
            // If this move would cause us to move through a setting that we know was recently worse than this
            // one, then back off to one before that setting.
            int direction = sign(newControlSetting - m_currentControlSetting);

            if (direction == -1)
            {
                for (int setting = m_currentControlSetting + direction; 
                     setting == newControlSetting || sign(newControlSetting - setting) == direction;
                     setting += direction)
                {
                    if (GetHistory(setting)->Count() > 0)
                    {
                        double slope = CalculateThroughputSlope(m_currentControlSetting, setting) * direction;

                        if (slope <= 0)
                        {
                            newControlSetting = setting - direction;
                            break;
                        }
                    }
                }
            }
        }

        return newControlSetting;
    }

    /// <summary>
    ///     Establishes control setting as current. This is the only method that updates the control settings.
    /// </summary>
    /// <param name="newControlSetting">
    ///     The control setting to be established.
    /// </param>
    void HillClimbing::EstablishControlSetting(unsigned int newControlSetting)
    {
        if (newControlSetting != m_currentControlSetting)
        {
            m_lastControlSetting = m_currentControlSetting;
            m_currentControlSetting = newControlSetting;
            GetHistory(m_currentControlSetting)->Clear(0);
            FlushHistories();
        }
    }

    /// <summary>
    ///     Calculates the throughput slope given two history measurements.
    /// </summary>
    /// <param name="fromSetting">
    ///     The control setting to move from.
    /// </param>
    /// <param name="toSetting">
    ///     The control setting to move to.
    /// </param>
    /// <returns>
    ///     A value representing a slope between two measurements.
    /// </returns>
    double HillClimbing::CalculateThroughputSlope(int fromSetting, int toSetting)
    {
        //
        // Configurable constants to control reactiveness of hill climbing
        //
        const double minJustifiesChange = 0.15;         // A minimum fractional change in measurement that justifies a change (cost for making a change)
        const double changeAdjustmentMultiplier = 1.0;  // Controls change factor by reducing uncertainty (bigger number pessimizes change frequency)

        double fractionalChangeInControlSetting = (double) (toSetting - fromSetting) / (double) fromSetting;

        MeasuredHistory * lastHistory = GetHistory(fromSetting);
        MeasuredHistory * currentHistory = GetHistory(toSetting);

        double lastHistoryMean = lastHistory->Mean();
        double currentHistoryMean = currentHistory->Mean();
        double meanChangeInMeasuredValue = currentHistoryMean - lastHistoryMean;
        double fractionalChangeInMeasuredValue = meanChangeInMeasuredValue / lastHistoryMean;

        double slope = (fractionalChangeInMeasuredValue/fractionalChangeInControlSetting) - minJustifiesChange;

        double varianceOfcurrentHistory = currentHistory->VarianceMean();
        double varianceOflastHistory = currentHistory->VarianceMean();
        double standardDeviationOfDifferenceInMeans = sqrt(varianceOfcurrentHistory + varianceOflastHistory);
        double coefficientOfVariationOfChangeInMeasuredValue = 
            (abs(meanChangeInMeasuredValue) > 0) ? abs(standardDeviationOfDifferenceInMeans / meanChangeInMeasuredValue) : 0;

        double adjustedSlope = slope * exp(-changeAdjustmentMultiplier * coefficientOfVariationOfChangeInMeasuredValue);

        return adjustedSlope;
    }

    /// <summary>
    ///     Determines whether a given history measurement is stable enough to make a hill climbing move.
    /// </summary>
    /// <returns>
    ///     True if history measurement is stable.
    /// </returns>
    bool HillClimbing::IsStableHistory(MeasuredHistory * pMeasuredHistory)
    {
        const double maxCoefficientOfVariation = 0.004; // Controls history relevance between min and max by bounding the error

        if (pMeasuredHistory->Count() > MaxHistorySize)
        {
            return true;
        }

        if (pMeasuredHistory->Count() < MinHistorySize)
        {
            return false;
        }

        if (abs(pMeasuredHistory->CoefficientOfVariationMean()) > maxCoefficientOfVariation)
        {
            return false;
        }

        return true;
    }

    /// <summary>
    ///     Flushes all measurement histories that are no longer relevant.
    /// </summary>
    void HillClimbing::FlushHistories()
    {
        for (int i = 0; i < MaxHistoryCount; i++)
        {
            if (m_histories[i].ControlSetting() != m_currentControlSetting &&
                m_histories[i].ControlSetting() != m_lastControlSetting &&
                m_totalSampleCount - m_histories[i].LastDataPointCount() > MaxHistoryAge)
            {
                m_histories[i].Clear(0);
            }
        }
    }

    /// <summary>
    ///     Clears all measurement histories.
    /// </summary>
    void HillClimbing::ClearHistories()
    {
        for (int i = 0; i < MaxHistoryCount; i++)
        {
            m_histories[i].Clear(0);
        }
    }

    /// <summary>
    ///     Makes a pseudo-random hill climbing move by alternating between up and down.
    /// </summary>
    /// <returns>
    ///     The random move.
    /// </returns>
    int HillClimbing::GetRandomMove()
    {
        int result = m_nextRandomMoveIsUp ? 1 : 0;
        m_nextRandomMoveIsUp = !m_nextRandomMoveIsUp;
        return result;
    }

    /// <summary>
    ///     Gets the history measurement for a given control setting.
    /// </summary>
    /// <returns>
    ///     The history measurement.
    /// </returns>
    HillClimbing::MeasuredHistory * HillClimbing::GetHistory(unsigned int controlSetting)
    {
        int i = controlSetting % MaxHistoryCount;

        if (m_histories[i].ControlSetting() != controlSetting)
        {
            m_histories[i].Clear(controlSetting);
        }

        return &m_histories[i];
    }

    /// <summary>
    ///     Creates a new measurement history.
    /// </summary>
    HillClimbing::MeasuredHistory::MeasuredHistory()
    {
        Clear(0);
    }

    /// <summary>
    ///     Clears the history values for this control setting.
    /// </summary>
    /// <param name="controlSetting">
    ///     The control setting to reset.
    /// </param>
    void HillClimbing::MeasuredHistory::Clear(unsigned int controlSetting)
    {
        m_count = 0;
        m_sum = 0;
        m_sumOfSquares = 0;
        m_controlSetting = controlSetting;
        m_lastDataPointCount = 0;
    }

    /// <summary>
    ///     Adds a new history data point.
    /// </summary>
    /// <param name="dataValue">
    ///     The value representing throughput in this invocation.
    /// </param>
    /// <param name="totalSampleCount">
    ///     The value representing the total number of samples for this history, including invalid samples and samples for previous settings.
    /// </param>
    void HillClimbing::MeasuredHistory::Add(const double dataValue, unsigned int totalSampleCount)
    {
        m_sum += dataValue;
        m_sumOfSquares += dataValue * dataValue;
        m_count++;
        m_lastDataPointCount = totalSampleCount;
    }

    /// <summary>
    ///     Gets the count for this history measurement.
    /// </summary>
    /// <returns>
    ///     The count.
    /// </returns>
    int HillClimbing::MeasuredHistory::Count()
    {
        return m_count;
    }

    /// <summary>
    ///     Gets the count at the last data point for this history measurement.
    /// </summary>
    /// <returns>
    ///     The last data point count.
    /// </returns>
    unsigned int HillClimbing::MeasuredHistory::LastDataPointCount()
    {
        return m_lastDataPointCount;
    }

    /// <summary>
    ///     Gets the control setting for this history measurement.
    /// </summary>
    /// <returns>
    ///     The control setting.
    /// </returns>
    int HillClimbing::MeasuredHistory::ControlSetting() {
        return m_controlSetting;
    }

    /// <summary>
    ///     Computes the mean for a given history.
    /// </summary>
    /// <returns>
    ///     The mean.
    /// </returns>
    double HillClimbing::MeasuredHistory::Mean()
    {