PLAWrightDoc.tioga
Copyright © 1984 by Xerox Corporation. All rights reserved.
Created by: Don Curry, September 20, 1984 11:38:52 am PDT
Last Edited by: Curry, September 24, 1984 10:49:47 am PDT
PLAWright
Don Curry (September 22, 1984)
Filed on: /Indigo/Dragon/PLAWright/PLAWrightDoc.tioga
© Copyright 1984 Xerox Corporation. All rights reserved.
Abstract: PLAWright is a program that tries to derive the smallest set of product terms which is sufficient to implement a mulitiple output boolean function specified as a sum of products. More specifically, it is used to reduce the size of programmed logic arrays (PLAs). Input and output are both in the form of truth table files (.tt). Options allow processing of subsets of the output variables.
XEROX Xerox Corporation
Palo Alto Research Center
3333 Coyote Hill Road
Palo Alto, California 94304
For Internal Xerox Use Only
PLAWright Overview
PLAWright reduces an input truth table file and produces one or more output truth table files and an updated log file. Computing a minimal set of covering product terms has two parts. During the first, the complete sum of all prime implicants is generated from the definition. This list of terms can be either larger or smaller than the definition, but it represents a set of terms guaranteed to contain a minimal set. The second part, searches the complete sum for the smallest set sufficient to cover the function. Both halves of the problem can take a great deal of time (you may be required to include instructions for the disposition of the output in your will) if you are dealing with a large and complex truth table and insist on computing an absolute minimum representation.
Switches (optional)
C,F,S - Selecting outputs (composite, field, single).
Subsets of the outputs are specified using three mutually exclusive switches and numerical modifiers. The default switch -f treats the outputs as being clumped into fields (defined in the input .tt file by inserting spaces or tabs). In the following, the input file is assumed to be PLA.tt.
-f => reduce each output field (default) producing PLA-F00.tt, PLA-F01.tt, etc.
-f[3..4] => reduce each output field in[3..4] producing PLA-F03.tt and PLA-F04.tt.
-f6 => reduce the seventh output field producing PLA-F06.tt
-s => reduce each single output producing PLA-S00.tt, PLA-S01.tt, etc.
-s[3..4] => reduce each single output in[3..4] producing PLA-S03.tt and PLA-S04.tt.
-s6 => reduce the seventh output producing PLA-S06.tt
-c => reduce composite outputs producing PLA-C00-xx.tt. (xx+1 outs total)
-c[3..4] => reduce composite outputs in[3..4] producing PLA-C03-04.tt.
-c6 => reduce output producing PLA-C06-06.tt (same as -s6).
-k"xxx" => look for key string xxx in input file before scanning
P - Partial sum
P is used to request construction of only a partial sum instead of the complete sum. It's useful for pla's that take a long time (forever) to generate complete sums. Use of this switch of course removes all guarantee's about the minimal size of the resulting reduced truth table but it can change the compute time from infinity to 30 sec and still produce good results. (observed on the Dagon IFU PLA). If you get tired of waiting the the complete sum to finish, and decide to restart with the -p switch, you might try activating the FinishCS menu button in the PLAWright Trace viewer first. It will try to finish using the same algorithm as the -p switch except that you will be starting with a (presumably) larger set of terms.
T - Set Minimization Timeout
T is used to specify a minimization timeout. Typically, a very good set of terms will be found quickly after minimization is begun. Including -t10 in the command line for intance tells the minimizer to accept the current best set if there has not been an improvement in the last 10 minutes. Since the timeout procedure may be a bit slow in getting control and it takes a while to unwind, the specified time represets a lower bound on the delay. Be patient. This option is best used when you are running overnite doing multiple pla's (-s or -f switches). The timeout can be forced interactively with the FinishMin menu button in the PLAWright Trace viewer.
Truth Table (.tt) format
For the purposes of this program (we should expand this to add symbol information), a .tt file is a text file containing one or more sequences of terms somewhere in it (each sequence represents a different PLA). A term is recognized by the scanner as a line whose first character is a `0',` 1' or `-'. Terms are made up of an input part, the vertial bar character `|' and an output part followed by a carrage return. The input and output parts contain only the characters `0', `1', space or tab. The input part may also contain the dont-care character `-'.
(Actually the dont-care character may also be `.' or `x') The spaces and tabs are optional and can be used to group together fields in the inputs and outputs. The number of inputs and outputs must of course be identical within each sequence of terms. For example, SomeFile.tt might contain:
some text
00 01 10001010 | 100 111110 0
11 01 -------- | 100 001110 1
1- 11 11101010 | 010 111001 0
11 -- 10001010 | 10- 110000 1
01 01 10110100 | 110 011110 0
more text
Examples
PLAWright SomePLA.tt
This will produce an updated log file SomePLA.log as well as:
SomePLA-F00.tt (12 inputs 3 outputs)
SomePLA-F01.tt (12 inputs 6 outputs)
SomePLA-F02.tt (12 inputs 1 outputs)
PLAWright -c SomePLA.tt
This will produce an updated log file SomePLA.log as well as:
SomePLA-C00-09.tt (12 inputs 10 outputs)
PLAWright -c(2..6) SomePLA.tt
This will produce an updated log file SomePLA.log as well as:
SomePLA-C03-05.tt (12 inputs 3 outputs)
PLAWright -s[1..4) -p SomePLA.tt
This will produce an updated log file SomePLA.log as well as:
SomePLA-S01.tt (12 inputs 1 outputs) not necessarily optimal
SomePLA-S02.tt (12 inputs 1 outputs) not necessarily optimal
SomePLA-S03.tt (12 inputs 1 outputs) not necessarily optimal
Result files
Each result file has a bit out the information which appeared in the log file as well as the best sum found in truth table format.
Notes
Some care has been taken to reduce the allocation requirements so that PLAWright may be reasonably expected to run for a long time (weekend, week?) without running out of VM. Preliminary experience indicates that good (best) minimums are achieved rather quickly and aborting the search say 10 minutes after the last minimum was found does not seem to cost much.