Power consumption is an important concern for future billion transistor designs. This paper proposes a novel technique for optimizing the power consumption of chip-multiprocessors (CMPs) using an integrated hardware-software mechanism. By using a high level synchronization construct, called the barrier, our technique tracks the idle times spent by a processor waiting for other processors to get to the same point in the program. Using this knowledge, the frequency of the processors can be modulated to reduce/eliminate these idle times, thus providing power savings without compromising on performance. Using real applications from the SpecOMP suite, and a complete system CMP simulator, we demonstrate that this approach can provide as much as 40% power savings (and 32% on the average across five applications) with little impact on performance.