prises inTurkey. Hehasalso worked asaUNIDOexpert, conducting var- niques, tobepublished, inTurkish, bytheInformation Processing Society iousprofessional seminars. Hiscurrent research interests areindatabaseofTurkey. systems, distributed systems, database computers, CAD/CAM,andAland Dr.OzsuisamemberoftheIEEEComputer Society, theAssociation databases. Hehasanupcoming book, Project Planning andControl Tech-forComputing Machinery, andSigma Xi. Proving Liveness andTermination ofSystolic Arrays Using…
Hui-Senglee · 1985
We model asystolic array asanetwork of, mostly identical, We modelasystolic arrayasanetwork ofcommunicat- communicating finite state machines that exchange messages over one-ingfinite state machines thatexchange messages overer- to-one, unbounded, FIFOchannels. Eachmachine hasacyclic behav-ror-free, one-to-one, unbounded, FIFO channels. Each ior; ineachcycle, amachine first receives onemessage fromeachofitsmachinehasa cyclic behavior: ineachcycle, a machine input channels, thensends onemessage toeachofits output channels. Ifinacycle amachine doesnothaveanydatamessage tosendtoonereceives onemessageviaeachofitsinput channels and ofits output channels, itsends anull message instead; thus, machines sendsonemessageviaeachofitsoutputchannels. Ifin exchange twotypes ofmessages, dataandnull. Wecharacterize thesomecyclea machinedoesnothavea datamessageto liveness andtermination properties forsuchnetworks, anddiscuss two sendviaan output channel, itsendsa nullmessagein- algorithms thatcanbeusedtodecide theseproperties foranygiven network. Weapply these algorithms toestablish theliveness andter-steadThusmachinesexchangetwotypesofmessages, mination properties offoursystolic array examples. These examples namely dataandnull. Becauseofthiscyclic behavior and include alinear matrix-vector multiplier, alinear priority queue, and thefactthatmachines exchange onlytwotypesofmes- asearch tree. sages, thecommunicating finite state machines inthis pa-