Wednesday, 3 January 2018

A Listing As High As The Moon!

Did you know that the source code for the Apollo Guidance Computer would reach all the way to the moon if it was printed out?

No? Good - because it's not true and we'll do the math here. There's a whole world of computing mythology that's sprung up over the decades. A classic claim is that the computers on the Apollo spacecraft were less powerful than the computer inside a typical digital watch.

That means there's more software on that watch than you need to reach the Moon!

It's all rubbish. The Apollo Guidance Computer was relatively complex; it was a 16-bit machine that had 36KW of firmware on it and ran. It would take a typical software engineer years to write the code that filled it, and in fact it did take a team of talented software engineers (headed by Margaret Hamilton who coined the term software engineer) years to write its code - in assembler.

Fortunately we can see the source code for the AGC these days as it's on github. Based on the Wikipedia article and assuming each Timing Pulse is 1.024MHz, then instructions would typically take between 12 timing pulses, which gives 85.3 KIPs and most instructions might require twice as much as that (assuming a memory access took another 12 pulses), giving speeds between 42.7KIPs and 85.3KIPs (which can be verified here).

36KW of firmware is equivalent to about 72Kb of firmware. That means the computer could handle software about as complex as microcomputers from the year 1984, where the limits of 16-bit addressing and the shift from writing in assembler to writing in high level languages were being tested. Some microcomputers from that era did have more RAM (e.g. the ACT Sirius), but here I'm taking common home computers as the baseline.

When you look at the software in GitHub you find that there are a reasonable number of files, usually of a reasonable length. The source code there has a GitHub header of about 26 lines on every file, but the rest of it is the original software.

Let's first think about how much code might be on there. Each assembler line is probably 1 instruction, which is one word (though it might be more if they used a macro assembler). Typical listing paper had 66 lines per page, So, 36,864 words would be 36,864/66 = 558.5 pages. So, how thick is a page? You can still buy listing paper, and it works out at 24.1cm for 700 pages, so the whole listing is, at a minimum: 558.5/700*24.1cm = 19.22cm high, just under half-way up to my knee.

So, at a first guess, it's not very high. But I could be badly wrong, because the real software was different for the Command module and the Lunar module; and also they would have had many comments in the code, which would have lengthened it. So, I took a look at the actual source files.

Helpfully, they have page numbers in them. Luminary099, which was the Lunar module's software has 1510 pages, and the command module's software in Commanche055 had 1516 pages. The total is thus: 3026 pages which is: 114.5cm tall. That's a bit more like the diagram, but it still only goes up to my chest.

Again this might not quite be accurate, because some of the code could have been shared, I hope to post a future update when I've figured out how much is!

Sunday, 31 December 2017

Z180 MMu-tiny

There's surprisingly little in the way of clear explanations for Z180's MMU, which is mostly OK because as an 8-bit CPU, the Z180 isn't very popular any more.

So, here's a bit of an explanation. The Z180 is basically a Z80 with some extra built-in peripherals, one of which is a bank-switching MMU which provides the CPU with the ability to manage 1Mb of physical memory.

The MMU itself is very simplistic. It divides the normal 16-bit address space into 3 sections: a section (called Common 0) that's always mapped to the beginning of physical memory; a section (called the Banked Area) which can be mapped anywhere in the 1Mb of physical memory; and a final section (called the Common 1 area) which can also be mapped anywhere in the 1Mb of physical memory.

The two banked areas can be made to start at any 4Kb region in the logical 64Kb memory space; though the Common 1 area should be made to start after the Banked Area.

The MMU is controlled via 3 x 8-bit registers in I/O space, at addresses at 0x38 to 0x3A as follows:

CA and BA are both reset to 0xf, which means that only the top 4Kb is mapped on boot-up, and since BBR and CBR are reset to 0, then this means that the top 4Kb is mapped to 0x0f000, which is good because the MMU can't be switched off.

Zilog (and Hitachi who first implemented the scheme) intended the MMU to operate so that only the Bank Area would move during the lifetime of any Z180 process, which is why the top segment is called "Common Bank 1", rather than, say "Bank Area 2" (or '1' if we'd numbered the Bank Areas from 0).

But this scheme severely restricts the flexibility of the MMU. That's because a flexible banked system needs at least 4 moveable banks for a process. You need a non-moving banked area of data to hold the stack and key global variables. Similarly, you need a non-moving banked area of code to hold key common routines, e.g. the bank switching code or a vector to the OS. Then to be able to use the 1Mb space for larger applications you need a relocatable segment for code and another for data; which means 4 banks in total. The Z180 only provides 2 movable banks.

If I had designed the Z180 MMU I would have chosen a pure bank-switching technique where each virtually addressed 16Kb bank is independently mapped somewhere in the physical address space. What might that look like if we were confined to the equivalent set of registers as for the real Z180 MMU?

Here the registers are called the FBP (Fixed Bank Page), the DBP (the Data Bank page) and the CBP (the Code Bank Page).

Each register is 8-bits and they map the virtual address to a 22-bit virtual address space (providing 4Mb) as follows:

So, the Code and Data bank pages map to the first two 16Kb banks anywhere in the physical address space and the last 32Kb normally maps to a 32Kb bank. There are two use-cases for how we might want to do the mapping. Firstly, there's the general purpose OS case. Here, we assume that it's fairly easy to map fixed code and data to consecutive banks (moving a pre-allocated moveable bank if needed). Hence we can make do with a single bank register for this purpose. The second use-case is for embedded systems where there would be a single application (in ROM). Here, the X bit can be set so that the top 16Kb can be mapped into RAM in the other half of the physical address space.

The logic involved in this scheme would be at least as simple as the original Z180, because no adder is required to compute the virtual Address + the bank register and no comparison logic is needed to determine which segment any particular virtual address belongs to. Instead, the top two virtual address bits directly index the MMU registers.

One additional feature is implemented: a RST xx instruction, including RST 0 - reset, will clear the CBP. This means that it would be possible for an application or process running from banked or the fixed code bank to execute a ROM routine - in rather the same way it works with CP/M.