A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem


Cinel S., BAZLAMAÇCI C. F.

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, vol.27, no.11, pp.2083-2087, 2008 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 27 Issue: 11
  • Publication Date: 2008
  • Doi Number: 10.1109/tcad.2008.2006085
  • Journal Name: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.2083-2087
  • Keywords: Distributed algorithms, graph problems, heuristics, physical design, rectilinear Steiner tree, routing, very large scale integration (VLSI), CONSTRUCTION
  • Middle East Technical University Affiliated: Yes

Abstract

Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and hatched greedy algorithm (BGA) by Kahng et al., have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a considerably faster version, a partially parallelized and distributed form of this modified algorithm is proposed. Computational tests using large random data sets have shown the advantage of the modification on RST, and tests conducted on a cluster of workstations have proven the proposed distributed approach to be very promising particularly for large problem instances.