Guido Meardi([email protected], until May 98)FPGA-coupled Microprocessors:the challenge of DynamicReconfiguration2AbstractMicroprocessors have been the dominant devices in general-purpose computing for the last decade,but there remains a large gap between the computational efficiency of microprocessors and that ofspecialized computing resources, such as Digital Signal Processors and application-specificprocessors (ASICs). Reconfigurable devices, such as Field Programmable Gate Arrays (basically,reconfigurable ASICs), have come closer to closing that gap, offering very nearly the performanceof ASICs (typically 10x to 100x performance boost), but with more than one application. On highlyregular, high throughput computations, reconfigurable architectures are clearly superior totraditional processor architectures. However, in irregular tasks and in those with low throughputrequirements, the traditional microprocessor organization is still more efficient than thesereconfigurable devices.The best solution, then, could come from combining the two opposite poles: by coupling a generalpurpose microprocessor with a reconfigurable logic array, we could clearly exploit the best of eachsolution. FPGA-coupled processors could swiftly execute computationally-intensive tasks whilemaintaining the flexibility of a programmable architecture.The very low reconfiguration times that modern FPGAs feature, in particular, are now markedlyopening the possibility of dynamic HW reconfiguration during the execution, adapting the system tothe actual flow of computation.This project focused on the dynamic reconfiguration problem. Using Acyclic SDF graphs and aparticular FPGA-coupled processor chip model, I developed reasonable heuristics to solve thescheduling and reconfiguration problems, considering the FPGA dimension, the instructions thatcan fit in the FPGA (with relative performances) and the relative reconfiguration times.31. The Big Picture1.1 What can we do with all those gates?Everybody knows that effective device densities and IC capacity grow at an exponential rate. Weare quite familiar with the progress of microprocessors, where performance increases roughly by60% per year and the number of gates increases by 25% per year. At the current rate, we can expectto have over 12 million gates available by the end of the century, and possibly an astounding 1billion gates in just 10 years. The current trend is in enhancing performance with additional, fixedfunctional units and reducing costs by integrating more of the system on a single chip (system-on-a-chip). It appears doubtful, though, that this is the most interesting use of the silicon real-estatebecoming available. Microprocessors may continue including more memory, more FPUs, moreALUs and more system functionalities, but the fixed functional units simply won’t provide a broad-based acceleration of applications in proportion to the area these fixed units consume [4]. Foralmost any application we can figure out solutions or modifications to the architecture that wouldsignificantly improve the application’s performance, but these modifications would obviously differfrom application to application. It’s unlikely, then, that including these additions in amicroprocessor with a broad application base would be the optimal choice.Incorporating reconfigurable logic into a general-purpose processor appears to be the right choice:every application would be allowed to tailor the hardware to its particular requirements, with hugepossible advantages in terms of performance. At the same time, this would allow themicroprocessor to maintain its appeal across a broad range of applications, and that would clearlymean commodity economics, high volumes and low prices.1.2 Configurable computingWhat made the notion of configurable computing possible was the design of new FPGAs (Field4Programmable Gate Arrays) that can be configured extremely quickly. The earliest FPGAsrequired several seconds or more to change their configuration, while newer FPGA can beconfigured in less than one millisecond, and in a couple of years configuration times could becomeas low as 100 microseconds [7]. With this kind of performance it becomes possible to conceiveprocessors that configure themselves on the fly, adapting to the software that is actually running andto the resources that it needs. Most of the processing time for computationally-intensive tasks isspent in relatively small and highly regular kernels, well suitable for HW (or, better, Morphware)implementation. Coupling a general purpose HW with Morphware may then considerably improveoverall performance, with boosts ranging from one to two orders of magnitude.1.3 Problems to addressOne of the tricky issues associated with FPGA-coupled processors is that the process of mappingalgorithms into FPGAs is not automated. Typically, programmers take care of identifying thealgorithm (or a portion thereof) to be implemented in hardware, and then specialized tools convertthe algorithm into a hardware description. The search for automated ways to solve the HW/SWPartitioning Problem is actually a hot issue of HW/SW Codesign, a field of research that lately hasbeen gaining more and more attention.Another interesting challenge associated with configurable computing is dynamic reconfigurationitself (and, overall, how to manage it): this is actually the primary focus of this project.Other challenges include the interfacing between the processor and the configurable logic, thegrain-size of the FPGA, the area and pin allocation and the problem of multitasking and stateinteraction. This last hurdle, in particular, appears quite daunting: the FPGA introduces a largeamount of state associated with each computation in progress, and the overhead necessary toreconfigure contemporary reconfigurable architectures is such that it makes time-sharing systemsquite simply impractical.52. This Project2.1 Reference ModelAs already stated, this project focuses on the problem of how to manage appropriately the dynamicrun-time reconfiguration of an FPGA-coupled DSP processor aimed at embedded applications. Iworked under the following assumptions:• The processor disposes of n traditional pipelines and a reconfigurable pipeline, in which one ormore Additional Instructions (from now on referred to as AIs) can be mapped at a time.• A certain number of AIs have formerly been identified. The AIs are subdivided in i groups: AIsof a same group share