Steven Wilton

Recent years have seen a dramatic increase in the use of hardware accelerators to perform machine learning computations. Designing these circuits is challenging, especially due to bugs that may only manifest after long run times, and interactions between hardware and software that are complex to understand. As a result, debugging the machine learning accelerator and ensuring that the system is delivering acceptable performance are very time-consuming processes that significantly limit productivity. This dissertation focuses on investigating how additional circuitry added to machine learning hardware designs may allow for the effective debugging of those systems and on gathering insights on how to better debug those systems. More specifically, we focus on techniques that are suitable for accelerators implemented using Field-Programmable Gate Arrays (FPGA), since many accelerators are prototyped using this type of reconfigurable fabric. This dissertation is comprised of four major contributions towards this goal. First, we present a debugging framework that allows the designer to observe domain-specific information (e.g. sparsity and other statistics) about the machine learning workload running on the accelerator, rather than raw information that is expensive to trace. This includes the creation of a custom circuitry that allows information to be recorded for at least 21.8x longer than in previous debugging architectures. Second, we create a technique to reduce the time between debug iterations by creating an overlay that enables designers to change which signals are being traced and select how those signals are being aggregated without the need of resynthesizing the design. Third, we investigate how to debug underperforming training jobs, resulting in a novel programmable debug architecture that allows designers to create custom ways of aggregating data at debug time, instead of being constrained by a few options selected at compile time. Finally, we investigate the impacts of hardware acceleration on the optimization landscape of training systems and how this information may be used to accelerate debug.We anticipate that the concepts presented in this thesis will be used to allow designers to aggregate domain-specific information in future commercial debugging tools and to motivate future work on improving the training performance of hardware accelerators.

View record

Field-Programmable Gate Array (FPGA) technology is rapidly gaining tractionin a wide range of applications. Nonetheless, FPGA debug productivity is a keychallenge. For FPGAs to become mainstream, a debug ecosystem which providesthe ability to rapidly debug and understand designs implemented on FPGAs isessential. Although simulation is valuable, many of the most elusive and troublesomebugs can only be found by running the design on an actual FPGA. However,debugging at the hardware level is challenging due to limited visibility. To gainobservability, on-chip instrumentation is required.In this thesis, we propose methods which can be used to support rapid and efficientimplementation of on-chip instruments such as triggers and coverage monitoring.We seek techniques that avoid large area overhead, and slow recompilationof the user circuit between debug iterations.First, we explore the feasibility of implementation of debug instrumentationinto FPGA circuits by applying incremental compilation techniques to reduce thetime required to insert trigger circuitry. We show that incremental implementationof triggers is constrained by the mapping of the user circuits.Second, we propose a rapid triggering solution through the use of a virtual overlayfabric and mapping algorithms that enables fast debug iterations. The overlayis built from leftover resources not used by the user circuit, reducing the area overhead.At debug time, the overlay fabric can quickly be configured to implementdesired trigger functionalities. Experimental results show that the proposed approachcan speed up debug iteration runtimes by an order of magnitude comparedto circuit recompilation.Third, to support rapid and efficient implementation of complex triggering capabilities, we design and evaluate an overlay fabric and mapping tools specializedfor trigger-type circuits. Experimental evaluation shows that the specialized overlaycan be reconfigured to implement complex triggering scenarios in less than 40 seconds, enabling rapid FPGA debug.The final contribution is a scalable coverage instrumentation framework basedon overlays that enables runtime coverage monitoring during post-silicon validation.Our experiments show that using this framework to gather branch coveragedata is up to 23X faster compared to compile-time instrumentation with a negligibleimpact on the user circuit.

View record

High-level synthesis (HLS) is a rapidly growing design methodology that allows designers to create digital circuits using a software-like specification language. HLS promises to increase the productivity of hardware designers in the face of steadily increasing circuit sizes, and broaden the availability of hardware acceleration, allowing software designers to reap the benefits of hardware implementation. One roadblock to HLS adoption is the lack of an in-system debugging infrastructure. Existing debug technologies are limited to software emulation and cannot be used to find bugs that only occur in the final operating environment. This dissertation investigates techniques for observing HLS circuits, allowing designers to debug the circuit in the context of the original source code, while it executes at-speed in the normal operating environment. This dissertation is comprised of four major contributions toward this goal. First, we develop a debugging framework that provides users with a basic software-like debug experience, including single-stepping, breakpoints and variable inspection. This is accomplished by automatically inserting specialized debug instrumentation into the user’s circuit, allowing an external debugger to observe the circuit. Debugging at-speed is made possible by recording circuit execution in on-chip memories and retrieving the data for offline analysis. The second contribution contains several techniques to optimize this data capture logic. Program analysis is performed to develop circuitry that is tailored to the user’s individual design, capturing a 127x longer execution trace than an embedded logic analyzer. The third contribution presents debugging techniques for multithreaded HLS systems. We develop a technique to observe only user-selected points in the program, allowing the designer to sacrifice complete observability in order to observe specific points over a longer period of execution. We present an algorithm to allow hardware threads to share signal-tracing resources, increasing the captured execution trace by 4x for an eight thread system. The final contribution is a metric to measure observability in HLS circuits. We use the metric to explore trade-offs introduced by recent in-system debugging techniques, and show how different approaches affect the likelihood that variable values will be available to the user, and the duration of execution that can be captured.

View record

A soft vector processor (SVP) is an overlay on top of FPGAs that allows data- parallel algorithms to be written in software rather than hardware, and yet still achieve hardware-like performance. This ease of use comes at an area and speed penalty, however. Also, since the internal design of SVPs are based largely on custom CMOS vector processors, there is additional opportunity for FPGA-specific optimizations and enhancements.This thesis investigates and measures the effects of FPGA-specific changes to SVPs that improve performance, reduce area, and improve ease-of-use; thereby expanding their useful range of applications. First, we address applications needing only moderate performance such as audio filtering where SVPs need only a small number (one to four) of parallel ALUs. We make implementation and ISA design decisions around the goals of producing a compact SVP that effectively utilizes existing BRAMs and DSP Blocks. The resulting VENICE SVP has 2x better performance per logic block than previous designs.Next, we address performance issues with algorithms where some vector elements ‘exit early’ while others need additional processing. Simple vector predication causes all elements to exhibit ‘worst case’ performance. Density time masking (DTM) improves performance of such algorithms by skipping the completed elements when possible, but traditional implementations of DTM are coarse-grained and do not map well to the FPGA fabric. We introduce a BRAM-based implementation that achieves 3.2x higher performance over the base SVP with less than 5% area overhead.Finally, we identify a way to exploit the raw performance of the underlying FPGA fabric by attaching wide, deeply pipelined computational units to SVPs through a custom instruction interface. We support multiple inputs and outputs, arbitrary-length pipelines, and heterogeneous lanes to allow streaming of data through large operator graphs. As an example, on an n-body simulation problem, we show that custom instructions achieve 120x better performance per area than the base SVP.

View record

As the CMOS technology scales down, the cost of fabricating an integrated circuit becomes more expensive. Field-programmable gate arrays (FPGAs) are becoming attractive because their fabrication costs are amortized among many customers. A major challenge that face adopting FPGAs in many low-power applications is their high power consumption due to their reconfigurablity. A significant portion of FPGAs' power is dissipated in the form of static power during applications' idle periods.To address the power challenge in FPGAs, this dissertation proposes architecture enhancements and algorithms support to enable powering down portions of a chip during their idle times using power gating. This leads to significant energy savings especially for applications with long idle periods, such as mobile devices. This dissertation presents three contributions that address the major challenges in adopting power gating in FPGAs.The first contribution proposes an architectural support for power gating in FPGAs. This architecture enables powering down unused FPGA resources at configuration time, and powering down inactive resources during their idle times by the help of a controller. The controller can be placed on the general fabric of an FPGA device. The proposed architecture provides flexibility in realizing varying numbers and structures of modules that can be powered down at run-time when inactive.The second contribution proposes an architecture to appropriately handle the wakeup phase of power-gated modules. During a wakeup phase, a large current is drawn from the power supply to recharge the internal capacitances of a power-gated module, leading to reduced noise margins and degraded performance for neighbouring logic. The proposed architecture staggers the wakeup phase to limit this current to a safe level. This architecture is configurable and flexible to enable realizing different user applications, while having negligible area and power overheads and fast power up times.The third contribution proposes a CAD flow that supports mapping users' circuits to the proposed architecture. Enhancements to the algorithms in this flow that reduce power consumption are studied and evaluated. Furthermore, the CAD flow is used to study the granularity of the architecture proposed in this dissertation when mapping application circuits.

View record

Electronic devices have come to permeate every aspect of our daily lives, and at the heart of each device is one or more integrated circuits. State-of-the art circuits now contain several billion transistors. However, designing and verifying that these circuits function correctly under all expected (and unexpected) operation conditions is extremely challenging, with many studies finding that verification can consume over half of the total design effort. Due to the slow speed of logic simulation software, designers increasingly turn to circuit prototypes implemented using field-programmable gate array (FPGA) technology. Whilst these prototypes can be operated many orders of magnitude faster than simulation, on-chip instruments are required to expose internal signal data so that designers can root-cause any erroneous behaviour. This thesis presents four contributions to enable rapid and effective circuit debug when using FPGAs, in particular, by harnessing the reconfigurable and prefabricated nature of this technology. The first contribution presents a post-silicon debug metric to quantify the effectiveness of trace-buffer based debugging instruments, and three algorithms to determine new signal selections for these instruments. Our most scalable algorithm can determine the most influential signals in a large 50,000 flip-flop circuit in less than 90 seconds. The second contribution of this thesis proposes that debug instruments be speculatively inserted into the spare capacity of FPGAs, without any user intervention, and shows this to be feasible. This proposal allows designers to extract more trace data from their circuit on every debug turn, ultimately leading to fewer debug iterations. The third contribution presents techniques to enable faster debug turnaround, by using incremental-compilation methods to accelerate the process of inserting debug instruments. Specifically, our incremental optimizations can speed up this procedure by almost 100X over recompiling the FPGA from scratch. Finally, the fourth contribution describes how a virtual overlay network can be embedded into the unused resources of the FPGA device, allowing debug instruments to be modified without any form of recompilation. Experimental results show that a new configuration for a debug instrument with 17,000 trace connections can be made in 50 seconds, thus enabling rapid circuit debug.

View record

Field-Programmable Gate Arrays (FPGAs) are widely used to implement logic without going through an expensive fabrication process. Current-generation FPGAs still suffer from area and power overheads, making them unsuitable for mainstream adoption for large volume systems. FPGA companies constantly design new architectures to provide higher density, lower power consumption, and faster implementation. An experimental approach is typically followed for new architecture design, which is a very slow and computationally expensive process. This dissertation presents an alternate faster way for FPGA architecture design. We use analytical model based design techniques, where the models consist of a set of equations that relate the effectiveness of FPGA architectures to the parameters describing these architectures. During early stage architecture investigation, FPGA architects and vendors can use our equations to quickly short-list a limited number of architectures from a range of architectures under investigation. Only the short-listed architectures need then be investigated using an expensive experimental approach. This dissertation presents three contributions towards the formulation of analytical models and the investigation of capabilities and limitations of these models.First, we develop models that relate key FPGA architectural parameters to the depth along the critical path and the post-placement wirelength. We detail how these models can be used to estimate the expected area of implementation and critical path delay for user-circuits mapped on FPGAs.Secondly, we develop a model that relates key parameters of the FPGA routing fabric to the fabric's routability, assuming that a modern one-step global/detailed router is used. We show that our model can capture the effects of the architectural parameters on routability. Thirdly, we investigate capabilities and limitations of analytical models in answering design questions that are posed by the FPGA architects. Comparing with two experimental approaches, we demonstrate that analytical models can better optimize FPGA architectures while requiring significantly less design effort. However, we also demonstrate that the analytical models, due to their continuous nature, should not be used to answer the architecture design questions related to applications having `discrete effects'.

View record

As process technology scales, the design effort and Non-Recurring Engineering(NRE) costs associated with the development of Integrated Circuits (ICs) is becoming extremely high. One of the main reasons is the high cost of preparing and processing IC fabrication masks. The design effort and cost can be reduced by employing Structured Application Specific ICs (Structured ASICs). Structured ASICs are partially fabricated ICs that require only a subset of design-specific custom masks for their completion.In this dissertation, we investigate the impact of design-specific masks on the area, delay, power, and die-cost of Structured ASICs. We divide Structured ASICs into two categories depending on the types of masks (metal and/or via masks) needed for customization: Metal-Programmable Structured ASICs (MPSAs) that require custom metal and via masks; and Via-Programmable Structured ASICs (VPSAs) that only require via masks for customization. We define the metal layers used for routing that can be configured by one or more via, or metal-and-via masks as configurable layers. We then investigate the area, delay, power, and cost trends for MPSAs and VPSAs as a function of configurable layers.The results show that the number of custom masks has a significant impact ondie-cost. In small MPSAs (area 100 sq.mm) is achieved with three or four configurable layers. The lowest cost in VPSAs is also obtained with four configurable layers. The best delay and power in MPSAs is achieved with three or four configurable layers. In VPSAs, four configurable layers lead to lowest power and delay, except when logic blocks have a large layout area. MPSAs have up to 5x, 10x, and 3.5x better area, delay, and power than VPSAs respectively. However, VPSAs can be up to 50% less expensive than MPSAs. The results also demonstrate that VPSAs are very sensitive to the architecture of fixed-metal segments; VPSAs with different fixed-metal architectures can have a gap of up to 60% in area, 89% in delay, 85% in power, and 36% in die-cost.

View record

Field-Programmable Gate Arrays (FPGAs) are pre-fabricated integrated circuits that can be configured as any digital system. Configuration is done by Computer-Aided Design (CAD) tools. The demand placed on these tools continues to grow as advances in process technology continue to allow for more complex FPGAs. Already, for large designs, compile-times of an entire work day are common and memory requirements that exceed what would be found in a typical workstation are the norm. This thesis presents three contributions toward improving FPGA CAD tool scalability.First we derive an analytical model that relates key FPGA architectural parameters to the CAD place-and-route (P&R) run-times. Validation shows that the model can accurately capture the trends in run-time when architecture parameters are changed.Next we focus on the CAD tool’s storage requirements. A significant portion of memory usage is in representing the FPGA. We propose a novel scheme for this representation that reduces memory usage by 5x-13x at the expense of a 2.26x increase in routing run-time. Storage is also required to track metrics used during routing. We propose three simple memory management schemes for this component that further reduces memory usage by 24%, 34%, and 43% while incurring a routing run-time increase of 4.5%, 6.5%, and 144% respectively. We also propose a design-adaptive scheme that reduces memory usage by 41% while increasing routing run-time by only 10.4%. Finally, we focus on the issue of long CAD run-times by investigating the design of FPGA architectures amenable to fast CAD. Specifically, we investigate the CAD run-time and area/delay trade-offs when using high-capacity logic blocks (LBs). Two LB architectures are studied: traditional and multi-level. Results show that for the considered architectures, CAD run-time can be reduced at the expense of area; speed improved. For example, CAD run-time could be reduced by 25% with an area increase of 5%. We also show that the run-time trade-offs through these architectural changes can be complementary with many previously published algorithmic speed-ups.

View record

Many-core architectures are the most recent shift in multi-processor design. This processor design paradigm replaces large monolithic processing units by thousands of simple processing elements on a single chip. With such a large number of processing units, it promises significant throughput advantage over traditional multi-core platforms. Furthermore, it enables better localized control of power consumption and thermal gradients. This is achieved by selective reduction of the core’s supply voltage, or by switching some of the cores off to reduce power consumption and heat dissipation. This dissertation proposes an energy optimization flow to implement applications on many-core architectures taking into account the impact of Process Voltage and Temperature (PVT) variations. The flow utilizes multi-supply voltage techniques, namely voltage island design, to reduce power consumption in the implementation. We propose a novel approach to voltage island formation, called Voltage Island Clouds, that reduces the impact of on-chip or intra-die PVT variations. The islands are created by balancing their shape constraints imposed by intra- and inter-island communication with the desire to limit the spatial extent of each island to minimize PVT impact. We propose an algorithm to build islands for Static Voltage Scaling (SVS) and Multiple Voltage Scaling (MVS) design approaches.The optimization initially allows for a large number of islands, each with its unique voltage level. Next, the number of the islands is reduced to a small practical number, e.g., four voltages. We then propose an efficient voltage selection approach, called the Removal Cost Method (RCM), that provides near optimal results with more than a 10X speedup compared to the best-known previous methods. Finally, we present an evaluation platform considering pre- and post-fabrication PVT scenarios where multiple applications with hundreds to thousands of tasks are mapped onto many-core platforms with hundreds to thousands of cores to evaluate the proposed techniques. Results show that the geometric average energy savings for 33 test cases using the proposed methods is 25% better than previous methods.

View record

With the continued trend in device scaling and the ever increasing popularity of hand heldmobile devices, power has become a major bottleneck for the development of futuregeneration System-on-Chip devices. As the number of transistors on the SoC and theassociated leakage current increases with every technology generation, methods for reducingboth active and static power have been aggressively pursued.Starting with the application for which the SoC is to be designed, the proposed design flowconsiders numerous design constraints at different steps of design process and produces a finalfloorplanned solution of the cores. Voltage Island Design is a popular method forimplementing multiple supply voltages in a SoC. Use of multiple threshold voltages withpower gating of cores is an attractive method for leakage power reduction. This thesisaddresses the design challenges of implementing multiple supply and threshold voltage on thesame chip holistically with the ultimate goal for maximum power reduction.Specifically, given the power-state machine (PSM) of an application, the high power and lowpower cores are identified first. Based on the activity of the cores, threshold voltage isassigned to each core. The next step is to identify the suitable range of supply voltage for eachcore followed by voltage island generation. A methodology of reducing the large number ofavailable choices to a useful set using the application PSM is developed. The cores arepartitioned into islands using a cost function that gradually shifts from a power-basedassignment to a connectivity-based one.Additional design constraints such as power supply noise and floorplan constraints can offsetthe possible power savings and thus are considered early in the design phase. Experimentalresults on benchmark circuits prove the effectiveness of the proposed methodology. Onaverage, the use of multiple VT and power gating can reduce almost 20% of power comparedto single VT. A proper choice of supply voltages leads to another 4% reduction in power.Compared to previous methods, the proposed floorplanning technique on average offers anadditional 10% power savings, 9% area improvement and 2.4X reduction in runtime.

View record

As the level of integrated circuit (IC) complexity continues to increase, the post-silicon validation stage is becoming a large component of the overall development cost. To address this, we propose a reconfigurable post-silicon debug infrastructure that enhances the post-silicon validation process by enabling the observation and control of signals that are internal to the manufactured device. The infrastructure is composed of dedicated programmable logic and programmable access networks. Our reconfigurable infrastructure enables not only the diagnoses of bugs; it also allows the detection and potential correction of errors in normal operation. In this thesis we describe the architecture, implementation and operation of our new infrastructure. Furthermore, we identify and address three key challenges arising from the implementation of this infrastructure. Our results demonstrate that it is possible to implement an effective reconfigurable post-silicon infrastructure that is able to observe and control circuits operating at full speed, with an area overhead of between 5% and 10% for many of our target ICs.

View record