1 2 // ================================================================================================= 3 // This file is part of the CLTune project, which loosely follows the Google C++ styleguide and uses 4 // a tab-size of two spaces and a max-width of 100 characters per line. 5 // 6 // Author: cedric.nugteren@surfsara.nl (Cedric Nugteren) 7 // 8 // This file implements a variant of particle swarm optimisation (PSO). It is adapted from PSO 9 // because of the higly dimensional discrete (or even boolean) search space. Therefore, there is no 10 // continous position nor velocity calculation. In fact, velocity is completely absent, following 11 // the principles of accelerated PSO (or APSO). Parameters to this form of PSO are the swarm size, 12 // the fraction of search space to explore, and the influences of the global best position, the 13 // local (particle's) best position, and the random influence. 14 // 15 // ------------------------------------------------------------------------------------------------- 16 // 17 // Copyright 2014 SURFsara 18 // 19 // Licensed under the Apache License, Version 2.0 (the "License"); 20 // you may not use this file except in compliance with the License. 21 // You may obtain a copy of the License at 22 // 23 // http://www.apache.org/licenses/LICENSE-2.0 24 // 25 // Unless required by applicable law or agreed to in writing, software 26 // distributed under the License is distributed on an "AS IS" BASIS, 27 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 28 // See the License for the specific language governing permissions and 29 // limitations under the License. 30 // 31 // ================================================================================================= 32 33 #ifndef CLTUNE_SEARCHERS_PSO_H_ 34 #define CLTUNE_SEARCHERS_PSO_H_ 35 36 #include <vector> 37 #include <random> 38 39 #include "internal/searcher.h" 40 #include "internal/kernel_info.h" 41 42 namespace cltune { 43 // ================================================================================================= 44 45 // See comment at top of file for a description of the class 46 class PSO: public Searcher { 47 public: 48 49 // Shorthand 50 using Parameters = std::vector<KernelInfo::Parameter>; 51 52 // Takes additionally a fraction of configurations to consider 53 PSO(const Configurations &configurations, const Parameters ¶meters, 54 const double fraction, const size_t swarm_size, const double influence_global, 55 const double influence_local, const double influence_random); ~PSO()56 ~PSO() { } 57 58 // Retrieves the next configuration to test 59 virtual KernelInfo::Configuration GetConfiguration() override; 60 61 // Calculates the next index 62 virtual void CalculateNextIndex() override; 63 64 // Retrieves the total number of configurations to try 65 virtual size_t NumConfigurations() override; 66 67 // Pushes feedback (in the form of execution time) from the tuner to the search algorithm 68 virtual void PushExecutionTime(const double execution_time) override; 69 70 private: 71 72 // Returns the index of the target configuration in the whole configuration list 73 size_t IndexFromConfiguration(const KernelInfo::Configuration target) const; 74 75 // Configuration parameters 76 double fraction_; 77 size_t swarm_size_; 78 79 // Percentages of influence on the whole swarm's best (global), the particle's best (local), and 80 // the random values. The remainder fraction is the chance of staying in the current position. 81 double influence_global_; 82 double influence_local_; 83 double influence_random_; 84 85 // Locations of the particles in the swarm 86 size_t particle_index_; 87 std::vector<size_t> particle_positions_; 88 89 // Best cases found so far 90 double global_best_time_; 91 std::vector<double> local_best_times_; 92 KernelInfo::Configuration global_best_config_; 93 std::vector<KernelInfo::Configuration> local_best_configs_; 94 95 // Allowed parameters 96 Parameters parameters_; 97 98 // Random number generation 99 std::default_random_engine generator_; 100 std::uniform_int_distribution<int> int_distribution_; 101 std::uniform_real_distribution<double> probability_distribution_; 102 }; 103 104 // ================================================================================================= 105 } // namespace cltune 106 107 // CLTUNE_SEARCHERS_PSO_H_ 108 #endif 109