John Lillis

Research Interests:

My main area of interest is in Electronic Design Automation (EDA). I am particularly interested in layout optimization, logic synthesis, programmable devices and timing optimization. I also have an interest in bridging so-called ``optimization disconnects'' between traditionally sequential design phases (e.g., between logic synthesis and physical design). This work is essentially applied combinatorial optimization and so I have a natural interst in areas such as local search, Integer Linear Programming, optimality studies, and lower bounding techniques.

Books and Book Chapters

“Generalized Buffer Insertion,” M. Hrkic, J. Lillis; In Handbook of Algorithms for VLSI Physical Design Automation, C. Alpert, S. Sapatnekar, and Dinesh D. Mehta, Editors, CRC Press, 2007; ISBN 0-8493-7242-9

“Algorithms for Timing-Driven Routing”, J. Lillis; in Optimizations in VLSI Designs: Floorplanning, Timing and Layout (Kluwer Academic Publishers); pp. 125-153. Editors: D.-Z. Du, B. Lu, S. Sapatnekar; ISBN-13: 978-1402000898

“Interconnect Analysis and Synthesis,” Chung-Kuan Cheng, John Lillis, Shen Lin, Norman Chang, Wiley Interscience, 2000; ISBN 0-471-29366-0

Journal Articles

“A Layout-Level Logic Restructuring Framework for LUT-Based FPGAs,” Hosung Kim; Lillis, J.; IEEE Transactions on Computer-Aided Design of Integrated Circuts and Systems, Volume 27, Issue 12, Dec. 2008 Page(s):2120 – 2132

“An Approach to Placement-Coupled Logic Replication,” M. Hrkic, J. Lillils, G. Beraudo, IEEE Transactions on Computer-Aided Design of Integrated Circuts and Systems, Nov. 2006, Vol 25, Issue 11, pp. 2539-2551

“RBI: Simultaneous Placement and Routing Optimization Technique,” Jariwala, D.; Lillis, J.; IEEE Transactions on Computer-Aided Design of Integrated Circuts and Systems, Volume 26, Issue 1, Jan. 2007 Page(s):127 – 141

“Buffer Tree Synthesis with Consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost, Congestion and Blockages,” M. Hrkic, J. Lillis, IEEE Transactions on Computer-Aided Design, April 2003

“A Fast Algorithm For Context-Aware Buffer Insertion”, A. Jagannathan, S.-W. Hur, J. Lillis, ACM Transactions on Design Automation of Electronic Systems (TODAES), Vol. 7, No. 1, January 2002, pp. 173-188

“Relaxation and Clustering in a Local Search Framework: Application fo Linear Placement,” S.-W. Hur, J. Lillis; VLSI Design, 2002 Vol. 14, (2), pp. 143-154

“Buffered Steiner Trees for Difficult Instances,” C.J. Alpert, G. Gandham, M. Hrkic, J. Hu, A.B. Kahng, J. Lillis, B. Liu, S.T. Quay, S. Sapatnekar, A. Sullivan, IEEE Transactions on Computer-Aided Design, vol 21, no. 1, pp. 3-14, Jan. 2002

“Timing-Driven Maze Routing,” S.-W. Hur, A. Jagannathan, J. Lillis; IEEE Transactions on Computer Aided Design, Feb. 2000, vol. 19, no. 2, pp. 234-241.

“Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion,” J. Lillis, C.-K. Cheng, IEEE Transactions on Computer Aided Design, Mar. 1999, vol. 18, no. 3, pp. 322-331

“Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, IEEE Journal of Solid State Circuits, vol. 31, no. 3, March 1996, pp. 437-447 (invited submission).

“Data Flow Partitioning for Clock Period Latency Minimization,” L.-T. Liu, M. Shih, J. Lillis, C.-K. Cheng, IEEE Transactions on Circuits and Systems, Mar. 1997, vol. 44 (no. 3), pp. 210-220.

Conference Articles

“A Method for Improved Final Placement Employing Branch-And-Bound with Hierarchical Placement Encoding and Tightened Bounds,” Xitian Li, John Lillis, Proceedings International Symposium on Quality Electronic Design-Asia 2009. Pages 304-312“A framework for layout-level logic restructuring,” H. Kim, J. Lillis; Proc. International Symposium on Physical Design (ISPD 2008), pp. 87-94, Portland, OR; 2008.“Trunk decomposition based global routing optimization” D. Jariwala, J. Lillis; Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, pp. 472-479, San Jose CA.”Techniques for improved placement-coupled logic replication,” H. Kim, J. Lillis, M. Hrkic, 16th ACM Great Lakes symposium on VLSIPhiladelphia, PA, USA Pages: 211 – 216 Year of Publication: 2006 ISBN:1-59593-347-6

“An LP-Based Methodology for Improved Timing-Driven Placement”, Q. Wang, J. Lillis, S. Sanyal; Proc. Asia and South Pacific Design Automation Conference; Jan. 18-21 2005, Shanghai China.

“On interactions between routing and detailed placement,” D. Jariwala, J. Lillis, Proc. IEEE International Conference on Computer-Aided Design, Nov. 7-11, 2004, San Jose, CA, pp. 387-393.

“An approach to placement-coupled logic replication,” M. Hrkic, J. Lillis, G. Beraudo. 2004 ACM/IEEE Design Automation Conference. San Diego CA, Jun 2004.

“Addressing the Effects of Reconvergence on Placement-Coupled Logic Replication,” M. Hrkic, J. Lillis, 13th International Workshop on Logic and Synthisis, Temecula CA, Jun 2004.

“Timing Optimization of FPGA Placements by Logic Replication,” G. Beraudo, J. Lillis, 2003 ACM/IEEE Design Automation Conference, pp. 196-201 (Best Paper Award Nominee).

“Buffer Tree Synthesis with Consideration of Temporal Locality, Sink Polarity Requirements, Solution Cost and Blockages,” M. Hrkic, J. Lillis,2002 ACM International Symposium on Physical Design (ISPD 2002), pp. 98, San Diego, April 2002.

“S-Tree: a Technique for Buffered Routing Tree Synthesis,” M. Hrkic, J. Lillis, Design Automation Conference, New Orleans, June 2002. (A version also appeared at the Workshop on Synthesis and System Integration of Mixed Technologies, Nara, Japan, Oct. 2001.)

“Buffered Steiner Trees for Difficult Instances”; C. J. Alpert, G. Gandham, M. Hrkic, J. Hu, A. B. Kahng, J. Lillis, B. Liu, S. T. Quay, S. S. Sapatnekar, A. J. Sullivan; 2001 ACM International Symposium on Physical Design (ISPD 2001).

“Mongrel: Hybrid Techniques for Standard Cell Placement,” S.-W. Hur, J. Lillis; Proc. IEEE International Conference on Computer-Aided Design; November 5-9, 2000, San Jose, CA; pp. 165-170.

“A Fast Algorithm for Context-Aware Buffer Insertion,” A. Jagannathan, S.-W. Hur, J. Lillis; Proc. 37th ACM/IEEE Design Automation Conference, LA, CA, Jun. 5-9, pp. 368-373.

“Relaxation and Clustering in a Local Search Framework: Application to Linear Placement,” S.-W. Hur, J. Lillis; Proc. 36th ACM/IEEE Design Automation Conference, New Orleans, LA, Jun. 21-25, 1999, pp. 360-366.

“Timing-Driven Maze Routing,” S.-W. Hur, A. Jagannathan, J. Lillis; Proc. 1999 ACM International Symposium on Physical Design, April 12-14 1999, Monterey, CA, pp. 208-213.

“Table-Lookup Methods for Improved Performance-Driven Routing,” J. Lillis, P. Buch; Proc. 35th ACM/IEEE Design Automation Conference, San Francisco, CA, Jun. 1998, pp. 368-373. (Preliminary version appeared at the 1997 ACM/IEEE International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, Austin TX, Dec. 1997.)

“Timing Optimization for Multi-Source Nets: Characterization and Optimal Repeater Insertion,” J. Lillis, C.-K. Cheng, Proc. 34th ACM/IEEE Design Automation Conference, Anaheim, CA, Jun. 1997, pp. 214-219.

“New Techniques for Performance Driven Routing with Explicit Area/Delay Tradeoff and Simultaneous Wire Sizing,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, C.-Y. Ho, Proc. 33rd ACM/IEEE Design Automation Conference, Las Vegas, Jun. 1996, pp. 395-400.

“New Spectral Linear Placement and Clustering Approach,” J. Li, J. Lillis, L.-T. Liu, C.-K. Cheng, Proc. 33rd ACM/IEEE Design Automation Conference, Las Vegas, Jun. 1996, pp. 88-93.

“Algorithms for Optimal Introduction of Redundant Logic for Timing and Area Optimization,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, Proc. IEEE International Symposium on Circuits and Systems, Atlanta, May 1996, v. 4, pp. 452-455.

“Simultaneous Routing and Buffer Insertion for High Performance Interconnect,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, Proc. Sixth IEEE Great Lakes Symposium on VLSI, Ames, Iowa, Mar. 1996, pp. 148-153. Also appeared by invitation at the Fifth ACM/SIGDA Physical Design Workshop, 1996, pp. 7-12.

“Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, Proceedings of 1995 IEEE International Conference on Computer-Aided Design, pp. 138-143.

“Linear Decomposition Algorithm for VLSI Design Applications,” J. Li, J. Lillis, C.-K. Cheng, Proceedings of 1995 IEEE International Conference on Computer-Aided Design, pp. 223-228.

“Optimal and Efficient Buffer Insertion and Wire Sizing,” J. Lillis, C.-K. Cheng, T.-T. Y. Lin, Proceedings of IEEE 1995 Custom Integrated Circuits Conference, pp. 259-262.

Ph.D. Dissertation

“Algorithms for Performance Driven Design of Integrated Circuits”; CSE Dept., UC San Diego, 1996.

BS Computer Science, University of Washington, 1989
MS Computer Science, UC San Diego, 1992
PhD Computer Science, UC San Diego, 1996