Page Numbers: Yes X: 520 Y: -.5" First Page: 36
Heading:
Dorado Hardware ManualMemory Section14 September 1981
Memory Section
Dorado supports a linear 22-bit to 28-bit virtual address space and contains a cache to increase memory performance. All memory addressing is done in terms of virtual addresses; later sections deal with the map and page faults. Figure 8 is a picture of the memory system; Figure 9 shows cache, map, and storage addressing. As Figure 8 suggests, the memory system is organized into three more-or-less independent parts: storage, cache data, and addressing.
Inputs to the memory system are NEXT (the task that will control the processor in the next cycle) from the control section, subtask from io devices, Mar (driven from A or by the IFU), MemBase, B, the fast input bus, and an assortment of control signals. Outputs are B, Md to the processor, the F/G registers for the IFU, the fast output bus (data, task, and subtask), and Hold.
The processor references the memory by providing a base register number (MemBase) and 16-bit displacement (Mar) from which a 28-bit virtual address VA is computed; the kind of reference is encoded in the ASEL field of the instruction in conjunction with FF[0:1]. Subsequently, cache references transfer single 16-bit words between processor and cache; fast io references independently transfer 256-bit munches between io devices and storage. There is a weak coupling between the two data sections, since sometimes data must be loaded into the cache from storage, or returned to storage.
The storage pipeline allows new requests every 8 cycles, but requires 28 cycles to complete a read. The state of the pipeline is recorded in a ring buffer called the pipe, where new entries are assigned for each storage reference. The processor can read the pipe for fault reporting or for access to internal state of the memory system.
Memory Addressing
Processor memory references supply (explicitly) a 16-bit displacement D on Mar and (implicitly) a 5-bit task-specific base register number MemBase. Subtask[0:1] (See "Slow IO") are OR’ed with MemBase[2:3] to produce the 5-bit number sent to the memory. MemBase addresses 1 of 32 28-bit base registers. The full virtual address VA[4:31] is BR[MemBase]+D. D is an unsigned number.
The 28 bits in BR, VA, etc. are numbered 4:31 in the discussion here, consistent with the hardware drawings. This numbering conveniently relates to word boundaries.
Note that although the VA path is 28 bits wide, limitations imposed by cache and map geometry limit usable virtual memory to only 222 or 224 words in most configurations, as discussed in "The Map" section later.
MemBase can be loaded from the five low bits of FF, and the FlipMemBase function loads MemBase from its current value xor 1. In addition, MemBase can be loaded from 0.MemBX[0:1].FF[6:7], where the purpose of the 2-bit MemBX register is discussed in "IFU Section." The IFU loads the emulator task’s MemBase at the start of each opcode with a MemBX-relative value between 0 and 3.
The intent is to point base registers at active structures in the virtual space, so that memory references may specify a small displacement (usually 8 or 16 bits) rather than full 28-bit VA’s. In the Mesa emulator, for example, two base registers point at local (MDS+L) and global (MDS+G) frames.
In any cycle with no processor memory reference, the IFU may make one. IFU references always use base register 31, the code base for the current procedure; the D supplied by the IFU is a word displacement in the code segment.
Programmers may think of Mar as an extension of A since, when driven by the processor, Mar contains the same information as A.
The base register addressed by MemBase can be loaded using BrLo←A and BrHi←A functions. VA is written into the pipe memory on each reference, where it can be read as described later. The contents of the base register are VA-D on any reference.
Processor Memory References
Memory references are initiated only by the processor or IFU. This section discusses what happens only when references proceed unhindered. Subsequent sections deal with map faults, data errors, and delays due to Hold.
Processor references (encoded in the ASEL and FF[0:1] instruction fields as discussed in the "Processor Section" chapter) have priority over IFU references, and are as follows:
Fetch←Initiates one-word fetch at VA. Data can be retrieved in any subsequent instruction by loading Md into R or T, onto A or B data paths, or masking in a shift operation.
Store←Stores data on B into VA.
LongFetch←A fetch for which the complete 28-bit VA is (B[4:15],,Mar[0:15])+BR[MemBase].
IFetch←A fetch for which BR[24:31] are replaced by Id from the IFU. When BR[24:31] are 0 (i.e., when BR points at a page boundary), this is equivalent to BR+Mar+Id, saving 1 instruction in many cases. Note: the IFU does not advance to the next item of ←Id for IFetch←, so an accompanying TisId or RisId function is needed to advance.
PreFetch←Moves the 16-word munch containing VA to the cache.
DummyRef←Loads the pipe with VA for the reference without initiating cache, map, or storage activity.
Flush←Removes a munch containing VA (if any) from the cache, storing it first if dirty (emulator or fault task only).
Map←Loads the map entry for the page containing VA from B and clears Ref; action is modified by the ReadMap function discussed later (emulator or fault task only).
IOFetch←Initiates transfer of munch from memory to io device via fast output bus (io task only).
IOStore←Initiates transfer of munch from io device to memory via fast input bus (io task only).
(Inside the memory system, there are three other reference types: IFU reads, dirty cache victim writes, and FlushStore fake-reads that result from Flush← references which hit dirty cache entries.)
The notation for these memory references has been confusing to people who first start writing microprograms. The following examples show how each type of reference would appear in a microprogram:
Fetch←T;*Start a fetch with D coming from T via Mar
T←Md;*Read memory data for the last fetch into T
Store←Rtemp, DBuf←T;*Start a store with D coming from an RM
*address via Mar and memory data from T via B.
PreFetch←Rtemp;
Flush←Rtemp;
IOFetch←Rtemp;
IOStore←Rtemp;
Map←Rtemp, MapBuf←T;*Start a map write with D coming from an RM
*address (Rtemp) via Mar, data from T via B
RMap←Rtemp;*Start a map read with D coming from an Rm
*address (Rtemp) via Mar.
LongFetch←Rtemp, B←T;*Start a fetch reference with
*VA = BR[4:31]+(T[4:15],,Rtemp[0:15]).
IFetch←Stack;*Start a fetch reference with Id replacing BR[24:31]
*and with D coming from Stack.
IFetch←Stack, TisId;*Start a fetch as above and also advance the IFU to the
*next item of ←Id.
The tricky cases above are Store←, Map←, and LongFetch←, which must be accompanied by another clause that puts required data onto B. DBuf← and MapBuf← are synonyms for B←, and do not represent functions encoded in FF; these synonyms are used to indicate that the implicitly loaded buffer registers (DBuf on MemD and MapBuf on MemX) will wind up holding the data.
The encoding of these references in the instruction was discussed in the "Processor" section under "ASEL: A Source/Destination Control". The ten possible memory reference types have the following properties:
Fetch←, IFetch←, and LongFetch←
These three are collectively called "fetches" and differ only in the way VA is computed. In any subsequent instruction, memory data Md may be read. If Md isn’t ready, Hold occurs, as discussed below. If the munch containing VA is in the cache and the cache isn’t busy, Md will be ready at t3 of the instruction following the fetch, with the following implications:
If Md is loaded directly into RM or T (loaded between t3 and t4), it can be read in the instruction after the fetch without causing Hold. This is called a deferred reference.
If Md is read onto A or B (needed before t2) or into the ALU masker by a shift (needed before t3), it is not ready until the second instruction after the fetch (Hold occurs if Md is referenced in the first instruction.). This is called an immediate reference.
The above timing is minimum, and delays may be longer if data is not in the cache or if the cache is still busy with an earlier reference.
Md remains valid until and during the next fetch by the task. If a Store← intervenes between the Fetch← and its associated ←Md, then ←Md will be held until the Store← completes but will then deliver data for the fetch exactly as though no Store← had intervened.
Store←
Store← loads the memory section’s DBuf register from B data in the same instruction. On a hit, DBuf is passed to the cache data section during the next cycle. On a miss DBuf remains busy during storage access and is written into the cache afterwards.
Because DBuf is neither task-specific nor reference-specific, any Store←, even by another task, holds during DBuf-busy. However, barring misses, Store←’s in consecutive instructions never hold. A fetch or ←Md by the same task will also hold for an unfinished Store←.
PreFetch←
PreFetch← is useful for loading the cache with data needed in the near future. PreFetch← does not clobber Md and never causes a map fault, so it can be used after a fetch before reading Md.
IOFetch←
An IOFetch← is initiated by the processor on behalf of a fast output device. When ready to accept a munch, a device controller wakes up a task to start its memory reference and do other housekeeping.
An IOFetch← transfers the entire munch of which the requested address is a part (in 16 clocks, each transferring 16 data+2 parity bits); the low 4 bits of VA are ignored by the hardware. If not in the cache, the munch comes direct from storage, and no cache entry is made. If in the cache and not dirty, the munch is still transferred from storage. Only when in the cache and dirty is the munch sent from the cache to the device (but with the same timing as if it had come from storage). In any case, no further interaction with the processor occurs once the reference has been started. As a result, requested data not in the cache (the normal case) is handled entirely by storage, so processor references proceed unhindered barring cache misses.
The destination device for an IOFetch← identifies itself by means of the task and subtask supplied with the munch (= task and subtask that issued IOFetch←). The fast output bus, task, and subtask are bussed to all fast output devices. In addition, a Fault signal is supplied with the data (correctable single errors never cause this fault signal); the device may do whatever it likes with this information. More information relevant to IOFetch← is in the "Fast IO" chapter.
IOFetch← does not disturb Md used by fetches, DBuf used by Store←, or MapBuf used by Map←.
There is no way to encode either IOFetch← or IOStore← in an emulator or fault task instruction, and there should never be any reason for doing this.
IOStore←
IOStore← is similar to IOFetch←. The processor always passes the reference to storage. The cache is never used, but a munch in the cache is unconditionally removed (without being stored if dirty). A munch is passed from device to memory over the fast input bus, while the memory supplies the task and subtask of the IOStore← to the device for identification purposes. The device must supply a munch (in 16 clocks, each transferring 16 bits) when the memory system asks for it.
The Carry20 function may be useful with IOFetch← and IOStore←. This function forces the carry-in to bit 11 of the ALU to be 1, so a memory address D on A can be incremented by 16 without wasting B in the same instruction.
Map←
This is discussed later.
Flush←
Flush← unconditionally removes a munch containing VA from the cache, storing it first if dirty. It is a no-op if no munch containing VA is in the cache; it immediately sets Vacant in the cache entry and is finished on a clean hit; it gives rise to a FlushStore reference on a dirty hit.
Only emulator or fault task instructions can encode Flush←, using the private pipe entry (0 or 1) pointed at by ProcSRN. The FlushStore triggered, if any, uses the ring-buffer part of the pipe. FlushStore turns on BeingLoaded in the cache entry and trundles through a (useless but harmless) storage access to the item being flushed; when this finishes Vacant is set in the cache entry; then the dirty-victim is written into storage.
Unfortunately, Flush← clobbers the Victim and NextV fields in the cache row, which causes the cache to work less efficiently for awhile.
Some applications of Flush← are discussed later in the Map section. Note: it is necessary to hold until any preceding private pipe entry fetch or Store← has finished by issuing ←Md—reasons for this are discussed in "The Pipe" section.
DummyRef←
DummyRef← writes VA into the pipe entry for the reference without initiating cache, map, or storage activity. This is provided for reading base registers and so diagnostic microcode can exercise VA paths of the memory system without disturbing cache or memory. Note: it is necessary to hold until any preceding private pipe entry fetch or Store← has finished by issuing ←Md—reasons for this are discussed in "The Pipe" section.
IFU References
The F and G data registers shown in the IFU picture (Figure 11) are physically part of the memory system. The memory system fetches words referenced by the IFU directly into these registers. The IFU may have up to two references in progress at-a-time, but the second of these is only issued when the memory system is about to deliver data for the first reference.
An IFU reference cannot be initiated when the processor is either using Mar or referencing the Pipe; for simplicity of decoding, the hardware disables IFU references when the processor is either making a reference or doing one of the functions 1208 to 1278 (CFlags←A’, BrLo←A, BrHi←A, LoadTestSyndrome, or ProcSRN←B); or 1608 to 1678 (B←FaultInfo’, B←Pipei, or B←Config’).
The IFU is not prevented from making references while the processor is experiencing Hold, unless the instruction being held is making a reference or doing one of the functions mentioned above.
Memory Timing and Hold
Memory system control is divided into three more or less autonomous parts: address, cache data, and storage sections. The storage section, in turn, has several automata that may be operating simultaneously on different references. Every reference requires one cycle in the address section, but thereafter an io reference normally deals only with storage, a cache reference only with the cache data section. Address and cache data sections can handle one reference per cycle if all goes well. Thus, barring io activity and cache misses, the processor can make a fetch or store reference every cycle and never be held.
If the memory is unready to accept a reference or deliver Md, it inhibits execution with hold (which converts the instruction into a Goto[.] while freezing branch conditions, dispatches, etc.). The processor attempts the instruction again in the next cycle, unless a task switch occurs. If the memory is still not ready, hold continues. If a task switch occurs, the instruction is reexecuted when control returns to the task; thus task switching is invisible to hold.
In the discussion below, cache references are ones that normally get passed from the address section to the cache data section, unless they miss (fetches, stores, and IFU fetches), while storage references unconditionally get passed to storage (IOFetch←, IOStore←, Map←, FlushStore arising from Flush← with dirty hit, and dirty-victim writes). PreFetch← and DummyRef← don’t fall into either category.
Situations When Hold Occurs
A fetch, store, or ←Md is held after a preceding fetch or store by the same task has missed until all 16 words of the cache entry are loaded from storage (about 28 cycles).
Store← is held if DBuf is busy with data not yet handed to the cache data or storage sections. LongFetch← (unfortunately) is also held in this case. Since DBuf is not task-specific, this hold will occur even when the preceding Store← was by another task.
An immediate ←Md is held in the cycle after a fetch or store, and in the cycle after a deferred ←Md.
Because the task-specific Md RAM is being read t2 to t3 for the deferred ←Md in the preceding cycle, and t0 to t1 for the immediate ←Md in the current cycle, which are coincident, hold is necessary when the tasks differ. Unfortunately, hold occurs erroneously when the immediate and deferred ←Md’s are by the same task.
Any reference or ←Md is held if the address section is busy in one of the ways discussed below.
←Md is erroneously held when the address section is busy, an unfortunate consequence of the hardware implementation, which combines logic for holding ←Md on misses with logic for holding references when the address section is busy.
B←Pipei is held when coincident with any memory system use of the pipe. Each memory system access uses the pipe for one cycle but locks out the processor for two cycles. The memory system accesses the pipe t2 to t4 following any reference, so B←Pipei will be held in the instruction after any reference. Storage reads and writes access the pipe twice more; references that load the cache from storage access the pipe a third time.
Map←, LoadMcr, LoadTestSyndrome, and ProcSRN← are not held for MapBuf busy; the program has to handle these situations itself by polling MapBufBusy or waiting long enough, as discussed in the Map section.
Flush←, Map←, and DummyRef← are not held until a preceding fetch or store has finished or faulted. The emulator or fault task should force Hold with ←Md before or coincident with issuing one of these references, if it might have a fetch or store in progress.
In the processor section, stack overflow and underflow and the hold simulator may cause holds; in the control section TaskingOff or an IFUJump in conjunction with the onset of one of the rare IFU error conditions may cause one-cycle holds; there is also a backpanel signal called ExtHoldReq to which nothing is presently connected—this is reserved for input/output devices that may need to generate hold in some situation. All of these reasons for hold are discussed in the appropriate chapters.
Address Section Busy
The address section can normally be busy only if some previous reference has not yet been passed to the cache data section (for a cache reference that hits) or to storage (for a storage reference, or a cache reference or PreFetch← that misses). A reference is passed on immediately unless either its destination is busy or the being-loaded condition discussed below occurs.
The address section is always busy in the two cycles after a miss, or in the cycle after a Flush←, Map←, IOFetch←, or IOStore←.
Hardware note: This allows Asrn to advance; for emulator and fault task fetch and store misses, which do not use Asrn, this hold is unnecessary. Unfortunately, the display controller’s word task finishes each iteration with IOFetch← and Block, so many emulator fetches and stores will be held for one cycle when a high-bandwidth display is being driven. Asrn is the internal register that contains the pipe address for storage references.
There are six other ways for the address section to be busy:
(1)A cache reference or PreFetch← that misses, or a FlushStore, transfers storage data into the cache. At the end of this reference, as the first data word arrives, storage takes another address section cycle.
(2)The preceding cache reference hit but cannot be passed to the cache data section because the data section is busy transferring munches to/from storage (or to an io device if an IOFetch← finds dirty data in the cache). Total time to fetch a munch from storage is about 28 cycles, but the cache data section is busy only during the last 10 of these cycles (9 for PreFetch or IOFetch← with dirty hit), while data is written into the cache. The cache data section is free during the interim.
(3)The preceding storage reference, or cache reference or PreFetch← that missed has not been passed on to storage because the storage section is busy. Storage is busy if it received a reference less than 8 cycles previously, and may be busy longer as follows:
successive cache references must be 10 cycles apart;
successive write references must be 11 cycles apart;
with 4k storage ic’s, successive references must be 13 cycles apart.
(4)A cache write (caused by a miss with a dirty victim or FlushStore) ties up the address section until the storage reference for the write is started; this happens 8 cycles after the storage reference for the miss or FlushStore is started. Note that the new munch fetch starts before the dirty victim store and that hold terminates right after the store is started.
(5)A reference giving rise to a cache write that follows any other cache miss will tie up the address section until the previous miss is finished.
(6)The address section is busy in the cycle after any reference that hits a cache row in which any column is being loaded from storage.
Any reference except IOFetch←, DummyRef←, or Map← that hits a cache row in which any column is being loaded from storage remains in the address section until the BeingLoaded flag is turned off—i.e., for the first 19 of the 28 cycles required to service a miss, the reference is suspended in the address section; during the last 9 cycles of the miss, when the munch is transferred into the cache data section, the reference proceeds (except that a fetch or store will still be held because the cache data section is busy during these 9 cycles). This is believed to be very infrequent.
A more perfect implementation would suspend a reference in the address section only when the hit column, rather than any column in the row, was being loaded. However, the situation is only costly when the suspended reference is by another task; since there are 64 rows, ~1.5% of all references will be held whenever any task is experiencing a miss. There is more discussion of this in the "Performance Issues" chapter.
References to storage arise as follows:
a cache miss (from a cache reference or PreFetch←) causes a storage read;
a cache reference or PreFetch← miss with dirty victim also causes a storage write immediately after the read;
a Flush← which gets a dirty hit causes a FlushStore read reference which in turn causes a storage write of the dirty victim;
every io reference causes a storage read or write;
a Map← causes a reference to storage (actually only the map is referenced, but the timing is the same as for a full storage reference).
The following table shows the activity in various parts of the memory system during a fetch that misses in the cache and displaces a dirty victim; the memory system is assumed idle initially and nothing unusual happens.
Table 15: Timing of a Dirty Miss
Time Time
(Cycles)Activity of Fetch(Cycles)Activity of Dirty-Victim Write
0Fetch← starts
1in address section 2-9in address section (wait for map)
3-18in ST automaton (generate
syndrome, transport to storage)
2-9in map automaton *10-17in map automaton *
7-14in memory automaton *15-22in memory automaton *
14-21in Ec1 automaton22-29in Ec1 automaton **
21-28in Ec2 automaton29-36in Ec2 automaton **
27←Md succeeds
* The map automaton continues busy for two cycles after a reference is passed to the memory automaton because it is necessary for the Map storage chips to complete their cycle.
** The work of the dirty-victim write is complete after it has finished with the memory automaton, but it marches through Ec1 and Ec2 anyway for fault reporting.
STOP! The sections which follow are about the Map, Pipe, Cache, Storage, Errors, and other internal details of the memory system. Only programmers of the fault task or memory system diagnostic software are expected to require this information. Since there are many complications, you are advised to skip to the next chapter.
The Map
VA is transformed into a real address by the map on the way to storage. The hardware is easily modifiable to create a page size of either 256, 1024, or 4096 words and to use either 16k, 64k, or 256k ic’s for map storage. The table below shows the virtual memory (VM) sizes achievable with different map configurations. However, the cache configuration limits VM size independently, as discussed later, and this limit may be smaller than the Map limit.
Table 16: Map Configurations
Map Map
ICPageVMAddressed
SizeSizeSize By
21428222VA[10:23]
214210224VA[8:21]
214212226VA[6:19]requires 16k-word cache
21628224VA[8:23]
216210226VA[6:21]requires 16k-word cache
216212228VA[4:19]requires 16k-word cache sans parity
21828226VA[6:23]218-bit ic’s don’t exist yet
218210228VA[4:23]218-bit ic’s don’t exist yet
Larger page sizes increase the virtual memory size limit. Since the 4k-word cache imposes a 225-word size limit (226 if the parity bit in the address section is converted into another address bit), the largest VM sizes are only achievable in conjunction with a 16k-word cache. Larger page sizes might reduce map and storage management overhead; our experience in this area is inconclusive but suggests that 4k-word pages would only be desirable with very large storage configurations.
Note that the physical storage size limit is unaffected by either cache parameters, map RAM size, or page size because RP is large enough to address the largest possible storage configuration (4 modules using 218-bit MOS RAM components), even when the smallest page size is used; this maximum size is 224 words.
The cache handles virtual addresses, so the map is never involved in cache references unless they miss.
A consequence of virtual addresses in the cache is that it is illegal to map several virtual pages into the same real page (unless all instances are write-protected). This restriction prevents cache and storage from becoming inconsistent.
A map entry contains a 16-bit real page number (RP) and three flags called Dirty, Ref, and WP, which have the following significance:
WPwrite-protects the page; a fault occurs if a write is attempted.
Dirtyindicates that storage has been modified; set by any IOStore← or by a dirty-victim write; Store← does not set Dirty.
Refindicates that the page has been referenced; set by any storage reference except Map←; cleared by Map←.
The combination WP=true with Dirty=true makes no sense, and encodes the Vacant state of the map entry. A map entry is vacant if it has no corresponding page in real memory.
Faults
Every storage reference causes a mapping operation. If mapping reveals something other than Vacant, the reference proceeds normally. Otherwise, the storage reference is aborted, and MapTrouble is reported as discussed later. There are two kinds of faults:
Page faultreference to a vacant map entry (WP = true, Dirty = true)
WP faultStore← that misses, IOStore←, or dirty-victim write with WP true. (Dirty-victim WP faults should not occur if the map and cache are handled as proposed below.)
Writing the Map
Map←, which can only be encoded in an emulator or fault task instruction, is used to write the map; like other storage references, it returns previous map contents in the pipe, where they can be read. For reasons discussed in "The Pipe" section later, Map← should not be issued if a preceding fetch or Store← might be in progress; normally issue a ←Md to hold until preceding references cannot fault.
Map← first writes B[0:15] and TIOA[0:1] into MapBuf (a buffer register on the MemX board) and turns on MapBufBusy in the pipe; 9 cycles later (barring delays) MapBuf has been written into the Map entry addressed by the appropriate bits of VA and MapBufBusy is turned off.
B[0:15] are the real page number, TIOA.0 is WP, and TIOA.1 is Dirty. Map← zeroes Ref, and there is no direct way to write a map entry with Ref=1; a fetch, Store←, or PreFetch← to the appropriate page after loading the map entry will set Ref=1. Note that if the real address space is less than 224 words (216 pages), high order RP bits are ignored during references though they are kept in the map and appear in the pipe.
Map← never wakes up the fault task.
If previous map contents indicated Vacant or had a parity error, MapTrouble will be true in the pipe but not reported to the fault task. Quadword and syndrome in the pipe, not written by Map←, contain previous values.
For all programming purposes, Map← is complete on the cycle when MapBufBusy is turned off; at this time, previous map contents are valid in the pipe entry. Polling MapBufBusy until it is false is the only way to find out when the pipe entry is valid.
Since Map← never faults and doesn’t use any pipe information clobbered by an overlapping reference, another reference may be started without waiting for Map← to finish, unless the following reference is another Map←. Also, Map← does not interfere with Md or DBuf, so its only interference with other kinds of references is its use of the private pipe entry (0 or 1) pointed at by ProcSRN. However, it is illegal to issue another Map←, LoadMCR, LoadTestSyndrome, or ProcSRN← without waiting for Map← to finish. These functions (discussed later) share the MapBuf register with Map←; there is no Hold arising from MapBufBusy, so the microprogram must ensure that MapBuf is free when one of these functions is executed.
B is latched in MapBuf during t2 to t3 and TIOA[0:1] are clocked into MapBuf at t2 for all of these; then MapBuf is written into MCR, TestSyndrome, or ProcSRN at t3 or into the Map at t14 (if no delays). In other words, MapBuf is a buffer register for all registers on the MemX board that are loaded from B.
Reading the Map
Every storage reference causes mapping and returns old contents of the relevant map entry in the pipe. I.e., Ref and Dirty may change as a result of a reference—old values appear in the pipe.
A ReadMap function accompanying Map← prevents the map entry from being modified, so that old contents can be read from the pipe without also smashing the map entry.
Flushing One Page From the Cache
Any cache reference or PreFetch← that misses or any IOFetch← or IOStore← sets Ref in the map; IOStore←’s set Dirty as well. If the victim for the miss or hit for the Flush← is dirty, Ref and Dirty for its map entry also get set. However, Store← does not set Dirty in the map entry until that munch is chosen as victim.
For this reason, any calculation based upon Dirty must first validate the map Dirty bit by flushing associated cache entries, as discussed below.
In addition, almost any change to a map entry requires a flush, again because of problems with dirty cache entries. The following examples illustrate this point:
Before changing RP, a flush prevents dirty victims from being written into the previous real page (if the old page had WP false).
Before turning on WP, a flush prevents dirty cache entries from being written into the now write-protected page.
Before turning off WP, a flush prevents multiple cache entries for a munch, one write-protected, the other not (The cache will not work correctly, if there are multiple entries for a munch.).
Before sampling Ref, flushing is required so that subsequent references to the page will set Ref=1 and so that dirty munches in the cache will not erroneously set Ref=1 when they are displaced.
Before clearing Dirty, a flush prevents dirty munches subsequently displaced from the cache from erroneously setting Dirty again.
To flush a 256-word page from the cache, 16 Flush← references may be made, one to each munch of the page (64 with 1024-word pages). Flush← invalidates any existing cache entry for the munch (and stores the munch if dirty).
This succeeds iff there are no anomalous multiple cache entries for a particular munch. Multiple cache entries for a munch should never occur except prior to system initialization or when some of the debugging features are turned on in Mcr.
Flushing the Entire Cache
Depending upon what kind of storage management algorithm is used, it may be desirable to clear out the entire cache; for example, this might be useful before looping through all the map entries to sample Ref. It would be extremely expensive to do this with Flush← one page at-a-time (216 Flush←’es for 1M words of storage). The cleverest method which we have thought of for doing this is as follows:
Designate 4 consecutive 256-word pages (64-row cache) or 16 consecutive pages (256-row cache) that contain vacant map entries; the munch VA’s in these pages will span every row in the cache. Make one pass through the cache for each column; before each pass, load Mcr with UseMcrV true and McrV equal to the column—even though it is usually illegal to modify Mcr while the memory system is active, it should be safe to change these particular fields. Then do PreFetch←’es for all 64 or 256 munches in the designated pages; these PreFetches will all miss and map fault, leaving the selected column filled with vacant cache entries. After clearing all four columns, restore Mcr to its previous value. While this flush is going on, io tasks may continue to reference memory, but they will experience more misses and longer miss wait than usual. The total time for this algorithm is about 9 cycles/PreFetch or about 138 ms with 64 rows or 553 ms with 256 rows in the cache at 60 ns/cycle.
Map Hardware Details
The map and its control are on the MemX board. Physically, map storage consists of 21 16k, 64k, or 256k x 1 MOS RAM’s; in addition to the 19 bits discussed earlier, there are a duplicate of the Dirty bit and an odd parity bit.
Dirty is duplicated so map parity won’t change when both Dirty bits are set. Ideally Ref should also be duplicated, but it is not, and Ref is not checked by map parity. The parity written on Map← is the exclusive-or of the two B byte parity bits and TIOA.0 (i.e., WP). Parity failure on any map read will cause MapTrouble and MemError and wakeup the fault task when appropriate.
On a cache reference that misses or on an IOFetch← or IOStore←, the map read starts at t4 and the real address is passed to storage at t14.
The MOS RAM’s in the map require refresh, carried out like the storage refresh discussed later.
An Automatic Storage Management Algorithm
We envision for Mesa, Lisp, etc. an automatic storage manager that will pick pages in storage which have not been referenced recently for replacement by new ones. This manager will use the Ref bits in map entries to determine which pages have not been referenced for a long time.
The storage manager discussed here controls N pages, where N is some subset of all pages in storage; in general N will vary. A procedure called DeliverPage() returns RP for one of the N pages to the caller and removes that page from N; a procedure called ManagePage(RP,Age) adds a page to N. A page returned by DeliverPage has been removed from the virtual space; pages accepted by ManagePage may or may not be vacant.
Entries for the N pages are sorted into 8 bins, such that entries in the bin 0 have age 0, bin 1 age 1, etc. Whenever DeliverPage has been called N/8 times or after a specified elapsed time has occurred, all N pages are aged, which means:
(a) Entries originally in bin 7 wind up in bin 0 if they have been referenced, bin 7 if not referenced;
(b) Entries in bin i (i # 7) wind up in bin 0 if referenced or bin i+1 if not referenced.
This aging is performed by first clearing the entire cache using the clever algorithm discussed earlier, then sampling and zeroing Ref.
DeliverPage first returns the RP of any page on the vacant queue. If the vacant queue is empty, it next scans entries on the disk write-complete queue; if one is found that has not been referenced in the interim, its map entry is cleared and its RP is returned; if referenced, it is moved to bin 0. If the disk write-complete queue is empty, entries in bin 7 are scanned; if this bin is exhausted, bin 6 is scanned, etc., until finally bin 0 is scanned. When an entry has been referenced, it is moved to bin 0; when unreferenced but dirty, it is put on the disk write queue; when unreferenced and clean it is returned.
The caller of DeliverPage will frequently be a disk read or new page creation procedure. It should complete its work and then call ReturnPage(RP,0) to restore the page to the storage manager. ReturnPage will put the page on the vacant queue, if it is vacant, or into bin 0.
Mesa Map Primitives
Basic Mesa mapping primitives are:
Associate[vp,rp,flags] adds virtual pages to the real memory, or removes them if flags=Vacant.
SetFlags[vp,flags] RETURNS oldValue: flags reads and sets the flags. If flags=Vacant, the page is removed from the real memory.
GetFlags[vp] RETURNS [rp,flags].
These are defined as indivisible operations and are implemented trivially on a machine with no cache (e.g., Dolphin). For example, if a SetFlags clears Dirty and sets WP, the returned value of Dirty tells correctly whether the page has been changed—no store into the page may occur between reading Dirty and setting WP.
One intended use of the primitives is illustrated by the following Mesa sequence for removing a virtual page from real memory:
oldFlags ← SetFlags[v,WP];
IF oldFlags.Dirty THEN WritePage[...]
SetFlags[v,Vacant]
This sequence prevents the page from being changed during the write. Another possibility would be just to clear Dirty, and then to check it again after the write. This must be done properly, however, to avoid a race condition:
WHILE (oldFlags←SetFlags[v, Vacant]).Dirty
DO SetFlags[v, [Dirty: false]]; WritePage[...]; ENDLOOP
To avoid inconsistent map and cache entries, SetFlags[v, ...] must remove entries for page v from the cache. Unfortunately, since we don’t want to make the cache removal process atomic, parts of the page already passed over by the removal process could be brought back into the cache before the process is complete. The implementation of the primitive must allow for this.
On Dorado it is, unfortunately, difficult to implement these primitives as indivisible operations because almost any change to map flags must be preceded by clearing all cache entries in the page. However, it is unacceptable to do this with TaskingOff because the time required might be as long as 16*10 cycles with 256-word pages or 64*10 cycles with 1024-word pages (if every munch in the page is in the cache and dirty), which is too long. Consequently, io tasks will be active during the removal process, and one of them might move a munch back into the cache after it has been passed over by the removal process. For this reason, the present Mesa code flushes once with tasking on and then again with tasking off.
The implementation of SetFlags(v, ...) proceeds as follows (Associate is similar.):
Flush all cache entries for the page in question. If any entry is dirty, removal will cause a write and set Dirty in the map, as discussed earlier.
Disable tasking.
Flush all cache entries for the page again.
oldFlags ← map[v].Flags
If turning on WP: map[v].flags ← [WP: true, Dirty: false, Ref: false].
If setting Vacant: map[v].flags ← [WP: true, Dirty: true, Ref: false].
If turning off WP: map[v].flags ← [WP: false, Dirty: false, Ref: false].
These are done with Map← after which old data is retrieved from the pipe (possibly followed by PreFetch to set map[v].Ref true).
Note: These primitives do not support the complete cache flush discussed earlier; another primitive will probably needed to do this. Also, we really want a primitive that will allow the flags to be sampled and Ref zeroed without changing the value of WP or Dirty. And efficiency may demand primitives particularly tailored to the needs of whatever storage management algorithm is employed.