%% This LaTeX-file was created by Wed Feb 9 20:44:00 2000 %% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team %% Do not edit this file unless you know what you are doing. \documentclass{article} \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \IfFileExists{url.sty}{\usepackage{url}} {\newcommand{\url}{\texttt}} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. \providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeatletter \usepackage[T1]{fontenc} \setlength{\oddsidemargin}{0in} \setlength{\evensidemargin}{0in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0in} \setlength{\headsep}{0.5in} \setlength{\textwidth}{6.5in} \setlength{\textheight}{9.0in} \setlength{\parindent}{0in} \setlength{\parskip}{0.05in} \makeatletter \makeatother \makeatother \makeatother \makeatother \begin{document} \title{Software Distributed Shared Memory Systems} \author{Norman Matloff} \date{February 8, 2000} \maketitle \section{Introduction} The general consensus in the parallel processing community is that the shared-memory programming paradigm is easier to program in than the message-passing paradigm. Yet shared-memory hardware is quite expensive, costing hundreds of thousands, or even millions, of dollars. By contrast, message-passing hardware is readily available in the form of ordinary networks of workstations. The goal of software distributed shared memory (SDSM) is to get ``the best of both worlds''--the ease of programming of the shared-memory paradigm, and the attractive price-performance ratio of networks of workstations. The SDSM programmer has the illusion of shared memory, and thus the clarity, without the expense of real shared-memory hardware. With shared-memory hardware, a shared variable is truly shared; it represents a single, physical memory location accessible by all processors.\footnote{% This is not quite true, since even shared-memory hardware machines usually have caches at each processor, so there really isn't a single copy after all. } In an SDSM environment, the sharing is only virtual; each processor ``secretly'' has its own copy of a given shared variable, though this is supposed to be transparent to the programmer (or, at least, as transparent as possible). Some mechanism is needed to keep the various copies consistent with each other; this is done by communication between the nodes, unseen by the application programmer. \section{Some Infrastructure} \subsection{Memory Allocation} Shared-memory systems, whether hardware- or software-based, often allocate memory by placing all global variables inside a huge \textbf{struct}. As an example, suppose we wish to have these global (thus shared) variables: \begin{verbatim} int x,y; int z[1000]; char u,v; \end{verbatim} In many SDSMs and even many hardware-based shared-memory machines, we would probably have to change this to: \begin{verbatim} struct glob { int x,y; int z[1000]; char u,v; } *mem; ... mem = malloc(sizeof(glob)); \end{verbatim} Then instead of statements like \begin{verbatim} x = 12; \end{verbatim} we would have \begin{verbatim} mem->x = 12; \end{verbatim} Of course, one could make the code less cluttered by using a trick like this: \begin{verbatim} #define X mem->x ... X = 12; \end{verbatim} \subsection{Cache Coherency} Just as hardware-based shared-memory machines need to have cache coherency mechanisms, SDSMs do too. A typical model would be a network of workstations, each machine running both a copy of the application program and an SDSM server program. Each global variable would have a copy at one or more of the servers. The application programs communicate with the servers to read and write shared variables, and the servers are written to maintain coherency with each other's copies. The standard cache coherency protocols, e.g. MESI, can be used here. For our purposes, it is easiest to assume that the application program and the server at a given node are the same program, say running as separate processes generated by a call to fork() from a parent program. This is to enable easy communication and sharing between the application and the server, but other models are possible too. The two main types of SDSMs are \textbf{paged-based} and \textbf{object-based}. \section{Page-Based SDMs} Page-based SDMs rely on the hardware's virtual memory system. The best-known example is probably Treadmarks (\url{http://www.cs.rice.edu/~willy/TreadMarks/overview.html}), developed at Rice University. Others include JIAJIA (\url{http://www.ict.ac.cn/chpc/dsm/index.html}) at the Academy of Sciences in China. \subsection{View Seen by the Application Programmer} For the most part, an application program in this kind of SDSM will look just like one on a shared-memory machine. \subsection{Internal Implementation} Here we make use of the mprotect() Unix system call. This function allows the Unix programmer to declare certain memory areas in his/her program as having READ(-only) permission, READ/WRITE permission or permission NONE. If the program executes a statement violating the permission for a given page in memory, a SIGSEGV signal is generated, which triggers execution of the Unix signal handler which the programmer wrote in the program. In general, the mprotect() function is used for safety. If the programmer knows that he/she wants certain variables to be read-only, then if a bug in the program causes such a variable to be written to, the error will be caught. For an SDSM, we use mprotect() with a different goal. Initially, we set all pages within the global \textbf{struct} to have permission NONE. This is analogous to state Invalid in MESI. The first time a program accesses a global variable, that will cause a page fault, which transfer control to the signal handler---which is the server. The server then provides the application with the contents of the given page, and sets the MESI state accordingly, again using a call to mprotect(). The servers are also in communication with each other, to maintain coherency. \section{Object-Based SDSMs} One of the problems with page-based SDSMs (and, for that matter, also with caches in shared-memory hardware machines) is that of \textbf{false sharing}. Here our concern is that two variables with no relation at all to each other have the misfortune of being in the same page. If one of the two variables becomes invalid due to having been written to at another node, the other variable becomes invalid too, even though its data is in fact still perfectly good. Object-based SDSMs allow MESI states for units of data which are smaller and of varying sizes, thus eliminating the false-sharing problem. In our example here, though, we will assume for the sake of simplicity that objects are of only one size, specifically one word. A number of object-based DSMs are available, such as the Adsmith system (\url{http://www.hensa.ac.uk/parallel/environments/pvm3/adsmith/}) developed at Taiwan National University. \subsection{View Seen by the Application Programmer} The main new feature here is that before accessing a variable, a programmer must ``ask permission'' before reading or writing a shared variable. For example, instead of \begin{verbatim} mem->x = 3; \end{verbatim} we would have something like \begin{verbatim} get_write_permission(&mem->x); mem->x = 3; release_write_permission(&mem->x); \end{verbatim} \subsection{Internal Implementation} The permission functions are executed by the servers, thus enabling coherency operations. \end{document}