Computer architects rely on cycle-by-cycle simulation to evaluate the impact of design choices and to understand tradeoffs and interactions among design parameters. Although several techniques reduce time per individual simulation, efficiently exploring exponential-size design spaces spanned by several interacting parameters remains an open problem: the sheer number of experiments renders detailed simulation intractable. We attack this via an automated approach for building highly accurate and confident predictive models of design spaces. We collect simulation data incrementally, giving reliable estimates of model error on the full parameter space at each step of the building process. As validation, we perform sensitivity studies on memory system and microprocessor design spaces (conducting over 300K detailed simulations). Our models generally predict IPC with less than 1-2% error, even when trained on as little as 2% of the full design space. Further, our mechanism is orthogonal to techniques that reduce simulation runtimes. SimPoint [23] reduces the number of simulated instructions per experiment by 8-62?. We reduce the total number of simulated instructions by 50-200?. Combining our approach with SimPoint reduces the number of simulated instructions required to complete thorough design-space explorations by 1000-13,000?. Our approach has potential to quantitatively and qualitatively transform computer architecture research, enabling studies heretofore beyond our computational abilities.