This thesis describes an approach to designing the control part of digital systems, beginning with a register-transfer level description of the data paths and control flow, and ending with a specification of optimized hardware that implements the desired function. The demand for such design aids is driven by the ever-increasing complexity of integrated circuits; the limiting design constraint is no longer packing density. Instead it is design time. The problem of building controllers, which we call "Control Allocation," spans a range of eight problems from interpreting the semantics of control primitives to optimizing the parallelism of the controller implementation. Details of these eight problems are given in the thesis, and an approach is presented which includes a solution to each of them. This approach uses high-level-language programming of large software products as a model, providing for hierarchical, modular design. To support this approach, we describe a control graph to represent the control flow information, new semantics to represent module control information, and "sets" of control signals that support a unique and elegant optimization technique. Five different optimization techniques are described. To evaluate the effectiveness of these techniques, they were applied to a large example design and they produced results that came within 14% of an equivalent portion of a commercial version of the same.;*This work was supported partially by an IBM Fellowship, partially by Bell Laboratories' Graduate Tuition Reimbursement Program, and partially by the Army Research Office, under grant number DAAG 29-78-G-0070.;machine. An analysis of worst-case performance demonstrates that the algorithmic complexity is low.
展开▼
