DE2609064C3 - Circuit arrangement for performing reconfigurations of the hardware structure of a programmable digital computer (bit field transfer unit) - Google Patents

Description

The invention relates to a circuit arrangement according to the preamble of claim 1.

For the economical use of digital computers and the correct execution of the by the user prescribed operations, a high level of availability and integrity is an essential requirement! That will be despite the finite lifetime and The large number of electronic circuits and storage elements that make up the computer are susceptible to failure

h

and to correct the errors caused thereby or to mask them from the start.

It is known (W, W, Peterson, PrOfbare and correctable codes, R, Oldenburg Verleg, Munich / Vienna, 1967), for monitoring both data storage and transport functions as well as error-detecting codes from some data-changing functions to prevent the occurrence of a bit pattern error during normal program operation of a Recognize the computer and the execution of a diagnostic program cause that localizes the faulty component, so that e.g. a manual Exchange can be made.

It is also known (W. W. Peterson, Verifiable and Correctable Codes, R. Oldenburg Verlag, Munich / Vienna, 1967), especially those caused by data storage and transport Bit pattern errors with the help of error-correcting codes to be corrected immediately and thus to mask the cause of the error.

The use of error-detecting or error-correcting codes is essential in order to be able to do so sporadically to handle occurring bit pattern errors that are not necessarily due to permanently defective Harwatre components are due. In particular, error-reporting codes remain due to the effort involved Codes and correction circuits limited to the correction of 1-bit errors, i. h, it can only be proportionate small improvements in reliability can be achieved.

In order to achieve a high level of invoice reliability against permanent component defects, the Method of triple-modular redundancy known (W. H. P i e r c e, Failure-Tolerant Computer Design, Academic Press, New York / London, 1965.) It is based on three similar components under completely identical ones Conditions to operate and with the help of a Voterschaltung the outputs of the three components evaluate. If the bit patterns of at least two of the three component outputs are the same, then this bit pattern becomes considered correct and processed further. This misalignment can be because of the extremely high Hardware costs are only of limited importance. To achieve the highest levels of reliability "standby" redundancy is known (IEEE transactions on Computers, Vol. C-20, no. 11, Nov. 1971, pp 1312-1322). Here, in addition to the components in operation, identical reserve components are used kept ready to take over the function of failing components.

This form of redundancy is particularly useful in the design of fault-tolerant semiconductor memories. So z. B. in US-PS 38 98 443 and in DE-OS 23 25 137 proposed to provide a reserve component for a certain number of memory components. If a fault is detected in one of the components in operation, it is logically switched off and the reserve component is logically switched off in the position of the defective component via a crossbar switchgear.

According to a method known from US Pat. No. 3,934,237, “standby” redundancy is used for a memory through this . ealisiert that an additional memory is provided, in the ι lit help of an address conversion mechanism Address ranges of the incorrect Konponenicn containing Storage can be migrated.

The disadvantages of these known devices are in particular that additional memory capacity in the form of additional memory modules (bit slices) or in the form of an additional memory must be kept ready and that a relatively complex switching mechanism is required, with the help of which a reserve component is switched to the position of a faulty component can be, and that this switching mechanism must be particularly expensive and complex if the failure of several components by providing a corresponding number of

ίο reserve components are to be compensated.

In connection with the development of multiprocessor computing systems is another method of achieving a high tolerance for hardware defects has been proposed as "graceful

is degradation «. It consists in a system made up of several identical processors and memory segments Processors and memory segments in which permanent hardware defects occur can no longer be allocated or the functions originally assigned to them by the system to identical, intact modules transferred and thus the total / oir available to reduce the standing hardware structure. Although this has a reduction in computing power - possibly up to the replacement of the defective modules - the consequence, but does not lead to a complete one System failure.

The principle of "graceful degradation" can be transferred to the regular two-dimensional cellular structure of the main memory or the one-dimensional bit slice structure of the processor of a computing system, if suitable facilities are available to logically switch off defective cells or bit slices and their To have functions carried out by intact cells or bit slices of the same type. This is how it becomes possible to carry out "graceful degradation" in single-processor systems with unsegmented main memory. This is an emulation problem in which the complete structure of the computer is in the In the event of defects in memory cells or in process orbit slices by means of suitable reconfiguration on a reduced structure is emulsified, and that is therefore solved at the level of microprogramming must become.

The invention is based on the task of reducing a given computer structure error-free working components with the help of micro-programmed Reconfiguration through suitable circuitry additions in the computer in such a way

support so that the additional time required to carry out error-correcting micro-operations kept as low as possible and the hardware expenditure compared to known devices of the invention Kind is significantly reduced.

According to the invention, this object is achieved by the circuit arrangement specified in the characterizing part of claim 1. Further developments of the invention are characterized in the subclaims
The advantages of the circuit arrangement according to the invention are that the breakdown of data words into individual bits or bit fields necessary for error correction and their correct positioning when inserted into a second data word or the assembly of data words from individual bits

e> -> or bit fields with a minimum of additional Micro-operation steps can be made and that by the arrangement of the bit field transfer unit at the interface between main memory and

Processor during data transfer errors that occur in the respective source module can be corrected before the data host is transferred to the sink module and data words before transfer to a defective one Sink module can be adapted to the defect.

An exemplary embodiment of the invention is shown in Drawing shown and is described in more detail below.

It shows

F i g. 1 shows a schematic representation of the correction of bit plane defects in the main memory,

Fig. 2 is a block diagram of the bit field transfer unit and its arrangement at the interface between Processor and memory.

To illustrate the operation of the circuit arrangement according to the invention, the principle of micro-programmed reconfiguration based on the correction of defects in the main memory and the Correction of processor defects explained in detail.

The basic building block of a main memory is generally a module consisting of an arrangement of 2 * binary memory cells with consecutive addresses, e.g. B. a core memory matrix or a semiconductor memory chip (MOS). A memory of 2 "(N> k) words of capacity and 2" (3 <n <N) bits of word length is accordingly made up of 2 ^N ~ ^k blocks of 2 "of these modules, which cover the same address range two stages, of which the first identifies the respective memory block and the second identifies the memory word within a block. An address bus line consisting of N lines supplies the address code to the address decoding logic, and a data bus line of 2 "lines takes over the data transport between the memory cells and the data buffer register of the Memory.

Corresponding to this physical structure of the memory there are three idealized defects, all of which are real occurring defects can be traced back to distinguish.

1) The defect of a memory module causes the failure of a bit plane segment in an address area between the addresses g ■ 2 * and (g + 1) ■ 2 * -1.

2) The defect of a line within the data bus causes the failure of the corresponding one complete bit plane.

3) The defect of a conduit within the address bus leads to the failure of a total of 2 ~ ^{N l} memory cells .en in a periodic pattern over ^ entire address area are distributed.

Diagnostic methods for the detection and localization of these defects are known from DE-OS 23 25137 and US-PS 38 98 443. B. expedient, after a hardware defect has been recognized by an error-detecting code, to test the entire memory or a memory segment in that a diagnostic program first describes each memory word cell with its own binary-coded address in a first run and then reads out all cell contents again, and then describes in a second pass per ZeDe with its complementary address and then also all cell content again reads in this way all of the memory word cells are tested, each with unique bit patterns that each bit position of a memory word with both "0" also described as having "I" will. The bit-by-bit comparison of the codes read from the memories with the associated address codes not only localizes incorrect binary digits, but also detects and localizes incorrect addressing.

The basic method for correcting the first two defects is for memory areas special correction bit fields with defective bit planes

ίο to be created in another suitable memory area and there to store those bits of complete data words that coincide with the defective bit planes. Correspondingly, a data word read from such a memory area must be defined by bits the correction bit field, and from a to be written into this memory area In the data word, the bits that coincide with the error must be extracted and written separately into the correction bit field will.

2n In the case of a defect in bit plane segments of the Length 2 * it can be assumed that there are still blocks of length 2 * in the memory, in which complete data words can be saved without errors. One or more contiguous Blocks of this kind are used as a correction bit region in which correction bit fields are used in the following manner be created:

The defect of a memory module in the address range g- 2 * ... (g ■ 1) · 2 * - 'affects a memory capacity

jo of 2 * bits, which can be accommodated in a correction bit field of 2 ^k ~ "words.

To simplify the addressing of the correction bit fields, regardless of the number of bit segment defects actually occurring, a correction bit field in a contiguous memory region of 2 ^h (h = 0, 1, 2, ...) physical blocks is used for each of the 2 ^N ~ ^{k physical memory blocks} Start address should be an integer multiple of 2 ^{A +} *, reserved. Starting at this base address, the following address space is subdivided into 2 ^N ~ ^k fields of 2 * - "memory words in such a way that the / -th field contains the correction bits of the / -th physical memory block and, more precisely, that the y-th word in / -th field and in it the / -th bit the error-coincident bit of the under the address

This means that the address of the correction bit can be taken directly from the address of the data word itself.

As in Fig. 1, the first N-k bits of the address are identical to the address of the correction bit field relative to the base of the correction bit region CBR, the subsequent k-n bits address the word within the correction bit field CBF, and the last π bits address the bit within of the word.

In order to carry out this correction procedure, it is also necessary, in a suitable third place in the Storage or in a separate, quickly retrievable

μ Associative memory to create an error table, which as Entries the addresses of the physical memory blocks with bit plane defects as well as the contains the respective bit positions of the defective bit planes. New entries in the table are made by

6 '> carried out the diagnostic program following Error detection is activated to identify the faulty bit plane and the affected address area to locate. The correction is carried out as follows:

Should ζ. If, for example, a data word is read from the memory at the physical address ρ, a normal memory access is first carried out. With the help of the block address' .- ils / the address ρ, the error table is searched in order to determine whether the generated address is in a memory area impaired by bit plane defects. If this is the case, the data word read from the memory under the address ρ is initially temporarily stored outside the memory in a suitable second register. A second memory access is then carried out with an address which is formed by addressing the most significant Nn bits of the address ρ to the least significant N-n bits of the base address of the correction bit region CBR . From the word read out at this address, which is temporarily stored in a suitable first register outside the memory, the position of the correction bit is determined with the aid of the least significant π bits of the address ρ. A suitable device extracts the correction bit from the first register and inserts it into the bit position of the data word contained in the second register, which is determined by the corresponding entry in the error table.

The second data register now contains the correct data word, which can be further processed in the usual way.

If the address ρ is in an error-free area, ie if there is no entry in the error table, then the data word read out under the address is error ^r rei. The described intermediate storage and access to the correction bit region are omitted, and the data word is processed further directly.

When a data word is stored under the address ρ , a normal memory access is also carried out first. At the same time, the data word is temporarily stored in the first register located outside of the memory in each case. In addition, the entries in the error table are checked again with the help of the block address part / address ρ and, if there is an incorrect memory region, the corresponding correction bit word is read out in a second memory access in the manner already described and placed in the second register outside of the memory. The error-coincident bit is now extracted from the data word of the first register and inserted into the provided binary position in the correction bit word contained in the second register. The new content of the second register is then stored again under its original address in the correction bit region.

In the event of a complete failure of a bit plane, the specified correction method must be modified to this extent are, as in this case nowhere in the memory a complete data word stored and consequently the correction bit fields cannot be created in their previous form. Therefore, only memory half-words are used to store the correction bit fields is used, namely left half-words if the bit plane failure is in the right half of the word and vice versa. This doubles the address space required for the entire correction bit region, but the addressing mechanism remains essentially the same.

The defective line within the address bus can be corrected in a similar way. Since the available address space is independent of the Bit position of the defect shrinks to half, a pseudo address space between the addresses 0 and 2 ^ ^{-1 is assigned} by the memory management, ie all addresses whose most significant bit contains a 0.

This pseudo address space can be mapped to the one that is actually still available as a result of the defect physical address space by converting the address bit that coincides with the defective address line into the most significant

ίο address bit position is used before memory is addressed if the defective address line does not coincide with the most significant bit anyway.

The correction methods for these three types of memory defects have in common that one bit from one appropriately specified bit position of a first data word is extracted and converted into a likewise specified Bit position of a second data word is used. In the case of defects in several bit planes, this can be several Concern bit positions. So it is also conceivable that specified method on a dsr basis of nibbles (contiguous fields of four bits), bytes (fields of eight bits) or half-words.

In principle, the same methods can also be used to resolve the issues caused by defective bit slices of the Correct the error caused by the processor. In the case of a defective bit slice of the arithmetic / logical functional unit, z. B. with logical operations that are carried out bit by bit via the operand data words to perform the operation as usual be executed, in which case the defective bit slice corresponding binary digit a faulty bit is to be expected in the result word. To correct this, the operation can e.g. B. with one or more binary digits to the left or right nen operands are repeated so that that in the first operation with the defective bit slice, bits that coincide now on an intact bit slice is calculated. This bit is then extracted from the result word obtained and converted to the correct one Binary digit of the result word received in the first operation is used. Alternatively, this is possible and in arithmetic operations with carry formation it is also necessary to have the operations on To execute operand halfwords, with the left Half of the arithmetic / logical unit is used, if the defective bit slice is in the right half and vice versa a first data word z. B. to extract the right half of the word and in a second data word in the left

so to use half of the word.

With a view to the fastest possible execution of the overall micro-operations required to correct a defect, it is necessary to set the bit or Bit field transfers if possible within a machine clock cycle through a special bit field transfer unit unwind. Because of its dual function of correcting memory and processor defects this unit is expediently arranged at the interface between the processor and memory

A schematic representation of the bit field transfer unit is shown in FIG. 2.

Two data registers Rt and R 2, which in the exemplary embodiment each comprise 32 binary digits, form essential components of the bit field transfer unit.

To carry out a Bh (field) transfer, the data word from which the bit field is to be extracted is placed in data register R 1 and the data word in which the bit field is to be inserted is placed in data register RI

loaded. A full data word, via the lines 32 comprehensive data bus Bl from the data buffer register MBR of the memory both in the data register R 1 can also be loaded into the data register R.sub.2. The data word contained in the data register R 2 can be transferred both to the memory address register MAR and to the data buffer register MBR via a second data bus line B 4 , also consisting of 32 lines. In the exemplary embodiment, devices are provided for transferring both individual bits and bytes (fields of eight bits) and half-words from data register R 1 to data register R 2 . These devices are a data line dl, which consists of a single line for transferring a bit, a data bus line B2, consisting of 8 lines via which a byte can be transferred, and a data bus line B 3 for transferring a half-word and a 5-bit address register A. 1 for addressing individual bits, bytes or words in data register R i, a 5-bit address register A 2 for addressing individual bits, bytes or half-words in data register R 2 and a 2-bit control register BB, with the help of which between bit addressing (BB is set to 00 ), byte addressing (BB is set at 01) and half-word addressing (BB is set to 10) can be discriminated. The address registers A 1 and A 2 can be loaded from the five least significant binary digits of the data buffer register MBR via a data bus B5 comprising five lines, while the control register BB is set from the control unit of the computer via line B 6.

If the check register BB set to 00, all the five bits of the address registers A 1 and A 2 are used to address one of the 32 binary digits of the registers R i and R 2 used in the case of byte addressing, that is, when the control register BB is set at 01 , only the two most significant bits of registers A 1 and A 2 are used to address one of four bytes in registers A1 and R2 . In the case of half-word addressing, that is, when the control register BB is set to 10, the address register A 1 and A 2 is for addressing a use of two half words of the data registers R 1 and R 2 only from most significant bit of the address decoder are in F i g. 2 not shown.

The mode of operation of the bit field transfer unit should now be based on the reading out of a data word from a memory area affected by a bit-plane defect will be explained.

The processor generates a physical address, the code of which is loaded into both the memory address register MA R and the data buffer register MBR. If a comparison with the error table shows that the address is in a defective memory area, the five least significant bits of the address, which also indicate the bit position of the correction bit in the associated correction bit word, are transferred to the address register A1. The control unit also sets the control bit BB to 00. After the memory access has been carried out, the data word which is incorrect in the bit position coincident with the bit plane defect is in the data buffer register MBR, from where it is transferred to the data register R 2 . The address calculation for the correction bit word is now carried out in the processor, the memory access is carried out with this address and the correction bit word is loaded into the data register R 1. The processor also creates the address of the bit position of the bit plane defect for the corresponding entry in the error table and inserts this into the address register A 2 . Let the address contained in the address register A 1 be 21, the address in the address register A 2

π address contained was 12 will now be decodes the addresses contained in the address registers A 1 and A 2, the contents of the 21 bit location of the data register R 1 to the Datensamme: oil line B 1 and transferred from there to the 12th bit location of the register R 2 taken over, jeizi emriäii daü Daienregister R 2 the corrected data word which is now reloaded into the data buffer register MBR , from where it can be taken over by the processor.
When transferring bytes, only the most significant two bits of the address registers A 1 and A 2 are decoded, the addressed byte of the data register R \ is transferred to the data bus B 2 , from where it is transferred to the byte of the addressed by the content of the address register A 2 Daterircgisters R 2 is taken over. This process is indicated schematically for the transfer of the byte between the binary positions 8 and 15 of the data register R 1 and the binary positions 24 and 31 of the data register R2.

The bit field transfer unit can be expediently supplemented by various measures. It is conceivable, the unit with a buffer memory comprising two to four registers for correction bit words equip. This allows when accessing several immediately consecutive addresses like this

z. B. is the case when running through instruction sequences, repeated memory accesses for procurement of the corresponding correction bits are avoided so that the program run can be accelerated.

The advantage of arranging the bit field transfer unit at the interface between the processor and the main memory lies in the fact that the errors in data words caused by defects in the processor and / or in the memory can be corrected during the transfer via the interface and that data words are defective

so handover to the appropriate unit can be customized.

It is therefore also possible to use several processors, e.g. B. channels, or additional memory segments to be connected, the possible defects of which could also be corrected by the bit field transfer unit. The control of the unit is expediently taken over by the control unit of the processor, which exercises control over the memory buffer register MBR

For this purpose 2 sheets of drawings

Claims (1)

Claims; I, circuit arrangement for deploying reconfigurations of the hardware structure of a programmable digital computer in the event of permanent defects in memory and / or switchgear components that have been identified with the help of error-detecting codes and then localized with a diagnostic program to a reduced structure in which the defective components and their functions are not used are transferred to similar 'intact components, characterized in that a bit field transfer unit (1) is connected between the processor and the main memory, that the bit field transfer unit (I) consists essentially of a bit-byte and half-word addressable first data register (RX) of word length and a bit, byte and half-word addressable second data register (R 2) of word length, that the first and the second data register (RX, R2) are connected via data transmission paths (BX, B 2, B 3) in such a way that within one Machine cycle every bit, byte or r half-word can be extracted from the first data register (RX) and inserted into a predetermined bit, byte or half-word position of the second data register (R 2) that a data buffer register (MBR) of the main memory is connected to the inputs of the first data register (RX) and to the Inputs of the second data register (R 2) is connected, so that a data word from the data buffer register (MBR) is optionally in each of the two data registers (R% R2) '. Transferbaren that the outputs of the second data register (R 2) with the Inputs of the data buffer: register (MBR) and the inputs of a memory address register (MAR) are connected, so that a data word from the second data register (R 2) can either be transferred to the data buffer register (MBR) or the memory address register (MAR) of the computer has a correction bit region for storing the bits that coincide with the defective bit planes, that one read from a faulty address area Data * word via the data buffer register (MBR) in the second data register (R 2) is inscribed in that of the Korrekturbitregion the associated Korrekturbitwort via the data buffer register (MBR) in the first data register (RX) is transferable, that with a addressing correction bits or bit fields from the first data register (RX) can be inserted into the error-coincident bit positions of the data word in the second data register (R 2 ) via one of the three data transmission paths (BX, B2, B3) and the processor can transfer the corrected content of the second data register (R 2) via the The data buffer register (MBR) assumes that a data word written in an error-prone address area of the main memory can be transferred to the first data register (RX) at the same time, that the second data register (R 2) is set up to accept the associated correction bit word, that the error-coincident bits or bit fields are removed the first data register (RX) via one of the three Data transmission lines (BX, B1, B3) can be transferred to the second data register (R 2) and the content of which is stored in the correction bit region so that the bit field transfer unit in a corresponding manner data words that are either generated by a processor impaired by bit slice defects or transferred to it, combines or disassembles and is only active during operations in faulty memory regions or processor elements, Z circuit arrangement me claim!, Characterized in that the first data register (RX), a first address register (AX) with decoding logic and the second data register (R 2) is assigned a second address register (A 2) with Delcodierlogik that each of the two address registers (A 1, A 2) π binary digits and each of the data registers ( R 1, R 2) 2 " Has binary digits, so that with the contents of the address register (AX, A 2) each binary digit of the respectively assigned data register (RX, R2) can be addressed, so that at least one control register (BB) on the input side via a data line (B 6) with the Control unit of the computer is connected and can be set by the control unit, and on the output side it is switched to the control inputs of the first and second address registers (A i, A 2), so that the same addressing devices are also used Contiguous fields of 8 bits (bytes) and 2 "- <bits (half-words) can be addressed so that the outputs of the least significant η binary digits of the data buffer register ^ AißÄ ^ over the data bus (BS) to the corresponding inputs the / 7 binary digits of the first and second address registers (AX, A 2) are switched. 3. Circuit arrangement according to claim 1 and 2, characterized in that a first data line (BX) consisting of buckets of conductors output side tig is connected to each binary digit of the first data register (RX) in such a way that the content of an addressed binary digit of the first data register (RX) can be transferred to the addressed binary digit of the second data register (R 2) Data line (B 2) consisting of eight conductors, on the output side with each of the 2 "-« byte fields of the first data register (RX) and on the input side with each of the 2 ^a ~ ³ byte fields of the second data register (R 2) is connected in such a way that the content of a addressed byte field of the first data register (RX) can be transferred to the addressed byte field of the second data register (R 2) and that via a third data line (BB) consisting of 2 "conductors, half-word fields from the so the first data register (RX) can be transferred to the second data register (R 2) .