The emerging FPGA-based edge computing systems enable IoT devices to offload compute-intensive tasks to the edge for custom hardware acceleration. The FPGA edge provides a shared multi-accelerator platform where various hardware accelerators are dynamically allocated and accessed by multiple applications. We propose ReinConfig, a deep-reinforcement-learning-based runtime system software for an FPGA-based multi-accelerator edge platform. ReinConfig supports concurrent scheduling and asynchronous learning, capturing the characteristics of incoming task loads and adaptively learning through interactions with the system to dynamically provide efficient task scheduling and accelerator allocation. We deployed ReinConfig for deep-learning-based vision applications such as object detection and classification. Experimental results show that ReinConfig outperforms the first-come, first-served approach with $1.4 \times$ higher throughput and $20.1 \%$ lower task drop rate. It also surpasses related learning-based approaches with $1.3 \times$ higher throughput, $16.3 \%$ lower task drop rate, and $2 \times$ shorter response time on average.

Edge computing plays a key role in providing ser-vices for emerging compute-intensive applications while bringing computation close to end devices. FPGAs have been deployed to provide custom acceleration services due to their reconfigurability and support for multi-tenancy in sharing the computing resource. This paper explores an FPGA-based Multi-Accelerator Edge Computing System, that serves various DNN applications from multiple end devices simultaneously. To dynamically maximize the responsiveness to end devices, we propose a system framework that exploits the characteristic of applications in patterns and employs a staggering module coupled with a mixed offline/online multi-queue scheduling method to alleviate resource contention, and uncertain delay caused by network delay variation. Our evaluation shows the framework can significantly improve responsiveness and robustness in serving multiple end devices.

Edge computing can potentially provide abundant processing resources for compute-intensive applications while bringing services close to end devices. With the increasing demands for computing acceleration at the edge, FPGAs have been deployed to provide custom deep neural network accelerators. This paper explores a DNN accelerator sharing system at the edge FPGA device, that serves various DNN applications from multiple end devices simultaneously. The proposed SharedDNN/PlanAhead policy exploits the regularity among requests for various DNN accelerators and determines which accelerator to allocate for each request and in what order to respond to the requests that achieve maximum responsiveness for a queue of acceleration requests. Our results show overall 2. 20x performance gain at best and utilization improvement by reducing up to 27% of DNN library usage while staying within the requests’ requirements and resource constraints.

In this paper, we present a method to find an optimal trade-off between computation and communication of decentralized linear task chain running on a network of mobile agents. Task replication has been deployed to reduce the data links among highly correlated nodes in communication networks. The primary goal is to reduce or remove the data links at the cost of increase in computational load at each node. However, with increase in complexity of applications and computation load on end devices with limited resources, the computational load is not negligible. Our proposed selective task replication enables communication-computation trade-off in decentralized task chains and minimizes the overall local computation overhead while keeping the critical path delay under a threshold delay. We applied our approach to decentralized Unscented Kalman Filter (UKF) for state estimation in cooperative localization of mobile multi-robot systems. We demonstrate and evaluate our proposed method on a network of 15 Raspberry Pi3B connected via WiFi. Our experimental results show that, using the proposed method, the prediction step of decentralized UKF is faster by 15%, and for the same threshold delay, the overall computation overhead is reduced by 2.41 times, compared to task replication without resource constraint.

Computer vision algorithms are computationally expensive and difficult to implement efficiently. Field Programmable Gate Arrays (FPGA)s offer a promising direction to reduce the computation cost by exploiting hardware parallelism. However, it is difficult to translate vision algorithms to FPGA bitstream efficiently. OpenVX is an industry standard for graph-based representation of vision algorithms. It defines a set of widely used vision kernels and data structures that can be used to form a Directed Acyclic Graph (DAG) to represent a vision algorithm. This paper proposes a framework for automatic FPGA acceleration of computer vision algorithms based on OpenVX specification, called AFFIX. AFFIX receives a vision algorithm formed using the OpenVX and generates a heterogeneous CPU-FPGA implementation. AFFIX incorporates several high level and low-level optimization methods to improve the efficiency of the FPGA implementation. It provides a configurable and extensible framework that enables vision algorithm developers to quickly develop, verify and test FPGA implementations of vision algorithms. We demonstrate the effectiveness of the proposed framework via development and evaluations of multiple vision algorithms.

Estimation techniques such as Unscented Kalman filter (UKF) are deployed for accurate joint location estimation in cooperative localization of cyber physical systems (CPS), e.g., to locate each robot in a cooperative mobile robotic network in GPS-denied environments. In order to avoid single point of failure in the centralized implementation of such estimation techniques, the decentralization of estimation algorithms has attracted considerable attention in the past two decades. However, the design of decentralized algorithms with reduced communication cost without loss in accuracy for compute-intensive estimation techniques such as UKF has been challenging. In the decentralized UKF, the tasks are partitioned and computed locally at robot nodes. Data communication overhead is overwhelming due to tight data dependency between the robots' computations. In this paper, we present a CPS framework for UKF decentralization in which computation and communication are tightly intertwined and computation replication is deployed in order to reduce the communication overhead among cooperative mobile robots. We demonstrate and evaluate the performance of our proposed work in a wireless network of 15 Raspberry Pi 3 B, with quad-core 1.2GHz 64bit CPU, emulating a network of mobile robots with onboard computation and communication capabilities. Our experimental results show that the End-to-End execution time of decentralized UKF prediction and update steps with replication are faster by up to 12.29 and 3.57 times, respectively, compared to the partially decentralized UKF algorithm of [1].

In this paper, we present MQMAI, multi-queue command-based data transfer mechanism that enables efficient and scalable access to multiple accelerators on FPGA via PCIe. The proposed framework provides a user-friendly non-blocking API with enhanced I/O parallelism to access FPGA-based accelerators. MQMAI is composed of I/O software stack in host CPU and accelerator controller in FPGA. A round-robin policy is developed to allow efficient run-time access to shared accelerators requested through multiple threads/applications. Our experimental results show that our proposed framework reduces the total latency of multi accelerators access significantly compared to the current state-of-the-art framework, RIFFA, by 18x for 4 threads per accelerator access.

This paper proposes a highly scalable sensor design for late transition detection in FPGA based platforms. Transition delays occur because of aging mechanisms such as Biased Temperature Instability(BTI) and Hot Carrier Injection (HCI). We propose a sensor clock (SCLK) that is a function of minimum slack time of a set of paths selected for age monitoring. There will be one such clock for many sensors as are needed in an entire FPGA. Our proposed sensor architecture makes it possible for a single SCLK to be shared by all sensors. Additionally, the proposed sensor occupies one slice (basic FPGA logic block), which leads to low area, power, and performance overhead. Using Artix-7-based board, experimental results demonstrate that the proposed aging sensor detects aging earlier than existing sensors and provides less power and performance overheads.

Due to advanced silicon technology, reconfigurable system-on-chip devices such as FPGAs are increasingly becoming sensitive to aging effects. This paper presents a high-level physical planning with reconfiguration strategy in order to mitigate the aging-induced delay degradation in FPGA resources. The proposed solution is an offline framework composed of an aging-aware floorplanner coupled with a proactive aging-aware reconfiguration policy which generates checkpoints aperiodically for runtime reconfiguration. We consider BTI and HCI aging mechanisms and consider the BTI-based aging recovery during idle periods using aging history map. The experiments demonstrate that sequence of configurations generated by this scheme provides average aging-rate reduction on FPGA resources and application performance by 53.2% and 17.5%, respectively.

Due to increasing demand for reconfigurability in embedded systems, real-time task scheduling is challenged by non-negligible reconfiguration overheads. We introduce the problem of real-time task scheduling under reconfiguration overhead on heterogeneous reconfigurable systems while considering the data dependencies and data communication overhead. We introduce a novel graph representation which captures the delay overhead due to data dependencies and reconfiguration. We formulate the problem as a network flow problem and provide a mixed integer linear programming solution to minimize the completion time so called makespan. Results show that our proposed scheduling improves the makespan by 24.20% (on average) in comparison with maximum-transition-overhead scheduling.

Energy harvesting from environments such as solar energy are promising solutions to tackle energy sustainability in embedded systems. However, uncertainties in energy availability, non-ideal characteristics of harvesting circuits, energy storage (battery or supercapacitor), and application demand dynamics add more complexity in the system. We present a unified model based on discrete-time Finite State Markov Chain to capture the dynamicity and variations in both the energy supply from solar irradiance and the energy demand from the application. In this paper, we exploit the temporal and spatial characteristics of solar energy and propose a deterministic profile with stochastic process to reflect the fluctuation due to unexpected weather condition. Optimal policy to maximize expected total QoS is derived from the presented model using a probabilistic dynamic programming approach. Compared to a state-of-the-art deterministic energy management framework, our proposed approach outperforms in term of QoS and energy sustainability (with less shutdown time) of the system.

This paper proposes a distributed flow-based routing technique in energy-harvesting wireless sensor networks (EHWSNs) in order to balance the energy consumptions by sending packets assigned to routers that are sent from sensors to base stations. The objective of the flow optimization problem is to minimize the total load factors of all the nodes and wireless links, which leads to sustainable management of the sensor networks that exploit renewable power from energy harvesting systems. We propose a novel algorithm based on tie-set graph theory where the underlying graph of an EHWSN is divided into a set of independent loops to significantly reduce the topological complexity, which simplifies the flow optimization problem to be solved in a distributed manner. Simulation experiments against the shortest-path and multi-path algorithms demonstrate that optimized packet flows by the proposed method realize the sustainable EHWSNs and maintain the useful life of storage devices with modest increase in total energy consumption by routings.

Intrusion detection approaches have been presented which detect anomalous malware behavior at runtime. Most techniques involve software-based analysis which is too slow to support the tight timing constraints often imposed on embedded systems. We propose a hardware-based intrusion detection approach which does not alter the functional performance of the system. When using a real-time operating system, the executing process changes several times each second, requiring fast adaptation on the part of the intrusion detection mechanism. We present a technique to exploit the partial runtime reconfiguration feature present on many modern field programmable gate arrays (FPGAs) to adapt intrusion detection to a new process at each context switch. The use of runtime reconfiguration enables the flexibility of software-based approaches with the performance benefits of hardware-based approaches.

In battery-powered embedded systems, the limit of battery charge creates a challenge in scheduling tasks to meet both their deadlines and Quality of Service (QoS) requirements. Harvesting energy from the surrounding environment continuously eliminates the concern of limited battery charge. However, the uncertainty in availability of energy brings challenges in embedded systems. In this paper, we propose an energy management technique to maximize QoS of the system. Our technique is composed of two steps: an offline step and an online step. In the offline step we use frame-based energy harvesting prediction in one harvesting period, in order to find the best QoS level for the tasks and maximize the energy utilization. The information provided from the offline step guides the online scheduler to decide about job scheduling at run-time to minimize the QoS violation. We compared our scheduler with other approaches and on average we reduce the violation count by 22%.

Due to the increase in demand for reconfigurability in embedded systems, schedulability in real-time task scheduling is challenged by non-negligible reconfiguration overheads. Reconfiguration of the system during task execution affects both deadline miss rate and deadline miss distribution. On the other hand, Quality of Service (QoS) in several embedded applications is not only determined by deadline miss rate but also the distribution of the tasks missing their deadlines (known as weakly-hard real-time systems). As a result, we propose to model QoS constraints as a set of constraints on dropout patterns (due to reconfiguration overhead) and present a novel online solution for the problem of reconfiguration-aware real-time scheduling. According to QoS constraints, we divide the ready instances of the tasks into two groups: critical and non-critical, then model each group as a network flow problem and provide an online scheduler for each group. We deployed our method on synthetic benchmarks as well as software defined radio implementation of VoIP on reconfigurable systems. Results show that our solution reduces the number of QoS violations by 19.01 times and 2.33 times (57.02%) in comparison with Bi-Modal Scheduler (BMS) for synthetic benchmarks with low and high QoS constraint, respectively.

Although triple modular redundancy (TMR) has been widely used to mitigate single event upsets (SEUs) in static random access memory-based field-programmable gate arrays (FPGAs), SEU-caused bridging faults between the triplicated modules do not guarantee the correctness of TMR designs under all SEUs. In this paper, we present a novel computer-aided design flow for redundancy-based applications on FPGAs in order to mitigate the impact of SEUs in the configuration bitstreams. We introduce the notions of modular redundancy conflicts and vulnerability-gap conflicts which maintain the fundamental assumption underlying the integrity of redundancy-based designs (i.e., self-containment of SEU-induced faults within a single replica of redundant resources). When the impact of SEU-induced bridging faults is considered in high-level synthesis as well as physical synthesis, on average more than 30% improvement in the number of potential SEU-induced bridging faults can be reached as well as improvements in the performance and area utilization, compared to post-synthesis TMR, in which the voters are applied to the feedback structures in the circuit. Compared to the extreme case of post-synthesis TMR in which the voters are applied at the end of every configurable logic block, we reach 38% (26%) improvement in performance(area) of the implemented circuits.

Due to increase in demand for reconfigurability in embedded systems, real-time task scheduling is challenged by non-negligible reconfiguration overheads. If such overheads are not considered, tasks may not be schedulable under given deadlines, and hence, affecting the quality of service. We introduce the problem of real-time periodic task scheduling under transition overhead on heterogeneous reconfigurable systems. We formulate the problem as a network flow problem and provide a mixed integer linear programming solution. We compare our proposed solution with optimal scheduling under maximum fixed transition overhead. We deployed our method on task scheduling for multiple communication protocols on reconfigurable FPGA-like systems. Results show that our proposed scheduling improves the task schedulability by 24.2% in comparison with non-preemptive EDF and by 17.5% in comparison with maximum-transition-overhead scheduling.

Dynamic voltage/frequency scaling (DVFS) and adaptive body biasing (ABB) have shown to effectively reduce dynamic and leakage energy consumption in real-time embedded systems. Although these techniques exploit the slack time on a given task ordering, the task ordering may not provide a slack time distribution that DVFS/ABB can benefit from and this can limit the potential energy saving such techniques can provide. In this paper, we present an optimal network flow based solution for simultaneous static real-time scheduling and energy minimization (DVFS and ABB) on multiprocessors. Results show that our optimal solution reduces the energy dissipation by 47.84%, 26.21% and 17.46%, on average, in comparison with no-DVFS execution, voltage scaling algorithm with virtual continuous speed and an optimal energy minimization algorithm without task re-ordering, respectively.

In this paper, a novel thermal-aware dynamic placement planner for reconfigurable systems is presented, which targets transient temperature reduction. Rather than solving time-consuming differential equations to obtain the hotspots, we propose a fast and accurate heuristic model based on power budgeting to plan the dynamic placements of the design statically, while considering the boundary conditions. Based on our heuristic model, we have developed a fast optimization technique to plan the dynamic placements at design time. Our results indicate that our technique is two orders of magnitude faster while the quality of the placements generated in terms of temperature and interconnection overhead is the same, if not better, compared to the thermal-aware placement techniques which perform thermal simulations inside the search engine.

Partial dynamic reconfiguration (often referred to as partial RTR) enables true on-demand computing. In an on-demand computing environment, a dynamically invoked application is assigned resources such as data bandwidth, configurable logic. The limited logic resources are customized during application execution by exploiting partial RTR. In this article, we propose an approach that maximizes application performance when available bandwidth and logic resources are limited. Our proposed approach is based on theoretical principles of minimizing application schedule length under bandwidth and logic resource constraints. It includes detailed microarchitectural considerations on a commercially popular reconfigurable device, and it exploits partial RTR very effectively by utilizing data-parallelism property of common image-processing applications. We present extensive application case studies on a cycle-accurate simulation platform that includes detailed resource considerations of the Xilinx Virtex XC2V3000. Our experimental results demonstrate that applying our proposed approach to common image-filtering applications leads to 15--20% performance gain in scenarios with limited bandwidth, when compared to prior work that also exploits data-parallelism with RTR but includes simpler bandwidth considerations. Last but not the least, we also demonstrate how our proposed theoretical principles can be directly applied to solve related problems such as minimizing schedule length under logic resource and power constraints.

Although Triple Modular Redundancy (TMR) has been widely used to mitigate single event upsets (SEUs) in SRAM-based FPGAs, SEU-caused bridging faults between the TMR modules do not guarantee correctness of TMR design under SEU. In this paper, we present a novel approximation algorithm for resource binding on scheduled datapaths at the presence of TMR, which aims at containment of each SEU within a single replica of tripled operations. The key challenges are to avoid resource sharing between modular redundant operations and also to reduce the possibility of TMR masking breaches in resource allocation. We introduce the notion of vulnerability gap during resource sharing to potentially reduce the effort for white space allocation at the physical design stage in order to avoid bridging faults between TMR resources. The experimental results show that our proposed resource binding algorithm, followed by floorplanner, reduces the potential of TMR breaches by 20%, on average.

Partial dynamic reconfiguration, often called run-time reconfiguration (RTR), is a key feature in modern reconfigurable platforms. In this paper, we present parallelism granularity selection (PARLGRAN), an application mapping approach that maximizes performance of application task chains on architectures with such capability. PARLGRAN essentially selects a suitable granularity of data-parallelism for individual data parallel tasks while considering key issues such as significant reconfiguration overhead and placement constraints. It integrates granularity selection very effectively in a joint scheduling and placement formulation, necessary due to constraints imposed by partial RTR. As a key step to validating PARLGRAN, we additionally present an exact strategy (integer linear programming formulation). We demonstrate that PARLGRAN generates high-quality schedules with: (1) a set of small test cases where we compare our results with the exact strategy; (2) a very large set of synthetic experiments with over a thousand data-points where we compare it with a simpler strategy that tries to statically maximize data-parallelism, i.e., only considers resource availability; and (3) a detailed application case study of JPEG encoding. The application case-study confirms that blindly maximizing data-parallelism can result in schedules even worse than that generated by a simple (but RTR-aware) approach oblivious to data-parallelism. Last, but very important, we demonstrate that our approach is well-suited for true on-demand computing with detailed execution time estimates on a typical embedded processor. Heuristic execution time is comparable to task execution time, i.e., it is feasible to integrate PARLGRAN in a run-time scheduler for dynamically reconfigurable architectures.

At system level, the on-chip temperature depends both on power density and the thermal coupling with the neighboring regions. The problem of finding the right set of input power profile(s) for accurate temperature estimation has not been studied. Considering only average or peak power density may lead either to underestimation or overestimation of the thermal crisis, respectively. To provide more realistic temperature estimation, we propose to incorporate multiple power profiles. Using the proposed statistical methods to determine the closeness between the power profiles, we apply a clustering algorithm to identify few input power profiles. We incorporate them in a thermal-aware floorplanner and empirical results show that using the single input power profile (average or peak) leads to 37% degradation in critical wire delay and 20% degradation in wire length, compared to using the multiple input power profiles.

Design variability due to within-die and die-to-die variations has potential to significantly reduce the maximum operating frequency and effective performance of the system in future process technology generations. When multiple cores in MPSoC have different delay distributions, the problem of assigning tasks to the cores become challenging. This paper targets system level task allocation to stochastically minimize the total execution time of an application on MPSoC under process variation. In this work, we first introduce stochastically optimal task allocation problem. We provide formal theorems of the optimality of the solution in simple scenarios. We extend our theoretical work for generic cases in normal distribution. The proposed techniques enable efficient computation of task allocation using non-stochastic analysis. We apply these techniques in allocating tasks in the embedded system benchmark suites on MPSoC. We show that deterministic solution for system-level task allocation on widely used benchmark topologies and distributions (normal distribution) is almost as good as the best probabilistic solution.

Software Defined Radio (SDR) base stations can compensate for failures in disaster scenarios by assimilating different communication technologies. FPGAs play an important role in the platform of an SDR base station because of flexibility and DSP processing power that they deliver. The flexibility of FPGAs comes at the high cost of reconfiguration time overhead which can be a serious deterrence because of QoS requirements of real time traffic. In this paper we propose a solution to reduce reconfiguration time overhead at system-level where we are provided the configuration of each wireless system. Following that we step further and integrate our solution in to a floorplanner to generate placements for wireless systems which can systematically hide or reduce reconfiguration time overhead. Our experiments show the effectiveness of our approach

Multimedia and DSP applications have several computationally intensive kernels which are often off loaded and accelerated by application-specific hardware. This paper presents a speculative loop pipelining technique to overcome limitations of binary translation for hardware acceleration. Although many compilers have been developed at source level, it is desirable to translate the binary targeted to popular processors onto hardware for several practical benefits. However, the translated code can be less optimized. In particular, it is difficult to optimize memory accesses on binary to exploit pipeline parallelism since memory optimization techniques require perfect dependence information for correctness and efficiency. This information is not often available at binary level or even at the source level. Our technique synthesizes the pipeline with memory dependence speculation and postpones some phases of compilation by generating a small dependence analysis code or logic which makes use of runtime values. Such speculative optimization achieves the large amount of parallelism and does not depend on any user annotation. The experimental results show a promising speedup of up to 2.53 compared with the code in which memory accesses are not optimized in the pipeline fashion due to conservative memory analysis. In addition, we have evaluated our technique at hardware level implementation on FPGA devices and achieved comparable clock frequency and power consumption compared to a conservative method while achieving significant improvement in throughput.

Partial dynamic reconfiguration (often referred to as partial RTR) enables true on-demand computing. A dynamically invoked application is assigned resources such as data bandwidth, configurable logic, and the limited logic resources are customized during application execution with partial RTR. In this work, we present key theoretical principles for maximizing application performance when available bandwidth is limited. We exploit bandwidth very effectively by selecting a suitable clock frequency for each task and maximize performance with partial RTR by exploiting data-parallelism property of common image-processing tasks. Our theoretical principles are integrated in our scheduling strategy, SCHEDRTR. We present detailed application case studies on a cycle-accurate simulation platform that addresses micro architectural concerns and includes detailed resource considerations of the Virtex XC2V3000 device. Our results demonstrate that applying SCHEDRTR to common image-filtering applications leads to 15--20% performance gain in scenarios with limited bandwidth, when compared to a sophisticated RTR scheduling strategy with data-parallelism but simpler bandwidth considerations.

The majority of configuration bits affecting a design are devoted to FPGA routing configuration. We present a SEU-aware routing algorithm that provides significant reduction in bridging faults caused by SEUs. Depending on the routing architecture switches, for MCNC benchmarks, the number of care bits can be reduced between 13% and 19% on average with comparable delay. In addition, in Asymmetric SRAM FPGA using our router average FIT (failure-in-time) rate is reduced by 36%.

The current generations of FPGA comprise of many specialized hardware cores, like embedded processors, multipliers, RAMs and FIFOs, along with the regular arrays of reconfigurable logic. On any FPGA device, these embedded cores are located at fixed locations only. This makes the task of floorplanning for the applications with heterogeneous components very difficult. Recently, some researchers have started looking into this problem of heterogeneous floorplanning on FPGA. However, all these work suffer from one fundamental flaw which affects the quality of solutions leading to higher device areas or excessively high runtime. In this paper, we propose a heterogeneous floorplanner for the FPGA, HPlan, which is fast and highly efficient in finding floorplans of variety of resources. We present a case study of a real implementation on Xilinx Virtex device. The proposed floorplanner could effectively implement the design with tight resource constraints whereas the traditional floorplanner could not find a feasible floorplan.

The current generations of FPGA comprise of many specialized hardware cores, like embedded processors, multipliers, RAMs and FIFOs, along with the regular arrays of reconfigurable logic. On any FPGA device, these embedded cores are located at fixed locations only. This makes the task of floorplanning for the applications with heterogeneous components very difficult. Recently, some researchers have started looking into this problem of heterogeneous floorplanning on FPGA. However, all these work suffer from a fundamental flaw which affects the quality of solutions leading to higher device areas or excessively high runtime. In [1], we propose a heterogeneous floorplanner for FPGA, HPlan, which is highly efficient in finding floorplans of variety of resources. In this paper, we extend the floorplanner to include an adaptive placer algorithm. We also perform our experiments on the MCNC benchmarks for the floorplan with random heterogeneous resource allocations. We observe that as the statistical variation in the heterogeneous resource allocations is increased, the traditional floorplanner gives an increasing area of all the benchmarks whereas the HPlan floorplanner does not. The proposed floorplanner thus provides an efficient way to handle floorplans with large variations in the heterogeneous resources.

In this paper, we present co-processor selection problem for minimum energy consumption in hw/sw co-design on FPGAs with dual power mode. We provide theoretical analysis for the problem under no constraint, resource constraint, and timing constraint. We prove that the complexity of the problem in each case is NP-Hard and we provide a generalized ILP formulation. We compared the result of our approach in minimizing energy to the result of other approaches that had not considered both static and dynamic power during optimization and we showed that we can reduce energy by 63% in some cases.

Due to decreasing transistor sizes and increasing clock frequency, interconnect delay is a dominant factor in achieving timing closure in deep-submicrometer designs. In field programmable gate arrays (FPGA), interconnect delay is contributed by programmable routing switches. This increases the wire delay significantly. In FPGA devices, the interconnect delay is usually more than 40% of the total delay. Techniques like wire pipelining and retiming can manage delay of timing critical wires. However, the latency of the design limits the total pipelining in the design. Therefore, new techniques are needed at synthesis stage to consider the effect of critical wires in the design. In this paper, we propose an intuitive Critical Edge Reduction (CER) algorithm, which minimizes the number of critical wires on a maximal delay- budgeting solution under fixed latency constraint. We prove that this problem is NP-hard. We provide an integer linear programming formulation of the problem and an iterative heuristic algorithm (CER). During the course of our algorithm, we introduce multiple graph problems. We give a proof of NP-hardness of one such problem, which we call max arc-cost balancing problem. In our experiments, we present an in-depth analysis of tradeoff between various maximal budgetings and critical edge minimization. We implemented our design flow using a set of MediaBench datapaths on Xilinx VirtexE FPGA devices. Using our algorithm, the Xilinx Place-and-Route tool achieved timing closure, which is, on average, 2.8 times faster than using maximum budgeting. The resulting average clock period using CER algorithm outperforms the one using the maximum budgeting by 6%. Other results show similar advantages of critical edge minimization over traditional budgeting techniques.

Partial dynamic reconfiguration, often called RTR (run-time reconfiguration) is a key feature in modern reconfigurable platforms. While partial RTR enables additional application performance, it imposes physical constraints necessitating simultaneous scheduling and placement while mapping application task graphs onto such architectures. In this paper, we present PARLGRAN, an approach that maximizes performance of application task chains by selecting a suitable granularity of data-parallelism for individual data parallel tasks. Our approach focuses on reconfiguration delay overhead and placement-related issues (such as fragmentation) while selecting individual data-parallelism granularity as an integral part of simultaneous scheduling and placement. We demonstrate that our heuristic generates high-quality schedules on an extensive set of over a 1000 synthetic experiments by comparing the results with an approach that tries to statically maximize data-parallelism, i.e., does not consider the overheads and constraints associated with partial RTR. A detailed case-study on JPEG encoding additionally confirms that blindly maximizing data-parallelism can result in schedules even worse than that generated by a simple (but RTR-aware) approach oblivious to data-parallelism

In this work, the goal is to develop a flexible CAD tool by which designers can explore integration of different types of embedded hard cores and interfaces in the FPGA architectures. Our tool takes a RTL design and defined embedded hard cores. The authors have modified VPR for place and route with embedded blocks. We have experimented different modules to be embedded as hard cores on a FPGA device. We also explore the FPGA routing architecture with embedded hard cores by applying uniform and non-uniform routing channels. In many cases, non-uniform channels produce more area-efficient architectures. Our results show that there is a need for a tool for better exploration of design space for FPGAs with embedded hard cores

Partial dynamic reconfiguration is an emerging area in FPGA designs which is used for saving device area and cost. In order to reduce the reconfiguration overhead, two consecutive similar sub-designs should be placed in the same locations to get the maximum reuse of common components. This requires that all the future designs be considered while floorplanning for any given design. In this work, we introduce a new multi-layer sequence pair representation based floorplanner that allows overlap of static and non-static components of multiple designs and guarantees a feasible overlapping floorplan with minimal area packing. The multi-layer sequence pair is an efficient representation that helps in reducing the total floorplan runtime significantly. It also improves the design quality of the whole sequence as floorplans of all the designs are simultaneously computed. In our experiments, compared to a traditional sequential floorplanner, our floorplanner removes infeasibility in many designs, achieves an improvement of clock period by 12% on average and reduces the place and route time by as much as 3 times. It also reduces the average wirelength by 50% in the designs. Our proposed floorplanner could be used for finding high quality floorplans for applications that use partial reconfiguration

Power consumption is a key concern on modern reconfigurable architectures. In this paper, we address the problem of minimizing peak power while mapping application task chains onto reconfigurable architectures with partial dynamic reconfiguration capability. Our proposed methodology minimizes peak power for a given timing constraint. It is based on detailed data-parallelism considerations to ensure that tight timing constraints are met. Our methodology generates physically placed task execution schedules and includes selection of a suitable number of data-parallel instances for each task, a suitable clock frequency, and execution workload for each task instance. Case studies on real image-filtering applications demonstrate that our approach results in significant peak power savings (between 40%-50%) for tight as well as relaxed timing constraints

The major drawback of partial dynamic reconfiguration is the reconfiguration delay overhead. To reduce the reconfiguration bitstream between two consecutive implementations, design components are reused. However, this incurs additional physical constraints to design which can lead to unroutability and congestion in design. In this paper, we propose a physically-aware component reuse strategy. We propose a floorplanning algorithm to support two-dimensional partial reconfiguration. The proposed floorplanning tool enables a wide design space exploration for component reuse. Key features are selection of the fixed modules, location of the fixed modules, mapping to the fixed modules, and interconnect planning between the fixed and reconfigurable modules. We implemented a sequence of dataflow graphs on Xilinx Virtex 4 devices using our tool for component reuse. When reuse is exploited, the experimental results report more than 50% reduction in the number of reconfiguration frames compared to the flow during which component reuse is not applied. Our proposed floorplan-aware matching technique (to map the modules to fixed components) can reduce the reconfiguration frames by 10% on average compared to dependency-based matching algorithm. In addition, we show that by different placement of the modules for two consecutive tasks, the variation in the number of reconfiguration frames can be between 25%-60% or it may even lead to unroutability of the circuits. The results imply that there is a need to tune the physical design tools for minimizing runtime reconfiguration delay overhead.

This paper presents a theoretical framework that solves optimally and in polynomial time many open problems in time budgeting. The approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation, and min-skew time budget distribution. The authors develop a combinatorial framework through which we prove that many of the time-management problems can be transformed into a min-cost flow problem instance. The methodology is applied to intellectual-property-based datapath synthesis targeting field-programmable gate arrays. The synthesis flow maps the input operations to parameterized library modules during which different time budgeting policies have been applied. The techniques always improve the area requirement of the implemented test benches and consistently outperform a widely used competitor. The experiments verify that combining fairness and maximization objectives improves the results further as compared with pure maximum budgeting. The combined fairness and maximization objective improves the area by 25.8% and 28.7% in slice and LUT counts, respectively.

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.

Partial dynamic reconfiguration is a key feature of modern reconfigurable architectures such as the Xilinx Virtex series of devices. However, this capability imposes strict placement constraints such that even exact system-level partitioning (and scheduling) formulations are not guaranteed to be physically realizable due to placement infeasibility. We first present an exact approach for hardware-software (HW-SW) partitioning that guarantees correctness of implementation by considering placement implications as an integral aspect of HW-SW partitioning. Our exact approach is based on integer linear programming (ILP) and considers key issues such as configuration prefetch for minimizing schedule length on the target single-context device. Next, we present a physically aware HW-SW partitioning heuristic that simultaneously partitions, schedules, and does linear placement of tasks on such devices. With the exact formulation, we confirm the necessity of physically-aware HW-SW partitioning for the target architecture. We demonstrate that our heuristic generates high-quality schedules by comparing the results with the exact formulation for small tests and with a popular, but placement-uanaware scheduling heuristic for a large set of over a hundred tests. Our final set of experiments is a case study of JPEG encoding-we demonstrate that our focus on physical considerations along with our consideration of multiple task implementation points enables our approach to be easily extended to handle heterogenous architectures (with specialized resources distributed between general purpose programmable logic columns). The execution time of our heuristic is very reasonable-task graphs with hundreds of nodes are processed (partitioned, scheduled, and placed) in a couple of minutes

As system-on-chip (SoC) designs become more complex, it is becoming harder to design communication architectures to handle the ever increasing volumes of inter-component communication. Manual traversal of the vast communication design space to synthesize a communication architecture that meets performance requirements becomes infeasible. In this paper, we address this problem by proposing an automated approach for floorplan-aware bus architecture synthesis (FABSYN) to synthesize cost-effective, bus-based communication architectures that satisfy the performance constraints in a design. Our synthesis approach incorporates a high-level floorplanning and wire delay estimation engine to evaluate the feasibility of the synthesized bus architecture and detect bus cycle time violations early in the design How, at the system level. We present case studies of network communication SoC subsystems for which we synthesized bus architectures, detected and eliminated timing violations, and generated core placements in a matter of hours instead of several days for a manual effort.

Many reconfigurable architectures offer partial dynamic configurability, but current system-level tools cannot guarantee feasible implementations when exploiting this feature. We present a physically aware hardware-software (HW-SW) scheme for minimizing application execution time under HW resource constraints, where the HW is a reconfigurable architecture with partial dynamic reconfiguration capability. Such architectures impose strict placement constraints that lead to implementation infeasibility of even optimal scheduling formulations that ignore the nature of these constraints. We propose an exact and a heuristic formulation that simultaneously partition, schedule, and do linear placement of tasks on such architectures. With our exact formulation, we prove the critical nature of placement constraints. We demonstrate that our heuristic generates high-quality schedules by comparing the results with the exact formulation for small tests and a popular, but placement-uanaware scheduling heuristic for larger tests. With a case study, we demonstrate extension of our approach to handle heterogenous architectures with specialized resources distributed between general purpose programmable logic columns. The execution time of our heuristic is very reasonable- task graphs with hundreds of nodes are processed in a couple of minutes.

As System-on-Chip (SoC) designs become more complex, it is becoming harder to design communication architectures to handle the ever increasing volumes of inter-component communication. Manual traversal of the vast communication design space to synthesize a communication architecture that meets performance requirements becomes infeasible. In this paper, we address this problem by proposing an automated approach for synthesizing cost-effective, bus-based communication architectures that satisfy the performance constraints in a design. Our synthesis flow also incorporates a high-level floorplanning and wire delay estimation engine to evaluate the feasibility of the synthesized bus architecture and detect timing violations early in the design flow. We present case studies of network communication SoC subsystems for which we synthesized bus architectures, detected timing violations and generated core placements in a matter of hours instead of several days it took for a manual effort.

In modern dynamic FPGA-based platforms where multiple processes may be executing concurrently, partial dynamic reconfiguration (RTR) is a key technique for maximizing application performance under resource constraints. For platforms with column-based partial RTR, we propose a new technique to statically transform linear task graphs (common in image processing applications). In our approach, the granularity of data parallelism for each task is determined while considering the reconfiguration overhead along with architectural constraints imposed by partial RTR. On JPEG applications, our technique can improve the execution time by up to 37% by choosing the right granularity of task parallelism.

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%.

Due to decreasing transistor sizes and increasing clock frequency, interconnect delay is a dominant factor in achieving timing closure in deep sub-micron designs. Techniques like wire pipelining and retiming can manage delay of timing critical wires. The latency of the system, however, limits the total pipelining in the design. New techniques are, thus, needed at synthesis stage to consider the effect of critical wires in the design. In this work, we propose a novel intuitive algorithm, critical edge reduction (CER) algorithm, which produces a maximal delay budgeting solution under fixed latency while minimizing the number of critical wires. We also present an in-depth analysis of trade-off between maximum budgeting and critical edge minimization. We implemented our design flow using a set of MediaBench data paths on Xilinx VirtexE FPGA devices. Using our algorithm, the Xilinx Place and Route tool achieved timing closure, on average, 2.8 times faster than using maximum budgeting. The resulting average clock period using CER algorithm outperforms the one using maximum budgeting by 6%.

Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.

This work presents a theoretical framework that optimally solves many open problems in time budgeting. Our approach unifies a large class of existing time-management paradigms. Examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation and min-skew time budget distribution. We show that many of the time management problems can be transformed into a min-cost flow instance that can be optimally and efficiently solved through well-known combinatorial techniques. Experiments include mapping of several designs, which are implemented using parameterized CoreGen IP cores, on Xilinx FPGA devices. Different time budgeting policies have been applied during the mapping stage. Our time management techniques always improved the area requirement of the implemented testbenches compared to a widely-used path-based method. We also compared the maximum budgeting and fairness in delay budget assignments. Our experimental results show that an average improvement of 19% in area can be achieved when fairness and maximum budgeting policies are combined, compared to pure maximum budgeting.

Excess delay that each component of a design can tolerate under a given timing constraint is referred to as delay budget. Delay budgeting has been widely exploited to improve the design quality in very large scale integrated computer-aided design flow. The objective of the delay-budgeting problem investigated in this paper is to maximize the total delay budget assigned to each node in a directed acyclic graph under a given timing constraint. Due to the discreteness of the timing of the components in the libraries during design-optimization flow, discrete solution for delay budgeting is essential. We present an optimal integer delay-budgeting algorithm. We prove that the problem can be solved optimally in polynomial time. In addition, we look at different extensions of the delay-budgeting problem, such as maximization of weighted summation of delay budgets assigned to the nodes with constraints on the lower and upper bounds on the delay budget allocated to each node. We prove that for both aforementioned extensions, our algorithm can produce an optimal integer solution in polynomial time. Our algorithm is generic and can be applied at different design tasks at different levels of abstraction. We applied our proposed optimal delay-budgeting algorithm in library mapping during datapath synthesis on a field programmable gate array (FPGA) platform, using preoptimized cores of FPGA libraries. For each application, we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms the zero-slack algorithm (Nair et al. 1989) in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place and route up to two times.

Delay budget is an excess delay each component of a design can tolerate under a given timing constraint. Delay budgeting has been widely exploited to improve the design quality. We present an optimal integer delay budgeting algorithm. Due to numerical instability and discreteness of libraries of components during library mapping in design optimization flow, integer solution for delay budgeting is essential. We prove that integer budgeting problem - a 20-year old open problem in design optimization [7]- can be solved optimally in polynomial time. We applied optimal delay budgeting in mapping applications on FPGA platform using pre-optimized cores of FPGA libraries. For each application we go through synthesis and place and route stages in order to obtain accurate results. Our optimal algorithm outperforms ZSA algorithm [3] in terms of area by 10% on average for all applications. In some applications, optimal delay budgeting can speedup runtime of place_and_route up to 2 times.

In this paper, we study the problem of customized regular segmentation design in FPGA routing channels. We propose a deterministic algorithm for segmentation design problem in which each interval is assigned to only one segment (1-Segmentation). We solve the problem of maximum number of incremental track assignment of intervals by mincost network flow technique for 1-Segmentation design. The general K-Segmentation design problem can also be solved by some modifications in our algorithm. We have experimented our algorithm on a set of MCNC benchmarks and compared the routability of the segmented channels with the routability of different segmentations in FPGA routing architectures, one used by industrial Xilinx TM 4000 FPGA series. The experimental results show that the routability of the segmentation in general-purpose architecture can be as low as 18.4% while the routability of our proposed customized segmentation can be as high as 91%. This result shows the gap between the general FPGA routing architecture and customized architecture for a given application can be very significant and our method is capable of generating such optimized segmentation with high routability for a given application.

The idea of managing the comprising computations of an application executed in an FPGA-based system is presented. An efficient algorithm for exploiting the timing slack of building blocks of the application is proposed. The slack of these blocks can be utilized by replacing them with slower but "cheaper" modules and by assigning the computations to the proper resources. Thus, our approach manages the comprising computations and system resources at the same time. This is performed without compromising the timing constraints of the application and can lead to significant improvements in power dissipation, computation accuracy or other design metrics based on the application domain. Our algorithm is well-suited for arbitrary tree computations. Moreover, it delivers solutions that are desirably close to the optimal solution. Experimental results for a number of object tracking applications executed on resources embedded in cameras, show a significant amount of slack utilization.

The global routing problem decomposes the large, complex routing problem into a set of more manageable subproblems. The high correlation between the output of the global router and the detailed router enables the designer to efficiently use the global route to refine the design quickly before running the full detailed route. Hence, routability of the global routing solution is the key factor. The routability of the circuit depends on the congestion of the routing. In this paper, we study Steiner trees in terms of routability. We introduce the notion of flexibility, a geometric property associated with Steiner trees. We show that the flexibility of a Steiner tree is related to its routability. The main contribution of this paper is an algorithm which takes a stable Steiner tree as an input and maps it to a more flexible Steiner tree. Any existing Steiner tree algorithm can be used for the initial construction of the Steiner tree. Experiments with a global router on a subset of nets show that routing congestion is improved by approximately 20% locally throughout the region where those nets are routed.

Deep submicron effects, along with increasing interconnect densities, have increased the complexity of the routing problem. Whereas previously we could focus on minimizing wirelength, we must now consider a variety of objectives during routing. For example, an increased amount of timing restrictions means that we must minimize interconnect delay. But, interconnect delay is no longer simply related to wirelength. Coupling capacitance has become a dominant component of delay due to the shrinking of device sizes. Regardless, the most important objective is producing a routable circuit. Unfortunately, this often conflicts with minimizing interconnect delay as minimum delay routes create congested areas, for which an exact routing cannot be realized without violating design rules. In this work, we use the concept of pattern routing to develop algorithms that guide the router to a solution that minimizes interconnect delay - by considering both coupling and wirelength-without damaging the routability of the circuit. The paper is divided into two parts. The first part demonstrates that pattern routing can be used without affecting the routability of the circuit. We propose two schemes to choose a set of nets to pattern route. Using these schemes, we show that the routability is not hindered. The second part builds on the previous part by presenting a framework for coupling reduction using pattern routing. We develop theory and algorithms relating pattern routing and coupling. Additionally, we give suggestions on how to extend our theory and use our algorithms for both global and detailed routing.

Future computing systems need to balance flexibility, specialization, and performance in order to meet market demands and the computing power required by new applications. Instruction generation is a vital component for determining these trade-offs. In this work, we present theory and an algorithm for instruction generation. The algorithm profiles a dataflow graph and iteratively contracts edges to create the templates. We discuss how to target the algorithm toward the novel problem of instruction generation for hybrid reconfigurable systems. In particular, we target the Strategically Programmable System, which embeds complex computational units such as ALUs, IP blocks, and so on into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. In addition, instruction generation can be used to create soft reconfigurable macros---tightly sequenced prespecified operations placed in the reconfigurable fabric.

Routing tools consume a significant portion of the total design time. Considering routability at earlier steps of the CAD flow would both yield better quality and faster design process. In this paper we are presenting a routability-driven clustering method for cluster-based FPGAs. Our method packs LUTs into logic clusters while incorporating routability metrics into a cost function. The objective is to minimize this routability cost function . Our cost function is consistently able to indicate improved routability. Our method yields up to 50 % improvement over existing clustering methods in terms of the number of routing tracks required. The average improvement obtained is 16.5 %. Reduction in number of tracks yields reduced routing area.

This paper presents the concept of flexibility -- a geometric property associated with Steiner trees. Flexibility is related to the routability of the Steiner tree. We present an optimal algorithm which takes a Steiner tree and outputs a more flexible Steiner tree. Our experiments show that a net with a flexible Steiner tree increases its routability. Experiments with a global router show that congestion is improved by approximately 20\%.

We present an algorithm for simultaneous template generation and matching. The algorithm profiles the graph and iteratively contracts edges to create the templates. The algorithm is general and can be applied to any type of graph, including directed graphs and hypergraphs. We discuss how to target the algorithm towards the novel problem of instruction generation and selection for a hybrid (re)configurable systems. In particular, we target the strategically programmable system, which embeds complex computational units like ALUs, IP blocks, etc. into a configurable fabric. We argue that an essential compilation step for these systems is instruction generation, as it is needed to specify the functionality of the embedded computational units. Additionally, instruction generation can be used to create soft macros tightly sequenced pre-specified operations placed in the configurable fabric.

Emerging reconfigurable systems attain high performance with embedded optimized cores. For mapping designs on such special architectures, synthesis tools, that are aware of the special capabilities of the underlying architecture are necessary. We propose an algorithm to perform simultaneous scheduling and binding, targeting embedded reconfigurable systems. The algorithm differs from traditional scheduling methods in its capability of efficiently utilizing embedded blocks within the reconfigurable system. The algorithm can be used to implement several other scheduling techniques, such as ASAP, ALAP, and list scheduling. Hence we refer to it as a super-scheduler. The algorithm is a path-based scheduling algorithm. At each step, an individual path from the input DFG is scheduled. The experiments with several DFGs extracted from MediaBench suite indicate promising results. The scheduler presents the capability to perform the trade-off between maximally utilizing the high-performance embedded blocks and exploiting parallelism in the schedule.

In this wrok, we develop methods to reduce interconnect delay and noise caused by coupling. First, we explain the Coupling-Free Routing (CFR) problem. CFR takes a set of nets and tries to find a one-bend couple-free routing for a subset of nets. A routed net must not couple with any other routed net. We define coupling as a boolean variable which is true when the coupling of two nets is greater than some threshold. Any pair-wise coupling definition can be used. We argue that this problem is useful in both global and detailed routing

We will review a few key algorithmic and analysis concepts with application to physical design problems. We argue that design and detailed analysis of algorithms is of fundamental importance in developing better physical design tools and to cope with the complexity of present-day designs.

Predictable routing is the concept of using prespecified patterns to route a net. By doing this, we allow an more accurate prediction mechanism for metrics such as congestion and wirelength earlier in the design flow. Additionally, we can better plan the routes, insert buffers and perform wire sizing earlier. With comparable routing quality we show that we can predictably route up to 30% of a selected subset of nets. Also, we introduce methods for finding a group of nets which can be predictably routed.