 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to digital data transmission employing a
data bus and data storage in a solid state memory which is accessed by the
bus. More particularly, the present invention is directed to a bus system
in which a variable number of bus lines are employed to transmit data and
a variable number of storage locations corresponding to different data
word locations in a memory are employed. The invention has a particular
application with respect to solid state data recorders such as those
employed in space missions in satellites or manned spacecraft. Solid state
data recorders employ solid state memory devices to store data, in
contrast to the typical storage medium of magnetic tape. Such recorders
can provide improved reliability in that they do not require complicated
tape handling mechanisms. In solid state recorders, data is stored by
appropriately addressing a random access memory (RAM) and recording a
series of data words of a predetermined number of bits each.
Since there are no moving mechanisms for tape handling or the like, solid
state recorders can provide a high degree of reliability. However, such
recorders are typically very expensive due to the high cost of memory.
Moreover, in the space environment where repair generally is not possible
during the course of a mission, provision must be made to ensure a certain
recording capacity throughout the life of the mission. Thus, sufficient
overall memory capacity must be provided such that even after failure of a
number of memory devices during a mission sufficient overall capacity will
be retained. In effect, "spare" memory devices must be provided to replace
failed devices in order to maintain a nominal recording capacity. The
necessity to provide spare devices further increases the overall cost of
the system.
2. Description of the Prior Art
Various solid state recorders have been proposed in the past, such as that
shown in U.S. Pat. No. 4,970,648 to Capots. The recorder disclosed in this
patent has the capability of detecting errors in its memory and avoiding
use of portions of the memory that have errors. The memory is controlled
by a control CPU on the basis of "pages", which are the smallest portion
of the memory array which has meaning to the CPU. The system evaluates the
memory to detect pages which have non-correctable errors. Such pages are
then removed from use. In this fashion, failed memory locations are
avoided and reliability is maintained.
Although a system in which memory pages are removed provides the necessary
reliability, the cost can be extremely high in terms of memory
requirements. This is especially so since failures are very often isolated
in a relatively small memory area (even an individual storage location),
and the removal of an entire page of memory often results in the removal
of a significant amount of usable memory along with failed memory. The
result is that greater memory overhead is required to maintain the
specified data capacity, and cost is significantly increased.
SUMMARY OF THE INVENTION
The present invention is directed to a solid state recorder in which memory
sparing efficiency is greatly improved and the removal of memory is much
more closely mapped to correspond to memory devices which have actually
failed, thereby avoiding the unnecessary removal of usable memory. This is
accomplished by employing a unique flexible width data bus and variable
word length system. The system nominally records data words of a
predetermined length, e.g., seventy-two bits. These data words are
provided to the memory via a seventy-two bit data bus. The data words are
formed of plural input words of, e.g., sixteen bits each, which have been
combined along with error detection and correction bits to form a
seventy-two bit data word. When failed memory locations are detected,
fewer input words are combined and the length of the formed data word is
reduced. The shortened data word is provided along appropriately selected
bus lines to memory locations in the word storage area which are still
usable. Bus lines corresponding to failed storage locations are masked out
and are not employed to store input data. In this fashion, memory can be
removed on a fraction of a data word basis, thus greatly reducing the
amount of good memory area which is taken out of use. In a similar manner,
if a bus line, bus driver or bus receiver fails, the bus line can be
masked out so as to maintain the integrity of the remaining bus lines.
Upon readout, data from the failed memory areas is not employed and the
input words which make up a particular data word are extracted. The
invention greatly reduces the rate at which usable memory is removed by
employing a variable data word length and a variable width data bus. That
is, although a data bus of predetermined width is provided, the number of
lines of the data bus which are used to transmit input data words varies
depending upon what locations of a memory are to be employed.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention will be described with reference to the accompanying
drawings, wherein:
FIG. 1 is a block diagram of the solid state recorder of the present
invention;
FIG. 2 is a diagram illustrating the physical memory configuration of the
present invention;
FIG. 3 is a diagram illustrating the logical memory mapping function which
maps physical blocks of memory to logical blocks and indicates attributes
of physical blocks;
FIG. 4 illustrates a logical memory configuration which has been altered to
reconfigure the logical memory upon detection of a failed memory location;
FIG. 5 is a diagram illustrating the logical-to-physical mapping operation
and the attribute table indicating failed memory locations which are to be
avoided;
FIG. 6 is a diagram illustrating the logical-to-physical mapping to place
logical blocks with an increasing number of failed memory locations toward
the end of a partition;
FIGS. 7A, 7B and 7C are a block diagram of the input circuit of the
recorder of the present invention;
FIGS. 8A, 8B and 8C are a block diagram of the output circuit of the
present invention; and
FIGS. 9A, 9B and 9C are a block diagram of the address generator of the
present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENT
The following description is of the best presently contemplated mode of
carrying out the invention. This description is made for the purpose of
illustrating the general principles of the invention and is not to be
taken in a limiting sense. The scope of the invention is best determined
with reference to the appended claims. In particular, although the
invention is described in terms of a solid state recorder, the flexible
width data bus of the present invention may also be used for other
applications.
Referring to FIG. 1, the solid state recorder of the present invention
includes a memory array 10 which in the present embodiment is formed of
eight separate memory cards each including one hundred forty-four static
random access memory (SRAM) devices per side. Each SRAM has a capacity of
one megabit that is organized as 128K by 8 bits wide. The total capacity
of the memory array is therefore 2.25 gigabits. As will be discussed in
more detail subsequently, the memory is configured to provide 1.8 gigabits
of user memory, 225 megabits of error detection and correction memory and
225 megabits of spare memory for replacing failed memory sections.
Data is transmitted to and from the memory cards 10 via a seventy-two bit
wide (i.e., seventy-two separate lines) data bus 12. The data bus is
coupled to an input and output circuit 14 which receives data to be stored
in the memory 10 at a data input port and provides data read out from the
memory 10 at a data output port. A buffer 16 is connected on the data bus
between the memory 10 and the input and output circuit 14.
Addressing of the appropriate memory locations is controlled by address
generator circuits 18 which provide a twenty-five bit address to the
memory 10 by way of an address bus 20 having a buffer 22. The address
generators 18 also communicate with the input and output circuit 14 as
will be described subsequently. In addition to the address signals, the
bus 20 also provides read/write control signals to the memory 10. These
are provided from a main memory arbitration logic and read/write sequence
generator 24. This circuitry communicates with the input and output
circuit 14 via interface 25, a built-in test circuit 26 via interface 29
and address generator circuits 18 and 28 via interfaces 21 and 23 and
determines access to the data bus 12 as well as controlling reading and
writing operations of the memory 10. The arbitration logic receives bus
requests and, based upon a fixed priority, grants bus access to one
requesting circuit at a time.
The built-in test circuit 26 replicates the input and output circuit 14 to
provide test data to store in the memory 10 and subsequently read out in
order to detect failed memory locations. Separate address generator
circuits 28 are associated with the built-in test circuit.
In the present embodiment of the invention, the input and output circuit,
addressing circuits and built-in test circuit are formed as special
purpose integrated circuits in order to provide maximum speed of
operation, with a microprocessor subsystem 30 performing background
processing operations. However, it should be noted that the functions of
these logic circuits could all be accomplished by a microprocessor
configuration.
The solid state recorder system treats the memory 10 as a logical memory
space which is divided into a number of partitions each of which include a
number of blocks of memory. Data is requested to be written into or read
out of the logical memory by means of logical requests provided to the
address generators 18 and 28 from the input and output circuit 14 or the
built-in test circuit 26 via address generator interfaces 17 and 27,
respectively. The address generators 18 and 28 in turn provide logical
addresses on lines 34 and 36, respectively, to a block logical-to-physical
translation table and attributes memory 38 which includes memory
containing logical-to-physical mapping information for the main memory 10.
Arbitration between the mapping table and attributes is controlled by
arbitration circuit 37 communicating via interfaces 39 and 41 to address
generators. Control signals are provided on line 43. Physical address data
corresponding to the logical address is provided back to the address
generators 18 and 28 via lines 40 and 42, respectively, and are used by
the address generators 18 and 28 to generate an overall physical address
to the memory 10. Attribute data is provided back to the input and output
circuit 14 and test circuit 26 via lines 40 and 42.
In operation, the system performs actual transfer of data between the input
and output ports to the memory array 10 without intervention by the
microprocessor 30. The microprocessor subsystem interacts with the data
transfer and control section (the input and output circuits and address
generators) by maintaining two tables, namely, the logical-to-physical
mapping table and the memory attribute table. The memory attribute table
contains information for avoiding failed sections of memory. For maximum
data transfer speed, the microprocessor 30 is not directly involved with
the data transfers but rather performs less time critical tasks of
background processing. Microprocessor 30 communicates with the tables 38
via address and data lines 44 and 46, respectively and with arbiter 37 via
line 45. The microprocessor 30 includes associated program ROM and working
RAM. The information in the table 38 is created and maintained by the
microprocessor in response to commanded self-test operations of the
self-test circuit which identifies failed memory locations. Once a failure
is diagnosed, the microprocessor updates the tables 38 to ensure that
future memory operations are not affected by the memory failures. The
microprocessor 30 also operates to control initialization of system
control registers which govern the acquisition and computation of address
information necessary to perform data transfers to the memory 10.
FIG. 2 illustrates the organization of the physical memory space of the
memory 10. The memory is configured as seventy-two bits (9 bytes) wide by
8K (8192) blocks deep with each block being 4K (4096) deep. Each block
therefore holds 4K seventy-two bit data words which are transmitted via
the seventy-two bit data bus 12. In practice, sixty-four bits of the
seventy-two bit word are employed for user data and eight bits are
employed to store error detection and correction bits in accordance with
Hamming code which is known in the art.
Failures within the memory are determined on a byte (8 bit) basis within
each block. The memory is therefore illustrated as being configured such
that each block is nine bytes wide. For illustration purposes, a failed
byte 48 is illustrated in FIG. 2. The manner of masking this failed
section in order to prevent its use in recording data will be described
subsequently.
The logical-to-physical mapping employed in the present invention is
illustrated in FIG. 3. The table 38 includes a translation table which
maps logical blocks to physical blocks of the memory. The logical memory
is divided into N partitions, each of which starts on a block boundary.
Each partition is treated as a separate addressable memory. In FIG. 3, the
logical blocks are mapped in order onto physical blocks, which is the case
if there is no failed memory sections. That is, the logical block number
and physical block number will correspond to one another.
In addition to the logical-to-physical block translation information, the
table 38 includes "block attributes" of bytes to be skipped within a block
and whether or not an alternate byte is to be employed for error detection
and correction (EDAC), which is used in the event that the memory area
normally employed for storing error detection and correction information
itself fails. When there are no failed memory areas, there will be no skip
information or alternate EDAC use for any of the blocks, as illustrated in
FIG. 3.
When a memory section has been determined to be bad, the attribute
information is updated and the logical-to-physical mapping is altered.
This is illustrated in FIG. 4. When it is determined that a byte within a
block has failed, such as the fourth byte within block 10 as illustrated
at 48 in FIG. 2, the logical mapping is altered to move the block having a
failed byte toward the end of the partition. Thus, FIG. 4 illustrates that
the logical-to-physical mapping has been changed to map logical block 10
onto physical block 20 (the last physical block in partition 1) and map
the logical block 20 onto the physical block 10. In this way, the physical
block having failed memory area is moved to the end of the partition.
In addition to altering the logical-to-physical mapping, the skip attribute
will be altered to indicate that logical block 20 will skip bytes 4 and 5
in order to avoid failed memory area. For ease of implementation, in the
present embodiment, errors are detected on a byte basis but memory areas
are removed two bytes at a time. It is for this reason that both the
number 4 and 5 bytes are to be skipped even though a single byte in
physical block 10 contains failed memory. In the event that a second byte
within physical block 10 fails, the skip attribute is updated to indicate
that byte 4 and the newly failed byte should be skipped.
The effect of skipping bytes is that the length of data words to be stored
in memory are reduced from the nominal seventy-two bit data word length.
Rather than avoiding entire seventy-two bit wide blocks when failed memory
is detected, the present invention operates to remove small sections of
the memory at a time by employing a variable data word length and, in
effect, a flexible width data bus. When two bytes are skipped as
illustrated in FIG. 4, the useful data word length to be stored in
physical block 10 is reduced by two bytes from nine bytes (seventy-two
bits) to seven bytes (fifty-six bits). This is accomplished by providing
input words which are less than the overall data word length and
selectively combining plural input words and EDAC information to form an
overall data word. This is illustrated in more detail in FIG. 5.
Data is input to the recorder as logical or data words of sixteen bits
each. To form a complete seventy-two bit data word for storage in the
memory array, four input words and one EDAC byte are combined, as
illustrated at 50, 52, 54 and 55 in FIG. 5. These data words are formed by
the input portion of the input and output circuit 14 and transmitted along
the data bus 12 for storage in memory 10. When various bytes of a block
are not to be used due to detection of failed memory locations, those
particular bytes of the in the memory array will be filled with dummy bits
as discussed in detail subsequently. Data words of reduced length will be
formed by the input portion of the input and output circuit 14, combined
with the dummy bits and transmitted along appropriate lines of the bus 12
to the memory. Thus, at 58 in FIG. 5, the first byte of the input word 3
location and the EDAC byte are not to be used. The data word which is
formed will therefore be fifty-six useful bits rather than seventy-two
bits and will be formed by combining three input words and an EDAC byte.
The combined information forms a data word of fifty-six bits which is
transmitted along appropriate lines of the data bus 12 to avoid the two
bytes which are indicated as not to be used (fill bits are provided for
these bytes). Since the normal position for the EDAC byte is not to be
used in data word 58, an alternate position in the input word 3 position
is used in the case of the block illustrated at 58. This information is
also contained in the attribute table which shows that the seventh byte is
to be skipped and that the alternate EDAC byte is to be employed. In
addition, the logical-to-physical block mapping indicates that physical
block number 2 is to be mapped onto logical block number 1 in this
example.
A similar situation exists with respect to the block 60 in which it is
illustrated that the memory array location corresponding to input word
number 2 is to be avoided. Again, a fifty-six bit data word will be formed
by appropriately combining input words and an EDAC byte and transmitted on
the appropriate lines of the data bus 12 along with fill bits
corresponding to the area not to be used for the storage of user data.
With respect to words to be stored in physical block 5 indicated at 62 in
FIG. 5, four bytes are to be avoided in the memory array. Data words
formed to be stored in that block will therefore have a total of forty
useful bits. With respect to physical block 8190 indicated at 64 in FIG.
5, a total of six bytes are to be avoided, such that a single input word
and the EDAC byte are to be employed, with a resultant data word length of
twenty-four useful bits. This is the shortest data word length of useful
bits to be employed.
FIG. 5 indicates the physical location of each data word at 66. Thus, for
the example shown, physical block 0 will contain physical data word
locations 0-4095, physical block 1 will contain data word locations
4096-8191, etc. Within a physical block, each data word will have the same
length.
Referring to FIG. 6, the logical configuration of a partition will be
described. The example shown in FIG. 6 employs blocks of eight locations
deep (as opposed to 4K locations in the actual embodiment) for ease of
discussion. Data is entered into the memory in groups of sixteen bit
logical or input words referred to as frames. In FIG. 6, each frame is
formed of seventeen input words of two bytes each. Each logical block has
eight addresses, i.e., addresses for eight data words. The partition
illustrated has fourteen frames. Frames are entered contiguous to one
another such that data from two different frames may be combined to form a
data word for storage in the memory, i.e., a frame may end in the middle
of a data word.
In order to take advantage of the maximum data word length as much as
possible, the logical-to-physical block mapping is arranged as shown in
FIG. 6 such that logical blocks are ordered in accordance with increasing
amount of failed memory locations and therefore decreasing useful data
word length. In FIG. 6, logical blocks 3-6, i.e., the first four blocks in
the current partition, have no memory locations to be skipped and the
useful data word length is therefore the full seventy-two bits. Logical
blocks 7, 8 and 9 each have two bytes which will be skipped and therefore
have a fifty-six useful bit data word length and will include three input
words per data word plus one EDAC byte. Logical block 10 is configured to
skip four bytes, such that the data word length will include two input
words and one EDAC byte for a total useful data word length of forty bits.
Logical block numbers 11, 12 and 13 are formed of a single input word and
an EDAC byte for a total useful data word length of twenty-four bits. As
can be seen in FIG. 6, a single frame may cross one or more block
boundaries.
In order to properly store and read out frames, it is necessary to provide
the proper logical block address and the address within a block
corresponding to the beginning of the frame. These addresses must be
converted to physical addresses to actually access the memory 10.
Operation of the input portion of the input and output circuit 14 will be
described with reference to FIGS. 7A-C. Data to be recorded in the memory
10 is received in serial fashion on data line 70 at an input interface
ready circuit 72. The serial data is converted into sixteen bit input
words by means of a shift register 74. The sixteen bit input word is
latched into two eight bit latches 76 and 78. The data in each latch is
sequentially applied to an input data bus 80 by means of a multiplexer 82
which receives a high/low byte select signal from a skipping logic section
84 on line 86. The two bytes supplied to the data bus 80 are directed to
appropriate ones of a group of eight latches 88 via corresponding
multiplexers 90. A data in signal from the skipping logic directs the
bytes from the latches 76 and 78 to the appropriate latches 88 by means of
a data in control signal. Subsequent input words formed at the shift
register 74 are directed to appropriate ones of the latches 88 to form up
to a sixty-four bit data word. The skipping logic 84 controls the loading
of the latches based upon the attribute information, which is loaded into
a latch 92 and provided to the circuit 84. Data will be prevented from
being loaded into latches which correspond to failed data bus byte or
memory byte locations. The latches 88 will thus contain a word of up to 64
bits formed by a combination of one or more input words. When data is
being entered, each of the multiplexers 90 will be coupled to the input
data bus 80 and the appropriate latch will be enabled for each byte by
latch enable signals on lines 94.
The word stored in the latches 88 is provided to a masking buffer 96. Based
upon attribute information from the latch 92, the masking buffer
substitutes a known data pattern (e.g., all 1's) in failed byte locations,
i.e., locations which did not have an input data byte entered into them.
When a full system data word of sixty-four bits is assembled, including
the failed data byte locations, the encoding of error detection and
correction bits occurs by a check bits generator 98. The check bits
generator employs the well known Hamming code to generate eight check bits
which enable two errors to be detected and one error to be corrected when
the data word is later read out of memory. The reason for using a known
data pattern in the place of ambiguous data from the failed byte locations
is so that a predictable error detection and correction encoding can be
successfully performed. The check bits are entered into a latch 100 via a
multiplexer 102. The latches 88 and the latch 100 therefore contain the
overall data word to be stored in the memory 10 of up to seventy-two bits.
After the error detection and correction encoding is completed, a request
for the data bus 12 is made to the bus arbiter 24 (FIG. 1) from the
skipping logic 84 on a line 104. In addition, an extend cycle signal is
output on line 107 when merging of data is required. Once the bus grant is
made, an R/W signal on line 105 indicates whether a read from or write to
memory is being done. For writing the up to sixty-four data bits plus
eight error code bits equalling up to a seventy-two bit data word are then
written into the main memory at the location specified by the input
portion of the address generator 18. The granting of the bus by the bus
arbitration circuit 24 is provided on line 106 to the skipping logic
(followed by the R/W signal on line 105, extend cycle signal on line 107
of necessary, and latch signal on line 109), and the contents of the
latches 88 and 100 are then provided to the bus 12 via output multiplexers
108. The multiplexers 108 are provided so that the input and output
portions of the input and output circuits can share a common set of system
data bus pins. A signal on line 111 controls whether input or output data
is selected.
When the latch 92 contains information that the alternate EDAC byte is to
be employed, a multiplexer 110 selects the EDAC byte so as to shift its
position from its normal last byte of the data word to the next adjacent
byte. In such a case, input data words are combined such that the
alternate EDAC position (i.e., the eighth byte) is not employed for input
data.
The input process is modified whenever the input data must be combined wit | | |
