Page table management in local/remote architectures

ABSTRACT

We conjecture that a paged memory with page migration by the operating system may be an effective system environment for a local/remote shared memory architecture executing a single parallel computation. Implementing a paged memory in such an architecture raises several issues with respect to page table management. These issues include page table placement, page table replication level, and page table storage overhead. We discuss these issues, propose alternative solutions, and present an experimental evaluation of the solutions. The experiments were conducted using software implemented page tables on a 32-node BBN Butterfly. The experiments have investigated the case of a single shared-memory parallel computation with one user process per processor. The implementation captures the costs of page table entry locking and reference information updating. Each user process has a copy of the computation's code and non-shared variables in local memory. Only shared data references use the page tables. A separate processor has a migration daemon that periodically unblocks itself and examines the page tables to make policy decisions concerning page migration. The conclusions drawn include that: 1) a fully replicated page-indexed page table significantly reduces network, memory, and lock contention in comparison to a single copy, 2) a fully replicated page-indexed page table faces a severe memory utilization problem in large-scale architectures, 3) a proposed approach based on inverted page tables appears to be a promising alternative to a fully replicated page-indexed page table.

REFERENCES

• 1: BBN. Butterfly Parallel Processor Overview. Bolt Beranek and Newman Adv. Computers Inc., Cambridge, MA, June 1985.
• 2: F. Darema-Rogers , G. F. Pfister , K. So, Memory access patterns of parallel scientific programs, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.46-58, May 11-14, 1987, Banff, Alberta, Canada
• 3: M.D. Hill etal. Spur: a vlsi multiproeessor workstation. IEEE Computer, November 1985.
• 4: D. C~jskl, D. Kuck, D. Lawrie, and A. Sarneh. Cedar--a large scale multiprocessor. In Proceedings of the 1983 International Conference on Parallel Processing, pages 524- 529, August 1983.
• 5: Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.229-239, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10610]
• 6: Michael N Nelson, Virtual Memory for the Sprite Operating System, University of California at Berkeley, Berkeley, CA, 1986
• 7: G. Pfister, W. Brentley, D. George, S. Harvey, W. Kleinfelder, K. McAuliffe, E. Melton, V. Norton, and J. Weiss. The IBM research parallel processor prototype (RPJ): introduction and architecture. In Proceedings of the 1985 international Conference on Parallel Processing, August 1985.
• 8: Richard Rashid , Avadis Tevanian , Michael Young , David Golub , Robert Baron, Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.31-39, October 1987, Palo Alto, California, United States
• 9: Sequent Computer Systems, Inc. Balance 8000 Technical Summary. Sequent Computer SysterrL~, Inc., 1986.
• 10: Alan Jay Smith, Cache evaluation and the impact of workload choice, Proceedings of the 12th annual international symposium on Computer architecture, p.64-73, June 17-19, 1985, Boston, Massachusetts, United States
• 11: A.J. Smith. A modified working set paging algorithm. IEEE Transactions on Computers, C-25(9):907- 914, September 1976.
• 12: Shreekant S Thakkar , Alan E Knowles, A high-performance memory management scheme, Computer, v.19 n.5, p.8-22, May 1986
• 13: D. A. Wood , S. J. Eggers , G. Gibson , M. D. Hill , J. M. Pendleton, An in-cache address translation mechanism, Proceedings of the 13th annual international symposium on Computer architecture, p.358-365, June 02-05, 1986, Tokyo, Japan

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

General Terms:
Design