25

I am working on an FPGA implementation of the original Space Invaders arcade machine and I'd like to implement access arbitration between the CPU and the video system. I can imagine several ways of doing it, and I would like to know how it was done on the real machine so I can implement something similar.

To recap, memory mapped to the CPU from 0x2400 to 0x4000 is an 8-bit-addressable 7K frame buffer where each byte represents 8 subsequent monochrome pixels. Obviously this memory needs to be accessible to the video system in time to draw the pixels as the electron beam sweeps across the screen.

1. Dual port RAM

In this setup, both the CPU and the video system can access the same memory at different addresses. Was this technology even available in 1978? Especially at a reasonable price?

2. Duplicate RAM with fanout writes

By using two 7K RAM modules, and fanning out writes from the CPU to both, we can have the CPU read from one and the video system read from the other, with no contention whatsoever. Of course, in a real hardware implementation, this requires an extra 7K RAM, which again is probably too expensive a solution in 1978.

3. Suspending the CPU via the READY pin during the entire visible screen

Quite extreme, but easy to implement: only allow the CPU to run during the horizontal and vertical retrace. While wasteful of CPU cycles, I think for Space Invaders this is probably viable, since I was able to get the game in a playable state (in an emulator, with no memory arbitration) with the CPU running in the low-hundred KHz range, so there is probably enough slack to make this workable.

4. Same as #3, but using the HOLD pin to only inhibit memory access from the CPU

This would allow the CPU to do a bit more work during the video system's VRAM access, and if I understand it right, it would require less components between the video RAM and the CPU since the CPU would electronically isolate itself from the bus.

5. Suspending the CPU (via READY) or inhibiting memory access (via HOLD) for every 8th pixel

Video system can read one byte at every 8th pixel into a shift register, then shift it out bit-by-bit. CPU only needs to be cordoned off from the video RAM for 1/8th of the time.

6. Suspending the CPU depending on the value on the address pins

This is the most efficient one I can think of, but also the most difficult to implement. In this scheme, the CPU is suspended (via READY) iff

  • The video system is accessing the VRAM (every 8th cycle during visible portion of the screen)
  • The CPU is requesting a read or a write to an address that is in the interval 0x2000..0x4000.

It seems to me that this would also require separate circuitry to isolate the CPU electronically from the bus, since by the time we can discover that the CPU is trying to access the video RAM at the wrong time, it would be "too late" to ask the CPU to release the bus.

7. Tick/tock access

(from a comment by user Janka): We can interleave memory access from CPU and from the video system by running them in two different clock phases (e.g. CPU on even, video on odd).

Although this makes sense intuitively for me, it is unclear how synchronous RAM access would work in this scheme, since the RAM would always have to reply with the contents of not the last, but the second-to-last cycle's address bus contents, right?

8. Other schemes I haven't thought of yet

Obviously the most exciting category.

So my question is, which of these approaches (or something else) did Space Invaders do to solve video RAM contention?

  • Most CPUs only access the external buses at one half of the clock cycle. This gives you the opportunity to use the other half of the clock cycle for video access. – Janka Jun 24 at 13:42
  • @Janka: oh, right, I wanted to add that "tick/tock" approach to my list but forgot. Do you know if that is what the Space Invaders arcade machine actually did? – Cactus Jun 24 at 13:49
  • 1
    I had called it "interleaved access" and the problem you see isn't one. There is no synchronous RAM access ever. The RAM has at least twice the access speed of the video logic. A more complicated video logic may also do two or more access cycles within its half of the CPU clock. – Janka Jun 24 at 14:29
  • @Janka: OK so I have misunderstood what you meant by 'one half of the clock cycle', I thought you meant the CPU setting the address bus at let's say the rising edge, then the video system sets the address bus at the falling edge, then the CPU reads the result on the next rising edge. – Cactus Jun 25 at 7:49
  • 1
    The 1MHz 6502 in the Apple II put an address out and 400 ns later read the data lines. Then no more until the beginning of the next microsecond. The video hardware then output its address and read a byte of video and the memory in turn would output that address. A fun thing was that if the CPU READ from memory-mapped OUTPUT, the actual memory wouldn't get the address. The video would go to memory and it'd hold that output data and that was the data the CPU saw. You could watch for sentinel data and toggle the display mid-refresh to combine text, hi-res graphics, and full color graphics. – Swiss Frank Jun 25 at 13:01
22

Space Invaders uses a simple display format where bytes are read from memory in order via an address counter, and shifted out via a shift register. Timing is controlled by discrete hardware.

The video hardware has priority over the CPU. When it needs to read a byte it asserts the 8080's READY signal, giving it exclusive access to the memory bus. This can be seen on the schematic at 5F.

This technique has the advantage of the 8080 not having to be synchronized with the display hardware at all.

  • 1
    A working link for the schematics: brentradio.com/images/Other/Docs/SpaceInvaders/… – lvd Jun 25 at 19:32
  • @lvd my link works for me, does it not work for you? – user Jun 26 at 7:59
  • There are no pings returned from www.robotron-2084.co.uk , as well as no download at all: wget halts at 'HTTP request sent, awaiting response...'. nmap says there are many open ports but obviously every connect gets unanswered. – lvd Jun 26 at 14:57
  • “This can be seen on the schematic” — Adding a co-ordinate would help. – ctrl-alt-delor Jun 27 at 9:39
  • Coordinates added. @lvd, I don't know why you are having problems with the link, but your comment offers an alternative so thanks. – user Jun 27 at 10:01
10

This is rather generic answer. As you point that Space Invaders uses 8080 CPU, it is known that 8080 accesses memory at the rate of 1 access per 3 clock cycles (max.). Other two cycles are freely available for the video system to fetch the required data.

For this kind of access to work reliably, DRAM chips must be able to operate at CPU clock speed (i.e. the timings of the whole access including /RAS and /CAS stages must fit in single CPU clock).

An example is this schematics http://www.spetsialist-mx.ru/schemes/Spetsialist.png of the USSR i8080-based computer. DD43 here is the i8080 (its USSR clone), DD15-DD18 are address multiplexers which route addresses from both video circuit and CPU to the DRAM, DD12.1 flip-flop (1/2 of 7474) is the arbiter that determines whether video circuit or CPU accesses the DRAM at any given clock cycle.

However, the most correct answer сould be immediately determined from the schematics of Space Invaders.

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.