Data Memory Paging Management, cont’d - Embedded.com

Data Memory Paging Management, cont’d



This page concludes the ESP January 2000 article
Data Memory Paging Management, Part 1

View Part 2 of this article published ESP February 2000
Data Memory Paging Management, Part 2

Attacking the problem, continued

In this type of situation, setting the page after the GOTO destination is more common, as in the latter example. If there are several GOTO s to the same label, setting the page once after the label is usually better than doing so several times before the GOTO s. This strategy makes it easier to modify the code later; if you add another GOTO , you don’t have to remember to set Page beforehand.

Shorthand

If you were to follow this method rigorously, you’d need a comment for nearly every instruction and label in the program, which would make the wordiness of the comments in the previous examples tiresome. For shorthand, I use four characters to show the possible paging values. I use a symbol for a page that is definitely not selected, and a # symbol for a page that may be, or definitely is, selected. Thus, when the current page is unknown, the comment would look like: ;#### . When you know the active page is page 1, the comment would be ;–#–– (taking the first character to represent page 0). When the active page may be either 1 or 2, the comment would be ;–##– . In addition, I put comments on the same line as the previous instruction (or label). Thus, using the second fix described above, the code fragments (put together) look like this:

#define  DataReg rD
#define  ChecksumReg_P0 r5
#define  CounterReg_P2 r0
#define  MaskReg_P2 r3

Label1: ;####
A<-X imm 2 ;####
Page<-A ;––#–
A<-A+X imm 1 ;–– #–
X<-A reg CounterReg_P2 ;–– #–
GOTO imm WhatNext
WhatNext: ;#–#–
A<-X imm 2 ;#–#–
Page<-X ;––#–
A<-X reg MaskReg_P2 ;–– #–
Label2: ;####
A<-X imm 0 ;####
Page<-A ;#–––
A<-X reg ChecksumReg_P0 ;#–––
A<-A+X reg DataReg ;#–––
X<-A reg ChecksumReg_P0 ;#–––
GOTO imm WhatNext

Note that the rule for GOTO s and GOTO destinations is not as clear as for the other instructions: from one place, page 2 may be active before a GOTO instruction and from another place, page 0 may be active before a GOTO instruction. If they both jump to the same place in the program, that place may have either page 2 or page 0 active. Symbolically, where the comment before the GOTO has a # , so must the comment after the label. Where the comment before a GOTO has a , the comment after the label may have either symbol.

Summary of the rules to date

This is a good point to take stock of what we’ve learned. The logical rules we have gathered are as follows:

  • L1: variables must be identified and tracked not by ambiguous logical registers, but by unambiguous physical registers
  • L2: wherever a paged variable is referenced, the page associated with the variable must be active — and equally important, all other pages must be inactive
  • L3: an instruction that modifies Page will change the active page
  • L4: any page that may be active before an instruction that does not modify Page and is not a flow-control instruction may be active after that instruction
  • L5: any page that may be active before a flow-control instruction may be active at the destination(s)
  • L6: any page that may be active before encountering a label may be active after the label

These rules can be expressed in symbolic terms:

  • S1: any variable name given to a register in page 0 must have the suffix _P0 , any variable name given to a register in page 1 must have the suffix _P1 , and so on
  • S2: any instruction that references a variable name with a suffix _P0 must be accompanied with a comment: ;#––– . Any instruction that references a variable name with a suffix _P1 must be accompanied with a comment: ;–#–– , and so on
  • S3: an instruction that modifies Page has a comment after it that reflects the new value of Page
  • S4: where a # appears in a comment before an instruction that does not modify Page and is not a flow-control instruction, so must a # appear in the comment after it
  • S5: where a # appears in a comment before a GOTO , so must a # appear in the comment after the destination label
  • S6: where a # appears in a comment before a label, so must a # appear in the comment after the label

The purpose of rule 1 is to identify variables not just by logical register, but by physical register as well. The purpose of rule 2 is to ensure that every reference to the logical register associated with a variable will, in fact, access the correct physical register. The purpose of rules 3 to 6 is to keep track of which page(s) may be active at any time.

This article represents the essence of my paging method. When the method is strictly adhered to, every instruction that accesses a paged register is effectively accompanied by a proof that the correct page is active at the time, regardless of which execution path led to that instruction. In the second part of this article, I will expound on the rules to cover conditional statements and subroutines, thus making the method suitable for use in nontrivial programs.

View Part 2 of this article published ESP February 2000
Data Memory Paging Management, Part 2

Hugh O’Byrne graduated from University College Dublin in 1995 with a BS in computer science. He’s currently pursuing an MS in mathematics.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.