E
`
`z3
`
`
`
`:\§§T§’§3iCflA.L 1E‘€'fI:§I.,i,.l(.i}3}
`
`ufia-aflased £@z2figm‘m2*
`ai Qwmmaéer fiygéa 3%‘
`
`
`éohn Ma§3rermz>£€
`
`Dc;>¢1:'iev‘mv: of (.713/}?;7?4fa“r§c’7i€I3C£?. C?:rm{;i:a~Me’?!zm
`E,r':2iz:£!:’5§r};, §§z:i:e271¢:'y {*’ar!:. Pi££:;bm'g§2. PA 15233.
`!J‘..‘§.A,
`
`fix. Feigenbaum
`Re::<>mmcnck:d ivy E:iwar<:i
`
`,...._...?...............
`AVMA............._._................A.....____......_._....____._.._........
`
`81 :'.t;rz;m;grm21 that crmfigurm‘ V/X36’-I137330mmpuzcrwsienzs‘ G:'z>en it cLasIunwr’.s vrzimt is a‘.:,?(e?1-'I1:i:§€.€
`wlmx, if (my. a2~.r3:2’ifx.'aIi(>ns have 1:; 124' made InxI:€t1rd<£r[(:rr::aM.§I15 a_f3ys!cm f:::mimaa.=‘:‘:y mm’ }7ma‘(éce.s* L:
`aurzzbcr of diagrams simwing how 11:? :,>arz'(:w; cvrr.=;><Im>nt.~z on (Ami rmiev {me to be u\'.\. ocixzlaf. Pic prugmm
`is «tume::.tly being used an a reguizzr basis by [)i;;i¥ua'
`I%'z.1u:',{.>nw::! C’or,zmran'rm’.s mam¢)‘}zctun'ng
`z:rg<n2:'2aIiw‘r, R1 is €n;;,:I<~::mzIed as :2 {1::nfl!¢.‘_l'.‘0ll S}£S‘!(’I‘-Q. I: was Mam}: as in pr2'm‘i;>a{ ;:mI.vI«::m- 5<2l:‘£::g
`ayzwizodz I: 3141.; ssxj}‘1'c€z>.::1
`i:nmvle*a’ge of she ronfigzsratzkuz xionzain and of the pcmI:'ari:i.es of the mriaus
`mnjigzcraxian m.m:!rm'm'.s' I}zatt1£<'(1c‘5I mag: 51: rixe canfzguraiiarx prcwzass, £1 ,s'x'mp!); mmgrrizczs what In clux
`C0nscqum1i}.=. lime search is reqzsirezti in orzierfcar {I I0 cwsfigtarr cs. mmpuzer synrlern.
`
`1. Introduction
`
`RE‘ 33 a .mIe—based system that has much in czmnmcm with other d0m3in~s;pet:.ifi::
`systems that hzwe heen develop;-(3 (user the past :»3r:vt:ra! years [1, '13]. 3t differs
`fmm ilzezsz-3 systems primarily in its use of Match rather ihan {3:;.ne1‘s31e-ami-test
`as its central pmblexn soiviug nzethcrd; rather than exploring several hypotheses
`émiii an acceptabic one is fnund. it expioits its knowledge of its task domain IQ
`generate a single acceplablrs. soiutican. RPS pzmicuiar area cf expertise is {ha
`
`’The develmpmcnl of R3 was supprmed by Digital Equipmeni Corpuralitfm. The research rhea:
`Mi :0 she di-zvelapmexaa of (3984, the language in which R! is wfitmm
`:;;2c»nwrec§ by [he
`Ditiensa: Ad\>:3nt.e.r} Research .Pr0juc1s fkgexmg (DOB). AHPA (Brae: Na. 359?. and mmiwresd hy
`1316: Air Force Axriuxaics .i.ai>oraImy under Ceonmact 3733635-?3~C~11S1. The vifiwx and <:un<:iusi:ms
`comained in ihis dommeni are those ni ihn: author and should not tax: interpreted
`representing
`the ofljcial }>{31iCi€‘$,
`zeither cxprcssed or iznpiied. of Qigiial \Equ§y:m:rA C‘m‘§,sm*ax1iun.
`tbf.’ Defense.
`Advanccd Research Projects Agency‘ my $36: US. Ci0\’ernmc:.n!.
`\~’.¢«.X.,
`I’D}"‘§I. LE¥\3§3'_3'LiS, and
`MASSBIJS are tradma;-ks of Digital Eiquipmcni Curpurarims.
`, ..
`‘Four years ago 1 couldrfi own my “knmxrledga engineer“. new I 1
`.4rtifit'fa1 1n,ré2:;gem aux ::2>:»s2} 3Q~?i$
`
`
`
`Page 1 of 34
`
`FORD 1211
`
`

`
`
`
`‘
`
`
`
`
`
`40
`
`J. MCDERMOTT .
`
`configuring of Digital Equipment Corporations VAX—11/780 systems. Its input 3
`is a customers Order and its output is a set of diagrams displaying the spatial
`-
`relationships among the components on the order; these diagrams are used by
`the technician who physically assembles the system.’ Two interdependent
`activities must be performed in configuring a VAX system.
`6 The customer’s order must be determined to be complete; if it is not, whatever
`components are missing must be added to the order.
`V
`Q The spatial relationships among all of the components (including those that are ,
`added) must be determined.
`The criterion of success for whether a configuration is complete does not reside
`in any simple test, but
`involves instead particular knowledge about all
`the
`individual components and their relationships. The criterion of successful
`spatial arrangement
`is more compact
`(reflecting the uniform character of
`geometric structure), but it too involves particular knowledge on a component
`by component basis. Thus, task accomplishment is defined by a large set of
`Constraints embodying a large amount of knowledge.
`Rl’s approach to the configuration task is to start with the set of components
`on the order and construct an acceptable configuration using its knowledge of
`the constraints on component relationships. Since it’s strategy is wholehartedly
`bottom-up, it may seem surprising that R1 is able to generate an acceptable
`configuration without doing backtracking. R1 is able to avoid search because its
`task domain permits the use of the Match method [9]. Match will be discussed
`at
`length in Section 2.3 below. Basically,
`the method is applicable if it
`is
`possible to order a set of decisions in such a way that no decision has to be
`made until the information sufficient for making that decision is available. This
`applicability condition is trivially satisfied if the set of decisions required by a
`task is fixed and can be ordered a priori. But in the VAX—1l/780 configuratio
`task. the set of decisions required varies widely from configuration to configura _
`tion. The Match method is a procedure for dynamically ordering a set of decisions. ,_.
`When Match is used, each decision brings one closer to the successful completion _
`of the task.
`
`it
`'
`i
`
`Although a significant portion of this paper is devoted to a description of
`precisely how R1 goes about doing the configuration task, I have tried to avoid
`letting the details of RI ‘s inner workings overshadow the domain independent
`lessons that have emerged from this research. There are two important lessons
`6 An expert system can perform a task simply by recognizing what to do,
`provided that‘it'is possible to determine locally (i.e., at each step) whether
`taking some particular action is consistent with acceptable performance on the
`task.
`
`oWhcn an expert system is implemented as a production system, the job of
`refining and extending the system‘s knowledge is quite easy.
`
`3R1’s output for a sample order is shown in Appendix B.
`
`
`
`Page 2 of 34
`
`FORD 1211
`
`

`
`
`
`
`
`_
`i
`'
`
`,
`”
`
`:' A RULEBASED CONFIGURER OF COMPUTER SYSTEMS
`
`most limited capabilities to what might fairly be called an expert. The third
`section describes Rl’s current
`level of expertise and isolates the design
`decisions that made the building of R1 straightforward.
`
`1. The Task
`
`. The VAX-11/780 is the first implementation of Digital Equipment Cor-
`poration’s VAX-ll architecture. It is similar in many respects to the PDP-11,
`hough its virtual address space is Znrather than 2"‘. The VAX~l1/780 uses a
`high speed synchronous bus, called the sbi (synchronous backplane inter-
`lonnect), as its primary interconnect. The central processor, one or two
`memory control units, one to four massbus interfaces, and one to four unibus
`nterfaces can be connected to the sbi. The massbuses and particularly the
`nibuses can support a wide variety of peripheral devices. Because the number
`fsystem variations is so large, the VAX configuration task is nontrivial.
`
`1.1. The size of the task
`
`A configurer must have two sorts of knowledge. First, he must have
`nformation about each of the components that a customer might order. For
`Z each component, the configurer must know the properties that are relevant to
`. system c0nfiguration—e.g., its voltage, its frequency, how many devices it can
`_ support (if it is a controller), how many ports it has; I will call this knowledge
`component information. Second, he must have rules that enable him to associate
`
`jcomponents to form partial configurations and to associate partial configura-
`tions to form a functionally acceptable system configuration. These rules must
`ndicate what components can (or. must} be associated -and: what constraints
`must be satisfied in order for these associations to be acceptable; I will call this
`nowledge constraint knowledge.
`The difficulty of the VAX configuration task is a function of the amount of
`omponent information and the amount of constraint knowledge required to
`F? atU)vr
`p-IV}
`"HE?1~<
`to3‘< 3 ('0V73‘El553.-. co 9 no
`toBOC:2 .. O"h
`!—i(‘F
`F)o5‘'0O:2 an:3 ('9
`
`over 3300 pieces of component information that a VAX configurer must have
`
`
`
`Before R1 was developed, it would have been difiicult to estimate accurately
`
`30f the 420 components, about 180 are actually bundles composed of various subsets of the
`remaining 240 Components.
`
`Page 3 of 34
`
`FORD 1211
`
`

`
`
`
`
`
`
`
`42
`
`
`
`the amount of constraint knowledge required for the configuration task. Muché
`of the required knowledge was not written down anywhere and thus the onlyg
`source of estimates would have been individual human experts. But the experts
`find the task of quantifying their constraint knowledge foreign. As I extracte /I"
`this knowledge from them, it became clear that their knowledge takes to forms
`(1) The experts have a sparse but highly reliable picture of their task domain
`When asked to describe the configuration task, they do so in terms of th
`subtasks involved and the various temporal relationships among these subtasks
`(2) They also have a considerable amount of very detailed knowledge tha
`indicates the features that particular partial configurations and uncontigure
`components must have in order for the partial configurations to be extended i
`particular ways.Both sorts of knowledge are easily expressable as rules.
`extracted 480 rules. Of these, 96 define situations in which some subtask shoul
`be initiated. The other 384 rules define situations in which some partials;
`configuration should-be extended in-some way.
`
`
`
`1.2. The constraints
`
`
`
`‘i1|
`
`
`
`
`
`:4
`is driven almost entirely by,
`that
`To understand a program, such as R],
`task-specific knowledge, it is necessary to understand the nature of the conli
`straints imposed by the task. This subsection provides an example of a specifi
`subtask that can arise within the configuration task and indicates (1)
`this
`constraint knowledge involved, (2) the informational demands imposed by thaé
`constraint knowledge, and (3) the extent to which the subtask presuppose
`other subtasks. The subtask is that of placing unibus modules in backplanes. As
`is the case with the configuration task in general, many of the constraints in th
`subtask have a strongly ad hoc flavor; they are not easily derivable from mot,‘
`general knowledge because they are the result of design decisions whose?
`justifications are hidden in a shadowy past. Moreover, the applicability of
`particular constraint is ordinarily dependent on a variety of factors; man
`
`
`
`account.
`
`Whenever more than one unibus optiop is ordered for a VAX, it is necessar
`to place the modules on the unibus in an acceptable sequence. Ignoring spati
`constraints,
`it
`is
`straightforward to determine the theoretically optim
`sequence. for..the...modules;
`the modules aresorted on the basis of
`the -
`interrupt priority and within that on the basis of their transfer rate. Before
`module can be placed on the unibus,
`it is necessary to select a backplan
`Several constraints come into play. Backplanes come in two sizes (4—sl0t and
`9—slot) and can have any of several pinning types. The backplane selected mu
`be of the pinning type required by the unibus module. To determine the size of
`the backplane to be selected, it is necessary, first, to determine whether the size
`is constrained by the box that the backplane will be placed in. A box c’
`accommodate five 4—slot backplanes; the exception is that a 9—slot backplane"
`
`Page 4 of 34
`
`FORD 1211
`
`

`
`
`
`
`
` R1: A RULELBASED CONFIGURER OF COMPUTER SYSTEMS
`
`
`
`
`
`43
`
`may not occupy the space reserved for the second and third 4—slot backplanesf’
`Assuming that either a 4»-slot or a 9-slot backplane would be acceptable, the
`next constraint to come into play is that a 9-slot backplane should not be
`selected unless the next N modules in the optimal sequence all require a
`backplane of the same type and will not all fit in a 4-slot backplane. Once a
`backplane is selected, the board or boards comprising the next module in the
`optimal sequence can be placed in the backplane. However, the first and last
`slots of a backplane cannot accomodate a full width board; thus the configurer
`must make sure that the boards will physically fit into the backplane. There are
`several other constraints. For example, the total amount of power that can be
`drawn from a regulator is limited; also, if the length of the unibus exceeds a
`certain limit or if the load on the unibus exceeds a certain limit, a backplane
`containing a unibus repeater must be placed in the box.
`. After a module has been placed in a backplane, there is frequently room for
`additional modules, but the next module in the optimal sequence may require a
`backplane of a different type or more space than is available in the backplane.
`At that point the configurer must decide whether to deviate from the optimal
`sequence or to leave some of the backplane slots empty; the decision is based
`on the total amount of box space available and the seriousness of the deviation.
`If there is suflicient box space to accommodate the modules when they are in
`the optimal sequence, the optimal sequence should be preserved (even if this
`entails adding additional backplanes to the order). If there is not sufficient
`space, the seriousness of the deviation must be determined; there are some less
`than optimal sequences that are acceptable. If the decision is that the deviation
`from the optimal would impair the functionality of
`the system,
`then the
`configurer must add another box (and possibly a cabinet as well) to the order; if
`the decision is that an acceptable suboptimal sequence can be found, then some
`module other than the next one in the optimal sequence is placed in the
`backplane. In general, it is acceptable to add a module that is not next in the
`-optimal sequence if it meets allof ‘the con’strai‘nt‘s mentioned above and has a
`transfer rate that
`is lower than that of any other module with the same
`interrupt priority that it will precede.
`There are reasons, other than lack of slot space or power, Why the configurer
`A must consider deviating from the optimal sequence. If the module that is to be
`added is a multiplexer, for example, then in addition to the space and power
`constraints, there is the added constraint that suflicient panel space must be
`available in the cabinet containing the box that will contain the multiplexer. If
`there is not enough panel space in that cabinet, the configurer must decide
`whether to deviate from the optimal ordering or to put all of the remaining
`modules in the remaining cabinets. Again, the decision must be made on the
`‘The box that contains unibus modules has two +5 volt regulators. One of these regulators supplies
`power to the first two slot backplanes (or to the first 9—slot backplane); the second supplies power to the
`other backplanes. All of the modules in a backplane must draw power from the same regulator.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 5 of 34
`
`FORD 1211
`
`

`
`
`
`
`
`
`
` 44
`
`J. McDER_M0'l'I"
`
`
`
`basis of the total space available and the seriousness of the deviation. If there
`are no other cabinets on the order, one must be added to the order.
`This description of how unibus modules are Configured brings to light most
`of the constraints relevant to that task for a simple, single unibus system. But it
`does not make very clear what the demands for component information are or
`the extent
`to which this task presupposes other tasks. For a module,
`the
`component information that the rules require is the module type, the number
`and size of each board in the module, transfer rate and interrupt priority, the
`pinning type required, the power drawn by the module, and the load it puts on
`the unibus. For a backplane, the information required is the pinning type, the
`size, the power drawn by the modules that have been placed in it, and the slots
`still available. For a box,
`the information is the box type,
`the amount of
`backplane space still available in the box, and the length of and load on its
`unibus. For a cabinet the information is the cabinet type and amount of box
`and panel space still available in the cabinet.
`Some of
`the tasks that
`this task presupposes were already mentioned:
`determining the optimal sequence, selecting a backplane, assigning the back-
`plane to a box, selecting some module other than the next one in the optimal
`sequence, verifying (when the module is a multiplexer) that there is sutficient
`panel space in the cabinet. There are several others: unibus adaptors have to
`have been configured (so unibus length can be computed); boxes have to have
`been assigned to cabinets and also to unibuses (so unibus length can be
`computed and so the amount of usable panel space will be known); the unibus
`cables that connect backplanes must be selected (so unibus length can be
`computed); before a module that is a laboratory peripheral can be put in a
`backplane,
`it must be determined that there is suflicient panel space in the
`cabinet and sufficient space and power in the box for the backplane that will
`contain the laboratory peripheral options.
`
`2. The System
`
`This section focuses on how to represent the knowledge required for the VAX
`configuration task so that the resulting system can perform the task expertly
`and etficiently and can easily acquire additional knowledge about the domain.
`The architecture in which R1 is embedded is described. Issues of search are
`discus'sed."Ili'e content and use of Ri1’s knowledge is analyzed. Finally, some
`design and implementation history is provided in order to show the extent to
`which the development of R1 was an evolutionary process.
`
`2.]. The production system architecture‘
`
`R1 is implemented as a production system [10]. The particular production
`system language used is OPS4. Since detailed descriptions of this language have
`
`
`
`Page 6 of 34
`
`FORD 1211
`
`

`
`
`
`
`
`l; A RULE~BASED CONFIGURER OF COMPUTER SYSTEMS
`
`‘been provided elsewhere [4, 5, 7], only a brief indication of the basic features of
`the language will be given in this paper. An OPS4 production system consists
`of a set of productions held in production memory and a set of data elements
`(e.g., state descriptions) held in working memory. A production is a conditional
`statement composed of conditions and actions; a production has the form
`
`Pg(CgC2'
`
`'
`
`' CH9/§;A2" ‘ 14,").
`
`An action typically modifies working memory by deleting, adding, or modifying
`data element; users may, however, define application specific actions. A
`‘condition is a pattern containing constants and variables; when each of the
`conditions in a production can be matched by an element in working memory,
`=the production is said to be instantiated. An instantiation is an ordered pair of
`production and a set of elements from working memory that satisfy the
`onditions of the production. The OPS4 interpreter operates within a control
`ramework called the recognize-act cycle. During the recognition part of the
`ycle, it finds the instantiation to be executed; during the act part, it performs
`he actions. The recognize—act cycle is repeated until either no production can
`e instantiated or an action explicitly stops the processing. Recognition can be
`ivided into pattern-match and conflict resolutions‘ During pattern-match, the
`"nterpreter finds the set of all instantiations of productions that are satisfied on
`-“the current cycle. During conflict resolution, it determines which instantiation
`
`OPS4 is a general—purpose production system language; it was not developed
`';with the configuration task in mind. Since OPS4 knows nothing of configura-
`;tion, all of the domain-specific knowledge that R1 requires to do the task——
`including domain-specific control knowledge—is contained in productions.
`.''Each of R1’s productions (rules) embodies a piece of constraint knowledge.
`_The ~production’s conditionstypically looksfor situations in. which a particular.
`2 type of extension to a particular type of partial configuration is permissable or
`required; the actions then effect that extension. Rl’s rules are such that on
`: almost every cycle several rules can be instantiated—frequently in a number of
`difierent ways. From Rl’s point of view, it often makes no difference which of
`_ these instantiations is executed; in these cases, how OPS4 determines which
`instantiation to execute is irrelevant.“ R1 does, however, rely heavily on one of
`OPS4's conflict resolution strategies,
`the special case strategy, and so this
`strategy needs to be understood. Given two instantiations. one of which
`
`5The term ‘pattern-match‘ (rather than ‘match‘) is used here to avoid confusion with the ‘Match
`.' method‘ (Section 2.3) which is the problem solving method R1 uses in performing the configuration
`
`‘For example, a rule that bears on configuring some particular type of component will have more
`j than one instantiation if more than one such component is available; any of these instantiations
`could be executed. Or if R! is filling a cabinet, it might make no difference which part of the
`cabinet is filled first.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 7 of 34
`
`FORD 1211
`
`

`
`
`
`46
`
`J. MCDERMOTT
`
`
`
`
`contains a proper superset of the data elements contained by the other, OPS4
`will select the instantiation containing more data elements on the assumption
`that it is specialized for the particular situation at hand. OPS4’s cycle time,
`though it is essentially independent of the size of both production memory and
`working memory [6], depends on particular features of the production system
`(e.g., the number and complexity of the conditions in each production). The
`average cycle time for OPS4 interpreting R1 is about 150 milliseconds.7
`R1 currently has 772 rules that enable it to perform the configuration task.
`An English translation of a sample rule is shown in Fig. 2.1. The first condition
`indicates that the subtask in which this rule is relevant is the distributing of
`massbus devices among massbuses. The other five conditions specify one of the
`sets of constraints that must be satisfied within this subtask in order for a disk
`drive to be assigned to a massbus. When an instantiation of this rule is
`executed, one of the single port disk drives on the order is assigned to one of
`the massbuses.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`To provide R] with access to information about each component that can
`
`
`appear on -an order, production memory and working memory have been
`
`
`augmented, for this application, with a third memory. This memory, the data
`
`
`base, contains descriptions of each of the 420 components currently supported -
`
`
`for the VAX. Each entry in the data base consists of the name of a component
`
`
`and a set of attribute/value pairs that indicate the properties of that component
`
`
`that are relevant for the configuration task. Every component has a type
`
`
`attribute and a class attribute; the class of a component determines what other
`
`
`attributes are relevant. There are 15 classes: bundle, cabinet, sbi module, sbi
`
`
`‘ "device, box, backplane, massbus device, unibus device, unibus module, panel,
`
`
`power supply, software, cable, document, and accessory. Each ‘component
`
`
`description consists, on the averagefof eight attribute/value pairs; there are
`
`
`only about 50 distinct attributes, several of which are common to all (or most)
`
`
`the entries in the data base. The
`of
`the classes. Fig. 2.2 shows two of
`
`
`RK'/ll-EA is a bundle of components; it contains a 25 foot cable (7042292-
`
`
`25), a disk drive (RK07-EA*), and a bundle of components (RK6I1) which
`
`
`itself consists of
`three continuity boards (G727), a unibus jumper cable
`
`
`(M9202). a backplane (70—l24l2-O0), and a disk drive controller (RK6l1*). The
`
`
`RK6ll* is a disk drive controller which, because of its interrupt priority and
`
`
`transfer rate, is typically located toward the front of the unibus. The module is
`
`
`comprised of five hex boards each of which start in lateral position ‘A’; it draws .
`
`
`l5.0 amps of +5 volt current, 0.175 amps of -15 volt current, and 0.4 amps of
`
`
`.+15 volt. current,and-it«generates<l -un-ibus—load.—~It can support up to eight disk
`
`
`drives and is connected to the first of these with a 70-12292 cable of some
`
`
`length.
`
`
`
`
`7OPS4 is implemented in MACLISP; R1 is run on a PD?-10 (model KL) and loads in 412 pages
`of core.
`
`
`
`Page 8 of 34
`
`FORD 1211
`
`

`
`
`
`
`
`
`
`{R A RULE-BASED CONFIGURER OF COMPUTER SYSTEMS
`
`DISTRIBUTE*M8~DEVICES-3
`IF: THE MOST CURRENT ACTIVE CONTEXT IS DISTRIBUTING MASSBUS DEVICES
`AND THERE IS A SINGLE PORT DISK DRIVE
`THAT HAS NOT BEEN ASSIGNED TO A MASSBUS
`AND THER£ ARE NO UNASSIGNED DUAL PORT DISK DRIVES
`AND THE NUMBER OF DEVICES TBAT EACH MASSBUS SHOULD SUPPORT IS KNOWN
`AND THERE IS A MASSSUS THAT HAS BEEN ASSIGNED AT LEAST ONE DISK DRIVE
`AND THAT SHOULD SUPPORT ADDITIONAL DISK DRIVES
`AND THE TYPE OF CABL£ NEEDED TO CONNECT THE DISK DRIVE
`TO THE PREVIOUS DEVICE ON THE MASSBUS IS KNOWN
`THEN: ASSIGR THE DISK DRIVE TO THE MASSBUS
`
`
`
`
`
`Fio. 2.1. A sample rule.
`
`
`
`
`
`
`
`In addition to containing descriptions of VAX components, the data base
`also contains a few cabinet templates. A cabinet template describes what space
`is available in a particular cabinet type. These templates serve two purposes:
`(1) they enable R1 to know, at any point in the configuration process, what
`container space is still available, and (2) they enable R1 to assign a specific
`location (i.e., coordinates) to each component that it places in a cabinet. Fig.
`2.3 shows the template for the cpu cabinet. The components that may be
`ordered for the cpu cabinet are sbi modules, power supplies, and an sbi device.
`The template for the cpu cabinet contains descriptions of the space available
`for each of these Classes of components and specifies what can be put where.
`For example, up to six sbi modules fit into a cpu cabinet; each cabinet contains
`’ a cpu module and some memory; in addition there are three ‘slots’ for options
`that occupy 4 inches of space and one slot for an option that occupies 3 inches
`of space. The description ‘cpu nexus—2 (3 5 23 30)’
`indicates that the cpu
`module must be associated with nexus 2 of the sbi; the numbers in parentheses
`indicate the top left and bottom right coordinates of the space that can be
`occupied by a cpu module.
`Initially, working memory is empty. It grows, during the course of configur-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CLASS: BUNDLE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`COMPONENT LIST:
`
`1 070—1229Z~Z5
`1 RK07-EA‘
`I RK611
`
`
`
`CLASS: UHIBUS MODULE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`PRIORITY LEVEL: BUFFERED NPR
`TRANSFER RATE: 212
`uunasa or SYST£M UNITS:
`2
`SLOTS REQUIRED:
`e RK611 (4 10 9)
`sonno LIST:
`(HEX A M7904)
`(HEX A M7903)
`DC POWER DRAWN: 15.0 .175 ,4
`unxsus LOAD: 1
`NUMBER or UNIBUS DEVICES surponrso: 8
`CABLE rvps REQUIRED:
`2 o7o—1229z FROM A DISK DRIVE UNIBUS D{VICE
`
`(HEX A M7902)
`
`(HEX A M7901)
`
`Fig. 2.2. Two component descriptions.
`
`
`
`(HEX A M7900)
`
`
`
`
`
`
`
`
`
`
`Page 9 of 34
`
`FORD 1211
`
`

`
`
`
`443
`
`J. h4cI)I3Ilh4()17T
`
`cru-cauruzr
`CLASS: casrutr
`HEIGfiT: 60 INCHES
`uronn 52 xucues
`urprn: an inches
`551 HODULE SPACE: cpu nexus-2 (3 5 23 so)
`4~1flCH-OPTION-SLOT 1 nexus-3 (23 5 27 av)
`msnonv uExus~4 (27 5 as an)
`4-INCH-OPTION-SLOY 2 NEXUS—5
`(33 5 42 an)
`4—Iucn-oPrron—sLor 3 NEXUS-5 (42 5 46 an)
`3-rncn~orrrou-stor u£xus~5 (as 5 49 30)
`POWER SUPPLY SPACE:
`rpa uzxus—1 (2 32 10 40)
`cvu NEXUS—2
`(10 32 19 40)
`4~INCR-OPTION—SLOT 1 NEXUS-3 (15 32 as an)
`MEMORY nExus~4 (25 32 34 40)
`4-INCH-OPTION-SLUT 2 NEXUS—5
`(34 32 42 an)
`CLOCK—aATTERY (2 49 26 52)
`MEMORY-BATTERY (2 45 25 49)
`IO (2 52 so as)
`
`sar DEVICE SPACE:
`
`
`
`FIG. 2.3. A sample template.
`
`ing a system, to contain descriptions of the components ordered, and as various
`components are associated, to contain descriptions of partial configurations as
`well as other component information i‘eq’Liired to do the configuration task. A
`component
`is represented in working memory as a c0mponent—t0ken with
`associated attribute/value pairs. R1 retrieves information from the data base as
`the need for such information arises. There are live actions that Rt can
`perform that provide it access to the data base. Three of these functions,
`generaIe—t0kens, find-token, and find-substitute-token,
`retrieve specified in
`formation about a component (or list of components) from the data base,
`create a component-token, and then add a partial description of the component
`to working memory. The other two, get-attributes and get-template, augment
`the description of an already existing component—token.
`In addition to containing component descriptions, working memory contains
`three other types of elements:
`- Elements that define partial configurations.
`~ Elements that indicate the results of various sorts of computations.
`— Context symbols.
`An element that defines a partial configuration contains a description of the
`relationships among two or more components. Typically, these elements in-
`dicate either that one component is to be connected to another by means of a
`cable or, in the case of a component that is a container, the spatial relationship
`between the container and each of the components it contains, An element that
`indicates the result of some computation contains a symbol
`identifying the
`’computation and one or more values indicating the ‘result. The component
`descriptions, together with the elements that define partial configurations and
`the elements that indicate the results of various computations, constitute what I
`referred to above as component information. A context symbol contains a
`context (subtask) name and an indication of whether or not the context is
`active.
`
`
`
`‘I
`
`l.4.
`'1.
`
`,1‘ 3I
`
`Page 10 of 34
`
`FORD 1211
`
`

`
`
`
` iii; A RULEBASED CONFIGURER OF COMPUTER SYSTEMS
` 2.2. Contexts
`
`The configuration task can be viewed as a hierarchy of subtasks that have
`strong temporal interdependencies. The actions required within each subtask
`are highly variable; they depend completely on the particular combination of
`components that appear on an order and the way in which sets of those
`_ components have been configured up to the point when the new subtask
`becomes appropriate. It is possible, however, to indicate what actions (includ
`ing the action of initiating a new subtask) are appropriate within a subtask in
`terms of a relatively small number of rules that are each sensitive to a few
`salient features of the current situation.
`
`Rl’s approach to exploiting the temporal relationships among subtasks is
`straightforward. The function of several of Rl’s rules is to recognize, on the
`basis of the component information in working memory, when a new subtask
`‘should be initiated. When one of these rules fires, it adds a context symbol to
`working memory. Each context symbol contains a context name, an indication
`of whether the context is active or not—active, and an indication of when (i.e.,
`how recently) the context was made active. Each rule contains two condition
`elements that are sensitive to context symbols. Together these conditions
`insure that only those rules that bear on the most current active context will
`fire. Which of these rules fires depends on what descriptions of components,
`partial configurations, and computational
`results‘ are in working memory.
`Typically, a few of the rules associated with a context contain the constraint
`knowledge ordinarily relevant within that context. Other rules associated with
`the context are special case rules;
`these rules, when their more stringent
`conditions are satisfied, fire before (and often instead of) the ordinary case
`rules. Each context has an associated rule containing only the two condition
`elements sensitive to a context symbol. This rule deactivates the current
`context. Since each deactivation rule is a general case of all ‘he other rules
`. sensitive to its context, it fires only after the other satisfied rules have fired. Rl,
`then, isa r_ecognition—driven‘system that relies’ on its knowledge of the'structu're"""'
`of the configuration task as well as on information about the set of components
`it is configuring to determine what to do. When it has several courses of action
`Open to it, it falls back on general (non—task-specific) strategies for selecting
`among alternatives. But it needs only two such strategies: (1) it uses special
`Case rules in preference to more general ones, and (2) it does all that it can
`within a context before leaving that context.
`The contexts that R1‘ makes use of in order to do the configuration task were
`not arrived at through a rigorous analysis of the demands of the configuration
`task. Rather, they reflect the way in which human experts who do the task
`actually approach it. As might be expected, as R1 evolved it became apparent
`that some modifications and reordering of
`the co