Article Preview
Top1. Introduction
In the last years, Real Time Embedded Systems (RTES) are becoming omnipresent (Kasim Al-Aubidy, 2011; Kopetz, 2011; Shaw, 2001). This new technology is very attached to our daily life and can be nearly found in all domains such as transport, house electro manager, consumable electronics, games, Telecommunication, multimedia, aerospace, military, etc. RTES are reactive systems with sensors/actuators tailored to execute specific tasks that can be periodic, Aperiodic or sporadic. These tasks can be subjected to a variety of temporal constraints. The most important one is may be the deadline. In fact, RTES are classed to hard, soft or firm systems. This taxonomy depends on the deadline respect or not and its impact on the environment. RTES design faces a big challenge and must minimize the overall cost and the power consumption.
The design flow of such systems consists in several sequential or iterative steps starting from functional/non-functional requirements specification to hardware (technology dependent) implementation. The latter can be realized with ASICs, FPGA, DSP or general-purpose embedded processors connected with a shared bus, buses hierarchy with fast links or a communication network (NOC: Network On Chip) to satisfy high performance. In this context, we are interested in high level performance estimation and optimization of RTES with periodic/aperiodic tasks and hard/soft constraints targeting multiprocessors architecture. Here, we must note some differences between traditional multiprocessor architecture and RTES multiprocessor architecture. Firstly, RTES architecture is based on distributed memory and not shared memory. Secondly, RTES architecture includes generally an RTOS (Real Time Operating System) implemented as a kernel without conventional files, complex I/O or memory management mechanisms (like pagination). RTOS is focused on Real Time Scheduling (Andersson et al., 2000; Anderson et al., 2005; Chéramy et al., 2012; Lalatendu et al., 2012; Zhang et al., 2012). An important difference is at the microprocessor level. Embedded processor is characterized by low clock frequency, low memory capacity and low power consumption. An embedded processor may change its frequency dynamically due to the DVS (Dynamic Voltage Scaling) strategy. DVS enables designers to compromise between tasks deadlines and power consumption.
As it has been known, the scheduling problem is NP-hard. This problem can be resolved using meta-heuristics. A meta-heuristic is applied on a vast class of problems with imprecise or incomplete data.
GAs appear a good choice for solving complex, non-linear, multi-objective and multi-modal problems that is the case in RTES. We can for instance optimize many objectives like response time, power consumption, the processor usage ratio, etc. However conventional genetic algorithms may consume much time to find good solutions. For this reason, a new class of genetic algorithms inspired from the quantum mechanics called Quantum Inspired Genetic Algorithms (QIGA) has been developed (Grover, 1996; Han, 2000; Laboudi et al., 2012; Layeb et al., 2007; Shor, 1994). These algorithms try to simulate some quantum principles found in mechanics such as state superposition to reduce the research time for good solutions. Our effective contributions reside in the proposition of a mix RTES model that integrates periodic and Aperiodic tasks with hard and soft constraints and to apply QIGA to minimize tasks mean response time and the number of tasks missing their deadlines on a multiprocessor architecture under the idea of balancing between processors usages ratios. Our proposed approach takes advantage of both static and dynamic preemptive scheduling. In fact, and in order to compare the performance of QIGA with conventional GAs (CGA), we have implemented four techniques called SCGA (Static Conventional Genetic Algorithm), DCGA (Dynamic Conventional Genetic Algorithm), SQIGA (Static Quantum Inspired Genetic Algorithm) and DQIGA (Dynamic Quantum Inspired Genetic Algorithm).