Synthesis Challenges for Next-Generation High-Performance and High-Density PLDsSynthesis Challenges for Next-Generation High-Performance and High-Density PLDsJason CongDepartment of Computer ScienceUniversity of California,Los Angeles, USAJason CongDepartment of Computer ScienceUniversity of California,Los Angeles, USASongjie XuAplus Design Technologies, Inc.Los Angeles, USASongjie XuAplus Design Technologies, Inc.Los Angeles, USASlide 2OutlineOutlineu Introductionu Synthesis Challenges for New Architecturesu Synthesis Challenges for High Density and High Performanceu Concluding Remarksu Introductionu IntroductionSlide 3PLD Industry GrowthPLD Industry Growthu Enjoyed the exponential growth as the rest of the semiconductor industryu With an even faster rateIntroduction27.78%36.07%24.50%15.71%0.00%5.00%10.00%15.00%20.00%25.00%30.00%35.00%40.00%Annual Growth Rate (1994-1998)Company/IndustrySemiconductor Industry Altera Intel LSI LogicSlide 4DefinitionsDefinitionsu PLD (Programmable Logic Device)z CPLD (Complex PLD)z Extensions of early PALz Consist of PLA-like blocksz Macrocellz FPGA (Field Programmable Gate Array)z Typically based on look-up tables (LUTs)z Multiple LUTs form a programmable logic block (PLB)IntroductionSlide 5CPLDCPLDu Example: Altera MAX 7000IntroductionSlide 6MacrocellMacrocellu Example: Altera MAX 7000z Each macrocell has a logic array, a product-term select matrix, and a programmable registerIntroductionSlide 7DefinitionsDefinitionsu PLD (Programmable Logic Device)z CPLD (Complex PLD)z Extensions of early PALz Consist of PLA-like blocksz Macrocellz FPGA (Field Programmable Gate Array)z Typically based on look-up tables (LUTs)z Multiple LUTs form a programmable logic block (PLB)IntroductionSlide 8FPGAFPGAu Example: Xilinx XC 4000IntroductionSlide 9PLBPLBu Xilinx XC 4000z Each PLB has two 4-LUTs, one 3-LUT and 2 FFsIntroductionSlide 10Advance of PLD ArchitecturesAdvance of PLD ArchitecturesIntroduction1980’s 1998/1999AlteraMAX 5000:32-192 P-terms600-3,750 usablegatesAPEX 20K:51,840 Logic elements (LUTs)442,368 RAM bits3,456 P-term macrocells60,000-1.5M usable gatesXilinxXC 2000:64-100 LUTs1,200-1,800 logicgatesVirtex:58K-4M system gates1Mb distributed RAM832Kb embedded memory1980’s 1998/1999AlteraMAX 5000:32-192 P-terms600-3,750 usablegatesAPEX 20K:51,840 Logic elements (LUTs)442,368 RAM bits3,456 P-term macrocells60,000-1.5M usable gatesXilinxXC 2000:64-100 LUTs1,200-1,800 logicgatesVirtex:58K-4M system gates1Mb distributed RAM832Kb embedded memorySlide 11PLD Synthesis Tends to Fall Behind ...PLD Synthesis Tends to Fall Behind ...u Additional features and capabilities in the new architecture often place new requirements for synthesis toolsu Higher density and higher performance demand better scalability and more efficient optimizationu Devil is always in the software …z Tool effort is often being underestimatedz Quick customization from ASIC or existing PLD synthesis tool leads to considerably inferior resultsz Software is often the bottleneck of new PLD product release ...IntroductionSlide 12Challenges to PLD SynthesisChallenges to PLD Synthesisu Support for new PLD architecturesz Hierarchical architecturesz Heterogeneous architecturesu Support for high-performance and high-density PLD designsz Layout-driven synthesisz Incremental synthesisz IP-based synthesisIntroductionSlide 13OutlineOutlineu Introductionu Synthesis Challenges for New Architecturesu Synthesis Challenges for High Density and High Performanceu Concluding Remarksu Synthesis Challenges for New Architecturesu Synthesis Challenges for New ArchitecturesSlide 14PLD Architecture DevelopmentPLD Architecture Developmentu Two important trendsz Hierarchical architecturesz Heterogeneous architecturesu Synthesis needsSynthesis Challenges for New ArchitecturesSlide 15PLD Architecture Development Trend ……Hierarchical ArchitecturesPLD Architecture Development Trend ……Hierarchical Architecturesu Basic Ideaz Group of basic logic blocks into clustersz Fast local programmable interconnects inside clustersz May have multiple levels of hierarchyu Benefitsz Exploit the inherent locality of interconnections in most applicationsz Lead to the improvement in both performance and densitySynthesis Challenges for New ArchitecturesSlide 16Example Hierarchical ArchitecturesExample Hierarchical Architecturesu Altera FLEX 10Kz Each LAB has 8 LEsz Each LE has a 4-LUT and a programmable registerSynthesis Challenges for New ArchitecturesSlide 17Two Types of ClustersTwo Types of Clustersu Hard-wired connection based cluster (HCC)z Intra-cluster connection is formed by hard wiresz e.g. CLB in XC4000u Programmable interconnection based cluster (PIC)z Intra-cluster connection is formed by a local programmable interconnection arrayz e.g. LAB in FLEX 10K and APEX 20KSynthesis Challenges for New ArchitecturesSlide 18Existing Synthesis Results for HCCExisting Synthesis Results for HCCu Traditional approachz Map into LUTs and then combine the LUTs to form HCCs in a heuristic post-processing stepu Recent advance [Cong & Hwang, FPGA’97]z Use Boolean matching techniques to completely characterize the set of functions that can be implemented in a HCCz Map a netlist directly into HCCsSynthesis Challenges for New ArchitecturesSlide 19Hard-Wired Connection Based Clusters (HCCs)Hard-Wired Connection Based Clusters (HCCs)u Example: Xilinx XC 4000 CLBz Each CLB has two 4-LUTs connected to a 3-LUTSynthesis Challenges for New ArchitecturesSlide 20u Characterization based on functional decompositionz f (X) = H ( F (X1) , G (X2) ),z f(X) = H ( F (X1) , G (X2) , x ),z f(X) = H (F(X1,x), G(X2), x ), z f(X) = H (F(X1,x), G(X2,x), x ).u Conditionsz F and G input sizes ≤ 4u Result: matched all “difficult examples” (over 1,700) from Xilinxz Best known tool produced only about 70% matchXC4K CLBGFHxf(X)Example: Boolean Matching for XC4K CLBExample: Boolean Matching for XC4K CLBSynthesis Challenges for New ArchitecturesSlide 21Example: Mapping to XC4K CLBExample: Mapping to XC4K CLBo Given a function f(0,1,2,3,4,5) wherea = 1’ + 3, b = 1 + 3f = 0’245b’ + 0’245’b + 0’145b + 012’5’a + 0’2’4’5a + 025b + 0’2’5’a’ + 045a’ + 05’b’o How many XC4K CLBs are needed to implement f(0,1,2,3,4,5) ?Synthesis Challenges for New ArchitecturesSlide 22Mapping Packing #CLBs #LevelsChortle-crf simple 9 4FlowMap simple 8 3FlowMap functional 6 3Boolean 1 1GFH312054The Boolean matching resultExample: Mapping to XC4K CLB