Existing data-plane verifiers face severe performance challenges in verifying hyper-scale underlay data center networks (DCNs) – centralized verifiers often fail to fully exploit the parallelism offered by the modern multi-core CPUs, while distributed verifiers suffer from high overhead due to task distribution and inter-node communication. To overcome these limitations, this paper introduces HeTu, a high-performance centralized parallel data-plane verifier specifically for verifying hyper-scale underlay DCNs. HeTu achieves ultra-fast verification through three key designs: (1) a fully parallel verification framework with small graph construction overhead, (2) a new binary decision diagram management strategy that enables full parallelism by using separated storage and selectively indexing and caching network-level predicates to reduce redundant operations, and (3) an optimized forwarding graph model that aggregates parallel tasks to eliminate redundant computation. Extensive evaluations on synthetic FatTree and large-scale production datasets show that HeTu outperforms state-of-the-art algorithms in runtime by 100× to 6000×, demonstrating its superior scalability and efficiency in data-plane verification of hyper-scale DCNs.