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, cilt.27, sa.11, ss.2083-2087, 2008 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 27 Sayı: 11
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1109/tcad.2008.2006085
  • Dergi Adı: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.2083-2087
  • Anahtar Kelimeler: Distributed algorithms, graph problems, heuristics, physical design, rectilinear Steiner tree, routing, very large scale integration (VLSI), CONSTRUCTION
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.