Automated processor specification and task allocation methods for embedded multicomputer systems.

摘要

This thesis considers the design problems of processor specification and task allocation for embedded multicomputer systems. Although these problems have traditionally been solved sequentially, since they are mutually constrained, coupled problems concurrent solution techniques are investigated. A concurrent formulation of the problems is defined which is proven to be NP-hard, and the size of the design space is shown to grow astronomically with problem size. Hence, heuristic solution techniques are required.; Two novel representations are proposed for the coupled design problems. The first is based on a packing paradigm, which is shown to be a generalization of the vector packing problem, while the second is based on graph partitioning. Algorithms based on these problem representations were proposed and developed, and they can be sorted into two broad categories: (1) Fast heuristic algorithms; (2) Heuristic search algorithms. The fast heuristic algorithms employ custom design advisor, packing and shrink-wrapping heuristics. The heuristic search algorithms incorporate adaptations of the Kernighan and Lin bipartitioning heuristic, simulated annealing and custom coalescing heuristics.; The algorithms were evaluated on a suite of real and synthetic test cases with respect to two figures of merit: hardware cost and run time. The real test cases are based on commercially developed automotive applications while the synthetic test cases represent a mix of hand- and automatically-generated examples that span a large portion of the design space. The results indicate that the proposed algorithms provide effective, concurrent solutions to the coupled design problems while exhibiting a range of trade-offs between solution quality and run time which has been quantified.