Volume 5 : Number 1 : Paper 2
June 2002 Special Issue of Best Papers presented at First Iberoamerican Conference on Software Engineering and Knowledge Engineering, ICSEKE 2001. Guest Editors: Juan Carlos Augusto, U. of Southampton, Silvia Teresita Acuna
Title:
The MT Stack: Paging Algorithm and Performance in a Distributed Virtual Memory System

Authors and Affiliations:
Marco T. Morazan,
Myles Nash,
Douglas R. Troeger, Department of Mathematics and Computer Science, Seton Hall University, USA Department of Computer Science, City University of New York, USA

Abstract:
Advances in parallel computation are of central importance toArtificial Intelligence due to the significant amount of time and space their pro- grams require. Functional languages have been identified as providing a clear and concise way of programming parallel machines for artificial intelligence tasks. The problems of exporting, creating, and manipulating processes have been thoroughly studied in relation to the paralleliza- tion of functional languages, but none of the necessary support structures needed for the ab- straction, like a distributed memory, have been properly designed. In order to design and im- plement parallel functional languages efficiently, we propose the development of an all-software based distributed virtual memory system de- signed specifically for the memory demands of a functional language. In this paper, we review the MT architecture and briefly survey the related literature that lead to its development. We then present empirical results obtained from observ- ing the paging behavior of the MT stack. Our empirical results suggest that LRU is superior to FIFO as a page replacement policy for MT stack pages. We present a proof that LRU is an opti- mal page replacement policy. Based on this proof the MT stack page replacement policy was de- veloped and implemented. We outline the paging algorithm and present an argument of partial cor- rectness. The MT stack page replacement policy is superior to LRU, because it does not incur the expensive time penalties associated with imple- menting LRU in software.


Received October 2001, Revised March 2002
Full paper, 15 pages [ PDF, 387 Kb ]