سنتزهای مشترک سخت افزار و نرم افزار سیستم های بی درنگ سخت با تنظیم مجدد FPGA ها

Real-time systems cover a wide application domain. This paper presents an efficient heuristic algorithm for enforcing the schedulability of aperiodic hard real-time tasks arriving simultaneously with precedence constraints and individual deadlines. The proposed co-synthesis algorithm integrates partitioning and non-preemptive scheduling. Reconfigurable FPGAs are incrementally added when schedulability suffers in a uniprocessor system. Initially, a schedule that minimizes the maximum lateness and satisfies the precedence constraints is made. If individual timing constraints are not met in this schedule, some tasks are selected and transferred to dynamically reconfigured FPGAs. The proposed algorithm was implemented and tested with a large number of task graphs with task size as high as 700 nodes. The algorithm could not only achieve schedulability but also could reduce the total completion time of the task graph. Moreover, incremental addition of reconfigurable FPGAs yielded a cost effective solution.

Hard real-time systems are characterized by strict constraints on task completion time, referred to as deadline. In such systems, which are found in flight control, telecom, defense control, nuclear power plants, automotive electronics and process control etc., missing the deadline may lead to catastrophic sequences. If software implementation of the tasks cannot fulfill the timing requirement of the real-time system, concurrent execution of part of the tasks by hardware components can be used to remedy this problem. An embedded system is composed of hardware (HW) and software (SW) computing components executing concurrently and cooperatively in order to benefit from the strength of each technology. The software component consists of one or more general purpose programmable processors, while the Field Programmable Gate Arrays (FPGAs) or the Application Specific Integrated Circuits (ASICs) are the hardware components. In the last decade, a systematic system design approach referred to as HW/SW co-design has been receiving a great attention in the research community. It is only recently that some attention has been given to the co-design of embedded real-time systems [3], [8] and [9]. Moreover, timing constraints are well defined in real-time systems which make them more suitable for HW/SW co-design. The co-design process includes three main activities, namely, (1) allocation of appropriate electronic components such as processors, FPGAs/ASICs, buses, memory etc., (2) partitioning the task set to be implemented among software and hardware component, and (3) scheduling the tasks on the electronic components [1] and [2]. Due to recent improvements which contributed to lower prices, higher gate counts and reconfiguration speed, embedded systems with dynamically reconfigurable FPGAs have become a reality, which provides a great deal of functional flexibility and execution speed [12]. Most of the existing approaches perform partitioning and scheduling in two separate steps. The tasks are first partitioned and then scheduling is performed to check the feasibility and the performance of the system. Integer programming, greedy heuristics and graph partitioning have been used to solve the partitioning problem in single CPU systems [3], [4], [5] and [6]. In the last few years, developing an integrated approach which combines scheduling and partitioning became an active area of research [7], [8], [9], [16], [18] and [19]. In this approach, tasks are initially assumed to be implemented in software and then selected tasks are moved from software to hardware until the specified constraints are met. The scheduling algorithms which determine the order in which the tasks are executed are classified based on the assumptions made on the system and on the tasks. Liu and Wong [7] used the integrated approach for partitioning and scheduling tasks with precedence constraint and uniform execution time. Two homogeneous CPUs and k hardware components were used to achieve reduction in completion time and hardware cost. Shin and Chico [9] reduced the execution time of tasks by assigning part or whole of the task from software to a coprocessor which is a hardware implementation of code segments of tasks. For optimal partitioning and comparing different target architectures, schedulability measurement was used as the criteria by Axelsson [8]. In both approaches [8] and [9], initial scheduling in software is done by rate monotonic scheduling algorithm, which is optimal for the class of tasks which are independent and periodic, where task dependency is not a criterion. HW/SW co-synthesis with FPGAs as the hardware component has been gaining attention of researchers [11], [13], [18] and [19]. Dick and Jha [13] introduced dynamically configurable FPGAs for HW/SW co-synthesis with an overall objective of achieving low cost systems. Jeong et al. [11], Noguera and Badia [19] have implemented co-design in systems where single processor and only one dynamically programmable FPGA were used. In this paper, tasks are assumed to be non-periodic with task dependency referred to as precedence constraint. It is also assumed that each task has its individual deadline constraint. For a set of tasks with precedence relations, finding an optimal schedule is in general NP-hard. Under particular assumptions on the tasks, namely tasks with simultaneous arrival time, it is possible to solve the problem in polynomial time [15]. The architecture for the co-design in this work is shown in Fig. 1. It consists of one SW processor, multiple FPGAs, a single independent controller for all the FPGAs, local memory for the controller, and shared memory for HW-SW communication. The SW processor can execute one task at a time and the controller can configure one FPGA at a time. The required configuration is stored in the local memory and is loaded by the controller when the FPGA is ready to accept it.Hard real-time tasks are initially scheduled on the uniprocessor in such a way as to reduce a cost function referred to as maximum lateness, which is defined in Section 2. It is assumed that a running task is never interrupted (non-preemptive scheduling). The schedulability of tasks missing their deadline is enforced by moving selected tasks, one after another, to dynamically reconfigurable FPGAs that are added to the system when needed. FPGA reconfiguration for each selected task is done by the controller. The tasks are assigned in such a way as to utilize HW/SW components effectively. We could achieve the schedulability of the task set and also a reduction in the total completion time of the task set. To the best of our knowledge, enforcing non-preemptive schedulability of aperiodic tasks with precedence and deadline constraints has not been considered using co-design technique in a uniprocessor system with multiple reconfigurable FPGAs added incrementally to achieve a cost effective solution. The remaining paper is organized in the following manner. The prelude in Section 2 discusses some of the terminology used in this paper. Section 3 explains the scheduling algorithm. Section 4 presents the experimental results and finally Section 5 concludes the paper.

A heuristic algorithm for enforcing schedulability of aperiodic tasks in hard real-time system using HW/SW co-design is presented. As the ultimate goal of this work is to achieve schedulability by adding hardware components, minimization of maximum lateness was taken as the prime metric for performance evaluation and the optimal LDF scheduling technique was used initially to schedule the tasks. Partitioning and scheduling tasks in an integrated manner among the reconfigurable FPGAs and the uniprocessor lead to successful execution of tasks within their deadlines. Using a single controller for reconfiguring all the FPGAs delayed the starting of task execution in HW components. Experiments conducted with large number of task graphs demonstrated the ability of the proposed algorithm to enforce task schedulability and meet precedence and deadline constraints. Future work will be directed towards handling task graphs with communication costs and concurrent execution of tasks on the same FPGA.