Transmission electron tomography (TET) is a widely used biomedical imaging technique. Iterative reconstruction with regularization is the common approach to obtain high-quality reconstructed images for TET. Mumford-Shah (MS) regularization has the advantage in preserving image edges; but it is computation and memory-intensive because it is NP-hard when applied to TET. In this work, we design an FPGA accelerator for iterative image reconstruction for TET with the MS regularization. We first design the accelerator with multiple processing elements (PE) to leverage the parallelism in the TET reconstruction. We then schedule the forward projection and back projection according to the imaging geometry of TET to optimize off-chip memory access. Finally, we optimize the local buffer with customized partitioning for the stencil memory access of basic operations to increase the throughput of a single PE. Our FPGA accelerator achieves 6.68X and 1.87X speedup with the same image quality compared with the same algorithm implemented on CPU and GPU, respectively. And the off-chip bandwidth requirements of forward and back projection are reduced by one to two orders of magnitude. Compared with the state-of-the-art acceleration works on GPU and FPGA, we achieve 1.18X and 1.91X throughput, respectively.

X-ray computed tomography (CT) is commonly used to obtain vivo images to characterize diseases but results in radiation exposure to patients. Low-dose CT (LDCT) provides CT images of clinical quality with reduced cumulative radiation dose. Iterative image reconstruction methods with effective regularization are used for LDCT but generally require more computing resources and induce higher computational load than the conventional filtered backprojection (FBP) methods. The high computational demand of the iterative reconstruction (IR) with notably increased reconstruction time precludes its routine clinical application. In this work, we focus on the FPGA acceleration of a compute-intensive full IR (full-IR) algorithm based on the Mumford-Shah regularization. At the algorithmic level, we propose a beam-based asynchronous update algorithm to reduce the computational cost and alleviate the conflicts. At the hardware-level, we first present pipeline-friendly optimization for the original algorithm to increase the computation throughput. We then apply the LDCT-specific tiling strategy to improve the data reuse rate. The experimental results show that our implementation takes 8.5 min to reconstruct a typical physical phantom with the image quality comparable with the vendor's result. The FPGA implementation achieves 11.6× throughput against the state-of-the-art GPU version.

FPGAs are becoming significant for implementing low-latency convolutional neural networks, because of performance demands and power constraints. Conventional implementations of convolutional layers are usually direct convolution, involving nested loops over channels, feature maps, and filters. Explicit general matrix multiplications (GEMMs) cost extra memory space, and the limited on-chip RAMs prevent an efficient GEMM-based implementation. In this paper, we evaluate a low-memory method of GEMMs on FPGAs based systolic arrays. We design a novel accelerator to save the bandwidth and increase the parallelism. We evaluate our design on MobileNet V1 and Inception V4. Our implementation achieves a throughput of around 3.5 TOP/s for both models. We also reduce the memory usage by 21% compared to explicit GEMM implementation for MobileNet V1 and 44% for Inception V4.

In this work, we aim to accelerate the iterative reconstruction (IR) algorithm used for 3D low dose computer tomography (LDCT) reconstruction to reduce the long execution time from an order of several hours on CPU to a few minutes. IR algorithms such as Mumford-Shah (MS) regularization can be used to get high-quality images even though the signal-noise ratio (SNR) of low dose projection data is low. However, IR is a computation and memory-intensive application and the long execution time precludes its clinical application. We adopt the ray-based parallel algorithm and designed a customized processing engine with multiple parallel processing elements (PEs) on field-programmable gate array (FPGA) to improve the computation efficiency. To reduce resource utilization, we proposed a best-first search algorithm combined with pruning to find the optimal bit width for fixed-point reconstruction. Besides, an offline memory optimization framework based on a greedy based clustering algorithm is proposed to reduce external memory bandwidth requirement and balance the workload of parallel PEs. Experiments on a 3D Shepp-Logan phantom show 2.81X and 1.91X speedup over the state of art single GPU and FPGA implementation.

Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13× speedup compared to the state-of-the-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is limited due to higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on asymmetric multi-FPGA architectures. In this approach, the neural network mapping can be formulated as a resource allocation problem. We design a dynamic programming-based partitioning to solve this problem optimally. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

FPGAs are commercially available off-the-shelf for implementing convolutional neural network (CNN) accelerators to trade off accuracy, performance, and power. Systolic array architecture for CNN accelerators on FPGAs has the potential to run at a high frequency due to its regular and simple interconnections. However, current FPGA CAD tools are unable to synthesize and layout systolic arrays in high quality. In this paper, we identify the reasons for the frequency degradation of systolic array designs for CNN accelerators. We also propose two methods to improve the frequency at the front-end and the back-end, respectively. The experimental results show that our methods are able to achieve 1.29 × higher frequency and attain 1.5TOPS for the VGG16 network on the Xilinx KCU1500 platform.

Serial equivalency can provide easier regression testing and customer support in production-grade CAD software. While existing parallel routing techniques have become sufficiently advanced to accelerate the execution time, support for serial equivalency has been very limited or ignored due to it was considered costly. In this paper, we propose serial-equivalent parallel routing for FPGAs. We use an optimal dependency-aware scheduling to facilitate serial equivalency of parallel routing algorithm. This capability enables the same answer as the serial version of the parallel algorithm, regardless of how many processing cores are used. We also validate this property across different hardware platforms. Further experimental results show that we achieve a 14.27x speedup on the MPI-based distributed parallel computer and a 19.65x speedup on the GPU-based massively parallel machine. To our knowledge, it is the first parallel routing with a serial equivalency guarantee.

FPGAs are very attractive to accelerate the deep neural networks (DNNs). While single-FPGA can provide good performance for small-scale DNNs, support for large-scale DNNs is very limited due to they require higher resource demand. In this paper, we propose an efficient mapping approach for accelerating large-scale DNNs on an asymmetric multi-FPGA architecture. Relative to the state-of-the-art single-FPGA resource reuse for large-scale DNNs, we consider multi-FPGA fashion to strive for higher performance. In this fashion, the neural network mapping problem can be formulated as a resource allocation problem, and a dynamic programming-based partitioning is designed to solve this problem optimally. Notice that the network topology and communication bandwidth of multiple FPGAs are always used to guide the partitioning to boost the performance while satisfying the constraints of resource-performance trade-off in a single FPGA. Experimental results using the large-scale ResNet-152 demonstrate that our approach deploys sixteen FPGAs to provide an advantage of 16.4x GOPS over the state-of-the-art work.

Stochastic gradient descent (SGD) is a widely-used algorithm in many applications, especially in the training process of deep learning models. Low-precision implementation for SGD has been studied as a major acceleration approach. However, if not appropriately used, low-precision implementation can deteriorate its convergence because of the rounding error when gradients become small near a local optimum. In this work, to balance throughput and algorithmic accuracy, we apply the Q-learning technique to adjust the precision of SGD automatically by designing an appropriate decision function. The proposed decision function for Q-learning takes the error rate of the objective function, its gradients, and the current precision configuration as the inputs. Q-learning then chooses proper precision adaptively for hardware efficiency and algorithmic accuracy. We use reconfigurable devices such as FPGAs to evaluate the adaptive precision configurations generated by the proposed Q-learning method. We prototype the framework using LeNet-5 model with MNIST and CIFAR10 datasets and implement it on a Xilinx KCU1500 FPGA board. In the experiments, we analyze the throughput of different precision representations and the precision-selection of our framework. The results show that the proposed framework with adapative precision increases the throughput by up to 4.3× compared to the conventional 32-bit floating point setting, and it achieves both the best hardware efficiency and algorithmic accuracy.

Low-dose X-ray computed tomography (XCT) is a popular imaging technique to visualize the inside structure of object non-destructively. Model-based Iterative Reconstruction (MBIR) method can reconstruct high-quality image but at the cost of large computational demands. Therefore, MBIR of ten resorts to the platforms with hardware accelerators such as GPUs to speed up the reconstruction process.

The non-exact projective NPNP (NP3) Boolean matching problem is practically significant in the applications of technology mapping, logic verification, and hardware security. However, its difficulty compels an unsatisfactory running time, and conventional algorithms for the basic NPNP Boolean matching problem perform terribly on the non-exact and projective type. In this paper, we propose a novel algorithm to solve this newly rising NP3 Boolean matching problem, and multiple types of optimization were applied to further improve the performance. Experimental results indicate that our algorithm has outstanding outcomes.

The dual-mode delay model, while being effective for characterizing on-chip timing variations, also yields timing analysis results that are overly pessimistic due to the Common Path Pessimism (CPP). In this paper, we develop a fast and accurate block-based algorithm for removing this pessimism in timing analysis, when the dual-mode delay model is used. We illustrate the effectiveness of our algorithm on a set of benchmarks from the TAU 2014 Contest [1].

Due to the continuous scaling of integration density and the increasing diversity of customized designs, there are increasing demands on the scalability and the customization of EDA tools and flows. Commercial EDA tools usually provide an interface of TCL scripting to extract and modify the design information for a flexible design flow. However, we observe that the current TCL scripting is not designed for the complete netlist extraction, resulting in a significant degradation in performance. For example, it takes over 20 minutes to extract the complete netlist of a 466K-cell design using TCL. This extraction may be repeated several times when interfacing between the existing EDA platforms and the actual distributed EDA algorithms. This drastic decrease in efficiency is a great barrier for customized EDA tool development. In this paper, we propose to build a distributed framework on top of TCL to accelerate the netlist extraction and use the distribution detailed placement as an example to demonstrate its capability. This framework is promising in scaling out physical design algorithms to run on a cluster.

The "early/late split" in delay modeling is an effective approach to handle the variability in deep submicron integrated circuits. However, static timing analysis with early/late split is often too conservative due to the common path pessimism, where the common path pessimism removal (CPPR) technique is helpful to eliminate the unnecessary pessimism. In this paper, we propose a fast and simple CPPR algorithm with sub-quadratic time complexity.

X-ray computed tomography is an important technique for clinical diagnose and nondestructive testing. In many applications a number of image processing steps are needed before the image information becomes useful. Image segmentation is one of such processing steps and has important applications. The conventional flow is to first reconstruct the image and then obtain image segmentation afterwards. In contrast, an iterative method for simultaneous reconstruction and segmentation (SRS) with Mumford-Shah model has been proposed, which not only regularizes the ill-posedness of the tomographic reconstruction problem, but also produces the image segmentation at the same time. The Mumford-Shah model is both mathematically and computationally difficult. In this paper, we propose a data-decomposed algorithm of the SRS method, accelerate it using FPGA devices. The proposed algorithm has a structure that invokes a single kernel many times without involving other computational tasks. Though this structure seems best fit on GPU-like devices, experimental results show that a 73X, 11X, and 1.4X speedup can be achieved by the FPGA acceleration over the CPU implementation of the original SRS algorithm and ray-parallel SRS algorithm, and the GPU implementation of the ray-parallel SRS.

The conventional approach of computed tomography (CT) is to solve each image processing task individually in sequence. An obvious drawback is that the measured data is only used once at the first step, and the possible errors, from noises in the measured data, inappropriate modeling, or inappropriate parameters, are not easy to be corrected and will be propagated into the later steps. As a consequence, approaches that combine the reconstruction and the specific processing task have become popular. This work adopts an iterative algorithm with simultaneous reconstruction and segmentation using the Mumford-Shah model, which can be applied not only to regularize the ill-posedness of the tomographic reconstruction problem, but also to compute segmentation directly from the measured data. The Mumford-Shah model is both mathematically and computationally difficult. In this paper, we accelerated this computation and data intensive application by FPGA devices and achieved 9.24X speedup over the conventional CPU implementation.

In this paper we propose a quantitative approach to analyze the impact of heterogeneous blocks (H-blocks) on the FPGA placement quality. The basic idea is to construct synthetic heterogeneous placement benchmarks with known optimal wire-length to facilitate the quantitative analysis. To the best of our knowledge, this is the first work that enables the construction of wirelength-optimal heterogeneous placement examples. Besides analyzing the quality of existing placers, we further decompose the impacts of H-blocks from the architectural aspect and netlist aspect. Our analysis shows that a heterogeneous design hides the wirelength degradation by a more compact netlist than its homogeneous version; however, the heterogeneity results in a optimality gap of 52% in wirelength, where 25% is from architectural heterogeneity and 27% is from netlist heterogeneity. Therefore, new heterogeneous placement algorithms are needed to bridge the optimality gap and improve design quality.