Computing systems designed using reconfigurable hardware are increasingly composed using a number of different Intellectual Property (IP) cores, which are often provided by third-party vendors that may have different levels of trust. Unlike traditional software where hardware resources are mediated using an operating system, IP cores have fine-grain control over the underlying reconfigurable hardware. To address this problem, the embedded systems community requires novel security primitives that address the realities of modern reconfigurable hardware. In this work, we propose security primitives using ideas centered around the notion of “moats and drawbridges.” The primitives encompass four design properties: logical isolation, interconnect traceability, secure reconfigurable broadcast, and configuration scrubbing. Each of these is a fundamental operation with easily understood formal properties, yet they map cleanly and efficiently to a wide variety of reconfigurable devices. We carefully quantify the required overheads of the security techniques on modern FPGA architectures across a number of different applications.

Nanoscale technology promises dramatically increased device density, but also decreased reliability. With bit error rates projected to be as high as 10%, designing a usable nanoscale memory system poses a significant challenge. In particular, we need to bootstrap a sea of unreliable bits into contiguous address ranges which are preferably as large as 4K-byte virtual memory pages. We accomplish this bootstrapping through a combination of dynamic error correction codes within 32-bit blocks and a static defect map which tracks usability of these blocks. The key insight is that statically-determined defect locations can be much more powerful than dynamically correcting for unknown locations, but that defect maps are only practical at a coarse granularity. Using a combination of BCH error correction codes and a Bloom-Filter-based defect map, we achieve a memory efficiency of 60% and 13% for 4K-byte pages at 1% and 10% bit-error rates, respectively.

Blurring the line between software and hardware, reconfigurable devices strike a balance between the raw high speed of custom silicon and the post-fabrication flexibility of general-purpose processors. While this flexibility is a boon for embedded system developers, who can now rapidly prototype and deploy solutions with performance approaching custom designs, this results in a system development methodology where functionality is stitched together from a variety of "soft IP cores," often provided by multiple vendors with different levels of trust. Unlike traditional software where resources are managed by an operating system, soft IP cores necessarily have very fine grain control over the underlying hardware. To address this problem, the embedded systems community requires novel security primitives which address the realities of modern reconfigurable hardware. We propose an isolation primitive, moats and drawbridges, that are built around four design properties: logical isolation, interconnect traceability, secure reconfigurable broadcast, and configuration scrubbing. Each of these is a fundamental operation with easily understood formal properties, yet maps cleanly and efficiently to a wide variety of reconfigurable devices. We carefully quantify the required overheads on real FPGAs and demonstrate the utility of our methods by applying them to the practical problem of memory protection.

Operation scheduling (OS) is a fundamental problem in mapping an application to a computational device. It takes a behavioral application specification and produces a schedule to minimize either the completion time or the computing resources required to meet a given deadline. The OS problem is NP-hard; thus, effective heuristic methods are necessary to provide qualitative solutions. We present novel OS algorithms using the ant colony optimization approach for both timing-constrained scheduling (TCS) and resource-constrained scheduling (RCS) problems. The algorithms use a unique hybrid approach by combining the MAX-MIN ant system metaheuristic with traditional scheduling heuristics. We compiled a comprehensive testing benchmark set from real-world applications in order to verify the effectiveness and efficiency of our proposed algorithms. For TCS, our algorithm achieves better results compared with force-directed scheduling on almost all the testing cases with a maximum 19.5% reduction of the number of resources. For RCS, our algorithm outperforms a number of different list-scheduling heuristics with better stability and generates better results with up to 14.7% improvement. Our algorithms outperform the simulated annealing method for both scheduling problems in terms of quality, computing time, and stability

Design space exploration during high-level synthesis is often conducted through ad hoc probing of the solution space using some scheduling algorithm. This is not only time consuming but also very dependent on designer's experience. We propose a novel design exploration method that exploits the duality of time- and resource-constrained scheduling problems. Our exploration automatically constructs a time/area tradeoff curve in a fast, effective manner. It is a general approach and can be combined with any high-quality scheduling algorithm. In our work, we use the max-min ant colony optimization technique to solve both time- and resource-constrained scheduling problems. Our algorithm provides significant solution-quality savings (average 17.3% reduction of resource counts) with similar runtime compared to using force-directed scheduling exhaustively at every time step. It also scales well across a comprehensive benchmark suite constructed with classic and real-life samples.

Design space exploration during high level synthesis is often conducted through ad-hoc probing of the solution space using some scheduling algorithm. This is not only time consuming but also very dependent on designer's experience. We propose a novel design exploration method that exploits the duality between the time and resource constrained scheduling problems. Our exploration automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. It uses the MAX-MIN ant colony optimization to solve both the time and resource constrained scheduling problems. We switch between the time and resource constrained algorithms to quickly traverse the design space. Compared to using force directed scheduling exhaustively at every time step, our algorithm provides a significant solution quality savings (average 17.3% reduction of resource counts) with similar run time on a comprehensive benchmark suite constructed with classic and real-life samples. Our algorithms scale well over different applications and problem sizes.

The authors propose a novel defect-tolerant design methodology using Bloom filters for defect mapping for nanoscale computing devices. It is a general approach that can be used for any permanent defects incurred during the manufacturing process. The redundant design methodology does not rely on a voting strategy, thus it utilizes the device redundancy more effectively than existing approaches. Additionally, our method does not have false-positive in defect identification, i.e. it will not report a defective device as functional. Moreover, it is very space economic and can be programmed to fit different scales and characteristics of the underlying specific nanoscale devices used in the system

While the exact manufacturing process for nanoscale computing devices is uncertain, it is abundantly clear that future technology nodes will see an increase in defect rates. Therefore, it is of paramount importance to construct new architectures and design methodologies that can tolerate large numbers of defects. Defect maps are a necessity in the future design flows, and research on their practical construction is essential. In this work, we study the use of Bloom filters as a data structure for defect maps. We show that Bloom filters provide the right tradeoff between accuracy and space-efficiency. In particular, they can help simplify the nanosystem design flow by embedding defect information within the nanosystem delivered by the manufacturers. We develop a novel nanoscale memory design that uses this concept. It does not rely on a voting strategy, and utilizes the device redundancy more effectively than existing approaches.

Modern field programmable gate array (FPGA) architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such a great flexibility comes at a high cost in terms of area, delay, and power. The authors propose a new FPGA routing architecture that utilizes a mixture of hardwired and traditional flexible switches. The result is an about a 30% reduction in leakage power consumption, a 5% smaller area, and 20% shorter delays, which translates to a 25% increase in the clock frequency. Despite the increase in clock speeds, the overall power consumption is reduced.

Modern FPGA architectures provide ample routing resources so that designs can be routed successfully. The routing architecture is designed to handle versatile connection configurations. However, providing such great flexibility comes at a high cost in terms of area, delay and power. We propose a new FPGA routing architecture\footnoteThis work was supported in part by a grant from NSF under contract CAREER CCF-0347891 that utilizes a mixture of hardwired and traditional flexible switches. The result is 24% reduction in leakage power consumption, 7% smaller area and 24% shorter delays, which translates to 30% increase in clock frequency. Despite the increase in clock speeds, the overall power consumption is %, including dynamic power, reduced by 8%.

Instruction scheduling is a fundamental step for mapping an application to a computational device. It takes a behavioral application specification and produces a schedule for the instructions onto a collection of processing units. The objective is to minimize the completion time of the given application while effectively utilizing the computational resources. The instruction scheduling problem is NP-hard, thus effective heuristic methods are necessary to provide a qualitative scheduling solution. In this paper, we present a novel instruction scheduling algorithm using MAX-MIN Ant System Optimization approach. The algorithm utilizes a unique hybrid approach by combining the ant system meta-heuristic with list scheduling, where the local and global heuristics are dynamically adjusted to the input application in an iterative manner. Compared with force-directed scheduling and a number of different list scheduling heuristics, our algorithm generates better results over all the tested benchmarks with better stability. Furthermore, by solving the test samples optimally using ILP formulation, we show that our algorithm consistently achieves a near optimal solution.

Modern, high performance configurable architectures integrate on-chip, distributed block RAM modules to provide ample data storage. Synthesizing applications to these complex systems requires an effective and efficient approach to conduct data partitioning and storage assignment. In this paper, we present a data and iteration space partitioning solution that focuses on minimizing remote memory accesses or, equivalently, maximizing the local computation. Using the same code but different data partitionings, we can achieve faster clock frequencies, without increasing the number of cycles, by simply minimizing global memory accesses. Other optimization techniques like scalar replacement, prefetching and buffer insertion can further minimize remote accesses and lead to average 4.8/spl times/ speedup in overall runtime.