Patent Publication Number: US-5894581-A

Title: Method for reducing control store space in a VLSI central processor

Description:
FIELD OF THE INVENTION 
     This invention relates to computer systems and, more particularly, to efficient storage of control words required to execute instructions in a central processor. 
     BACKGROUND OF THE INVENTION 
     As faster operation of computer systems has been sought, numerous hardware/firmware features have been employed to achieve that purpose. One feature widely incorporated in central processing units (CPUs) that is directed to increasing the speed of operation is pipelining in which the various stages of execution of a series of consecutive machine level instructions are undertaken simultaneously. For example, during a given time increment, a first stage of a fourth (in order of execution) instruction may be undertaken while a second stage of a third instruction, a third stage of a second instruction and a fourth stage of a first instruction are all undertaken simultaneously. This procedure dramatically increases the speed of operation of a CPU. 
     The execution of the instructions in the repertoire of instructions of a CPU requires the coordinated sequential generation of numerous control signals, and these control signal combinations are particularly complex and diverse in a pipelined CPU. The control signals are typically derived from firmware stored in a read-only-memory (ROM). This firmware consists of stored control words, each control word representing a combination of binary signals, or bits, necessary to carry out a microstep in the execution of one or more instructions. 
     In the CPU family in which the subject invention finds exemplary use, a virtual control word set, or control program, of on the order of 4K words of 256 bits each is required to provide for all the necessary signal combinations for performing the numerous microsteps during execution of the instruction set of the CPU. This CPU family is implemented in very large scale integrated (VLSI) circuitry on several chips including an address and execution (AX) chip which incorporates the ROM containing the control word set. However, those skilled in the art will understand that, at the state of the art, a ROM of 4K by 256 bits would take up much of the room available for circuitry on a VLSI chip. Since the remainder of the AX chip is itself very complex, a ROM of this size cannot be accommodated, and this constraint presented a serious problem which was successfully addressed by the use of the present invention. Further, in combination with other innovations, a very significant additional decrease in the size of the control store ROM for the AX chip was achieved. 
     OBJECTS OF THE INVENTION 
     It is therefore a broad object of this invention to provide a control store for a CPU which is relatively small, but which is capable of storing a complete set of the control combinations necessary to specify all microsteps required to execute the full instruction repertoire of the CPU. 
     It is a more specific object of this invention to provide such a control store divided into a main rom (MROM), basic rom (BROM) an address rom (AROM), a first secondary address rom (DROM) and a second secondary address rom (EROM) and to selectively address the BROM, AROM, DROM and EROM from fields in control words stored in the MROM and to perform certain other operations on the information stored in at least the AROM which permits the further reduction of the physical size thereof. 
     SUMMARY OF THE INVENTION 
     Briefly, these and other objects of the invention are achieved by writing the firmware in virtual control words which are then reduced by allotting them to a primary control word memory and at least one secondary control word memory which is addressed by a field in the primary control word memory. A virtual set of secondary control words, or secondary nanocontrol words are each divided into a plurality of fields, and each field of each secondary virtual control word is marked as guarded or &#34;don&#39;t care&#34;. If a field is marked as &#34;don&#39;t care&#34;, the function represented by the virtual control word will perform properly no matter what the content of that field. Secondary nanocontrol word pairs are then examined to ascertain if they can be combined into a single control word. If the guarded fields in the first secondary nanocontrol word align with the &#34;don&#39;t care&#34; fields in the second secondary nanocontrol word and vice versa, the two control words can be combined into a single control word containing the contents of the guarded fields from both secondary nanocontrol words, the remaining fields, if any, remaining &#34;don&#39;t care&#34;. This process may be reiterated to determine if the combined control word can be further combined with another secondary nanocontrol word. In operation, all the functions represented by a combined control word are executed by calling for that single control word stored in the secondary control word memory. 
    
    
     DESCRIPTION OF THE DRAWING 
     The subject matter of the invention is particularly pointed out and distinctly claimed in the concluding portion of the specification. The invention, however, both as to organization and method of operation, may best be understood by reference to the following description taken in conjunction with the subjoined claims and the accompanying drawing of which: 
     FIG. 1 is a block diagram of a central processing unit in which the subject invention may be employed; 
     FIG. 2 is a simplified block diagram of the address and execution unit of the central processor shown in FIG. 1; 
     FIG. 3 is a representation of the four different modes in which control words may be stored and used in a main ROM component of the address and execution unit; 
     FIG. 4 is a representation of the virtual control word format used to write the firmware for the execution and control unit; 
     FIG. 5 is a partial block diagram of the execution and control unit illustrating the manner in which subsidiary ROMs for storing control words are addressed from the main ROM; 
     FIG. 6 is a logic diagram illustrating the functional relationship among an exemplary fraction on the control signals present in the address and instruction unit; 
     FIG. 7 is a representation of the fields present in an AROM addressed from the main ROM; 
     FIG. 8 is a flow diagram illustrating an exemplary method for practicing the subject invention; and 
     FIG. 9 is a simplified example of the application of the invention in a specific instance. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT(S) 
     Referring to FIG. 1, the Address and Execution Unit (AX unit) is a microprocessing engine the circuits of perform all address preparation and executes all instructions except decimal arithmetic, binary floating point and multiply/divide instructions. Two identical AX chips 10, 10A perform duplicate actions in 
     parallel, and the resulting AX chip outputs are constantly compared to detect 
     errors. The main functions performed by the AX unit include: 
     effective and virtual address formation; 
     memory access control; 
     security checks; 
     register change/use control; 
     execution of basic instructions, shift instructions, security instructions, character manipulation and miscellaneous instructions. 
     The cache unit 11 includes a data part of 64K bytes (16K words) and a set associative directory pall which defines the main memory location of each 64-byte (16-word) block stored in the cache data part. Physically, the cache unit is implemented in an array of ten DT chips and has directly associated with it a cache directory (CD) chip 12 and a duplicate directory (DD) chip 13. 
     The specific functions performed by the cache unit 11 include: 
     combined instruction and operand data storage; 
     instruction and operand buffering and alignment; 
     data interface with the system bus 7 (FIG. 1 ); 
     CLIMB safestore file. 
     Two copies of the cache directory information are respectively maintained in the CD and DD chips which perform different logic functions. The two directory copies allow interrogation of the cache contents from the system bus in parallel and without interference with instruction/operand access from the CPUs and also provide for error recovery. Functions performed by the CD chip 12 include: 
     cache directory for CPU accesses; 
     instruction, operand and store buffer management; 
     virtual-to-real address translation paging buffer. 
     Functions performed by the DD chip 13 include: 
     cache directory for system accesses; 
     system bus control; 
     distributed connect/interrupt management; 
     cache directory error recovery. 
     Efficient scientific calculation capability is implemented on the Floating Point (FP) coprocessor chips 15, 15A. The identical FP chips execute all binary floating point arithmetic in duplicate. These chips, operating in concert with the duplicate AX chips 10, 10A, perform scalar or vector scientific processing. 
     The FP chip 15 (duplicated by the FP chip 15A): 
     executes all binary and fixed and floating point multiply and divide 
     operations; 
     computes 12 by 72-bit partial products in one machine cycle; 
     computes eight quotient bits per divide cycle; 
     performs modulo 15 residue integrity checks. 
     Functions performed by the FP chips 15, 15A include: 
     executes all floating point mantissa arithmetic; 
     executes all exponent operations in either binary or hexadecimal format; 
     preprocesses operands and postprocesses results for multiply and divide instructions; 
     provides indicator and status control. 
     Two special purpose random access memories (FRAM 17 and XRAM 18) are incorporated into the CPU. The FRAM chip 17 is an adjunct to the FP chips 15, 15A and functions as an FP control store. The XRAM chip 18 is an adjunct to the AX chips 10, 10A and serves as a scratchpad as well as providing safestore and patch functions. 
     The CPU also employs a Clock Distribution (CK) chip 16 whose functions include: 
     clock distribution to the several chips constituting the CPU; 
     shift path control; 
     maintenance; 
     interface between an external Clock and Maintenance Unit and CPU; 
     provision of clock stop logic for error detection and recovery. 
     The DN chip 14 (in parallel with the DN chip 14A) performs the execution of decimal numeric Extended Instruction Set (EIS) instructions. It also executes Decimal-to-Binary (DTB), Binary-to-Decimal (BTD) conversion EIS instructions and Move-Numeric-Edit (MVNE) EIS instructions in conjunction with the AX chip 10. The DN chip both receives operands from memory and sends results to main memory (not shown) via the cache unit 11. 
     The AX, DN and FP chips, collectively, are sometimes referred to as the Basic Processing Unit (BPU). It was previously noted that the AX, DN and FP chips are duplicated with the duplicate units operating in parallel to obtain duplicate results which are available for integrity checking. Thus, master and slave results are obtained in the normal operation of these chips. The master results are placed onto a Master Result Bus (MRB) 20 while the slave results are placed onto a Slave Result Bus (SRB) 21. Both the master and slave results are conveyed, on the MRB and SRB respectively, to the cache unit 11. In addition, a COMTO (&#34;command to&#34;) bus 22 and a COMFROM (&#34;command from&#34;) bus 23 couple together the AX unit, the DN unit and the FP unit for certain interrelated operations. 
     Referring now to FIG. 2, the AX chip 10 of the CPU shown in FIG. 1 incorporates, by way of simplified example, an instruction register 30, a main rom or MROM 31, a micro-sequencer control word register 32, a basic rom or BROM 33, a basic operations (BOPS) control word register 34, a register file 35, an arithmetic and logic unit (ALU) 36 and a result register 37. Typically, the AX chip also includes intermediate write control (WtC) registers 38, 39 and ALU function control (FUNC) register 40. In accordance with the present invention, the AX chip also includes the subsidiary control word ROMs: AROM 41, DROM 42 and EROM 43. As will be discussed more fully below, high priority control functions 44 may be carried out directly under the influence of signals issued by the micro-sequencer control register 32. 
     Also referring briefly to FIG. 3, a given main control word, or primary nanocontrol word stored in the MROM 31, called by a corresponding opcode issued by the instruction register 30 to reside in nicro-sequencer control word register 32, may be any one of four types: basic, new systems architecture (NSA), basic operations packed (BOPS --  PK) or EIS/vector. (For certain practical reasons, the main control word is made up of two 25-bit words, MROML and MROMR, but for purposes of explaining the present invention, it may be considered a single word.) The type of main control word is defined in the two-bit mode field 50. 
     Secondary nanocontrol words stored in the EROM 43 are only used in the execution of a few special instructions relating to certain recently developed hardware. Secondary nanocontrol words stored in the DROM are used in performing certain paging operations and other address modification operations in the transfer of operand blocks into the BPU. Secondary nanocontrol words stored in the AROM contain the fundamental addressing information for operations to be performed during the addressing of operand blocks. Still referring to FIG. 3 as well as FIG. 2, the EROM address field, which appears only in the NSA mode, is indicated at 51. The DROM and AROM address fields, which appear in all modes, are indicated at 52 and 53, respectively. 
     Attention is now directed to FIGS. 4 and 5. FIG. 4 represents a virtual main rom 49. In the CPU family in which the subject invention finds exemplary use, a virtual control word set, or control program, of on the order of 4K words of 256 bits each is required to provide for all the necessary signal combinations for performing the numerous microsteps during execution of the instruction set of the CPU. As previously discussed, those skilled in the art will understand that a physical ROM of this size would take up an unacceptably large fraction of the room available for circuitry on the VLSI AX chip. As described above, in order to decrease the size of the MROM 31, the primary nanocontrol words stored therein contain address fields to the other control ROMS: AROM 41, BROM 33, DROM 42 and EROM 43. Conventional bit packing techniques may be employed to reduce the overall size of the control word ROMs, but not to the extent desired, and it is in the application of the subject invention that a further significant decrease in the required control word ROM storage is achieved. 
     When the firmware is written, it is prepared using the virtual word which, as noted, is much larger than can be physically implemented. After the firmware is defined and checked out with simulation, the control words must be compacted into a size which can be implemented. The virtual ROM bits are sorted (manually or using a suitable brief program) into groups. 
     The first group are those controls which must be fast and which are used early in the logic. These are used directly from the MROM by, for example, the blocks 38, 40, 44 shown in FIG. 2. A relatively small number of controls used in the NSA mode only are used from the EROM which, as previously noted, is addressed only from the MROM in the NSA mode. 
     The remaining control signals, all related to addressing, are used from the AROM and DROM which are themselves addressable in all modes of MROM operation, and it is in the coding of the information in these ROMs that the subject invention finds use in the exemplary system. As previously mentioned, conventional bit packing techniques may be employed to reduce the necessary size of the AROM and BROM; however, this technique did not result in a sufficient reduction in their size. It is in the subsequent steps according to the invention that this further reduction is achieved. 
     In order to reduce the size of the AROM, for example, the secondary nanocontrol words are merged into a set of nanowords which perform the desired function(s) for a given microstep along with any other function(s) which have no effect upon the microstep. According to the invention, this is achieved by merging secondary nanocontrol word pairs which have the same values in fields which both words care about or have different values if one of the words doesn&#39;t care about the given field. Whether or not a control word &#34;cares&#34; about the state of a field is determined by a field mask which is set by the microcode assembler each time a microfunction sets the state of the field. In coding the microsteps, each programmer will get the default state of each field for which no entry is made. This microstep, of course, will have been tested with these defaults in place. However, because of the merging process, these fields may be replaced by non-default values when the nano-ROM is produced if, according to the mask, the word &#34;doesn&#39;t care&#34; about the state of the field. In order to assure the proper state of the masks, a series of &#34;guard functions&#34; is provided in the assembler which allow the firmware programmer to specify the default state of those firmware fields which will have an effect upon each microstep. 
     Referring now to FIGS. 6 and 7, FIG. 6 is an exemplary control signal diagram. Those skilled in the art will understand that this diagram is one of many which, all taken together, represent all the control signals necessary to perform all the functions within the capability of the AX chip. (It may be noted that it is not necessary to understand the meaning of the various control signals to obtain a full appreciation of the subject invention, and therefore no description of the actual functions of the control signals is discussed.) FIG. 7 is a representation of the configuration of the secondary nanocontrol words stored in the AROM. 
     In FIG. 6, four types of fields are represented: 1) those which are guarded by default, 2) those which are guarded at the option of the programmer, 3) those which are guarded under predetermined conditions and 4) those for which there is no need to be guarded. For example: 
     AR --  WT --This control signal, represented by the block 60, will be guarded by default. 
     AR --  HLD --This control signal, represented by the block 62, is guardable at the option of the firmware programmer by using AR --  HLD,NOP. 
     AR --  WD --  OVRD --This control signal, represented by the block 61, will be automatically guarded whenever there is used AR --  HLD,x which does not coexist with AR --  WORD. 
     ADD-BIT, ADD-DIGIT, ADD-CHAR, ADD BYTE--These mode field control signals, represented by blocks 63, need not be guarded. 
     It will be observed that, while some of the signals shown in FIG. 6 are directly represented in the AROM (FIG. 7) as designated fields, others are not and must be guarded indirectly by the appropriate control field states. 
     The presently preferred method of practicing the invention is set out with more particularity in the flowchart shown in FIG. 8. After the firmware has been written in virtual control words and debugged by simulation or any other appropriate method, the process of reducing the amount of storage required for the corresponding physical control words is undertaken. The earliest required control signals are allocated to reserved fields in the MROM word as previously discussed, and other control signals are obtained by accessing the BROM, AROM, DROM and EROM which are individually addressed by address fields stored in the MROM. Using the AROM as an example, further reduction of its required storage capacity and hence its size is obtained by the practice of the invention. 
     A comprehensive set of secondary nanocontrol words for the functions controlled by the AROM are developed, and the represented signals are allocated to predetermined fields in the AROM word template. For those fields, such as AR --  WT, which must always be guarded, all such secondary nanocontrol words are accordingly marked. A secondary nanocontrol word is then preprocessed. If, for the specific function defined by this control word, any fields should be guardable at the option of the firmware programmer (e.g., to handle unusual signal combinations), these fields are correspondingly marked. Similarly, if, for the specific function defined by this secondary nanocontrol word, any fields should be conditionally guardable, these fields are correspondingly marked. The term &#34;conditionally guardable&#34; in this context means that if a predetermined condition, such as the presence of some other signal simultaneously with the set of signals developed from the AROM, then the field must be guarded. The remaining fields for this control word are marked &#34;don&#39;t care&#34;; i.e., the function defined by this virtual control word will be properly carried out regardless of the state of the fields so marked. 
     The secondary nanocontrol word, all its fields having been analyzed, is now compared with another preprocessed secondary nanocontrol word, and a determination is made as to whether there is a match based on complementary control fields. That is, if the needed control fields in one of the control words are all &#34;don&#39;t care&#34; control fields in the other word (or are identical in content) and vice versa, then the two control words may be combined into a single secondary nanocontrol word which will carry out both functions accurately in conceit with other control signals originating elsewhere such as directly from the MROM control word. If no match is found, another preprocessed virtual control word is tried and so on until a match is either found or it is determined that the secondary nanocontrol word cannot be matched. 
     The principles of this combining procedure can readily be understood with reference to the simplified example shown in FIG. 9. In control word #1, field A has been marked as guarded, perhaps it is one that is mandatorily guarded. Field D has also been marked as guarded, perhaps field D is guardable, and the firmware programmer recognized that the signals to be controlled form this field as sensitive for this particular function and so he has used the option However, fields B and C have been identified as &#34;don&#39;t care&#34; for the control function represented by this control word; that is, whatever the contents of fields B and C, the function will be carried out correctly and without causing any secondary problems. In control word #2, field A is mandatorily guarded, and field B is also guarded, but fields C and D have both been identified as &#34;don&#39;t care&#34;. Therefore, these two control words can be combined into a single control word which will be called to perform both functions A and B if the contents of field A are the same. Assuming that has been found to be the case, the combined control word will contain the appropriate in formation in field A, the guarded information from control word #2 in field B and the guarded control word from control word #1 in field D. It will be observed that field C remains &#34;don&#39;t care&#34; such that it is possible that this combined control word could be combined with yet another control word to further reduce the required number of combined control words to represent the function set. 
     This process is reiterated until all secondary nanocontrol words have been completely processed and all possible matches have been tried. As noted, during this process, it is possible that it will be found that more than two functions may be performed utilizing a single AROM control word which result in a further reduction in the size of the AROM virtual control word set. Finally, a still further reduction in the secondary nanocontrol word set can be accomplished if desired by conventional bit packing. For example, if the conditions are right, the bit-wise code &#34;1001&#34; (bit 0 on and bit 3 on) can be reduced to binary &#34;101&#34; (5) which is easily decodable to obtain the requisite signal combination 
     Those skilled in the art will understand that there are various ways in which the procedure could be slightly revised to better fit a given environment. Referring again to FIG. 8, one such variant that is readily noted is that all the virtual AROM control words could be processed for marking in batch mode before the matching procedure is undertaken. 
     Thus, while the principles of the invention have now been made clear in an illustrative embodiment, there will be immediately obvious to those skilled in the art many modifications of structure, arrangements, proportions, the elements, materials, and components, used in the practice of the invention which are particularly adapted for specific environments and operating requirements without departing from those principles.