Due　to　the　high　level　of　parallelism,　there　are　unique　challenges　in　developing　system　software　on　massively　parallel　hardware　such　as　GPUs.　One　such　challenge　is　designing　a　dynamic　memory　allocator　whose　task　is　to　allocate　memory　chunks　to　requesting　threads　at　runtime.　State-of-the-art　GPU　memory　allocators　maintain　a　global　data　structure　holding　metadata　to　facilitate　allocation/deallocation.　However,　the　centralized　data　structure　can　easily　become　a　bottleneck　in　a　massively　parallel　system.　In　this　paper,　we　present　a　novel　approach　for　designing　dynamic　memory　allocation　without　a　centralized　data　structure.　The　core　idea　is　to　let　threads　follow　a　random　search　procedure　to　locate　free　pages.　Then　we　further　extend　to　more　advanced　designs　and　algorithms　that　can　achieve　an　order　of　magnitude　improvement　over　the　basic　idea.　We　present　mathematical　proofs　to　demonstrate　that　(1)　the　basic　random　search　design　achieves　asymptotically　lower　latency　than　the　traditional　queue-based　design　and　(2)　the　advanced　designs　achieve　significant　improvement　over　the　basic　idea.　Extensive　experiments　show　consistency　to　our　mathematical　models　and　demonstrate　that　our　solutions　can　achieve　up　to　two　orders　of　magnitude　improvement　in　latency　over　the　best-known　existing　solutions.　©　2022　ACM.