CaltechAUTHORS
  A Caltech Library Service

Load balancing loosely synchronous problems with a neural network

Fox, G. C. and Furmanski, W. (1988) Load balancing loosely synchronous problems with a neural network. In: C3P Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues. Vol.1. ACM , New York, NY, pp. 241-278. ISBN 0-89791-278-0. http://resolver.caltech.edu/CaltechAUTHORS:20161024-153822707

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20161024-153822707

Abstract

Hopfield and Tank have introduced the use of neural networks for the solution of optimization problems such as the traveling salesman problem. Here we show how to generalize this method to decompose loosely synchronous problems onto parallel machines and in particular the hypercube. In this case, decomposition or load balancing can be formulated graph theoretically in terms of optimal partitioning of the computational graph into N = 2d subgraphs. The algorithm has a suggestive spin system interpretation, with the ferromagnetic interaction minimizing the communication and the long range paramagnetic force balancing the load. The optimal fixed point of the network is in the Higgs phase of the magnet, with the domains of constant spontaneous magnetization representing the optimal decomposition map. The method is fast, reliable and admits various simple implementations: sequential, concurrent on the hypercube, analog on the neural network with adaptive weights (“learning”). We analyze the sequential performance of various mean field based network algorithms and we compare the network approach with the statistical Monte Carlo technique of simulated annealing.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1145/62297.62327DOIPaper
http://dl.acm.org/citation.cfm?doid=62297.62327PublisherPaper
Additional Information:© 1988 ACM. Work supported in part by DOE grant DE-FG03-85ER25009, the Program Manager of the Joint Tactical Fusion Office, and the ESD division of the USAF, as well as grants from IBM, and SANDIA.
Funders:
Funding AgencyGrant Number
Department of Energy (DOE)DE-FG03-85ER25009
Joint Tactical Fusion OfficeUNSPECIFIED
U.S. Air ForceUNSPECIFIED
IBMUNSPECIFIED
Sandia National LaboratoriesUNSPECIFIED
Record Number:CaltechAUTHORS:20161024-153822707
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20161024-153822707
Official Citation:G. C. Fox and W. Furmanski. 1988. Load balancing loosely synchronous problems with a neural network. In Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues - Volume 1 (C3P), Geoffrey Fox (Ed.), Vol. 1. ACM, New York, NY, USA, 241-278. DOI=http://dx.doi.org/10.1145/62297.62327
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:71411
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:24 Oct 2016 22:47
Last Modified:24 Oct 2016 22:47

Repository Staff Only: item control page