A Computer Aided Design Tool For Area Optimization Using Breadth First Search Technique

Abstract

Floorplanning is the process of partitioning an area on any surface such that the partitions guarantee minimum wasted area. The technique used to partition a given are depends on the requirements of the application. In an integrated circuit design the floorplan is done on one piece of silicon and the partitions depend on other information such as the electrical wiring which must be minimized. This requires a study of the functions (area and wiring) and the relations between all functions. The technique to solve the problem is not trivial since area and wiring functions are both considered. Another example where good floorplanning is required is any material cutting process. Glass sheets come in different sizes and the requirements for any application not necessarily require the same size. So it is important to cut the required sheets from the available ones. This process will require an expert to deal with the cutting however it is not necessary to guarantee the minimization in wastages. This paper investigates a technique to minimize wastage areas and to give the best solution for multi-project with multi-sheets of different sizes. The algorithm is based on the breadth first which expand a tree based on the number of nods given. Two examples are given to demonstrate the results of the algorithm.