Back to search

Rochester Institute of Technology

Simulated Annealing with min-cut and greedy perturbations

Abstract

dc:description.abstract

Custom integrated circuit design requires an ever increasing number of elements to be placed on a physical die. The process of searching for an optimal solution is NP-hard so heuristics are required to achieve satisfactory results under time constraints. Simulated Annealing is an algorithm which uses randomly generated perturbations to adjust a single solution. The effect of a generated perturbation is examined by a cost function which evaluates the solution. If the perturbation decreases the cost, it is accepted. If it increases the cost, it is accepted probabilistically. Such an approach allows the algorithm to avoid local minima and find satisfactory solutions. One problem faced by Simulated Annealing is that it can take a very large number of iterations to reach a desired result. Greedy perturbations use knowledge of the system to generate solutions which may be satisfactory after fewer iterations than non-greedy, however previous work has indicated that the exclusive use of greedy perturbations seems to result in a solution constrained to local minima. Min-cut is a procedure in which a graph is split into two pieces with the least interconnection possible between them. Using this with a placement problem helps to recognize components which belong to the same functional unit and thus enhance results of Simulated Annealing. The feasibility of this approach has been assessed. Hardware, through parallelization, can be used to increase the performance of algorithms by decreasing runtime. The possibility of increased performance motivated the exploration of the ability to model greedy perturbations in hardware. The use of greedy perturbations while avoiding local minima was also explored.

Degree

thesis:*
Name thesis:degree_name
Computer Engineering (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Engineering (KGCOE)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cody, Brian J.
Contributors dc:contributor
  • Marcin Łukowiak

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/8039

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Cody, Brian J.. Simulated Annealing with min-cut and greedy perturbations. Thesis thesis, https://repository.rit.edu/theses/8039