DIRECTORY OrderedRefArray, IPCTG, IPCoTab, IPTop, IPPlaceKit; IPPlaceBinPack: CEDAR DEFINITIONS = BEGIN Components: TYPE = IPPlaceKit.Components; OrderingFn1: IPPlaceKit.OrderingFn; OrderingFn2: IPPlaceKit.OrderingFn; PlaceEvaluator1: IPPlaceKit.PlaceEvaluator; PlaceEvaluator2: IPPlaceKit.PlaceEvaluator; PlaceEvaluator3: IPPlaceKit.PlaceEvaluator; PlaceCompTGen1: IPPlaceKit.PlaceCompTGen; PlaceCompTGen2: IPPlaceKit.PlaceCompTGen; RemoveEvaluator1: IPPlaceKit.RemoveEvaluator; RemoveCompsTGen1: IPPlaceKit.RemoveCompTGen; END. ¶--File: IPPlaceBinPack.mesa Last Edited by: CSChow, February 2, 1985 2:37:10 am PST -- Intro: This is some sample heuristics on 'BIN-PACKING' -- Assumes no netlength and no notion of types; components can be non-rectangular --Ordering Functions: --Order by bounding area -- VARS: (I) of1Depth: PUBLIC NAT _ 3; (II) of1Breadth: PUBLIC NAT _ 3; (iii) of1EnumIncreasing: PUBLIC BOOL _ TRUE; -- Uses OrderingFn1 -- VARS: (i) of2DepthN and (ii) of2BreadthN N = [1..5] -- (III) of2EnumIncreasing: BOOL --Place Evaluator -- Just use assembly area, NO pruning -- vaue is assembly are -- simple prunning by including in area of unplaced components --value is assembly area --Use exact prunning. ie. prune => with high probablity of not being good -- Also incorp method of precomputing the area once only --PlaceComp Trial generator --Generate all grow position: -- (i) Grow and Grow1 -- (ii) Do Various IPPlaceKit.CompactComp0 --VAR: Number generated controlled by: pctgX1Keep: PUBLIC NAT _ 10 -- (i) Grow and Grow1 -- (ii) and IPPlaceKit.CompactComp1 --VAR: Number generated controlled by: pctgX2Keep: PUBLIC NAT _ 10 --RemoveComp Evaluator -- Use area of assembly. --NO prunning. Havent figure out how to --RemoveComp Trial generator --Actually removes each component, exhaustively. --value of removal = active area + (bounding area of comp removed _ more thought) --VARS: (i) rctg1Keep: PUBLIC NAT _ 3, and(ii) rctg1ShrnkDn: PUBLIC IPCTG.ChType _ hor; ÊJ˜J™J™7J™codešÏk ˜ K˜Kšœ˜K˜K˜Kšœ˜—K˜šœœœ˜)K™9K™QK˜Kšœœ˜)K˜K™šœ#˜#K™šœœœ™&Kšœœœ™"Kšœœœœ™,——K˜K˜šœ#˜#Kšœ™Kšœ6™6Kšœ ™ —K•StartOfExpansion -- [top: IPTop.Ref, yetToPlace: IPPlaceKit.Components, cutOff: INT _ 2147483647] RETURNS [value: INT, prune: BOOL _ FALSE] -- ˜K™šœ+˜+K™%—K˜šœ+˜+K™KšÏc>™>—K™šœ+˜+K™K™IKšž8™8—K˜K™šœ)˜)™K™Kšœ*™*—Kšž4œœ™C—K˜šœ)˜)K™Kšœ$™$Kšž4œœ™CK˜—K˜K™šœ-˜-K™Kšž'™'—K˜K™šœ,˜,K™1K™QKš œœœœœ™W—K˜Kšœ˜——…—