% -*- Mode:TeX -*-

% Source file for ``Supporting State-Sensitive Computation in a Dataflow System''
% Paul Barth and Rishiyur Nikhil
% March, 1989

\documentstyle[11pt]{article}

% HORIZONTAL MARGINS
% Left margin 1 inch (0 + 1)
\setlength{\oddsidemargin}{0in}
% Text width 6.5 inch (so right margin 1 inch).
\setlength{\textwidth}{6.5in}
% ----------------
% VERTICAL MARGINS
% Top margin 0.5 inch (-0.5 + 1)
\setlength{\topmargin}{-0.5in}
% Head height 0.25 inch (where page headers go)
\setlength{\headheight}{0.25in}
% Head separation 0.25 inch (between header and top line of text)
\setlength{\headsep}{0.25in}
% Text height 9 inch (so bottom margin 1 in)
\setlength{\textheight}{9in}
% ----------------
% PARAGRAPH INDENTATION
\setlength{\parindent}{0in}
% SPACE BETWEEN PARAGRAPHS
\setlength{\parskip}{\medskipamount}
% ----------------
% VARIOUS CONVENIENT WIDTHS RELATIVE TO THE TEXT WIDTH, FOR BOXES.
\newlength{\hlessmm}
\setlength{\hlessmm}{\textwidth}
\addtolength{\hlessmm}{-2em}

\newlength{\hlessmmmm}
\setlength{\hlessmmmm}{\textwidth}
\addtolength{\hlessmmmm}{-4em}
% ----------------
% CODE FONT (e.g. {\cf x := 0}).
\newcommand{\cf}{\footnotesize\tt}
% ----------------------------------------------------------------
% ID CODE DISPLAYS.
% Id code displays are enclosed between \bid and \eid.
% Most characters are taken verbatim, in typewriter font,
% Except:
%  Commands are still available (beginning with \)
%    but use ` and ' instead of { and }
%  Math mode is still available (beginning with $)
%    but use ~ and ! for ^ and _

\outer\def\beginid{%
  \begin{list}{$\bullet$}{%
    \setlength{\topsep}{0in}
    \setlength{\partopsep}{0in}
    \setlength{\itemsep}{0in}
    \setlength{\parsep}{0in}
    \setlength{\leftmargin}{1.5em}
    \setlength{\rightmargin}{0in}
    \setlength{\itemindent}{0in}
  }\item[]
  \catcode`\{=12
  \catcode`\}=12
  \catcode`\&=12
  \catcode`\#=12
  \catcode`\%=12
  \catcode`\~=12
  \catcode`\_=12
  \catcode`\^=12
  \catcode`\~=7
  \catcode`\!=8
  \catcode`\'=2
  \catcode`\`=1
  \obeyspaces
  \obeylines \footnotesize\tt}

\outer\def\endid{%
  \end{list}
  }

{\obeyspaces\gdef {\ }}

% ----------------
% ILLUSTRATIONS
% This command should specify a JJ directory for ps files for illustrations.
\def\psfileprefix{/jj/nikhil/docs/89-03-managers/}
\def\illustration#1#2{
\vbox to #2{\vfill\special{psfile=\psfileprefix#1.ps hoffset=-72 voffset=-45}}} 

% \illuswidth is used to set up boxes around illustrations.
\newlength{\illuswidth}
\setlength{\illuswidth}{\textwidth}
\addtolength{\illuswidth}{-7pt}

% ----------------------------------------------------------------
% ----------------------------------------------------------------

\typein{Include which sections? (intro,manage,impl,comparison,disc):}

% ----------------------------------------------------------------

\begin{document}

\begin{center}

{\Large Supporting State-Sensitive Computation in a Dataflow System}

Paul S. Barth \\
Rishiyur S. Nikhil

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\footnotetext[2]{
 This report was supported in part by the Advanced Research Projects Agency
of the Department of Defense under the Office of Naval Research contract
N00014-84-K-0099.
Paul Barth was supported by a fellowship from Schlumberger Technology
Corporation.
}
\renewcommand{\thefootnote}{\arabic{footnote}}

Massachusetts Institute of Technology \\
Laboratory for Computer Science \\
{\footnotesize
545 Technology Square, Cambridge, MA 02139, USA

\begin{tabular}{ll}
barth@juicy-juice.lcs.mit.edu    & (617)-253-3219 \\
nikhil@juicy-juice.lcs.mit.edu   & (617)-253-0237
\end{tabular}
}

\vspace{1cm}

{\bf Abstract}

\begin{minipage}{\hlessmmmm}

\end{minipage}

\end{center}

\vspace{1.5cm}

% ----------------

\input{intro}
\input{manage}
\input{impl}
%\input{comparison}
%\input{disc}

\bibliographystyle{abbrv}
\bibliography{fpca}

\end{document}

% The second example of a memory
% manager demonstrate that non-trivial managers can be written, and
% that the implementation is efficient enough to support systems
% programming.  It also demonstrates the importance of explicit 
% scheduling functions.

% \subsubsection{Memory Allocation}
% A more complex example is a buddy-system memory allocator.  In a
% buddy system, memory is divided into blocks of size $2^{k}$,
% for $k$ from  1 to $m$, the log of the size of memory.
% Each block lies on a $2^{k}$ memory boundary.   Blocks of
% memory are allocated and deallocated, and split and
% coelesced to avoid waste yet maintain blocks  large enough
% for arrays.

% The manager implementation of this fairly straightforward.
% A manager is defined that handles allocation and deallocation
% requests for blocks of size $2^{k}$.  $m$ instances of this manager
% are created, one for each block size from 1 to $m$.  These managers are
% placed in the array $B$, with the index indicating the exponenent of the
% block size being managed.  The manager definition for each manager is below:


% \begin{verbatim}
% % B,m are globals
% def_manager buddy mem_q (make_alloc_q,enq_alloc,deq_alloc) =
%      alloc b k when entries? = (top_of_q mem_q),signal (rest mem_q)
%   || dealloc b mem = {k = logsize mem;
%                       my_buddy = get_buddy mem;
%                       In
%                         if (free? my_buddy) then
%                           (dealloc B[k+1] (coalesce mem my_buddy)),mem_q
%                         else _,signal (enqueue mem mem_q)};

% def make_alloc_q = make_fifo_q;
% def make_alloc_deq q = make_alloc_deq q;
% def enq_alloc q entry = 
%    {k = (entry_arg entry 2);
%     b = alloc B[k+1] k+1;
%     b1,b2 = split b;
%     call dealloc B[k] b1;
%     call dealloc B[k] b2;
%     In
%       cons entry q};

% \end{verbatim}

% Low level details of the support functions are omitted for simplicity.
% The state variable is a queue of memory blocks of size $2^{k}$.  The
% {\tt alloc} request handler has a guard that checks the queue for
% entries.  If there are entries, the top of the queue is returned and the
% rest of the queue becomes the new state.  If the queue is empty, control
% passes to the enqueue function, which attempts to allocate the next larger
% size block. This recurs until a block is
% found, or we fail with the largest block size ($2^{m})$.  When a larger
% block is found, it is split and the two halves are put on the next
% smaller queue via a dealloc request.  The {\tt dealloc} request handler
% checks to see if the incoming memory can be coelesced with its
% ``buddy'', i.e., the other block of memory originally produced by the
% split.  If so, they are coelesced and dealloc is recursively called on
% the manager for $2^{k+1}$ size blocks.  Otherwise the block is simply
% enqueued.  Note that the direct call from the signal to any waiting
% alloc requests prevents blocks from being coelesced when there are
% outstanding allof.
