Cloud computing has drawn increasing attention from the scientific computing community due to its ease of use, elasticity, and relatively low cost. Because a high-performance computing (HPC) application is usually resource demanding, without careful planning, it can incur a high monetary expense even in Cloud. We design a tool called CAP3 (Cloud Auto-Provisioning framework for Parallel Processing) to help a user minimize the expense of running an HPC application in Cloud, while meeting the user-specified job deadline. Given an HPC application, CAP3 automatically profiles the application, builds a model to predict its performance, and infers a proper cluster size that can finish the job within its deadline while minimizing the total cost. To further reduce the cost, CAP3 intelligently chooses the Cloud's reliable on-demand instances or low-cost spot instances, depending on whether the remaining time is tight in meeting the application's deadline. Experiments on Amazon EC2 show that the execution strategy given by CAP3 is cost-effective, by choosing a proper cluster size and a proper instance type (on-demand or spot). © 2013 IEEE.