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

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.

Authors:

• Jae Young Park
• Soongyu Kwon
• Kyu Han Kim
• Hyeong Geon Lee
• Jong Tae Kim

Keywords:

• lowest cost chip set
• MCNC benchmark
• multi-way partitioning.

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