Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-02-17
2001-01-23
Teska, Kevin J. (Department: 2763)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
C716S030000, C716S030000, C716S030000, C703S013000, C703S014000
Reexamination Certificate
active
06178542
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the design of real-time distributed embedded systems, and, in particular, to the process of partitioning an embedded system specification into hardware and software modules using hardware-software co-synthesis.
2. Description of the Related Art
Many embedded systems employ heterogeneous distributed architectures on which a large number of tasks are run concurrently. Such architectures consist of several general-purpose processors and application-specific integrated circuits (ASICs) of different types interconnected by various communication links. Each of the embedded system tasks can be performed by a number of hardware and software platforms which have different dollar costs. For example: 1) a telecom protocol handling function can be implemented on a general-purpose processor (software) or an ASIC (hardware), 2) an information packet (control or communication data) can be transferred via a point-to-point link, bus, or a local area network (LAN). Each option has varying delay, area, and power requirements. Architecture definition of an embedded system requires simultaneous synthesis of the hardware and software architectures which is usually referred to as hardware-software co-synthesis.
Finding an optimal hardware-software architecture entails selection of processors, ASICs, and communication links such that the cost of the architecture is minimum and all real-time constraints are met. Hardware-software co-synthesis involves various steps such as allocation, scheduling, and performance estimation. The allocation step determines the mapping of tasks to processing elements (PEs) and inter-task communications to communication links. The scheduling step determines the sequencing of tasks mapped to a PE and sequencing of communications on a link. The performance estimation step estimates the finish time of each task and determines the overall quality of the architecture in terms of its dollar cost, ability to meet its real-time constraints, power consumption, and fault tolerance, etc. Both allocation and scheduling are known to be NP-complete. See Reference (1). Therefore, optimal co-synthesis is computationally a very hard problem.
Many embedded systems are characterized by both aperiodic and periodic tasks. Examples of such systems are: flight control systems, telecom systems, command and control systems, process control systems, automobile control systems, space shuttle avionics systems, and defense control systems. Periodic tasks arrive at regular intervals. Aperiodic tasks have random arrival times. Periodic task graphs generally have hard real-time constraints, whereas aperiodic task graphs can have either hard or soft real-time constraints. Many researchers have addressed co-synthesis of periodic task graphs. Also, there exists a large amount of literature on scheduling of aperiodic tasks for a given architecture which either minimizes the probability of failure to complete an aperiodic task by its hard deadline or minimizes its response time.
Hardware-Software Co-Synthesis
Researchers have primarily focused their interest in the last several years on hardware-software partitioning, a major sub-problem in co-synthesis (see References (3)-(11)) where target embedded systems have one-CPU-one-ASIC architectures. In these approaches: 1) attempts have been made to move operations from hardware to software or vice versa to minimize cost and meet deadlines, and 2) the issue of fine-grain and coarse-grain granularity has been addressed during partitioning of embedded system specifications. Co-design frameworks for co-specification and co-simulation have been described in References (12)-(19) where hardware/software partitioning is performed manually. These systems provide an integrated environment to manage both hardware and software in co-design projects. In the area of distributed system co-synthesis, the target architecture can employ multiple processors, ASICs, and field-programmable gate arrays (IPGAs). See Reference (20). Two distinct approaches have been used to solve the distributed system co-synthesis problem: optimal and heuristic. In the optimal domain, the approaches are: 1) mixed integer linear programming (MILP) (see Reference (21)), and 2) exhaustive. See Reference (22). These are applicable to only small co-synthesis problem instances. There are two distinct approaches in the heuristic domain: 1) iterative (see References (23)-(24)), and 2) constructive. See References (2) and (25)-(26).
None of the above co-synthesis algorithms support co-synthesis of aperiodic task graphs with hard real-time constraints which are found in many embedded systems.
Scheduling Techniques for Aperiodic Tasks
There is a vast amount of literature in the area of scheduling of soft and hard aperiodic tasks (see References (27)-(40)) for a given architecture. A survey of scheduling techniques is provided in Reference (27). These techniques address only scheduling, and not co-synthesis. There are two possible approaches for scheduling of aperiodic tasks: 1) static scheduling where the schedule is defined a priori, and 2) dynamic (also referred to as “on-line”) where the decision regarding execution of aperiodic tasks is made on-line. Static scheduling is generally used for periodic task graphs. In case of aperiodic tasks, though static scheduling requires some up front knowledge of the tasks, it has less computational overhead. Aperiodic task graphs can be soft or hard. Soft aperiodic task graphs do not have fixed deadlines. Algorithms proposed for scheduling aperiodic tasks in References (28)-(40) are based on the dynamic scheduling paradigm. These approaches either minimize the probability of not meeting the deadline during allocation of tasks on a given architecture or minimize the response times. Although a dynamic approach does not require prior knowledge of task characteristics, it suffers from the following inherent disadvantages: 1) it incurs a computational overhead in determining the most suitable PE to allocate an aperiodic task to, such that the aperiodic task deadline can be met, 2) it incurs an additional delay in transferring the aperiodic task to another PE in the event a deadline cannot be shown to be met for the aperiodic task on the PE it first arrived at, and 3) it cannot give a guarantee that deadlines will always be met. In References (28)-(34), techniques are presented to handle dynamic scheduling of soft and hard aperiodic tasks for uniprocessor systems based on the concept of slack stealing from the existing schedule of periodic tasks. Their limitations are: 1) they ignore precedence among tasks, i.e. the inter-task communications, and 2) they cannot handle simultaneous scheduling of aperiodic and periodic tasks. In References (35)-(38), dynamic scheduling of aperiodic tasks is considered for homogeneous multiprocessor systems. However, these techniques too do not take inter-task communication into consideration. In Reference (39), dynamic scheduling of aperiodic task graphs with precedence constraints is considered, however, inter-task communication scheduling is ignored and the target architecture is restricted to a set of homogenous processors. In Reference (40), deadline assignment for tasks of an aperiodic task graph is considered for dynamic scheduling. Both static and dynamic approaches can employ either preemptive or non-preemptive scheduling. Though a preemptive scheduler may provide efficient schedules and utilization of resources, non-preemptive scheduling algorithms are sometimes preferred for the following reasons: 1) in many practical real-time I/O systems, properties of hardware and software either make preemption prohibitively expensive or impossible, and 2) the overhead associated with a preemptive algorithm is more difficult to characterize and predict than that of a non-preemptive algorithm.
The problem of scheduling hard real-time aperiodic task graphs without the above-mentioned restrictive assumptions has not been considered for distributed heterogeneous syst
Lucent Technologies - Inc.
Mendelsohn Steve
Sergent Douglas W.
Teska Kevin J.
LandOfFree
Hardware-software co-synthesis of embedded system... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Hardware-software co-synthesis of embedded system..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hardware-software co-synthesis of embedded system... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441640