Due to the ever-escalating power consumption, a significant proportion of the future many-core chips is mandatory to be switched off to meet the power budgets. This trend has brought up a paradigm shift from conventional low-power to power budgeting designs, where performance optimization needs to be performed under a tight power budget constraint. There are two key issues to be considered when moving this new design paradigm forward. Firstly, with per-core frequency scaling, the number of frequency combinations of the cores grows exponentially. As more cores are integrated onto a chip, it becomes more challenging to achieve the optimal performance over a given power budget. Secondly, the power budgets of many-core system might undergo a rapid fluctuation. Consequently, the power budgeting scheme needs to be prompt to make appropriate changes to track such power budget variation. This paper is aiming at resolving the problem of optimizing overall performance over a power budget using frequency scaling technique. To solve the problem efficiently at runtime, we propose a parallel dynamic programming network, in which the Pareto-optimal solutions can be obtained using linear time complexity. Experimental results have confirmed that the proposed approach can reduce the execution time by 45% when compared to other existing methods. The runtime overhead and hardware cost of the proposed approach are reasonably small, such as the average area and power consumption are less than 1% of the whole network-on-chip. This paper demonstrates an effective formulation for delivering Pareto-optimal solutions for power budgeting in future many-core systems.