Recommendation systems, social network analysis, medical imaging, and data mining often involve processing sparse high-dimensional data. Such high-dimensional data are naturally represented as tensors, and they cannot be efficiently processed by conventional matrix or vector computations. Sparse Tucker decomposition is an important algorithm for compressing and analyzing these sparse high-dimensional datasets. When energy efficiency and data privacy are major concerns, hardware accelerators on resource-constraint platforms become crucial for the deployment of tensor algorithms. In this work, we propose a hybrid computing framework containing CPU and FPGA to accelerate sparse Tucker factorization. This algorithm has three main modules: 1) tensor-times-matrix (TTM); 2) Kronecker products; and 3) QR decomposition with column pivoting (QRP). In addition, we accelerate the former two modules on a Xilinx FPGA and the latter one on a CPU. Our hybrid platform achieves$23.6 \times \sim 1091\times $speedup and over 93.519% ~ 99.514% energy savings compared with CPU on the synthetic and real-world datasets.

Reconfigurable digital filter is being widely used in applications such as communication and signal processing. Its performance, power consumption, and logic resource utilization are the major factors to be taken into consideration when designing the filters. This paper proposes a concise canonic signed digit coefficient grouping method aiming at reducing the number of common subexpressions (CSs). Further, we statistically analyze every CS occurance for numerous sorts of the finite-impulse response (FIR) filters and obtain characterization of the distribution behavior for all the possible CS patterns in a 16-bit coefficient. Thus, a novel processing element structure is proposed to form a medium-grain array for computationally efficient realization of reconfigurable FIR filter. The experiment results suggest such design implementations typically achieve 21% reduction in silicon area, 20% decrease in power consumption, and 14% improvement in operation speed in comparison to other conventional FIR architectures.

In the last decade, progress in logic synthesis has brought about new advantageous circuit representations. These representations, such as And-Inverter Graphs in the ubiquitous open-source synthesizer ABC, have inspired new designs of Field Programmable Gate Arrays (FPGAs), which, instead of using Look-Up Tables (LUTs), mimic the topology of the circuit representation in the basic logic cells. More recent examples are Majority-Inverter Graphs, another uniform representation which has triggered considerable interest in synthesis and which naturally suggests new logic cells. Yet, in this paper we observe how naïvely adapting technology mapping solutions for classic LUT-based FPGAs to these new architectures incurs severe shortcomings. The key issue is that LUTs are inherently input-constrained (the logic function they implement is irrelevant) and have generally a single output; on the other hand, logic cells made of uniform networks of some fundamental logic function (e.g., And-Invert) are constrained in terms of logic depth and multiple outputs are an integral feature. We introduce novel and effective solutions to address these differences; the result is a highly versatile mapper—thus enabling further research in these new architectures—with a significantly better performance than what is described in literature for one such architecture. Specifically, when we compare with the state of the art on one sample architecture, we obtain a significant decrease in area (on average 18% over several benchmarks) while also improving slightly the critical path (a reduction of 3%).

FPGA-based SoCs have been gaining great favors among traditional applications and expanding the application domains to some new areas. Reusing and sharing components is an attractive and pratical methodology for system designers to reduce the design complexity of the SoC architectures. Open source hardware has become an effective method of improving the design productivity. As the core functional component, processors affects the performance of SoC systems. This paper investigates existing open source processors, and gives an overview. From the points of usability and stability, the main features of open source processors are summarized. Following these features, some open source processors with high usability and stability are selected. These open source processors and existing vendor-provided soft processors are implemented on Stratix V and Virtex-7 FPGAs using corresponding EDA tools, Quart us n and ISE. The implementation results are compared and discussed.

Dual-output lookup tables (LUTs) are mainstream in the design of commercial FPGA products. A detailed exploration of architectural parameters of FPGAs based on dualoutput LUTs is presented. Different from traditional single-output LUT based architecture, “shared inputs” between the sub-LUTs is a new parameter specific to dual-output architecture. In this paper, we focus on the effect of ratio of shared inputs on the performance and area-efficiency. First, we study the required cluster inputs and derive a relationship between cluster inputs, LUT size and cluster size under different ratios of shared inputs. Secondly, our evaluation results show that a FPGA with 4-LUTs and a shared input ratio of two thirds is preferred for area-efficiency, while a large LUT size of 9 with no shared inputs achieves best performance. Finally, we determine that a LUT size of 4, a cluster size from 3 to 8, and a shared input ratio between 1/3 and 2/3, provide the best area-delay product for dual-output LUT based FPGAs.

An approach to estimate the performance of FPGA architectures is proposed based on semi-supervised model tree algorithm. The proposed approach avoids synthesizing, mapping, packing, placing and routing, which are essential steps in a traditional flow to obtain the performance of FPGA. Thus it is time efficient while the performance predicted maintains quite close to the result obtained through the traditional method (a tool flow called VTR). This can be utilized effectively during the early FPGA design stage to choose an optimal architecture under a certain metric. Comparisons are made between the performance obtained by the proposed approach and by VTR on a commercial 40nm technology. Results show that the proposed approach has MRE below 7.62% compared to VTR, and improves the time cost by thousands of times when utilized in architecture design space exploration.

In this paper we first examine the impact of FPGA size on overall performance and run-time of placement and routing in the context of cluster-based island-style FPGAs. Based on the observations, an FPGA placement algorithm, Min-Size, is introduced to alleviate the deterioration of performance and run-time of placement and routing when using a large FPGA to implement a circuit. We achieve this by allowing Min-Size to generate a more compact placement of logic, I/O and hard blocks. Our experimental results have shown a 3X and AX speedup in placement and routing run-time, a 38% and 41% reduction in wire length, and a 8% and 5% improvement in critical path delay when FPGA size increases 10 times.

Compared to the use of a typical software development flow, the productivity of developing FPGA-based compute applications remains much lower. Although the use of high-level synthesis (HLS) tools may partly alleviate this shortcoming, the lengthy low-level FPGA implementation process remains a major obstacle to high productivity computing, limiting the number of compile-debug-edit cycles per day. Furthermore, high-level application developers often lack the intimate hardware engineering experience that is needed to achieve high performance on FPGAs, therefore undermining their usefulness as accelerators. To address the productivity and performance problems, a HLS methodology that utilizes soft coarse-grained reconfigurable arrays (SCGRAs) as an intermediate compilation step is presented. Instead of compiling high-level applications directly to circuits, the compilation process is reduced to an operation scheduling task targeting the SCGRA.

Physical block memory is one of the earliest hardened blocks in modern FPGAs. FPGA memory mapping utilizes memory blocks to construct user's logic memory designs. Previous mapping methods optimized for circuit area or power consumption. However, timing performance becomes more important for large and critical logic memory designs. In this work, a critical path delay model will be presented for the first time to estimate implementation performance during memory mapping. Experiment results showed that over 90% estimation errors by the model were within 10% and the average was only 3.5%. Based on the delay model, we proposed the first timing-constrained FPGA memory mapping algorithm. The algorithm generates memory configurations that meet the user's performance requirement. The algorithm also achieves optimal area/power subject to the user's timing constraint. The area or power optimum was validated with a commercial FPGA memory mapper.

Compiling high-level user applications for execution on FPGAs often involves synthesizing dataflow graphs beyond the size of the available on-chip computational resources. One way to address this is by folding the execution of the given dataflow graphs onto an array of directly connected simple configurable processing elements (CPEs). Under this scenario, the performance and energy-efficiency of the resulting system depends not only on the mapping schedule of the compute operations on the CPEs, but also on the topology of the interconnect array that connects the CPEs. This paper presents a framework in which the operation scheduler and the underlying CPE interconnect network topology are co-optimized on a per-application basis for energy-efficient FPGA computation. Given the same application, more than 2.5x difference in energy-efficiency was achievable by the use of different common regular array topologies to connect the CPEs. Moreover, by using irregular application-specific interconnect topologies derived from a genetic algorithm, up to 50% improvement in energy-delay-product was achievable when compared to the use of even the best regular topology. The use of such framework is anticipated to serve as part of a rapid high-level FPGA application compiler since minimum hardware place-and-route is needed to generate the optimal schedule and topology.

Computations involving matrices form the kernel of a large spectrum of computationally demanding applications for which FPGAs have been utilized as accelerators. Their performance is related to their underlying architectural and system parameters such as computational resources, memory and I/O bandwidth. A simple analytic model that gives an estimate of the performance of FPGA-based sparse matrix-vector and matrix-matrix multiplication is presented, dense matrix multiplication being a special case. The efficiency of existing implementations are compared to the model and performance trends for future technologies examined.

The design and implementation of a sparse matrix-matrix multiplication architecture on FPGAs is presented. Performance of the design, in terms of computational latency, as well as the associated power-delay and energy-delay tradeoff are studied. Taking advantage of the sparsity of the input matrices, the proposed design allows user-tunable power-delay and energy-delay tradeoffs by employing different number of processing elements (PEs) in the architecture design and different block size in the blocking decomposition. Such ability allows designers to employ different on-chip computational architecture for different system power-delay and energy-delay requirements. It is in contrast to conventional dense matrix-matrix multiplication architectures that always favor the maximum number of PEs and largest block size. In our implementation, the better energy consumption and power-delay product favors less PEs and smaller block size for the 90%-sparsity matrix-matrix multiplications. While in order to achieve better energy-delay product, more PEs and larger block size are preferred.

Many high-performance applications involve large data sets that are impossible to fit entirely within on-chip memories of even the largest FPGAs. As a result, they must be stored in off-chip SDRAMs and loaded onto the FPGAs as computations progress. Because of the high latency and energy consumption associated with off-chip memory accesses, it is important to develop efficient operation schedules that not only minimize latency of computations, but also the amount of data I/Os. We formulate this problem as a modified resource-constrained job scheduling problem. The problem is then solved using a list scheduling algorithm that takes advantage of the fast burst-mode access of SDRAMs. Results have shown that for large problem sizes, the performance of our algorithm is within 1% of a hand-optimized matrix-matrix multiplication implementation, with no memory overhead, and is within 0.03% of the theoretical minimum latency of an 8-by-8 cofactor matrix computation.