Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/18638
Title: HARDWARE-SOFTWARE CODESIGN FOR RUN-TIME RECONFIGURABLE FPGA-BASED SYSTEMS
Authors: SIM JOON, EDWARD
Keywords: FPGA, Hardware-Software Codesign, Run-time Reconfiguration, Compiler, Control Flow Graph, Partial Reconfiguration
Issue Date: 8-Jan-2010
Source: SIM JOON, EDWARD (2010-01-08). HARDWARE-SOFTWARE CODESIGN FOR RUN-TIME RECONFIGURABLE FPGA-BASED SYSTEMS. ScholarBank@NUS Repository.
Abstract: Run-time reconfigurable FPGA-based systems create both opportunities and challenges for hardware-software codesign. On the one hand, it has been shown that significant speedups could be obtained for computations when performed on the reconfigurable hardware fabric and this potential speedup can be achieved without re-fabrication costs. On the other hand, the virtualization of the hardware resources comes at a price. Hardware computation modules have to be pre-loaded onto the FPGA prior to execution and the time taken to preload these modules can be significant. In order to obtain quality solutions for implementing applications on these platforms, we need to navigate the trade-off between the speedup achievable for individual components and the reconfiguration costs required to load them. Envisioning that run-time reconfigurable computing will be a major part of mainstream computing, this thesis studies and proposes methodologies that can be incorporated into the design process of single, sequential programs written in high-level programming language (e.g. Java, C etc) for reconfigurable computing platforms. This thesis makes the following contributions. First, we propose a novel design-space search framework for hardware-software partitioning of a single, sequential program. A key feature of this framework is that it facilitates the efficient computation of reconfiguration costs. Our definition of neighboring relationships between design points, when coupled with execution traces encoded in SEQUITUR grammar, speeds up the process of reconfiguration cost estimation when the search moves between neighboring design points. To our knowledge, this is the first work that examined the problem of implementing neighborhood searches of both the temporal and spatial partitioning space. Our experiments show that searches can be speeded up by up to 2 orders of magnitude when all the key features of our framework are employed. xv Second, although the design-space search framework allows efficient computation of reconfiguration costs, it has been assumed that the reconfiguration costs cannot be hidden through techniques such as configuration prefetching that can occur in parallel with computation. In the second part of the thesis, we propose a novel, polynomial time algorithm that examines an execution trace and schedules placement-aware configurations to minimize overall execution time. This algorithm is provably optimal and our experiments show a speedup of up to 40% when compared with schedules done by online scheduling algorithms that relies on hardware predictors. Finally, we visit the problem of inserting configuration prefetching calls into an Interprocedural Control-Flow Graph statically. While the algorithm described above yields optimal schedules, the schedules that it produces are very specific for particular input execution traces. Through the usage of profiled execution frequencies of control-flow edges, our proposed algorithm estimates placement-aware probabilities of reaching hardware execution for each basic block. The prefetches are then generated based on these probabilities. Experiments show that our proposed algorithm makes significant improvements over the state-of-the-art prefetching strategies that do not consider placement conflicts.
URI: http://scholarbank.nus.edu.sg/handle/10635/18638
Appears in Collections:Ph.D Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
thesis.pdf2.33 MBAdobe PDF

OPEN

NoneView/Download

Page view(s)

460
checked on Dec 11, 2017

Download(s)

550
checked on Dec 11, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.