Reconfigurable hardware accelerators (RAs) have become a frequent choice in embedded systems design to meet the performance demand of current embedded applications. However, answering when the combination of general purpose processors (GPPs) and RAs can provide the expected performance at the additional area and energy cost demands an extensive design space exploration. In this scenario when varying microarchitectural characteristics of both GPPs and RAs, one can easily reach million combinations. Evaluating one of these solutions through hardware synthesis is an extremely costly task. And even the use of high-level simulation tools as alternative does not allow simulating all solutions and meeting time-to-market. In this work, we propose the use of predictive models based on machine learning algorithms to simplify and speed up the design space exploration process of GPPs with RAs. In our case study we combine a superscalar processor and a Coarse-Grained Reconfigurable Architecture. Additionally, considering the accuracy of the prediction, we investigate ten different algorithms by comparing their error prediction rate. In this investigation, we were able to achieve an error prediction rate bellow 2% on average and reduce the time for exploring the design space up to 33× when comparing with a scenario that uses a high-level simulation tool.