%A M. Carey
%T Modeling and evaluation of database concurrency control algorithms
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D September 1983

%A J.-H. Chang
%T High performance execution of Prolog programs
based on a statis data dependency analysis
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D October 1985

%A S.L. Glanville
%T A machine independent algorithm for code generation
and its use in retargetable compilers
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D 1977

%A R.R. Henry
%T Graham-Glanville code genetarors
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D 1984

%A James Larus
%T Compiling and optimizing multiprocessor programs
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D 1986
%X SUMMARY:
Many small to medium sized multiprocessors will preform poorly when
running programs written under the assumption of an unlimited number
of cheap processes and processors. I am looking at transformations to
"compile" a program written for an ideal processor for a practical
one. These transformations can rearrange the process structure of a
program, to make the processes large and longer-lived.

%A J.M. Pendleton
%T A design methodology for VLSI processors
%R Ph.D. dissertation
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D November 1985

%A F. Schmidt
%T Controlling large software development in a distributed environment
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D 1982

%A D. Skeen
%T Crash recovery in distributed database management system
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D 1982

%A D.M. Ungar
%T The design and evaluation of a high performance Smalltalk system
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D March 1986

%A K.S. VanDyke
%T SLANG, a logic simulation language
%R M.S. report
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D June 1982

%A Benjamin G. Zorn
%T Multiprocessor garbage collection in Lisp
%R Ph.D. thesis
%I Department of Electrical Engineering and Computer Science,
University of California at Berkeley
%D December 1987
%X ABSTRACT:
Automatic storage management has been used successfully in Lisp
systems for many years. The methods of automatic management have
evolved in step with the development of new computers and symbolic
applications. Multiprocessor Lisp programs will require new
techniques for minimizing contention for memory and distributing
automatic memory management. Research on garbage collection
algorithms has usually taken the form of reporting the performance of
an algorithm in the context of a particular Lisp system (including
hardware and software). This approach has the drawback that the
factors that affect the performance of garbage collection are hard to
separate and study independently. I intend to use a trace driven
simulation model to study the performance of garbage collection
algorithms. I will transform existing Lisp programs so that when they
run, information about creations of objects and references to objects
is recorded. With this trace information, I will be able to simply
construct simulators for a variety of garbage collection algorithms.
By separating the analysis of garbage collection algorithms from any
particular Lisp system implementation, I will be able to more easily
identify the factors that are most important in efficient algorithms.
With object trace information, I will investigate different approaches
to multiprocessor garbage collection. The most interesting algorithm
appears to be generation garbage collection, first proposed by
Lieberman and Hewitt. I plan to investigate garbage collection models
where all processors stop when garbage collection is required, and
cooperate in collecting the reachable objects. I plan to contrast
this approach, which is not incremental, with an approach that uses
Baker incremental collection using multiple processors (as does
Halstead's Multilisp garbage collector). Some of the most important
considerations for an efficient algorithm include minimizing
synchronization between processors, minimizing shared resource
contention, avoiding memory non-locality (at the cache and page
level), and providing non-disruptive response to the user. With this
thesis, I hope to demonstrate the effectiveness of trace driven
simulation in better understanding memory management problems in Lisp,
and to provide insight into the design of effective garbage collection
algorithms for multiprocessor Lisp.
(Supervisor: Paul N. Hilf