Statement of Research
My research
is focused on many different aspects of field programmable gate array
technology, including the design of the chip architectures and the algorithms
that are used to implement circuits in these devices, as well as applications
of FPGAs. In addition to my academic position at the University of
Toronto, I maintain an active involvement in the Altera Toronto Technology
Center, where I lead a research group for a number of years that designed and
implemented CAD algorithms in the Altera Quartus II software package. By
combining my involvement in both the University of Toronto and Altera, it has
been possible to develop research results that are both interesting from the
academic point, as well as being of practical use when implemented in an industrial
quality CAD tool. The main research areas that I have been involved in are
listed below (paper references are from my curriculum vitae, and they also
match the publications listed on the web page http://www.eecg.toronto.edu/~brown/papers.html).
FPGA routing architectures and algorithms
The paper
C43 A
Detailed Router for Field-Programmable Gate Arrays
and the journal paper J13 of the same title represent the
first known published results for the detailed routing problem in FPGAs.
The algorithm described in this paper was used to produce the first known FPGA
routing architecture results, which were published in paper C44 Flexibility
of Interconnection Structures in Field-Programmable Gate Arrays and the journal paper J14 with the
same title. Journal paper J12 A
Stochastic Model to Predict the Routability of Field-Programmable Gate Arrays
provides a theoretical study
of the routing architecture problem, and provides a validation of the practical
results previously produced. Later work on FPGA routing architectures and
algorithms was published in papers C42 "Using
Architectural and CAD Interactions to Improve FPGA Routing Architectures, C41 Modeling
Routing Delays in SRAM-based FPGAs, C40 "Minimizing
FPGA Interconnect Delays,
C36 "On
Two-Step Routing for FPGAs,
C29 "The Case
for Registered Routing Switches in Field Programmable Gate Arrays, and
journal papers J11 "Segmented
Routing for Speed-Performance and Routability in Field-Programmable Gate Arrays
and J9 "Minimizing
FPGA Interconnect Delays.
FPGA chip architectures
Paper C38 "Hybrid
FPGA Architecture and
journal paper J7 with the same title describe a novel chip architecture that
combines the features of a traditional FPGA with those of a Complex PLD.
Paper C34 "The
Computational FPGA Architecture describes another interesting type of FPGA architecture, in which the
traditional lookup tables are combined with arithmetic logic units, leading to
a device that is more capable than a normal FPGA for performing
convocation. This architecture received a United States patent.
Another FPGA architecture study is described in C35 "An LPGA
with Foldable PLA-Style Logic Blocks, which combines the idea is used in a laser programmable
gate array with those used in a traditional PLD. Finally, C7 "Adaptive
FPGAs: High-Level Architecture and a Synthesis Method describes the architecture of an
FPGA that is especially area friendly, and offers some unique features that are
not available in commercial devices.
Technology mapping
Papers C18 "Heuristics
for Area Minimization in LUT-Based FPGA Technology Mapping and journal paper J4 with the same
title describe a novel technology mapping algorithm called IMap. At the time of
publication this algorithm produced best-in-class results compared to other technology
mapping algorithms. Other related papers in this area include C12 "Timing-Driven
Functional Decomposition for FPGAs, C4 "BddCut:
Towards Scalable Symbolic Cut Enumeration, C15 "FPGA Logic
Synthesis using Quantified Boolean Satisfiability, C31 "Technology
Mapping Issues for an FPGA with Lookup Tables and PLA-like blocks, and C32 "Technology
Mapping for Large CPLDs.
Also, paper C15 "FPGA Logic
Synthesis using Quantified Boolean Satisfiability and journal paper J2 "FPGA PLB
Architecture Evaluation and Area Optimization Techniques using Boolean
Satisfiability provide in
unique and interesting approach to mapping circuits into FPGA logic blocks by
using Boolean satisfy ability.
Physical synthesis
A number of
novel results for physical synthesis for FPGAs have been published, including
C21 "Using
Logic Duplication to Improve Performance in FPGAs, C28 "Constrained Clock Shifting for Field Programmable Gate Arrayse, C22 "An
Area-Efficient Timing-Closure Technique for FPGAs using Shannon.s Expansion, C19 "Post-Placement
Functional Decomposition for FPGAs, C11 "Incremental
Retiming for FPGA Physical Synthesis, C10 "Two-Stage
Physical Synthesis for FPGAs,
C9 "Difficulty
of Predicting Interconnect Delay in a Timing Driven FPGA CAD Flow, and the journal paper J3 "Predicting
Interconnect Delay for Physical Synthesis in an FPGA CAD Flow. Variants of some of the
algorithms described in these papers have been implemented in the Quartus II
commercial CAD tool, as part of the research group that I lead in the Altera
Toronto Technology Center.
Placement
Papers C26 "Incremental
Placement for Layout-Driven Optimizations in FPGAs, C2 "Incremental
Placement for Structured ASICs using the Transportation Problem, and the submitted journal paper
JS1 Incremental Placement Techniques for FPGAs and Structured ASICs provide the first known
publications which addressed the incremental placement problem; this problem
involves using a post-processing step to improve placement quality, usually in
a CAD flow that includes physical synthesis. Another placement oriented paper
is provided in C27 "Integrated Retiming and Placement for Field Programmable Gate Arrays, which shows
how timing results can be improved by making a placement algorithm aware of
retiming possibilities.
Power optimization
The study
described in paper C3 "Using
Negative Edge Triggered FFs to Reduce Glitching Power in FPGA Circuits
presents a novel and powerful
way of estimating where glitches occur in FPGA circuits, and gives an algorithm
that can be used to reduce the power dissipation due to these glitches.
FPGA applications
Papers C33 "The Design and Implementation of the NUMAchine Multiprocessor, C30 "The NUMAchine Multiprocessor and C37 "Experience in Designing a Large-scale Multiprocessor using Field-Programmable Devices and Advanced CAD Tools describe experiences in building practical circuits with FPGA devices. These papers describe the new machine multiprocessor, which is a large-scale shared memory multiprocessor designed and constructed at the University of Toronto. Finally, papers C6 "A Multithreaded Soft Processor for SoPC Area Reduction and C17 "Experiences with Soft-Core Processor Design describes a soft processor for implementation on an FPGA.