Using Simulated Annealing to Design Interconnection Networks .
F. Comellas, M. A. Fiol
Departament de Matemàtica Aplicada i Telemàtica;
Universitat Politècnica de Catalunya
DMAT Report 05-290, January 1990
Simulated annealing is a computational technique
reported to give good results in coping with complex
combinatorial problems. These problems usually consist
of finding a global minimum of a cost function on a
(large) set of states (also known as feasible solutions). In
this paper we explore modifications to the standard
simulated annealing method that we apply to the
design of dense interconnection networks, that is
networks that have as many nodes as possible for a
given maximum number of links from each node to other
nodes, and a given maximum distance between all pair
of nodes. We are particularly interested in the
directed-symmetric case in wich all links have a
direction, and the network, roughly speaking, looks
the same from any node. In that case each node may
execute, without modifications, the same
communication software.
The set of states are the
different networks and a cost function is defined and
is used to accept or reject a new network obtained
from a modification of a previously accepted one. The
annealing algorithm reduces the `temperature'
parameter and drives the sequence of networks towards
an optimum. The results show that with less
computational effort than in more traditional
approaches we are able to find the best results known
and in some cases improve them.
Load: