1 /////////////////////////////////////////////////////////////////////////////// 2 // BSD 3-Clause License 3 // 4 // Copyright (c) 2021, The Regents of the University of California 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright notice, this 11 // list of conditions and the following disclaimer. 12 // 13 // * Redistributions in binary form must reproduce the above copyright notice, 14 // this list of conditions and the following disclaimer in the documentation 15 // and/or other materials provided with the distribution. 16 // 17 // * Neither the name of the copyright holder nor the names of its 18 // contributors may be used to endorse or promote products derived from 19 // this software without specific prior written permission. 20 // 21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 22 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 // ARE 25 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE 26 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 27 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 28 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 29 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 30 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 32 /////////////////////////////////////////////////////////////////////////////// 33 34 #pragma once 35 36 #include <algorithm> 37 #include <iostream> 38 #include <random> 39 #include <string> 40 #include <unordered_map> 41 #include <vector> 42 43 #include "block_placement.h" 44 #include "shape_engine.h" 45 #include "utl/Logger.h" 46 47 namespace pin_alignment { 48 49 class SimulatedAnnealingCore 50 { 51 private: 52 float init_prob_ = 0.95; 53 float rej_ratio_ = 0.95; 54 int max_num_step_ = 1000; 55 int k_; 56 float c_; 57 int perturb_per_step_ = 60; 58 float alpha_ = 0.4; 59 float beta_ = 0.3; 60 float gamma_ = 0.3; 61 62 float cooling_rate_; 63 64 float outline_width_ = 0.0; 65 float outline_height_ = 0.0; 66 67 float height_ = 0.0; 68 float width_ = 0.0; 69 float area_ = 0.0; 70 float wirelength_ = 0.0; 71 float outline_penalty_ = 0.0; 72 73 float pre_height_ = 0.0; 74 float pre_width_ = 0.0; 75 float pre_area_ = 0.0; 76 float pre_wirelength_ = 0.0; 77 float pre_outline_penalty_ = 0.0; 78 79 float norm_area_ = 0.0; 80 float norm_wirelength_ = 0.0; 81 float norm_outline_penalty_ = 0.0; 82 float init_T_ = 0.0; 83 84 int action_id_ = -1; 85 bool flip_flag_ = true; 86 std::vector<shape_engine::Macro> macros_; 87 std::vector<block_placement::Net*> nets_; 88 std::unordered_map<std::string, std::pair<float, float>> terminal_position_; 89 std::unordered_map<std::string, int> macro_map_; 90 91 std::vector<int> pos_seq_; 92 std::vector<int> neg_seq_; 93 std::vector<int> pre_pos_seq_; 94 std::vector<int> pre_neg_seq_; 95 96 float flip_prob_ = 0.2; 97 float pos_swap_prob_ = 0.5; // actually prob = 0.3 98 float neg_swap_prob_ = 0.8; // actually prob = 0.3 99 float double_swap_prob_ = 1.0; // actually prob = 0.2 100 101 std::mt19937 generator_; 102 std::uniform_real_distribution<float> distribution_; 103 104 void PackFloorplan(); 105 void SingleFlip(); 106 void SingleSwap(bool flag); // true for pos swap and false for neg swap 107 void DoubleSwap(); 108 void Flip(); 109 void Perturb(); 110 void Restore(); 111 void Initialize(); 112 void CalculateWirelength(); 113 void CalculateOutlinePenalty(); 114 float NormCost(float area, float wirelength, float outline_penalty) const; 115 void FastSA(); 116 117 public: 118 // constructor 119 SimulatedAnnealingCore( 120 const std::vector<shape_engine::Macro>& macros, 121 const std::vector<block_placement::Net*>& nets, 122 const std::unordered_map<std::string, std::pair<float, float>>& 123 terminal_position, 124 float cooling_rate, 125 float outline_width, 126 float outline_height, 127 float init_prob = 0.95, 128 float rej_ratio = 0.95, 129 int max_num_step = 1000, 130 int k = 100, 131 float c = 100, 132 int perturb_per_step = 60, 133 float alpha = 0.4, 134 float beta = 0.3, 135 float gamma = 0.3, 136 float flip_prob = 0.2, 137 float pos_swap_prob = 0.3, 138 float neg_swap_prob = 0.3, 139 float double_swap_prob = 0.2, 140 unsigned seed = 0); 141 142 void Run(); 143 GetWidth()144 float GetWidth() const { return width_; } GetHeight()145 float GetHeight() const { return height_; } GetArea()146 float GetArea() const { return area_; } GetWirelength()147 float GetWirelength() const { return wirelength_; }; 148 bool IsFeasible() const; 149 150 void WriteFloorplan(const std::string& file_name) const; 151 GetMacros()152 std::vector<shape_engine::Macro> GetMacros() const { return macros_; } 153 }; 154 155 // wrapper for run function of SimulatedAnnealingCore 156 void Run(SimulatedAnnealingCore* sa); 157 158 // Parse macro file 159 void ParseMacroFile(std::vector<shape_engine::Macro>& macros, 160 float halo_width, 161 const std::string& file_name); 162 163 bool PinAlignmentSingleCluster( 164 const char *report_directory, 165 shape_engine::Cluster* cluster, 166 const std::unordered_map<std::string, std::pair<float, float>>& 167 terminal_position, 168 const std::vector<block_placement::Net*>& nets, 169 utl::Logger* logger, 170 float halo_width, 171 int num_thread, 172 int num_run, 173 unsigned seed); 174 175 // Pin Alignment Engine 176 bool PinAlignment(const std::vector<shape_engine::Cluster*>& clusters, 177 utl::Logger* logger, 178 const char *report_directory, 179 float halo_width, 180 int num_thread, 181 int num_run, 182 unsigned seed = 0); 183 184 } // namespace pin_alignment 185