Partitioning concurrent VLSI simulation programs onto a multiprocessor by simulated annealing
作者:
J.Sheild,
期刊:
IEE Proceedings E (Computers and Digital Techniques)
(IET Available online 1987)
卷期:
Volume 134,
issue 1
页码: 24-30
年代: 1987
DOI:10.1049/ip-e.1987.0005
出版商: IEE
数据来源: IET
摘要:
Efficiently loading concurrent programs onto multiprocessor architectures is a graph partitioning problem where both the edges and vertices are weighted. The corresponding optimisation problem is computationally NP-hard, and the optimal solution can only be found by exhaustively examining all possible partitioning configurations. Near-optimal solutions can be found by using heuristic algorithms such as iterative improvement and simulated annealing. The simulated annealing heuristic is experimentally evaluated against simple iterative improvement for graphs representing the concurrent simulation programs of four VLSI circuits where the vertices were weighted. A simple cost function and an annealing schedule are presented for partitioning the graphs onto a star network of identical processors. Experimental results show that simulated annealing produces a better solution than simple iterative improvement but at the expense of considerable computer running times. It is suggested that the time required for simulated annealing to give better solutions than iterative improvement depends on the nature of distributions of weighted vertices and edges in the concurrent simulation graph as well as its size.
点击下载:
PDF
(858KB)
返 回