The week's pick
Reseach Article
A Study on Applying Parallelism for Construction of Steiner Tree Algorithms in VLSI Design
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 148 - Number 2 |
| Year of Publication: 2016 |
| Authors: Shyamala G., Latha N. R. |
10.5120/ijca2016911006
|
Shyamala G., Latha N. R. . A Study on Applying Parallelism for Construction of Steiner Tree Algorithms in VLSI Design. International Journal of Computer Applications. 148, 2 ( Aug 2016), 7-12. DOI=10.5120/ijca2016911006
Abstract
We present a survey of the different approaches that can be parallelized and also the parallel algorithms available today with special concern to Rectilinear steiner tree for VLSI Design and their appropriateness for high-performance computing. Thus, we review the parallel algorithms for solving the Stiener tree problem as it is of great importance for very large scale integration routing and wire length estimation. As the steiner problem in general is NP-hard, it is difficult to develop a polynomial-time algorithm to solve the problem exactly. This is why the most of research has looked at finding efficient heuristic algorithms. Additionally, many authors focused their work on utilizing the ever-increasing computational power and developed many parallel methods for solving the problem. Hence we are able to obtain better results in less time than ever before.The study shows that the accessibility of multi-core CPUs has given new impulse to the shared memory parallel programming approach., Hybrid parallel programming is the current way of harnessing the capabilities of computer clusters with multi-core nodes. On the other hand, high performance heterogeneous programming is found to be an increasingly well accepted paradigm, as a result of the availability of multi-core CPUs and GPUs systems. The use of open industry standards like OpenMP, MPI, or OpenCL, as opposed to proprietary solutions, seems to be the way to categorize and extend the use of parallel programming models. Here, we present a survey of the parallel methods for solving the stiener tree problem specifically for VLSI design
References
- Hanan, Maurice. "On Steiner's problem with rectilinear distance." SIAM Journal on Applied Mathematics 14.2 (1966): 255-265.
- Hwang, Frank K. "On Steiner minimal trees with rectilinear distance." SIAM journal on Applied Mathematics 30.1 (1976): 104- 114.
- Ho, J-M., Gopalakrishnan Vijayan, and C. K. Wong. "New algorithms for the rectilinear Steiner tree problem." ComputerAided Design of Integrated Circuits and Systems, IEEE Transactions on 9.2 (1990): 185-193.
- J. L. Ganley and J. P. Cohoon, “Routing a multiterminal critical net: Steiner tree construction in the presence of obstacle,” in Proc. ISCAS, 1994, pp. 113–116.
- A. B. Kahng and G. Robins. A new class of iterative steiner tree heuristics with good performance. IEEE Transactions Computer-Aided Design, 11(7):893–902, July 1992.
- A. B. Kahng and G. Robins. On Optimal Interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.
- J. Griffith, G. Robins, J. S. Salowe, and T. Zhang. Closing the gap: Near-optimal steiner trees in polynomial time. IEEE Transactions Computer-Aided Design, 13(11):1351–1365, November 1994.
- G. Robins and J. S. Salowe. Low-degree minimum spanning trees. Discrete and Computational Geometry, 14:151–165, September 1995.
- Jayaraman, R., Rutenbar, R.A.: A parallel Steiner heuristic for wirelength estimation of large net populations. In: 1991 IEEE International Conference on Computer-Aided Design Digest of Technical Papers, pp. 344–347 (1991)
- Dunlop, A.E., Kernighan, B.W.: A procedure for placement of standard-cell VLSI circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 4, 92–98 (1985)
- Fobel, C.,Grewal, G.: A parallel Steiner tree heuristic for macro cell routing.In: IEEE International Conference on Computer Design, vol. 27–33 (2008)
- Martins, S.L., Ribeiro, C.C., Souza, M.C.: A parallel GRASP for the Steiner problem in graphs. In: IRREGULAR ’98: Proceedings of the 5th International Symposium on Solving Irregularly Structured Problems in Parallel, pp. 285–297 (1998)
- Kruskal Jr, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am.Math. Soc. 7, 48–50 (1956)
- Martins, S.L., Resende,M.G.C., Ribeiro, C.C., Pardalos, P.M.: A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search strategy. J. Global Optim. 17(1), 267–283 (2000)
- Totsukawa, H., Senou, H., Ohmura, M.: A parallel genetic algorithm for 3-D rectilinear Steiner tree with bounded number of bends. In: 2008 51st Midwest Symposium on Circuits and Systems, pp. 89–92 (2008)
- Wing-Kai Chowa,n, LiangLi a, Evangeline F.Y.Young a, Chiu-WingSham b Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach
- A Parallel Algorithm for Constructing Obstacle-Avoiding Rectilinear Steiner Minimal Trees on Multi-Core Systems Cheng-Yuan Chang and I-Lun Tseng, Department of Computer Science and Engineering, Yuan Ze University, Taiwan
- Takumi Watanabe, Hitoshi Kitazawa, and Yoshi Sugiyama, “A Parallel Adaptable Routing Algorithm and Its Implementation on a Two-Dimensional Array Processor,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 6, no. 2, pp. 241-250, 1987
- McKee, S.A., Barrera, T., Griffith, J., Robins, G., Zhang, T.: Toward a Steiner engine: enhanced serial and parallel implementations of the iterated 1-Steiner MRST algorithm. In: Proceedings of the Third Great Lakes Symposium on VLSI-Design Automation of High Performance VLSI Systems,vol. 2442, pp. 90–94 (1993)
- SWARM: A Parallel Programming Framework for Multicore Processors David A. Bader, Varun Kanade and Kamesh Madduri
Index Terms
Keywords