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.c󰀁Springer-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.