Sequential and parallel heuristic algorithms for the rectilinear Steiner tree problem

Download

index.pdf

Date

2006

Author

Cinel, Sertaç

Metadata

Show full item record

Item Usage Stats

259
views

55
downloads

The Steiner Tree problem is one of the most popular graph problems and has many application areas. The rectilinear version of this problem, introduced by Hanan, has taken special attention since it addresses a fundamental matter in “Physical Design” phase of the Very Large Scale Integrated (VLSI) Computer Aided Design (CAD) process. The Rectilinear Steiner Tree Problem asks for a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments, enabling the use of extra points. There are various exact algorithms. However the problem is NP-complete hence approximation algorithms have to be used especially for large instances. In this thesis work, first a survey on heuristics for the Rectilinear Steiner Tree Problem is conducted and then two recently developed successful algorithms, BGA by Kahng et. al. and RST by Zhou have been studied and investigated deeply. Both algorithms have subproblems, most of which have individual backgrounds in literature. After an analysis of BGA and RST, the thesis proposes a modification on RST, which leads to a faster and non-recursive version. The efficiency of the modified algorithm has been validated by computational tests using both random and VLSI benchmark instances. A partially parallelized version of the modified algorithm is also proposed for distributed computing environments. It is implemented using MPI (message passing interface) middleware and the results of comparative tests conducted on a cluster of workstations are presented. The proposed distributed algorithm has also proved to be promising especially for large problem instances.

Subject Keywords

Electronic Computers., Computer Science.

URI

http://etd.lib.metu.edu.tr/upload/12607896/index.pdf
https://hdl.handle.net/11511/16154

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Efficient scheduling in distributed computing on grid Kaya, Özgür; Bozyiğit, Müslim; Department of Computer Engineering (2006) Today many computing resources distributed geographically are idle much of time. The aim of the grid computing is collecting these resources into a single system. It helps to solve problems that are too complex for a single PC. Scheduling plays a critical role in the efficient and effective management of resources to achieve high performance on grid computing environment. Due to the heterogeneity and highly dynamic nature of grid, developing scheduling algorithms for grid computing involves some challenges....
A new approach for better load balancing of visibility detection and target acquisition calculations Filiz, Anıl Yiğit; Can, Tolga; Department of Computer Engineering (2010) Calculating visual perception of entities in simulations requires complex intersection tests between the line of sight and the virtual world. In this study, we focus on outdoor environments which consist of a terrain and various objects located on terrain. Using hardware capabilities of graphics cards, such as occlusion queries, provides a fast method for implementing these tests. In this thesis, we introduce an approach for better load balancing of visibility detection and target acquisition calculations b...
Hierarchical parallelisation strategy for multilevel fast multipole algorithm in computational electromagnetics Ergül, Özgür Salih (Institution of Engineering and Technology (IET), 2008-01-03) A hierarchical parallelisation of the multilevel fast multipole algorithm (MLFMA) for the efficient solution of large-scale problems in computational electromagnetics is presented. The tree structure of MLFMA is distributed among the processors by partitioning both the clusters and the samples of the fields appropriately for each level. The parallelisation efficiency is significantly improved compared to previous approaches, where only the clusters or only the fields are partitioned in a level.
Random Set Methods Estimation of Multiple Extended Objects Granstrom, Karl; Lundquist, Christian; Gustafsson, Fredrik; Orguner, Umut (Institute of Electrical and Electronics Engineers (IEEE), 2014-06-01) Random set-based methods have provided a rigorous Bayesian framework and have been used extensively in the last decade for point object estimation. In this article, we emphasize that the same methodology offers an equally powerful approach to estimation of so-called extended objects, i.e., objects that result in multiple detections on the sensor side. Building upon the analogy between Bayesian state estimation of a single object and random finite set (RFS) estimation for multiple objects, we give a tutorial...
Resource-aware load balancing system with artificial neural networks Yıldız, Ali; Şener, Cevat; Department of Computer Engineering (2006) As the distributed systems becomes popular, efficient load balancing systems taking better decisions must be designed. The most important reasons that necessitate load balancing in a distributed system are the heterogeneous hosts having different com- puting powers, external loads and the tasks running on different hosts but communi- cating with each other. In this thesis, a load balancing approach, called RALBANN, developed using graph partitioning and artificial neural networks (ANNs) is de- scribed. The ...

Citation Formats

S. Cinel, “Sequential and parallel heuristic algorithms for the rectilinear Steiner tree problem,” M.S. - Master of Science, Middle East Technical University, 2006.