I am particularly interested in topics in the systems area of computer science, in particular, practical aspects of programming languages. My research focuses on techniques to make programming easier and more reliable, although sometimes I have obtained results in areas tangential to my main interests.
Older Projects
Dominance Drawings and their Applications
Dominance drawings have some useful properties. In particular, they allow one to determine whether there is a path between two nodes in a graph in O(1) time. Previous algorithms for constructing dominance drawings have assumed that the graph is known when the drawing is made. I have developed a simple algorithm for creating a dominance drawing incrementally.
Determinacy Checking
In my doctoral dissertation, I developed a runtime technique that can detect deficiencies in parallel programs, irrespective of the way the program is scheduled. My LR-tags determinacy-checking method detects indeterminacy in asynchronous parallel programs---such as those using nested parallelism on shared-memory mimd machines. My technique detects violations of Bernstein's conditions, which prevent determinacy races by avoiding write/write and read/write contention between parallel tasks. Previous attempts to enforce Bernstein's conditions at runtime have had non--constant-factor overheads, sometimes coupled with serial-execution requirements.
My LR-tags method can check Bernstein's determinacy conditions (or Steele's generalized conditions) at runtime while avoiding some of the drawbacks present in previous approaches to this problem. My method has constant-factor space and time overheads when run on a uniprocessor machine and runs in parallel on multiprocessor machines, whereas the best previous solution, Cilk's Nondeterminator (a constant-space and nearly constant-time approach), requires serial execution.
Old Pending Projects
The following projects are pending, awaiting time.
Pthieves: A simple, portable workstealing scheduler
Pthieves is a portable work-stealing scheduler, originally developed as part of my doctoral research. Most existing work-stealing schedulers sacrifice portability in order to be space efficient. In essence these schedulers change the usual calling conventions of stack-based languages (such as C, C++, and Java), a change that is inherently non-portable and brittle. Pthieves, on the other hand, is an an efficient portable work-stealing parallel scheduler that runs using only the basic facilities provided by Posix threads.
The original version of Pthieves developed for my dissertation made no claims about efficiency---my only purpose was to have a portable platform on which I could run parallel code. Katrina Ray (an HMC summer student) and I analyzed this scheduler and confirmed a speculation I had made that Pthieves was indeed memory efficient. In addition, I developed preliminary scheduling rules that would ensure efficient use of address space (c.f., memory). Katrina and I refined these rules, and by the end of the summer Katrina proved a bound on the amount of address space required. Unfortunately, the result wasn't quite as good as I had originally hoped.
Distributed Systems
Although my research to date has focused on shared memory machines, I am also interested in distributed systems. As part of my courses on operating systems, I have organized class projects on distributed task execution and distributed shared memory. I see these areas as fertile ground for new research and I hope to extend some of my research results to a distributed setting.
Cotton: A portable, easy to use, thread library interface
Cotton is a thread-library front end that allows programmers to write code for a traditional thread-library (such as Posix threads) in a more natural way than using the thread library's API directly. Under Cotton, parallel programs are written in a style similar to Cilk's parallel extensions to C, but do not require a special translator. Part of the motivation for developing Cotton was to improve the portability of benchmark programs originally written for Cilk. Other possible papers relate to my parallelization of Sleator and Dietz's ordered-list data structure to allow order queries to occur without locking.
Tangled Data Structures
My work on the fat-elements data structure has revealed some interesting research opportunities in garbage collection. I discussed some of those issues as they related to my data structure in my doctoral dissertation, but I believe that other data structures may need similar garbage-collection strategies, especially as garbage collection becomes more common in mainstream programming languages (e.g., Java). Although ad hoc techniques such as weak pointers and finalizers can enable many complex data structures to be garbage collected efficiently, I hope to examine whether there may be better solutions that can handle an even wider range of data structures.
Past Projects
Fat-Elements Method for Functional Arrays
Both my master's thesis and doctoral dissertation discuss remedies for one of the drawbacks of functional programming. Functional programs have good potential for optimization and parallelization because they eschew non-local state, but these benefits come at the price of making several traditional data structures awkward or inefficient to use. To address this problem, I developed the fat-elements method, which provides arrays as a true functional analog of imperative arrays while maintaining the properties that functional programmers expect from their data structures. My method avoids many of the drawbacks of previous approaches to the problem, which typically sacrifice usability or performance.
The fat-elements method efficiently supports array algorithms from the imperative world by providing constant-time operations for single-threaded array use. Fully persistent array accesses may also be performed in constant amortized time if the algorithm satisfies a simple requirement for uniformity of access. For algorithms that do not access the array uniformly or single- threadedly, array reads or updates take at most O(log n) amortized time for an array of size n. The method is also space efficient---creating a new array version by updating a single array element requires constant amortized space.
Research History
I began my research career examining declarative programming languages, intrigued by their potential for parallelization. As my research has progressed, I have moved into areas addressing the difficulties faced by programmers doing more mainstream parallel programming. This later research leveraged my earlier ideas, allowing me to address these problems from a fresh perspective.
While I believe strongly in the importance of depth in research, I have also discovered from personal experience the value of breadth of understanding. My research work has required (and sometimes provided) solutions that lie in other areas in computing science, including graph algorithms, storage management, distributed computing, operating systems, parallel scheduling, and software engineering.
Both my master's thesis and doctoral dissertation discuss remedies for one of the drawbacks of functional programming. Functional programs have good potential for optimization and parallelization because they eschew non-local state, but these benefits come at the price of making several traditional data structures awkward or inefficient to use. To address this problem, I developed the fat-elements method, which provides arrays as a true functional analog of imperative arrays while maintaining the properties that functional programmers expect from their data structures. My method avoids many of the drawbacks of previous approaches to the problem, which typically sacrifice usability or performance.
While persuing my doctoral research, I moved away from my functional programming background and examined reproducibility in parallel systems. In my doctoral dissertation, I described a new, low-overhead, runtime checking technique (analogous to runtime array-bounds checking) that can detect deficiencies in parallel programs, irrespective of the way the program is scheduled. My technique detects violations of Bernstein's conditions--- programs that satisfy these conditions avoid write/write and read/write contention between parallel tasks, allowing efficient lock-free access to data. Previous attempts to enforce Bernstein's conditions, such as Feng and Leiserson's Nondeterminator, have had non--constant-factor overheads, sometimes coupled with serial-execution requirements --- deficiencies my technique avoids.
Publications
Doctoral Dissertation
Version Stamps for Functional Arrays and Determinacy Checking: Two Applications of Ordered Lists for Advanced Programming Languages.
Abstract. Full text is available as PDF (2.3 MB) .
Papers in Refereed Journals
"A New Method For Functional Arrays", written with F. Warren Burton Appeared in the September, 1997, (vol. 7, no. 5) issue of the Journal of Functional Programming. Pp. 487-514. Available as PDF (368 KB) and PostScript (1.16 MB)
Master's thesis
A Data Structure for More Efficient Support of Truly Functional Arrays.
Contains similar ideas to those in "A New Method For Functional Arrays", but less well developed; generally you'd be better reading my JFP paper.
Available as PDF (568 KB) and PostScript (1.74 MB).