Given a collection of recurring tasks or processes that comprise the software for an embedded system, and a number of different types of available processing units, the minimum cost synthesis problem is concerned with obtaining an implementation of the embedded system upon a multiprocessor platform comprised of processing units from among the available types, such that the total cost of the platform is minimized. It is shown that this problem is intractable (NP-hard in the strong sense). Approximation algorithms are presented that guarantee to obtain implementations with cost no more than a constant amount greater than twice the cost of an optimal implementation.