| This thesis presents a genetic algorithm (GA) to place circuit components on to an array of reconfigurable algorithmic logic units (ALUs), known as datapath units (DPUs). Word-oriented reconfigurable arrays are relatively new, and design flows for them are still developing. One of the challenges of such "coarse grain" arrays is the lesser flexibility with which their resources can be arranged and recruited. Placement methodologies for application-specific integrated circuits (ASICs) and bit-wise "fine grain" arrays are not directly applicable. The greater predefined structure in a coarse grain array results in placement restrictions on some components.; In the array used in this thesis, the coarse granularity resulted in such a high level of abstraction that it was not necessary to separate placement and routing. The routing was simple enough that routability could be accurately determined by the placement GA. Hence, the GA could simultaneously deal with placement, routing, and heterogeneous position constraints. The flexibility in formulating problems for a GA lent itself very well to a multifaceted approach to enforcing the various architecturally imposed constraints.; A comprehensive design case was undertaken to establish the difficulties which automated placement has to deal with. In addition to developing the GA and partially designing the test suite of circuits for its characterization, a preliminary analysis was made of evolutionary approaches to circuit synthesis for coarse grain reconfigurable arrays. |
