hillclimbing.cpp

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

// ==++==
//
// Copyright (c) Microsoft Corporation.  All rights reserved.
//
// ==--==
// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
//
// HillClimbing.cpp
//
// Defines classes for the HillClimbing concurrency-optimization algorithm.
//
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

#include "concrtinternal.h"
#include <math.h>

namespace Concurrency
{
namespace details
{
    //
    // Initial hill climbing configuration settings. These are the starting points for any hill climbing instance.
    //
    static const unsigned int AlwaysIncrease = 0;            // Test setting for always allocating more resources
    static const unsigned int ControlGain = 1;               // Used to determine the magnitude of moves, in units of (coefficient of variation)/(thread count)
    static const unsigned int MaxControlSettingChange = 0;   // Maximum number of resources that can be changed in one transition (i.e. a capper)
    static const unsigned int MinHistorySize = 3;            // Minimum history size to consider relevant for climbing (used for significance test)
    static const unsigned int MaxHistorySize = 5;            // Maximum history size, after which a climbing move must be recommended
    static const unsigned int WarmupSampleCount = 1;         // How many samples are needed to warm up hill climbing
    static const unsigned int MinCompletionsPerSample = 1;   // Minimum number of completions needed to try hill climbing
    static const unsigned int MaxInvalidCount = 3;           // Maximum number of consecutive invalid samples; minimum recommended after this point
    static const unsigned int MaxHistoryAge = 50;            // Maximum amount of ticks to keep a history from a previous setting

    /// <summary>
    ///     Creates a new instance of hill climbing.
    /// </summary>
    /// <param name="id">
    ///     Scheduler id.
    /// </param>
    /// <param name="numberOfCores">
    ///     Number that represents the maximum resources available on the machine.
    /// </param>
    /// <param name="pSchedulerProxy">
    ///     The scheduler proxy that controls this hill climbing instance.
    /// </param>
    HillClimbing::HillClimbing(unsigned int id, unsigned int numberOfCores, SchedulerProxy * pSchedulerProxy) :
        m_id(id), m_pSchedulerProxy(pSchedulerProxy), m_sampleCount(0), m_totalSampleCount(0), m_currentControlSetting(0),
        m_lastControlSetting(0), m_nextRandomMoveIsUp(true), m_saveCompleted(0), m_saveIncoming(0), m_invalidCount(0)
    {
        //
        // Assign default configuration
        //
        m_controlGain = ControlGain * numberOfCores;
        m_maxControlSettingChange = (MaxControlSettingChange != 0) ? MaxControlSettingChange : numberOfCores;
    }

    /// <summary>
    ///     External call passing statistical information to hill climbing. Based on these
    ///     statistics, hill climbing will give a recommendation on the number of resources to be used.
    /// </summary>
    /// <param name="currentControlSetting">
    ///     The control setting used in this period of time.
    /// </param>
    /// <param name="completionRate">
    ///     The number of completed units or work in that period of time.
    /// </param>
    /// <param name="arrivalRate">
    ///     The number of incoming units or work in that period of time.
    /// </param>
    /// <param name="queueLength">
    ///     The total length of the work queue.
    /// </param>
    /// <returns>
    ///     The recommended number of resources to be used.
    /// </returns>
    unsigned int HillClimbing::Update(unsigned int currentControlSetting, unsigned int completionRate, unsigned int arrivalRate, unsigned int queueLength)
    {
        HillClimbingStateTransition transition = Undefined;
        int recommendedSetting = 0;

        // If there are no resources devoted to this scheduler proxy then there is
        // no statistical analysis needed.
        if (currentControlSetting == 0)
        {
            return 0;
        }

        //
        // Hill climbing made a recommendation for a number of resources to be used the next time around. However, that
        // does not mean that this recommendation was accepted by the consumer of that information. Thus, first establish
        // the control setting passed in by the consumer so that we can accurately track history information. Also, it is
        // necessary to flush old, stale history information before trying to hill climb.
        //
        m_totalSampleCount++;
        EstablishControlSetting(currentControlSetting);

        //
        // If we had some invalid samples, then carefully modify the actual parameters to this function
        //
        if (m_invalidCount > 0)
        {
            completionRate += m_saveCompleted;
            arrivalRate += m_saveIncoming;
        }

        //
        // If we have long running tasks that are not yet completed, report completions and arrivals for those
        // tasks, effectively chunking them up into sample sized tasks. A long running task scenario is defined as:
        //
        //  a) Number or completed tasks is smaller than number of resources used in the time interval, AND
        //  b) Number of completed tasks is smaller than a length of the queue (resources cannot be invalid)
        //
        if (completionRate < currentControlSetting && completionRate < queueLength)
        {
            arrivalRate += (currentControlSetting - completionRate);
            completionRate = currentControlSetting;
        }

        //
        // Check if reported statistics are within the bounds of a valid sample. A sample is invalid iff:
        // it is not a warmup run AND it is EITHER too short of a measurement OR there were not enough completions.
        //
        if (m_sampleCount >= WarmupSampleCount && MinCompletionsPerSample > completionRate && MinCompletionsPerSample > arrivalRate && queueLength == 0)
        {
            //
            // If this is an invalid sample, save the data
            //
            m_invalidCount++;
            m_saveCompleted = completionRate;
            m_saveIncoming = arrivalRate;

            unsigned int minimumSetting = m_pSchedulerProxy->MinHWThreads();
            unsigned int maximumSetting = m_pSchedulerProxy->DesiredHWThreads();

            recommendedSetting = (m_invalidCount < MaxInvalidCount) ? m_currentControlSetting : minimumSetting;

            TRACE(CONCRT_TRACE_HILLCLIMBING,
                L"********** Invalid sample!\n Process: %u\n Scheduler: %d\n Invalid count: %d\n Completions: %d\n Arrivals: %d\n Queue length: %d\n Minimum: %d\n Maximum: %d\n Current setting: %d\n Last setting: %d\n -----\n Recommended setting: %d\n**********\n", 
                GetCurrentProcessId(),
                m_id,
                m_invalidCount,
                completionRate,
                arrivalRate,
                queueLength,
                minimumSetting,
                maximumSetting,
                m_currentControlSetting,
                m_lastControlSetting,
                recommendedSetting);

            return recommendedSetting;
        }

        unsigned int numberOfSamples = m_invalidCount + 1;

        //
        // Reset the statistics kept for invalid samples and initiate a valid sample
        //
        m_sampleCount++;
        m_saveCompleted = 0;
        m_saveIncoming = 0;
        m_invalidCount = 0;

        // Unless there is a good reason to climb, the current setting (set by EstablishControlSetting) will remain the same.
        recommendedSetting = m_currentControlSetting;

        // Calculate the throughput for this given instance
        double throughput = CalculateThroughput(numberOfSamples, completionRate, arrivalRate, queueLength);

        if (m_sampleCount <= WarmupSampleCount)
        {
            //
            // We're in the "warmup" phase, where we simply bide our time (and initialize our current control setting).
            //
            _ASSERTE(m_currentControlSetting != 0);
            m_lastControlSetting = m_currentControlSetting;
            transition = Warmup;
        }
        else
        {
            MeasuredHistory * currentHistory = GetHistory(m_currentControlSetting);
            MeasuredHistory * lastHistory = GetHistory(m_lastControlSetting);

            currentHistory->Add(throughput, m_totalSampleCount);

            if (AlwaysIncrease > 0)
            {
                //
                // We're in the "always increase" diagnostic mode.  Just increase the control setting
                // along the desired slope.
                //
                unsigned int newSetting = (unsigned int) ((AlwaysIncrease / 1000.0) * m_sampleCount);

                if (newSetting > m_currentControlSetting)
                {
                    recommendedSetting = RecommendControlSetting(newSetting);
                    transition = DoClimbing;
                }
                else
                {
                    transition = ContinueLookingForClimb;
                }
            }
            else if (lastHistory->Count() == 0 || currentHistory == lastHistory)
            {
                //
                // If we have no previous history, then we need to initialize.  We wait until
                // the current history is stable, then make our first move.
                //
                if (IsStableHistory(currentHistory))
                {
                    // 
                    // This is our first move; we have no history to use to predict the correct move.
                    // We'll just make a random move, and see what happens.
                    //
                    recommendedSetting = RecommendControlSetting(m_currentControlSetting + GetRandomMove());
                    transition = CompletedInitialization;
                }
                else
                {
                    transition = ContinueInitializing;
                }
            }
            else if (!IsStableHistory(currentHistory))
            {
                transition = ContinueLookingForClimb;
            }
            else
            {
                //
                // We have two separate stable histories.  We can compare them, and make a real climbing move.
                //
                double slope = CalculateThroughputSlope(m_lastControlSetting, m_currentControlSetting);
                double controlSettingAdjustment = slope * m_controlGain;
                unsigned int newControlSetting = (unsigned int) (m_currentControlSetting + controlSettingAdjustment);

                if (newControlSetting == m_currentControlSetting)
                {
                    newControlSetting = (unsigned int) (m_currentControlSetting + sign(controlSettingAdjustment));
                }

                recommendedSetting = RecommendControlSetting(newControlSetting);
                transition = DoClimbing;
            }
        }

        _ASSERTE(transition != Undefined); // Unhandled case for HillClimbing controller

#if defined(CONCRT_TRACING)
        LogData(recommendedSetting, transition, numberOfSamples, completionRate, arrivalRate, queueLength, throughput);
#endif

        return recommendedSetting;
    }

    /// <summary>
    ///     Calculates the throughput based on the input parameters.
    /// </summary>
    /// <param name="numberOfSamples">
    ///     The number of sample points in this measurement, including invalid ones.
    /// </param>
    /// <param name="completionRate">
    ///     The number of completed units or work in that period of time.
    /// </param>
    /// <param name="arrivalRate">
    ///     The number of incoming units or work in that period of time.
    /// </param>
    /// <param name="queueLength">
    ///     The total length of the work queue.
    /// </param>
    /// <returns>
    ///     The calculated throughput.
    /// </returns>
    double HillClimbing::CalculateThroughput(unsigned int numberOfSamples, unsigned int completionRate, unsigned int arrivalRate, unsigned int queueLength)
    {
        const double samplesPerSecond = 10.0;    // A double constant representing number of valid samples per second

        // Compute the rate at which the queue is growing or shrinking. If it is growing, report a higher
        // number which will cause more resources to be allocated for this instance; it the length of the queue
        // is shrinking, try to take away resources while still shrinking the queue.
        //
        //           /_\ length     incoming - completed
        // growth = ------------ = ----------------------
        //            /_\ time            t2 - t1
        // 
        // For now, instead of looking at the change in the queue length, completion rate will be used. This is due
        // to the fact that typical loads in ConcRT are self-balancing, i.e. completion rate ~ incoming rate.
        //
        return (completionRate * samplesPerSecond) / (double) (numberOfSamples);
    }

    /// <summary>
    ///     Recommends NewControlSetting to be used.
    /// </summary>