a language to describe and simulate multiprocessor computer一種描述和模擬多處理器計算機的語言

IowaStateUniversity

DigitalRepository@IowaStateUniversity

RetrospectiveTliesesandDissertations

1972

Alanguagetodescribeandsimulatemultiprocessor

computersystems

DonaldEarlElliott

IowaStateUniversity

Followthisandadditionalworksat:/rtd

PartoftheComputerSciencesCommons

RecommendedCitation

Elliott,DonaldEarl,'Alanguagetodescribeandsimulatemultiprocessorcomputersystems"(1972).RetrospectiveThesesand

Dissertations.Paper4736.

ThisDissertationisbroughttoyouforfreeandopenaccessbyDigitalRepository@IowaStateUniversity.Ithasbeenacceptedforinclusionin

RetrospectiveThesesandDissertationsbyanauthorizedadministratorofDigitalRepository@IowaStateUniversity.Formoreinformation,please

contacthinefuku@.

INFORMATIONTOUSERS

Thisdissertationwasproducedfromamicrofilmcopyoftheoriginaldocument.

Whilethemostadvancedtechnologicalmeanstophotographandreproducethis

documenthavebeenused,thequalityisheavilydependentuponthequalityof

theoriginalsubmitted.

Thefollowingexplanationoftechniquesisprovidedtohelpyouunderstand

markingsorpatternswhichmayappearonthisreproduction.

1.Thesignor“target〃forpagesapparentlylackingfromthedocument

photographedis''MissingPage(s)Ifitwaspossibletoobtainthe

missingpage(s)orsection,theyaresplicedintothefilmalongwith

adjacentpages.Thismayhavenecessitatedcuttingthruanimageand

duplicatingadjacentpagestoinsureyoucompletecontinuity.

2.Whenanimageonthefilmisobliteratedwithalargeroundblack

mark,itisanindicationthatthephotographersuspectedthatthe

copymayhavemovedduringexposureandthuscauseablurred

image.Youwillfindagoodimageofthepageintheadjacentframe.

3.Whenamap,drawingorchart,etc.,waspartofthematerialbeing

photographedthephotographerfollowedadefinitemethodin

“sectioning"thematerial.Itiscustomarytobeginphotoingatthe

upperlefthandcornerofalargesheetandtocontinuephotoingfrom

lefttorightinequalsectionswithasmalloverlap.Ifnecessary,

sectioningiscontinuedagain-beginningbelowthefirstrowand

continuingonuntilcomplete.

4.Themajorityofusersindicatethatthetextualcontentisofgreatest

value,however,asomewhathigherqualityreproductioncouldbe

madefrom"photographs''ifessentialtotheunderstandingofthe

dissertation.Silverprintsof“photographs"maybeorderedat

additionalchargebywritingtheOrderDepartment,givingthecatalog

number,title,authorandspecificpagesyouwishreproduced.

UniversityMicrofilms

300NorthZeebRoad

AnnArbor.Michigan48106

AXeroxEducationCompany

73-9443

ELLIOTT,DonaldEarl,1938-

ALANGUAGETODESCRIBEANDSIMULATEMULTIPROCESSOR

CCMPUTERSYSTEMS.

IowaStateUniversity,Ph.D.,1972

Can5juterScience

UniversityMicrofilms,AXEROXCompany,AnnArbor,Michigan

Belowisgivenannualworksummary,donotneedfriendscandownloadaftereditordeleted!!!!!!

Welcometovisitagain

XXXXannualworksummary

Deareveryleader,colleagues:

LookbackendofXXXX,XXXXyearsofwork,havethejoyofsuccessinyourwork,havea

collaborationwithcolleagues,workinghard,alsohavedisappointedwhenencountereddifficulties

andsetbacks.Imperceptibleintenseandorderlytobeoverayear,ayear;underthelovingcare

andguidanceoftheleadershipofthecompany,underthesupportandhelpofcolleagues,through

theirownefforts,variousaspectshavemadecertainprogress,bettertocompletethejob.For

betterwork,sumupexperienceandlessons,willnowworkabriefsummary.

Tocontinuouslystrengthenlearning,improvetheircomprehensivequality.Withgood

comprehensivequalityisthepreconditionofcompletesthelaborofdutyandconditions.Ayear

alwaysputlearningintheimportantposition,tryingtoimprovetheircomprehensivequality.

Continuouslearningprofessionalskills,learnfromsurroundingcolleagueswithrichwork

experience,equipthemselveswithknowledge,theexpandedaspectofknowledge,effortsto

improvetheircomprehensivequality.

ThesecondDobest,strictlyperformtheirresponsibilities.Setupthecompany,tomaximize

thecustomertothesatisfactionofthecompany'sproducts,doagoodjobintechnicalservicesand

productpromotiontothecompany.Andcollectedonthepropertiesoftheproductsofthe

company,inordertomakeimprovementintime,maketheproductsbettermeettheusing

demandofthescene.

Threetolearntobegoodatcommunication,coordinatingassistance.On-sitetechnical

servicepersonnelshouldnotonlyhavestrongprofessionaltechnology,shouldalsohavegood

communicationability,alotofaproductduetoimproperoperationtoappearproblem,butoften

notcustomersreflectthequalityofno,sothistimeweneedtofindoutthecrux,andcustomer

communication,standardizedoperation,toavoidcustomer'smistrustoftheproductsandeventhe

damageofthecompany'simage.Someexperiencesinthepastwork,mentalityisveryimportantin

thework,worktohavepassion,keepthesmileofsunshine,canclosethedistancebetweenpeople,

easytocommunicatewiththecustomer.Dobetterinthedailyworktocommunicatewith

customersandachievecustomersatisfaction,excellenttechnicalserviceeverytime,onbehalfof

thecustomeronourproductsmuchaunderstandingandtrust.

Fourth,weneedtocontinuetolearnprofessionalknowledge,dopracticalgraspskilled

operation.Overthepastyear,throughcontinuouslearningandfumble,studiedthegasgeneration,

collectionandmethods,graduallyfamiliarwithandmasterthecompanyintroducedtheworking

principle,operationmethodofgasmachine.Withthehelpofthedepartmentleadersand

colleagues,familiarwithandmasterthelaunchofthedivisionprinciple,debuggingmethodofthe

controlsystem,andtowuhanChenGuchonggarbagepowerplantofgasmachinecontrolsystem

transformation,learntodebug,accumulatedsomeexperience.Allinall,overthepastyear,did

somework,havealsomadesomeachievements,buttheresultscanonlyrepresentthepast,there

aresomeproblemstowork,can'tmeetthehigherrequirements.Inthefuturework,Imust

developtheoneselfadvantage,lackofcorrect,fosterstrengthsandcircumventweaknesses,for

greaterachievements.LookingforwardtoXXXXyearsofwork,I'llbemoreefforts,constant

progressintheirjobs,makegreaterachievements.EveryyearIhaveprogress,thegrowthof

believewillgetgreaterreturns,Iwillmybiggestcontributiontothedevelopmentofthecompany,

believeinyourselfdobetternextyear!

Iwishyouallworkstudyprogressintheyeartocome.

Alanguagetodescribeandsimulate

multiprocessorcomputersystems

by

DonaldEarlElliott

ADissertationSubmittedtothe

GraduateFacultyinPartialFulfillmentof

TheRequirementsfortheDegreeof

DOCTOROFPHILOSOPHY

Major：ComputerScience

Approved:

Signaturewasredactedforprivacy.

InthargeofMajorWork

Signaturewasredactedforprivacy.

FortheMajorDepartment

Signaturewasredactedforprivacy.

FortheGraduateCollege

IowaStateUniversity

Ames,Iowa

1972

PLEASENOTE:

Somepagesmayhave

indistinctprint.

.Filmedasreceived.

UniversityMicrofi1ms,AXeroxEducationCompany

ii

TABLEOFCONTENTS

Page

CHAPTERI.INTRODUCTION1

CHAPTERII.LITERATUREREVIEW4

CHAPTERIII.PROGRAMMINGSYSTEM8

CHAPTERIV.MULTIPROCESSORDESCRIPTION12

CHAPTERV.SIMULATION36

CHAPTERVI.SINGLEPROCESSOREXAMPLE40

CHAPTERVII.MULTIPLEPROCESSOREXAMPLE47

CHAPTERVIII.LANGUAGEIMPLEMENTATION54

CHAPTERIX.CONCLUSION61

LITERATURECITED64

APPENDIXA:SYNTAXOFLANGUAGE66

APPENDIXB:TRANSLATORROUTINES69

APPENDIXC:SIMULATIONROUTINES109

APPENDIXD:$RUNSOURCE113

APPENDIXE:JOBCONTROL116

APPENDIXF:SINGLETEL_COMPDESCRIPTION120

APPENDIXG:SINGLETEL_COMPSIMULATION124

APPENDIXH:MULTIPLETEL_COMPDESCRIPTION172

APPENDIXI:MULTIPLETELCOMPSIMULATION177

1

CHAPTERI.INTRODUCTION

Currentlythereexistsaneedforalanguagecapableofdescribingthe

structureandbehaviorofmultiprocessorcomputersystems.Thisneedis

illustratedbythedeficiencyofastandardlanguagetodescribethe

constructionandbehaviorofpresentdaysystems.Theimplenientationof

suchalanguagewouldallowthecomputerdesignertosymbolicallydesigna

system,studyitsbehaviorandthenusethissymbolicdesignastheinput

toanautomateddesignsystemtoactuallyconstructthesystem.

Therequirementsplaceduponthislanguagearemanyandvaried.To

insurethattheresultingsymbolicdesigncouldactuallybethefirst

stepinanautomateddesignsystemthelanguagemustreflectthestructure

orthelogicalbuildingblockswithinthesystem.Thisrequirement,in

andofitself,leadstootherrequirements.First,thelanguagemust

accuratelyrepresenttheinterconnectionoftheiteratedlogiccircuits

foundindigitalcomputersystems.Thisrepresentationmustbeconcise

andcompactforeaseofreadabilityandyetreflectthebehaviorofthese

logiccircuits.

Second,thelanguagemustallowthesystemtobepartitionedintothe

variousindividualprocessorswithinthesystem.Thisfeatureallowsthe

designertoadd/deleteprocessorsto/fromthesystemandstudytheeffects

onthebehaviorofthesystemduetothesechanges.

Third,thelanguagemustdescribetheinterconnectionsbetweenthe

variousprocessorswithinthesystem.Thisenablesthedesignerto

accuratelygaugethephysicalnumberofinputandoutputlinesrequired

2

foreachoftheprocessors.Knowingthisnumbermayenablethedesigner

toreconfigurehisproposeddesigntoreducethenuniberoftheseinter-

connections.

Fourth,thelanguagemustprovideaconvenientwayforthedesigner

tospecifyhowandwhenthepossibleactionswithineachoftheprocessors

aretotakeplace.Thisspecificationofthecontrolsignalsshouldnot

havetobeexplicitlystatedbytheuseofcontrolsignalsandshould

allowforawidevarietyofactionstooccurinparallel,serial,ora

combinationofboth.

Fifth,thelanguageshouldprovideaconvenientwaytoindicatehow

theflowofcontrolmaybedependentupontheprioritybetweensignals?

Itshouldalsoexplicitlyshowhowtheflowofcontrolwithinoneprocessor

maybedependentnotonlyuponitsowninternalconditions,butalsoupon

externalconditions.

Inorderfortheresultingsystemtobecapableofbeingeffectively

simulatedotherrequirementsmustbeplaceduponthelanguage.First,

thesimulationshouldbedoneatthehighestlevelconsistentwiththe

requirementsnecessaryforautomatedconstruction.Thislevelisthe

registertransferlevel.Therehasbeenmuchworkinthesimula-

tionofdigitaldesignsatthelogiclevelandusingthestatisticalchar*

acteristicsofproposedsystems,butverylittleworkhasbeendoneto

simulatemultiprocessorsystemsattheregistertransferlevel.

Second,thesimulatorshouldallowthedesignertoinputtestcases

tocheckoutthelogicalconsistancyofthesystemunderconsideration.

3

Otherconsiderationsbesidesthestructureandbehaviorofthe

systemcomeintoplayintheimplementationofthelanguage.Oneofthese

isthatthelanguageshouldbemachinereadableinordertoallowtheuse

oftranslationtechniquesalreadydevelopedforhighlevellanguages.

Alsoitallowsamoresystematicapproachtochangestothelanguageif

theneedarises.

Andfinallythelanguageshouldreflecthowthedesignervisualizes

theflowofcontrolwithincomputersystems.Generalpurposelanguages

tendtoforcetheuser,inthiscasethecomputerdesigner,intothink-

ingnotofhowtosolvehisproblem,butratherintohowtogetthe

generalpurposelanguagetodowhathewantsittodo.

Theworkreportedonheredoesnotattempttosolvetheautomated

constructionofdigitalsystems,butinsteadfocusesitsattentionon

thedevelopmentofalanguagetodescribemultiprocessorcomputersystems

andthesimulationofthosesystemsatahighlevel.Itssignificance

comesnotonlyfromthefactthatthesymboliclanguageiscapableof

describingtheparallelandserialperformanceofeventswithina

multiprocessorsystem,butfromthesimulationofthoseevents.

u

CHAPTERII.LITERATUREREVIEW

GomanandAnderson(12)recognizedthatcomputerscouldaidinthe

designofothercomputers.Theywroteaprogramthatreadinthesystem

structureofregistersandtransferpaths,andcombinedthesewiththe

hardwarecharacteristicsandthedesiredsequencesofregistertransfers

toobtainaneworderedsequencesoflegitimateregistertransfers.From

thesenewsequencestheyformedthenecessaryBooleanequationstobuild

thesystem.Caseetal.(5)describedanautomatedlogicdesignprogramming

systemthatdocumentsthelogicdesignfortheSYSTEM/360andallowedfor

partialsimulationofthatdesign.

Proctor(24)inhissystemLDT(LogicDesignTranslator)developed

logicequationsforastoredprogramdigitalcomputerfrominformation

containedinitssystemdiagramandtheinstructionrepertoireofthe

machine.HealongwithBellandNewell(2,3),Pump1in(25)andZucker(29)

consideredthespecialcaseofastoredprogramcomputerwithitsclassical

“fetch-execute*1cycle.

Falkoffetal.(10)usedAPL(AProgrammingLanguage)byIverson(14,

15)todescribethebehavioroftheSYSTEM/360.UnfortunatelyAPLdoesn't

indicatethephysicalstructureofthesystembecauseitcontainsno

dimensionstatementsandhasoperationswithinitthatexpandandcompress

thedimensionsoftheiroperands.Takingthesediscrepanciesintoaccount,

Friedman(11)usedasubsetofAPLtorepresentthelogicdesignofa

mLcroprogrammedcomputerandgenerateditsassociatedBooleanequations?

5

Schlaepi(26)inhislanguageLOTIS(Logic,Timing,Sequencing)in-

formallypresentedmethodsofdescribingregistertransfers,timingof

thosetransfers,concurrenttransfersandgroupingofthesetransfers.He

alsosuggestedthatsuchalanguagecoulddescribeboththestructureand

behaviorofacomputer.

Schorr(27)describedanalgorithmforconvertingamicroprogram

consistingofstatementswithaconditionalpartandaregistertransfer

partintoinputequationsforR-Sflipflops.

Chu(6)suggestedthatthedesignlanguagehavetheformofahigh

levellanguagesuchasALGOL(19)?Withsuchaform,thetranslation

techniquesdevelopedforhighlevellanguageswouldbeapplicabletothe

translationofthecomputerdesignlanguage.HislanguageCDL(Computer

DesignLanguage)usedconditionallabelsongroupsofregistertransfer

statementsthatweretobedoneinparallel.Iftheconditionallabel

wastruethestatementsweretobeexecuted,otherwisetheywerenot.

Sincehewasdescribingonlyasynchronouscomputer,eachoftheconditional

labelshadareferencetooneoftheclockphases.Thisprovidedacon-

venientwayofdescribingtheflowofcontrolwithinasynchronousmachine.

Pardo(20)demonstratedhowCDLbyChucouldbeusedformicroprogram

designandverificationbywritingamicroprogramforcoderelocationin

CDL.InteractivedesignandsimulationforalanguagesimilartoCDLwas

donebyCrallandTracy(7)?

Symbolicdimensioningofregistersandmemorieswassuggestedby

MetzcandSeshu(18),byusingaFORTRANtypelanguageasthebasisfor

hardwareindependentsystemdescriptionlanguage.

6

Anexperimenta1languagedescribingthesystemascontainingsubsystems

waspresentedbyPamasandDarringer(22)?Eachofthesubsystemswas

describedeitherstructurally,i?e?theirBooleanequations,orbehaviorally,

i-e.asanALGOLprogram(21).

DuleyandDietmeyer(8,9)informallyproposedalanguageforasystem

offiniteautomataeachhavingprivatefacilities(registers,memories,

etc.)andsharingpublicfacilities.Intheirdescriptivelanguageto

specifytheseinterconnectedautonomousunits,theydescribedtheflow

ofcontrolwithineachunitasbeingcomposedofcompatiblesetsof

operationsthatwouldbeexecutedsimultaneouslywhentheunitwasin

thatstate.Theythendescribedhowthesequencingthroughthesevarious

stateswasdonebyastatesequencingregisterthatcouldbechangedbya

statementwithinthelanguage.

Twoinforma1languagesareusedtodescribeacomputersystemby

BellandNewell(2)?Theinterconnectionsbetweenprocessor,memories,

andassociatedswitchesarediagramedalongwiththeirgrosshardware

characteristics.Thisformsthesystemlanguage.Eachindividualpro-

cessoristhendescribedinaregistertransferlanguage.

Stabler(28)usedaregistertransferlanguagetodefinethepossible

microactionsforamicroprogrammedcomputer.Thenheprovidedpossible

transformationsonthemicroprogramswhichkeptthesystem1sbehaviorthe

same.Usingthesetransformationsthemicroprogrammer(i?e?thecomputer

designer)canreducethenumberofstepsinthemicroprogrambyparallel-

ingmutuallyexclusivemicroactions.

Thedescriptionandsimulationforonlystoredprogramcomputerswas

donebyPump1in(25)andZucker(29).Simulationofflipflopsand

7

logicelenientswasdescribedbyMcClure(16)andHays(13)?McKay(17)

suggestedbuildingaspecialpurposecomputertodothissimulation.

Parnas(21)suggestedextendingALGOLtosimulatethef,blackbox"picture

ofasystem.

Potashetal.(23)translatedhisdesigndescriptionintoapseudo

machinelanguagethatwhenexecutedonhispseudomachinewouldsimulate

themachinedescribed.WhereasPumplin(25)translatedthedesignlanguage

intoPL/1statementswhichwhencompiledwouldactasthesimulator.

8

CHAPTERIII.PROGRAMMINGSYSTEM

Theprogrammingsystempresentedhereconsistsoftwoparts?

Thefirstpartisalanguagetosymbolicallydescribetheconstructionof

multiprocessorcomputersystems.Thislanguageisdescribedinformally

inChapteriv.

Thesecondprimarypartisthesimulationofthesymbolicdesign

beingconsidered.Thisalsorequiresalanguagetodescribetheinitial

conditionsoftheprocessorsandwhenthesimulationistobeterminated.

ThislanguageisdescribedinformallyinChapterV.

Theimplementationdetailsofdescribingtheimplementationofthese

translators,thesimulationoftheresultingtargetcodeandtheirre-

strictionsarediscussedinChapterVITI.

Theexamplesofthedescriptionandsimulationofprocessorsare

giveninChapterVIandVII.ChapterVIshowsthedescriptionand

simulationofasingleprocessorwhileChapterVildescribesamulti-

processorsystemanditsassociatedsimulation.

Oneofthedesirablequalitiesinalanguagetodescribethecon-

structionofamultiprocessorsystemisthatthesyntaxofthelanguage

bedescribedformally.Inorderforthistooccur,ametalanguagemust

beadopted.Themetalanguage,orratherthelanguagetodescribeanother

language,usedherewasdevelopedbyBrookerandMorris(4).Itisa

modificationandextensionofthemetalanguageBackus-Naurusedtodes-

cribeALGOL(19).

Thismetalanguagecanbestbeexplainedbyillustratingsomeofthe

basicprimitiveswithinthelanguagecurrentlytobedescribed,i.e.the

9

]anguagetodescribemultiprocessors(MPS).Thefollowingexampleis

usedl<>illustrateasimpledeflnitionusingthismetalanguage:

DIGITrOfIfp|?2?||?4<|IIg.|.7fj?811

Theleftmostitemineachdefinition,inthiscaseDIGIT,indicatesthe

nameofthesyntacticclassthatisbeingdefined*Thecharacters11::=n

foilowingthisnameareusedtoseparatethenameoftheclassbeingde-

finedanditsdefinition.Thesecharacterscanbeliterallyread

asnisdefinedtobe'LCharactersbelongingtothelanguagebeingdefined

areenclosedinquotes(').Ifthecharacterquote(')istobeusedin

thelanguagebeingdefined,thentwoadjacentquotes(1*)mustbeusedto

representthesinglequote.Themetacharacterisusedtoindicate

alternatesandcanliterallybereadasMorn.Thisstatementcannowbe

readasthe°syntacticclassDIGIT""isdefinedtobe"thecharactern0n?

"or"thecharacter11ln,"or"thecharacter"2",etc.

Thenextexampleillustratesanothersymbolusedinthemetalanguage,

thedollarsign($)?Thedollarsignisusedtoindicatezeroormore

occurrencesofthesyntacticclassorgroupfollowingitsuse.Forexample

thefollowingdefinitionofintegerusesthissymbol:

INTEGER::=DIGIT$DIGIT

Inthisexamplethe,,syntacticclassINTEGER11nisdefinedtobe"one

occurranceofthe