In this paper we present BINET (BInding using NETwork flows), a heuristic for solving the binding problem which occurs in high-level synthesis of digital systems. BINET is derived from an ILP formulation by mapping the binding problem for each time step onto a network optimization problem which can be optimally solved in polynomial time. Solving a sequence of these network flow problems gives a heuristic solution to the binding problem. BINET considers floorplanning during the design process and uses this information to reduce interconnect area. By using a rip-up and re-bind approach, considerable improvements can be achieved in the quality of the RTL design. BINET produces very good solutions in the order of seconds for several benchmarks. Among several current heuristics, BINET produces designs requiring minimum wiring requirements.

BINET: an algorithm for solving the binding problem

DE LEONE, Renato
1994-01-01

Abstract

In this paper we present BINET (BInding using NETwork flows), a heuristic for solving the binding problem which occurs in high-level synthesis of digital systems. BINET is derived from an ILP formulation by mapping the binding problem for each time step onto a network optimization problem which can be optimally solved in polynomial time. Solving a sequence of these network flow problems gives a heuristic solution to the binding problem. BINET considers floorplanning during the design process and uses this information to reduce interconnect area. By using a rip-up and re-bind approach, considerable improvements can be achieved in the quality of the RTL design. BINET produces very good solutions in the order of seconds for several benchmarks. Among several current heuristics, BINET produces designs requiring minimum wiring requirements.
1994
0818649909
Computational complexity, Computer systems, Conformal mapping, Electric network synthesis, Electric wiring, Heuristic methods, Integrated circuit layout, Linear programming, Multiplexing equipment, Optimization, Polynomials, Shift registers; Binding problem, Binding wing network flows, Data flow graph, Floorplanning, High level synthesis, Integer linear programming, Network optimization problem, Polynomial time, Register transfer level, Registers; Algorithms
273
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/241392
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact