I recently learned that an old colleague and friend, Dr. Dain Samples, died much to young of an undetected heart condition. Dain and I had similar technical interests and touched base every few years; I deeply regret that I have never discussed my dissertation work with him. His dissertation was in a close enough area that it would have seemed like old times...
But more then that, Dain was the kind of person that made a difference; he really cared intrinsically for science; he cared about doing science because of the importance and interest of problems, not just as a career path. He had sacrificed greatly to work in the field that he loved, and the world will be a lesser place without him.
I have collected some of his work, with minor annotation:
Abstract, Profile-Driven Compilation, Alan Dain Samples, CSD-91-627:
As the size and complexity of software continues to grow, it will be necessary for software construction systems to collect, maintain, and utilize much more information about programs than systems do now. This dissertation explores compiler utilization of profile. Several widely help assumptions about collecting profile data are not true. It is not true that the optimal instrumentation problem has been solved, and it is not true that counting traversals of the arcs of a program flow graph is more expensive and complex than counting executions of basic blocks. There are simple program flow graphs for which finding optimal instrumentations is possibly exponential. An algorithm is presented that computes instrumentations of a program to count are traversals (and therefore basic block counts also). Such instrumentations impose 10% to 20% overhead on the execution of a program, often less than the overhead required for collecting basic block execution counts. An algorithm called Greedy Sewing improves the behavior of programs on machines with instruction caches. By moving basic blocks physically closer together if they are executed close together in time, miss rates in instruction caches can be reduced up to 50%. Arc-count profile data not only allows the compiler to know which basic blocks to move closer together, it also allows those situations that will have little or no effect on the final performance of the reorganized program to be ignored. Such a low-level compiler optimization would be difficult to do without arc-count profile data. The primary contribution of this work is the development of TYPESETTER, a programming system that utilizes profile data to select implementations of program abstractions. The system integrates the development, evaluation, and selection of alternative implementations of programming abstractions into a package that is transparent to the programmer. Unlike previous systems, TYPESETTER does not require programmers to know details of the compiler implementation. Experience indicates that the TYPESETTER approach to system synthesis has considerable benefit, and will continue to be a promising avenue of research.
This document appears to have been one of Dain's most widespread writings.
Abstract:
M5 is a powerful, easy to use, general purpose macro language. M5.s syntax allows concise, formatted, and easy to read specifications of macros while still giving the user control over the appearance of the resulting text. M5 macros can have named parameters, can have an unbounded number of parameters, and can manipulate parameters as a single unit. M5 provides separate macro name spaces called 'pools' that simplify the creation and management of context-dependent macros and dynamic macros (macros defined by macros based on the input). Several examples demonstrate m5's power and flexibility, including a random string generator that uses BNF grammars to specify the form of the strings; an implementation of a Turing machine; and a demonstration of how m5 can process LATEX input and programming language source in the same file to simplify code maintenance and documentation.
Stan Dixon of New Mexico State University
has written
a summary
of this paper.
Abstract:
Program performance can be improved on machines with virtual memory by reorganizing
the program's address space. We address the question whether reorganization could
benefit programs on machines with instruction caches. We have performed experiments
to determine the efficacy of restructuring using simple reordering algorithms and profile
data, concluding that performance improvement can be obtained relatively cheaply.
Experiments show improvements in rise rates on the order 30% to 50%, and sometimes
as high as 50% to 80%, by performing a simple algorithm that relocates only 3% to 5% of
the basic blocks of a program.
Review (Reviewer unknown):
A simple approach to instruction cache optimizations. Guided by
profile data their algorithm tries to position
basic blocks, linked by a frequently traversed arc,
adjacently in the address space. Ideally, code
reorganization can improve spatial locality by
matching the blocks temporal locality with physical
locality. Code motion also addresses capacity and
conflict misses.
Simulations show that their strategy reduces the instruction cache
miss-rates, in particular for very small caches (by
1995 standards). They suppose that lower miss-rates
translate directly into shorter execution times,
which doesn't take into account memory bandwidth
contention. However, it is fair to say that their
reorganization will tend to decrease the traffic
between cache and memory, since cache lines are
better utilized.
Abstract:
This document is the definition of the SOAR (Smalltalk on A RISC architecture and
implementation, and is not meant to be the first exposure of a reader to SOAR, the RISC
approach to architecture, or Smalltalk. This document makes several references to the
Proceedings of CS29 Architectural Investigations Class, April 1983. The Proceedings'
first chapter was written by Milce Klein and Pete Foley and was the starting point for this
document. Readers who are unfamiliar with Smalltalk and the RISC I architecture should
not expect to understand everything in this document.
The Dr. A. Dain Samples Scholarship is awarded to a Computer Science or Ministry major. Contact Milligan College, Northeast Tennessee.