  Pairwise sequence alignment is a very time-consuming step in common
bioinformatics pipelines. Speeding up this step requires heuristics, efficient
implementations, and/or hardware acceleration. A promising candidate for all of
the above is the recently proposed GenASM algorithm. We identify and address
three inefficiencies in the GenASM algorithm: it has a high amount of data
movement, a large memory footprint, and does some unnecessary work. We propose
Scrooge, a fast and memory-frugal genomic sequence aligner. Scrooge includes
three novel algorithmic improvements which reduce the data movement, memory
footprint, and the number of operations in the GenASM algorithm. We provide
efficient open-source implementations of the Scrooge algorithm for CPUs and
GPUs, which demonstrate the significant benefits of our algorithmic
improvements. For long reads, the CPU version of Scrooge achieves a 20.1x,
1.7x, and 2.1x speedup over KSW2, Edlib, and a CPU implementation of GenASM,
respectively. The GPU version of Scrooge achieves a 4.0x 80.4x, 6.8x, 12.6x and
5.9x speedup over the CPU version of Scrooge, KSW2, Edlib, Darwin-GPU, and a
GPU implementation of GenASM, respectively. We estimate an ASIC implementation
of Scrooge to use 3.6x less chip area and 2.1x less power than a GenASM ASIC
while maintaining the same throughput. Further, we systematically analyze the
throughput and accuracy behavior of GenASM and Scrooge under various
configurations. As the best configuration of Scrooge depends on the computing
platform, we make several observations that can help guide future
implementations of Scrooge. Availability: https://github.com/CMU-SAFARI/Scrooge
