Minimum-perimeter domain assignment

Data:	1997
Resum:	For certain classes of problems defined over two-dimensional domains with grid structure, optimization problems involving the assignment of grid cells to processors present a nonlinear network model for the problem of partitioning tasks among processors so as to minimize interprocessor communication. Minimizing interprocessor communication in this context is shown to be equivalent to tiling the domain so as to minimize total tile perimeter, where each tile corresponds to the collection of tasks assigned to some processor. A tight lower bound on the perimeter of a tile as a function of its area is developed. We then show how to generate minimum-perimeter tiles. By using assignments corresponding to near-rectangular minimum-perimeter tiles, closed form solutions are developed for certain classes of domains. We conclude with computational results with parallel high-level genetic algorithms that have produced good (and sometimes provably optimal) solutions for very large perimeter minimization problems. .
Drets:	Tots els drets reservats.
Llengua:	Anglès
Document:	Article ; recerca ; Versió publicada
Publicat a:	Mathematical Programming, vol. 78 n. 2 (1997) p. 283-303, ISSN 0025-5610

21 p, 1.1 MB

Accés restringit a la UAB

Registre creat el 2006-03-13, darrera modificació el 2023-06-03