Sea Cucumber A Synthesizing Compiler for
- 格式:pdf
- 大小:160.29 KB
- 文档页数:11
SeaCucumber:ASynthesizingCompilerforFPGAs
JustinL.Tripp,PrestonA.Jackson,andBradL.HutchingsBrighamYoungUniversity,Provo,Utah
Abstract.SeaCucumber(SC)isasynthesizingcompilerforFPGAsthatacceptsJavaclassfilesasinput(generatedfromJavasourcefiles)andthatgeneratescircuitsthatexploitthecoarse-andfine-grainedpar-allelismavailableintheinputclassfiles.Programmersdeterminethelevelofcoarse-grainedparallelismavailablebyorganizingtheircircuitasasetofinter-communicating,concurrentthreads(usingstandardJavathreads)thatareimplementedbySCasconcurrenthardware.SCauto-maticallyextractsfine-grainedparallelismfromthebodyofeachthreadbyprocessingthebytecodescontainedintheinputclassfilesandem-ploysconventionalcompileroptimizationssuchasdata-flowandcontrol-flowgraphanalysis,dead-codeelimination,constantfolding,operationsimplification,predicatedstaticsingleassignment,if-conversion,hyper-blockformation,etc.TheresultingEDIFfilescanbeprocessedusingXilinxplaceandroutesoftwaretoproducebitstreamsthatcanbedown-loadedintoFPGAsforexecution.
1IntroductionTheprincipalchallengefacingdevelopersofsynthesizingcompilersforFPGAsthatarebasedonsequentialprogramminglanguagesisthediscoveryandex-tractionofsufficientparallelism.FPGAsystemstypicallyoperateataclockratelessthan1/10thatofaprocessorfabricatedinthesameprocess.Inordertoovercomethisclockratepenalty,anFPGAcircuitmustexploitmorethananorderofmagnitudemoreavailableparallelismthanaconventionalsoftwarecompiler.Extractingparallelismfromsequentialdescriptionsisalreadyaverydifficultproblem.Requiringthatthecompilerautomaticallyextractevenmoreparallelismwillonlymaketheproblemthatmuchmoredifficult.SCtakesapragmaticapproachtotheproblemofextractingparallelism.SCrequiresthatprogrammersexposecoarse-grainedparallelismbyorganizingtheirapplicationasstandardJavathreadsthatintercommunicateusingprovidedli-braryfunctions.SCthenanalyzesthebodyofeachthreadandusesavarietyofcompilerandcircuitoptimizationtechniquestoextractfine-grainedparallelism.Experiencehasshownthatprogrammerscandoareasonablejobofmanuallyorganizingsoftwareasrelativelycoarseunitsthatoperateinparallel[1].Inad-dition,thereisagreatbodyofworkthatdealswithautomateddiscoveryandexploitationoffine-grainedparallelisminthecompilerliterature[2].Itisbelievedthatbycombiningthesetwoapproaches(programmer-exposureofcoarse-grained
M.Glesner,P.Zipf,andM.Renovell(Eds.):FPL2002,LNCS2438,pp.875–885,2002.cSpringer-VerlagBerlinHeidelberg2002876JustinL.Tripp,PrestonA.Jackson,andBradL.Hutchingsparallelismandautomateddiscoveryoffine-grainedparallelism),SCcanproduceFPGAcircuitrythatexploitsmuchmoreavailableparallelism.SCisaworkinprogressandthispapergivesabriefoverviewofitscurrentstatus,includinganoverviewoftheprogrammingmodel,presentationofanaly-sistechniquesforextractingfine-grainedparallelism,andsuggestionsforfuturework.
2RelatedWorkCompilingfromJavabytecodesisnotnew.Pastefforts,includingGALADRIELandNENYA[3]andapreviousBYUeffort[4],compileusingbyte-codesastheirinput.Collectively,theseeffortsindicatetheadvantagesofusingbytecodes.Theadvantagesinclude,amongothers,thelackofwritingandmaintainingaparser,accesstostandardcompileranddebuggingtools,andaccesstoawiderangeofavailablebyte-codeanalysisandmodificationtools.SCsignificantlydiffersfromtheseprojectsinvariousways.First,unlikeGAL-ADRIEL,SCdirectlygeneratesEDIFfilesasoutput.GALADRIELgeneratesVHDLasoutputandthusrequirestheuseofanadditionalsynthesistooltogenerateEDIFfiles.ItshouldbenotedthatbecauseSCperformsonlylimitedcircuitoptimizations,theultimatequalityofcircuitscouldbelowerwithSCthanwithamaturesynthesistool.WefeelthatthisdiscrepancyisassuagedbytheeaseofworkingwithSCasasingleintegratedtool.Workingwithtwosepa-ratesynthesistoolsforcestheusertobeconversantinbothtodebugproblems.Second,unliketheearlierworkatBYU,SCprogramscanbeverifiedbycompil-ingtheJavafileswiththestandardJavacompilerandexecutingtheclass-filesinthestandardJavaVirtualMachine.ThisfeatureeliminatestheneedforcircuitsimulationtoverifybehaviorasusedintheearlierBYUeffort.Snideretal.[5]werethefirsttoarticulatethegeneralideaofusingageneral-purposelanguagetodescribeprogrammer-exposedcoarseparallelismandau-tomaticdiscoveryoffine-grainedparallelismtoanFPGAaudience.SChasadoptedthiscoarse/fineapproachalongwiththeuseofpredicatedstaticsingleassignment(PSSA)[6]andothercompileroptimizationsdescribedbySnideretal.However,theircoarse-levelparallelprogrammingmodelusesacustomap-proachbasedonC++andinheritancewhereasSCadoptsthestandardJavathreadmodelandaugmentsitwithacommunicationmodelbasedonCommu-nicatingSequentialProcesses(CSP)[7].Inaddition,SCuseshyperblocksandif-conversionoptimizationsthatarenotdiscussedbySnideretal.andprovideswaystocontrolthebit-widthofvariablesinJava.TheGarpproject[8]appliessomeofthetechniquesanddatastructuresfoundinVLIWcompilerresearchtoFPGAsynthesis.Inparticular,Garpisolatesacriticalpathinacodesegmentandsynthesizesittoareconfigurableco-processor.SCusesmanyofthesametechniquesanddatastructuresbutdiffersfromGarpintheextenttowhichtheyareused.SCextendsthecritical-pathsynthesisperformedinGarptoentiresystemsynthesiswithmultiplepathsandmultipleparallelthreads.