  With the recent proliferation of on-device AI, there is an increasing need to
run computationally intensive DNNs directly on mobile devices. However, the
limited computing and memory resources of these devices necessitate effective
pruning techniques. Block-wise pruning is promising due to its low accuracy
drop tradeoff for speedup gains, but it requires block positions to be aligned
with block size, hindering optimal position selection to minimize model
accuracy drop. Unaligned block pruning (UBP) addresses this by allowing blocks
to be selected at arbitrary positions, yet its practical use is limited by a
time-consuming optimal block selection algorithm and lack of efficient
inference kernels. In this paper, we propose a pseudo-optimal yet fast block
selection algorithm called Block Expansion and Division (BED), which can be
integrated into an iterative model training process. Additionally, we introduce
an efficient inference kernel implementation for mobile devices, enabling a
UBP-based model to achieve similar latency to a DNN model compressed by aligned
block pruning. We demonstrate the superiority of our techniques on a real
mobile phone with MobileNet and ResNet models.
