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.
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.
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.
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.
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.
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.
Ongoing research directions I continue to be interested in advancing the state of the art in the synthesis and physical synthesis areas, as indicated by recent papers. Also, with the recent release of open specifications that allow the connection of FPGA chips to both Intel and AMD modern processors, FPGA-based coprocessing is becoming increasingly promising. A key innovation needed to leverage this technology across the board-base is a tool flow that allows software programmers, as opposed to hardware designers, to access the FPGA devices. I am interested in a number of research aspects related to this area, and intend to pursue related research directions.