13
$\begingroup$

In the Smarter Every Day video How did NASA Steer the Saturn V?- Smarter Every Day 223 Destin is talking with Luke Talley about the memory modules used in the Saturn V LVDC computer.

This computer controls all the timing; start engine, stop engine, fire separation, fire retro rockets, all this kind of stuff.

It does navigation and guidance. You have stored in the memory a profile; at this point in time I need to be here going this fast in this direction[…]

Now when the Saturn’s flying, both of these memories are executing the same flight program, and they’re comparing the outputs to make sure that they’re getting the same answer.

If they’re were to not get the same answer, go into a subroutine and say ‘at this point in the flight I’ve got these two numbers, what makes the most sense to keep using, use that number to keep going.

Question: with triple redundancy you can (hopefully) choose to throw out one result if they disagree with the other two. However, what was the technique used to resolve potential disagreements between data returned from the two redundant memory modules used in LVDC systems? How to know "...what makes the most sense to keep using..."?

update: this link from @OrganicMarble is helpful, and explains that the IBM architecture provides two modes, called SIMPLEX and DUPLEX. Only in one mode was the memory redundant (the subject of my question) but it seems that during flight this mode was not used. Nonetheless I'm asking about the mode designed by IBM in which the two memory units would be used in a doubly-redundant fashion.


Related: Is this really the Saturn V computer only, or are there other systems here as well?

Smarter Every Day Saturn V LVDC memory Smarter Every Day Saturn V LVDC memory

$\endgroup$
  • 5
    $\begingroup$ Talley says quite clearly, that memory was double-redundant, processing was triple redundant. For memory, assuming a parity bit, if one unit encounters a parity error, use the other one and rewrite the good word back to where the error was to correct it. For processing, triple-redundant would be 2 of 3 voting. For the memory situation, single bit errors probably occurred infrequently, double-bit errors (in the same word) or single bit errors in the same word in both units was probably so unlikely that further protections would not have been worth the cost/complexity/mass budget. $\endgroup$ – Anthony X Aug 11 at 15:56
  • $\begingroup$ @uhoh: I don't know if you get notified about answer edits on SE, but my answer now deals with the whole parity thing after I did a bunch of reading. $\endgroup$ – tfb Aug 11 at 16:03
  • $\begingroup$ @tfb thanks for the ping, no it seems edits to existing answers don't generate flags to the OP so I wouldn't have known without your comment. It's now quite an answer, wow! $\endgroup$ – uhoh Aug 11 at 22:51
21
$\begingroup$

This answer is a guess based on NASA Technical Note D-5869: Description and performance of the Saturn launch vehicle's navigation, guidance and control system (referred to as 'D-5869' below), also the Launch Vehicle Digital Computer pages (referred to as 'LVDC' below) and finally the description in the video in the question (referred to as 'the video' below).

This is a heavily modified edit of a previous version of itself: I considered adding a new answer but I decided the old one was not interesting enough to keep.

In summary it looks as if at least four techniques were used, of which at least two apply to the memory system.

The system

First of all the computer itself (including registers &c but excluding main memory) was triple-redundant, so it could, by voting, detect internal errors.

It is not the case that each of the three copies of the computer had its own main memory: there was only one chunk of main memory which they all read (or which was read once and the data then sent to all three copies of everything).

The main memory system was core & so writable, and consisted of a number of modules, each of which was 4096 28-bit words divided into two 14-bit syllables (this is because you could fit two instructions per word). Being core meant that you could patch programs much later, but it also meant that it was less reliable than the non-writable memory in the AGC. You could use the memory in simplex mode or duplex mode, where there were two copies of everything.

The LVDC pages make the claim that the configuration used to run the Saturn ran in simplex mode. However there is clearly some confusion:

For the AS-206RAM LVDC Flight Program, a simplex model was required

and

One puzzle I don't understand, however, is the question of SIMPLEX vs DUPLEX memory configurations. Recall that there are two possible memory configurations, "SIMPLEX" and "DUPLEX". In DUPLEX mode, half of the memory is used to precisely mirror the other half, thus even though the same number of memory modules might be available in one as in the other, only half as much memory is actually accessible to the software in DUPLEX mode as in SIMPLEX mode. The two syllables of any given memory word generally are not identical, implying a SIMPLEX configuration. On the other hand, in the HOP constants we decoded above, we invariably found that the DUPIN and DUPDN bits are 1, implying DUPLEX mode. So obviously I'm confused about the DUPIN and DUPDN flags work.

(Both quotes from LVDC pages.)

We also have evidence from the video that the program ran in duplex mode.

I also think we can make a strong assumption that they would have run it in duplex mode if they possibly could have done: why would you not do something which makes the system more reliable and which costs nothing if the program is small enough?

I believe that the LVDC confusion can be resolved by assuming that the duplexing was at the word level, not at the syllable level: when the system was duplexed there are two copies of each word spread across two different modules, not two copies of each syllable in a single word. However I'm not sure this is right.

In what's below I will assume that the program did run in duplex mode, or more generally that programs could do this, and answer the question of how this would make them more redundant.

The mechanisms of error detection

There seem to have been at least four of these, not all of which apply to memory.

Firstly the computer itself, excluding main memory was triply redundant and had some kind of 2-of-3 voting system. This does not have any impact on the reliability of the memory, because the main memory was not triply redundant. D-5869 talks at some length about this and gives figures for how much this improves reliability at a cost of 3.4 in component count (3 for each copy, 0.4 for the comparison circuitry): (3R - 2R2)N where R is the reliability of a module and N the number of modules in the computer.

Secondly there were clearly sanity checks for data: D-5869 talks about detection of stuck values from accelerometers &c. An earlier version of this answer assumed that this technique could be used for memory checks, as a single bit error is likely to give an answer which is obviously insane). I think this is unlikely to be the case in fact as the program was running from memory (ie there was no ROM in this machine, as there was in the AGC), and instructions & memory addresses don't have the kind of continuity conditions that data from physical systems have.

Thirdly there was parity in the memory system. Each 14-bit syllable had a parity bit, so a 28-bit word had two parity bits. This means that any single-bit error in a syllable can be detected, and more than half (14/27) two-bit word errors can be detected. No errors can be corrected: there is no ECC (I'm not sure if ECC techniques for memory were in use by then).

Fourthly the program, by assumption, ran in duplex mode, each word being duplicated across two (perhaps four with one syllable in each) memory modules.

How duplexing improves reliability

And now we can answer the question. For simplicity I'm just going to think of it as if there is a single parity bit: in real life for duplexing at the word level we can do better than this.

I'll call the two halves of the memory L and R, and here is a table of the bad cases (as preformatted text, because Stack Exchange). The column headers are

  • LE: error in L
  • LP: parity detects error in L;
  • RE: error in R;
  • RP: parity detects error in R;
  • EB: number of bits that must be flipped
    • n means exactly n,
    • n+ means n or more,
    • n+? means n and some combinations of more than n
  • result: the result
    • OK means can carry on with a comment on which side should be used,
    • panic means an error is detected but we can't carry on from here unless we know how to sanity-check the data somehow,
    • bad means an undetected error.
LE  LP  RE  RP  EB  result
N   N   N   N   0   OK (either)
Y   Y   N   N   1+? OK (use R)
Y   N   N   N   2+  panic (R is right but we can’t know it is)
N   N   Y   Y   1+? OK (use L)
Y   Y   Y   Y   2+? panic (both sides in error)
Y   N   Y   Y   3+  bad (undetected >= 2-bit error in L)
N   N   Y   N   2+  panic (L is right, but we can’t know it is)
Y   Y   Y   N   3+  bad (undetected >= 2-bit error in R)
Y   N   Y   N   4+  if equal then bad (two identical undetected >= 2-bit errors)
                    if not equal then panic (we know there are errors
                    but not what they are)

Note that:

  • all single bit errors are recovered from;
  • all errors with 2 bits are either recovered from or cause a panic;
  • no error of less than 3 bits goes undetected.

whereas in simplex mode:

  • all single bit errors cause a panic;
  • some 2 bit errors go undetected.

So, in the presence of parity, duplexing does significantly improve reliability. I have not tried to do any computation of how likely the various possibilities are: I am sure NASA did this though!


A counterfactual possibility: ECC

One thing they could have done is to use ECC in the memory. This would have achieved the same reliability as duplexing. But:

  • it does not protect against the wholesale physical failure of a module in the way duplexing does;
  • it requires more complex logic I think;
  • it may just not have been known about when this machine was being designed.
$\endgroup$
  • 1
    $\begingroup$ Great analysis! $\endgroup$ – Organic Marble Aug 11 at 16:26
  • $\begingroup$ Wow!! Thank you for taking the time to write such a thorough and thought-out answer! I'm going to need some time and coffee to step through this ;-) $\endgroup$ – uhoh Aug 11 at 22:52
  • 2
    $\begingroup$ I would regard the use of dual memories combined with the use of parity to auto-select which copy to believe as a form of ECC which has 114% overhead. Rather high, but the ability to recover from certain systemic failures as well as single-bit errors would add considerable value. $\endgroup$ – supercat Aug 12 at 16:16
  • $\begingroup$ @supercat: well, I think 'ECC' may have some restrictive technical meaning which excludes what they did, but yes, I agree, especially given the ability to recover from a large-scale failure (a whole memory module failing say), which conventional ECC does not get you. $\endgroup$ – tfb Aug 12 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.