/****************************************************************************/ /* Released Software: Fast Buffer Insertion for Interconnect Optimization Version 1.1: Sept. 2004 Author: Zhuo Li -- zhuoli@ee.tamu.edu Author: Weiping Shi -- wshi@ee.tamu.edu All Rights Reserved Description: This software contain codes for the buffer insertion to maximize the slack at the source. Two algorithms are included: Van Ginneken's O(n^2) time algorithm, Lillis, Cheng and Lin O(B^2n^2) time algorithm. and Shi and Li's fast buffer insertion (FBI) algorithm. For more detailed description about the two algorithms, see "Buffer placement in distributed RC-tree network for minimal Elmore delay," by L. P. P. P. van Ginneken, International Symposium on Circuits and Systems , pp. 865-868, 1990. "Optimal wire sizing and buffer insertion for low power and a generalized delay model," by J. Lllis, C.K. Cheng and T.-T. Y. Lin, IEEE J. Solid-State Circuits, vol. 31(3), pp. 437-447, 1996. "An O(nlogn) time algorithm for optimal buffer insertion", by Weiping Shi and Zhuo Li, Proc. of 40th Design Automation Conference (DAC), 2003, pp. 580-585. "A Fast Algorithm for Optimal Buffer Insertion", by Weiping Shi and Zhuo Li, IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, to appear. */ /****************************************************************************/ The programs are available on "as is" basis. They are not guaranteed to be free of bugs, and the authors assume no responsibility for any potential problems. The programs are designed to run under Sparc Solaris 2.7 or above. PACKAGE FBI: dynamically linked binary file FBI_st: statically linked binary file routing_tree.m: MATLAB program to read the output tree and buffer information SYNOPSIS buffer_insert -f netfile -b libraryfile [-t] [-o] [-d] OPTIONS -f netfile topology file filename. -b libraryfile Buffer Library filename. -t Print the time and memory used by the buffer insertion algorithm. -o Print nonredundent solutions before the source, detail memory usage. -d Print debugging information. INPUT FORMAT Use the format described in sample.net to build a tree. Use the format described in sample.lib to build the technology file. Wire Segmenting coef: Define how many segments are divided for each original edge Van Ginneken (1) or FBI Algorithm (2): 1: Van Ginneken O(n^2) and Lillis O(B^2n^2) Algorithm 2: FBI Algorithm OUTPUT 1. The slack after buffer insertion and total number of buffers added are printed. 1. The buffer location information is stored in file with netfile.buf extension name. 2. The net file after segmenting is stored in file netfile.finalnet. 3. Use routing_tree.m (written in MATLAB) to read the netfile.buf and .finalnet to display the tree and buffer information SAMPLE Eight sample net topology files are included: p1.net, p2.net, r1.net, r2.net, r3.net, r4.net, r5.net, long_line.net. p1, p2, r1, r2, r3, r4, and r5 are generated by constructing routing trees with an algorithm similar to A-tree algorithm on clock net benchmarks from IBM benchmarks (from R.S. Tsay) and MCNC benchmarks (from DAC90 paper by Jackson et al.). The details can be found at http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/BST/ or paper "On the Bounded-Skew Clock and Steiner Routing Problems", by D. J.-H. Huang, A. B. Kahng, and C.-W. A. Tsao, Proc. 32nd ACM/IEEE Design Automation Conf., 1995, pp. 508-513. long_line are a two-pin net randomly generated. Two buffer library sample files are included: buffer.lib and buffer5.lib.