Volume 2 Number 1 (Jan. 2013)
Home > Archive > 2013 > Volume 2 Number 1 (Jan. 2013) >
IJCCE 2013 Vol.2(1): 28-32 ISSN: 2010-3743
DOI: 10.7763/IJCCE.2013.V2.129

Implementation of Multi-Way Partitioning Algorithm

Kulpreet S. Sikand, Sandeep S. Gill, R. Chandel, and A. Chandel

Abstract—This paper presents a discussion of methods to solve partitioning problems and advocates the use of multi-way partitioning algorithms. The paper gives an implementation of a multi-way partitioning algorithm based on partitioning without size constraint and iterative improvement. A top-down clustering technique is employed to deal with the local minima problems faced in common heuristics and a primal-dual approach is used to enhance the iterative improvement. The Fiduccia-Mattheyses (FM) algorithm has been taken as the core algorithm which has been subjected to iterations, clustering and primal-dual iterations. The algorithm has been implemented in a way that it gives netlist files for each partitioned block. These netlists can further be used to implement actual hardware or detailed analysis. The results obtained were compared to the results obtained from the traditional FM algorithm. The results show good improvements.

Index Terms—Benchmarks, Cells, Clustering, Hypergraph,Net, Netlist, Nodes, Pads, Partitioning, Primal-Dual.

Kulpreet S. Sikand and Sandeep S. Gill are with the Guru Nanak DevEngg. College, Ludhiana, Punjab, India (e-mail: kpsikand@gmail.com,ssg@gndec.ac.in).
R. Chandel and A. Chandel are with the NIT Hamirpur, Hamirpur, India(e-mail: rchandel@yahoo.com, ashwani@nithm.ac.in).

Cite: Kulpreet S. Sikand, Sandeep S. Gill, R. Chandel, and A. Chandel, "Implementation of Multi-Way Partitioning Algorithm," International Journal of Computer and Communication Engineering vol. 2, no. 1, pp. 28-32 , 2013.

General Information

ISSN: 2010-3743 (Online)
Abbreviated Title: Int. J. Comput. Commun. Eng.
Frequency: Quarterly
Editor-in-Chief: Dr. Maode Ma
Abstracting/ Indexing: INSPEC, CNKI, Google Scholar, Crossref, EBSCO, ProQuest, and Electronic Journals Library
E-mail: ijcce@iap.org
  • Dec 29, 2021 News!

    IJCCE Vol. 10, No. 1 - Vol. 10, No. 2 have been indexed by Inspec, created by the Institution of Engineering and Tech.!   [Click]

  • Mar 17, 2022 News!

    IJCCE Vol.11, No.2 is published with online version!   [Click]

  • Dec 29, 2021 News!

    The dois of published papers in Vol. 9, No. 3 - Vol. 10, No. 4 have been validated by Crossref.

  • Dec 29, 2021 News!

    IJCCE Vol.11, No.1 is published with online version!   [Click]

  • Sep 16, 2021 News!

    IJCCE Vol.10, No.4 is published with online version!   [Click]

  • Read more>>