Modern high performance processors employ advanced techniques for thermal management, which rely on accurate readings of on-die thermal sensors. As the importance of thermal effects on reliability and performance of integrated circuits increases careful planning and embedding of thermal monitoring mechanisms into these systems will be crucial. Systematic tools for analysis of thermal behavior and determination of best allocation and placement of thermal sensing elements is therefore a highly relevant problem. In this paper, we propose novel optimization techniques for determining the optimal locations and allocations for thermal sensors to provide a high fidelity thermal profile of a complex microprocessor system. Our algorithm identifies an optimal physical location for each sensor such that the sensor's the attraction towards steep thermal gradient is maximized. We also present a hybrid allocation and placement strategy showing the trade-offs associated with number of sensors used and expected accuracy. Our results show that our tool is able to create a sensor distribution for a given microprocessor architecture providing thermal measurements with maximum error of 3.18°C and average maximum error of 1.63°C across a wide set of applications.