Rapid growth in the cache sizes of Chip Multiprocessors (CMPs) to support high performance applications will lead to increase in wire-delays and unexpected access latencies. NUCA architectures help in managing the capacity and access time for such larger cache designs. Static NUCA (S-NUCA) has a fixed address mapping policy whereas dynamic NUCA (D-NUCA) allows blocks to relocate nearer to the processing cores at runtime. As the blocks can map to more than one location in D-NUCA, we need efficient searching mechanism to locate the requested block. In this paper we propose a searching algorithm for D-NUCA designs in CMPs, called the HKState-NUCA (Home Knows where to find data and its state within the NUCA cache). This algorithm provides faster access to data lines compared to existing searching mechanisms. We have shown that our HKState-NUCA search mechanism reduces search requests (hop count) by about 50.89%, and achieves an average improvement of 7.04% in the hit-rate, compared to an existing searching algorithm HK-NUCA [1]. © 2015 IEEE.