Digital Computer Memory

This invention relates generally to digital computer memories and more particularly to digital computer memories which are made up of a plurality of data storage components.

As is known in the art, microprogram controlled digital computers generally include a microinstruction memory for storing a plurality of microinstructions. Each stored microinstruction generally includes a plurality of fields, each field corresponding to one or more bits in the stored microinstruction. Each bit is represented by one of two logical states. If there are N bits in each microinstruction and if M microinstructions are to be stored in a microinstruction memory, or NxM microinstruction memory has heretofore been designed. Further, it is known that generally many stored microinstructions have a particular field, or portion thereof, which includes a plurality of bits, each being represented by the same logical state.

The microinstruction memory is generally of the "read only" type. Since read only memory (or data storage) components readily available in the marketplace are generally limited to a maximum of 1024 or 2048 addressable words (or locations), each eight bits in length, and many microprogram controlled digital computers require microinstructions which are greater than eight bits in length and more than 2048 addressable words or microinstructions, a plurality of read only memory or data storage components is required to provide the requisite microinstruction storage capacity. Because the cost of each one of the read only memory components adds to the overall cost of the computer, it is desirable to minimize the number of read only memory components required in such computer.

In accordance with the present invention a digital computer memory includes a set of address terminals, a set of data output terminals and a plurality of data storage components arranged in a matrix of rows and columns, each one of such data storage components having a predetermined number of addressable locations and a predetermined number of bits of storage in each one of such locations, the data storage components in each one of the rows being coupled to the address terminals and the storage elements in such columns being coupled to the data output terminals, the number of bits of storage in predetermined ones of such rows of the memory being less than the number of data output terminals.

With such an arrangement those fields, or portions thereof, which are represented by the same logical state, in particular ones of the microinstructions stored in the memory, are not stored in the data storage components, thereby reducing the number of data storage components used in such memory.

The above-identified and other features of the invention will become more apparent by reference to the following description taken together in conjunction with the accompanying drawings in which:

FIG. 1 is a block diagram, somewhat simplified, of a digital computer using a microinstruction memory according to the invention;

FIG. 2 is a diagram useful in understanding the organization of the microinstruction memory used in the digital computer shown in FIG. 1;

FIG. 3 is a block diagram of the microinstruction memory used in the computer shown in FIG. 1; and

FIG. 4 is a schematic diagram showing open collector output gates of one terminal of a column of data storage components in a wired -OR configuration to form an output terminal of the microinstruction memory used in the digital computer shown in FIG. 1.

Referring now to FIG. 1, a microprogram controlled digital computer 10 is shown to include a macroprogram and data memory 12, here any conventional random access memory, adapted to store a repertoire of macroinstructions, a microinstruction memory 14, here of the "read only" memory type, the details of which will be described in connection with FIG. 3, adapted to store sets of microinstructions, each one of such stored macroinstructions corresponding to a set of stored microinstructions, a register 15 for storing a selected one of such microinstructions, such selected one being the microinstruction under execution by the digital computer 10, a data flow unit 16, here including two input buses 18, 20, two output buses 21, 22, a plurality of registers P, IA and IB, a scratch pad random access memory, SP, and an input/output (I/O) device and an arithmetic unit AU, all of conventional design, and a microinstruction memory address control unit 24, which may be of any conventional design, such as, for example, a control unit similar to the microinstruction memory address control unit described in our copending patent application Ser. No. 662,303, filed Mar. 1, 1976 and assigned to the same assignee as the present invention, and a conventional timing unit 25.

As described in our copending patent application referred to above, the execution of each one of the macroinstructions is accomplished by the execution of each one of the microinstructions in the corresponding set thereof, such execution providing control signals to the data flow unit 16 thereby to control the flow of data in such unit 16 in accordance with each one of the microinstructions. Each one of the microinstructions includes a data flow control field for controlling the flow of data through the arithmetic unit, AU, the registers P, IA and IB, the scratch pad memory SP via input buses 18, 20, output buses 21, 22 and I/O device, while also controlling the function the arithmetic unit AU is to perform on selected data. In addition to such data flow control field each one of such microinstructions includes a microinstruction memory address control field which is fed to the microinstruction memory address control unit 24 for selecting the address of the next microinstruction as described in our above-mentioned copending patent application. After completion of a set of microinstructions which correspond to a selected macroinstruction a new macroinstruction is "fetched" and the operation code thereof is coupled via bus OP to the microinstruction address control unit 24 to provide the address of the first microinstruction in the set thereof which corresponds to the "fetched" macroinstruction.

The data control field may be considered as here being made up of the following fields:

In particular, the data flow control field of the microinstruction provides binary signals on buses AU.sub.C, AD.sub.S, P.sub.C, IA.sub.C, IB.sub.C, SP.sub.W, SP.sub.AD, TM.sub.C, I/O.sub.C, B.sub.1, B.sub.2, I/O.sub.S. It is noted that while each one of such buses is indicated as a single line, such buses are adapted to carry a plurality of bits, each bit represented by one of two logical states. For example, the AU.sub.C bus is an eight bit bus which couples the data in the ALUC field to the arithmetic unit, thereby to select the arithmetic or logic function to be performed on the two digital words supplied to such arithmetic unit AU. One of such data words is coupled to the arithmetic unit AU via output bus 21 from a selector 26. The other one of such data words is coupled to the arithmetic unit AU via selector 28 from either the macroprogram and data memory 12 or bus 22.

The signals in buses AD.sub.S, P.sub.C, IA.sub.C, IB.sub.C, SP.sub.W, SP.sub.AD and TM.sub.C and I/O.sub.C are developed in response to the digital word in the REGC field of the microinstruction stored in the register 15. The buses P.sub.C, IA.sub.C and IB.sub.C each carry three bit signals to the registers P, IA and IB, respectively, to control the function of such registers. It should be noted that the P register here serves as a program counter and the IA and IB registers are here general purpose registers. In response to the three bit signals supplied to the register P and register IA, such registers respectively either accept and store data on the bus 18, accept and store data on bus 20; accept, shift right and store data on the bus 18, accept, shift right and store data on bus 20; maintain its present state; or increment the data stored in such registers. In response to the three bit signal supplied to register IB, such register either accepts and stores data from the bus 18; accepts and stores data from bus 20; accepts, shifts right and stores data on bus 18; accepts, shifts right and stores data on bus 20; shifts stored data to the right; stores a logical 0; maintains its present state; or shifts data left. The bus AD.sub.S provides a 1 bit control to selector 28 to selectively couple either the data on bus 18 or the data on bus 22 to the arithmetic unit AU. The bus SP.sub.W provides a 1 bit control signal to the scratch pad memory SP to place such memory in either a read mode or a write mode, thereby to enable data on input bus 20 to be stored in such scratch pad memory at the location specified by an eight bit word on bus SP.sub.AD . The bus TM.sub.C provides a 1 control signal to the macroprogram and data memory 12 in either a read or write mode, the address of such memory being supplied by the data on bus 22. The bus I/O.sub.C provides a 1 bit signal to the I/O device to enable such device to accept data from input bus 20.

The signals on buses B.sub.1 and B.sub.2 are developed in response to the BUSC field of the microinstruction stored in register 15. Bus B.sub.1 carries a 2 word to selector 26 to selectively couple to output bus 21 either a word stored in the register P, a word stored in register IA, a word stored in register IB or a word stored in the scratch pad memory SP (such stored word being at a location specified by the data on bus SP.sub.AD). Bus B.sub.2 carries a three bit binary signal to selector 30 to couple to output bus 22 selectively either the digital word stored in the register P, the digital word stored in the register IA, the digital word stored in register IB, the digital word of the peripheral devices in the I/O device as selected by the signal on bus I/O.sub.S or the digital word stored in the scratch memory SP, such word being stored therein at the location specified by the data on bus SP.sub.AD.

The signals on bus I/O.sub.S are developed in response to the digital word in the I/OS field of the microinstruction stored in register 15. Such signal is here a four bit signal used to couple a selected one of a plurality of, here 16, peripheral devices (not shown) to the selector 30. The selected peripheral may be then coupled to bus 22 in response to a signal on bus B.sub.2.

In a typical operation of the digital computer 10 many of the microinstructions have a field, or portion thereof, which includes a plurality of bits represented by the same logical state. For example, a particular set of microinstructions may not use the I/OS field because during execution of such set data from peripheral devices are not being fed to the bus 22. Therefore, such microinstructions will have, here, logical 1's for all bits in the I/OS field. Likewise, when data is being fed from a selected peripheral device to the data memory in response to certain microinstructions the ALUC field is not used. Therefore, such microinstructions will have, here, all logical 1's for all of the bits in the ALUC field. Still further, certain microinstructions require use of only a portion of a field. For example, the portion of the REGC field which develops signals on buses I.sub.A and SP.sub.W may not be used in a particular set of microinstructions. Therefore, such microinstructions will have, here, logical 1's for all bits in such portion of the REGC field. The microinstruction memory 14 is made up of a plurality of data storage components, here read only memory (ROM) components. As will be shown hereinafter, the number of ROM components required to make up the microinstruction memory 14 is minimized by grouping together microinstructions which have a particular field, or portion thereof, which is made up of bits represented by the same logical state. In the example the microinstruction memory 14 is adapted to store 4096 microinstructions. Each microinstruction includes a 38 bit data control field (made up an 8 bit ALUC field, a 5 bit BUSC field, a 4 bit I/OS field and a 21 bit REGC field) and a microinstruction memory address control field, here 22 bits, to form a 60 bit microinstruction. As is known, such microinstruction memory 14 may be implemented using 60 ROM data storage components, each ROM data storage component being adapted to store 1024 words, each word having 4 bits. The arrangement of microinstructions in the microinstruction memory 14 is as represented in FIG. 2. In the example, for each microinstruction, bits 0-7 represent the ALUC field, bits 8-11 represent the I/OS field, bits 12-32 represent the REGC field, bits 33-37 represent the REGC field, and bits 38-59 represent the microinstruction memory address control field. It should be noted that bits 12-15 of an addressed microinstruction stored in register 15 develop the signals on bus IA.sub.C and bus SP.sub.W. Further, in the example, the microinstructions in locations (1001).sub.10 through (4095).sub.10 have logical 1's for all bits in the I/OS field because the peripheral devices are not fed to bus 22 during execution of the microinstructions in such locations. Further, in the example, the microinstructions in locations (1022).sub.10 through (2050).sub.10 have logical 1's for all bits in the REGC field which develops signals on bus IA.sub.C and bus SP.sub.W (i.e., bits 12-15). Still further, in the example, the microinstructions in locations (3070).sub.10 through (4095).sub.10 have logical 1's for all bits in the ALUC field because a selected peripheral device is being fed to the macroprogram memory from bus 22 during execution of the macroinstructions in such locations.

Referring now to FIG. 3, microinstruction memory 14 is shown to include a decoder 40, here of any conventional design. Such decoder 40 is fed by bus 38. Such microinstruction memory 14 also includes a plurality of data storage components, 40.sub.m,n, arranged in a matrix of rows and columns, the subscript m designating the row of such components and the subscript n designating the column of such component. Each one of such data storage components 40.sub.m,n is a TTL, open collector output, read only memory component, here a Model A 6350 manufactured by Monolithic Memories, Inc.. Each one of the data storage components 40.sub.m,n is adapted to store 1024 digital words, each word having 4 bits. Each data storage component includes 10 address terminals A.sub.0 --A.sub.9, a chip enable terminal CE, and four output terminals 0.sub.0 -0.sub.3, as shown, for an exemplary one of such data storage components, here data storage component 40.sub.1,1. The 10 data address terminals A.sub.0 -A.sub.9 are connected to 10 address outputs A'.sub.0 -A'.sub.9 of the decoder 40. Four chip enable lines CE.sub.1 -CE.sub.4 are coupled between the decoder 40 and the chip enable terminals CE of the data storage components 40.sub.m,n. As shown, the chip enable line CE.sub.1 is connected to the chip enable terminals CE of the data storage components in the first row (i.e., data storage components 40.sub.1,1 -40.sub.1,15). Chip enable line CE.sub.2 is connected to the data storage components in the second row (i.e., data storage components 40.sub.2,1 -40.sub.2,2 and 40.sub.2,5 -40.sub.2,15). Chip enable line CE.sub.3 is connected to the data storage components in the third row (i.e., components 40.sub.3,1 -40.sub.3,2 and 40.sub.3,4 -40.sub.3,15). Chip enable line CE.sub.4 is connected to the data storage components in the fourth row (i.e., components 40.sub.4,4 -40.sub.4,15). The data storage components in each column are wired -OR to a +V voltage supply through a conventional pull-up or load resistor, not numbered, in a conventional manner, as described in the book entitled "Designing With TTL Integrated Circuits," edited by R. L. Morris and J. R. Miller, published by McGraw Hill Book Company, New York, N.Y., 1971, pg. 46 and pgs. 127-128. That is, referring also to FIG. 4, exemplary ones of the output terminals of an exemplary one of the columns of data storage components, here output terminal 0.sub.3 of the data storage components in the first column (i.e., components 40.sub.1,1, 40.sub.2,1, 40.sub.3,1) are shown connected to open collector output gates. As shown, each open collector output gate includes a coupling transistor T.sub.1 having one emitter electrode coupled to the chip enable terminal, CE, of such component through an inverter, I, the chip enable terminals CE of components 40.sub.1,1 -40.sub.3,1 being coupled to chip enable lines CE.sub.1 -CE.sub.3, respectively, as discussed above. The second emitter electrode of transistor T.sub.1 is coupled to an INPUT line, such line being coupled to the "memory" element (not shown) of the ROM data storage component in any conventional manner. The base electrode of transistor T.sub.1 is connected to a +V voltage supply through a resistor R.sub.1 and the collector electrode of such transistor T.sub.1 is connected to the base electrode of transistor T.sub.2. The collector electrode of transistor T.sub.2 is connected to the +V voltage supply through a resistor R.sub.2 and the emitter electrode of transistor T.sub.2 is connected to: (a) ground through a resistor R.sub.3, and (b) the base electrode of transistor T.sub.3. The emitter electrode of transistor R.sub.3 is connected to ground and the collector electrode is connected to the output terminal 0.sub.3.

In operation, to enable a data storage component the chip enable terminal CE of such component is fed with a "low" signal and to disable such component such terminal CE is fed with a "high" signal. It is noted that when the chip enable terminal CE is "low," transistor T.sub.1 is controlled by the signal on the INPUT line and when the chip enable terminal CE is "high," transistor T.sub.1 goes "on" and transistors T.sub.2 and T.sub.3 go "off," thereby providing an open circuited output to terminal 0.sub.3. Considering the case when the chip enable line CE.sub.1 is "low" (i.e., component 40.sub.1,1 is enabled) and therefore lines CE.sub.2 -CE.sub.4 are "high" (i.e., components 40.sub.2,1 -40.sub.3,1 are "open circuited" as discussed above), if the INPUT line of component 40.sub.1,1 is "low" (i.e., logical 0), transistor T.sub.1 turns "on" and the base electrode of transistor T.sub.2 goes "low," turning transistor T.sub.2 "off," thereby turning transistor T.sub.3 "off," causing terminal 0.sub.3 (and hence B.sub.3) to be an "open circuit." Therefore, the "high" +V voltage souce appears at terminal B.sub.0 and therefore such terminal B.sub.0 produces a logical 1 signal. If the INPUT line of component 40.sub.1,1 is "high" (logical 1), transistor T.sub.1 goes "off," transistors T.sub.2 and T.sub.3 turn "on" and hence a logical 0 is produced at terminal 0.sub.3 and hence at terminal B.sub.0. It is noted that any one of the output terminals 0.sub.3 in the column of components will produce a logical 1 if, and only if, the output signals of all output terminals 0.sub.3 in such column are logical 1's and the resulting output signal at terminal B.sub.0 is then a logical 1. As soon as one of the output terminals 0.sub.3 in the column becomes a logical 0 the output terminal B.sub.0 becomes a logical 0. That is, considering, for example, the first column of data storage components (i.e., components 40.sub.1,1 -40.sub.3,1) the output terminals 0.sub.0 -0.sub.3 of each one of such components are wired -OR to the +V voltage supply through pull-up or load resistors, not numbered, to form memory output terminals B.sub.0 -B.sub.3, respectively. Likewise, the output terminals 0.sub.0 -0.sub.3 of each one of the data storage components in the second column (i.e., data storage components 40.sub. 1,2 -40.sub.3,2) are wired --OR to four memory output terminals B.sub.4 -B.sub.7. Continuing from column to column, the memory output terminals B.sub.8 -B.sub.59 are likewise found. The output terminals B.sub.0 -B.sub.59, therefore, provide the output terminals for microinstruction memory 14 and the 60 bit microinstruction read from such memory appears on such output terminals B.sub.0 -B.sub.59 and is fed to register 15 (FIG. 1). As described above and and also in the referenced book, because the data storage components in each column are wired -OR, any one of the output terminals B.sub.0 -B.sub.59 will produce a logical 1, if, and only if, the output signals of all open collector output data storage component outputs coupled to such one of the terminals are logical 1's and the resulting output signal on such one of the output terminals becomes a logical 1. As soon as one of the output signals coupled to such one of the output terminals becomes a logical 0, such output terminal produces a logical 0. Therefore, considering an exemplary one of the memory output terminals, say memory output terminal B.sub.0, such terminal B.sub.0 produces a logical 1 unless the outputs 0.sub.0 of data storage components 40.sub.1,1 and/or data storage component 40.sub.2,1 and/or data storage component 40.sub.3,1 is a logical 0.

Considering now the microinstruction memory 14, in operation, when the chip enable line CE.sub.1 is enabled a microinstruction in one of the locations 0 through (1023).sub.10 is addressed, the specific one of such locations being selected in accordance with the ten bit address signal applied to address terminals A.sub.0 -A.sub.9. Likewise, chip enable lines CE.sub.2 through CE.sub.4 are adapted to enable microinstructions in locations (1024).sub.10 through (2047).sub.10, (2048).sub.10 through (3071).sub.10 and (3072).sub.10 through (4095).sub.10, respectively, to be addressed, the specific microinstruction in such selected row of data storage components being selected in accordance with the 10 bit address signal on terminals A.sub.0 -A.sub.9. The selected or addressed microinstruction appears as a set of binary signals on the memory output terminals B.sub.0 -B.sub.59, the binary signals on such terminals B.sub.0 -B.sub.59 representing bits 0-59 respectively, of the addressed microinstruction. It should be noted that, because the data storage components in each column are wired -OR as described above, if a microinstruction in locations (3072).sub.10 through (4095).sub.10 is addressed, the data storage components in the first and second columns will produce logical 1's at the output terminals thereof because such terminals have open collector outputs and such data storage components are not enabled by the lines CE.sub.1 -CE.sub.3 and therefore logical 1's are produced at memory output terminals B.sub.0 -B.sub.7. Similarly, when a microinstruction in locations (1024).sub.10 -(4095).sub.10 is addressed, memory output terminals B.sub.8 -B.sub.11 produce logical 1's because open collector output data storage component 40.sub.1,3 is not enabled. Likewise, when a microinstruction in locations (1024).sub.10 through (2047).sub.10 is addressed, terminals B.sub.12 -B.sub.15 produce logical 1's because open collector output data storage components 40.sub.1,4 and 40.sub.3,4 -40.sub.4,4 are not enabled. It should now be noted that instead of requiring 15.times.4 or 60 data storage components to implement the microinstruction memory 14, here only 54 data storage components are required in the example because of the grouping together of microinstructions in the memory 14 which have common unused fields. More specifically, in the example (and referring also to FIG. 2), the microinstructions which have logical 1's for all bits in the ALUC field are grouped together so as to include locations (3072).sub.10 through (4095).sub.10 and therefore logical 1's are developed at terminals B.sub.0 -B.sub.7 when the microinstruction in such locations are addressed without requiring data storage components in row 4, columns 1 and 2, to store the ALUC field in such locations. The logical 1's, are developed at terminals B.sub.0 -B.sub.7 by the wired -OR open collector output data storage components 40.sub.1,1 -40.sub.3,1 and data storage components 40.sub.1,2 -40.sub.3,2, respectively. Therefore, data storage components are not required in column 1, row 4 or column 2, row 4 of the memory 14. Likewise, the microinstructions which have logical 1's for all bits in the I/OC field are grouped to include locations (1024).sub.10 through (4095).sub.10. When a microinstruction in such locations is addressed, the date storage component 40.sub.1,3 develops logical 1's at memory output terminals B.sub.8 -B.sub.11, eliminating the requirement for data storage components in column 3, rows 2 through 4 of the memory 14. Likewise, the microinstructions which have logical 1's for all bits in the portion of the REGC field unused are grouped together to include locations (1024).sub.10 through (2047).sub.10. When a microinstruction in such locations in addressed, the wired -OR data storage components 40.sub.1,4, 40.sub.3,4, 40.sub.4,4 develop logical 1's at terminals B.sub.12 -B.sub.15, eliminating a data storage component in column 4, row 2.

To put it another way, a data storage component having an open collector output can produce either: (a) an open circuit to the +V voltage supply and load resistor, in which case the +V voltage source produces a logical 1 signal; or (b) a "ground" for the +V voltage source and load resistor, in which case a logical 0 is produced. Therefore, considering the example, the logical 1's produced at output terminals B.sub.0 -B.sub.7 when the microinstructions in locations (3072).sub.10 through (4095).sub.10 are addressed lines CE.sub.1 -CE.sub.3 are "high" and chip enable line CE.sub.4 is "low" (i.e., dispensable) are produced by the +V voltage source and load resistors coupled to such terminals because the then disabled open collector components 40.sub.1,1, 40.sub.2,1, 40.sub.3,1 provide an open circuit to such load resistor and +V voltage source. Likewise, when the microinstructions in locations (1024).sub.10 through (4095).sub.10 are addressed the logical 1's at terminals B.sub.8 -B.sub. 11 are produced by the +V voltage source and the load resistors connected to such terminals, because of the open circuit provided by the disabled component 40.sub.1,3 ; and, when the microinstructions in locations (1024).sub.10 through (2047).sub.10 are addressed logical 1's at terminals B.sub.12 -B.sub.15 are produced by the +V voltage source and the load resistors connected to such terminals because of the open circuit provided by the disabled components 40.sub.1,4, 40.sub.3,4 and 40.sub.4,4.

Having described a preferred embodiment of this invention, it is now evident that other embodiments incorporating its concepts may be used. For example, tri-state output data storage components may be used because when not enabled such components provide an open circuit to the +V voltage source and load resistor. With such arrangement those columns which include a data storage component in each row thereof need not include a load resistor because such tri-state output data storage component is adapted to produce a logical 1, a logical 0 or an "off" (or open circuit) output. Still further, data storage components adapted to store other than 1024 digital words may be used. Likewise, such data storage components need not be limited to storage of words having four bits. It is felt, therefore, that this invention should not be restricted to the preferred embodiment, but rather should be limited only by the spirit and scope of the appended claims.