We present efficient power estimation techniques for hardware-software (HW-SW) system-on-chip (SoC) designs. Our techniques are based on concurrent and synchronized execution of multiple power estimators that analyze different parts of the SoC (we refer to this as coestimation), driven by a system-level simulation master. We motivate the need for power coestimation, and demonstrate that performing independent power estimation for the various system components can lead to significant errors in the power estimates, especially for control-intensive and reactive-embedded systems. We observe that the computation time for performing power coestimation is dominated by: i) the requirement to analyze/simulate some parts of the system at lower levels of abstraction in order to obtain accurate estimates of timing and switching activity information and ii) the need to communicate between and synchronize the various simulators. Thus, a naive implementation of power coestimation may be too inefficient to be used in an iterative design exploration framework. To address this issue, we present several acceleration (speed-up) techniques for power coestimation. The acceleration techniques are energy caching, software power macro-modeling, and statistical sampling. Our speed-up techniques reduce the workload of the power estimators for the individual SoC components, as well as their communication/synchronization overhead. Experimental results indicate that the use of the proposed acceleration techniques results in significant (8/spl times/ to 87/spl times/) speed-ups in SOC power estimation time, with minimal impact on accuracy. We also show the utility of our coestimation tool to explore system-level power tradeoffs for a TCP/IP check-sum engine subsystem.