Abstract
This thesis presents an automatic partitioning methodology included in a broader methodology oriented to the development of data flow dominated embedded systems. It is described the partitioning problem, which depends on the target architecture and is considered a crucial task to implement a system with software and several hardware components.
The thesis starts with a survey of the more relevant meta-models used with embedded systems, to justify the option for PSM to describe the systems at the interface between the partitioning task and the remaining development methodology. A new meta-model, PSMfg, was developed as an internal way to describe the systems during the partitioning process.
A target architecture is presented, based on two types of reconfigurable devices (FPGAs and CPLDs): the EDgAR-2. The prototype system contains an EDgAR-2 platform connected to a PC host system. EDgAR-2 was built to support the proposed partitioning methodology.
The developed partitioning methodology includes a constructive partitioning algorithm and its closeness function, an iterative partitioning algorithm and its cost function and the metrics estimators. The constructive partitioning algorithm generates an initial solution that iterative algorithm tries to successively improve.
A literature review on partitioning algorithms suggested the adoption of the cluster growth constructive algorithm and the tabu search iterative algorithm, as the base foundation for the proposed methodology.
The process of creating partitioning solutions with cluster growth constructive algorithm, the applied closeness function and the estimation of the metrics required by this function are presented.
Tailoring the tabu search algorithm to the presented partitioning problem is detailed, with an emphasis on the implementation of the tabus, the tabu list, the visited solutions memory, the partial neighbourhood search, the aspiration criteria and the techniques that reinforce the convergence to the optimum solution and the escape from local minima of the cost function. The cost function applied by the tabu search algorithm depends on a set of metrics and on the constraints or requirements associated with these metrics.
To estimate the metrics whose cost function depends on, a software model for the processor, a hardware model for the FPGAs and CPLDs and a communication model for the interconnection resources were defined. To reduce the estimation time while providing a high degree of precision, the estimation process is incremental and it is performed at two abstraction levels: (i) at the higher abstraction level, one estimates the hardware partitions data path and control unit area and the system performance and (ii) at the lower abstraction level, one estimates values for the system model objects metrics.
The validation of the partitioning methodology was carried out through two examples: the convolution of an image and a cryptography algorithm. The quality of the automatically generated partitioning solutions, the precision and fidelity of the estimations, the performance of the developed tool and its support to implement the partitioning solutions were evaluated with promising results.
Keywords: partitioning methodology, metrics estimation, hardware/software co-design, digital embedded systems, tabu search algorithm, cluster growth algorithm, PSM meta-model, PSMfg meta-model, FPGA, CPLD, reconfigurable target architecture.
Copyright © 2001, António J A Esteves.
Last updated: 15 July 2001