Designing a microprocessor involves determining the optimal microarchitecture for a given objective function and a given set of constraints. This paper studies the shape of the design space of superscalar out-of-order processors under different objective functions and constraints. We show that local optima exist whose objective function values are significantly worse than for the global optimum, in several cases more than 20% off. We subsequently consider the implications of this observation for early design stage exploration studies. Four design space search algorithms (random descent, steepest descent, one-parameter-at-a-time and simulated annealing) are evaluated according to their ability to avoid local optima and their overall simulation time. We conclude that one-parameter-at-a-time achieves a good balance between both criteria. In addition, we study the usefulness of fast simulation techniques for early design stage exploration. A case study with statistical simulation shows that significant simulation speedups are achieved while incurring little inaccuracy (a few percent) on the optimal design point.