Computational requirements to land a booster.

[nicp]

How much computational power does a Falcon 9 carry in order to land?

As I understand it, Falcon 9 uses 'Kalman filters' in its landing system. I'm a software engineer, not a mathematician but as I understand it a Kalman filter is a mathematical approach to getting excellent 'best guess' information (position, velocity, etc) from noisy inputs.

An old friend of mine (sadly no longer with us) was a Phd in mathematics - and worked on missile systems. He probably told me far more than he should have over a pint or three, but one thing I do recall him saying is that Kalman filters are computationally very expensive.

These days of course a few giga-FLOPs costs nothing, so what level of computer hardware are we talking about here? Could a Raspberry Pi do it? (I would guess 'yes').

As an aside (and I believe this has been discussed somewhere on the forum but I can't find it) - I am personally convinced a booster could have been landed maybe in the 70's - but not using the same approach. If a BAC Trident can do a blind landing (with passengers) in 1966 (which I bet was an analogue system) then something along similar lines could surely have been done to land a booster.

[FutureSpaceTourist]

I’m afraid there’s not a lot in the public domain on this.

The attached article gives some hints / pointers on what F9 does. Note that the article has its own thread: https://forum.nasaspaceflight.com/index.php?topic=41935.0 so best to follow-up on it there.

[edzieba]

For Falcon 9 specifically, I'd wager computational requirements are a LOT lower than many would assume. The problem is not a complex one to solve in and of itself (the complex part is tuning the control parameters), and it is a relatively 'slow' process to control (i.e. you have milliseconds to seconds to react, you're not trying to do anything crazy down in the nanosecond to picosecond range). I'd also wager that commodity microcontrollers would be suitable - beyond rad hardening requirements - rather than needing FPGAs or custom ASICs.

However, throwing computational power at a simple problem does have benefits, mostly in development speed and ease. We already know that Falcon 9 runs on a voting trio of dual-core x86 CPUs - plus the engine management controllers, one per engine - more than enough grunt to run the landing control software. That extra overhead lets you throw in plenty of monitoring and debugging, lets you retune parameters in real time, and generally means your software can be written and maintained in a sane manner with modern software development practices, rather than via summoning a chasing-the-beam-grade greybeard to delicately deposit bits into a limited memory and cajole instructions into a predetermined sequence to fit within clock intervals.

A lot of the simplicity of the control problem comes from the availability of accurate GPS. It means "where am I? Where is my landing point?" is answered immediately by a nice pair of coordinate strings with a pretty damn good accuracy, available throughout the flight regime. Once SpaceX start getting into Moon and Mars landings, they now need to deal with the problem of finding your position relative to a landing site where you do not know a priori where either you or the landing site are. That is now an optical (or SAR) SLAM problem, and throwing as much computation as you have available at one of those is never a bad thing. Though this is not a new problem, and there are several development efforts towards pinpoint landing from optical data (e.g. ALHAT on Morpheus). This is also a realm where availability of cheap commodity ML-acceleration hardware makes things much cheaper than a few years ago.

In terms of 'could a booster have propulsively landed in the 70s', I'd say pretty strongly 'yes', if a dedicated position tracking system were produced alongside it to provide precise and up-to-date position information to the landing booster in real-time (not an enormous task, really, given contemporaneous AESA capability). Otherwise, waiting until the availability of accurate GNSS would be a prerequisite. The other requirement would be focussed research into control theory to apply known 1D solving strategies to 3D problems. Nothing that would have been impossible in the 70s, but it wasn't something anyone had already worked out at the time.

[launchwatcher]

However, throwing computational power at a simple problem does have benefits, mostly in development speed and ease. We already know that Falcon 9 runs on a voting trio of dual-core x86 CPUs - plus the engine management controllers, one per engine - more than enough grunt to run the landing control software. That extra overhead lets you throw in plenty of monitoring and debugging, lets you retune parameters in real time, and generally means your software can be written and maintained in a sane manner with modern software development practices,

The cited Raspberry Pi systems, while relatively small and cheap on the outside, are not small in historic terms.  The Broadcom System-on-a-Chip models used in the Pi were apparently developed for embedded tasks like TV set-top boxes which requires no small amount of horsepower to decrypt and decode video streams.

Never played with one myself, but the biggest looks to be a quad-core 64-bit ARM CPU running at 1.5Ghz with up to 8GB of memory; smallest is about 8 years old and has a single CPU and a "mere" 256 MB.   Looks like decent floating point in the CPU -- probably more than enough for double-precision Kalman filters -- plus a GPU if they need lots of single-precision oomph.   My sense is that they're probably a little shy in the I/O department for managing all the sensors and actuators.   

That said, using x86 on-board means you can efficiently run the exact software image you'll load on the rocket in virtualization on developer desktops, server farms, cloud, etc.; ARM servers are becoming more common these days but at the time SpaceX picked a CPU, x86 was the safe bet.

rather than via summoning a chasing-the-beam-grade greybeard to delicately deposit bits into a limited memory and cajole instructions into a predetermined sequence to fit within clock intervals.

Modern architectures, with out-of-order speculative execution supported by multiple layers and kinds of cache, branch prediction, etc., make trying to find the optimal instruction sequence a fool's game in most cases.   Over the life of the system, half of the caches will end up disabled or degraded to fix security holes, and the next rev of the chip is going to do it differently anyway..

[dglow]

For Falcon 9 specifically, I'd wager computational requirements are a LOT lower than many would assume.

We had a rather infamous thread, years ago, that touched on this exact question. One of the old-timers asserted the Shuttle flight computer, a custom IBM design of of mid-'70s vintage, could successfully land a Falcon 9 booster. This was in the context of a larger argument that NASA could have done flyback booster return, years before SpaceX, as part of Shuttle development if only it had been a requirement.

As I recall it was somehow revealed that most of the F9 booster's landing solution is pre-computed, in advance, on the ground.

However, throwing computational power at a simple problem does have benefits, mostly in development speed and ease. <snip> That extra overhead lets you throw in plenty of monitoring and debugging, lets you retune parameters in real time, and generally means your software can be written and maintained in a sane manner with modern software development practices...

Yes yes yes. It's all about the development ecosystem and practices enabled by modern hardware, operating systems, and the tools that accompany them. State of the art compilers, debuggers, and especially CI will get better code and faster iteration out of your team. It'll be a happier team, too. 

rather than via summoning a chasing-the-beam-grade greybeard to delicately deposit bits into a limited memory and cajole instructions into a predetermined sequence to fit within clock intervals.

Modern architectures, with out-of-order speculative execution supported by multiple layers and kinds of cache, branch prediction, etc., make trying to find the optimal instruction sequence a fool's game in most cases.   Over the life of the system, half of the caches will end up disabled or degraded to fix security holes, and the next rev of the chip is going to do it differently anyway..

This.

Leave it to the compiler's optimizer. LLVM FTW

[jebbo]

Never played with one myself, but the biggest looks to be a quad-core 64-bit ARM CPU running at 1.5Ghz with up to 8GB of memory; smallest is about 8 years old and has a single CPU and a "mere" 256 MB.   Looks like decent floating point in the CPU -- probably more than enough for double-precision Kalman filters -- plus a GPU if they need lots of single-precision oomph.   My sense is that they're probably a little shy in the I/O department for managing all the sensors and actuators.   

The original 2830-based one is more than 8 years old as myself & Eben defined it at Broadcom in Cambridge, and I've not worked for BRCM for ~10 years :-)

The newer versions have vector FP, so oodles of performance but the original didn't have very much FP at all as the area budget for the core was tiny.

That said, using x86 on-board means you can efficiently run the exact software image you'll load on the rocket in virtualization on developer desktops, server farms, cloud, etc.; ARM servers are becoming more common these days but at the time SpaceX picked a CPU, x86 was the safe bet.

Arm has a significant power advantage over x86, which doesn't matter too much for boosters but will for longer duration stuff.

Modern architectures, with out-of-order speculative execution supported by multiple layers and kinds of cache, branch prediction, etc., make trying to find the optimal instruction sequence a fool's game in most cases.   Over the life of the system, half of the caches will end up disabled or degraded to fix security holes, and the next rev of the chip is going to do it differently anyway..

Nah. I don't think I've seen a single mitigation that disables caches (the v early Spectre/Meltdown stuff did some nasty things to branch predictors and TLBs but only because Intel had made some very poor design choices).  Most mitigations are around kernel calls etc and essentially are speculation barriers, so they are very unlikely to affect main-line code paths like filters (it is unclear why a closed system would need to protect against speculation attacks).

But the broader point is correct: hand tuning the code is pretty pointless; just rely on the compiler.

--- Tony

[alexs]

As I understand it, Falcon 9 uses 'Kalman filters' in its landing system. ... I do recall him saying is that Kalman filters are computationally very expensive.

Apollo guidance system used Kalman filters. In terms of performance, AGC would be roughly comparable to ATmega, the
microcontroller used in Arduino. And comparable in this case means just several times slower, as in, not orders of magnitude.

https://github.com/chrislgarry/Apollo-11/blob/master/Luminary099/KALMAN_FILTER.agc

I'd wonder if a mid-range STM32 would be enough to land F9, but somehow I think the answer would probably be a solid yes.

Modern computers are just so small and so light it doesn't really matter they are using grossly overspecced hardware just because they find it more convenient to work with or something like that. From what I recall from their (SpaceX) software presentation, I'd guess they are not limited by the available computational resources in the slightest.

[Remes]

Kalman Filters are considered expensive, as one has to calculate the inverse of a matrix. As more states are tracked, as more complex the calculation gets. But it's not taken without good reason: Having a physical real world model in the filter, having build in handling of stochastic signals, having the ability to react on input values, beeing able to calculate non measuerd values, etc all in one algo, makes it worth it.

As said, a Kalman Filter was used in the command module and the lunar module. They where implemented in fixpoint, leading to much lower requirements in hardware (no floating point unit). Somewhere in the 2000's I had my last fixpoint project.

The overall control of position, attitude, etc, will run relatively slow, in the area of 10's of ms cycletime. There is no point in beeing faster, as the rocket can't be swiveled faster with a faster computation. Actuators need time to reach actuator values. And this low cycletime allows some Kalman Filters to be even executed on Apollo era hardware.

The main computer is one thing. Many other subsystems have nowadays their own processors.

I don't now, how they control all the valves on the engines. Might be, that there are on/off valves or valves having two mechanical stops. But controlling hydraulic servovalves linearly (i.e. you can command every value between -100%..100%) requires cycletime in the are of 10's or 100's of microseconds for the coil current, then going up for velocity/position control of the spool. (For the space shuttle tvc no computer was used. 4 servovalves received a current signal. From there on all control was fully mechanical. The 4 valves acted on a spool, the spool acted as the main valve for the piston. The piston would pull a wire, which brought the 4 servovalves back to zero, when the actaution value was reached).

For landing they use radar. There is also quiet some computation necessary to get from reflections to object hypothesis. There is an IMU which will most likely have their own cpu.

I think having a few cpu with floating point in the range of few 100MHz should be enough. Even if SpaceX is not using radiation hardened cpu, it will be still some design which is less susceptible to radiation. Hubble used 486.

rather than via summoning a chasing-the-beam-grade greybeard to delicately deposit bits into a limited memory and cajole instructions into a predetermined sequence to fit within clock intervals.

Modern architectures, with out-of-order speculative execution supported by multiple layers and kinds of cache, branch prediction, etc., make trying to find the optimal instruction sequence a fool's game in most cases.    [...]

...
Leave it to the compiler's optimizer. LLVM FTW

I go with processor designer Jim Keller: "Some people say, that a processor should have a perfectly clean design. From my experience I can say, that there is no market for clean and slow pocessors".



Caches will stay. Out of order execution will stay. And on top compilers will produce more and more efficient code.

[edzieba]

In terms of performance, AGC would be roughly comparable to ATmega, the microcontroller used in Arduino. And comparable in this case means just several times slower, as in, not orders of magnitude.

Best figure I can find for the AGC is 80k instructions per second (0.08 MIPS). A basic Arduino Uno (a ATMEGA4809) is ~20 MIPS, so yes orders of magnitude. Dang near any uC you can buy today beats the pants off of the AGC in terms of raw computational performance.

[alexterrell]

Not related to the computing power ON the Falcon, but now the identical software as used to control the Falcon 9 can also control a simulation of the Falcon 9 in a computer model, where various external influences can be tested.

This means that before a first flight, the flight can be run hundreds of times in a simulator. I very much suspect that SpaceX destroyed hundreds of virtual Falcon 9s, before trialling something on a real system.

I'm not sure how long this technology has been around - probably since the introduction of Advanced Flight simulators in the 1980s, and perhaps perfected for Advanced Gaming in the 2000s. (Here's an article about using Grand Theft Auto to teach self driving cars to drive: https://www.newscientist.com/article/mg23230970-200-playing-can-teach-autonomous-cars-how-to-drive/)

Without this, software in the 1970s could have landed a booster, but it could never have been developed.

New technology and big processors make things a lot easier, and easier to check. Like checking calculations in Excel compared to checking them in Assembler. For example, if you want to calculate rocket pitch, would you once have needed a sensor to detect the horizon? Now can you have a GPS receiver at the top and a GPS receiver at the base, and some really simple trigonometry to tell you the pitch?

[Wicky]

Probably just plugged in a cat a la (The Ship Who Sang) Neuralink ;-)

[Remes]

but now the identical software as used to control the Falcon 9 can also control a simulation of the Falcon 9 in a computer model, where various external influences can be tested.

It's called software in the loop.
Don Eyles (LEM-developer) described software in his book, where sw was testing sw.

With hardware in the loop (HIL), the final computer including software is connected to another computer. The second computer simulates physics. In the Apollo project they had HILs including even a LEM or command module.

I'm not sure how long this technology has been around - probably since the introduction of Advanced Flight simulators in the 1980s

First flight simulators where created around world war 2. Used to train pilots, and they were build with analog computation technology.

In Boris Chertok's book one can read, that somewhere in the 30 a student had the idea to describe physics with capacitors and inductivities. They describe first order differential equations. And with multiples of them different things can be simulated. It was then used in the development of the V2 control system.

Edit:
http://www.analogmuseum.org/library/hamburg_hoelzer.pdf
it's german, but it describes the work of Hölzer on the V2. Shows also some schematics.

[alexterrell]

I'm always amazed at the ingenuity of the engineers and mathematicians who had to do all this with analogue systems. Slide 70/131 in that pdf is impressive, and to put that into a flight control system....

I can quite easily conceive of how a rocket can launch, with GPS sensor data and multiple digital inputs, extensive computations, maybe even running "what-if" scenarios, etc, and the luxury of thousands of processor cycles before needing to output a signal.

But how they did all that with analogue control system is a wonder. Or Rocket Science.

I would contend that in some areas - maybe not space flight - there is now less use of advanced maths and statistical models, as it's replaced with finite element analysis and various forms of Monte Carlo simulation.

I think early flight simulators took the pilots control as inputs and moved hydraulics to match. It would have taken them sometime to bring in external effects like a change in pressure, or the loss of a wing. Though they could simulate internal effects by disconnecting a hydraulic. 

[libra]

One of the most impressive achievements with analog computers in aviation is the CF-105 Arrow FBW - very similar to the 1974 F-16 and 1978 Mirage 2000 own analog FBW systems... except right from 1958.
15 to 20 years ahead. Quite a feat.

Of course FBW full potential was only exploited with digital - not analog.
The whole thing started with the Lunar Module control system, that Neil Armstrong passed to Dryden FRC in 1970, who put it in a F-8 Crusader in 1972.
Some years down the road, it found its way into the F-18 Hornet, first flight November 1978.

[laszlo]

As long as you have good telemetry and control links, you don't really need any onboard computational power to speak of to land a booster. You can do like the Atlas ICBMs did back when computers were big and heavy and leave the computer on the ground. A relatively simple control and guidance system (simple in that it could be implemented with existing analogue components) would ride the booster and take care of getting it back to the approximate vicinity of the launch site. At some point, a ground tracking system would acquire the booster and work out its position, velocity and accelerations. This data would be fed to the ground-based computer which would then generate control commands that would be radioed to the booster control and guidance system. This was all within the capabilities of 1950's, not to mention 1970's, tech. The reason it wasn't done is because there was no requirement for propulsive booster recovery.

And from a psychological point of view, doing it all with only analogue systems wasn't seen as a major accomplishment since there was no alternative. It was working with the latest technology on challenging projects and the engineers were trained to do so. Using op amps to calculate mathematical functions was every bit as ordinary then as grabbing for a CPU is today.

Same thing for programming systems with "only" 4K of memory. It's what you had and you used your skills to make sure it worked. It sure didn't feel primitive back then because it was the latest tech and probably reasonably expensive, too. It's only 40 or 50 years later that it seems limited.

As for compilers, any tricky assembly language coder who was awake saw that the jig was up for hand-optimized code when computers started beating Grand Masters at chess. And good riddance, too.

Finally, the Apollo Abort Guidance System with its 4K words of memory allowed a Lunar Module to escape into lunar orbit if necessary and helped bring Apollo 13 home when the main computer would have used too much electricity. Most desktops with 16GB play infinite cat videos while receiving the continuously streaming updates from Microsoft. Who's the smarter technology? 

[Barley]

As long as you have good telemetry and control links, you don't really need any onboard computational power to speak of to land a booster. You can do like the Atlas ICBMs did back when computers were big and heavy and leave the computer on the ground.

Any modern radio almost certainly has far more processor power than would be needed to perform the trajectory computation on board. 

Modern radios rely heavily on digital processing for error correction, efficient encoding, spread spectrum, phased array antennae, etc.  You can compensate for some of these things with steerable dishes, MW of power, and GHz of spectrum; but digital solutions are far lighter, cheaper, and more reliable than an analog data link.

The telemetry links of the original Atlas were, in their own field, as impressive at the time, and now as quaintly obsolete, as any other part of the system.

[joncz]

[Lar]

(fan) Some acronyms I need help with

LLVM (from dglow)
FBW (libra) I think that one is fly by wire
AGC (alexs) I think that one is automated guidance control

(mod) Better to fully expand any acronym you aren't 100% sure everyone knows.

[starsilk]

LLVM is a compiler, C, C++ and a few other languages these days

Sent from my ONEPLUS A6003 using Tapatalk

[Frogstar_Robot]

(fan) Some acronyms I need help with

LLVM (from dglow)
FBW (libra) I think that one is fly by wire
AGC (alexs) I think that one is automated guidance control

(mod) Better to fully expand any acronym you aren't 100% sure everyone knows.

Apollo Guidance Computer

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies. Despite its name, LLVM has little to do with traditional virtual machines. The name "LLVM" itself is not an acronym; it is the full name of the project.