The Fast Fourier Transform (FFT) is a fundamental algorithm in signal processing; significant efforts have been made to improve its performance using software optimizations and specialized hardware accelerators. Computational imaging modalities, such as MRI, often rely on the Non-uniform Fast Fourier Transform (NuFFT), a variant of the FFT for processing data acquired from non-uniform sampling patterns. The most time-consuming step of the NuFFT algorithm is “gridding;” wherein non-uniform samples are interpolated to allow a uniform FFT to be computed over the data. Each non-uniform sample affects a window of non-contiguous memory locations, resulting in poor cache and memory bandwidth utilization. As a result, gridding can account for more than 99.6% of the NuFFT computation time, while the FFT requires less than 0.4%. We present Slice-and-Dice, a novel approach to the NuFFT's gridding step that eliminates the presorting operations required by prior methods and maps more efficiently to hardware. Our GPU implementation achieves gridding speedups of over 250× and 16× vs prior state-of-the-art CPU and GPU implementations, respectively. We achieve further speedup and energy efficiency gains by implementing Slice-and-Dice in hardware with JIGSAW, a streaming hardware accelerator for non-uniform data gridding. JIGSAW uses stall-free fixed-point pipelines to process M non-uniform samples in approximately M cycles, irrespective of sampling pattern-yielding speedups of over 1500× the CPU baseline and 36× the state-of-the-art GPU implementation, consuming $\sim 200\mathrm{m}\mathrm{W}$ power and $\sim 12\mathrm{m}\mathrm{m}^{2}$ area in 16 nm technology. Slice-and-Dice GPU and JIGSAW ASIC implementations achieve unprecedented end-to-end NuFFT speedups of 8× and 36× compared to the state-of-the-art GPU implementation, respectively.

The 3-D ultrasound imaging provides distinct advantages over its 2-D counterpart leading to a more accurate analysis of tumors and cysts. However, the front end of a 3-D system must receive and process data at prodigious rates, making it impractical for power-constrained portable systems. Synthetic aperture sequential beamforming (SASB) is an ultrasound beamforming technique that splits the computation into two stages, such that the computation in Stage 1 can be completed in the power-constrained front end while the remaining computation can be done elsewhere. In this article, we present several algorithmic and architectural techniques to enable efficient computation of Stage 1 processing without compromising imaging quality. Specifically, we present algorithmic techniques that reduce the computational complexity in Stage 1 by 17× through a systematic reduction in the number of apodization coefficients. We propose a 3-D die stacked architecture where the signals received by 961 active transducers are digitized, routed by a network-onchip, and processed in parallel. This architecture does not require the explicit storage of incoming data samples. We synthesize the architecture using TSMC 28-nm technology node. The front-end power consumption is around 1.5 W, making it suitable for portable applications.

Managing tail latency is a primary challenge in designing large-scale Internet services. Queuing is a major contributor to end-to-end tail latency, wherein nominal tasks are enqueued behind rare, long ones, due to Head-of-Line (HoL) blocking. In this paper, we introduce Q-Zilla, a scheduling framework to tackle tail latency from a queuing perspective, and CoreZilla, a microarchitectural instantiation of our framework. On the algorthmic front, we first propose Server-Queue Decoupled Size-Interval Task Assignment (SQD-SITA), an efficient scheduling algorithm to minimize tail latency for high-disparity service distributions. SQD-SITA is inspired by an earlier algorithm, SITA, which explicitly seeks to address HoL blocking by providing an express-lane for short tasks, protecting them from queuing behind rare, long ones. But, SITA requires prior knowledge of task lengths to steer them into their corresponding lane, which is impractical. Furthermore, SITA may underperform an M/G/k system when some lanes become underutilized. In contrast, SQD-SITA uses incremental preemption to avoid the need for a priori task-size information, and dynamically reallocates servers to lanes to increase server utilization with no performance penalty. We then introduce Interruptible SQD-SITA, which further improves tail latency at the cost of additional preemptions. Finally, we describe and evaluate CoreZilla, wherein a multi-threaded core efficiently implements ISQD-SITA in a software-transparent manner at minimal cost. Our evaluation demonstrates that CoreZilla improves tail latency over a conventional SMT core with 2, 4, and 8 contexts by 2.25×, 3.23×, and 4.88×, on average, respectively.

High volume acquisition rates are imperative for certain medical ultrasound imaging applications, such as 3D elastography and 3D vector flow imaging. As ultrasound imaging transitions from 2D to 3D, the massive data bandwidth and billions of trigonometric operations required to reconstruct each volume leaves conventional computer architectures falling short. Despite recent algorithmic improvements, high-volume-rate ultrasound imaging remains computationally infeasible on known platforms. In this article, we expand our previous work on Tetris, a novel hardware accelerator for separable ultrasound beamforming that enables volume acquisition rates up to the physics limits of acoustic propagation delay. Through algorithmic and hardware optimizations, we enable an image reconstruction system design outclassing previously proposed accelerators in performance while lowering hardware complexity, storage, and power requirements. Tetris operates in a streaming fashion-without requiring on-chip storage of the entire receive signal-reconstructing volumes in real-time. For a representative imaging task, our proposed system generates physics-limited 13,000 volumes per second in a 2 watt power budget. The Tetris beamformer has an unprecedented power efficiency of 2.03 tera-beamforming operations per watt-an increase in efficiency of nearly 3× compared to the prior work.

High volume acquisition rates are imperative for medical ultrasound imaging applications, such as 3D elastography and 3D vector flow imaging. Unfortunately, despite recent algorithmic improvements, high-volume-rate imaging remains computationally infeasible on known platforms.