Physical Design Automation for System-on-Packages

PhysicalDesignAutomationforSystem-on-Packagesand3D-IntegratedCircuitsAThesisPresentedtoTheAcademicFacultybyJacobRajkumarMinzInPartialFulllmentoftheRequirementsfortheDegreeDoctorofPhilosophySchoolofElectricalandComputerEngineeringGeorgiaInstituteofTechnologyDecember2006PhysicalDesignAutomationforSystem-on-Packagesand3D-IntegratedCircuitsApprovedby:Asst.ProfessorSungKyuLim,AdvisorSchoolofElectricalandComputerEngineeringGeorgiaInstituteofTechnology,AdviserProfessorMadavanSwaminathanSchoolofElectricalandComputerEngineeringGeorgiaInstituteofTechnologyProfessorAbhijitChatterjeeSchoolofElectricalandComputerEngineeringGeorgiaInstituteofTechnologyProfessorGabrielRincon-MoraSchoolofElectricalandComputerEngineeringGeorgiaInstituteofTechnologyAsst.ProfessorGabrielH.LohCollegeofComputingGeorgiaInstituteofTechnologyDateApproved:20thJuly2006Dedicatedtomymother,MaryIgnatiaMinzandmylatefather,AnthonyMinziiiACKNOWLEDGEMENTSIwouldliketoexpressmydeepestgratitudetoProf.SungKyuLimforhissupportandguidanceduringmyPhDatGeorgiaTech.Hissupporthasbeencrucialforthesuccessfulcompletionofthisresearchandthesis.IalsothankthemembersofmyreadingcommitteeProf.MadhavanSwaminathan,andProf.AbhijitChatterjee,andothermembersofmydis-sertationcommittee,Prof.GabrielRincon-Mora,andProf.GabrielLohfortheirtimeandhelpfulfeedbacks.Prof.ParthaPratimChakrabarti,andProf.DipwanitaRaychaudhurifromIndianInstituteofTechnology,KharagpurhavebeenveryinstrumentalandinuentialinmydecisiontopursuePhD.Theywillalwayshavemyrespectandappreciationforbeingexcellentteachers.IwouldalsoliketorememberlateProf.JohnUyemurawhoencouragedmetopursuePhDatGeorgiaTech.Iwouldliketoextendmyheartfeltthankstothemembers(pastandpresent)oftheGTCADgroup:MongkolEkpanyapong,FaikBaskaya,MichaelHealy,SomasThyagaraja,EricWong,andMohitPathakfortheirfriendship,collaboration,andencouragement.IwouldalsoliketoexpressmythankstoPinarKorkmaz,whohasbeenveryforthcomingwithanyhelpIneededduringmyPhDcareer.ThanksaredueinnosmallparttoallmyfriendsinAtlanta,andelsewhere,someofwhomIhaveknownfromthedaysofmyundergradinIITKharagpur.However,IwouldliketoextendspecialthankstoMrinmoyGhosh,AtriDutta,BevinPerumana,andBiswajitMitra,whohavebeenextremelyhelpful,andgenerouswiththeiradvices.AheartythanksisalsoduetoRachanaMukhopadhyay,whoproofreadpartsofmythesis.Myfamilyhasalwaysbeensupportive,butmymotherhasbeenthegreatestsourceofinspirationforme.Surely,notsparingtherodonacertainchildhasresultedinthisdissertation.IwouldnothavebeenwhereIamtoday,ifnotforherconstantprayers,andsteadfastbeliefintheGod.AndforalltheendowmentsthatIhavehad,IoermythankstotheGodAlmighty.ivTABLEOFCONTENTSDEDICATION......................................iiiACKNOWLEDGEMENTS..............................ivLISTOFTABLES...................................viiiLISTOFFIGURES..................................xSUMMARY........................................xiiiIINTRODUCTION.................................11.1ThesisStatement................................41.2ProblemStatement...............................51.3Contributions..................................51.4ThesisOrganization...............................7IIORIGINANDHISTORYOFTHEPROBLEM..............92.1Background...................................92.2GlobalRouting.................................112.3OpticalRouting.................................122.4NoiseandCongestionAwareFloorplanning.................132.5ClockDistribution................................14IIIPERFORMANCE-DRIVENGLOBALROUTING............153.1MCMvsSOPRouting.............................153.2ProblemFormulation..............................173.2.1SOPRoutingResource.........................173.2.2SOPRoutingProblem.........................183.3Overviewof3PGRAlgorithm.........................203.3.1SOPPinRedistribution........................223.3.2CoarsePinDistribution........................243.3.3DetailedPinDistribution........................263.3.4SOPLayerAssignment.........................293.3.5SOPChannelAssignment.......................313.4ExperimentalResults..............................34v3.5Conclusions...................................39IV3DOPTICALROUTING............................414.1SOPOpticalInterconnectTechnology.....................414.2ProblemFormulation..............................434.3SOPOpticalRoutingAlgorithm........................454.3.1OverviewoftheAlgorithm.......................454.3.2WaveguideConstructionAlgorithm..................464.3.3OpticalNetSelectionAlgorithm....................514.3.4OpticalRouting.............................514.4ExperimentalResults..............................534.5Conclusions...................................55VCONGESTIONANDNOISE-DRIVENFLOORPLANNING.....565.1ProblemFormulation..............................565.1.1SOPPlacementProblem........................565.23DPowerSupplyNoiseModeling.......................575.33DDecouplingCapacitorPlacement.....................595.43DWireCongestionComputation.......................615.5OverviewoftheAlgorithm...........................635.6ExperimentalResults....