DNC-FILE copy
`
`oh
`
`.
`
`oe eS
`ar
`eea ee .FE ay ot
`
`PY
`
`soar(Y
`
`R1: A RULE-BASED CONFIGURER
`
`
`
`
`
`
`
`April, 1980
`
`-
`
`OF COMPUTER SYSTEMS
`
`John McDermott
`
` AD-A223957
`
`DEPARTMENT
`
`of
`
`COMPUTER SCIENCE
`
`pee
`
`ELECTE §
`
`sp Ca
`Yan
`
`ray
`
`DISTRIBUTION STATEMENT
`Appraved im public release;
`Distriswtion Unlimited
`
`
` —_—_—_.__., Stinegy
`Carnegie-WViellon University
`
`oo o7 16 150
`
`COMFIGIT 1029
`
`CONFIGIT 1029
`
`1
`
`

`

`
`
`CMU-CS-80-119
`
`
`
`
`oO
`
`
`
`R1: A RULE-BASED CONFIGURER
`
`
`| Accessfon For
`NTIS) GhA&I
`
`Drie T4838
`
`Unannewnced
`1 Juntitiestio
`
`OF COMPUTER SYSTEMS
`
`John McDermott
`
`\
`
`April, 1980
`
`
`
`Abstract, R1 is a program. that configures VAX-11/780 computer systems. Given a customer's
`order, it determines what,if any, modifications have to be madeto the order for reasons of system
`functionality and produces a numberof diagrams showing how the various components on the order
`are to be associated. The program is currently being used on a reqular basis by Digital Equipment
`Corporation’s manufacturing organization. R1 is implemented as a production system.
`It has
`sufficient knowledge of the configuration domain and of the peculiarities of the various configuration
`constraints that at each step in the configuration process,
`it simply recognizes what
`to do.
`
`Consequently,little search is required in order forit to configure a computer system. er )
`
`APPROVED FOR PUELIC RELEASE
`DISTRIBUTION UNLIMITED
`
`The development of R1 was supported by Digital Equipment Corporation. The research that led to the
`development of OPS4, the language in which R1 is written, was sponsored by the Defense Advanced Research
`Projects Agency (DOD), ARPA Order No. 3597, and monitored by the Air Force Avionics Laboratory under
`Contract F33615-78-C-1151. The views and conclusions contained in this document are those of the author and
`should not be interpreted as representing the official policies, either expressed or implied, of Digital Equipment
`Corporation, the Defense Advanced Research Projects Agency, or the U.S. Government. VAX, PDP-11, UNIBUS,
`and MASSBUS are trademarks of Digital Equipment Corporation.
`
`>
`
`2
`
`

`

`
`
`INTRODUCTION
`R1' is a rule-based system that has much in commonwith other domain-specific systems that have
`been developed over the past several years [Amarel 77, Waterman 78].
`It differs from these systems
`
`primarily in its use of Match rather than Generate-and-test as its central problem solving method;
`rather than exploring several hypotheses until an acceptable oneis found,it exploits its knowledge of
`its task domain to generate a single acceptable solution. R1's particular area of expertise is the
`
`configuring of Digital Equipment Corporation's VAX-11/780 systems.
`
`Its input is a customer's order
`
`and its output is a set of diagramsdisplaying the spatial relationships among the components on the
`order; these diagrams are used by the technician who physically assembles the system.” Two
`inter-dependentactivities must be performed in configuring a VAX system.
`
`e The customer's order must be determined to be complete;
`componentsare missing must be added to the order.
`
`if
`
`it
`
`is not, whatever
`
`e The spatial relationships amongall 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 aboutall the individual components andtheir 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, the task accomplishmentis defined by a large set of constraints embodying a large amount of
`
`knowledge.
`
`Although a significant portion of this paper is devoted to a description of precisely how R1 goes
`
`| have tried to avoid letting the details of R1's inner workings
`about doing the configuration task,
`overshadow the domain independent lessons that have emerged from this research. There are two
`
`important lessons:
`
`Recognition knowledge can be used to drive an expert system's behavior, provided thatit
`is possible to determinelocally (ie. at each step) whether taking some particularactionis
`consistent with acceptable performance on the task.
`
`« When an expert system is implemented as a production system, the job of refining and
`extending the system's knowledgeis quite easy.
`
`The paperis divided into three sections. Thefirst section describes the VAX-11/780 configuration
`
`task and characterizesits difficulty. The second section describes R1 and discussesits evolution
`
`Veour years ago | couldn't even say "knowledge engineer", now |...
`2p 1's outpul for a sample order is shown in Appendix 2,
`
`
`
`
`
`3
`
`

`

`
`
`from a system with only the mostlimited capabilities to what might fairly be called, a true expert. Tha
`
`third section describes R1’s currentlevel of expertise and isolates the design decisions that made the
`
`building of R1 straightforward.
`
`1. THE TASK
`
`implementation of Digital Equipment Corporation's VAX-11
`the first
`The VAX-11/780 is
`architecture. {tis similar in many respects to the PDP-11, though its virtual address spaceis 232
`rather than 2'®, The VAX-11/780 uses a high speed synchronousbus, called the sbi (synchronous
`backplane interconnect), as its primary interconnect. The central processor, one or two memory
`
`control units, one to four massbus interfaces, and one to four unibus interfaces can be connected to
`
`the sbi. The massbuses and particularly the unibuseés can support a wide variety of peripheral
`
`devices. Because the number of system variations is so large, the VAX configuration task is
`
`non-trivial.
`
`1.1. THE SIZE OF THE TASK
`
`A configurer must have two sorts of knowledge. First, he must have information about each of the
`
`components that a customer might order. For each component, the configurer must know the
`
`properties that are relevant to system configuration -- eg, its voltage, its frequency, how many devices
`
`it can support (if it is a controller), how many ports it has; | will call this knowledge component
`
`information. Second, he must have rules that enable him to associate components to form partial
`
`configurations and to associate partial configurations to form a functionally acceptable system
`
`configuration. These rules must indicate what components can (or must) be associated and what
`
`constraints must be satisfied in order for these associations to be acceptable;
`
`| will call
`
`this
`
`knowledge constraint knowledge.
`
`The difficulty of the VAX configuration task is a function of the amount of componentinformation
`
`and the amountof constraint knowledge required to perform the task.
`
`It is fairly easy to estimate the
`
`amount of componentinformation that is needed. On the average, a configurer must know eight
`
`properties of a componentin order to be able to configure it appropriately. Currently about 420
`components are supported for the VAX.? Thusthere are over 3300 pieces of componentinformation
`that a VAX configurer must have access to.
`
`Before R1 was developed,
`
`it would have been difficult to estimate accurately the amount of
`
`constraint knowledge required for the configuration task. Much of the required knowledge was not
`
`Soy the 420 components, about 180 are actually bundles composed of various subsets of the remaining 240
`components,
`
`
`
`4
`
`

`

`
`
`written down anywhere and thus the only source of estimates would have been individual human
`
`experts. But the experts find the task of quantifying their constraint knowledge foreign. As | extracted
`
`this knowledge from them,it becameclearthat their knowledge takes two 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 the subtasks involved and the various temporal relationships among these
`
`(2) They also have a considerable amount of very detailed knowledge that indicates the
`subtasks.
`features that particular partial configurations and unconfigured components must havein order for
`
`the partial configurations to be extended in particular ways. Both sorts of knowledge are easily
`
`expressable as rules.
`
`| extracted 480 rules. Of these, 96 define situations in which some subtask
`
`should beinitiated. The other 384 rules define situations in which somepartial configuration should
`
`be extended in some way.
`
`1.2. THE CONSTRAINTS
`
`This subsection provides two examples of specific subtasks that can arise within the configuration
`
`task and indicates for each (1) the constraint knowledge involved, (2) the informational demands
`
`imposed by that constraint knowledge, and (3) the extent to which the subtask presupposes other
`
`subtasks. The first subtask is to place unibus modules into backplanes; the second is to assign
`massbus devices to massbuses.
`
`Example: Placing unibus modules in backplanes. Whenever more than one unibusoption is
`
`ordered for a VAX, itis necessary to place the modules on the unibus in an acceptable sequence. Itis
`
`straightforward to determine the optimal sequence for the modules; the modules are sorted on the
`
`basis oj their interrupt priority and within that on the basis of their transfer rate. Before a module can
`
`be placed on the unibus,it is necessary to select a backplane. Several constraints come into play.
`
`Backplanes comein twosizes (4-slot and 9-slot) and can have any of several pinning types. The
`backplane selected must beofthe pinning type required by the unibus module. To determine the size
`of the backplaneto be selected, it is necessary, first, to determine whetherthe size is constrained by
`
`the box that the backplane will be placed in. A box can accommodatefive 4-slot backplanes.
`
`In most
`
`cases a 9-slot backpane may beusedin place of two 4-slot backplanes; the exceptionis that a 9-slot
`backplane may not occupythe spacereserved for the second andthird 4-slot backplanes,* Assuming
`that either a 4-slot or a 9-slot backplane would be acceptable, the next constraint to comeinto playis
`
`that a 9-slot backplane should not be selected unless the next N modulesin the optimal sequenceall
`
`require a backplane of the same type andwill not all fit in a 4-slot backplane. Once a backplaneis
`
`“The box that contains unibus modules has two +5 voli regulators. Cne of these regulators supplies power to
`the first two 4-slot backplanes (or to the first 9-slet backplane);
`the second supplies power to the other
`backplanes. Allof the modules ina backplane must draw power from the same requlator.
`
`
`
`5
`
`

`

`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 accomodateafull 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 confiqurer must decide whether to deviate from
`
`the optimal sequenceor 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 sufficient 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
`
`sequencesthat 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 crder; if the decision is that an acceptable suboptimal sequence can be found, then some
`
`module other than the next one in the optimal sequenceis placed in the backplane.
`
`In general, it is
`
`acceptable to add a module thatis not next in the optimal sequenceif it meets all of the constraints
`
`mentioned above and has a transfer rate that is lower than that of any other module with the same
`
`interrupt priority thatit will precede.
`
`There are reasons, other than lack of slot space or power, why the configurer must consider
`
`deviating from the optimal sequence.
`
`If ihe 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 sufficient 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 putall of the remaining modulesin the remaining cabinets. Again, the decision
`
`must be made on the 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 the task presupposes other tasks. The
`
`componentinformation that the rules require is, for a module, the module type, the numberandsize 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
`
`
`
`6
`
`

`

`the pinning type, the size, the power drawn by the modules that have been placed init, and the slots
`
`still available. For a box, the information is the box type, the amount of backplane spacestill 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 mentioned: determining the optimal sequence, selecting a backplane, assigning
`
`the backplane 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 sufficient panel space in the cabinet. There
`
`are several others:
`
`the unibus adaptors have to have been configured (so unibus length can be
`
`computed); boxes have to have been assigned to cabinets and also to unibuscs (so unibus length can
`
`be computed and so the amountof 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 sufficient panel
`
`spacein the cabinet and sufficient space and powerin the box for the backplane thatwill contain the
`
`laboratory peripheral options.
`
`Example: Assigning massbus devices to massbuses. Whenever an order contains massbus
`
`devices, those devices must be assigned to massbuses. There are a numberofrules that constrain
`
`how these assignments can be made: Up to eight disk drives and master tape drives can be assigned
`
`to each massbus.
`
`|f there are enough massbuses so that disk drives and tape drives can be assigned
`
`to separate massbuses,that should be done.
`
`If not, the order of assignment should be such that the
`
`disk drives precede the tape drives on the massbus containing both types of devices (even thoughin
`
`the spatial layout, some of the tape drives will be closer to the cpu cabinet-- and thus to the massbus
`
`adaptor-- than will the disk drives), Unless there are more massbus adaptors than massbus devices,
`
`each massbus should be assigned at least one massbus device. Disk drives are either single port or
`
`dual port; each dual port disk drive must be assigned to two massbuses. Dual port disk drives should
`
`precede single port disk drives on the massbus. Up to seven slave tape drives can be assigned to
`
`each master tape drive.
`
`If the ratio of slave tape drives to master tape drives on an order is greater
`
`than 7 to 1, a formatter must be added to one of the slave tape drives to make it a master.
`
`If the number of massbus adaptors on the order is too few to accommodate the disk drives and
`
`tape drives, then additional massbus adaptors must be added to the order. To determine whetherall
`
`of the massbus devices can be configured,
`
`it
`
`is necessary to determine whether the numberof
`
`adaptors exceeds the number permitted. Up to four massbus adaptors are permitted.
`
`If the total
`
`numberof unibus adaptors and massbus adaptors on the orderis greater than three, a cpu expansion
`
`cabinet is required.
`
`If the total number of unibus adaptors and massbus adaptors is greater than
`
`seven and there is only one memory controller on the order, a second cpu expansion cabinet is
`
`required.
`
`If the total number of unibus adaptors and massbus adaptorsis greater thanfive and there
`
`7
`
`

`

`
`
`are two memory controllers, a second cpu expansion cabinetis required.
`
`The componentinformation required by the rules is the type of each massbus device (disk drive,
`
`master tape drive, or slave tape drive), the number of ports (for disk drives), the number of devices
`
`assigned to each massbus and the type of each device assigned, the numberof slave tape drives
`
`assigned to each master, and the space available for massbus adaptors in the cpu and cpu expansion
`
`cabinets. The task of assigning slaves to masters must be done before either disk drives or master
`
`tape drives are assigned so that the number of massbus adaptors required and the distribution of
`
`devices among massbuses can be determined. The tasks of assigning memory and unibus adaptors
`
`to the cpu and cpu expansion cabinets must be done before the massbus devices are assigned in
`
`order to determine whether the number of massbus devices exceeds the maximum permitted and to
`
`determine whether additional cabinet space will be required.
`
`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 efficiently and can easily acquire
`
`additional knowledge about the domain. The architecture in which R1 is embedded is described.
`
`Issues of search are discussed. The content and use of R1'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.1. THE PRODUCTION SYSTEM ARCHITECTURE
`
`Ri is implemented as a production system [Newell 77]. The particular production system language
`used is OPS4. Since detailed descriptions of this language have been provided elsewhere {[Forgy
`79, Forgy 77, McDermott 78], 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 (eg, state descriptions) held in working memory. A production is a
`
`conditional statement composed of conditions and actions; a production has the form:
`
`Pr Wy Co.
`
`sons ByAg Ag, ate Alal
`
`Actions typically modify working memory by deleting, adding, or modifying a data element; users may,
`
`however, define application specific actions. Conditions are templates; 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 a production and a set of elements from working
`
`memory that satisty the conditions of the production. The OPS4 interpreter operates within a control
`
`framework called the recognize-act cycle. During the recognition part of the cycle,
`
`it finds the
`
`instantiation to be executed; during the act part, it performs the actions, The recognize-act cycle is
`
`8
`
`

`

`
`
`repeated until either no production can be instantiated or an action explicitly stops the processing.
`
`Recognition can be divided into match and conflict resojution. During match, the interpreter finds the
`
`set of all instantiations of productions that are satisfied on the current cycle. During conflict
`
`resolution, it determines whichinstantiation to execute.
`
`Each of R1's productions (rules) embodies a piece of constraint knowledge. The production's
`
`conditions typically look for situations in which a particular type of extension to a particular type of
`
`partial configuration is permissable or required; the actions then effect that extension. R1's rules are
`
`such that on almost every cycle several rules can be instantiated -- often in a numberofdifferent
`
`ways. From R1's point of view,it often makes no difference which of these instantiations is executed;
`in these cases, haw OPS4 determines whichinstantiation to executeis irrelevant.> R1 does, however,
`
`rely heavily on one of OPS4's conflict resolution strategies, the specia/ case strategy, and so this
`
`strategy needs to be understocd. Given twoinstantiations, one of which contains a proper superset
`
`of the data elements contained by the other, OPS4will select the instantiation containing more data
`
`elements on the assumption thatit is specialized for the particular situation at hand. OPS4’s cycle
`
`time, though it is essentially independentof the size of both production memory and working memory
`
`[Forgy 80], depends on particular features of the production system (eg, the number and complexity
`of the conditions and actions in each production). The average cycle time for OPS4 interpreting Rit is
`about 150 milliseconds.®
`
`As wesaw in the previous section, there is a considerable amount of information which has to be
`
`known about each component that can appear on an order. To provide R1 with access to this
`
`information, OPS4’s two memories 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 fype attribute and a class attribute; the class of a
`
`component determines whatother 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
`
`average,of eightattribute/value pairs; there are only about 50 distinctattributes, several of which are
`
`commonto all (or most) of the classes, Figure 2-1 showsfive of the entries in the data base. The
`
`RK711-EA is a bundle of components;
`
`it contains a 25 foot cable (70-12292-25), a disk drive
`
`Seo, example, a rule that bears on configuring some particular type of component will have more than one
`instantiation if more than one such component is available; any of these instantiations could be executed. Or if
`Al is filling a cabinel, it might make no difference which parl of (he cabinet is filled first.
`5opsa is implemented in MACLISP: A1 is run ona PDP-10 (model KL) and loads in 412 pages of core.
`
`
`
`9
`
`

`

`RK711-EA
`CLASS: BUNDLE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`COMPONENT LIST: 1 070-12292-26
`1 RKO7-EA*
`1 RK611
`
`RKO7-EA®
`CLASS: UWIBUS DEVICE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`FLOOR RANK: 8
`OEPTH: 28 INCHES
`WIDTH: 24 ere
`HEIGHT: 42 INCHES
`UNIBUS MODULE REQUIRED: AKO11*
`PORTS: 1
`VOLTAGE? 120 VOLTS
`FREQUENCY: 60 HERTZ
`CABLE TYPE REQUIRED:
`
`1 070-12292 FROM A DISK DRIVE UNIBUS MODULE
`OR 1070-12292 FROM A DISK DAIVE UNIBUS DEVICE
`
`RKO11
`CLASS: BUNDLE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`COMPOWENT LIST: 3 G727
`1 M9202
`1 070~12412-00
`1 AK6iLe
`
`070-12412-00
`CLASS: BACKPLANE
`TYPE: RK611
`SUPPORTED: YES
`NUMBER OF SYSTEM UNITS: 2
`LENGTH: 2.0 FEET
`NUMBER OF SLOTS: 9
`SLOT TYPES: 3 src{1 TO 3)
`6 RK6i1 (4 TO 9)
`
`Figure 2-1:
`
`Somerepresentative items from the data base
`
`twofeet; its first three slots are for boards that require spc (small peripheral controller) pinning, and
`
`(RKO7-EA*), and a bundle of components (RK611) which itself consists of three continuity boards
`(G727), a unibus jumper cable (M9202), a backplane (70-12412-00), and a disk drive controller
`(RK611*). The RKO7-EA’ is a single port disk drive; it is a unibus device that requires an RK611* as
`its controller, and it is connected to that controller either directly or via another disk drive with a
`70-12292 cable of some length. The 70-12412-00 is a 9-slot backplane whose “electrical length" is
`
`RK611°
`CLASS: UNIBUS MODULE
`TYPE: DISK DRIVE
`SUPPORTED: YES
`PRIORITY LEVEL: BUFFERED NPR
`TRANSFER RATE: 212
`WUMBER OF SYSTEM UNITS: 2
`SLOTS REQUIRED: 6 RK61i (4 TO 9)
`BOARD LIST:
`(HEX A M7904)
`(HEX A M7903)
`DC POWER DRAWN: 16.0 .176 .4
`UNIBUS LOAD: 4
`NUMBER OF UNIBUS DEVICES SUPPORTED: 4
`CABLE TYPE REQUIRED: 1070-12292 FROM A DISK DRIVE UMIBUS DEVICE
`
`(MEX A M7902)
`
`(HEX A M7901)
`
`(HEX A M7900)
`
`10
`
`

`

`
`
`the remaining six slots are for the RK611", The RK611* is adisk drive controller which, becauseofits
`
`interrupt priority and tia.isfer rate, is typically located toward the front of the unibus. The module is
`
`comprised of five licx boards each of whichstart in lateral position "A"; it draws 15.0 amps of +5 volt
`
`current, .175 amps of -15 volt current, and .4 amps of +15 volt current, and it generates 1 unibus
`
`load.
`
`li can support up to eight disk drives and is connected to thefirst of these with a 70-12292 cable
`
`of somelength.
`
`In addition to containing descriptions of VAX components, the data base also contains a few
`
`cabinet templates. A cabinet template describes what spaceis 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 spaceis still available, and (2) they enable R1 to assign a specific location
`
`(ie, coordinates) to each componentthatit places in a cabinet. Figure 2-2 showsthe templates for the
`
`cpu and unibus expansion cabinets. The components that may be ordered for the cpu cabinetare 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 numbersin parentheses
`
`indicate the top left and bottom right coordinates of the space that can be occupied by a cpu module.
`
`The components that may be ordered for the unibus expansion cabinet are boxes and panels. Note
`
`that multiplexer panels and (half-size) laboratory peripheral panels occupy the same space; one piece
`
`ol R1's constraint knowledgeis that two panels cannot occupy the same spaceat the sametime.
`
`Initially, working memory is empty.
`
`It grows, during the course of configuring 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 required to do the
`
`configuration task. A component is represented in working memory as a component-token with
`
`associated attribute/value pairs. R1 retrieves information from the data base as the need for such
`
`information arises. There are five actions that R1 can perform that provide it access to the data base,
`
`Three of these functions, generate-tokens, find-loken, and find-substitute-token, retrieve specified
`
`information 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-ailributes
`
`and gel-template,
`
`augment
`
`the description of
`
`an
`
`already
`
`existing
`
`component-token. Generate-tokens takesa list of component names and a setof attribute names as
`
`its arguments, and returns, for each component onthelist, a component-token andthe value of each
`
`of the specified attributes. Find-token takes a partial description (a set of attribute/value pairs) and a
`
`
`
`11
`
`
`
`11
`
`

`

`10
`
`CPU-CABINET
`CLASS: CABINET
`HEIGHT: 60 INCHES
`WIDTH: 62 INCHES
`DEPTH: 30 INCHES
`SBI MODULE SPACE: CPU NEXUS-2 (3 & 23 30)
`4-INCH-OPTION-SLOT 1 NEXUS-3 (23 6 27 30)
`MEMORY NEXUS-4 (27 6 38 30)
`4-INCH-OPTION-SLOT 2 WEXUS-6 (38 6 42 30
`4-INCH-OPTION-SLOT 3 NEXUS-5 (42 6 46 30
`3-INCH-OPTION-SLOT NEXUS-6 (46 6 49 30)
`POWER SUPPLY SPACE: FPA WEXUS-1 (2 32 10 40)
`CPU NEXUS-2 (10 32 18 40)
`4-INCH-OPTION-SLOT 1 NEXUS-3 (18 32 26 40)
`MEMORY NEXUS-4 (26 32 34 40)
`4-INCH-OPTION-SLOT 2 NEXUS-5 (34 32 42 40)
`CLOCK-BATTERY (2 49 26 62)
`MEMORY-BATTERY (2 46 26 49)
`SBI DEVICE SPACE: 10 (2 52 60 66)
`
`UBX-CABINET
`CLASS: CABINET
`HEIGHT: 60 INCHES
`WIDTH: 28 INCHES
`DEPTH: 30 INCHES
`BOX SPACE: UBX 1 (2 39 26 46)
`UBX 2 (2 13 26 22)
`PANEL SPACE: MUX 1
`1 BACK (14 27 26 36)
`MUX 2 2 BACK (2 2 26 11)
`MUX 3 3 FRONT (2 27 14 36
`
`LPA 1 1 BACK (14 27 26 2)
`
`LPA 1 2 BACK (14 32 26 36
`LPA 2 3 BACK (2 2 26 6)
`LPA 2 4 BACK (2 7 26 13)
`LPA 3.5 FRONT (2 27 14 34
`LPA 3 6 FRONT (2 32 14 36
`
`Figure 2-2:
`
`Twosample templates
`
`set of attributes as its arguments,
`
`finds a component
`
`in the data base matching that partial
`
`description, and returns a component-token and the value of each of the specified attributes.
`
`Find-substitute-token takes a component name,a partial description, an exceptionlist, and a set of
`
`attribute names as its arguments, finds a component in the data base that is like the original
`
`component except thatit satisfies the partial description and may differ with respect to the attributes
`
`on the exceptionlist, and returns a new component-token and the values of the specified attributes.
`
`Get-attributes takes a component, a component-token, and a set of attribute names as its arguments
`
`and returns the values of the specified attributes. Get-template takes a template mame and a
`
`component-tokenas its arguments and returns the attribute/value pairs of that template.
`
`In addition to containing component descriptions, working memory contains three other types of
`elements:
`
`e Elements that define partial configurations.
`
`« Elements that indicate the results of various sorts of computations.
`
`12
`
`12
`
`

`

`
`
`® Context symbols.
`
`An elementthat defines a partial configuration contains a description of the relationships among two
`or more components. Typically,
`these elements indicate either that one component
`is to be
`
`connected to another by means of a cable or, in the case of a componentthat is a container, the
`
`spatial relationship between the container and each of the components it contains. An elementthat
`
`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 detine
`
`partial configurations and the elements that indicate the results of various computations, constitute
`
`the componentinformation. A context symbol contains a context (suotask) name and anindication of
`
`whetheror not the context is active.
`
`Production memory contains constraint knowledge-- all of R1's permanent knowledge about how
`
`to configure VAX systems. Ri currently has 772 rules that enable it to perform the task. An English
`translation of a sample rule is shown in Figure 2-3. The first condition indicates that the contextin
`
`whichthis rule is relevantis the distributing of massbus devices among massbuses. Theotherfive
`
`conditions specify one of the sets of constraints that mustbe satisfied within this context in order for a
`
`disk drive to be assigned to a massbus. Whenan instantiation of this rule is executed, one of the
`
`single port disk drives on the orderis assigned to one of the massbuses.
`
`DISTRIBUTE-MB-DEVICES~3
`
`IF: THE MOST CURRENT ACTIVE CONTEXT IS DISTRIBUTING MASSBUS DEVICES
`AND THERE IS A SINGLE PORT DISK DAIVE
`THAT HAS NOT BEEN ASSIGNED TO A MASSBUS
`AND THERE ARE "0 UNASSIGNED DUAL PORT DISK DRI