Note: Descriptions are shown in the official language in which they were submitted.
Background of the Invention
This invention relates to a random access memory and
more particularly to apparatus for transferring one or more
bytes of a digital word to and from one or more memory
locations within one memory cycle.
A computer or data processing system usually comprises
a memory subsystem having a plurality of memory locations for
the storage of digital words made up of a specific number o
bits such as 8, 16, 24 or 32. The computer architecture for
some prominent 32 bit general register machines employs vari-
able length instructions represented by a sequence of bytes
with the first byte specifying the operation to be performed
and succeedlng bytes specifying the operands. Each operand
may be 8, 16, 32, or even 64 bits. Storage of a mixture of
variable length instructions and data in a 32 bit word memory
ac~ieves maximum utilization of the memory storage space
available if, for example, part of a 32 bit instruction or
data word is stored in the same location as a 16 bit instruc-
tion or data word and the remainder in a subsequent memory
?al~ locAtion.
In the prior art, efficient utilization of memory space
has been accomplished by a combination of hardware and soft~
ware techniques. However, more than one memory cycle has
been required when part of an instruction or data word was
stored in one memory location and the other part stored in
another memory location. The result has been that efficient
utilization of memory space is accomplished, but the processing
~peed of the computer is reduced. Using ~his invention as
local storage, that is storage associated with a central pro-
cessing unit as opposed to the main storage of a data
3~5
processing system~ conventional main storage still can be
used while achieving the benefits of making multi-byte
accesses within one memory cycle in local storage.
3~7.~
Summary of the Inven~ion
According to a broad aspect oE the present invention,
there is provided in combination: memory means for storing in
one or more of a plurality of word locations variable length
digital words, each of said words having at least one byte and
each one of said word locations comprising a plurality of byte
positions, a first byte of one of said digital words being
stored at any one of said byte positions of one of said word
locations and any remaining bytes of said one of said digital
words being stored in any remaining byte positions of said one
of said word locations and in byte posi~ions of one or more
successive word locations as required to store said one of said
digital words; means coupled to said memory means for address-
ing one or more of said plurality of byte positions within
said one of said word locatio~s and one or more of said
successive word locations having stored therein the byte or
b~tes of said one of said digital words; said addressing means
comprising means Eor reading one or more of said bytes of said
on~ o:E said dig;.tal words from said one o:E sai.d word locations
~nd any remainincJ bytes o:E said onc o:E said digital words from
an adjacent one o.E said successive word locations within one
memory cycle; and common data bus means coupled to said memory
means for providing a bi-directional input-output port -to
transmit and receive said digital words.
~ ccording to another broad aspect of the present
invention, there is p.rovided in combination: memory means for
storiny in one or more of a plurality of word locations variable
leng~h dicJital words, each of said words having at least one
~yte ancl each one oE sa.id word locations comprising a plurality
~() of byte positions, a first byte of one of said digital words
being stored at any one of said byte positions of one of said
word locations and any remaining bytes of said one of said
-- 3
: 'r
3~7~
digital words being stored in any remaining byte positions of
said one of said word locations and in byte positions of one or
more successive word locations as required to store said one of
said digital words; means coupled to said memory means for
address.ing one or more of said plurality of byte positions
within said one of said word locations and one or more of said
successive word locations having stored therein the byte or
bytes of said one of said digital words; said addressing means
eomprising means for wri.ting or reading one or more of said
bytes of said one of said digital words into or from one of said
word locations within one memory cycle; said writing means
eomprising means for writing one or more of said bytes of said
one of said digital words into said one of said word locations
arlcl any remaining hytes of said one of said digital words into
an adjacent one of said successive word locations within one
memory cycle; said reading means comprising means for reading
one or more o:E said b~tes of said one o:E said digital words
.e~om sa~.d one of said word loeations and any remaining bytes of
sai.d one of said digital words from an adjacent one of said
~n sueeessive word locations within one memory cycle; means for
incrementing an address o~ one of said word locations enabling
said reading means to read more than one of said successive
word locations during one memory cycle; common data bus means
coupled to said memory means for providing a bi-directional
input-output port to transmit and receive said digital words;
means to said data bus, to said memory means and to said
a~dressincJ means :Eor aligning said bytes of said one oE said
d:Lgital words in a pre:Eerred se~uential orcler upon writing one
o~ said words into or reading one of said words from said memory
3n means; and said writing or reading means comprising means for
writing or reading a plurality of said bytes of said one of said
digital words into or from a combination of three successive
_ a, --
,~
~32~
memory word locations of said memory means within two memory
cycles, each of said word locations comprising four byte
positions and a first byte of said plur.ality of bytes being
stored in a first word location of said three successive word
locations and a last byte of said plurality of bytes of said one
of said digital words being stored in a third word location of
said three successive word locations.
According to a further broad aspect of the present
invention, there is provided in combination: memory means for
storing in one or more of a plurality of word locations variable
length digital words, each of said words having at least one
byte and each one of said word locations comprising a plurality
o:E byte posi.tions, a first byte of one of said digital words
being s-tored at any one of said byte positions of one of said
word locations and any remaining bytes of said one of said
digita]. words being stored in any remaining successive byte
positions of said one of said word locations and in byte
po~itions Oe one or more successive word locations as recluired
ko s-tore said one of said digita]. words; means for providing a
rst ~ddress to se:l.ect one of said word locations; means for
provid.ing a second address to select a first one of said byte
pos.Ltions in said one of said word locations; means for provid-
ing a third address to select one or more of said byte
positions in said one of said word locations; means for
incrementing said first address to enable more than one of said
word locations to be addressed during one memory cycle; first
decod.Lng means coup:led to said incrementing means and responsive
ko sclid ~econd address and said third address for producing
control s:lcJnals for sa.id incrementing means; second decoding
~() me~ns responsive to said second address and said third address
for providing read and write enable signals to each of said byte
positions in said word locations of said memory means; third
-- 5 --
,.
. ~
3;~7~
decoding means responsive to said second address and said third
address for producing control signals for aligning an original
order of said bytes of one of said digital words transferring to
or from said memory means into an order to enable said first
byte of one of said digital words belng stored at any one of
said byte positions of one of said word locations and to enable
said one of said digital words to be aligned to said original
order when read from said memory means; and means for trans-
ferring said digital words to or from said memory means, and
responsive to said aligning control signals from said third
decoding means.
According to yet another broad aspect of the present
i.nvention, there is provided a memory system wherein each one
o:E a plurality of digital words is transferred between a bus
and a memory means, said bus having a plurality of, N, bus byte
positions arranged in an order from a lowest order bus byte
po~:ltion to a higllest order bus byte position, said digital
wo.rds hav.ing one or more bytes arranged in an order from a
:I.owest order bytc to a highest order byte, said memory means
hav~ng a plural.ity O:e word locations, each one oE said word
locations haviny a plurality of N memory byte positions arranged
in an order from a lowest order memory byte position to a
highest order memory byte position, said memory system compris
ing: (a) means for addressing said memory means for storage in,
or retrieval from, said memory means each one of said plurality
of d:Lgital words being transferred between the bus and the
memo.ry means, said addressing means addressing either: each one
of the N memory byte positions in a word location; or, a Eirst
g.rou~ of the memory byte positions ln a first word location and
a second group of the memory byte positions of a second
successive word location, the order of the memory byte positions
of the first group being different from the order o:E the memory
- 5a -
3~7~
byte positions of the second group; and ~b) means for couplingeach one of the plurality of digital words either from the bus
to the memory means, for storage in such memory means, or to the
bus from the memory means, when retrieved from the memory means,
said digital words being coupled with the byte or bytes, of said
coupled digital words being rearranged from said initially
arranged order.
- 5b -
3~75
Brief Description of the Drawin~s
Other and further features and advantages of the
invention will become apparent in connection with the
accompanying drawings wherein:
FIG. 1 is a block diagram of the byte addressable memory
invention; and
FIG. 2 is a memory map with byte references for a list
of exemplary variable length instructions with variable
number of operands and different byte size data types.
FIG, 3 is a block diagram of the memory array shown in
FIG. l;
FIG. 4 is a block diagram of the adders shown in FIG. l;
FIG. 5 is a loglc diagram of the word boundary decoder
shown in FIG. 1;
FIG. 6A is a logic diagram of a first portion of the
column enable decoder shown in FIG. 1
FIG. 6B is a logic diagram of a second portion of the
column enable decoder shown in FIG. 1;
FIG. 7 is a logic diagram of the aligner decoder shown
2~ in FIG. l;
FIG. 8 is a block diagram of the bi-directional multi~
plexer shown in FIG. 1; and
FIG. 9 is a table of the connections for the bi-di-
rectional multiplexer as shown in FIG. 8 indicating which
m~mory bus bits are connected to each input multiplexer and
which RAM data out bits are connected to each output multi-
plexer.
327.~i
Description of ~he Preferred Embodiment
Referring now to FIG. 1 r there is shown in block diagram
form a word organized, byte addressable, random access memory
126. The storage element or Memory Array 106 in the preferred
embodiment is implemented with a plurality of semiconductor
random access memory (RAM) devices. Information in the form
of a 32 bit parallel digita] word is transferred on a 32 Bit
(4 byte) Memory Data 8us 102, to and from the Memory Array 106
via a Bi-directional Multiplexer 104. The digital word size
of a storage location in Memory Array 106 is 32 bits with four
byte reference (~R) positions per location and ~he number of
memory locations "m" is variable depending on the size of the
RAM devices used to implement Memory Array 106 and the storage
needs for various applications. Three memory locations are
illustrated in FIG. 1 containing a mixture of variable or
different word length instructions and data. Memory Array
106 is deEined to be word organized and byte addressable with
in~truct~ons and data aligned on arbitrary byte boundaries.
'~he locRtion or locations in memory to be addressed or
referenced are determined by the ~ord Address MSBS 118,
Memory Address LSBS 120 and Word Byte Size 122 input signalsO
The number of Memory Address LSBS 120 signals is determined
by the log2N where N - number of bytes in a memory location
word. In the preferred embodiment shown in FIG. 1, there
are ~our bytes per word so the Mem)ry Address LSBS 120 signals
consists o~ the two least significant bits of the memory
addre~s~ A maximurn of 4 bytes may be referenced in one memory
cycle. The remaining memory address bits make up the Word
Addres~ MSBS 118 signals. The Word Byte Size 122 siynals
3~ determine the number of bytes in the particular memory
-- 7 --
location being addressed in memory which is generally 1, 2
or 4 bytes. However, 8 bytes may be addressed in two memory
cycles as discussed subsequently. The Word Address MSBS 118
signals connect to each of the Adders 110, 112, 114 and 116.
The Memory Address LSsS 120 and the Word Byte Size 122 signals
connect to a Word Boundary Decoder 124 which determines when
the digital word being addressed i5 partly contained in two
successive memory locations requiring a second memory location
to be addressed; they also connect tc an Aligner Decoder 100
the outputs of which connect to the Bi-directional Multiplexer
104. The combination of the Aligner Decoder 100 and the
Bi-directional Multiplexer 104 controls the order of the
bytes in a digital word being transferred to and from Memory
Array 10G. In addition, the Memory Address LS8S 120 and the
Word Byte Size 122 signals also connect to a Column Enable
Decoder 108 which selects the columns or bytes within a memory
location oE Memory Array 106 that are being addressed.
Referring now to FIG. 2, twelve bytes of digital inform-
ation are listed illu~trating a typical mixture of variable
length in~truct.ions with variable numbers of operand speci-
~iers and variable size data types which may be 8, 16, 32 or
64 bits lon~ that may be stored in a Memory Array 106. The
memory map for word address location 0, word address location
1, and word address location 2 shown in FIG. 1 indicates a
typical efficient storage arrangement for this mixture oE
information. Each instruction includes an operation code
(OPCODE) that specifies the particular operation to be
per~ormed. In addition, an instruction may include one or
mor~ operand specifiers depending on the type of instruction.
Although the length o~ a particular instruction or data word
~3~7~
may vary depending on ~he number of by~es it comprises as
shown in FIG. 2, each memory address location in the preferred
embodiment word organized Memory Array 106 contains 4 bytes
or a total of 32 bits. This means that a portion of an in-
struction or data may be stored in one memory location and
the balance may be stored in a successive memory location in
order to achieve efficient ut-lization of the total memory
storage capacity available in a given Memory Array 106
Each column of bytes, as shown in the Memory Array 106
in FIG. 1, is addressed independently of the other columns by
one of the Adders 110, 112, 114 and 116. The Word Address
MSBS 118 signals for a memory location to be referenced
consist oE all the memory address bits except the log2~l
least significant bits and they are applied to the input o
each Adder 110 to 116. In the present embodiment where
there are ~our bytes in one memory location word, N = 4 and
Log2 (4) results in Z least significant bits which become the
Memory Address LSBS 120 æignals. Each Adder 110 to 116
either passes the Word ~ddress MSBS 118 signals unmodified
or increments the word address by one via Carry in Llnes
128-134 from the Word Boundary Decoder 124 which decode~ the
Memory Address LSBS 120 signals and the Word Byte Size 122
signals.
Since the preferred embodiment comprises 4 bytes per
memory location, provision has been made for referencing
8 bytes in two memory cycles when said 8 bytes are stored
within three successive memory locations. Referring again
to FIG. 1, if an 8-byte string located in byte references
BR2, BR3t BR4, BR5, BR6, BR7, BR8, and BR9 is referenced, the
first memory cycle wiLl reference BR2, BR3, BR4, BR5. Control
~3~7S;
signal INC 148 is asserted during the first and second memory
cycles effectively causing the starting Word Address MSBS 118
to be incremented two times and thereby addressing byte
references BR6, sR7, BR8, and BR9 during the second cycle.
Referring now to FIG. 3, the Memory Array 106 comprises
four 64 x 4 random access memories (RAMs) 150, 152, 154, 156,
such as the Type 93419 integrated circuits, each RAM comprising
a plurality of storage locations. In larger memory
implementations, each RAM would be replaced with a plurality
of RAM banksO Each RAM (or bank of RAMs) receives a byte of
data from the si-directional Multiplexer 104 during write
operations, and outputs a byte of data to the Bi-directional
Multiplexer 104 during read operations. The RAM read and
write enables are controlled by the Column Enable Decoder 108.
The ~AM Word Addresses 140, 142, 144, 146 provided by the
Adders are connected to the most significant address bits
(Ao ancl Al) o~ the RAMs 150 to 156. One skilled in the art
will recognixe that the number of address bits is determined
by the number Oe memory storage locations to be used in a
RAM or bank of RAMs. In F'IG. 3, only two adclress bits (Ao
and Al) of each RAM 150 to 156 are used, but others may
readily be connected.
The Adders 110, 112, 114, 116, are shown in more detail
in FIG. 4. They generate the RAM Word Addresses 140, 142,
144, 146 for addressing each word address location in the
Memory Array 106 under the control of the Word Boundary
Decoder 124. Each adder may, for example, be embodied as a
Type 5482 integrated circuit if only two address bits were
requirecl. The Carry-in Signals 128, 130, 132, 134 to each
adder from the Word Boundary Decoder 124 provide the
- 10 -
3~7~;
capability o~ addiny 1 to the Word Address MS3S 118 signals
represented by lines MAo 160 and MAl 162 in order to perform
two memory references within one memory cycle. An INC Signal
148 provides the capability of adding a second 1 to all RAM
word addresses simultaneously thereby enabling a total of
three RAM addresses to be generated for referencing 8 byte
instructions or data. Each adder of the Type 5482 integrated
circuit has the capability of performing the addition of two
2-bit binary numbers. For memory arrays requiring more RAM,
word address bits which generally would be the case, higher
density integrated circuit adders or combinations thereof
may readily be utilized by one skilled in the art.
Referring now to FIG. 5, the logic circuit for the Word
Boundary Decoder 124 is shown. This decoder comprising NOR
gate 164 and NAND gate 166 controls the action o the Adders
110-116 as a function o the LSBs of the memory address and
the byte size of the instruction or data memory re~erence.
If both memory address LSBs, MA2 and MA3, are true, than a
carry in will be produced to Adder 0, Adder 1 and Adder 2 on
lines 128, 130 and 132, thereby adding one to the associated
Word Address MS8S 118. If only LSB MA2 is true, than a carry-
in will be produced to Adder 0 and Adder 1 on line 128 and 130,
thereby adding one to the associated Word Address MSBS 118.
I only LSB MA3 is true, than a carry-in will be produced to
Adder 0 on line 128, thereby adding one to the associated
Word Address MSBS 118. The carry~in to Adder 3 on line 134 is
always false. The INC 148 signal in the present embodiment is
one of the Word Byte Size 122 signals. ~t is a control signal
generated during the second half of a two cycle 8 byte memory
reference, thereby adding one to all associated word addresses.
~ ~ ~3~
The detail combinational logic networks for the Column
Enable Decoder 108 are shown in FIG, 6A (gates 210-230 and
inverters 228-230) and Fig. 6B (gates 240-256 and inverters
258 and 260). This decoder generates the write enable and the
output or chip enable for each RAM 150-156 shown in FIG. 3 as
a function of the memory reference size (1 byte or 4 byte)
and LSBs (MA2 and MA3) of the memory address. The control
signals lbyte 170, 2byte 172, and 4byte 174 are provided by
the Word Byte Size 122 input word and they identify the
number of bytes in a memory reference. The starting memory
byte location is specified by the Memory Address LSBS 120
slgnals which in the present embodiment comprise MA2 and
MA3. When the inormation stored in a memory location of
the Memory Array 106 is to be read out, an output or chip
enable signal such as CE ~AM '~ is generated where "R" is
the RAM re~erence designation number 0, 1, 2, or 3, causing
a RAM to per~orm a read cycle. When information is to be
stored in a Memory Array 106, an output signal CE RAM "R" is
ANDed with control signals WRITE 176 and WRIT~ PLS 178 causing
~n the WE RAM r~ signals to be generated which causes a RAM to
perform a write cycle.
Referring now to FIG. 7, the detail combinational logic
comprising gates 270~280 and inverter 282 for the Aligner De-
coder 100 is shown. The Aligner Decoder 100 logic design is
such that i a memory reference is not for one byte or four
bytes of inormation, then the circuit generates output
signals as if two bytes are requested. The Aligner Decoder
100 generates the Select A and Select B signals for the
Bi-directional Multiplexer 104 as a function of the Memory
3n Address LSBS 120 signals (MA2 and MA3) and the Word Byte
- 12 -
3~75
lize 122 signals (lByte 170 and 4Byte 174). The Input-Output
Mux Sel A 180 signal is used for both the Input Multiplexer 190
and the Output Multiplexer 192 of the Bi-directional Multiplexer
104 while the Input Mux Sel B 184 is derived from the Output Mux
Sel B 182 signal and the Input-Output Mux Sel A 180 signal.
The Input Multiplexer 190 and Output Multiplexer 192
comprising the Bi-directional Multiplexer 104 are shown in
FIG~ ~ and Table 1 contains the connections to multiplexer
inputs Co, Cl, C2 and C3 as shown in FIG. 9. Bi-directional
Multiplexer 104 rotates by~es into the proper order during
memory reference read and write operations. The Output
Multiplexers 192 are active during memory read operation;
they comprise thirty-two 4:1 multiplexers, each of which may
be embodied as a Type 74LS353 integrated circuit. The control
signal READ 194, which indicate~ that the Memory Array 106
is performing a read cycle is used to control the output
enable of the Output Multip:l,exer 192. The Output Multiplexer
192 Select Lines A 196 and B 198 are controlled by the Aligner
Decoder 100; the Input-Output Mux Sel A 180 signal connects
to S~lect A line 196 and the Output Mux Sel B, 182 signal
connects to the Select B line 198. The Input Multiplexers 190
are active during memory write operations; they comprise
thirty-two 4:1 multiplexers, each of which may be embodied
as a Type 74LS153 integrated circuit. The Aligner ~ecoder
100 also controls the select lines A 200 and B 202 of the
Input Multiplexer 190; the Input-Output Mux Sel A 180 signal
connects to Select A line 200 and the Input Mux Sel B 184
~ignal connects to the Select B line 202. Table 1 also
indlcates which memory bus bits are connected to each Input
Multiplexer 190 and which RAM Data Out bits are connected to
3;27~
each Output Multiplexer 192.
rrhe operation of the byte addressable memory invention
shown in FIGo 1 can be explained by using as an example the
referencing of a four byte data string in one memory cycle
located in byte references BR6, BR7, BR8 and BR9 of Memory
Array 106. The memory address for this data string is sepa-
rated into a most signi~icant bit part and a least significant
bit part which are called Word Address MSBS 118 signals and
Memory Address LSRS 120 signals respec~ively. The Word
Address MSBS 118 signals are connected to each one of the
Adders 110, 112, 114, 116 and select a word address location
in the Memory Array 106 such as Word Address Location 1 in
this example, which is where BR6 and BR7 are located in
addition to BR~ and BR5 which are not wanted~
In order to select the desired bytes such as BR6 and
~R7, the Word Byte Size 122 signals are provided to identify
the number o bytes in the memory address bei.ng reEerenced
whlch i~ ~our bytes in the present example. This is im-
portant because in this example the inEormation oE the
2n re~erenced memory address i~ partially located in two
memory loca~ions, that is, BR6 and BR7 are stored in Word
Address Location 1 and BR8 and BR9 are stored in Word Address
Location 2. The Word Address ~SBS 118 siynals pass through
Adder 114 and Adder 116 causing BR6 and BR7 in Word Address
Location 1 to be referenced. During the same memory cycle,
the Word Address MSBS 118 signals are incremented by 1 when
passin~ through ADDER 110 and ADDER 112 as a result o~ Word
Boundary Decoder 124 which results in BR8 and B~9 being
re~erellced in Word Address Location 2. The writing or reading
3~ oE the proper number of inEormakion bytes ~o or from a
- 14 -
3%~7~
location in the Memory Array 106 also is determined by the
Column Enable Decoder 108 which generates output enable (read)
signals such as CE RAM O 149 or a write enable signal such as
WE RAM O 147. When the output enable or read signals are
generated, the referenced bytes will appear at the input-
ou~put ports of the Memory Array 106 in the order BR8, BR9,
BR6 and BR7. Then the Bi-directional Multiplexer 104 under
the control of the Aligner Decoder 100 rearranges the order
to achieve the byte order BR6, BR7, BR8, BR9 on the 32 Bit
(4-~yte) Memory Data Bus 102 interface. Initially in this
example when ~he contents of BR6, BR7, BR8 and B~9 were stored
in Memory Array 106 by a write operation, the information
appeared on the 32 bit (4 byte) Memory Data Bus 102 in the
order BR6, BR7, BR8, RR9. The Bi-directional Multiplexer
immediately rearranged the byte order to BR8, BR9, BR6, BR7
in order to direct BR6 and BR7 into the second half oE Word
Address Location 1 and BR8 and BR9 into the first half oE
Word Addre~ r.ocation 2 o Memory Array 106.
In the case where an 8-byte strin~ o information located
in BR2, BR3~ BR~, BR5, BR6, 3R7 and BR8 is to be read from
Memory Array 106 t the operation for obtaining byte references
B~2, BR3, BR4, BR5 is as described hereinbefore during the
first memory cycle. During a second memo~y cycle, a control
signal INC 148 is generated which causes an addi~ional 1 to
be added to the Word Address MSBS 118 signals passing through
Adders 110, 112, 114, 116 which results in addressing BR6,
BR7, BR8 and B~9 in a similar manner as described hereinbefore
with the Bi-Directional Multiplexer 104 again performing the
appropriate reordering.
This concludes the description of the preferred embodi-
- 15 -
~3~
ment. However, many modifications and alterations will be
obvious to one of ordinary skill in the art without departing
from the spirit and scope of the inventive concept. For
example, although the preferred embodiment is described
a read-write random access memory (RAM) array
element, a read-only memory (ROM) integrated circuit chip may
also be used to implement the memory array; such a chip of
cour~e will not require any write control signals and the
speed and storage efficiencies achieved by this invention
will be realized for a ROM memory. The total storage capacity
needed in the RA~s or RO~s will vary depending on application
requirements; the number of bits or bytes in a word may vary
as well as the total number of words. As the storage capacity
increases, the number of address bits will increase requiring
multiple bit adders or banks of adders for incrementing the
memory re~erence address. In addition, all of the integrated
circuits required ~o implemen~ ~he present invention may be
implementea on one large scale inteyrated (LSI) chip. rrhere-
fore, lt is intended that the scope of this invention be
~n limited only by the appended claims.
- 16 -