Simulated annealing for mapping DSP algorithms onto multiprocessors

To solve a real-time DSP problem using a multiprocessor, one first chooses a mathematical algorithm, and then considers ways of mapping this algorithm onto multiprocessors. To date, most mappings are devised via “intuition” and “rules of thumb”. However, an alternative approach utilizing optimization techniques has shown promise. With the latter approach, it is essential to define a good cost function. The authors begin by considering the fidelity of cost functions found in the literature. Then, they propose new or modified cost functions which improve upon the old via better modeling of communication and idle time. Empirical evidence shows that the new functions provide move accurate models of the desired quantity, namely execution time. These new functions are developed through a case study of the recursive least squares problem. The authors show that with an appropriate cost function this optimization approach can generate mappings as good as published “intuitive” mappings. They conclude by applying this technique to two other problems of interest to the DSP community: full QR and radix-2 FFTs