Downloads: 113 | Views: 170

Research Paper | Electronics & Communication Engineering | India | Volume 4 Issue 11, November 2015

Implementation of KL Algorithm for Partitioning using Perl

Swapnil D. Ninawe | Pranali D. Surkar

Abstract: This paper presents the implementation of KL algorithm for circuit partitioning using PERL. Circuit partitioning is NP hard problem. To solve the circuit partitioning problem, heuristic iterative algorithm is used. The algorithm treats the circuit as a graph, logic gates as nodes and interconnecting nets as edges. It randomly generates the initial partition of the circuit. The text file is used as an input which contains list of nodes and adjacency matrix of edges. The complete algorithm is implemented using arrays and associative arrays in PERL. Associative arrays are used to store the initial partition, improvement values, gain values and final partition. Nodes are stored as keys of associative arrays. The output file is generated which contains final partitions. This process helps to reduce the computation time of this iterative algorithm.

Keywords: Circuit partitioning, KL Algorithm, two-way partitions, improvement values, gain values, associative arrays and adjacency matrix

Edition: Volume 4 Issue 11, November 2015,

Pages: 1503 - 1506