This paper considers the robust ${cal D}$-stability margin problem under polynomic structured real parametric uncertainty. Based on the work of De Gaston and Safonov (1988), we have developed techniques such as, a parallel frequency sweeping strategy, different domain splitting schemes, which significantly reduce the computational complexity and guarantee the convergence.