Allocation algorithms based on path analysis

Abstract

Although allocation in high-level synthesis is a relatively well understood topic, little has been written about the details of the actual hardware generation. This paper presents a general approach for allocation using path analysis, which handles complex schedules involving arbitrary loops and conditionals, and also mutually exclusive registers and functional units. Allocation for path-based As-Fast-As-Possible scheduling, which includes initial allocation, global optimizations and generation of control signals, is described in detail. Novel problems in register, interconnection and control generation, for designs that rely partially on combinational logic control within each cycle, are discussed. The use of Binary Decision Diagrams, with different variable orderings, for computation of control signals, is explained. Results for several benchmark examples are presented. © 1992.