The Dragon Map Processor is a single logical device that implements the mapping from virtual addresses to real and provides per-page memory protection. Its main features are: fast response to mapping requests on the average (300 ns); the use of a map table that consumes a small (< 1%), fixed fraction of real memory; the support of multiple virtual address spaces that are permitted to share memory; and an organization in which both function and performance can be enhanced relatively easily after hardware implementation. In spite of these features the design is simple.

This document begins with the addressing architecture supported by the Map Processor. It then describes the Map Processor's organization in terms of its three components: the Map Cache, which is a custom VLSI chip; the Map Cache Controller, whose functionality is implemented by ordinary Dragon processors; and the main memory Map Table, which stores the virtual to physical mapping information. The following section provides the functional specifications for the Map Processor; it also indicates how each function is invoked and where it is implemented. The next three sections describe each of the components in greater detail, while the last section addresses design issues that do not fit elsewhere. Important information is collected together in the Appendices.

The Map Processor's addressing architecture supports multiple address spaces, with fixed size pages being the unit of mapping and protection. The virtual addresses issued by each Dragon processor are mapped according to one of a number of independent addressing contexts, or address spaces. For a given virtual address the mapping to a real address can be thought of as a two step process, the first step being to determine the address space in which the virtual address must be interpreted, and the second being to perform the actual translation.

Before we describe each of these steps it is convenient to define basic terms and introduce some shorthand notation. A page is a contiguous chunk of memory 2s 32-bit words long, aligned on a 2s word boundary; s is fixed at 10. In our description virtual addresses will be denoted by va, real addresses by ra, virtual pages by vp, real pages by rp, and offsets into pages by offset. Both va and ra are 32-bit quantities, both vp and rp are (32—s)-bit quantities, and offset is an s-bit quantity. If vp and offset are the virtual page and offset corresponding to va, we will write va=vp|offset; similarly, we will write ra=rp|offset for real addresses. Four flags bits are kept for each page; these will be denoted by flags. Faults associated with address mapping will be communicated via a three-bit order field. The sizes of these quantities are constrained in the architecture by the relation ||rp||+||flags||+||order||=32, where ||x|| is shorthand for log2xË, the number of bits needed to represent x. Address spaces will be denoted by their address space id, aid, a quantity constrained by ||aid||+||vp||=32. Processors will be identified by their processor number, pn.

Figure 1 illustrates address mapping for procesor pn. Recall that the first step involves determining what address space to use for translating a given va. For this step the 32-bit address space of each processor is divided up into two non-overlapping regions: a 228 word shared region at the low end of the address space, and a 232-228 word switched region comprising the rest. If va lies in the shared region the address space used for mapping is space 0, otherwise it is the one currently loaded on the processor. At most one address space can be loaded on a given processor at a time, but the same space may be present simultaneously on different processors. The overall effect of the first step therefore is to map (pn, va<31:28>) onto aid. The second step translates va in the context of the aid given by the first step. This translation produces ra=rp|offset, where rp is obtained by looking up the entry corresponding to aid|vp in the Map Table.

The architecture also provides a mechanism to bypass the above mapping. Bypassing is needed to provide a way for processors to access the Map Table and map-fault handling code without getting map faults in the process; it is also useful in turning off mapping altogether. Bypassing gets activated whenever a processor makes a reference to a portion of virtual address space called the map bypass area. This area appears at the same locations in all address spaces, and is defined by three (32—s)-bit quantities BypassMask, BypassPattern, and BypassBase. The mask and pattern determine the bypass area's location and size in virtual memory as follows: a va is defined to be in the bypass area if the bits of va under BypassMask match the corresponding bits of BypassPattern. BypassBase determines the starting location of the area in real memory. The real address produced by bypass mapping is ra=rp|offset, where rp= (BypassBase.BypassMask) ( (vp.~BypassMask). The mask, pattern and base can all be modified.

This architecture is designed to facilitate sharing between address spaces. The shared area provides a restricted form of sharing where all of the vp's sharing a particular rp must be identical; this sharing is also all-or-nothing in that a page is shared by all spaces if it is shared by any. It is expected that all but a few cases of sharing will be covered by this restricted mechanism. The architecture also permits more general sharing in which the vp's sharing a particular rp are unrestricted and where each page may be shared by any subset of the spaces.

The Map Processor consists of three components (Figure 2): a custom VLSI Map Cache, a Map Cache Controller, and a Map Table kept in main memory. The Map Cache is simply a performance accelerator that sits between processor caches and the Map Table. It contains around 1200 mapping entries and allows mapping requests that hit to be serviced in three cycles, or 300 ns. Processor caches themselves keep a limited number of entries (~50), so the Map Cache is really a second level cache. When a map miss occurs in a processor cache, the cache fires off a mapping request to the Map Cache. The Map Cache returns the entry if it is present, and signals a map fault if it is not. This fault is then handled by the processor attatched to the cache that got the map miss. A small table in the Map Cache is used to determine the address space in which the references for each processsor should be mapped (the first step of the mapping process described in the last section). The Map Cache also implements a number of other operations, including ones to flush entries, to manipulate the control bits for entries in processor caches, to switch address spaces, and to control the location and size of the map bypass area. All communication with the Map Cache occurs over the M-Bus.

The Map Cache Controller is a fictitious device whose functionality is implemented by ordinary Dragon processors. As explained above, whenever the Map Cache misses, the processor whose cache got the miss fields the map fault. This processor plays the role of the Cache Controller in fetching the missing entry from the Map Table and shipping it to the Map Cache. In addition to servicing misses, the Controller also implements a complete set of operations for manipulating the Map Table. The code for these operations is available to all processors and can be executed by any one of them. This split in functionality between Map Cache and Controller forces us to freeze in hardware only that portion of the design which is necessary for speed, leaving the remainder to be implemented by ordinary Dragon code. As a result, enhancements in both function and performance can be made relatively easily. For example, the structure of the Map Table can be left completely open since the hardware has no knowledge of it.

The final component is the Map Table. It serves as the repository for mapping information for all address spaces, mapping (aid, vp) to rp. For each real page the table also maintains four flag bits used for paging and memory protection; in high to low order these are: shared, wtEnable, dirty, and spare. Note that this order is compatible with ED's order which is: spare, wtEnable, dirty, and referenced. The Map Table stores information only about pages currently in main memory, and is structured as a hash table indexed by (aid, vp). This allows the table to fit in a small, fixed fraction of main memory (< 1%), in contrast with direct map schemes. These schemes consume table space proportional to all of virtual memory or to the fraction being used frequently, depending on how they are implemented. Assuming that the hash function spreads things properly, the average time to access the table will be quite good. The worst case time, however, depends on how collisions are resolved. Initially, linear chaining with "move to front on access" will be used; if this turns out to be a performance problem the scheme will be modified to use a tree structure. Dragon processors access the Map Table directly via the map bypass area.

This section describes the functions implemented by the Map Processor. Map Cache functions are taken up first, followed by Cache Controller functions. The description for each function includes its specification, the method used for invoking it, and miscellaneous information relevant largely only to the implementor.

The Map Cache is an accelerator for speeding up mapping requests issued by processor caches. It has space for around 1200 of the entries stored in the Map Table, and is able to respond to requests in 300 ns in the case of a hit. It is implemented as a single VLSI chip whose main link with the outside world is via the M-Bus. The chip also connects to the D-Bus to permit initialization and debugging.

Two overall aspects of the design are worth pointing out here because they contribute to simple implementation and good performance. The first is that the cache is pure: an entry is never modified within the cache once it has been read in; if modifications need to be made, the entry is flushed from the cache, modified in the Map Table, and read in again. The most important consequence of this is that the cache can hold many more entries by making use of dynamic cells. These cells are smaller than static ones, but also much more prone to alpha particle hits. However, since the cache never contains irreplaceable data, we don't need to worry about correcting errors—we can get away by simply detecting them and flushing erroneous entries. Another consequence is that entries never need to be written through or written back, making the control portions of the chip simpler. The second aspect of the design is that the cache functions as a slave to other devices. Thus it never has to arbitrate for the M-Bus, and all of its interactions with the bus are simple. This minimizes the control logic needed for interfacing to the M-Bus.

Maintainence of dirty bit: when a processor writes into a page the first time after it has been brought into main memory, its dirty bit must be set. Since the Map Cache has a copy of this bit, this copy must get set also. This is done by flushing the entry from the Map Cache and signalling a write protect fault in response to a MapForWrite from a processor cache. This operation is issued by a cache when it tries to do a write, but finds wtEnabled clear. It is then up to the Map Cache Controller software to figure out whether the write protect fault is real or not and to update the dirty bit in the Map Table and send the updated entry to the Map Cache if it is not.

As stated earlier, the Map Cache Controller is implemented by software running on Dragon processors. This software provides two interfaces, one to service requests from the Map Cache and the other to perform more general manipulations on the Map Table.

Dragon procesors access the Map Table through the special map bypass area provided in low virtual memory. This area is also meant to contain any other system code (such as some of the fault handlers) that cannot tolerate map faults during its execution.

The Map Table is stored in main memory, and maps pairs (aid, vp) to pairs (rp, flags). It is implemented as a hash table, where the hash index is derived by folding and XORing the 32 bits of (aid, vp). Each row of the table is 4 words long and is quadword aligned. A row contains two mapping entries and two pointers used in collision resolution.

Initially, the method for resolving collisions will be linear chaining. If this causes performance problems the method will be changed to tree chaining. This change will be straightforward since the access algorithms are in Dragon code.

Since there may be more than one mapping entry per physical page, it is possible for the Map Table to overflow. The number of entries in the table will be 1.5 times the number of real pages in main memory, making overflow extremely unlikely. However, overflow is still possible, and it is a problem because a miss in the Map Table does not necessarily mean page fault—it could also mean that there was not enough space in the table. To fix this problem, the Map Table will be maintained using the all-or-nothing rule, which states that either all of the vp's for a given rp are in the table or none are. With this rule, table miss once again means page fault, freeing the software from having to discriminate between page faults and table misses.

-- Variable page size

-- Multiple Map Caches

-- Multiple M-Bus systems

-- In restricted sharing all vp's must have identical protection info

The map bypass area must be large enough to fit the Map Table as well as code for handling traps. Since the Map Table will larger by far, we need only consider its size to calculate how large to make the bypass area. Map Table size in turn depends directly on the amount of real memory. Assuming that 4 Mbit chips will be available within the lifetime of Dragon, that we can surface mount 1024 memory chips per board, and that we will put at most 8 memory boards on the largest Dragons, the maximum amount of real memory comes out to 1 GWord.

The size of the Map Table is 1.5*(#pages in real memory)*4 words. Rounding up the 1.5 up to 2, the Map Table occupies 223 words. Note that in rounding up 1.5 to 2 we've left plenty of space for code and any other data that needs to be kept in the bypass area.

||x|| log2xË, or the number of bits needed to represent x

a|b a*2||b||+b

vp virtual page

rp real page

s page size

aid address space id

pn processor number