Implementing virtual memory in a vector processor with software restart markers

ABSTRACT

Traditional vector architectures often lack virtual memory support because it is difficult to support fast and precise exceptions for these machines. In this paper, we propose a new exception handling model for vector architectures based on software restart markers, which divide the program into idempotent regions of code. Within a region, the processor can commit instruction results to the architectural state in any order. If an exception occurs, the machine jumps immediately to the exception handler and kills ongoing instructions. To restart execution, the operating system has just to begin execution at the start of the region. This approach avoids the area and energy overhead to buffer uncommitted vector unit state that would otherwise be required with a high-performance precise exception mechanism, but still provides a simple exception handling interface for the operating system. Our scheme also removes the requirement of preserving vector register file contents in the event of a context switch. We show that using our approach causes an average performance reduction of less than 3% across a variety of benchmarks compared with a vector machine that does not support virtual memory.

REFERENCES

• 1: Trimaran homepage. http://www.trimaran.org.
• 2: Krste Asanovic , John Wawrzynek, Vector microprocessors, 1998
• 3: D. I. August et al. Sentinel scheduling with recovery blocks. Technical Report CRHC-95-05, Center for Reliable and High-Performance Computing, University of Illinois at Urbana-Champaign, January 1995.
• 4: K. Bala et al. Software prefetching and caching for translation lookaside buffers. In OSDI-1, November 1994.
• 5: D. H. Brown Associates, Inc. Cray launches X1 for extreme supercomputing, November 2002.
• 6: W. Buchholz. The IBM System/370 vector architecture. IBM Systems Journal, 25(1), 1986.
• 7: DEC. Exception reporting mechanism for a vector processor. U.S. Patent 5,043,867, August 1991.
• 8: Roger Espasa , Mateo Valero , James E. Smith, Out-of-order vector architectures, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.160-170, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: Roger Espasa , Federico Ardanaz , Joel Emer , Stephen Felix , Julio Gago , Roger Gramunt , Isaac Hernandez , Toni Juan , Geoff Lowney , Matthew Mattina , André Seznec, Tarantula: a vector extension to the alpha architecture, Proceedings of the 29th annual international symposium on Computer architecture, p.281, May 25-29, 2002, Anchorage, Alaska
• 10: R. Espasa , M. Valero, Decoupled vector architectures, Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture, p.281, February 03-07, 1996
• 11: Richard E. Hank , Wen-Mei W. Hwu , B. Ramakrishna Rau, Region-based compilation: an introduction and motivation, Proceedings of the 28th annual international symposium on Microarchitecture, p.158-168, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 12: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 13: W. W. Hwu , Y. N. Patt, Checkpoint repair for out-of-order execution machines, Proceedings of the 14th annual international symposium on Computer architecture, p.18-26, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30353]
• 14: Bruce L. Jacob , Trevor N. Mudge, A look at several memory management units, TLB-refill mechanisms, and page table organizations, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.295-306, October 02-07, 1998, San Jose, California, United States
• 15: Gerry Kane, MIPS RISC architecture, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 16: K. Kitagawa et al. A hardware overview of SX-6 and SX-7 supercomputer. NEC Research & Development Journal, 44(1), January 2003.
• 17: A. Klaiber. The technology behind Crusoe processors. White paper, Transmeta Corporation, January 2000.
• 18: Christoforos Kozyrakis , David A. Patterson, Scalable vector media-processors for embedded systems, 2002
• 19: Christos Kozyrakis , David Patterson, Overcoming the limitations of conventional vector processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 20: Ronny Krashinsky , Christopher Batten , Mark Hampton , Steve Gerding , Brian Pharris , Jared Casper , Krste Asanovic, The Vector-Thread Architecture, Proceedings of the 31st annual international symposium on Computer architecture, p.52, June 19-23, 2004, München, Germany
• 21: Samuel Larsen , Rodric Rabbah , Saman Amarasinghe, Exploiting Vector Parallelism in Software Pipelined Loops, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.119-129, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.20]
• 22: Corinna G. Lee , Mark G. Stoodley, Simple vector microprocessors for multimedia applications, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.25-36, November 1998, Dallas, Texas, United States
• 23: Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu , B. Ramakrishna Rau , Michael S. Schlansker, Sentinel scheduling for VLIW and superscalar processors, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.238-247, October 12-15, 1992, Boston, Massachusetts, United States
• 24: Mayan Moudgill , Stamatis Vassiliadis, Precise Interrupts, IEEE Micro, v.16 n.1, p.58-67, February 1996 [doi>10.1109/40.482313]
• 25: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• 26: Francisca Quintana , Jesus Corbal , Roger Espasa , Mateo Valero, Adding a vector unit to a superscalar processor, Proceedings of the 13th international conference on Supercomputing, p.1-10, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305148]
• 27: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 28: Richard L. Sites, Alpha architecture reference manual, Digital Press, Newton, MA, 1992
• 29: Richard Uhlig , David Nagle , Tim Stanley , Trevor Mudge , Stuart Sechrest , Richard Brown, Design tradeoffs for software-managed TLBs, ACM Transactions on Computer Systems (TOCS), v.12 n.3, p.175-205, Aug. 1994 [doi>10.1145/185514.185515]
• 30: Teruo Utsumi , Masayuki Ikeda , Moriyuki Takamura, Architecture of the VPP500 parallel supercomputer, Proceedings of the 1994 conference on Supercomputing, p.478-487, December 1994, Washington, D.C., United States
• 31: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

General Terms:
Design, Performance

Keywords:
exception handling, vector processors