Browse Prior Art Database

Parallel Simulated Annealing Method for Highly Parallel Multiple Computer Processors

IP.com Disclosure Number: IPCOM000040608D
Original Publication Date: 1987-Dec-01
Included in the Prior Art Database: 2005-Feb-02
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Darema-Rogers, F: AUTHOR [+3]

Abstract

A technique is described whereby simulated annealing (SA) algorithms are executed in parallel format for solving optimization problems, such as the placement of computer chips and wiring for circuit network configurations. Several variant approaches are discussed, utilizing SA as the optimization method and so as to enable multiple computer processors to function cooperatively in the execution of the algorithm in parallel format. In "serial" SA chip placement algorithms, pairs of chips are typically selected randomly and their positions are considered for exchange by computing the effect of the exchange on cost factors, such as the length of wire needed to connect all the chips in the network.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Parallel Simulated Annealing Method for Highly Parallel Multiple Computer Processors

A technique is described whereby simulated annealing (SA) algorithms are executed in parallel format for solving optimization problems, such as the placement of computer chips and wiring for circuit network configurations. Several variant approaches are discussed, utilizing SA as the optimization method and so as to enable multiple computer processors to function cooperatively in the execution of the algorithm in parallel format. In "serial" SA chip placement algorithms, pairs of chips are typically selected randomly and their positions are considered for exchange by computing the effect of the exchange on cost factors, such as the length of wire needed to connect all the chips in the network. Optimization movement of chip placement and wiring, implemented by the algorithm, take place when the effect of an exchange decreases the cost function. Should the cost function increase, then the move is accepted with certain probability dependents, such as the operational temperature of the system. At a given temperature, a number of exchanges are attempted. With decreases in temperature, the algorithm is repeated until the steady state cut-off criteria is reached, indicating that no more substantial reduction of the cost factor can be achieved. The technique discussed herein implements SA algorithms, similar to "serial" processing, but uses various processors in the "parallel" execution of simultaneous exchanges of disjoint pairs of chips. Each processor selects randomly two chips, sets a flag so that no other processor can move any of these chips, called locking the chips, and attempts to exchange positions. Each processor computes the cost function, based on the data at the moment, and the move is accepted or rejected based upon a particular score. However, this approach introduces random errors. With varying degrees of acceptable errors, two methods of executing the SA algorithms in parallel are introduced: The first method provides a means of locking nets and

chips. A net is defined as a wire connecting two or

mo...