Low Cost Chip Set Selection Algorithm for Multi-way Partitioning of Digital System

Authors: Jae Young Park, Soongyu Kwon, Kyu Han Kim, Hyeong Geon Lee, Jong Tae Kim

Abstract:

This paper considers the problem of finding low cost chip set for a minimum cost partitioning of a large logic circuits. Chip sets are selected from a given library. Each chip in the library has a different price, area, and I/O pin. We propose a low cost chip set selection algorithm. Inputs to the algorithm are a netlist and a chip information in the library. Output is a list of chip sets satisfied with area and maximum partitioning number and it is sorted by cost. The algorithm finds the sorted list of chip sets from minimum cost to maximum cost. We used MCNC benchmark circuits for experiments. The experimental results show that all of chip sets found satisfy the multiple partitioning constraints.

Keywords: lowest cost chip set, MCNC benchmark, multi-way partitioning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1333744

References:

[1] S. M. Sait and H. Youssef, "VLSI PHYSICAL DESIGN AUTOMATION", IEEE PRESS, pp.28
[2] C. J. Alpert and A. B. Kahng, "Recent Directions in Netlist Partitioning: A survey" Integration : the VLSI Journal, 19(1-2), 1995, 1-81
[3] R. Kuznar, R. Brglez, and K. Kozminski, "Cost Minimization of Partitions into Multiple Devices", 30th ACM/IEEE Design Automation Conference.
[4] S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi, "Optimization by Simulated Annealing", Science, 220(4598), pp. 498-516, May 1983
[5] J. L. Hennessy and D. A. Patterson, "Computer Architecture A Quantitative Approach," , pp. 62