An algorithm for synthesis of large time-constrained heterogeneous adaptive systems

Large time-constrained applications are highly computer-intensive and are o ften implemented as a complex organization of pipelined data parallel tasks on a pool of embedded processors, DSP processors, and FPGAs. The large num ber of design alternatives available at each task level, the application as a whole, and the special needs of the reconfigurable devices (such as the FPGA) make the manual synthesis of such systems very tedious. The automatic synthesis algorithm in this paper combines exact (MILP-based) and heuristic techniques to solve this problem, which basically involves ( 1) propagation of timing constraints; (2) pipelining the loops to meet thro ughput requirements; (3) resource selection and allocation, keeping the pro cessing requirements and the timing constraints in view; (4) scheduling the resources across the tasks to ensure maximum utilization; and (5) hiding t he reconfiguration delays of the FPGAs. While the use of MILP techniques helps in getting high-quality results, com bining them with heuristics ensures acceptable synthesis times, striking a good balance between quality of results and synthesis time. Our experimenta l evaluation of the algorithm shows an average 40% in resource cost reducti on (compared to manual synthesis) with synthesis times from minutes to as l ow as a few seconds in some cases.