Computer Engineering Seminar

Designing Commercial Servers and Token Coherence

Mark D. Hill

Computer Sciences Department, University of Wisconsin-Madison
The WISCONSIN MULTIFACET PROJECT ( which I co-lead with David Wood, seeks to improve the multiprocessor servers that form the computational infrastructure for Internet webservers, databases, and other demanding applications. Work focuses on using the transistor bounty provided by Moore's Law to improve multiprocessor performance, cost, and fault tolerance, while also making these systems easier to design and program. This talk quickly summarizes our work and then focuses on one result, Token Coherence.
Most multiprocessor servers enforce a coherence invariant that permits each memory block to have either multiple read-only copies or a single writable copy (but never both at the same time). Current coherence protocols enforce this invariant indirectly via a subtle combination of local actions and request ordering restrictions. Unfortunately, emerging workload and technology trends reduce the attractiveness of these existing solutions.

We propose the TOKEN COHERENCE framework that directly enforces the coherence invariant by counting tokens (all a block's tokens to write; at least one token to read). This token-counting approach enables more obviously-correct protocols that do not rely on request ordering and can operate with alternative policies that seek to improve the performance of future multiprocessors.

This work was selected for IEEE Micro's 2003 "top Picks in Computer Architecture” (
Biography: Mark D. Hill ( is Professor in the Computer Sciences Department and the Electrical and Computer Engineering Department at the University of Wisconsin – Madison. Dr. Hill's research targets the memory systems of shared-memory multiprocessors and high-performance uniprocessors. He is perhaps best known for developing the 3C model of cache misses and for memory consistency model work. In 2000, Hill was named an IEEE Fellow for contributions to cache memory design and analysis. Hill has been at Wisconsin since 1988, with sabbatical years at Sun Microsystems (1995-96) and Universidad Politecnica de Catalunya (2002-03). Hill earned a Ph.D. from Berkeley in 1987 and a B.S.E. from Michigan in 1981.

Sponsored by