What do you do when you run out of address space? Go to a bigger processor? Maybe, but another option is building a memory manager.
For novel ideas about building embedded systems (both hardware and firmware), join the 35,000 engineers who subscribe to The Embedded Muse, a free biweekly newsletter. The Muse has no hype and no vendor PR. Click here to subscribe.
By Jack Ganssle
Nelson Rockefeller, when asked how much money is enough, reportedly replied "just a little bit more." We poor folks may have trouble understanding his perspective, but all too often exhibit the same response when picking the size of the address space for a new design. Given that the code inexorably grows to fill any allocated space, "just a little more" is a plea we hear from the software people all too often.
Is the solution to use 32 bit machines exclusively, cramming a full 4 GB of RAM into our cost-sensitive application in the hopes that no one could possibly use that much memory?
Though clearly most systems couldn't tolerate the costs associated with such a poor decision, an awful lot of designers take a middle tack, selecting high end processors to cover their (ahem) posterior parts.
32 bit CPUs have tons of address space. 16 bitters sport (generally) one to 16 Mb. It's hard to imagine needing more than 16 Mb for a typical embedded app; even 1 Mb is enough for the vast majority of designs.
A typical 8 bit processor, though, is limited to 64k. Once this was an ocean of memory we could never imagine filling. Now C compilers let us reasonably produce applications far more complex then dreamed of even a few years ago. Today the mid-range embedded systems I see usually burn up something between 64k and 256k of program and data space - too much for an 8 bitter to handle without some help.
If horsepower were not an issue I'd simply toss in an 80188 and profit from the cheap 8 bit bus that runs 16 bit instructions over 1 Mb of address space. Sometimes this is simply not an option; an awful lot of us design upgrades to older systems. We're stuck with tens of thousands of lines of "legacy" code (sounds more like the name of a car than a technical term) that are too expensive to change. The code forces us to continue using the same CPU. Like taxes, programs always get bigger, demanding more address space that the processor can handle. Whatcha gonna do?
Perhaps the only solution is to add address bits. Build an external mapper using PLDs or discrete logic. The mapper's outputs go into high order address lines on your RAM and ROM devices. Add code to remap these lines, swapping sections of program or data in and out as required.
Logical to Physical
Add a mapper, though, and you'll suddenly be confronted with two distinct address spaces that complicate software design.
The first is the physical space - the entire universe of memory on your system. Expand your processor's 64k limit to 256k by adding two address lines, and the physical space is 256k.
Logical addresses are the ones generated by your program, and thence asserted onto the processor's bus. Executing a MOV A,(0FFFF) instruction tells the processor to read from the very last address in its 64k logical address space. External banking hardware can translate this to some other address, but the code itself remains blissfully unaware of such actions. All it knows is that some data comes from memory in response to the 0FFFF placed on the bus. The program can never generate a logical address larger than 64k (for a typical 8 bit CPU with 16 address lines).
I'll present my Better Firmware Faster seminar in Melbourne and Perth, Australia February 20 and 26th. All are invited. More info here. The early registration discount ends January 20.
Conversely, if there's no mapper then the physical and logical spaces are identical.
Consider doubling your address space by taking advantage of processor cycle types. If the CPU differentiates memory reads from fetches you may be able to easily produce separate data and code spaces. The 68000's seldom-used function codes are for just this purpose, potentially giving it distinct 16 Mb code and data spaces.
Writes should clearly go to the data area (you're not writing self-modifying code, are you?). Reads are more problematic. It's easy to distinguish memory reads from fetches when the processor generates a fetch signal for every instruction byte. Some processors (e.g., the Z80) produce a fetch only on the read of the first byte of a multiple byte opcode; subsequent ones all look the same as any data read. Forget trying to split the memory space if cycle types are not truly unique.
When such a space spitting scheme is impossible then build an external mapper that translates address lines. However, avoid the temptation to simply latch upper address lines. Though it's easy to store A16, A17 et al in an output port, every time the latch changes the entire program gets mapped out. Though there are awkward ways to write code to deal with this, add a bit more hardware to ease the software team's job.
Design a circuit that maps just portions of the logical space in and out. Look at software requirements first to see what hardware configuration makes sense.
Every program needs access to a data area which holds the stack and miscellaneous variables. The stack, for sure, must always be visible to the processor so calls and returns function. Some amount of "common" program storage should always be mapped in. The remapping code, at least, should be stored here so that it doesn't disappear during a bank switch. Design the hardware so these regions are always available.
Is the address space limitation due to an excess of code or of data? Perhaps the code is tiny, but a gigantic array requires tons of RAM. Clearly, you'll be mapping RAM in and out, leaving one area of ROM - enough to store the entire program - always in view. An obese program yields just the opposite design. In either of these cases a logical address space split into three sections makes the most sense: common code (always visible, containing runtime routines called by a compiler and the mapping code), mapped code or data, and common RAM (stack and other critical variables needed all the time).
For example, perhaps 0000 to 03FFF is common code. 4000 to 7FFF might be banked code; depending on the setting of a port it could map to almost any physical address. 8000 to FFFF is then common RAM.
Sure, you can use heroic programming to simplify the hardware. I think it's a mistake, as the incremental parts cost is minuscule compared to the increased bug rate implicit in any complicated bit of code. It is possible - and reasonable - to remove one bank by copying the common code to RAM and executing it there, using one bank for both common code and data.
It's easy to implement a three-bank design. Suppose addresses are arranged as in the previous example. A0 to A14 go to the RAM, which is selected when A15 = 1.
Turn ROM on when A15 is low. Run A0 to A14 into the ROM. Assuming we're mapping a 128k x 8 ROM into the 32k logical space, generate a fake A15 and A16 (simple bits latched into an output port) that go to the ROM's A15 and A16 inputs. However, feed these through AND gates. Enable the gates only when A15=0 (RAM off) and A14=1 (bank area enabled).
RAM is, of course, selected with logical addresses between 8000 and FFFF. Any address under 4000 disables the gates and enables the first 4000 locations in ROM. When A14 is a one, whatever values you've stuck into the fake A15 and A16 select a chunk of ROM 4000 bytes long.
The virtue of this design is its great simplicity and its conservation of ROM - there are no wasted chunks of memory, a common problem with other mapping schemes.
Occasionally a designer directly generates chip selects (instead of extra address lines) from the mapping output port. I think this is a mistake. It complicates the ROM select logic. Worse, sometimes it's awfully hard to make your debugging tools understand the translation from addresses to symbols. By translating addresses, you can provide your debugger with a logical to physical translation cheat sheet.
In assembly language you control everything, so handling banked memory is not too difficult. The hardest part of designing remappable code is figuring out how to segment the banks. Casual calling of other routines is out, as you dare not call something not mapped in.
Some folks write a bank manager that tracks which routines are currently located in the logical space. All calls, then, go through the bank manager which dynamically brings routines in and out as needed.
If you were foresighted enough to design your system around a real time operating system (RTOS), then managing the mapper is much simpler. Assign one task per bank. Modify the context switcher to remap whenever a new task is spawned or reawakened.
Many tasks are quite small - much smaller than the size of the logical banked area. Use memory more efficiently by giving tasks two banking parameters: the bank number associated with the task, and a starting offset into the bank. If the context switcher both remaps and then starts the task at the given offset, you'll be able to pack multiple tasks per bank.
Some C compilers come with built-in banking support. Check with your vendor. Some will completely manage a multiple bank system, automatically remapping as needed to bring code in and out of the logical address space. Figure on making a few patches to the supplied remapping code to accommodate your unique hardware design.
In C or assembly, using an RTOS or not, be sure to put all of your interrupt service routines and associated vectors in a common area. Put the banking code there as well, along with all frequently-used functions (when using a compiler, put the entire runtime package in unmapped memory).
As always, when designing the hardware carefully document the approach you've selected. Include this information in the banking routine so some poor soul several years in the future has a fighting chance to figure out what you've done.