Course Name: CS6800 : VLSI Design Automation Algorithms

Description: Review of basics: Time complexity? Problem intractability? Linear programming? Lagrangian relaxation, Graph algorithms. Paths, trees,. Search algorithms? Network flows and cuts, Convex optimization? greedy methods? hill climbing? dynamic programming? geometric programming. Geometric data structures? problems on a plane? representation of a circuit? representation of a layout. EDA industry roadmap, design methodologies. Partitioning, Floorplanning and Placement: Circuit partitioning using Kernighan-Lin, Fiduccia-Mattheyses and hMetic methods. Partitioning of graphs and hypergraphs. Floorplanning using slicing floorplan techniques and Wong-Liu?s simulated annealing algorithm? Placement using simulated annealing, force-directed methods? Partitioning-based placement? Gate array and standard cell placement. Recent placement methodologies. Routing: Global routing? Steiner trees? Maze routing. Detailed routing issues: channel routing? Vertical/Horizontal constraint graphs? Leftedge algorithm? Greedy channel routin

Slot: A

RoomNo: CS26

Instructor: Shankar Balachandran

Period: JUL-NOV 2013

This page was created on: Thursday 19th of September 2013 09:42:16 PM