# E-Token Energy-Aware Proportionate Sharing Scheduling Algorithm for Multiprocessor Systems

Authors: Pasupuleti Ramesh; Uppu Ramachandraiah
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

WSN plays vital role from small range healthcare surveillance systems to largescale environmental monitoring. Its design for energy constrained applications is a challenging issue. Sensors in WSNs are projected to run separately for longer periods. It is of excessive cost to substitute exhausted batteries which is not even possible in antagonistic situations. Multiprocessors are used in WSNs for high performance scientific computing, where each processor is assigned the same or different workload. When the computational demands of the system increase then the energy efficient approaches play an important role to increase system lifetime. Energy efficiency is commonly carried out by using proportionate fair scheduler. This introduces abnormal overloading effect. In order to overcome the existing problems E-token Energy-Aware Proportionate Sharing (EEAPS) scheduling is proposed here. The power consumption for each thread/task is calculated and the tasks are allotted to the multiple processors through the auctioning mechanism. The algorithm is simulated by using the real-time simulator (RTSIM) and the results are tested.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are used for healthcare systems, Supervisory Control and Data Acquisition (SCADA) systems, smart grids, agriculture and environment monitoring, public safety, and military systems. Sensors in WSNs are predictable to run unconventionally for a longer period of time in order to increase the network lifetime. It is not possible always to manually reload the jots due to the conservation cost and unapproachability. In WSN’s multicore or multiprocessor architectures emerging advancements are focused on making them more effective in processing different tasks without any deadline missing. These architectures may be homogeneous or heterogeneous and must be effective in the aspects like size, processing speed, power consumption, and so forth. The response of the real-time system for different incoming resources at different time intervals is the major obligation for an efficient and effective system. Generally, in multiprocessor architecture scheduling is decided based on the system applications, types of inputs, type of the processor and response of the system, and so on. Based on these parameters a new scheduling algorithm is proposed here. It is flexible and compatible with different tasks. In this scheduling the energy efficiency is achieved through the task allocation based on its energy consumption. As per the sorting mechanism the task allocation is done with advantage of less energy consumption compared to the other techniques.This paper is ordered as follows: in the subsequent section, we presented the contemporary prevailing scheduling schemes. In Section3, we recommend EEAPS algorithm. In Section 4, we originate the hardware details of multiprocessor systems and Section 5 deliberates real-time simulator model. In Section 6, we analyze the EEAPS power and energy graphs for different threads. Lastly, Section 7 concludes this paper.


## 2. Related Works

Anastasi et al. present energy-preservation structures in wireless sensor networks [1]. Here the writers concentrated on duty cycle and data-saving methods. Contemporary reviews reveal that numerous methods are projected for energy effectiveness like Energy-Aware routing protocols [2], data accumulation systems [3, 4], and energy gathering tactics [5]. A scheduling algorithm combining the energy efficiency and the performance for proportional-share scheduling of threads in a heterogeneous processor is developed in [6]. An optimal scheduling algorithm for uniprocessors is real-time static voltage and frequency scaling is projected in [7]. Tasks models with both fixed and migrating tasks are considered with the existence of fair scheduling proved in [8]. Both the tasks are scheduled differently between the resources at several times. A periodic schedule is produced by the fair scheduler. Here, each task is allocated to a time which is the same as its period [9]. Through a static analysis and runtime scheduling, the proposed scheduling maps the program to the best fit processor which is designed based on the program phases in [10]. Here it is showed that the energy efficiency for the phase based scheduling is achieved by comparing this against the statical mapping and the periodic sampling. To synthesize multiprocessor implementations of hard real-time system with independent periodic tasks many algorithms are presented in [11]. Goossens et al. present Pfair scheduler which is optimal for periodic tasks on multiprocessor systems [12]. In Pfair tasks are obviously required to make evolution at steady rates. Baruah et al. proposed two optimal Pfair schedulers named PF [13] and PD [12]. Both algorithms assign priority based on deadline. If two subtasks have the same deadline then PF compares future subtask deadlines, which is expensive technique but PD inspects four tie-break parameters. A new proof is demonstrated for the Pfair scheduling algorithm which is optimal for the sporadic tasks in multiprocessor system [14]. A hierarchical Pfair algorithm is proposed with allocation constraints in [15]. Here the amount of time by which the fixed task is missed is bounded. A task dependent job allocation for a multiprocessor system is shown in [16]. Energy characteristics analysis of parallel algorithms for scalable multiprocessor processors is evaluated by a methodology in [13] while satisfying the performance requirements. It is quite different in scalability for parallel algorithm with power and performance. Using this method, we can determine number of processors to be used to minimize energy consumption. Anderson and Srinivasan presented ER-fair and offered new algorithm called PD2. It is also called mixed Pfair or modified Pfair (Pfair-M). It is optimal for both early release and nonearly release periodic tasks [17]. Based on literature survey we understood that many of the scheduling algorithms suffer from NP-hard problem due to nonpreemption mechanism and minimization of total completion time. The two rules earliest completion time and earliest release time are heuristic algorithms, and for them accuracy bounds are unknown.


## 3. The Proposed Work

Here, we proposed an energy efficient scheduling algorithm based on preemptive mechanism called E-token Energy-Aware Proportionate Sharing (EEAPS) scheduling algorithm. For multiprocessor architecture based on homogeneous structure the processors are classified with respect to threshold energy. The task set is split into number of threads/tasks and their energy requirement is calculated. Thus to perform the task allocation among the processors based on their energy requirement, this is called auctioning mechanism. The processor power consumption is calculated prior to the tasks to decide the task allocation after their arrival. The incoming tasks/threads are analyzed with their characteristics for the application in the system. Sample EEAPS algorithm is represented in the Algorithm1.Algorithm 1:Sample EEAPS algorithm.
( 1 ) for i=1 to N do ( 2 )     for k=1 to M do ( 3 )        Calculate Power consumption of the task Pi,k=βk-γk∗Mαi+γk ( 4 )       Calculate Energy consumption of the task Eτi=Pi,k∗Ci ( 5 )       if (Eτi<Eth) then ( 6 )        Call Processor1() ( 7 )       else if (Eτi == Eth) then ( 8 )          Call Processor2() ( 9 )          else Call Processor3() ( 10 )       end if ( 11 )       end if ( 12 )       Calculate total energy consumption of the clients Eclients=∑i=1N∑k=1MPi,k∗Ci ( 13 )       end for ( 14 )  end for ( 15 )  Calculate Total Energy consumption of the System ETotal=Eserver+∑i=1N∑k=1MPi,k∗Ci


### 3.1. Task Model

The system consists of a set ofn independent and m dependent tasks Γ={τ1,τ2,…,τn}.The characteristics of each taskτi are represented as (Ci,Ti,di) and here Ci denotes task worst case execution time, Ti is the time period, and di is the dependency of the task. The energy of each task Eτi is calculated and compared with the threshold energy Eth of the system. Task (τi) allocation to the processors is defined as the function of energy and time. It is represented as(1)FτiE,t=Processor1Eτi<EthProcessor2Eτi=EthProcessor3Eτi>EthProcessor4forSporadicTasks.Here Eth is the average energy of the available processors. Periodic tasks follow fixed priority mechanism based on their periods and here task deadline Di=Ti and it allows preemption mechanism whenever high priority task arrives. Aperiodic tasks follow dynamic priority. Sporadic tasks are directly allotted to processor4 without checking the energy requirement. If two or more sporadic tasks arrive simultaneously, then priority is assigned to the sporadic tasks depending on its deadline.The total utilization of the task setUi is always within the available processor capacity (c) of the system.(2)Ui=∑i=1n+mCiTi≤c(see [18]). For the defined task set, EEAPS is feasible because it satisfies the following condition:(3)C1T1+C2T2+⋯+CNTN≤1(see [18]). Here T1,T2,…,TN are time period of the tasks and C1,C2,…,CN are task’s execution times. In order to minimize the complexity (NP-hard) of the algorithm, this work proposed competent heuristic approach. It is energy efficient and also compatible for different tasks set. This model adopts global approach for multiprocessor task allocation and scheduling based on task’s energy requirement.


### 3.2. Processor Model

The system consists ofP homogeneous k processors P1,P2,…,Pk. That means all processors have equal voltage and frequency ratings and exhibit similar computational capacities. Here we considered ARM7TDMI LPC2148 microcontrollers for implementation. It is compatible with RT-Linux and μc-Linux. Its specifications are given in Table 1.Table 1
ARM7TDMI specifications.
S. number Parameters Specification 1 Operating voltage 3.3 V 2 Current 100 mA–500 mA 3 ADC 16 channels with 10-bit resolution 4 UARTs 2


### 3.3. Energy Model

Energy (E) consumed by the processor which can be represented in terms of the power consumption (P) is(4)E=P∗t.Here “t” is the processor task execution duration. The power dissipation or consumption (P) of CMOS based processor is (5)P=Ceff∗V2∗f(see [8]). Ceff = effective load capacitance, V = supply voltage, and f = clock frequency.Thus the energy consumption is given by(6)E=Ceff∗V2∗f∗t(see [9]). The total energy consumed by k processors of CMOS system is (7)Esystem=Ceff∗∑i=1kVi2∗fi∗t(see [9]). In this model, the total energy consumption of the system is the sum of the energy consumed by the server node and client nodes.(8)Esystem=Eserver+Eclients.The power consumption of the individual thread/task for EEAPS can be computed as(9)Pi,k=βk-γk∗Mαi+γk,where β is busy power, γ is idle power, αi is computational capacity for the corresponding task τi, i is task ID, k = processor ID, M = million instructions per second for the corresponding task = (PCS∗IEPC)/106, PCS is Processor Clock Speed, and IEPC is number of instructions executed per cycle.Then the energy consumption of the task is given by(10)Eτi=Pi,k∗Ciand Ci represents task execution time.The sum of the power consumption of the tasks will give total power consumption of the clients. It can be computed as(11)Pclients=∑i=1N∑k=1MPi,k.Here M represents number of client nodes present in the system. The total energy consumption of the clients is thus calculated as (12)Eclients=∑i=1N∑k=1MPi,k∗Ci.Then the total energy consumed by the system can be computed as(13)ETotal=Eserver+∑i=1N∑k=1MPi,k∗Ci.


## 3.1. Task Model

The system consists of a set ofn independent and m dependent tasks Γ={τ1,τ2,…,τn}.The characteristics of each taskτi are represented as (Ci,Ti,di) and here Ci denotes task worst case execution time, Ti is the time period, and di is the dependency of the task. The energy of each task Eτi is calculated and compared with the threshold energy Eth of the system. Task (τi) allocation to the processors is defined as the function of energy and time. It is represented as(1)FτiE,t=Processor1Eτi<EthProcessor2Eτi=EthProcessor3Eτi>EthProcessor4forSporadicTasks.Here Eth is the average energy of the available processors. Periodic tasks follow fixed priority mechanism based on their periods and here task deadline Di=Ti and it allows preemption mechanism whenever high priority task arrives. Aperiodic tasks follow dynamic priority. Sporadic tasks are directly allotted to processor4 without checking the energy requirement. If two or more sporadic tasks arrive simultaneously, then priority is assigned to the sporadic tasks depending on its deadline.The total utilization of the task setUi is always within the available processor capacity (c) of the system.(2)Ui=∑i=1n+mCiTi≤c(see [18]). For the defined task set, EEAPS is feasible because it satisfies the following condition:(3)C1T1+C2T2+⋯+CNTN≤1(see [18]). Here T1,T2,…,TN are time period of the tasks and C1,C2,…,CN are task’s execution times. In order to minimize the complexity (NP-hard) of the algorithm, this work proposed competent heuristic approach. It is energy efficient and also compatible for different tasks set. This model adopts global approach for multiprocessor task allocation and scheduling based on task’s energy requirement.


## 3.2. Processor Model

The system consists ofP homogeneous k processors P1,P2,…,Pk. That means all processors have equal voltage and frequency ratings and exhibit similar computational capacities. Here we considered ARM7TDMI LPC2148 microcontrollers for implementation. It is compatible with RT-Linux and μc-Linux. Its specifications are given in Table 1.Table 1
ARM7TDMI specifications.
S. number Parameters Specification 1 Operating voltage 3.3 V 2 Current 100 mA–500 mA 3 ADC 16 channels with 10-bit resolution 4 UARTs 2


## 3.3. Energy Model

Energy (E) consumed by the processor which can be represented in terms of the power consumption (P) is(4)E=P∗t.Here “t” is the processor task execution duration. The power dissipation or consumption (P) of CMOS based processor is (5)P=Ceff∗V2∗f(see [8]). Ceff = effective load capacitance, V = supply voltage, and f = clock frequency.Thus the energy consumption is given by(6)E=Ceff∗V2∗f∗t(see [9]). The total energy consumed by k processors of CMOS system is (7)Esystem=Ceff∗∑i=1kVi2∗fi∗t(see [9]). In this model, the total energy consumption of the system is the sum of the energy consumed by the server node and client nodes.(8)Esystem=Eserver+Eclients.The power consumption of the individual thread/task for EEAPS can be computed as(9)Pi,k=βk-γk∗Mαi+γk,where β is busy power, γ is idle power, αi is computational capacity for the corresponding task τi, i is task ID, k = processor ID, M = million instructions per second for the corresponding task = (PCS∗IEPC)/106, PCS is Processor Clock Speed, and IEPC is number of instructions executed per cycle.Then the energy consumption of the task is given by(10)Eτi=Pi,k∗Ciand Ci represents task execution time.The sum of the power consumption of the tasks will give total power consumption of the clients. It can be computed as(11)Pclients=∑i=1N∑k=1MPi,k.Here M represents number of client nodes present in the system. The total energy consumption of the clients is thus calculated as (12)Eclients=∑i=1N∑k=1MPi,k∗Ci.Then the total energy consumed by the system can be computed as(13)ETotal=Eserver+∑i=1N∑k=1MPi,k∗Ci.


## 4. Hardware Details

It consists of four ARM7 LPC2148 microcontrollers. It follows client-server model. Processor4 itself acts as server. The server node acts as shared memory and the other three nodes act as clients. The communication between the clients is not possible in the present architecture.The real-time application of health monitoring system consisting of eight real-time tasks is considered. Server node holds the information of all tasks and it runs task allocation algorithm in order to reduce the energy consumption of the system. The client-server communication is established using ZigBee.The real-time tasks are as follows:(i)
Patient body temperature measuring task using an ADC-channel I(ii)
Motor control task to adjust room temperature with an ADC-channel II(iii)
EMG sensor task to sense the muscular activities of the patient with an ADC-channel III(iv)
ECG sensor task to sense the heart activities of the patient with an ADC-channel IV(v)
LED ON/OFF task to indicate the power availability(vi)
LCD display task to display patient health status(vii)
Power switch ON/OFF task to trigger the buzzer(viii)
Buzzer task to generate emergency signalReal-time tasks with their attributes are shown in Table 2. All tasks except task3 and task4 are periodic. These two tasks may be aperiodic or sporadic in nature depending on the patient health condition.Table 2
Task set with attributes.
Task/thread ID Execution time (Ci) Time period (Ti) Thread 1 9 msec. 20 msec. Thread 2 11.3 msec. 25 msec. Thread 3 21 msec. X Thread 4 23.5 msec. X Thread 5 6µsec. 31µsec. Thread 6 40µsec. 60µsec. Thread 7 3 msec. 9µsec. Thread 8 25µsec. 45µsec. X represents aperiodic/sporadic task.The frame format of ZigBee is shown below.Here header represents address/ID of the client. EOF indicate end of frame. ZigBee provides acknowledged transmission of data.


## 5. Real-Time Simulator

Real scheduling issues are far removed from theoretical assumptions; simulations analyse and address them. To enable the investigation of scheduling algorithm, we used an enthusiastic tool: RTSIM, a real-time scheduling simulator. It is available in open source platform and user friendly module. The main advantages of this compiler are the computational effective nature and optimization of the workload through its modules MetaSim, rtlib, ctrlib, and jtracer. Each module has its own contribution; all these things will help the user to understand, simulate, and analyze the scheduling algorithms in a better way.RTSIM is built on the MetaSim framework [19], which grants general interface for the prioritized event queue. In this simulation it is divided into ticks. It offers three key notions: processors accomplished by akernelare owed totasksby ascheduler. Here, we used modified kernel notion for multiple processors and task notion for modelling the tasks. We applied roots of the scheduler notion for our scheduling algorithms. We made comprehensive simulation of our algorithm and the outcomes are offered in the subsequent section.


## 6. Results

The proposed algorithm is simulated by using the RTSIM simulator.Table3 represents power consumption of the threads by considering processor parameters like busy power, idle power, computational capacity, number of processors, and the number of cycles per instruction into account. The graphical representation of the thread’s power consumption and their minimum and maximum power requirements are shown in Figure 1. Here the y-axis represents the power in terms of watts and x-axis represents the threads ID.Table 3
Power consumption of the threads.
Thread ID Number of cycles for instruction Power consumption in watts Max power Min power Thread 1 8 2.694 2.694 2.694 Thread 2 6 2.925 2.925 2.694 Thread 3 12 2.462 2.925 2.462 Thread 4 16 3.850 3.850 2.462 Thread 5 3 2.347 3.850 2.347 Thread 6 9 2.617 3.850 2.347 Thread 7 2 4.775 4.775 2.347 Thread 8 5 3.210 4.775 2.347Figure 1
Power analysis.The task set is simulated for the EEAPS algorithm and the energy consumption of the processor nodes is displayed in Figure2.Figure 2
Energy consumption of the processors.The energy consumption results of the EEAPS scheduler are compared with the existing optimal Pfair and modified Pfair schedulers. This is displayed in Figure3. The graph clearly shows that EEAPS reduces 10% of energy consumption with respect to Pfair-M and 30% of energy consumption with respect to Pfair algorithm.Figure 3
Comparison of EEAPS energy consumption with Pfair algorithms.


## 7. Conclusion

The proposed energy efficient scheduling algorithm EEAPS for multiprocessor systems calculates the energy requirement of each task. Based on this the tasks are allocated to the processors through the auctioning mechanism. This model reduces the energy consumption of the system. It is more effective compared to the existing scheduling algorithms. It is so flexible and compatible to different task set for different processors. It is optimal for periodic and aperiodic tasks but it is not for sporadic tasks. This model allocates the dedicated processor to handle the sporadic tasks without missing the deadline.



---

*Source: 8382026-2017-02-15.xml*