The theory

Any modern CPU implements paging (the now defunct alternative being 'segmentation') and DME does so as well. In modern CPUs paging is used to give every process its own, clean, address space: a 32-bit CPU can address 4 GB of memory and with paging enabled, each process can address and access all of it (in practice the OS will limit each process size). For DME, paging provides another functionality: DME has 512kb of physical memory. However, being a 16bit architecture, DME can only address 64kb. Paging allows DME to use all of its 512kb of physical memory, while only being able to address 64kb of it simultanously. This way DME can keep multiple address spaces in memory and swap to the right address space just before it starts or resumes a process.

Having explained the theory: paging is complex! Not so much the high level concept, or even the implementation, but just thinking about it is complex: what is suppose to happen?, what is actually happening?, does it work? For this reason, adding paging to DME was 80% translating the high level concept into a detailed concept - all with pen and paper. Once I had that figured out, the other 20%, the implementation in Verilog, took just a few lines of code.

DME's paging concept
To make paging a reality we need to implement the following:
1. when turned on, logical addresses are translated to physical addresses
2. this translation is dynamic: the (OS) programmer can manipulate how addresses are translated
3. the implementation should recognize the concept of an address space: a bunch of translations that belong together
4. paging functionality can be turned on and off (otherwise you go mad trying to program it)

Conceptually, my implementation divides 512kb of physcial memory into 256 pages of 2kb each. Furthermore, it also divides 512kb into 8 address spaces of 64kb each (= 32 pages). This last point is a major simplification which I will discuss under point 3.

1. Translate logical addresses to physical addresses
The paging logic should take a 16-bit logical address and translate this in a 19-bit physical address (512kb = 2^19). It consists of:

Page Table: actually not a table, but just a list consisting of 256 16-bit addresses, that hold a reference to physical page locations, so called Page Table Entries (PTE). To translate a logical address an index is calculated and this is used as an index into the Page Table (e.g. if ptidx equals 47 the 47th entry of the Page Table is used).

Page Table Base (PTB): used to determine which of the 8 available address spaces is visible to the CPU. The PTB functions as an offset to the base of an address space in the Page Table. For example, the second address space would be indicated by a PTB value of 32, meaning the first page of the second address space is page 32 in the Page Table.

Page Table Index (ptidx): used to determine which PTE should be used from the Page Table. In pseudo code it is calculated as: address space offset + page number. The address space offset is simply the value of PTB. The page number can be gotten from the logical address (held in MAR): the bottom 11 bits give the location within a page (2^11 = 2048), the highest 5 bits when shifted right 11 places give a number between 0 and 31 - the page number.

The physical address (pageaddr) is then concatenated from PTE (highest 8 bytes) and the MAR (lowest 11 bytes) resulting in a 19-bit address.

2. User editable Page Table
Page Table Entries (PTEs) can be loaded into the Page Table by the command WPTE (Write PTE). It takes 2 arguments: the ptidx of the entry (0..255) and the physical page it should be mapped to shifted left 8 bit. In hindsight I could have shifted during the concatination of pageaddr, this would make the PTE entries easier to interpret. Perhaps I'll change it.

3. Recognize address spaces
The PTB register can be loaded with the WPTB (Write PTB) command. The implementation of the translation above guarantees that any mapping falls within the current address space: the top 5 bits from MAR can create no greater offset than 31. Offset 31 refers to the 32nd page, 32 x 2048 = 64kb. This behaviour results from my choice to divide the 512kb into 8 address spaces. This means that the value of PTB will always be a multiple of 32 between 0 and 224. The cost of this choice is that there can only ever be 8 processes running simultanously (7 user, 1 OS). Even if each process only requires 1kb of memory, 8 is the maximum number of processes as each process gets a full address space assigned in the PTB. Implementing dynamic address space sizes is a lot more complex due to the need to check if a logic address does not go out of bounds and the fact that address spaces sometimes need to increase in size. The first could probably be implemented in hardware with a second register (Page Table Top). The second point is harder. In any case, I went with the simplest implementation possible: 8 addresses spaces max.

4. Turn on/of
Turning paging on and off is as easy as checking bit 3 in the control register (CR[2]): if its set the pageaddr is used as the address going to ram (RAMaddr) if not, MARout is directly used. THus, when paging is off only the first 64kb of physical memory can be addressed.

The actual implementation in Verilog of the above is very simple. As I said, the hard part is deciding upon the conventions that make up your paging implementation. The translation part is realized in 3 lines of code. The loading of the page table and setting of PTB add another 8, very simple, lines.

This is all there is to the hardware implementation of Paging. The complexity does not end here though, dealing with paging is equally complex (to me at least) in software and deserves its own post. 

If people are interested I'll write that up next.