MIC 2007: The Seventh Metaheuristics International Conference 0095-1 Min-Cost electronic design using tabu search

The High-Level Synthesis (HLS) problem consists in transforming a source code (e.g. in the C or VHDL language) so that an electronic component can execute it as many times as required. Our goal is to help the decision maker to design a FPGA (field programmable gate array). This will be done by the use of specific libraries that combine logic programmable components into basic operators (adders, multipliers, etc). A complete introduction to HLS can be found in [1]. GAUT [2] is such a HLS platform and a major algorithmic phase transforms the source code into a large graph of basic operations. The input is a set of operations (tasks) that have to be scheduled on different resources. For each task j, a duration pj, a release date rj, a due date dj, a specific type of resource tj and a set of preceding tasks are considered. An unlimited set of resources is available to solve the problem. Two kinds of resources can be considered: the single purpose resources that are only of one type (typically adders and multipliers), and the multi-purpose resources (ALU for example). For each kind of resources a specific cost is given. We denote by sj the starting time of the job j. Job j cannot start before its release date (sj ≥ rj) and is completed before its due date (sj + pj ≤ dj). 2 Proposed methodology Based on previous work [3], we have extended the approach to deal with new features like precedence constraints, multi-purpose resources and resource costs