An algorithm for synthesis of large timeconstrained heterogeneous adaptive systems

Nagaraj Shenoy*, Alok Choudhary, Prithviraj Banerjee

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Large time-constrained applications are highly computer-intensive and are often implemented as a complex organization of pipelined data parallel tasks on a pool of embedded processors, DSP processors, and FPGAs. The large number 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 throughput requirements; (3) resource selection and allocation, keeping the processing requirements and the timing constraints in view; (4) scheduling the resources across the tasks to ensure maximum utilization; and (5) hiding the reconfiguration delays of the FPGAs. While the use of MILP techniques helps in getting high-quality results, combining them with heuristics ensures acceptable synthesis times, striking a good balance between quality of results and synthesis time. Our experimental evaluation of the algorithm shows an average 40% in resource cost reduction (compared to manual synthesis) with synthesis times from minutes to as low as a few seconds in some cases.

Original languageEnglish (US)
Pages (from-to)207-225
Number of pages19
JournalACM Transactions on Design Automation of Electronic Systems
Issue number2
StatePublished - 2001


  • Algorithm
  • Delay/cost table
  • Design
  • Experimentation
  • Hierarchical control data-flow graph
  • List scheduling
  • Mixed integer linear programming
  • Pipelining
  • Reconfigurable computing
  • Timeconstrained synthesis

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'An algorithm for synthesis of large timeconstrained heterogeneous adaptive systems'. Together they form a unique fingerprint.

Cite this