APRIL.XGP[BIB,CSR] - www.SailDart.org

perm filename APRIL.XGP[BIB,CSR] blob sn#413879 filedate 1979-01-30 generic text, type T, neo UTF8
/LMAR=0/XLINE=3/FONT#0=NONM/FONT#1=BAXM30/FONT#2=MATH30/FONT#3=FIX25/FONT#4=GRKL30
␈↓ ↓N␈↓α␈↓ W1


␈↓ ↓N␈↓␈↓ ↓]MOST RECENT CS REPORTS - APRIL 1979         ␈↓ π∞␈↓recent␈α,synthesis␈α,of␈α,computer␈α,and
                                            ␈↓ π∞␈↓communications technology.
␈↓ ↓N␈↓    Listed␈α∞below␈α∞are␈α
abstracts␈α∞of␈α∞the␈α
most
␈↓ ↓N␈↓recent␈α∂reports␈α∞published␈α∂by␈α∂the␈α∞Computer         ␈↓ π∞␈↓    A␈α∨conceptual␈α∨framework␈α∨called␈α∨the
␈↓ ↓N␈↓Science Department of Stanford University.  ␈↓ π∞␈↓␈↓↓Contract␈α∨Net␈↓␈α∨framework␈α∨that␈α≡specifies
                                            ␈↓ π∞␈↓communications,␈α≤control,␈α≤and␈α≤knowledge
␈↓ ↓N␈↓    TO␈α REQUEST␈α REPORTS:␈α  Check␈α the              ␈↓ π∞␈↓organization␈α_has␈α↔been␈α_developed.␈α↔ Task
␈↓ ↓N␈↓appropriate␈α⊂places␈α⊂on␈α⊂the␈α⊂enclosed␈α⊂order         ␈↓ π∞␈↓distribution␈α↔is␈α⊗viewed␈α↔as␈α↔an␈α⊗interactive
␈↓ ↓N␈↓form,␈αand␈αreturn␈αthe␈αentire␈αorder␈αform␈α
page        ␈↓ π∞␈↓process,␈α∞a␈α∞␈↓↓discussion␈↓␈α∞carred␈α∞on␈α∞between␈α
a
␈↓ ↓N␈↓(including␈α∞mailing␈α∞label)␈α∞by␈α∞April␈α∞27,␈α
1979.      ␈↓ π∞␈↓node␈α∩with␈α⊃a␈α∩task␈α⊃to␈α∩be␈α⊃executed␈α∩and␈α⊃a
␈↓ ↓N␈↓In␈α∞many␈α∞cases␈α∞we␈α∞can␈α∞print␈α∞only␈α∞a␈α∞limited           ␈↓ π∞␈↓group␈α≠of␈α~nodes␈α≠that␈α~may␈α≠be␈α≠able␈α~to
␈↓ ↓N␈↓number␈α⊗of␈α∃copies,␈α⊗and␈α∃requests␈α⊗will␈α∃be            ␈↓ π∞␈↓execute␈αthe␈αtask.␈α This␈αis␈αthe␈αorigin␈αof␈αthe
␈↓ ↓N␈↓filled␈α
on␈α
a␈α
first␈α
come,␈α
first␈α
serve␈α
basis.␈α If      ␈↓ π∞␈↓contract␈α∂metaphor␈α∞for␈α∂control,␈α∂where␈α∞task
␈↓ ↓N␈↓the␈α∞code␈α∞(FREE)␈α∞is␈α∞printed␈α∞on␈α∞your␈α
mailing         ␈↓ π∞␈↓distribution␈α.corresponds␈α.to␈α-contract
␈↓ ↓N␈↓label,␈αyou␈α
will␈αnot␈α
be␈αcharged␈αfor␈α
hardcopy.       ␈↓ π∞␈↓negotiation.
␈↓ ↓N␈↓This␈α_exemption␈α↔from␈α_payment␈α_is␈α↔limited
␈↓ ↓N␈↓primarily␈α⊗to␈α⊗libraries.␈α⊗ (The␈α⊗costs␈α∃shown        ␈↓ π∞␈↓    The␈α
types␈α
of␈αknowledge␈α
used␈α
in␈α
such␈αa
␈↓ ↓N␈↓include␈αall␈αapplicable␈αsales␈α
taxes.␈α PLEASE      ␈↓ π∞␈↓problem␈α~solver␈α→are␈α~discussed,␈α→together
␈↓ ↓N␈↓SEND␈αNO␈αMONEY␈αNOW,␈αWAIT␈αUNTIL␈αYOU␈αGET              ␈↓ π∞␈↓with␈α~the␈α~ways␈α~that␈α~the␈α≠knowledge␈α~is
␈↓ ↓N␈↓AN INVOICE.)                                ␈↓ π∞␈↓indexed␈α with␈α an␈α individual␈α node␈α and
                                            ␈↓ π∞␈↓distributed␈α∂among␈α∞the␈α∂collection␈α∂of␈α∞nodes.
␈↓ ↓N␈↓    ALTERNATIVELY:␈α2 Copies␈α2of␈α2most             ␈↓ π∞␈↓The␈α
use␈α
of␈α
two␈α
primary␈α
types␈αof␈α
knowledge
␈↓ ↓N␈↓Stanford␈α⊂CS␈α⊂Reports␈α⊂may␈α⊂be␈α⊃obtained␈α⊂by            ␈↓ π∞␈↓(referred␈α,to␈α,as␈α-␈↓↓Task-Centered␈↓␈α,and
␈↓ ↓N␈↓writing␈α (about␈α 2␈α months␈α!after␈α MOST               ␈↓ π∞␈↓␈↓↓Knowledge-Source Centered␈↓) is shown.
␈↓ ↓N␈↓RECENT␈α⊃CS␈α⊃REPORTS␈α⊃listing)␈α⊃to␈α⊂NATIONAL
␈↓ ↓N␈↓TECHNICAL␈α_INFORMATION␈α→SERVICE,␈α_5285            ␈↓ π∞␈↓    We␈α∃illustrate␈α∀the␈α∃kinds␈α∃of␈α∀information
␈↓ ↓N␈↓Port␈α$Royal␈α$Road,␈α%Springfield,␈α$Virginia          ␈↓ π∞␈↓that␈αmust␈αbe␈αpassed␈αbetween␈αnodes␈αin␈α
the
␈↓ ↓N␈↓22161.␈α) Stanford␈α)Ph.D.␈α)theses␈α)are               ␈↓ π∞␈↓distributed␈α
processor␈α
in␈α
order␈α
to␈α∞carry␈α
out
␈↓ ↓N␈↓available␈α≥from␈α≥UNIVERSITY␈α≤MICROFILMS,          ␈↓ π∞␈↓task␈α∃and␈α∃data␈α∃distribution.␈α∃ We␈α∃suggest
␈↓ ↓N␈↓300␈α∞North␈α∞Zeeb␈α
Road,␈α∞Ann␈α∞Arbor,␈α
Michigan          ␈↓ π∞␈↓that␈α≡a␈α≥common␈α≡internode␈α≡language␈α≥is
␈↓ ↓N␈↓48106.                                      ␈↓ π∞␈↓required␈α'and␈α&that␈α'the␈α&task-specific
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓␈↓↓expertise␈↓␈α
required␈αby␈α
a␈αprocessor␈α
node␈αcan
                                            ␈↓ π∞␈↓be␈α≥obtained␈α≡by␈α≥internode␈α≡transfer␈α≥of
␈↓ ↓N␈↓STAN-CS-78-700                              ␈↓ π∞␈↓procedures and data.
␈↓ ↓N␈↓    A␈αFRAMEWORK␈αFOR␈αPROBLEM␈αSOLVING␈α
IN
␈↓ ↓N␈↓A DISTRIBUTED PROCESSING ENVIRONMENT        ␈↓ π∞␈↓    The␈α∞use␈α∞of␈α∞the␈α∞contract␈α∞net␈α∞framework
                                            ␈↓ π∞␈↓is␈α≤demonstrated␈α≤with␈α≥two␈α≤implemented
␈↓ ↓N␈↓Author:  Reid Garfield Smith␈↓ ¬<(Thesis)        ␈↓ π∞␈↓examples:␈α
 search␈α
in␈αthe␈α
context␈α
of␈α
the␈αN
                                            ␈↓ π∞␈↓Queens␈αproblem␈αand␈αarea␈αsurveillance␈αby␈αa
␈↓ ↓N␈↓    Abstract:␈α_ The␈α_concept␈α_of␈α↔␈↓↓Distributed       ␈↓ π∞␈↓Distributed␈αSensing␈α
System.␈α Consideration
␈↓ ↓N␈↓↓Problem␈αSolving␈↓,␈αor␈αthe␈αcooperative␈αsolution     ␈↓ π∞␈↓is␈α∪also␈α∩given␈α∪to␈α∩the␈α∪implementation␈α∪of␈α∩a
␈↓ ↓N␈↓of␈α!problems␈α!by␈α!a␈α"decentralized␈α!and               ␈↓ π∞␈↓number␈α≠of␈α~familiar␈α≠Artificial␈α~Intelligence
␈↓ ↓N␈↓loosely-coupled␈α⊗collection␈α⊗of␈α⊗knowledge-       ␈↓ π∞␈↓problem solvers.
␈↓ ↓N␈↓sources␈α→that␈α→operates␈α→in␈α~a␈α→distributed
␈↓ ↓N␈↓processor␈αarchitecture␈αis␈αpresented.␈α Such      ␈↓ π∞␈↓    Features␈αof␈αthe␈αframework␈αapplicable␈αto
␈↓ ↓N␈↓architectures␈α∨offer␈α∨high-speed␈α∨reliable        ␈↓ π∞␈↓problem␈α⊂solving␈α∂in␈α⊂general␈α⊂are␈α∂abstracted
␈↓ ↓N␈↓computation␈α≥at␈α≡low␈α≥cost␈α≥and␈α≡are␈α≥an                ␈↓ π∞␈↓from␈α∂the␈α⊂results␈α∂of␈α∂this␈α⊂preliminary␈α∂study.
␈↓ ↓N␈↓effective␈α≠way␈α≤to␈α≠utilize␈α≠the␈α≤new␈α≠LSI              ␈↓ π∞␈↓Comparisons␈α≤with␈α≥PLANNER,␈α≤HEARSAY-II,
␈↓ ↓N␈↓processors␈α∩and␈α∩the␈α∩developments␈α∪of␈α∩the           ␈↓ π∞␈↓and␈α∪PUP6␈α∪are␈α∪used␈α∪to␈α∪demonstrate␈α∩that
␈↓ ↓N␈↓α␈↓ V2


␈↓ ↓N␈↓␈↓↓negotiation␈↓,␈α&the␈α&two-way␈α&transfer␈α&of            ␈↓ π∞␈↓main␈α∞function␈α∞of␈α∞most␈α∞debugging␈α∞tools␈α
and
␈↓ ↓N␈↓information␈α∞combined␈α
with␈α∞mutual␈α
selection      ␈↓ π∞␈↓techniques.␈α Concluding␈αthis␈αfirst␈αpart␈αis␈αan
␈↓ ↓N␈↓prior␈α⊂to␈α⊂invocation,␈α⊂is␈α⊂a␈α⊂natural␈α∂extension       ␈↓ π∞␈↓analysis␈α#of␈α#the␈α$particular␈α#difficulties
␈↓ ↓N␈↓to␈α⊂the␈α⊂control␈α⊂mechanisms␈α⊂used␈α⊂in␈α∂earlier         ␈↓ π∞␈↓involved␈α≤in␈α≠monitoring␈α≤the␈α≤behavior␈α≠of
␈↓ ↓N␈↓problem-solving systems.                    ␈↓ π∞␈↓programs in large and complex AI systems.

␈↓ ↓N␈↓No. of pages:  150                          ␈↓ π∞␈↓    The␈α⊂second␈α⊂half␈α⊂presents␈α⊂an␈α⊂approach
␈↓ ↓N␈↓Cost:  $ 5.90                               ␈↓ π∞␈↓to␈α∀the␈α∪design␈α∀of␈α∪monitoring␈α∀facilities␈α∪for
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓complex␈α⊃systems.␈α⊃ The␈α⊃need␈α∩for␈α⊃system-
                                            ␈↓ π∞␈↓level␈α∞tools␈α∞similar␈α∞to␈α∞the␈α∂ones␈α∞traditionally
␈↓ ↓N␈↓STAN-CS-79-701                              ␈↓ π∞␈↓available␈α~is␈α→indicated.␈α~ A␈α~new␈α→concept
␈↓ ↓N␈↓    MONITORING␈α≤SYSTEM␈α≠BEHAVIOR␈α≤IN␈α≠A             ␈↓ π∞␈↓called␈α?␈α∞"meta-monitoring"␈α?␈α
replaces
␈↓ ↓N␈↓COMPLEX COMPUTATIONAL ENVIRONMENT           ␈↓ π∞␈↓traditional␈αdumps␈α
and␈αtraces␈αwith␈α
selective
                                            ␈↓ π∞␈↓reporting␈α→of␈α→high-level␈α~information␈α→␈↓↓about␈↓
␈↓ ↓N␈↓Author:  Mitch L Model␈↓ ¬<(Thesis)              ␈↓ π∞␈↓computations.␈α! The␈α importance␈α!of␈α the
                                            ␈↓ π∞␈↓visually-oriented␈αanalogical␈αpresentation␈αof
␈↓ ↓N␈↓    Abstract:␈α?␈απ Complex␈α?␈απprogramming            ␈↓ π∞␈↓high-level␈αinformation␈αand␈α
the␈αneed␈αto␈α
take
␈↓ ↓N␈↓environments␈α∪such␈α∪as␈α∪the␈α∩representation         ␈↓ π∞␈↓into␈α∩account␈α∩differences␈α∩between␈α⊃states
␈↓ ↓N␈↓systems␈α>constructed␈α?in␈α>Artificial              ␈↓ π∞␈↓and␈α_active␈α_processes␈α_are␈α_stressed.␈α_ A
␈↓ ↓N␈↓Intelligence␈αresearch␈αpresent␈αnew␈αkinds␈αof       ␈↓ π∞␈↓generalized␈α5method␈α5for␈α5generating
␈↓ ↓N␈↓difficulties␈α"for␈α"their␈α"environment,␈α!the         ␈↓ π∞␈↓descriptions␈α-of␈α-system␈α.activity␈α-is
␈↓ ↓N␈↓traditional␈α∪tools␈α∪and␈α∪techniques␈α∩available      ␈↓ π∞␈↓developed.␈α⊗ This␈α⊗method␈α⊗is␈α⊗based␈α⊗on␈α⊗a
␈↓ ↓N␈↓for␈α∂this␈α∂task␈α∞are␈α∂inadequate.␈α∂ Not␈α∂only␈α∞do         ␈↓ π∞␈↓theoretical␈α;schematization␈α;of␈α:the
␈↓ ↓N␈↓traditional␈αtools␈αaddress␈αstate␈αand␈α
process      ␈↓ π∞␈↓fundamental␈α∩structures␈α⊃and␈α∩operations␈α⊃of
␈↓ ↓N␈↓elements␈α
at␈αtoo␈α
low␈αa␈α
conceptual␈αlevel,␈α
but        ␈↓ π∞␈↓computational␈α%systems␈α$and␈α%is␈α$easily
␈↓ ↓N␈↓an␈α∀Artificial␈α∀Intelligence␈α∃system␈α∀typically     ␈↓ π∞␈↓instantiated␈α⊃for␈α⊃any␈α⊃particular␈α∩AI␈α⊃system.
␈↓ ↓N␈↓imposes␈α(its␈α(own␈α(data␈α(and␈α'control                 ␈↓ π∞␈↓Some␈α≥specific␈α≥display-based␈α≥monitoring
␈↓ ↓N␈↓structures␈α$on␈α$top␈α$of␈α$those␈α%of␈α$its                 ␈↓ π∞␈↓tools␈α/and␈α/techniques␈α0which␈α/were
␈↓ ↓N␈↓implementation␈α⊃language,␈α∩thereby␈α⊃evading       ␈↓ π∞␈↓implemented␈α∪for␈α∪this␈α∪work␈α∪are␈α∪exhibited.
␈↓ ↓N␈↓the␈α∨reach␈α∨of␈α traditional␈α∨program-level          ␈↓ π∞␈↓Several␈α≠of␈α≠the␈α≠experimental␈α~monitoring
␈↓ ↓N␈↓debugging␈α∂tools.␈α∂ This␈α∂work␈α∂is␈α∂directed␈α∂at        ␈↓ π∞␈↓facilities␈α%which␈α%were␈α%constructed␈α%in
␈↓ ↓N␈↓the␈α∂development␈α∞of␈α∂appropriate␈α∞monitoring       ␈↓ π∞␈↓accordance␈α≠with␈α≠the␈α≠principles␈α≠of␈α~the
␈↓ ↓N␈↓tools␈α∀for␈α∀complex␈α∀systems,␈α∀in␈α∀particular,        ␈↓ π∞␈↓proposed␈αapproach␈αare␈αdescribed␈αand␈α
their
␈↓ ↓N␈↓the␈α→representation␈α→systems␈α→of␈α_Artificial        ␈↓ π∞␈↓application␈αto␈α
existing␈αArtificial␈α
Intelligence
␈↓ ↓N␈↓Intelligence research.                      ␈↓ π∞␈↓Systems␈α⊗illustrated.␈α↔ While␈α⊗much␈α↔of␈α⊗the
                                            ␈↓ π∞␈↓research␈α
was␈α∞performed␈α
in␈α
the␈α∞context␈α
of
␈↓ ↓N␈↓    The␈α∞first␈α∞half␈α∞of␈α∞this␈α∞work␈α∞provides␈α
the       ␈↓ π∞␈↓the␈αKRL-1␈α
system␈αdeveloped␈α
at␈αXerox␈α
Palo
␈↓ ↓N␈↓foundation␈α↔for␈α↔the␈α↔design␈α↔approach␈α⊗put           ␈↓ π∞␈↓Alto␈α+Research␈α+Center,␈α+the␈α+general
␈↓ ↓N␈↓forth␈α→and␈α_demonstrated␈α→in␈α→the␈α_second.            ␈↓ π∞␈↓applicability␈α∂of␈α∂the␈α∂theory␈α∂and␈α∂techniques
␈↓ ↓N␈↓Certain␈α≤facts␈α≤concerning␈α≤limitations␈α≤on         ␈↓ π∞␈↓of␈α∪the␈α∪present␈α∩work␈α∪is␈α∪demonstrated␈α∩by
␈↓ ↓N␈↓human␈α%information␈α&processing␈α%abilities         ␈↓ π∞␈↓one␈α∃of␈α∃thes␈α⊗facilities,␈α∃which␈α∃acts␈α⊗as␈α∃a
␈↓ ↓N␈↓which␈α∂formed␈α∂the␈α∂background␈α∂for␈α⊂much␈α∂of           ␈↓ π∞␈↓monitor␈α→for␈α→MYCIN,␈α→a␈α→medical␈α→diagnosis
␈↓ ↓N␈↓the␈α⊃research␈α⊃are␈α⊃introduced.␈α∩ The␈α⊃nature         ␈↓ π∞␈↓system␈α∪developed␈α∪at␈α∪Stanford␈α∩University
␈↓ ↓N␈↓of␈α∂computer␈α∂programs␈α∞is␈α∂discussed,␈α∂and␈α∞a          ␈↓ π∞␈↓that␈α∪embodies␈α∀knowledge␈α∪in␈α∪the␈α∀form␈α∪of
␈↓ ↓N␈↓concept␈α
of␈α␈↓↓computational␈α
behavior␈↓␈αis␈α
defined.    ␈↓ π∞␈↓production rules.
␈↓ ↓N␈↓A␈α
thematic␈α∞survey␈α
of␈α∞traditional␈α
debugging
␈↓ ↓N␈↓tools␈α∞is␈α
presented,␈α∞followed␈α
by␈α∞a␈α
summary         ␈↓ π∞␈↓No. of pages:  189
␈↓ ↓N␈↓of␈α∀recent␈α∀work.␈α∀ Observation␈α∀of␈α∀program          ␈↓ π∞␈↓Available in microfiche only.
␈↓ ↓N␈↓behavior␈α∩(␈↓↓monitoring␈↓)␈α∪is␈α∩shown␈α∩to␈α∪be␈α∩the          ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓α␈↓ U3


␈↓ ↓N␈↓STAN-CS-78-702                              ␈↓ π∞␈↓Cost:  $ 2.40
␈↓ ↓N␈↓    AN␈α?␈α∪O(n␈↓α*␈↓Ilog␈↓#
2␈↓#I)␈α?␈α∩MAXIMUM-FLOW               ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓ALGORITHM
                                            ␈↓ π∞␈↓STAN-CS-79-704
␈↓ ↓N␈↓Author:  Yossi Shiloach                     ␈↓ π∞␈↓    A␈α∞SURVEY␈α∂OF␈α∞THE␈α∞STATE␈α∂OF␈α∞SOFTWARE
                                            ␈↓ π∞␈↓FOR PARTIAL DIFFERENTIAL EQUATIONS
␈↓ ↓N␈↓    Abstract:␈α∂ In␈α∂this␈α∂paper␈α∂we␈α⊂present␈α∂an
␈↓ ↓N␈↓algorithm␈α_to␈α_find␈α_a␈α_maximum␈α_flow␈α_in␈α↔a              ␈↓ π∞␈↓Author:  Roland A. Sweet
␈↓ ↓N␈↓network␈αwhich␈αhas␈αn␈αvertices␈αand␈αm␈αedges
␈↓ ↓N␈↓in␈α∞time␈α∞of␈α∞O(n␈↓α*␈↓Ilog␈↓#
2␈↓#I),␈α∞where␈α∞I␈α∞=␈α∞m+n␈α∞,␈α
the          ␈↓ π∞␈↓    Abstract:␈α This␈αpaper␈αsurveys␈α
the␈αstate
␈↓ ↓N␈↓input␈α∞size␈α∂(up␈α∞to␈α∂a␈α∞constant␈α∂factor).␈α∞ This        ␈↓ π∞␈↓of␈α∨general␈α∨purpose␈α∨software␈α∨for␈α∨the
␈↓ ↓N␈↓result␈α⊂improves␈α⊂the␈α⊂previous␈α⊂upper␈α⊂bound         ␈↓ π∞␈↓solution␈αof␈α
partial␈αdifferential␈α
equations.␈α A
␈↓ ↓N␈↓of␈αZ.␈αGalil␈α[G]␈αwhich␈αhas␈αan␈αO(I␈↓#
7/3␈↓#)␈αworst-         ␈↓ π∞␈↓discussion␈α∞of␈α
the␈α∞purported␈α∞capabilities␈α
of
␈↓ ↓N␈↓case performance.                           ␈↓ π∞␈↓twenty-one␈α~programs␈α→is␈α~presented.␈α→ No
                                            ␈↓ π∞␈↓testing of the routines is performed.
␈↓ ↓N␈↓    The␈α6algorithm␈α6is␈α6basically␈α5an
␈↓ ↓N␈↓implementation␈α_of␈α_Dinic's␈α_algorithm␈α_in␈α_a         ␈↓ π∞␈↓No. of pages:  31
␈↓ ↓N␈↓data-structure␈α⊂which␈α⊂enables␈α⊂us␈α⊃to␈α⊂store         ␈↓ π∞␈↓Cost:  $ 2.60
␈↓ ↓N␈↓sections␈α∞of␈α∂paths␈α∞that␈α∞have␈α∂already␈α∞been          ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓traversed␈α∃and␈α∃also␈α∃cut␈α∃and␈α∃paste␈α∀such
␈↓ ↓N␈↓sections,␈αfind␈αtheir␈αbottlenecks␈αand␈α
update      ␈↓ π∞␈↓STAN-CS-79-705
␈↓ ↓N␈↓the␈α∩residual␈α∩capacities␈α∩of␈α∩their␈α∩edges␈α⊃in         ␈↓ π∞␈↓    GENERALIZED␈α↔VORONOI␈α↔DIAGRAMS␈α⊗AND
␈↓ ↓N␈↓logarithmic time.                           ␈↓ π∞␈↓GEOMETRIC SEARCHING

␈↓ ↓N␈↓No. of pages:  33                           ␈↓ π∞␈↓Author:  Robert Lewis (Scot) Drysdale, III␈↓ n
␈↓ ↓N␈↓Cost:  $ 2.65                               ␈↓ π∞␈↓ 
|␈↓(Thesis) 
␈↓ ↓N␈↓--␈↓ ε∩--
                                            ␈↓ π∞␈↓    Abstract:␈α! A␈α!Voronoi␈α!diagram␈α"is␈α!a
␈↓ ↓N␈↓STAN-CS-79-703                              ␈↓ π∞␈↓partitioning␈α∩of␈α∩the␈α∩plane␈α∩into␈α∩n␈α⊃polygonal
␈↓ ↓N␈↓    A␈α≠POLYNOMIAL␈α~TIME␈α≠ALGORITHM␈α~FOR             ␈↓ π∞␈↓regions,␈α⊃one␈α⊃region␈α⊃associated␈α⊃with␈α⊃each
␈↓ ↓N␈↓SOLVING␈αSYSTEMS␈αOF␈αLINEAR␈αINEQUALITIES          ␈↓ π∞␈↓of␈α⊂n␈α⊃given␈α⊂points.␈α⊂ The␈α⊃region␈α⊂associated
␈↓ ↓N␈↓WITH TWO VARIABLES PER INEQUALITY           ␈↓ π∞␈↓with␈α⊃point␈α⊃p␈α⊃consists␈α⊃of␈α⊃all␈α⊃points␈α∩in␈α⊃the
                                            ␈↓ π∞␈↓plane␈α
closer␈α
to␈α
p␈α
than␈α
to␈α
any␈α
of␈α
the␈α
other
␈↓ ↓N␈↓Author:  Bengt Aspval & Yossi Shiloach      ␈↓ π∞␈↓n-1␈α+given␈α+points.␈α+ Michael␈α+Shamos
                                            ␈↓ π∞␈↓developed␈α⊃a␈α⊃divide-and-conquer␈α⊂algorithm
␈↓ ↓N␈↓    Abstract:␈α∃ We␈α∃present␈α∃a␈α∃constructive        ␈↓ π∞␈↓which␈α∂computes␈α∂the␈α∂diagram␈α∂in␈α∂O(n␈α∂log␈α∂n)
␈↓ ↓N␈↓algorithm␈α~for␈α~solving␈α~systems␈α~of␈α→linear          ␈↓ π∞␈↓time.␈α_ He␈α_showed␈α_that␈α_the␈α_all-nearest-
␈↓ ↓N␈↓inequalities␈α(LI)␈αwith␈αat␈αmost␈αtwo␈αvariables      ␈↓ π∞␈↓neighbors␈α→problem,␈α→and␈α→other␈α_seemingly
␈↓ ↓N␈↓per␈α∞inequality.␈α∞ The␈α∞algorithm␈α∂is␈α∞polynomial     ␈↓ π∞␈↓unrelated␈α∃problems␈α∀can␈α∃all␈α∀be␈α∃solved␈α∀in
␈↓ ↓N␈↓in␈α
the␈α
size␈α
of␈α
the␈α
input.␈α
 The␈α
LI␈α∞problem␈α
is         ␈↓ π∞␈↓time␈α∂which␈α∂is␈α∞optimal␈α∂to␈α∂within␈α∂a␈α∞constant
␈↓ ↓N␈↓of␈αimportance␈αin␈αcomplexity␈αtheory␈αsince␈αit       ␈↓ π∞␈↓factor␈α≥by␈α≡first␈α≥computing␈α≡the␈α≥Voronoi
␈↓ ↓N␈↓is␈α≠polynomial␈α≤time␈α≠equivalent␈α≤to␈α≠linear          ␈↓ π∞␈↓diagram.␈α∞ These␈α∞kinds␈α∞of␈α∞problems␈α∞arise␈α
in
␈↓ ↓N␈↓programming.␈α The␈αsubclass␈αof␈αLI␈αtreated␈αin       ␈↓ π∞␈↓wire␈α≠layout,␈α≠facilities␈α≤location,␈α≠cutting-
␈↓ ↓N␈↓this␈α⊂paper␈α⊃is␈α⊂also␈α⊃of␈α⊂practical␈α⊃interest␈α⊂in        ␈↓ π∞␈↓stock␈α!problems,␈α"geometric␈α!optimization
␈↓ ↓N␈↓mechanical␈α∃verification␈α∃systems,␈α∃and␈α∀we         ␈↓ π∞␈↓problems,␈α5clustering␈α5problems,␈α5and
␈↓ ↓N␈↓believe␈α⊃that␈α⊃the␈α⊂ideas␈α⊃presented␈α⊃can␈α⊂be           ␈↓ π∞␈↓contouring problems.
␈↓ ↓N␈↓extended␈αto␈αthe␈αgeneral␈α
linear␈αinequalities
␈↓ ↓N␈↓problem.                                    ␈↓ π∞␈↓    A␈α⊂natural␈α∂question␈α⊂is,␈α∂"Can␈α⊂the␈α∂Voronoi
                                            ␈↓ π∞␈↓diagram␈α∃be␈α∃generalized␈α∃to␈α∃other␈α∀shapes
␈↓ ↓N␈↓No. of pages:  25
␈↓ ↓N␈↓α␈↓ W4


␈↓ ↓N␈↓and␈α
to␈αother␈α
metrics␈αon␈α
R␈↓#
2␈↓#?"␈α
 Ignoring␈αthe         ␈↓ π∞␈↓    An␈α⊂O(n␈α⊂c␈↓#
␈↓α␈↓#
\␈↓␈↓#
log␈α∂n␈↓#)-time␈α⊂algorithm␈α⊂may␈α∂be
␈↓ ↓N␈↓200-mile␈α∩limit,␈α⊃the␈α∩territorial␈α⊃waters␈α∩of␈α⊃a       ␈↓ π∞␈↓worse␈α9than␈α:asymptotically␈α9slower
␈↓ ↓N␈↓country␈α⊂are␈α⊂precisely␈α⊂its␈α⊂Voronoi␈α⊂diagram.       ␈↓ π∞␈↓algorithms␈α∂for␈α∞␈↓↓practical␈α∂sized␈↓␈α∂problems.␈α∞ For
␈↓ ↓N␈↓Therefore␈α∃the␈α∀question␈α∃is␈α∀of␈α∃interest␈α∀in          ␈↓ π∞␈↓this␈α∩reason␈α∪this␈α∩paper␈α∪presents␈α∩methods
␈↓ ↓N␈↓map-making.␈α∀ Lee␈α∀and␈α∀Wong␈α∃studied␈α∀the            ␈↓ π∞␈↓for␈α∀efficiently␈α∀implementing␈α∀the␈α∪algorithm
␈↓ ↓N␈↓Voronoi␈α
diagram␈α
for␈α
points␈α
under␈α
the␈αL␈↓#v1␈↓#␈α
and        ␈↓ π∞␈↓and␈α∞includes␈α
a␈α∞complete␈α∞implementation␈α
of
␈↓ ↓N␈↓L␈↓β␈↓#v∞␈↓#␈α⊗␈↓metrics␈α⊗and␈α⊗its␈α⊗applications␈α⊗to␈α∃two-           ␈↓ π∞␈↓the␈α→algorithm␈α→for␈α→line␈α→segments␈α~as␈α→an
␈↓ ↓N␈↓dimensional␈α&memory␈α'storage␈α&systems.            ␈↓ π∞␈↓Appendix.␈α≠ The␈α~results␈α≠of␈α≠these␈α~tests
␈↓ ↓N␈↓Shamos␈α≤posed␈α≤the␈α≤problem␈α≥of␈α≤quickly              ␈↓ π∞␈↓comparing␈α∩running␈α∩times␈α∩for␈α∩the␈α⊃nearest-
␈↓ ↓N␈↓computing␈α∨minimum␈α∨spanning␈α∨trees␈α∨for            ␈↓ π∞␈↓neighbor␈α∀problem␈α∃solved␈α∀directly␈α∃and␈α∀by
␈↓ ↓N␈↓circles␈α&and␈α&line␈α&segments.␈α' A␈α&fast               ␈↓ π∞␈↓using␈αthe␈αVoronoi␈αdiagram␈αfor␈αvarious␈αsized
␈↓ ↓N␈↓procedure␈α$for␈α$computing␈α$the␈α$Voronoi             ␈↓ π∞␈↓data␈α
sets␈α
seem␈α∞to␈α
indicate␈α
that␈α∞there␈α
are
␈↓ ↓N␈↓diagram␈α≠for␈α≤circles␈α≠and␈α≤line␈α≠segments            ␈↓ π∞␈↓applications␈α∞where␈α∂the␈α∞algorithm␈α∂would␈α∞be
␈↓ ↓N␈↓would␈α⊗solve␈α⊗this␈α⊗problem.␈α⊗ Many␈α⊗of␈α⊗the            ␈↓ π∞␈↓valuable.␈α⊂ For␈α∂some␈α⊂types␈α∂of␈α⊂input␈α⊂it␈α∂was
␈↓ ↓N␈↓applications␈αmentioned␈α
above␈αhave␈α
analogs       ␈↓ π∞␈↓faster␈α&to␈α'use␈α&the␈α'Voronoi␈α&diagram
␈↓ ↓N␈↓where␈αthe␈αobjects␈αunder␈αconsideration␈αare        ␈↓ π∞␈↓whenever␈α≠the␈α≠number␈α≠of␈α≤objects␈α≠was
␈↓ ↓N␈↓best␈α~represented␈α→by␈α~geometric␈α→shapes            ␈↓ π∞␈↓greater than 100.
␈↓ ↓N␈↓other␈α≤than␈α≠points␈α≤(e.g.,␈α≤conductors␈α≠or
␈↓ ↓N␈↓components␈αin␈α
wire␈αlayout␈α
problems␈αmay␈α
be         ␈↓ π∞␈↓No. of pages:  196
␈↓ ↓N␈↓rectangles,␈α≡circles,␈α≡or␈α∨line␈α≡segments).         ␈↓ π∞␈↓Available in microfiche only.
␈↓ ↓N␈↓Applications␈α*also␈α)arise␈α*in␈α)computer             ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓graphics.
                                            ␈↓ π∞␈↓STAN-CS-79-706
␈↓ ↓N␈↓    This␈α!paper␈α presents␈α!a␈α divide-and-           ␈↓ π∞␈↓    GRAPH␈α92-ISOMORPHISM␈α:IS␈α9NP-
␈↓ ↓N␈↓conquer␈α≡method␈α≡for␈α≡computing␈α≡Voronoi            ␈↓ π∞␈↓COMPLETE
␈↓ ↓N␈↓diagrams␈α⊃for␈α⊃a␈α⊂wide␈α⊃variety␈α⊃of␈α⊂geometric
␈↓ ↓N␈↓shapes␈α∃(including␈α∃line␈α⊗segments,␈α∃circles,       ␈↓ π∞␈↓Author:  F. Francis Yao
␈↓ ↓N␈↓and␈αpolygons)␈αin␈αthe␈αEuclidean␈αplane␈αin␈αO(n
␈↓ ↓N␈↓c␈↓#
␈↓α␈↓#
\␈↓␈↓#
log␈α⊂n␈↓#)␈α⊂␈↓↓basic␈α⊃steps␈↓,␈α⊂where␈α⊂the␈α⊃␈↓↓basic␈α⊂steps␈↓        ␈↓ π∞␈↓    Abstract:␈α Two␈αgraphs␈αG␈αand␈αG'␈αare␈αsaid
␈↓ ↓N␈↓include␈α~such␈α→operations␈α~as␈α~finding␈α→the           ␈↓ π∞␈↓to␈α∂be␈α∂k-isomorphic␈α∂if␈α∂their␈α∂edge␈α⊂sets␈α∂can
␈↓ ↓N␈↓locus␈α of␈α∨points␈α equidistant␈α from␈α∨two             ␈↓ π∞␈↓be␈α
partitioned␈α
into␈α
E(G)␈α
=␈α
E␈↓#v1␈↓#␈α
␈↓β∪␈↓␈α
E␈↓#v2␈↓#␈α∞␈↓β∪␈↓...␈↓β∪␈↓␈α
E␈↓#vk␈↓#
␈↓ ↓N␈↓objects,␈α∞find␈α∂the␈α∞intersection␈α∞of␈α∂two␈α∞such        ␈↓ π∞␈↓and␈αE(G')␈α=␈αE␈↓#
'␈↓#␈αp␈↓#v␈α1␈↓#␈α
␈↓β∪␈↓␈αE␈↓#
'␈↓#␈αp␈↓#v␈α2␈↓#␈α␈↓β∪␈↓...␈↓β∪␈↓␈αE␈↓#
'␈↓#␈αp␈↓#v␈αk␈↓#␈α
such␈αthat
␈↓ ↓N␈↓loci,␈α≤and␈α≤finding␈α≤the␈α≤lines␈α≤of␈α≤support            ␈↓ π∞␈↓as␈α⊃graphs,␈α⊃E␈↓#vi␈↓#␈α⊃and␈α⊃E␈↓#
'␈↓#␈αp␈↓#v␈α⊃i␈↓#␈α⊃are␈α∩isomorphic␈α⊃for
␈↓ ↓N␈↓between␈α#two␈α#objects.␈α# Part␈α#of␈α"this               ␈↓ π∞␈↓1 ␈↓β≤␈↓ i ␈↓β≤␈↓ k␈α∞.␈α∞ In␈α∞this␈α∞note␈α∞we␈α∞show␈α∞that␈α∂it␈α∞is
␈↓ ↓N␈↓algorithm␈α
is␈α
a␈α
procedure␈α
for␈α∞computing␈α
the        ␈↓ π∞␈↓NP-complete␈α
to␈α
decide␈α
whether␈αtwo␈α
graphs
␈↓ ↓N␈↓convex␈α
hull␈α
of␈α
a␈αset␈α
of␈α
n␈α
convex␈αobjects␈α
in          ␈↓ π∞␈↓are 2-isomorphic.
␈↓ ↓N␈↓O(n␈αlog␈αn)␈αbasic␈αsteps,␈αwhich␈αis␈αinteresting
␈↓ ↓N␈↓in␈α∩its␈α∩own␈α∪right.␈α∩ It␈α∩is␈α∩shown␈α∪that␈α∩these           ␈↓ π∞␈↓No. of pages:  12
␈↓ ↓N␈↓methods␈αwork␈αfor␈αa␈αwide␈αvariety␈αof␈α
metrics         ␈↓ π∞␈↓Cost:  $ 2.05
␈↓ ↓N␈↓on␈α R␈↓#
2␈↓#,␈α including␈α the␈α L␈↓#vp␈↓#␈α metrics␈α for               ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓1 < p < ␈↓β∞␈↓.
                                            ␈↓ π∞␈↓STAN-CS-79-707
␈↓ ↓N␈↓    There␈α≤is␈α≤a␈α≤strong␈α≤temptation␈α≠when            ␈↓ π∞␈↓    A␈αPROGRAMMING␈αAND␈αPROBLEM-SOLVING
␈↓ ↓N␈↓working␈α⊂with␈α⊂geometric␈α⊂algorithms␈α⊃to␈α⊂say,        ␈↓ π∞␈↓SEMINAR
␈↓ ↓N␈↓"It's␈α∨obvious!␈α∨ Look␈α∨at␈α∨the␈α≡diagram!"
␈↓ ↓N␈↓Geometric␈α≤intuitions␈α≠are␈α≤vital,␈α≤but␈α≠are          ␈↓ π∞␈↓Authors:  Chris Van Wyk & Donald E. Knuth
␈↓ ↓N␈↓occasionally␈α∞wrong.␈α
 There␈α∞important␈α
facts
␈↓ ↓N␈↓are stated as lemmas and proved.            ␈↓ π∞␈↓    Abstract:␈α∃ This␈α∀report␈α∃contains␈α∀edited
                                            ␈↓ π∞␈↓transcripts␈α≤of␈α≤the␈α≤discussions␈α≥held␈α≤in
␈↓ ↓N␈↓α␈↓ W5


␈↓ ↓N␈↓Stanford's␈α'course␈α'CS␈α(204,␈α'Problem               ␈↓ π∞␈↓    Abstract:␈α
 In␈α∞this␈α
paper␈α
we␈α∞explore␈α
the
␈↓ ↓N␈↓Seminar,␈α∨during␈α∨autumn␈α∨quarter␈α≡1978.            ␈↓ π∞␈↓use␈αof␈α2-3␈αtrees␈αto␈αrepresent␈αsorted␈αlists.
␈↓ ↓N␈↓Since␈α∀the␈α∀topics␈α∀span␈α∀a␈α∀large␈α∀range␈α∀of             ␈↓ π∞␈↓We␈α analyze␈α the␈α worst-case␈α!cost␈α of
␈↓ ↓N␈↓ideas␈α
in␈α
computer␈αscience,␈α
and␈α
since␈αmost         ␈↓ π∞␈↓sequences␈α
of␈α
insertions␈α
and␈α
deletions␈α
in␈α
2-
␈↓ ↓N␈↓of␈α∩the␈α∩important␈α∩research␈α∪paradigms␈α∩and          ␈↓ π∞␈↓3␈α∞trees␈α∞under␈α∞each␈α∞of␈α∞the␈α∞following␈α∞three
␈↓ ↓N␈↓programming␈αparadigms␈αcame␈αup␈α
during␈αthe         ␈↓ π∞␈↓assumptions:␈α& (i)␈α%only␈α&insertions␈α%are
␈↓ ↓N␈↓discussions,␈α!these␈α!notes␈α!may␈α!be␈α of               ␈↓ π∞␈↓performed;␈α0(ii)␈α/only␈α0deletions␈α/are
␈↓ ↓N␈↓interest␈α
to␈α
graduate␈α
students␈α∞of␈α
computer        ␈↓ π∞␈↓performed;␈α∃(iii)␈α∃deletions␈α∃occure␈α∃only␈α∃at
␈↓ ↓N␈↓science␈αat␈αother␈αuniversities,␈αas␈αwell␈αas␈αto       ␈↓ π∞␈↓the␈α∀small␈α∀end␈α∃of␈α∀the␈α∀list␈α∃and␈α∀insertions
␈↓ ↓N␈↓their␈αprofessors␈αand␈αto␈αprofessional␈αpeople      ␈↓ π∞␈↓occur␈α⊂only␈α⊂away␈α⊂from␈α⊂the␈α⊂small␈α⊂end.␈α⊂ Our
␈↓ ↓N␈↓in the "real world."                        ␈↓ π∞␈↓analysis␈α_leads␈α_to␈α_a␈α_data␈α_structure␈α_for
                                            ␈↓ π∞␈↓representing␈α
sorted␈αlists␈α
when␈α
the␈αaccess
␈↓ ↓N␈↓No. of pages:  83                           ␈↓ π∞␈↓pattern␈α⊃exhibits␈α⊂a␈α⊃(perhaps␈α⊂time-varying)
␈↓ ↓N␈↓Cost:  $ 4.05                               ␈↓ π∞␈↓locality␈α∩of␈α∩reference.␈α∩ This␈α∩structure␈α⊃has
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓many␈α1of␈α1the␈α1properties␈α2of␈α1the
                                            ␈↓ π∞␈↓representation␈α/proposed␈α/by␈α.Guibas,
␈↓ ↓N␈↓STAN-CS-79-708                              ␈↓ π∞␈↓McCreight,␈αPlass,␈αand␈αRoberts␈α[4],␈αbut␈αit␈αis
␈↓ ↓N␈↓    AN␈α
ANALYSIS␈α∞OF␈α
A␈α∞MEMORY␈α
ALLOCATION           ␈↓ π∞␈↓substantially␈α∞simpler␈α∂and␈α∞may␈α∂be␈α∞practical
␈↓ ↓N␈↓SCHEME FOR IMPLEMENTING STACKS              ␈↓ π∞␈↓for lists of moderate size.

␈↓ ↓N␈↓Author:  Andrew C. Yao                      ␈↓ π∞␈↓No. of pages:  50
                                            ␈↓ π∞␈↓Cost:  $ 3.10
␈↓ ↓N␈↓    Abstract:␈α∪ Consider␈α∪the␈α∪implementation     ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓of␈α≡two␈α≡stacks␈α≥by␈α≡letting␈α≡them␈α≥grow
␈↓ ↓N␈↓towards␈α⊂each␈α⊃other␈α⊂in␈α⊂a␈α⊃table␈α⊂of␈α⊃size␈α⊂m.
␈↓ ↓N␈↓Suppose␈α∩a␈α⊃random␈α∩sequence␈α∩of␈α⊃␈↓↓insertions␈↓
␈↓ ↓N␈↓and␈α≠␈↓↓deletions␈↓␈α≠are␈α≠executed,␈α≠with␈α~each
␈↓ ↓N␈↓instruction␈α"having␈α"a␈α#fixed␈α"probability
␈↓ ↓N␈↓p (0 < p < 1/2)␈α
to␈α
be␈α
a␈α
deletion.␈α Let␈α
A␈↓#vp␈↓#(m)
␈↓ ↓N␈↓denote␈α⊃the␈α⊃expected␈α⊃value␈α⊃of␈α⊃max{x,y},
␈↓ ↓N␈↓where␈αx␈αand␈αy␈αare␈αthe␈αstack␈αheights␈αwhen
␈↓ ↓N␈↓the␈α_table␈α_first␈α↔becomes␈α_full.␈α_ We␈α↔shall
␈↓ ↓N␈↓prove␈α~that,␈α~as␈α~m ␈↓↓→ ␈↓β∞␈↓,␈α~A␈↓#vp␈↓#(m)␈α~=␈α~m/2␈α→+
␈↓ ↓N␈↓␈↓α\␈↓m/(2␈↓∧p␈↓(1-2p))␈α≤+␈α≤0((log␈α≥m)/␈↓α\␈↓m).␈α≤ This
␈↓ ↓N␈↓gives␈α⊗a␈α⊗solution␈α∃to␈α⊗an␈α⊗open␈α⊗problem␈α∃in
␈↓ ↓N␈↓Knuth␈α∃[␈↓↓The␈α∃Art␈α∃of␈α∃Computer␈α∃Programming␈↓
␈↓ ↓N␈↓Vol. 1, Exercise 2.2.2-13].

␈↓ ↓N␈↓No. of pages:  18
␈↓ ↓N␈↓Cost:  $ 2.20
␈↓ ↓N␈↓--␈↓ ε∩--

␈↓ ↓N␈↓STAN-CS-78-709
␈↓ ↓N␈↓    DESIGN␈α AND␈α ANALYSIS␈α OF␈α A␈α∨DATA
␈↓ ↓N␈↓STRUCTURE␈α~FOR␈α~REPRESENTING␈α~SORTED
␈↓ ↓N␈↓LISTS

␈↓ ↓N␈↓Authors:  Mark R. Brown & Robert E. Tarjan
␈↓ ↓N␈↓α␈↓ W6


␈↓ ↓N␈↓␈↓ ↓{SYSTEMS OPTIMIZATION LABORATORY             ␈↓ π∞␈↓function.␈α⊂ The␈α⊂methods␈α⊂utilize␈α⊂the␈α∂penalty
                                            ␈↓ π∞␈↓and␈α$barrier␈α$functions␈α$only␈α$as␈α$merit
␈↓ ↓N␈↓    The␈α
following␈α
reports␈α
are␈α
available␈α
from     ␈↓ π∞␈↓functions,␈αand␈αdo␈αnot␈αgenerate␈α
iterates␈αby
␈↓ ↓N␈↓the␈α≤Systems␈α≠Optimization␈α≤Lab.␈α≠ Further          ␈↓ π∞␈↓solving␈α"a␈α"sequence␈α#of␈α"ill-conditioned
␈↓ ↓N␈↓information␈α∞on␈α∞them␈α∞can␈α∞be␈α∞obtained␈α
from:         ␈↓ π∞␈↓problems.␈α~ The␈α~search␈α~direction␈α≠is␈α~the
␈↓ ↓N␈↓Gail␈α*L.␈α*Stein,␈α+Systems␈α*Optimization             ␈↓ π∞␈↓solution␈α⊂of␈α⊂a␈α⊂simple,␈α⊂well-posed␈α∂quadratic
␈↓ ↓N␈↓Laboratory,␈α&Department␈α&of␈α%Operations           ␈↓ π∞␈↓program␈α*(QP),␈α)where␈α*the␈α)quadratic
␈↓ ↓N␈↓Research,␈α→Stanford␈α→University,␈α_Stanford,       ␈↓ π∞␈↓objective␈α⊃function␈α∩is␈α⊃an␈α∩approximation␈α⊃to
␈↓ ↓N␈↓California 94305 U.S.A.                     ␈↓ π∞␈↓the␈α∞Lagrangian␈α∂function;␈α∞the␈α∂steplength␈α∞is
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓based␈α≤on␈α≤a␈α≤sufficient␈α≤decrease␈α≥in␈α≤a
                                            ␈↓ π∞␈↓penalty␈α≤or␈α≥barrier␈α≤function,␈α≥to␈α≤ensure
␈↓ ↓N␈↓SOL 78-8                                    ␈↓ π∞␈↓progress toward the solution.
␈↓ ↓N␈↓    FORTRAN␈α∀SUBROUTINES␈α∀TO␈α∃SOLVE␈α∀THE
␈↓ ↓N␈↓LINEAR␈α$LEAST-SQUARES␈α$PROBLEM␈α#AND               ␈↓ π∞␈↓    The␈α↔penalty␈α↔trajectory␈α↔algorithm␈α↔was
␈↓ ↓N␈↓COMPUTE␈α!THE␈α!COMPLETE␈α ORTHOGONAL                ␈↓ π∞␈↓first␈α↔proposed␈α↔by␈α↔Murray␈α↔in␈α↔1969;␈α↔the
␈↓ ↓N␈↓FACTORIZATION                               ␈↓ π∞␈↓barrier␈α⊃trajectory␈α⊃algorithm,␈α⊃which␈α⊂retains
                                            ␈↓ π∞␈↓feasibility␈αthroughout,␈αwas␈αgiven␈αby␈αWright
␈↓ ↓N␈↓Authors:␈α∂ Margaret␈α⊂H.␈α∂Wright␈α∂&␈α⊂Steven␈α∂C.          ␈↓ π∞␈↓in␈α$1976.␈α$ Here␈α$we␈α$give␈α$a␈α$unified
␈↓ ↓N␈↓Glassman                                    ␈↓ π∞␈↓presentation␈α$of␈α$both␈α%algorithms,␈α$and
                                            ␈↓ π∞␈↓indicate␈α_their␈α_relationship␈α_to␈α→other␈α_QP-
␈↓ ↓N␈↓    Abstract:␈α~ This␈α~report␈α≠describes␈α~the        ␈↓ π∞␈↓based␈α7methods.␈α7 Full␈α8details␈α7of
␈↓ ↓N␈↓computational␈α∀procedures␈α∀involved␈α∃in:␈α∀(i)       ␈↓ π∞␈↓implementation␈α↔are␈α⊗included,␈α↔as␈α↔well␈α⊗as
␈↓ ↓N␈↓solution␈α∀of␈α∀linear␈α∀least-squares␈α∀problems       ␈↓ π∞␈↓numerical␈α
results␈α
that␈α
display␈α
the␈α
success
␈↓ ↓N␈↓(including␈α∃systems␈α∃of␈α⊗non-singular,␈α∃orer-       ␈↓ π∞␈↓of the methods on non-trivial problems.
␈↓ ↓N␈↓and␈α
under-determined␈α
linear␈α
equations);␈α
(ii)    ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓formation␈α"of␈α"the␈α"complete␈α"orthogonal
␈↓ ↓N␈↓factorization␈α≠of␈α≠a␈α≠general␈α≤real␈α≠matrix.          ␈↓ π∞␈↓SOL 78-27
␈↓ ↓N␈↓Some␈α∩aspects␈α∪of␈α∩implementation␈α∪and␈α∩the           ␈↓ π∞␈↓    ERROR␈α!PROPAGATION␈α"AND␈α!SOLUTION
␈↓ ↓N␈↓estimation␈α~of␈α→rank␈α~are␈α~discussed.␈α→ Full          ␈↓ π∞␈↓RECONSTRUCTION␈α?␈α3IN␈α?␈α2NESTED
␈↓ ↓N␈↓documentation␈α∀(including␈α∪source␈α∀code)␈α∪is        ␈↓ π∞␈↓DECOMPOSITION
␈↓ ↓N␈↓given␈α!for␈α!a␈α!modular␈α!set␈α"of␈α!Fortran
␈↓ ↓N␈↓subroutines␈α⊂to␈α⊂solve␈α⊂problems␈α⊂(i)␈α⊂and␈α∂(ii),       ␈↓ π∞␈↓Author:  Larry Nazareth
␈↓ ↓N␈↓and several related problems.
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓    Abstract:␈α  We␈α study␈α some␈α!of␈α the
                                            ␈↓ π∞␈↓numerical␈α)properties␈α)of␈α)the␈α)nested
␈↓ ↓N␈↓SOL 78-23                                   ␈↓ π∞␈↓decomposition␈α⊂algorithm␈α∂of␈α⊂Ho␈α⊂and␈α∂Manne.
␈↓ ↓N␈↓    PROJECTED␈α6LAGRANGIAN␈α5METHODS              ␈↓ π∞␈↓In␈α∪particular␈α∪we␈α∪seek␈α∪to␈α∪show␈α∪how␈α∪well
␈↓ ↓N␈↓BASED␈α∂ON␈α∞THE␈α∂TRAJECTORIES␈α∂OF␈α∞PENALTY             ␈↓ π∞␈↓developed␈α+theory␈α*in␈α+the␈α+area␈α*of
␈↓ ↓N␈↓AND BARRIER FUNCTIONS                       ␈↓ π∞␈↓computational␈α⊂linear␈α⊂algebra,␈α⊂due␈α∂primarily
                                            ␈↓ π∞␈↓to␈α⊃J.␈α∩H.␈α⊃ Wilkinson,␈α∩carries␈α⊃over␈α∩to␈α⊃linear
␈↓ ↓N␈↓Authors:␈α↔  Walter␈α⊗Murray␈α↔&␈α↔Margaret␈α⊗H.           ␈↓ π∞␈↓programming␈α⊂and␈α∂yields␈α⊂useful␈α⊂insight␈α∂into
␈↓ ↓N␈↓Wright                                      ␈↓ π∞␈↓the behavior of algorithms in this area.
                                            ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓    Abstract:␈α' This␈α&report␈α'contains␈α&a
␈↓ ↓N␈↓complete␈αderivation␈αand␈αdescription␈α
of␈αtwo       ␈↓ π∞␈↓SOL 78-28
␈↓ ↓N␈↓algorithms␈α'for␈α(nonlinearly␈α'constrained         ␈↓ π∞␈↓    MODULES␈α⊃TO␈α⊃AID␈α⊃THE␈α⊃IMPLEMENTATION
␈↓ ↓N␈↓optimization␈αwhich␈αare␈αbased␈αon␈αproperties       ␈↓ π∞␈↓OF LP ALGORITHMS
␈↓ ↓N␈↓of␈α the␈αsolution␈αtrajectory␈αof␈αthe␈αquadratic
␈↓ ↓N␈↓penalty␈αfunction␈αand␈αthe␈αlogarithmic␈αbarrier     ␈↓ π∞␈↓Author:  Larry Nazareth
␈↓ ↓N␈↓α␈↓ W7


␈↓ ↓N␈↓    Abstract:␈α∩ Implementing␈α∩large␈α∩scale␈α∩LP      ␈↓ π∞␈↓Author:  Larry Nazareth
␈↓ ↓N␈↓algorithms␈αis␈αa␈αdifficult,␈αlaborious␈αand␈αoften
␈↓ ↓N␈↓poorly␈α⊂rewarded␈α∂task.␈α⊂ This␈α⊂is␈α∂particularly      ␈↓ π∞␈↓    Abstract:␈α⊃ We␈α⊂briefly␈α⊃go␈α⊂over␈α⊃the␈α⊂well
␈↓ ↓N␈↓true␈α of␈α!algorithms␈α which␈α!exploit␈α the             ␈↓ π∞␈↓known␈α⊂dual␈α⊂relationship␈α⊃between␈α⊂Dantzig-
␈↓ ↓N␈↓structure␈αof␈αthe␈αLP␈αmatrix.␈α For␈αthis␈αreason       ␈↓ π∞␈↓Wolfe␈α8Decomposition␈α8and␈α7Benders
␈↓ ↓N␈↓many␈αalgorithms␈α
have␈αbeen␈α
proposed␈αin␈α
the         ␈↓ π∞␈↓Decomposition,␈αin␈αorder␈αto␈αdevelop␈αsuitable
␈↓ ↓N␈↓literature,␈α⊂but␈α⊂few␈α⊂have␈α⊂been␈α⊂turned␈α∂into         ␈↓ π∞␈↓e␈α∪notation,␈α∪and␈α∪then␈α∪elaborate␈α∪upon␈α∪the
␈↓ ↓N␈↓good␈α
computer␈α
codes.␈α Very␈α
little␈α
is␈αknown        ␈↓ π∞␈↓dual␈α∞relationship␈α∞between␈α∞nested␈α
versions
␈↓ ↓N␈↓about␈α
the␈αrelative␈α
performance␈αof␈α
different      ␈↓ π∞␈↓of␈α?␈α
Dantzig-Wolfe␈α?␈αand␈α?␈α
Benders
␈↓ ↓N␈↓algorithms.␈α
 In␈α
this␈α
paper␈α
we␈α
discuss␈αsome        ␈↓ π∞␈↓Decomposition.␈α∀ Next␈α∀we␈α∀develop␈α∀a␈α∀new
␈↓ ↓N␈↓of␈α⊃the␈α⊃suggestions␈α⊂that␈α⊃have␈α⊃been␈α⊂made            ␈↓ π∞␈↓pair␈α"of␈α"dually␈α"related␈α!decompositions
␈↓ ↓N␈↓for␈αalleviating␈αthis␈αproblem␈αand␈αdescribe␈α
an      ␈↓ π∞␈↓termed␈α)symmetric␈α*Dantzig-Wolfe␈α)and
␈↓ ↓N␈↓approach␈α⊃based␈α⊃upon␈α⊃a␈α∩carefully␈α⊃defined          ␈↓ π∞␈↓symmetric␈α⊃Benders␈α∩Decomposition.␈α⊃ Finally
␈↓ ↓N␈↓collection␈α(of␈α(subroutines␈α)which␈α(are             ␈↓ π∞␈↓we␈α3discuss␈α2the␈α3advantages␈α2and
␈↓ ↓N␈↓designed␈α⊃to␈α⊃aid␈α⊃the␈α⊃task␈α⊃of␈α⊂implementing          ␈↓ π∞␈↓disadvantages␈α≥of␈α≤applying␈α≥nested␈α≤and
␈↓ ↓N␈↓and␈α$comparing␈α$LP␈α$algorithms.␈α# These             ␈↓ π∞␈↓symmetric␈αdecompositions␈αto␈α
structured␈αLP
␈↓ ↓N␈↓subroutines␈α
or␈α
modules␈α
may␈α
be␈α
regarded␈α
as         ␈↓ π∞␈↓problems,␈α)in␈α)particular␈α)to␈α(staircase
␈↓ ↓N␈↓the␈α('primitives'␈α)of␈α(a␈α)language␈α(for               ␈↓ π∞␈↓structures.
␈↓ ↓N␈↓implementing␈α↔experimental␈α↔LP␈α↔algorithms,       ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓particularly␈α
algorithms␈αwhich␈α
exploit␈αmatrix
␈↓ ↓N␈↓structure.␈α≥ A␈α≤set␈α≥of␈α≤such␈α≥modules␈α≤is              ␈↓ π∞␈↓SOL 78-31
␈↓ ↓N␈↓described.␈α∂ These␈α∞have␈α∂been␈α∞implemented         ␈↓ π∞␈↓    A␈α≡LAND␈α≥MANAGEMENT␈α≡MODEL␈α≥USING
␈↓ ↓N␈↓in␈α_FORTRAN,␈α_and␈α_user␈α_documentation␈α↔is            ␈↓ π∞␈↓DANTZIG-WOLFE DECOMPOSITION
␈↓ ↓N␈↓available.
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓Author:  Larry Nazareth

␈↓ ↓N␈↓SOL 78-29                                   ␈↓ π∞␈↓    Abstract:␈α≥ This␈α≤paper␈α≥deals␈α≥with␈α≤a
␈↓ ↓N␈↓    A␈α%STUDY␈α%OF␈α%CONJUGAT␈α$GRADIENT                ␈↓ π∞␈↓mathematical␈α↔model␈α⊗designed␈α↔to␈α⊗provide
␈↓ ↓N␈↓METHODS                                     ␈↓ π∞␈↓guidelines␈α∃for␈α∃managing␈α∃a␈α∃land␈α∃resource
                                            ␈↓ π∞␈↓over an extended period of time.
␈↓ ↓N␈↓Authors:  L. Nazareth & J. Nocedal
                                            ␈↓ π∞␈↓    We␈α∞develop␈α∞a␈α∞framework␈α∞which␈α∞permits
␈↓ ↓N␈↓    Abstract:␈α⊃ We␈α∩prove␈α⊃a␈α⊃number␈α∩of␈α⊃new           ␈↓ π∞␈↓sequences␈αof␈α
management␈αdecisions␈α
to␈αbe
␈↓ ↓N␈↓properties␈α⊂of␈α⊂algorithms␈α⊂of␈α⊃the␈α⊂Conjugate        ␈↓ π∞␈↓conveniently␈α6formulated,␈α6and␈α6their
␈↓ ↓N␈↓Gradient␈α⊃type,␈α⊃paying␈α∩particular␈α⊃attention      ␈↓ π∞␈↓associated␈α∪costs␈α∪and␈α∪benefits␈α∩specified.
␈↓ ↓N␈↓to␈α∃methods␈α∃which␈α∃utilize␈α⊗variable␈α∃metric         ␈↓ π∞␈↓This␈α∩takes␈α∩the␈α∩form␈α∩of␈α∩a␈α∩network.␈α⊃ Each
␈↓ ↓N␈↓information␈α⊗in␈α⊗determining␈α↔the␈α⊗conjugate        ␈↓ π∞␈↓path␈α∞in␈α
the␈α∞network␈α
represents␈α∞a␈α
possible
␈↓ ↓N␈↓gradient␈αsearch␈αdirections.␈α We␈α
attempt␈αto       ␈↓ π∞␈↓decision␈α≠sequence.␈α≠ We␈α≠study␈α≠how␈α~to
␈↓ ↓N␈↓a␈α)comprehensive␈α)discussion␈α*of␈α)the               ␈↓ π∞␈↓select␈α_suitable␈α↔decision␈α_sequences␈α↔and
␈↓ ↓N␈↓conjugate␈α∩gradient␈α∩methods,␈α∩and␈α∩present         ␈↓ π∞␈↓what␈αproportion␈αof␈αthe␈αresource␈αto␈αmanage
␈↓ ↓N␈↓each␈α
algorithm␈α
within␈α
the␈α
context␈α
of␈α
other        ␈↓ π∞␈↓with␈α∀each␈α∃selected␈α∀sequence,␈α∀so␈α∃as␈α∀to
␈↓ ↓N␈↓existing␈α≠algorithms,␈α≠an␈α≠approach␈α≠which          ␈↓ π∞␈↓optimize␈α≤some␈α≤specified␈α≥objective␈α≤and
␈↓ ↓N␈↓provides␈α~fresh␈α~insights␈α~and␈α≠some␈α~new             ␈↓ π∞␈↓meet␈α0the␈α0constraints␈α1imposed␈α0on
␈↓ ↓N␈↓algorithms.                                 ␈↓ π∞␈↓management␈α≤of␈α≠the␈α≤resource.␈α≤ An␈α≠L.P.
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓model␈α⊂is␈α⊂formulated.␈α⊂ The␈α⊂solutio␈α⊂strategy
                                            ␈↓ π∞␈↓decomposes␈α
the␈α
L.P.␈α
matrix␈α
using␈α
Dantzig-
␈↓ ↓N␈↓SOL 78-30                                   ␈↓ π∞␈↓Wolfe␈α%decomposition␈α$and␈α%solves␈α$the
␈↓ ↓N␈↓    DUALLY␈α'EQUIVALENT␈α&DECOMPOSITION           ␈↓ π∞␈↓subproblems␈α1efficiently␈α1by␈α1dynamic
␈↓ ↓N␈↓ALGORITHMS␈α2WITH␈α2APPLICATION␈α1TO                 ␈↓ π∞␈↓programming␈α∩or␈α∩a␈α∩network␈α∪flow␈α∩algorithm.
␈↓ ↓N␈↓SOLVING STAIRCASE STRUCTURES
␈↓ ↓N␈↓α␈↓ n8


␈↓ ↓N␈↓Computational␈α⊂aspects␈α⊂are␈α⊃discussed␈α⊂and
␈↓ ↓N␈↓the␈α-concepts␈α-and␈α-procedures␈α-are
␈↓ ↓N␈↓illustrated␈α≤in␈α≤the␈α≤Appendix,␈α≤for␈α≠forest
␈↓ ↓N␈↓management.
␈↓ ↓N␈↓--␈↓ ε∩--

␈↓ ↓N␈↓SOL 78-32
␈↓ ↓N␈↓    SOFTWARE FOR OPTIMIZATION

␈↓ ↓N␈↓Author:  Larry Nazareth

␈↓ ↓N␈↓    Abstract:␈α∪ Our␈α∪aim␈α∪in␈α∪this␈α∪paper␈α∪is␈α∪to
␈↓ ↓N␈↓provide the reader with:

␈↓ ↓N␈↓    a)␈α
 Some␈αfeel␈α
for␈αwhat␈α
quality␈αsoftware
␈↓ ↓N␈↓entails.

␈↓ ↓N␈↓    b)␈α⊃ An␈α⊃overview␈α⊂of␈α⊃various␈α⊃aspects␈α⊂of
␈↓ ↓N␈↓optimization software.

␈↓ ↓N␈↓    c)␈α∃ Information␈α∃on␈α⊗solution␈α∃techniques
␈↓ ↓N␈↓and␈α∪available␈α∪software␈α∀in␈α∪the␈α∪form␈α∀of␈α∪a
␈↓ ↓N␈↓decision tree.

␈↓ ↓N␈↓    d)␈α∀ An␈α∀extensive␈α∀bibliography␈α∀so␈α∀that
␈↓ ↓N␈↓the␈α_reader␈α_can␈α_further␈α_pursue␈α↔specific
␈↓ ↓N␈↓topics of interest.

␈↓ ↓N␈↓    We␈α?␈αλconcentrate␈α?␈αλupon␈α?␈απlinear
␈↓ ↓N␈↓programming,␈α0non-linear␈α0unconstrained
␈↓ ↓N␈↓optimization␈α∪and␈α∪related␈α∪areas,␈α∀and␈α∪non-
␈↓ ↓N␈↓linear programming.

␈↓ ↓N␈↓    This␈αpaper␈αis␈αintended␈αto␈αsupplement␈αan
␈↓ ↓N␈↓earlier␈α~oral␈α~presentation␈α~at␈α~the␈α~Texas
␈↓ ↓N␈↓Conferenct␈α$on␈α$Mathematical␈α$Software
␈↓ ↓N␈↓entitled␈α5"State␈α5of␈α6Software␈α5for
␈↓ ↓N␈↓Optimization".
␈↓ ↓N␈↓--␈↓ ε∩--
␈↓ ↓N␈↓α␈↓ n9


␈↓ ↓N␈↓␈↓ β∨CSL REPORTS                                 ␈↓ π∞␈↓We␈α≡also␈α≡indicate␈α≡how␈α≡optimal␈α≥control
                                            ␈↓ π∞␈↓structures may be constructed.
␈↓ ↓N␈↓    The␈α
following␈α
reports␈α
are␈α
available␈α
from     ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓the␈α$Computer␈α$Systems␈α%Lab.␈α$ Further
␈↓ ↓N␈↓information␈α∞on␈α∞them␈α∞can␈α∞be␈α∞obtained␈α
from:         ␈↓ π∞␈↓CSL TR-158
␈↓ ↓N␈↓Naomi␈α2Schulman,␈α2Computer␈α1Science               ␈↓ π∞␈↓    PERFORMANCE␈α CHARACTERIZATION␈α∨OF
␈↓ ↓N␈↓Laboratory,␈α∩ERL-234,␈α∪Stanford␈α∩University,      ␈↓ π∞␈↓PARALLEL COMPUTATIONS
␈↓ ↓N␈↓Stanford, California 94305 U.S.A.
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓Author:  Ruby Bei-Loh Lee

␈↓ ↓N␈↓CSL TR-156                                  ␈↓ π∞␈↓    Abstract:␈α# This␈α#paper␈α#defines␈α"and
␈↓ ↓N␈↓    OPTIMAL␈α?␈α!PROGRAM␈α?␈α CONTROL                   ␈↓ π∞␈↓interprets␈α∩quantitative␈α∩measure␈α∩by␈α∩which
␈↓ ↓N␈↓STRUCTURES␈α⊃BASED␈α⊃ON␈α⊃THE␈α⊃CONCEPT␈α⊃OF               ␈↓ π∞␈↓we␈α_may␈α_characterise␈α_the␈α_absolute␈α_and
␈↓ ↓N␈↓DECISION ENTROPY                            ␈↓ π∞␈↓relative␈α-performance␈α-of␈α.a␈α-parallel
                                            ␈↓ π∞␈↓computation,␈α⊂compared␈α⊂with␈α⊂an␈α∂equivalent
␈↓ ↓N␈↓Author:  Ruby Bei-Loh Lee                   ␈↓ π∞␈↓serial␈α;computation.␈α; The␈α;absolute
                                            ␈↓ π∞␈↓performance␈α∀measure␈α∀are␈α∀the␈α∪Parallelism
␈↓ ↓N␈↓    Abstract:␈α
 The␈α
ability␈α
to␈α
make␈αdecisions     ␈↓ π∞␈↓Index,␈α∂PI(P),␈α⊂the␈α∂Utilization,␈α∂U(P),␈α⊂and␈α∂the
␈↓ ↓N␈↓dynamically␈α∂during␈α∂program␈α∂execution␈α∂is␈α∂a        ␈↓ π∞␈↓maximum␈α∂Quality,␈α∞Q(P).␈α∂ The␈α∞corresponding
␈↓ ↓N␈↓very␈α2powerful␈α2and␈α2valuable␈α2tool.                ␈↓ π∞␈↓relative␈α~performance␈α→measures␈α~are␈α→the
␈↓ ↓N␈↓Unfortunately,␈α#it␈α#also␈α#causes␈α"severe            ␈↓ π∞␈↓Speedup,␈α_S(P,1),␈α↔the␈α_Efficiency,␈α↔E(P,1),
␈↓ ↓N␈↓performance␈α→degradations␈α→in␈α_high-speed         ␈↓ π∞␈↓and␈αthe␈αQuality,␈α
Q(P,1).␈α We␈αshow␈α
how␈αthe
␈↓ ↓N␈↓computer␈α∂organizations␈α∂which␈α∂use␈α∞parallel,      ␈↓ π∞␈↓corresponding␈α.absolute␈α.and␈α-relative
␈↓ ↓N␈↓pipelined␈α
or␈α
lookahead␈α
techniques␈α
to␈α
speed       ␈↓ π∞␈↓performance␈α∞measures␈α
are␈α∞related␈α∞via␈α
the
␈↓ ↓N␈↓up␈α⊃program␈α⊂execution.␈α⊃ An␈α⊃optimal␈α⊂control        ␈↓ π∞␈↓Redundancy␈α≠measure,␈α≠R(P,1).␈α≠ We␈α≠also
␈↓ ↓N␈↓structure␈α
is␈α
one␈α
where␈α
the␈α
average␈α
number         ␈↓ π∞␈↓examine␈α∪the␈α∩range␈α∪of␈α∪permissible␈α∩values
␈↓ ↓N␈↓of␈α∀decisions␈α∀to␈α∀be␈α∀made␈α∀during␈α∀program            ␈↓ π∞␈↓for each performance measure.
␈↓ ↓N␈↓execution␈α≠is␈α≤minimal␈α≠among␈α≤all␈α≠control
␈↓ ↓N␈↓structures␈α+for␈α+the␈α,program.␈α+ Since              ␈↓ π∞␈↓    Ideally,␈α∀we␈α∃would␈α∀like␈α∀to␈α∃compare␈α∀an
␈↓ ↓N␈↓decisions␈α!are␈α usually␈α!represented␈α by            ␈↓ π∞␈↓optimal␈αparallel␈αcomputation␈αwith␈αan␈αoptimal
␈↓ ↓N␈↓conditional␈α∩branch␈α∩instructions,␈α∩finding␈α⊃an     ␈↓ π∞␈↓equivalent␈α∩serial␈α⊃computation,␈α∩in␈α∩order␈α⊃to
␈↓ ↓N␈↓optimal␈α∩control␈α∩structure␈α∩is␈α∪equivalent␈α∩to       ␈↓ π∞␈↓determine␈α~the␈α~prformance␈α~improvements
␈↓ ↓N␈↓minimizing␈α)the␈α)expected␈α*number␈α)of               ␈↓ π∞␈↓due␈α#solely␈α$to␈α#parallel␈α$versus␈α#serial
␈↓ ↓N␈↓conditional␈α#branch␈α#insturctions␈α$to␈α#be           ␈↓ π∞␈↓processing.␈α∀ Toward␈α∀this␈α∀end,␈α∀we␈α∪define
␈↓ ↓N␈↓encountered per program execution.          ␈↓ π∞␈↓optimal␈α↔parallel␈α↔and␈α_serial␈α↔computations,
                                            ␈↓ π∞␈↓and␈α_show␈α_how␈α_such␈α_optimality␈α_may␈α_be
␈↓ ↓N␈↓    By␈α#decision␈α#entropy,␈α#we␈α#mean␈α#a               ␈↓ π∞␈↓approximated in practice.
␈↓ ↓N␈↓quantitive␈α8characterization␈α9of␈α8the
␈↓ ↓N␈↓uncertainty␈α
in␈α
the␈α
instruction␈α
stream␈α
due␈α
to      ␈↓ π∞␈↓    In␈α⊂order␈α∂to␈α⊂facilitate␈α∂the␈α⊂calculation␈α∂of
␈↓ ↓N␈↓dynamic␈α)decisions␈α)imbedded␈α*in␈α)the               ␈↓ π∞␈↓the␈α
above␈α
performance␈α
measures,␈α
we␈α
show
␈↓ ↓N␈↓program.␈α∨ We␈α∨define␈α∨this␈α∨concept␈α∨of              ␈↓ π∞␈↓how␈α"the␈α"complexity␈α"of␈α"modelling␈α!an
␈↓ ↓N␈↓decision␈α3entropy␈α2in␈α3the␈α2Shannon                 ␈↓ π∞␈↓arbitrary␈α!parallel␈α computation␈α!may␈α be
␈↓ ↓N␈↓information-theoretic␈α
sense.␈α
 We␈αshow␈α
that      ␈↓ π∞␈↓reduced␈α&substantially␈α&to␈α&two␈α&simple
␈↓ ↓N␈↓a␈αprogram's␈αintrinsic␈αdecision␈αentropy␈αis␈αan      ␈↓ π∞␈↓canonical␈α~forms,␈α~which␈α~we␈α≠denote␈α~the
␈↓ ↓N␈↓absolute␈α~lower␈α~bound␈α~on␈α~the␈α~expeced              ␈↓ π∞␈↓computations's␈αParallelism␈αProfile␈αand␈αTOP-
␈↓ ↓N␈↓number␈α∞of␈α∂decisions,␈α∞or␈α∂conditional␈α∞brance       ␈↓ π∞␈↓form.
␈↓ ↓N␈↓instructions,␈α∀per␈α∀program␈α∀execution.␈α∀ We
␈↓ ↓N␈↓show␈α∂that␈α∂this␈α∞lower␈α∂bound␈α∂is␈α∂achieved␈α∞if          ␈↓ π∞␈↓    Finally,␈α⊃we␈α⊂show␈α⊃how␈α⊂all␈α⊃the␈α⊂canonical
␈↓ ↓N␈↓each␈α⊗decision␈α⊗has␈α⊗maximum␈α⊗uncertainty.          ␈↓ π∞␈↓forms␈α⊃and␈α⊃performance␈α⊃measures␈α⊃may␈α⊃be
␈↓ ↓N␈↓α␈↓ @10


␈↓ ↓N␈↓generalized␈α
from␈α
one␈α
computation␈α
to␈α∞a␈α
set         ␈↓ π∞␈↓supported␈αhere␈αis␈αFOTRAN␈αto␈αthe␈α
full␈α1966
␈↓ ↓N␈↓of␈α∃computations,␈α⊗to␈α∃arrive␈α⊗at␈α∃aggregate          ␈↓ π∞␈↓standard,␈α⊗extended␈α∃with␈α⊗those␈α∃features
␈↓ ↓N␈↓canonical and performance descriptions.     ␈↓ π∞␈↓commonly␈α≤expected␈α≤by␈α≥available␈α≤large
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓scientific programs.
                                            ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓CSL TR-159
␈↓ ↓N␈↓    SPECIFICATION␈α⊃AND␈α⊃VERIFICATION␈α⊃OF␈α⊃A         ␈↓ π∞␈↓CSL TR-161␈↓ 	←(STAN-CS-79-715) 
␈↓ ↓N␈↓NETWORK MAIL SYSTEM                         ␈↓ π∞␈↓    S-1 ARCHITECTURE MANUAL

␈↓ ↓N␈↓Author:  Susan S. Owicki                    ␈↓ π∞␈↓Authors:␈α→ Brent␈α→T.␈α→Hailpern␈α→&␈α→Bruce␈α→L.
                                            ␈↓ π∞␈↓Hitson
␈↓ ↓N␈↓    Abstract:␈α≡ Techniques␈α≡for␈α≥describing
␈↓ ↓N␈↓and␈α*verifying␈α*modular␈α+systems␈α*are               ␈↓ π∞␈↓    Abstract:␈α$ This␈α$manual␈α$provides␈α#a
␈↓ ↓N␈↓issustrated␈α⊗using␈α⊗a␈α⊗simple␈α↔network␈α⊗mail          ␈↓ π∞␈↓complete␈αdescription␈αof␈αthe␈αinstruction-set
␈↓ ↓N␈↓problem.␈α The␈αdesign␈αis␈αpresented␈αin␈αa␈α
top-        ␈↓ π∞␈↓architectures␈α≥of␈α≥the␈α≥S-1␈α≤Uniprocessor
␈↓ ↓N␈↓down␈α⊃style.␈α⊂ At␈α⊃each␈α⊂level␈α⊃of␈α⊂refinement,         ␈↓ π∞␈↓(Mark␈α
IIA),␈α
exclusive␈α
of␈α∞vector␈α
operations.
␈↓ ↓N␈↓the␈α⊂specifications␈α⊂of␈α⊂the␈α⊂higher␈α⊂level␈α∂are        ␈↓ π∞␈↓It␈α~is␈α~assumed␈α~that␈α~the␈α~reader␈α~has␈α~a
␈↓ ↓N␈↓verified␈α∪from␈α∀the␈α∪specifications␈α∀of␈α∪lower        ␈↓ π∞␈↓general␈α?␈α∧knowledge␈α?␈α∧of␈α?␈αβcomputer
␈↓ ↓N␈↓level components.                           ␈↓ π∞␈↓architecture.␈α
 The␈αmanual␈α
was␈α
designed␈αto
␈↓ ↓N␈↓--␈↓ ε∩--                                        ␈↓ π∞␈↓be␈α
both␈α
a␈α∞detailed␈α
introduction␈α
to␈α∞the␈α
S-1
                                            ␈↓ π∞␈↓and␈α≤an␈α≤architecture␈α≤reference␈α≤manual.
␈↓ ↓N␈↓CSL TR-160␈↓ ∧∨(STAN-CS-79-714)                  ␈↓ π∞␈↓Also␈α↔included␈α⊗are␈α↔user␈α⊗manuals␈α↔for␈α⊗the
␈↓ ↓N␈↓    PCFORT:␈α?␈α	 A␈α?␈αλFORTRAN-TO-PCODE               ␈↓ π∞␈↓FASM
␈↓ ↓N␈↓TRANSLATOR                                  ␈↓ π∞␈↓--␈↓ R--

␈↓ ↓N␈↓Authors:␈α↔ Fernando␈α↔Castaneda,␈α⊗Frederick        ␈↓ π∞␈↓CSL TN-145
␈↓ ↓N␈↓Chow,␈α≤Peter␈α≥Nye,␈α≤Dan␈α≤Sleator␈α≥&␈α≤Gio                ␈↓ π∞␈↓    DESIGN␈α+FOR␈α,MAINTAINABILITY␈α+AND
␈↓ ↓N␈↓Wiederhold                                  ␈↓ π∞␈↓TESTABILITY

␈↓ ↓N␈↓    Abstract:␈α∞ PCFORT␈α∞is␈α
a␈α∞compiler␈α∞for␈α
the       ␈↓ π∞␈↓Author:  Edward J. McClukey
␈↓ ↓N␈↓FORTRAN␈α∃language␈α∃designed␈α∃to␈α∃fit␈α∃as␈α∀a
␈↓ ↓N␈↓building␈α≤block␈α≥into␈α≤a␈α≥PASCAL␈α≤oriented            ␈↓ π∞␈↓    Abstract:␈α This␈αpaper␈αpresents␈αa␈αsurvey
␈↓ ↓N␈↓environment.␈α' It␈α'forms␈α'part␈α'of␈α&the               ␈↓ π∞␈↓of␈α≠various␈α~techniques␈α≠that␈α≠have␈α~been
␈↓ ↓N␈↓programming␈α⊂systems␈α∂being␈α⊂developed␈α∂for         ␈↓ π∞␈↓proposed␈αfor␈αdesign␈αof␈αdigital␈αsystems␈α
that
␈↓ ↓N␈↓the␈α∃S-1␈α∃multiprocessor.␈α∃ It␈α∃is␈α∃written␈α∀in         ␈↓ π∞␈↓can␈αbe␈αeasily␈αtested␈αor␈αmaintained␈αor␈αboth.
␈↓ ↓N␈↓PASCAL,␈α(and␈α(generates␈α(P-code,␈α(an                ␈↓ π∞␈↓An extensive bibliography is included.
␈↓ ↓N␈↓intermediate␈α?␈αεlanguage␈α?␈απused␈α?␈αεby                  ␈↓ π∞␈↓--␈↓ R--
␈↓ ↓N␈↓transportable␈α4PASCAL␈α5compilers␈α4to
␈↓ ↓N␈↓represent␈αthe␈αprogram␈αin␈αa␈αsimple␈αform.␈α P-        ␈↓ π∞␈↓CSL TN-146
␈↓ ↓N␈↓code␈α~is␈α~either␈α~compiled␈α≠or␈α~interpreted           ␈↓ π∞␈↓    PERFORMANCE␈α∂COMPARISON␈α⊂OF␈α∂UPDATE
␈↓ ↓N␈↓depending␈α~upon␈α≠the␈α~objectives␈α≠of␈α~the             ␈↓ π∞␈↓ALGORITHMS FOR DISTRIBUTED DATABASES
␈↓ ↓N␈↓programming system.
                                            ␈↓ π∞␈↓Author:  Hector Garcia-Molina
␈↓ ↓N␈↓    A␈α≠PASCAL␈α≠written␈α≤FORTRAN␈α≠compiler
␈↓ ↓N␈↓provides␈α∪a␈α∪bridge␈α∪between␈α∪the␈α∩FORTRAN            ␈↓ π∞␈↓    Abstract:␈α⊂ A␈α⊂centralized␈α⊂locking␈α⊂update
␈↓ ↓N␈↓and␈α?␈α	PASCAL␈α?␈α	communities.␈α?␈α	 The                   ␈↓ π∞␈↓algorithm␈α↔for␈α↔distributed␈α↔databases␈α↔was
␈↓ ↓N␈↓implementation␈α6allows␈α6PASCAL␈α5and               ␈↓ π∞␈↓presented␈αand␈αits␈αperformance␈αanalyzed␈αin
␈↓ ↓N␈↓FORTRAN␈α⊂generated␈α⊂code␈α⊂to␈α⊃be␈α⊂combined            ␈↓ π∞␈↓[1].␈α⊗ (The␈α⊗algorithm␈α∃was␈α⊗studied␈α⊗in␈α∃the
␈↓ ↓N␈↓into␈α⊂one␈α⊂program.␈α⊂ The␈α⊂FORTRAN␈α⊂language          ␈↓ π∞␈↓case␈α∩of␈α⊃completely␈α∩duplicated␈α⊃databases
␈↓ ↓N␈↓α␈↓ @11


␈↓ ↓N␈↓in␈α
a␈α
no␈αfailure␈α
update␈α
only␈αenvironment.)␈α
 In      ␈↓ π∞␈↓    P-CODE␈α3INTERMEDIATE␈α2ASSEMBLER
␈↓ ↓N␈↓that␈αalgorithm,␈αan␈αupdate␈αsequence␈α
number        ␈↓ π∞␈↓LANGUAGE
␈↓ ↓N␈↓was␈α⊃added␈α∩to␈α⊃all␈α∩lock␈α⊃grant␈α∩and␈α⊃perfomr
␈↓ ↓N␈↓update␈α≠messages␈α≠in␈α≠order␈α≠to␈α~properly             ␈↓ π∞␈↓Authors:  Erick J. Gilbert & David W. Wall
␈↓ ↓N␈↓sequence␈α+conflicting␈α+updates.␈α+ Even
␈↓ ↓N␈↓though␈αit␈αwas␈αnot␈αmentioned␈αin␈αthat␈αreport,        ␈↓ π∞␈↓    Abstract:␈α
 The␈αsyntax␈α
and␈α
semantics␈αof
␈↓ ↓N␈↓each␈α lock␈α∨grant␈α and␈α perform␈α∨update               ␈↓ π∞␈↓P-Code,␈α
the␈αinter␈α
mediate␈α
language␈αused␈α
in
␈↓ ↓N␈↓message␈α_issued␈α_must␈α_contain␈α_additional          ␈↓ π∞␈↓the␈α↔current␈α↔S-1␈α↔programming␈α↔system␈α↔is
␈↓ ↓N␈↓information␈αbecause␈α
otherwise␈αthe␈α
updates       ␈↓ π∞␈↓described.
␈↓ ↓N␈↓are performed with reduced parallelism.     ␈↓ π∞␈↓--␈↓ R--

␈↓ ↓N␈↓    This␈α⊂report␈α∂will␈α⊂describe␈α⊂this␈α∂additional
␈↓ ↓N␈↓information␈α↔and␈α↔why␈α⊗it␈α↔is␈α↔needed.␈α⊗ The
␈↓ ↓N␈↓effect␈α∩on␈α∪prformance␈α∩of␈α∩only␈α∪including␈α∩a
␈↓ ↓N␈↓fraction␈α
of␈αthis␈α
information␈α
in␈αthe␈α
messages
␈↓ ↓N␈↓is␈α
then␈αstudied␈α
through␈αsimulations.␈α
 Finally,
␈↓ ↓N␈↓several␈α≤implementation␈α≥alternatives␈α≤are
␈↓ ↓N␈↓suggested␈α→for␈α_coding␈α→and␈α→handling␈α_the
␈↓ ↓N␈↓additional information in the messages.
␈↓ ↓N␈↓--␈↓ ε∩--

␈↓ ↓N␈↓CSL TN-147
␈↓ ↓N␈↓    S-1␈αINTERMEDIATE␈αLOADER␈α
FORMAT␈αAND
␈↓ ↓N␈↓S-1 LINKER

␈↓ ↓N␈↓Authors:  Arthur Keller & Gio Wiederhold

␈↓ ↓N␈↓    Abstract:␈α The␈αloader␈αformat␈αfor␈αthe␈αS-1
␈↓ ↓N␈↓and␈α↔the␈α↔Linker␈α⊗for␈α↔the␈α↔S-1␈α↔ using␈α⊗this
␈↓ ↓N␈↓format␈α# are␈α# described.␈α#  The␈α# loader
␈↓ ↓N␈↓format␈α; was␈α: designed␈α; to␈α: be
␈↓ ↓N␈↓transportable,␈α easily␈α  human␈α∨ readable,
␈↓ ↓N␈↓and␈α∪editable␈α∩ on␈α∪ available␈α∪ text␈α∩editors.
␈↓ ↓N␈↓For␈α≠ these␈α~ reasons,␈α≠ it␈α~ only␈α≠uses␈α~ a
␈↓ ↓N␈↓minimal␈α↔ subset␈α_ of␈α↔ the␈α_printable␈α↔ASCII
␈↓ ↓N␈↓character␈α∀set.␈α∀ It␈α∀is␈α∀ used␈α∀for␈α∃both␈α∀the
␈↓ ↓N␈↓Linker␈αinput␈α and␈α
output,␈αso␈αthat␈αlinking␈α
can
␈↓ ↓N␈↓proceed in stages.

␈↓ ↓N␈↓    The␈α&Linker␈α&is␈α&part␈α&of␈α&the␈α&S-1
␈↓ ↓N␈↓programming␈α∩system.␈α⊃ It␈α∩was␈α∩designed␈α⊃to
␈↓ ↓N␈↓support␈α linking␈αmodules␈α from␈αcompilers␈α of
␈↓ ↓N␈↓different␈α∂ languages.␈α∂  In␈α∂order␈α∂to␈α∂make␈α∞it
␈↓ ↓N␈↓transportable,␈α∀it␈α∃was␈α∀written␈α∃in␈α∀PASCAL.
␈↓ ↓N␈↓The␈α
output␈α can␈α
be␈α
relocatable␈αor␈α
absolute,
␈↓ ↓N␈↓but it is usually absolute.
␈↓ ↓N␈↓--␈↓ ε∩--

␈↓ ↓N␈↓CSL TN-148