Tim Sherwood
Associate Vice Chancellor for Research
Professor of Computer Science
University of California, Santa Barbara
Office 5163, Harold Frank Hall
Santa Barbara, CA 93106-5110
sherwood@cs.ucsb.edu
Interest Areas
I am interested in everything from low-level gate effects and logic design all the
way through system architecture and applications. If it involves both some sort
of hardware and some sort of software, then I am into it. Below is a word-cloud
from the abstracts of the papers I have written since joining UCSB to give you
a sense, but if you want to know know what I am going to do next you have
to talk to me in person!
Some Recent Research Awards
A Brief Overview of Some Research
- Line-Rate Network Processing with Guaranteed Performance: Next generation network processing
applications, such as deep packet scanning, are throughput-driven, irregular, and bounded by the need
for worst-case performance. These characteristics are not well supported by cache-heavy
latency-intolerant traditional designs. The architectures we are developing take advantage of many
small wide word on-chip memories [netproc], tools that allow network memories to be accurately
modeled [tcamjournal, tcampower, srammodel], and careful worst-case latency hiding
with virtual pipelines [vpnm, vpnm-journal]. With these techniques we can design machines
capable of very rapidly traversing the large graph structures common to many network and security
applications. Through a rethinking of one of the key string-searching algorithms and the theory behind
it, we have further developed methods that are able to scan network packets 10x faster than prior
approaches [string, string1, stringmicro], prove that those algorithms are
correct [stringproof, string-journal], and implement those algorithms in a functional
hardware prototype [stringtaco].
- Digital MEMS Control Architectures: Micro-Electro-Mechanical Systems (MEMS) combine
lithographically formed mechanical structures with electrical and computational elements to create
physical systems that operate on the scale of microns. Many complex MEMS sensors, such as
accelerometers and gyroscopes, require feedback control at the time scale of device oscillation -
usually in the sub $\mu$s domain. To enable smaller and more complex MEMS sensors, a programmable
platform is needed, one that can handle high-throughput low-overhead event handling without
compromising tight size, cost, and power restrictions. To address these concerns our initial prototype
hardware was an interleaved multi-threaded AVR processor supporting eight threads [jackknife2]
built using our new architectural control synthesis method [jackknife1]. While
multi-threading is typically used to improve resource utilization, we demonstrate that in the embedded
space it can provide zero-cycle context switching and interrupt service threads (IST), enabling complex
programmable control in latency constrained environments. Building on our experience implementing a
working controller for a MEMS-based quantum-tunneling accelerometer, we proposed, evaluated, and
synthesized both novel control architectures [mems] and metric-based closed-loop control
transformations to reduce power consumption [mems2]
- Introspective Computer Architectures: Developing fast, quality software on a modern computer
system is by no means easy. Even today, software bugs are so damaging and widespread that they cost the
U.S. economy an estimated $59.5 billion annually (more than half a percent of the US GNP). As our
applications and software continue to grow in complexity, it is worth considering a processor with
built-in support for introspection -- everywhere from the circuits to the software. Such a design
could enable systems that monitor themselves for defects, that catch security violations as they occur,
and optimize themselves over time. My lab has been exploring the use of both existing board level
interconnect [perf-analysis] and novel technologies such as 3D-Integration [3dtherm] to add
introspection hardware in the last stages of processor fabrication [introspect3d,
introspect3dmicro]. Such support could allow both novel methods of generating execution
profiles [multihash, quantify, rap, rapjournal] and, more interestingly, the
tracking of ``fat'' information-flow tags to help analyze complex software systems [systomo,
rangecache].
- Computing at the Whiteboard: When solving complex problems, exploring multiple designs, or even
simply creating lists, nothing is more natural than quick sketches on a whiteboard. Software that can
understand and react to these sketches in real time would enable written equations to be captured and
solved, sketches of state machines to be executed and debugged, and biological systems to be diagrammed
and simulated all at the same time. Performing computation on the whiteboard requires working with
inputs that are inherently noisy, whose interpretations are ambiguous, in a space frequently shared for
many separate purposes, all interactively with the user. While many pieces of the solution exist in
isolation, a real roadblock to progress in the area is the lack of a unifying framework enabling
composability, modularity, and multiple interpretations of the same data. My lab has developed an
experimental framework with support for managing and coordinating shared resources (such as stroke
data), scheduling communication (through stroke attributes), dynamically controlling the allocation and
deallocation of application code, and regularizing the integration of sketch-based components through a
minimal interface. We will soon demonstrate the first general purpose sketch recognition system capable
of handling multiple, simultaneous applications [boardquant, boardworkshop,
boarduist].
- Provable Security Properties for Embedded Systems: Systems responsible for controlling aircraft,
protecting a bank's master secret keys, or regulating access to extremely sensitive commercial or
military information, all demand a level of assurance far beyond the norm. Creating these systems today
is an incredibly expensive operation both in terms of time and money; and even assessing the assurance
of the resulting system can cost upwards of $10,000 per line of code. Building upon my groups
experience developing novel security methods for FPGAs [rcsec1, rcsec-cs-journal,
rcsec-dt-journal, rcsecmoats, rcsec-recon-journal, rcsec-todaes-journal], we
have developed a novel method for building embedded systems that allow us to verify the integrity or
secrecy of all information executing in that system. This includes safety from covert channels,
information flows introduced during refinement, implicit flows, and even timing channels. The key to
our approach is to verify properties of the both the hardware and the software down at the lowest level
digital level of refinement -- at the individual Boolean logic gates. Specifically we developed a new
logic discipline for security, {\it Gate-Level Information-Flow Tracking (GLIFT)} logic, and
demonstrated its effectiveness by creating functional units, control logic, a new ISA, language,
compiler, and fully synthesizable prototype CPU in this new logic [glift-cpu, glift-toppick,
glift-lease].
- Program Phase Analysis: As a graduate student a major contribution of my thesis was SimPoint 1.0.
SimPoint uses techniques from machine learning to surgically extract the regions of program execution
that will quickly and accurately represent the behavior of the whole execution for the purposes of
architecture simulation [largescale]. At the time it was not uncommon for papers and even
graduate text books to use the first billion instructions of execution to represent the whole program,
which we showed can lead to order-of-magnitude errors. Over the years we further refined the
technique [bbda, cophase, phase6, phasebook, phasemicro,
waveletphase], we examined its machine learning implications [simpointjmlr], and we
demonstrated a hardware-assisted online phase-tracking method that allows processors to adapt to
long-term program behaviors [phasetaco, phasetrack, phaseprof]. Most major
microprocessor companies now use SimPoint or a derivative to guide their architectural studies.