System-level synthesis of application specific systems using A* search and generalized force-directed heuristics

Abstract

This paper presents a system-level approach to the synthesis of multi-task, hard real-time applications. The goal is to select a set of off-the-shelf processors with minimal cost while satisfying timing constraints. Our approach has three design phases: resource allocation, assignment, and scheduling. With the observation that the resource allocation is a search for a set of processors which requires the minimum cost, we adopted A* search based technique. For assignment we use a variation of the force-directed technique. Final task scheduling is based on the Earliest Deadline First (EDF) algorithm. Experimental results show that this approach is highly effective on a variety of examples.