Placement by Simulated Annealing on a Multiprocessor

摘要: Physical design tools based on simulated annealing algorithms have been shown to produce results of extremely high quality, but typically at a very cost in execution time. This paper selects representative application--standard cell placement--and develops multiprocessor-based for placement. A taxonomy possible multiprocessor decompositions is presented which divides decomposition schemes into two broad classes: those divide individual moves subtasks and distribute them across cooperating processors, perform complete parallel. It that the choice strategy influenced by temperature; particular, introduces idea adaptive strategies dynamically change parallel scheme achieve maximum speedup as task progresses through each temperature regime. Implementations three placement are described an experimental shared-memory multiprocessor. Practical speedups achieved over serial version algorithm, it switches between optimal yields significantly better than any single approach. Models developed account observed performance, predict crossover points switching strategies.