A Task Dependence Net Generator for Concurrent Ada Programs
Yoshiaki Kasahara, Jingde Cheng, Kazuo Ushijima · 2007
ATaskDep endenceNetGeneratorforConcurrentAdaProgramsYoshiakiKasahara,JingdeCheng,andKazuoUshijimaDepartment ofComputerScienceandCommunication EngineeringKyushuUniversity6-10-1Hakozaki, Higashi-ku,Fukuoka 812,Japane-mail:fkasahara, cheng, [email protected] vetypesofbasicprogramdep endencesinconcurrentprograms.TaskDep endenceNet(TDN)isan arc-classi ed digraph to explicitly represent the vetyp es of basic program dep endences in concurrent Adaprograms.Thispap erdescrib esalgorithmstocom-puteTDNsforaclassofconcurrentAdaprograms,andshowsthestructureimplementationofourTDN generator for concurrent Ada programs based onthese algorithms.The pap er also discusses some appli-cationsoftheTDNgeneratorindevelopmentcon-currentAdaprograms.1Intro ductionWhenwereadaprogramandunderstandtheb ehav-ioroftheprogram,itisnecessarytoreadcontrolowanddataowintheprogramdeterminere-lationshipb etweenstatements.Iftheexecutionofastatement in a program a ects the execution of anotherstatement,thereisadep endencerelationshipb etweenthetwostatements.Programdep endencesaresuchdependencerelationshipsholdingb etweenstatementsinaprogramthataredeterminedbycontrolowanddata ow in the program.There are two typ es of basicprogram dep endences prop osed and studied for sequen-tial programs in the literature:the control dep endencethatisdeterminedbycontrolowinaprogram,andthedatadep endencethatisdeterminedbyowinaprogram.Sincecapturingprogramdep endencesb etweenstatementsofaprogramisindisp ensabletomanysoftwaredevelopmentactivities,adep endence-basedprogramrepresentationhasmanyapplicationsinvar-ioussoftwaredevelopmentactivitiesincludingpro-gramoptimization,parallelization,understanding,testing, debugging,maintenance, andcomplexity met-rics[1][8][9][10][11][12][16].Forexample,programde-p endencegraph[8][10][11][12],whichexplicitlyrepre-sentsb othcontrolanddataasequen-tial program, has b een developed as an imp ortant pro-gramrepresentationto olusedincompilerconstruc-tion and software testing, debugging, and maintenance.However, although a number of dep endence-based pro-gramrepresentationshaveb eenprop osedandstud-iedforsequentialprograms,untilrecently,thereisnodep endence-basedrepresentation prop osedforconcur-rentprograms.Ingeneral,aconcurrentprogramconsistsofnum-b erofpro cesses,andtherefore,ithasmultiplecontrolows andmultiple dataws.Thesecontrol ows anddata ows are not indep endent b ecause of the existenceof interpro cess synchronization among multiple controlows andinterpro cesscommunicationamongmultipledataowsinprogram.Moreover,pro cessconcurrentprogrammaynondeterministicallyselectacommunicationpartneramonganumb erofpro cessesreadyforcommunicationwithpro cess.Itisobvi-ous that only using usual control and data dep endencesprop osed for sequential programs is inadequate for rep-resentingfullb ehaviorofaconcurrenprogram.Inadditiontotheusualcontrolanddatadep en-dences,Chengprop osedthreenewtypesofbasicpro-gramdep endencesinconcurrentprograms,namedthe selection dep endence, synchronization dep endence,and communication dep endence, which are determinedby interaction b etween multiple control ows and mul-tipleowsinprograms,andanewpro-gramrepresentationforconcurrentprograms,namedthePro cessDep endenceNet(PDN),whichisanarc-classi eddigraphexplicitlyrepresentthe vetypesofbasicprogramdep endencesintheprograms[5][6].TaskDep endenceNet(TDN)isakindofPDNthatappliedtoconcurrenAdaprograms.But,thede -nitionofPDNisnotconstructive.Also,Chengdidnotgiveametho dtogeneratePDNsforconcurrent{315