Effective Learning Analytics Integration: Key Considerations
Educational data mining and learning analytics are essential in improving student support and success in higher education. This presentation delves into the challenges and considerations when integrating learning analytics into an institution, addressing myths, biases, and key concepts.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Modern Floor-planning Based on B -Tree and Fast Simulated Annealing Paper by Chen T. C. and Cheng Y. W (2006) Presented by Gal Itzhak 22.7.15
Agenda Introduction What is a Floor-Planning? Motivation for global floor-planning optimization B* tree blocks representation Simulated annealing Classic simulated annealing for floor-planning optimization Fast and adaptive simulated annealing for floor-planning optimization An addition and comparison A generalization and comparison: Simulated Tempering
What is floor-planning? A schematic representation of the major blocks of a hardware design Applies for both ASIC and FPGA designs
What is floor-planning? A sliceable floor-planning A non- sliceable floor-planning
Motivation Modern chips and hardware designs complexity is growing dramatically: Smaller transistor widths Faster clocks Much more logics and memory Less margin for floor-planning global optimization is required I ll use the floor-planning optimization problem to present some important stochastic global optimization algorithms All make use of the simulated annealing framework
B* tree representation A generalization of the well known binary tree Does not limit the number of children of a node to 2 provides a unique and convenient representation of both sliceable and non- sliceable floor-planning For a sliceable floor-planning: reduced to a binary tree
B* tree representation Basic rules (similar to DFS in some manner): 1. set the lower left block as the root. recursively build: 2. the adjacent right hand side set of blocks as the left child. 3. the lowest block above as the right child.
B* tree representation Example:
B* tree representation Adjacent B* trees may differ by: A single block rotation A single block (node) move As single swap of blocks (nodes) Resize a single soft block
Simulated Annealing The most common stochastic global optimization method Uses MCMC techniques (Metropolis-Hastings sampler) to optimize and evaluate some cost function C(x) Sampling is taken from the Boltzman distribution over the state space: ?? ? exp( ? ? ?) The proposal distribution is usually uniform: 1?? ? ?,? = Thus, for a fixed temperature we get an acceptance probability of: (x,y)=min{1,?? ?? ? ?? ?? exp( ?? ?? ?}=min{1, ?)} ?
Simulated Annealing for floor-planning We define the following cost function: ? ? = ? ? + ? ?+(1 ? ) ? ? 2 Where A and W are the total planning area and wire length respectively ? is the required aspect ratio of the fixed outline
Aspect ratio Denote by the (user defined) maximal percentage of dead space. Then: 1 + ? ? ? = 1 + ?? ,? = ? =1 ? =2 ? =3 ? =4
Simulated Annealing for floor-planning Sampling Algorithm: Set ? = ?0, ? = ?0 Do Pick a neighbor state y Accept a move to state y, w.p. (x,y) Check the new solution cost and update the best so far Update temperature ? Until converged or cooled down Return the best solution
Simulated Annealing for floor-planning Obviously, the cooling schedule of T has a dramatic impact on the algorithm s performance: Cooling too fast would fail to optimize globally Cooling too slow would result in very long running time Common schedules are ??+1= ???(0<?<1) or decay rate 1/k [GG84] suggests a logarithmic schedule, though in practice it s too moderate
Fast Simulated Annealing for floor- planning
Fast Simulated Annealing for floor- planning 1. High temperature random search- accepts inferior solutions and avoid getting trapped in a local minimum 2. Low temperature local search- converge to some local minimum with high probability 3. Up-hill climbing search- instantly increase temperature to allow acceptance of uphill solutions. Then slowly cool to converge. As the two first stages usually require only a few iterations, one may allow to devote the spare time to the third stage
Fast and adaptive Simulated Annealing for floor-planning ? ? = ? ?+(1 ?) ? ? 2 Suppose now, for simplicity, that ? = 0 Choosing the right beforehand is impractical Trying all possible s is inefficient ? = ?????+(1 ?????) ????? ????? ? 1 ?
Fast and adaptive Simulated Annealing for floor-planning Sampling Algorithm: Set ? = ?0, ? = ?0 Do Pick a neighbor state y (perturb the current b* tree) Accept a move to state y, w.p. (x,y) Check the new solution cost and update the best one so far Adapt the weights in the cost function C(x) Update temperature: ? = ??according to the fast SA schedule Until converged or cooled down Return the best solution
SA algorithms for floor-planning comparison
SA algorithms for floor-planning comparison
? ? = ? ?+(1 ?) ? ? 2 The importance of
A generalized variation: Simulated Tempering Looking to accelerate optimization convergence time, applications dictated a non-logarithmic cooling schedule Therefore, convergence to the global minimum is no longer guaranteed with high probability [GG84] Simulated Tempering: let T be a RV chosen from a finite set of temperatures: ?1, ,??where ?1> ?2 > ?? ? ? for each ??: ???? = ?? exp( ??)
Simulated Tempering In ST the markov chain state space is augmented to (x,i), where i indicates the random temperature. An adjacent temperature transition ?? ??+1or ?? ?? 1is accepted according to the Metropolis-Hastings method: ??,? ???? ??,? ????}=min{1, The proposal distribution is ?1,2= ??,? 1= 1, ??,?+1= ??,? 1= 0.5 ??,? ?? ??,? ?? exp( ?(?) ( (??,??)=min{1, 1??))} 1?? Observe that unlike SA, the temperature may also increase
Simulated Tempering for floor-planning Sampling Algorithm: Set ? = ?0, ? = ?1 While stopping criteria not met Run S iterations of M-H or Gibbs. At each, accept transition to state y (which is a perturbation of the current B* tree) w.p. (x,y) that was previously mentioned. Keep the best solution. Propose a move to an adjacent temperature by ??,? Accept the proposal by (??,??) Return the best solution
Simulated Tempering for floor-planning Classical SA ST Timber Wolf SA It seems that ST provides a better solution than SA in terms of wirelength, for roughly similar running time Timber wolf fails to outperform the classical SA
To conclude The notion of floor-planning, its importance, and stochastic methods for its construction optimization have been introduced (all based on the SA framework) On the on hand, the method of Fast and Adaptive SA was shown, resulting in classical SA W* and A* results; however obtained much quicker On the other, the Simulated Tempering algorithm induced a better solution in terms of W*, for similar running time
References Chen T. C. and Cheng Y. W. Modern Floorplanning Based on B -Tree and Fast Simulated Annealing. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, VOL. 25, NO. 4, APRIL 2006, pp 637-650. Cong J. et al. Relaxed simulated tempering for VLSI floorplan designs. Design Automation Conference, 1999. Proceedings of the ASP-DAC 99. Asia and South Pacific. Geman, Stuart, and Donald Geman. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images." IEEE Transactions on Pattern Analysis and Machine Intelligence (1984) pp 721-741.
