Batyrkhan Omarov

Aigerim Altayeva

Young Im Cho
email: yicho@gachon.ac.kr

Smart Building Climate Control Considering Indoor and Outdoor Parameters

Keywords: HVAC systems, fuzzy logic, thermal balance, indoor microclimate

Heating, ventilation, and air conditioning (HVAC systems) account for the majority of the energy used in buildings. Consequently, any business has the potential to realize significant cost savings by improving control of HVAC operations and increase the efficiency of the system it uses. Using a highly efficient HVAC equipment can lead to significant energy and emissions savings. The entire structure of the building in combination with the enhanced comfort zone can produce a much greater savings. Extended comfort includes the use of concepts such as providing a warm, but drier air using a desiccant dehumidification in the summer, or the colder air from the warm walls of windows and warm in winter. In addition, high efficiency HVAC can provide enhanced thermal comfort for people, as well as to contribute to the improvement of environmental quality in the room. The paper explores thermal process and the affecting parameters, and introduce fuzzy logic based energy consumption model based on controlling of HVAC devices.

Introduction

Individuals spend most their time in an indoor environment and comfort is one of the most important issues with respect to staying indoors. Environmental quality of an interior environment is directly dependent on its organization and content. Therefore, the task of maintaining a comfortable environment is extremely important for health, good spirit, and human activity. Several parameters can be adjusted to achieve comfort in a room-air temperature, humidity, air quality, speed of movement of air throughout the room, oxygen content in the air, ionization of air, and noise level [START_REF] Arcos-Aviles | Fuzzy Logic-Based Energy Management System Design for Residential Grid-Connected Microgrids[END_REF]. A deviation of the aforementioned parameters could result in the deterioration of the normal state of an individual. This can lead to the disruption of thermal balance as well as result in a negative impact on health and productivity.

Prior to determining the microclimate of a room and determining any adjustments, it is necessary to find a certain method to determine the real condition of several parameters, i.e., to conduct a study of the microclimate.

An important stage in creating a system to manage temperature and humidity conditions involves the development of greenhouse facility models. This reflects the processes occurring within a system from two different standpoints, namely the synthesis of algorithms and the analysis of management quality. If the model requirements are adequate from the second standpoint, then the development of models with respect to the first class of problems should consider the satisfactory requirements as well as the current level of scientific support task synthesis algorithms. According to this classification key [START_REF] Chaouachi | Multiobjective Intelligent Energy Management for a Microgrid[END_REF][START_REF] Zhang | Framework for Multipoint Sensing Simulation for Energy Efficient HVAC Operation in Buildings[END_REF] there are two groups of climate models as follows: a) A fundamental model aimed at solving problems of the object properties of analysis and quality control systems. The models in this group of physical phenomena are described by differential equations (usually in the state space). Parameters in the models of this group involve a physical interpretation. b) Black box models involve solution-oriented control algorithms synthesis problems. They are based on the specific synthesis problem using either static models (regression, polynomial, based on the use of neural networks, fuzzy sets) or dynamic models (usually in the form of differential equations in which the coefficients are determined from experimental data by identification methods, and a clear relationship is absent between the physical parameters and structural parameters of the greenhouse).

The present study used a schematic model of the microclimate as a basis for the development of both classes of models.

Indoor Microclimate Thermal Balance

Individuals only experience wellness and comfort within a narrow range of thermal conditions. Hence, the natural climate of a limited number of geographical locations is conducive for the comfort of individuals. In most regions, climate conditions are comfortable only for a limited time daily and for a limited time period annually. A building is an enclosure that protects individuals against external conditions. Thus, the interior of a building should provide a comfortable environment. Thermal balance is a principle in which the entire building is considered an entity with a number of energy sources and sinks. A thermal balance corresponds to the net amount of all gains and losses. The energy efficiency of a building is defined through its thermal balance.

Typically, energy flows in cold climates are either welcome gains (sources) or unwelcome losses (sinks) based on the time of year and external conditions. It is necessary to balance the gains and losses that result in the residual energy to create comfortable indoor conditions. Q i -Internal heat gain corresponds to the total amount of internal energy gains. This includes heat emitted from human bodies, electrical devices, and artificial lighting.

Q c,T -Conductive heat loss corresponds to energy lost by the transmission of heat through the building envelope. Q s -Solar heat gain corresponds to the total amount of energy input induced by incoming solar radiation that heats indoor air and thermal mass in the building. Q v -Ventilation heat loss or gain is caused by supply of fresh air; removal of stale indoor air to remove smells, CO 2 , and other contaminants; infiltration of cold air and exfiltration of warm indoor air through cracks in the building envelope; mixing of air from different temperature zones; and mechanical ventilation. This is expressed as follows:

Heat Losses: Q Tv + Q i,Sink + Q s = Q sink Heat Sources: Q s + Q T + Q v + Q i,Source = Q source A thermal equilibrium exists when Q sink = Q source If Q sink < Q source ,
then the temperature inside the building increases.

If Q sink > Q source , then the building cools down.

Additional systems and technologies are required for heating or cooling in buildings in which a thermal system is not naturally in equilibrium. It is necessary for the net heating energy to be provided by a heating system. The heating system experiences losses when heat is produced from a primary energy source. The total heating energy demand of a building corresponds to the sum of heating energy and heating equipment losses.

Parameters for sources and losses of energy can be categorized into building, environmental, legal, and usage parameters. The possibility of increasing the energy efficiency of a building exists when buildings are designed by considering given and fixed environmental and usage parameters.

How to ensure desired temperature in the room? An automatic temperature control system was used to formalize the description of the temperature regime of the process as the initial model. With respect to temperature control, it is necessary to consider the heat flows entering and exiting the system as well as the accumulation of thermal energy due to the cumulative capacity of the object. It is necessary to consider the existence of the following three thermal flows:

1. Q gainheat gain from the heating system.

2. Q envheat loss through the building envelope.

3. Q fr.airheat loss for heating of fresh air.

Given the volume of the indoor air (V), air density (𝜌), the specific heat capacity of air (C) and using the procedure of drawing up energy balance [START_REF] Chaouachi | Multiobjective Intelligent Energy Management for a Microgrid[END_REF][START_REF] Arcos-Aviles | Fuzzy Logic-Based Energy Management System Design for Residential Grid-Connected Microgrids[END_REF][START_REF] Chuan | Modeling and Validation of Electrical Load Profiling in Residential Buildings in Singapore[END_REF] results in the equation of heat that affects the change in air temperature inside a room as follows:

      ) ( ) ( ) ( ) ( . t Q t Q t Q dt t dT VC air fr env gain  (1)
where 𝜌 -air density (kg/m 3 ); 𝑉 -air volume (m 3 ); 𝐶 -specific heat of air (J/°С•kg); (𝑡) -indoor air temperature (°С); 𝑄 gain (𝑡) -Heat proceeding from the heating system (W); Σ𝑄 env (𝑡) -heat loss through the building envelope (W); 𝑄 fr.air (𝑡)heat loss for heating of fresh air (W).

Define heat loss through the building envelope [START_REF] Zhang | Framework for Multipoint Sensing Simulation for Energy Efficient HVAC Operation in Buildings[END_REF]:

     ) ( ) ( ) ( t T t T F k t Q outdoor air env (2)
where 𝑘heat transfer coefficient of building envelope (J/ (m 2 s •℃)); Fthe building envelope square (m 2 ); 𝑇 air (𝑡)air temperature inside the building (℃); 𝑇 outdoor (𝑡)outdoor air temperature (℃).

Heat losses for heating fresh air [START_REF] Zhang | Framework for Multipoint Sensing Simulation for Energy Efficient HVAC Operation in Buildings[END_REF] are given by the following expression:

) ( ) ( ) ( ) ( . . t T t T C t G t Q outdoor indoor air air fr air fr     (3)
where 𝐺 fr.air (𝑡) -fresh air consumption for ventilation premises (kg/s); 𝐶 airspecific heat of air (J/kg•℃); 𝑇 air -air temperature inside the building (℃); 𝑇 outdooroutdoor air temperature (℃).

The initial equation ( 1) for the temperature change is specified as follows:

        T C t G t T t T kF t Q dt t dT VC air air fr outdoor air gain ) ( ) ( ) ( ) ( ) ( .  (4)
The 𝑇 outdoor (𝑡) is accepted for the current temperature in the room 𝑇(𝑡). Additionally, (𝑡) is expressed as follows:

T C t G
     ) ( 1 ) ( ) ( 1 ) ( ) ( .
  T C t G kF t T t Q kF t T p T air air fr outdoor gain T      ) ( 1 ) ( ) ( 1 ) ( 1 . (7)
Hence, it follows that T(𝑡) was influenced by 𝑄 gain (𝑡), 𝑇 outdoor (𝑡), and 𝐺 fr.air (𝑡). The next section investigates the influence of these parameters.

1. Specifically, T outdoor denotes the value of outdoor temperature. The average annual temperature was determined by the schedule for a particular geographic location premises [START_REF] Zhang | Framework for Multipoint Sensing Simulation for Energy Efficient HVAC Operation in Buildings[END_REF][START_REF] Földváry | Analysis of Energy Performance and Indoor Climate Conditions of the Slovak Housing Stock Before and After its Renovation[END_REF]. The transfer function to change the inside and outside temperatures specified in Equation ( 7) is as follows:

) 1 ( 1 ) ( ) ( ) ( 1    p T p T p T p W T out T (8)
where 𝑇(𝑝) is the Laplace image for the indoor temperature, 𝑇outdoor(𝑝) is the Laplace image for the outdoor temperature, and 𝑇𝑇 is the time constant.

Temperature changing process includes an inertia property and describes a typical inertial link. In the winter, the process can be characterized by cooling the building with no active heating system and other sources of heat flows affecting the temperature balance.

Component

) ( 1 t Q kF gain considers the effect of the heating system that provides the heat necessary to maintain the heat balance of the room. The transfer function for adjusting the inside air temperature that is influenced by heat is as follows:

) 1 ( ) ( ) ( ) ( 1 2    p T k p T p T p W T gain T (9)
where 𝑇(𝑝) is the Laplace image for the indoor air temperature, 𝑄gain(𝑝) is the Laplace transform for the heating system, and kF k 1 1  is the heating system efficiency factor, 𝑇𝑇 is the time constant. This temperature change process also presents a typical inertial link. The process is inertial and presented by an inertial link. Increases in air flow led to decreases in air temperature, and vice versa, given a condition in which a positive temperature differential was present.

The complex influence of external factors on the indoor air temperature can be described by a block diagram as shown in Fig. 1.

Fig. 1. The relationship structure between indoor temperature and influencing factors

Thus, the indoor air temperature T(t) is an object of control that can represent a dynamic system. It is influenced by three input values, namely a value controlling action Q gain (t) and two perturbing T outdoor (t) and G fr.air (t) values. The control action represented by the feed of heat from the heating system with the transfer function WT2(p) described the transfer function of WT1(p), and heat loss during operation of the ventilation system for the preparation of fresh outdoor air. The control function was aimed at compensating disturbances in the form of heat loss through the building envelope (with a positive differential indoor T indoor (t) and the outside temperature Tout(t)). The consumption of fresh air G fr.air (t) was determined by the process of stabilizing loop air quality and its impact on the temperature T(t) as described by the WT3(p) transfer function.

Ensure predetermined air humidity in the room

The approach discussed above was used to describe the dynamic relationship between air humidity in the rooms with the control actions and influence disturbances. The initial equation involved using an equation given in a previous study [START_REF] Yu | An intelligent wireless sensing and control system to improve indoor air quality: monitoring, prediction, and preaction[END_REF] to describe the moisture content in the air as follows:

Identify applicable sponsor/s here. (sponsors) With respect to once-through ventilation systems, fresh air flow 𝐺 fr.air (𝑡) was approximately equal to that of the outgoing air flow 𝐺 outgoing_air (𝑡) given that the air is not compressed and has a constant density (ρ = 𝑐𝑜𝑛𝑠𝑡.) and given that the size of the room was unchanged (𝑉 = 𝑐𝑜𝑛𝑠𝑡.)). As a first approximation, it was assumed that the humidity of the outgoing air from the room was equal to the actual value of the humidity 𝑋 outgoing_air (𝑡)=𝑋(𝑡). The initial equation can then be expressed as follows:

) ( ) ( ) ( ) ( ) ( ) ( _ _ . . t G t X t G t X t G dt t dX V
) ( ) ( ) ( ) ( ) ( ) ( . . _ t G t X t G t X t G dt t dX V steam air fr air fr air outgoing     (12)
The equation is transformed by dividing it into 𝐺 outgoing_air (𝑡) as follows:   The value of the air humidity is determined by climatic conditions of a region. The impact of a parameter is considered via a transfer function that follows from a differential equation as follows: As observed from the transfer function, the process was described by the standard inertial and inertial element. The process involved room ventilation with outside air in the absence of external factors affecting the change in room humidity that led to indoor humidity values similar to the outdoor air humidity value.

) ( ) ( ) ( ) ( ) ( _ . _ _ _ t G t G t X G G t X dt t dX G V
) ( 1 ) ( ) ( 1 _ . _ _ t G G t X G G t X p T
  1 1 ) ( ) ( ) ( . 1    Xp air fr X T p X p X p W
Steam consumption is a reference variable that compensates for humidity deficit in the air. The parameter of the transfer function that binds air humidity (t) and exposure 𝐺 steam (𝑡) is considered as follows: The process is also inertial and described by a typical inertial link.

  1 ) ( ) ( ) ( 3 2    p T k p X p X p
The relationship between air humidity and air flow from the ventilation system is considered. It is assumed that

) ( 1 _ t G
air outgoing corresponds to G`(t) and the transfer function for the relationship between air humidity and a flow rate of fresh air G`(t) is derived as follows: Based on the transfer functions, the dependence of air humidity on the influencing factors can be described by the structure shown in Fig. 2, which corresponds to a structure of multiple connected systems.

  1 ) ( ) ( ) ( 4 ' 3    p T k p G p X

Fig. 2. Structure of the relations between the indoor humidity and influencing factors

The indoor air humidity X(t) was represented by a dynamic system with three input variables, namely a manipulated variable G steam (t) and two perturbing variables X fr.air (t) and G'(t). The control action described the transfer function W X2 (p) and was aimed at compensating air humidity due to operation disturbances described by transformation functions W X1 (p) and W X3 (p), as a result of the ventilation system with G fr.air (t) performance and X fr.air (t) fresh outdoor air humidity.

Experiment Results

The experiments were conducted at the Artificial Intelligent and Smart City laboratory in Gachon University. In the laboratory space, an area of 3×6 m 2 with a height of 2.5 m on one of the outer walls included six work areas separated by translucent partition walls (with a height 1.5 m) with personal computers. Fig. 3 illustrates the plan of the laboratory.

The room provided fresh air supply through the three dimension 400x400mm windows. The experimental studies indicated that at an outside temperature below T outdoor (-5 °C) during heating and ventilation operations, the air temperature significantly exceeded the critical temperature, and the relative humidity was in the range of 5-10%. Also, Fig. 4 shows the results of measurements of the relative humidity at elevations of 1.5 m above the floor space at T outdoor = -11 °C. The low relative humidity primarily negatively affected the respiratory organs. Furthermore, humid air is a poor conductor of static electricity. This contributed to the accumulation of humid air on the surface, and this exceeded the performance of the electromagnetic field with respect to the remote control at the workplace with PC and led to failure of the electronic equipment. Humidification units were installed to ensure standardized relative humidity values in the installation of central air conditioning. Nevertheless, the generation of vapor or fine water required significant energy costs. Furthermore, as shown by field studies, the humidified air flowed in the duct and over obstacles (e.g., silencers, etc.). There were significant losses due to moisture condensation on solid surfaces. Thus, a power saving humidification process is necessary to determine the minimum amount of normal air and water supply wherein the relative humidity of indoor air was given. For this purpose, a numerical simulation of the spatial distribution of relative humidity in the room was initially conducted through corresponding field experiments.

In the study, the results indicated the minimum amount of moisture in the supply air by which it was possible to determine the rated value of relative humidity of internal air. The moisture content corresponded to d = 5•10 -3 .

The numerical simulation results shown in Fig. 4 include temperature field distribution, air velocity, and relative humidity in the horizontal plane data distance of 1.500 m from the room floor.

Field temperatures (Fig. 4b) confirmed the impact of rising convective flow from heating devices, individuals, and PCs. Accordingly, downward flows were also observed near the outer wall. All heat flows corresponded to limited translucent partitions. In the workplace, the temperature values and variations in the range of 20-22°C satisfied the requirements of regulatory documents [START_REF] Boduch | Standards of human comfort: relative and absolute[END_REF]. 4c illustrates distribution of moving air speed. In the workplace, air velocity satisfied the requirements of normative documents [START_REF] Boduch | Standards of human comfort: relative and absolute[END_REF]. The rate of change of range of motion of air was in the range of 0.05-0.2 m/s, and it also satisfied the aforementioned requirements. The average values of relative humidity corresponded to the normal values. The range of changes in the relative humidity of the air in the occupied zone corresponded to 33-35%, as illustrated in Figure 4c. Minimum relative humidity in the range 30-32% was observed in the zones of influence of convective flows and translucent structures.

Conclusion

Holistic project explores the specific climate of the building open state of the climate zone, as well as the cultural characteristics that lead to the development of specific requirements. Sustainable energy management requires a focus on the environment and economic efficiency of users. Combined monitoring of comfort and energy consumption is set to gain a better understanding of the reaction of the building to a particular climate, as well as user behavior and acceptance of users. It shows how the extreme conditions in the building can be designed and effectively as refrigeration and air conditioning can be optimized in view of the hot/cold temperatures and high/low humidity.

 ( 6 )

 6 Equation (6) corresponds to a first order differential equation describing the temperature change as a function of defining and disturbances. It is assumed that kF VC TT   is a time constant. The equation was expressed in operational form as follows:

  of heat that is caused by changes in temperature compensation Δ𝑇 supply and indoor air in the room. The consumption of fresh air 𝐺 fr.air depends on the performance of the ventilation system and considers the value set by the control loop to stabilize the value of the qualitative composition of the air. The relationship between the change in air temperature 𝑇(𝑝) and the flow of fresh air 𝐺 fr.air (𝑝) is describedwith the following equation:

  𝑇 (𝑝) -Laplace transform for the indoor air temperature, 𝐺 fr.air (𝑝) -Laplace image for fresh air consumption, efficiency factor, and 𝑇𝑇 -time constant.

  density (kg/m 3 ); 𝑉 -air volume (m 3 ); X(𝑡) -absolute humidity in the room ( 𝐺 fr.air (𝑡) -fresh air consumption (kg/second); 𝑋 fr.air (𝑡) -absolute humidity of fresh air (kg water /kg air ); 𝐺 outgoing_air (𝑡) -outgoing air consumption (kg/s); 𝑋 outgoing_air (𝑡) -absolute humidity of the outgoing air ( water /kg air ); 𝐺 steam (𝑡) -steam consumption (kg/s).



  and the equation is expressed in an operational form as follows:

  be specified as follows:

  -Laplace image for indoor humidity, 𝑋 fr.air (𝑝) -Laplace image for indoor humidity, and of humidifying process.

  of the steam consumption.

-

  Laplace image for fresh air consumption, k 4 =G steam -the transformation coefficient for the fresh air consumption, and of humidifying process.

Fig. 3 .

 3 Fig. 3. The results of experimental studies of the distribution of the relative air humidity. 1desktops with PC; 2 -partitions; 3 -copying equipment

Fig. 4 .

 4 Fig. 4. Horizontal plane simulation results

Acknowledgements

This paper is supported by NRF project "Intelligent Smart City Convergence Platform-. Project number is 20151D1A1A01061271.


Joanna Karbowska-Chilinska

ORCID Pawel Zabielski

Maximization of attractiveness EV tourist routes

Keywords: Orienteering Problem with Time Windows, Tourist Trip Generation, Electric Vehicles, Evolutionary Algorithm

This paper presents model and an algorithmic approach for the problem of generation optimal tourist route for electric vehicles (EVs).

In the discussed problem a starting and a final point of a route are EV charging stations where tourist could charge the battery and then continue a journey. The main objective is to select to the route points of interests (POIs) which maximizing tourist attractiveness. Furthermore maximum length of the route is limited by the number of kilometers that the car can travel on a single battery charge. The model applied by us is the graph routing problem named as the Orienteering Problem with Time Windows (OPTW). In OPTW each location has positive score and a specific time interval in which a location can be visited. The solution of OPTW is a route (from the given starting to the ending point) with a fixed limit of length including a subset of locations. Moreover the route maximizes the total score of the locations visited in the predefined time intervals. As a solution we present the evolutionary algorithm with combines path relinking method instead crossover. Computational experiments are conducted on realistic database POIs and EV charging stations of Podlasie region in Poland. Tests results and execution time of the algorithm shows that the described solution could be a part of EV software module with generates the most interesting route.

Introduction

Nowadays carbon dioxide emissions have rapidly increased due to cities development and population growth. Transport has a high negative impact, on the environment degradation. In this reason in last years Green Logistics (GL) has received increasing attention in business as well as in a research field [3]. The main goals of GL are: maximum utilization of means of transport, development of green intelligent transportation systems which reduces the energy consumption, promotion of alternative fuels and vehicles with electric engines. Environmental aspects has been included to the optimization problem of vehicle routing problems (VRP) and also green vehicle routing problem is developed (G-VRP) [3]. In modern transportation system the electrical vehicles (EVs) are beneficial to the environment. EVs are more silent in operation and emission free compared to gasoline powered cars. However the driving range of a car depends largely on the capacity of the battery. It is important constraint which affect into routing planning for EVs. Batteries need to be charged a significant amount of time extending the route time. Literature describes some problems such as Electric Vehicle Scheduling Problem (E-VSP) [START_REF] Wen | An adaptive large neighborhood search heuristic for the Electric Vehicle Scheduling Problem[END_REF], Electric Vehicle Routing Problem (EVRP) [START_REF] Afroditi | Electric Vehicle Routing Problem with Industry Constraints: Trends and Insights for Future Research[END_REF], Electric Vehicles Routing problem with Time Windows and Recharging Stations(E-VRPTW) [START_REF] Schneider | The Electric Vehicle Routing Problem with Time Windows and Recharging Stations[END_REF] which solutions minimizing total traveled distance and give possibility of recharging batteries. In many touristic regions when clear air and national parks are important e.g. US [START_REF]Last access[END_REF] (California, Arizona, Orlando), Europe (Goms and Haslital region of the Swiss Alps [START_REF]Last access[END_REF]) the Electric Vehicle Tourism is popularized. Especially EV rental cars services are developed in those touristic regions. Tourist that use EV are satisfied when they could choose the most interesting POIs for each trip day and have not to care about charging the battery. It is comfortable if the battery charging can take place during e.g. an accommodation or the other break in a tour. The opening and closing time assigned to each POIs is additional constraint considered in a tour scheduling. To the best our knowledge any web, mobile and cars applications (e.g. rang assistant in BMW i3, EV TripPlanner for Tesla S users [START_REF]EV trip planner[END_REF]) do not select the set of POIs maximizing tourist satisfaction and taking into account the trip constraints such as: driving range of a car battery as well as POIs visiting hours. In this regard, this article presents the suitable model for the described problem. Moreover the effective evolutionary algorithm with path relinking instead crossover developed by us in [START_REF] Karbowska-Chilinska | Genetic Algorithm with Path Relinking for the Orienteerig Problem with Time Widows[END_REF] is used to generate the most satisfying tourist trip for EVs user with the aforementioned limitations. The graph optimisation routing problem called Orienteering Problem with Time Windows (OPTW) [START_REF] Tsiligirides | Heuristic methods applied to orienteering[END_REF] is used by us as the model. The considered graph have vertices with assigned score/ profit which was interpreted by us as a vertex attractiveness. An extension of OPTW is Team Orienteering Problem with Time Windows (TOPTW) where the given number of optimal routes (the parameter m) are generated, each one not exceeded the same constraint. Methods for the TOPTW could also be applied to the OPTW because the solution OPTW is only one optimal route (m=1). Both these problems belongs to the class NP-hard [START_REF] Vansteenwegen | The Orienteering Problem: A survey[END_REF]. In literature there are many meta-heuristic approaches giving satisfactory solutions e. g. local search methods [START_REF] Vansteenwegen | Iterated local search for the team orienteering problem with time windows[END_REF], tabu search [START_REF] Tang | A tabu search heuristic for the team orienteering problem[END_REF], ant colony optimisation [START_REF] Montemanni | Ant colony system for team orienteering problems with time windows[END_REF], variable neighbour search [START_REF] Labadi | The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search[END_REF], evolitionary inspired algorithms [START_REF] Ostrowski | Evolutioninspired local improvement algorithm solving orienteering problem[END_REF].

The remainder of the paper is organized as follows. The OPTW problem definition and its transformation to the problem of generation optimal tourist routes of EVs are presented in Section 2. In Section 3, we describe the concept of our evolutionary algorithm for solving the problem. The computational experiments run on realistic database POIs and EV charging stations of Podlasie region in Poland are discussed in Section 4. Finally the paper is concluded in Section 5. In this section we also lay the groundwork for further research.

The Problem Definition

In this work the optimization of an EV tourist route is modeled by the known graph problem called OPTW [START_REF] Kantor | The Orienteering Problem with Time Windows[END_REF], [START_REF] Vansteenwegen | The Orienteering Problem: A survey[END_REF]. In OPTW a set of the fixed locations is given. Each location i has a positive score S i , which is added after the visit of the location and a visiting time T i as well as a time window [O i , C i ], where O i and C i denote the opening and closing time, respectively. Service of a location must begin and end within this interval. It is permissible to wait before the opening time in order to visit profitable locations and maximize the total score. Each edge between locations i and j has a fixed cost t ij which is interpreted as distance needed to travel between locations. The OPTW goal is to determine a single route from the fixed starting to the ending point, that visits some of vertices within the fixed time windows and maximizes the total score. Moreover, the total cost of the edges on the route must be less than the threshold t max , and any vertex on the path can only be visited once. A feasible solution not violate any time window constraint on the fixed travel time limit (or travel length) of the route. In the case of the optimization of a tourist route of EV the set A of n POI(s) and the set B of m EV charging stations are given. Each POI i has assigned interval [O i , C i ] in which a visit can last and the fixed visiting time T i . The distances between each pair of POIs and each POI and EV charging station are denoted by t ij for i, j ∈ {1, ..., n + m} . Each POI i has a score S i ≥ 0 interpreted as its attractiveness. The EV charging stations have profits equal to zero. Moreover t max -the number of kilometers that the consider model of car can travel on a single battery charge is known. The starting and ending points, denoted by s and e respectively are selected among the points from the set B and their distance does not exceed the limit t max . The optimization goal is the generation a route from starting to the ending point that maximizes the total collected score (connected with attractiveness of the route), each POI is visited at most once in the predefined time interval and the length of the route does not exceed the limit t max . The problem can be formulate as a mixed integer problem with the decision variable: x ij = 1 if the direct link between i and j is included in a route, and x ij = 0 otherwise. Moreover start i denotes the start of service time at vertex i and M is a large constant. The objective function (1) maximizes the total collected profit of the route:

max n+m-1 i=1 n+m j=2 S i x ij . (1)
The constraint in (2) guarantees that the path starts at vertex 1 and ends at vertex n + m:

n+m j=2 x 1j = n+m-1 i=1 x in+m = 1. (2)
Constraint (3) requires that there may be at most one visit to any vertex:

n+m-1 i=1 x ik = n+m j=2 x kj ≤ 1 ∀k ∈ {2, ..., n + m -1}. (3)
The constraint in (4) ensures that the distance of the route is limited by t max :

n+m-1 i=1 n+m j=2 t ij x ij ≤ t max . (4)
Constraint ( 5) ensures the timeline of the route:

start i + T i + t ij -start j ≤ M • (1 -x ij ). ( 5
)
The start of the service is restricted by a time window as in ( 6):

O i ≤ start i ≤ C i ∀i = 1, ..., n + m . ( 6
)

Evolutionary Algorithm

To solve the presented problem, the evolutionary algorithm (EA) is used, previously developed by us to solve OPTW [START_REF] Karbowska-Chilinska | Genetic Algorithm with Path Relinking for the Orienteerig Problem with Time Widows[END_REF]. The EA for OPTW gives about 2% better results in comparison to other metaheuristics like iterated local search or greedy randomized adaptive search procedure [START_REF] Karbowska-Chilinska | Genetic Algorithm with Path Relinking for the Orienteerig Problem with Time Widows[END_REF]. In this reason we decide to use EA also to solve the presented in this paper problem. In the algorithm instead of the crossover a path relinking (PR) strategy is used. PR starts from selecting initial and guiding solutions to represent the starting and the ending points of the route [START_REF] Glover | A Template For Scatter Search And Path Relinking[END_REF]. Attributes from the guiding solution are gradually introduced into the intermediate solutions, so that these solutions contain less characteristics from the initial solution and more from the guiding solution. As a result, the selective moves between initial and guiding solutions provide the better routes than the input routes. In the literature PR significantly improves the different metaheuristics solving different optimization problems e.g. greedy randomized adaptive search procedure (GRASP) [START_REF] Campos | Grasp with Path Relinking for the Orienteering Problem[END_REF], variable neighbor search (VNS) [START_REF] Perez | A hybrid VNS-path relinking for the p-hub median problem[END_REF], genetic algorithms (GA) [START_REF] Huang | Genetic algorithm with Path Relinking for the Multi-Vehicle Selective Pickup and Delivery problem[END_REF] and tabu search (TS) [START_REF] Jia | Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem[END_REF]. Let N g denotes a number of the algorithm generations, P size describes the number of routes in the initial population. The basic structure of the EA is given as follows:

compute initial P_size routes; iter=0; not_imp=0; stop= false while (iter< Ng) and (stop =false) do iter++; evaluate the fitness value of each route; make a tournament grouping selection; perform path relinking; perform mutation; if no improvements in an attractiveness after 100 iterations then stop= true; od return the route with the highest profit value;

The subsequent steps of the EA are described in detail in the following subsections.

Initialization

In our approach a route is coded as a sequence of POIs but the starting (s) and ending (e) points are the fixed among EV charging stations. First the route is initialized by s and e stations. Then the following values are assigned sequentially to a POI selected to route: arrival i -arrival time at POI i, wait i -waiting time, if the arrival at a POI i is before opening time, start i and end i -starting and ending service time at POI i. Moreover, the maximum time the a visit i can be delayed without making other visits infeasible is calculated for each POI in the route as follows [START_REF] Vansteenwegen | Iterated local search for the team orienteering problem with time windows[END_REF]:

M axShif t i = M in(C i -start i -T i , wait i+1 + M axShif t i+1 ) (7)
Let POI l be the predecessor of charging station e in the route. In the subsequent steps a set of POIs is included. Each location v from this set is adjacent to location l and the station e and will satisfy the following conditions after insertion: (a) start v and end v are within the range [O v , C v ]; (b) the locations after v could be visited in the route; and (c) the current travel length of the route does not exceed the given t max . A random location v is chosen from this set. The values arrival v , wait v , start v and end v are calculated and the location v is inserted. After the insertion, the values arrival e , wait e , start e and end e are updated. Moreover, for each POI in the tour (from vertex e to s) the M axShif t value is updated as well. The route generation is continued for as long as POIs that have not been included are present and t max is not exceeded.

Selection

We use tournament grouping selection used by us in [START_REF] Zabielski | A genetic algorithm with grouping selection and searching operators for the orienteering problem Lecture Notes in Computer Science[END_REF] and in [START_REF] Karbowska-Chilinska | A Genetic Algorithm Solving Orienteering Problem with Time Windows[END_REF]. This selection yields better adapted individuals than standard tournament selection. In this method a set of P size routes is divided into k groups and the tournaments are carried out sequentially in each of the groups. t size routes are removed from the group, the chromosome with the highest value for the fitness function in the form:

T otalP rof it 3 T ravelT ime [START_REF] Huang | Genetic algorithm with Path Relinking for the Multi-Vehicle Selective Pickup and Delivery problem[END_REF] is copied to the next population, and the t size previously chosen individuals are returned to the old group. T otalP rof it denotes sum of POI's profits in the route and T ravelT ime is the time connected with the visit of the POI's as well as length of the route. After repetition of P size /k selection from the group currently analyzed, P size /k routes are chosen for a new population. Finally, when this step has been repeated in each of the remaining groups, a new population is created, containing P size routes.

Path Relinking

In this paper PR is used by us as alternative to the crossover. The method was developed by us with good results on benchmarks in the case of OPTW solution in [START_REF] Karbowska-Chilinska | Genetic Algorithm with Path Relinking for the Orienteerig Problem with Time Widows[END_REF]. Let V R1-R2 be the set of POIs present in a route R 1 and not presented in R 2 , and let V R2-R1 denotes the set of POIs present in R 2 and not in R 1 .

During PR(R 1 , R 2 ) we attempt to insert POIs from V R2-R1 into R 1 in the best possible positions. The total consumption time associated with inserting a POI j between i and k is calculated in the following way:

Shif t j = t ij + wait j + T j + t jk -t ik . (9)
In addition, we check whether the shift resulting from the new insertion exceeds the constraints associated with the previously calculated wait and M axShif t values for the vertices located directly after the newly inserted one. If the shift exceeds the constraints the vertices from V R1-R2 are removed to restore the possibility of inserting new POIs. For each vertex u from this set a ratio is calculated as follows:

RemovalRatio = (p u ) 2 end u -arrive u . ( 10
)
After this computation the POI with the smallest value for RemovalRatio is removed. This removal is repeated until we can insert some vertices into the path. Finally the vertex u with the highest value:

InsertionRatio = (p u ) 2 Shif t u ( 11
)
is selected for insertion if not exceed the mentioned constraints. After u is inserted, the values of arrive u , wait u , start u and end u are calculated. For each location in the route after u the arrival time, waiting time, start and end of service are updated. M axShif t values are also updated for the locations from the starting point to the ending point of the route. The process is repeated for as long as t max is not exceeded and the set V R2-R1 is not empty. Similarly, PR(R 2 , R 1 ) is performed by inserting vertices from V R1-R2 into R 2 . In result two new routes are created . If the fitness values of the new routes are higher than the fitness value of R 1 and R 2 , they replace them.

Mutation

In mutation phase a random route is selected from all routes. Two types of mutation are used by us a gene insertion or gene removal (the probability of each is 0.5). The mutation process is repeated on the selected route N m times, where N m is the parameter of the algorithm. In insertion mutation, all possibilities for inclusion of each new POI not presented in the route are considered. We check whether the shift resulting from the new insertion exceeds the constraints associated with the previously calculated wait and M axShif t values of the POIs located directly after the newly inserted one. The location u with the highest value of (p u ) 2 /T ravelT imeIncrease(u) is selected for insertion. T ravelT imeIncrease(u) is defined as the increased travel and visit time when POI u is included. After the insertion POI u into the route the values of arrival u , wait u , start u and end u are calculated. For each location after u the arrival time, waiting time, start and end of service are updated. The M axShif t value is updated for each location in the tour.

In the deletion mutation we remove a randomly selected POI in order to shorten the travel length. After the gene is removed, all locations after the removed gene are shifted towards the beginning of the route. Furthermore, the locations before and after the removed POI should be updated.

Computational Experiment

The EA was implemented in C++ and run on an Intel Core i7, 1.73 GHz CPU (turbo boost to 2.93 GHz). The computational experiments were carried out on realistic database 531 POIs and EV charging stations Podlasie region (Poland). Each POI is specified by coordinates, profit (determined on the basis of the votes of Internet users on the given object), time window and visiting time (randomly assigned). Shortest car distance between each pair of POIs and between POIs and battery charging stations were determined on the basis of the queries to Bing Map Service (Routes API). For comparison results we also tests another version of EA having crossover instead path relinking process. The version with crossover is denoted by EA CR and the version with path relinking by EA PR. In the crossover we selected two routes and in these routes we determine all genes which could be replaced without violating time windows conditions and the limit of route length. Finally a random pair is selected from all similar pairs of genes and this is a point of crossover. The new routes are created by exchange chromosome fragments from both parents from crossover point to the end of route. Many tests were carried out to establish the evolutionary algorithms parameters and determine convergence and sensitivity. The parameter values which represent the best trade-off between the quality of the solutions and the computational time are as follows: the number of routes in the initial population-P size =150, the number of groups in the tournament selection-k=15, the number of routes removed from the group t size =10, the mutation process is repeated on the selected route N m = 15 times. In tests we take different limit of routes length (t max ) because of different number of kilometers possible to drive on a single battery charge (this value depends on an EV brand and do not exceed 500 km). We recall that by the attractiveness we mean sum of scores connected with POI's included to the route. The attractiveness of routes balance (see Fig. 1) because of removing POI in deletion mutation. It can be notice that the attractiveness is not higher after 1000 iterations so the maximum number of algorithm generations was set to 1000. Additionally after each 100 generations the current population is checked and the algorithm is stopped if no improvements in attractiveness of route have been found. The comparison of the results according to the EA CR (the version with In tables the length is given in kilometers, execution time of the algorithm in seconds. The algorithm is run 15 times and in tables we place the best results from all runs. The execution time is calculated as a sum from 15 runs of algorithm. Results indicate that both algorithms give results in the comparable execution time (about 0.2 s). In the case when the starting and ending points are different (see Tab. 1) both versions give the same results in the length of route and attractiveness. The exception is t max =300 where EA PR gives better result in attractiveness than EA CR about 2%. When the starting and ending point is the same for t max =400, 500 (see Tab. 2) the length of routes is higher in case of EA PR than EA CR . However, in case of t max =400 for EA CR the attractiveness of a route is higher about 0.7% in comparison to EA PR. Both algorithms for t max = 200, 300 give the same attractiveness and the length. For t max =500 results EA PR outperform EA CR about 0.1%.

Conclusions and Further Work

In this paper we describe the problem of generation EV tourist routes which maximizing the attractiveness of a trip and the length do not exceeded the number of kilometers that a car can travel on a single battery charge . The problem is transformed to the graph routing problem named the Orienteering Problem with Time Windows. The evolutionary algorithm is presented by us as the solution of the problem. The tests on the real dates show that two versions of algorithm generate routes with similar attractiveness.The execution time of the algorithm is relatively short to use them in practice. Modern electric vehicles like BMWi3, Tesla S have navigation system to make driving easy and convenient. For example the range assistant with dynamic range map indicate the maximum distance that the vehicle can achieve in all directions from current location and the route is modified in real time. The navigation system in these cars do not select the set of POIs maximizing tourist satisfaction and do not take into account the trip constraints such as: driving range of a car as well as POIs visiting hours. In this regard the evolutionary algorithm described in this paper could be a module of the software application which suggest a driver the most attractiveness trip and the length of the route do not exceed a battery range. It easy notice that OPTW model allows describe route which are only one stage (i.e. the route ends when a battery is discharged). In our further research it is our intention to generate multistage route i.e. we want maximize the attractiveness of EV tourist routes which be continue after charging battery. In this case Team Orienteering Problem with Times Windows models such problem [START_REF] Labadi | The Team Orienteering Problem with Time Windows: An LP-based Granular Variable Neighborhood Search[END_REF].

Fig. 1 .

 1 Fig. 1. Convergence of the GA PR for tmax= 200-500 value

  Fig. 1, 2 illustrate generated routes by EA PR marked on Podlasie region map. In figures green points denotes POIs and their size depend on POI attractiveness. The starting and ending points (battery charging stations) are blue.

Fig. 2 .

 2 Fig. 2. EV route example: 1-352-24-370-56-344-441-442-5-2 (the battery charging stations are different).

Fig. 3 .

 3 Fig. 3. EV route example:1-2-357-442-344-433-381-431-23-1. (the battery charging station is the same)

Table 1 .

 1 Comparison EA CR and EA PR routes (starting and ending charge stations are different)

		EA CR		EA PR
	tmax length attractiveness time length attractiveness time
	200 198.970	1427	0.164 198.970	1427	0.168
	300 287.640	42629	0.154 296.420	43497	0.159
	400 393.224	51206	0.177 393.224	51206	0.174
	500 499.152	65460	0.221 499.152	65460	0.187

Table 2 .

 2 Comparison EA CR and EA PR routes (the starting and the ending charge station is the same)

		EA CR		EA PR
	tmax length attractiveness time length attractiveness time
	200 198.324	9695	0.165 198.324	9695	0.164
	300 285.147	42103	0.166 285.147	42103	0.160
	400 382.272	64014	0.171 386.839	63569	0.171
	500 488.931	66411	0.193 497.797	66466	0.209

Acknowledgements

The authors gratefully acknowledge support from the Polish Ministry of Science and Higher Education at the Bialystok University of Technology (grant S/WI/1/2014 and S/WI/2/2013).


Atanu Majumder
email: a.majumder007@gmail.com

Sangeet Saha
email: sangeet.saha87@gmail.com

Amlan Chakrabarti
email: amlanc@ieee.org

A K Choudhury

Task Allocation Strategies for FPGA Based Heterogeneous System on Chip

Keywords: Tasks allocation, FPGA, Branch and Bound, makespan time

FPGA based heterogeneous System On Chips (SOCs) have become a prospective processing platform for modern performance-sensitive systems, like automotive, avionics, chemical reactor etc. In such system, "makespan" time minimization plays a crucial role to achieve higher throughput as well as performance efficiency and thus, efficient task allocation schemes are indeed essential. This paper presents two task allocation algorithms for such FPGA based heterogeneous SOCs. The first allocation strategy is based on well known "Branch and Bound" optimization technique. Secondly, we proposed a novel heuristic based allocation mechanism, TAMF (Task Allocation Mechanism for FPGA based heterogeneous SOC). The simulation based experimental results reveal that both the strategies are able to provide lower makespan time over various simulation scenarios with acceptable runtime overheads. Achieved simulation results are further tested through a validation, carried out on practical ZYNQ SOC platform using standard benchmark task sets.

Introduction

Embedded systems are now-a-days employing FPGAs as a prospecting computing platform in various fields, ranging from avionic and automotive systems, nuclear reactors [START_REF] Hayashi | Application of fpga to nuclear power plant i&c systems[END_REF] to synthetic vision, object tracking [START_REF] Jin | Real-time multiple object centroid tracking for gesture recognition based on fpga[END_REF] etc. These FPGAs provide the performance efficiency of a dedicated hardware as well as flexibility of a general purpose processor. Recently, FPGAs are also being integrated in System on Chip (SOC) along with pre-fabricated Hard-core processors and Soft-core processors (Constructed using FPGA logic) [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF]. Such "Heterogeneous" systems contain different Processing Elements (PEs) with certain performance characteristic and can execute a set of tasks by assigning them on suitable PEs .

As an interesting example, such heterogeneous SOCs may be used as a performance efficient processing platform for automotive systems. In automotive systems [START_REF] Fürst | Autosar-a worldwide standard is on the road[END_REF], an ample amount of routine tasks need to be executed at system instantiation before its full phase functioning begins. Suppose, this SOC will perform the parallel execution of those initial set of tasks by appropriately assigning them on individual PEs, such that the completion time of all tasks are minimized and the system can quickly start functioning , after its instantiation. Therefore, it is essential to have well defined tasks allocation strategy, feasibility criteria for achieving high resource utilization with performance efficiency.

In this paper, we propose two novel static tasks allocation strategies for FPGA based heterogeneous SOCs. The first strategy is optimal "Branch and Bound" [START_REF] Corrêa | Branch and bound. Parallel Algorithms for Irregular Problems: State of the Art[END_REF] based task allocation technique and the second one, is based on heuristic approach, coined as TAMF allocation strategy. The contributions of this work can be summarized as follows:

-ILP based problem formulation for tasks assignments on FPGA based heterogeneous SOCs. -Employing the optimal "Branch and Bound" strategy for tasks assignments.

-Proposal of a new TAMF heuristic for faster tasks allotments.

-The experimental results reveal the efficacy of the proposed approaches in various simulation scenarios and also showed that the performance of TAMF is comparable to optimal Branch and Bound technique in most of the cases. -Validation of the proposed tasks allocation strategies on actual FPGA based heterogeneous SOC named ZYNQ [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF], using benchmark task sets.

The rest of the paper is organized as follows. The next section provides a brief discussion on important related works conducted. This is followed by a discussion on the system model adopted in this work in section 3. In section 4, we present the formulation of the tasks allocation problem. The proposed Branch and Bound based strategy and TAMF with illustrating examples, are discussed in section 5 and 6, respectively. Section 7 presents simulation based experimental results along with analysis and discussion on the same. The validation of the approaches on ZYNQ platform is discussed in section 8. The paper finally concludes in section 9.

Related Work

The generic problem of efficient task allocation on heterogeneous multiprocessor systems (with CPUs and GPUs or Processors having different instruction sets) have drawn considerable research interest in last few years [START_REF] Moreira | Scheduling multiple independent hard-realtime jobs on a heterogeneous multiprocessor[END_REF][START_REF] Satish | Scheduling task dependence graphs with variable task execution times onto heterogeneous multiprocessors[END_REF]. One stream of researchers [START_REF] Dhingra | Hybrid gasa for bi-criteria multiprocessor task scheduling with precedence constraints[END_REF][START_REF] Biswas | Multi-objective bayesian optimization algorithm for real-time task scheduling on heterogeneous multiprocessors[END_REF] have delved towards finding out the efficient allocation schemes for dependent task sets. On the other hand, a plethora of research works [START_REF] Baruah | Ilp-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors[END_REF][START_REF] Raravi | Task assignment algorithms for two-type heterogeneous multiprocessors[END_REF] are available which dealt with independent tasks sets. Authors in [START_REF] Baruah | Ilp-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors[END_REF], present an Integer Linear Programming (ILP) based tasks allotment scheme which guarantees the execution speedup upto a certain bound. In [START_REF] Raravi | Task assignment algorithms for two-type heterogeneous multiprocessors[END_REF], authors proposed two tasks assignment algorithms and discussed about the performance between migrative allocation approach which allows tasks migration among different types of processors and the non-migrative approach. Further, the problem of tasks handling in heterogeneous multiprocessor systems has spun-off in another direction where tasks could be static or dynamic in nature. In [START_REF] Kofler | An automatic input-sensitive approach for heterogeneous task partitioning[END_REF], authors considered static allocation where the tasks remain quantitatively constant through out the schedule. Similarly in [START_REF] Tabatabaee | Dynamic task scheduling modeling in unstructured heterogeneous multiprocessor systems[END_REF], authors proposed a dynamic allocation technique for heterogeneous multiprocessor system where tasks arrive in arbitrary instances. Minimization of the makespan1 time remains one of the principal research focus for researchers during allocation of tasks on heterogeneous multiprocessors. Thus, the researchers reported both fast heuristic based algorithms as well as optimal algorithms. Heuristics based independent task allocation strategies such as greedy approach, ant colony optimization techniques can be found in [START_REF] Luo | A revisit of fast greedy heuristics for mapping a class of independent tasks onto heterogeneous computing systems[END_REF]. In [START_REF] Chow | On mapping signal processing algorithms to a heterogeneous multiprocessor system[END_REF], authors proposed "Branch and Bound" based optimization strategy to achieve optimal solution. However, literatures about tasks allocation on FPGA based heterogeneous SOCs with proper optimization technique is merely a handful. The existing research works [START_REF] Pagani | Towards real-time operating systems for heterogeneous reconfigurable platforms[END_REF][START_REF] Li | Hardware/software partitioning based on hybrid genetic and tabu search in the dynamically reconfigurable system[END_REF] mainly employed hardware and software tasks partitioning as a tasks allocation strategy. The computation intensive tasks are being executed using FPGA fabric as a hardware task whereas tasks having less computation requirements are assigned to CPUs for execution as a software task. However, such allotments are often plagued with some limitations.

System Model and Assumptions

The system model, considered in this work is a FPGA based heterogeneous SOC. Our heterogeneous SOC contains an FPGA logic area and pre-fabricated Hard Cores (HCs). Further, the FPGA logic consists of Reconfigurable Regions or tiles (RRs) to execute hardware tasks and Soft Cores (SCs) (which constructed using FPGA logic) for software tasks execution. Hence, the system model under consideration contains three distinct types of PEs that is RR, SC, HC which completely resembles with modern ZYNQ [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF] architecture. Depending upon the SOC architecture, a particular type of PE could exist in multiple units.

Being an embedded system, the initial distributions of tasks are known at design time and each task is capable of running on each type of PEs. The proposed system model is further characterized by the following assumptions:

-A task cannot execute simultaneously on two distinct PEs at same instant and will be strictly executed on a single PE (till it execution requirements fulfills), which implies that tasks are non-migrative in nature. -Tasks are independent and thus, each PEs can operate in parallel to execute an individual task. -The cost of execution of each task over each distinct type of PEs is calculated through profiling and stored in offline. -PEs are capable to suffice the memory and I/O requirements of any task.

At system instantiation (time, t = 0), a fixed number of tasks will arrive for possible allotment on SOC and will be stored in a queue. Our strategy will attempt to allocate tasks, such that the makespan time gets minimized. Algorithms will operate through a dedicated HC (termed as allocator ) and will allocate tasks on respective PEs, as per the outcome. The pictorial representation of the proposed system model is shown in figure 1. A practical validation of the proposed system model on physical ZYNQ platform is illustrated in section 8.

Problem Formulation

Let us assume a task set τ = {T 1 , T 2 , ..., T N }, arrives for possible allotment over M distinct types of PEs where each j th type of PE is comprised of k j units. Such multiple units of a particular type of PE is individually referred as "core". It may be noted that the cost of execution of a task, will be same for all the cores which belong to a particular type of PE.

At a particular instant t, we can allocate atmost ( M j=1 k j ) tasks for parallel execution over all resources. Let, C i,j denotes the cost of execution incurred by T i when assigned to j th type of PE. Let us define a binary variable t ik j as follows:

t ik j =
1, when Ti is assigned to any one of the k j cores of j th type PE 0, otherwise Hence, we can illustrate the makespan time mk as:

mk = M ax{ η i=1 k j i =1 Cij * t ik j }, ∀j ∈ M (1)
where, η denotes the number of tasks assigned to j th type of PE.

In order to achieve lower mk, the objective function can be defined as :

Minimize mk (2)
Subject to the following constraints :

-The maximum number of tasks that can operate in parallel at a particular instant, can be atmost equal to the total number of available resources. -No task can simultaneously execute on different resources. Thus, at a particular instant, following equation has to be satisfied.

M j=1 k j i =1 t ik j ≤ M j=1 k j (3)

Branch and Bound Based Allocation Strategy

The above problem formulation clearly depicts that the proposed task allotment phenomena turns into an ILP based optimization problem and hence, NPcomplete in nature [START_REF] Papadimitriou | Computational complexity[END_REF]. Once a problem enrolls into the NP-complete category, it is very unlikely that an algorithm with polynomial time complexity can be designed in order to solve that one. The optimal Branch and Bound [START_REF] Corrêa | Branch and bound. Parallel Algorithms for Irregular Problems: State of the Art[END_REF], implicitly enumerates all of the feasible solutions by forming and traversing a "state space tree." 2 The tree is constructed using DFS [START_REF] Everitt | Analytical results on the bfs vs. dfs algorithm selection problem. part i: Tree search[END_REF] algorithm. At each node of the state space tree, the Lower Bound (LB) has to be calculated such that, search effort for probing the solution space can be reduced.

The cost incurred by the allocated tasks and the probable (underestimate) cost that will be incurred by the remaining unallocated tasks, will reflect as a sum in LB. Similarly, Upper Bound (UB), is calculated by considering the worst case cost (instead of minimum cost) of the unallocated tasks.

At a particular node (N T ), if the calculated LB appears to be larger or equal to the best solution result found so far, then the enumeration of the subtree rooted at N T can be skipped. It definitely implies that some nodes and subtrees will be "pruned-off" but it will obviously not jeopardize the optimality.

The pseudo-code for the proposed Branch and Bound strategy is shown in algorithm 1. In the following section, we will illustrate an example which will depicts our proposed Branch and Bound allocation strategy through a test case.

An example of Branch and Bound (BnB) based Strategy

Let us consider six tasks, τ = {T 1 , T 2 , ..., T 6 } that appear for the possible allotment (such that makespan time get minimized) in our proposed FPGA based heterogeneous SOC. Let us assume that system under consideration contains, one unit of RR (k 1 = 1), two units of SC (hence, k 2 = 2; core 1 and core 2 of SC) and two cores of HC (k3 = 2), one of which is dedicatedly acting as allocator. The performance of each task over these three (M = 3) distinct types of PEs is measured through profiling and displayed in Table 1. 3 It may be noted that the execution performance for both the cores of SC will be same and hence, not explicitly shown in the Table 1. The minimum execution cost demanded by HC is one time-unit for executing T 3 . Similarly, SC demands minimum three time-units for both the cores and RR demands minimum five time-units while executing the tasks T 6 and T 3 , respectively. Hence, Start V alue = 1+3+3+5 = 12.

A particular LB value can be calculated as follows: let us consider, T 6 is allocated in SC and thus, the incurred cost of T 6 will be 3 time-units. This allocation implies that, SC (core 1 ) and T 6 will be out of consideration for the next course of calculation. The minimum cost that will be incurred by remaining unallocated tasks can be found as: "minimum execution cost demand by HC": 1 + "minimum execution cost demand by SC (core 2 )": 3 + "minimum execution cost demand by RR": 5 . Hence, the corresponding LB becomes : 3+(1+3+5)=12. Similarly, by considering each individual allotment possibilities, LBs for each task corresponding to each type of processing resource is calculated and shown in tabular form in the Table 2.

Following the steps 6-8 of algorithm 1, min-LB can be found as 12 of T 6 for SC (core 1 ). Hence, U B of T 6 for SC can be calculated as follows: "maximum execution cost for HC": (14) + "maximum execution cost for SC (core 2 )": (11)+ "maximum execution cost for RR": (9) + cost of T 6 for SC (core 1 ) (3). Hence, U B of task T 6 for SC becomes : 37. Before the task allocation procedure begins, Allocated Value is initialized as zero. Thus, it may be observed that T 6 is satisfying the conditions stated in step 10 of the algorithm 1. Hence, T 6 successfully assigned to SC (core 1 ) and removed from the task set τ . In the same way, following the steps of algorithm 1, the allocation procedure will continue until τ becomes empty. The final task allocation scenario and corresponding mk is shown in Table 3.

TAMF-Working Principle

It is worth mentioning that Branch and Bound strategy demands higher degree of computations and may become computationally intensive when the number of task increases. Hence, we propose a novel heuristic based tasks allocation strategy called TAMF. TAMF will be executed once at system instantiation and tasks will be allocated as per the achieved task-to-PE mapping information.

At the beginning of TAMF, the task set τ gets ready with sorted execution cost of each task (in non-decreasing order) for different types of PEs. We assume that each type of PE provides minimum execution cost for atleast one task. Hence, TAMF will choose the element of the sorted sequence for allocation. It ensures that the task will be allocated to that particular PE for which it has the minimum execution cost. Now as soon as core/cores of a PE, finishes its preassigned execution, it will look for the next most eligible candidate task T α . T α can only be allocated to a "free"4 PE, if and only if the following two conditions hold alternatively: i. The execution cost of the T α is minimum for the free PE (among all PEs). ii. The execution cost of the T α for the free PE ≤ average execution cost of T α .

Here, both the conditions attempt to ensure that T α should completes with its lower execution requirement and thus, maximizing the probability of having minimum mk. Moreover, the allocation of T α to any other PE might not be able to provide better mk. TAMF will continue its own operation till any unallocated task remains. The pseudo-code for TAMF is depicted in algorithm 2.

TAMF in work: an example

Let us consider, the same set of tasks τ as shown in Table 1. As stated earlier, in this case τ contains all the parameters in a sorted fashion. Let us consider T 1 as a first candidate for allocation. It may be noted that the execution cost of T 1 , related to each PEs is already being stored in a sorted sequence. T 1 consumes minimum execution cost 3 time units while executes in SC. On the other hand, the average execution cost of T 1 over all PEs becomes: {(3+4+7)/3}. It may increases by keeping N fixed, the number of traversed node (AF prun) as well as CO BnB also increases, this is mainly because the additional overheads incurred in LB calculation for the increment in processing resources. This observations is also supported by figure 2(a). Table 5 also establishes the fact that TAMF demands less computational overhead than Branch and Bound based strategy. This observation may be attributed to the fact that being a heuristic based policy, TAMF does not implicitly enumerate all possible solutions instead, employs task selection mechanism with linear overhead and thus, costs less CO T AM F . Moreover, like BnB based strategy, increase in N also endorses increment in TAMF's overheads. However, if BnB based strategy and TAMF runs on an allocator whose frequency is 1.5 GHz then CO BnB and CO T AM F for N = 10 (with six processing resources) becomes 0.72 and 0.16 in milliseconds, respectively. Figure 2 makespan time (mk) produced by Branch and Bound based strategy and TAMF for number of tasks (N ) varying from 10 to 30 with constant number of process-ing resources as 8. From the respective figure, it is very much evident that in most of the cases, the efficiency of Branch and Bound based strategy and TAMF (in terms of mk) is comparable. Through a deeper observation, it can be observed that for N = 20 tasks, BnB based strategy provides mk = 18 (slightly lower) while TAMF produces mk = 21. However, TAMF will cost CO T AM F =552112 clock cycle which is 18.6% lower than the BnB based strategy (refer, Table 5).

Validation in Physical ZYNQ platform

Besides of the thorough theoretical and simulation studies, we have also validated the proposed strategies in actual FPGA based heterogeneous SOC (ZYNQ:ZC702) with synthetic task sets. The platform contains three distinct types of PEs that is the FPGA chip, dual core ARM Cortex-A9 processor and MicroBlaze (MB) processor. In the ZYNQ board, these ARMs are located in PS (Processing System) region and FPGA logics are separate as PL (Programmable logic) region [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF]. In PL, the Reconfigurable Regions (RRs) are done to carry out the hardware task execution and Soft Core (SC) MB executes software tasks. In PS, ARMs are prefabricated and hence, termed as Hard Core (HC). It may be observed that the ZYNQ architecture resembles our adopted system model. Xilinx PlanAhead 14.4 and XPS, EDK, SDK 14.4 [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF] tools are have been used for this validations.

Customization of the platform

For the purpose of the meaningful validation, the ZYNQ platform needs to be architecturally customized.

• In the PL, RR was properly marked and the execution of each task on that RR is ensured by properly maintaining the UCF [START_REF] Crockett | The Zynq Book: Embedded Processing with the Arm Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc[END_REF] constraints.

• Two MBs are added in the PL using XPS IP-core. RR and MB are connected through inter PL bus architecture.

• The RR, MB both are operated with PLs clock (FCCLK) of 50 MHz frequency.

• One ARM core (core-0) is kept for possible task allotment and another ARM (core-1) works as allocator. These ARMs are operating using 667 MHz frequency.

• Both the PS and PL are communicating through GP0 and GP1 port. PS and PL are also connected with OCM (On-Chip Memory) using AXI bus.

Synthetic Task Set Creation

To cope-up with the customized platform, it is essential to have proper set of tasks. In our validation, we have constructed and profiled the sets of task. These task sets are taken from well known Benchmark task set named ITC'99 benchmarks [START_REF] Davidson | Itc'99 benchmark circuits-preliminary results[END_REF]. This Benchmark consists of numerous task such as "Adder", "Decoder", "Integer to Float conversion" etc.

• Synthetic hardware tasks are created using VHDL code and performance of each such tasks is measured forming proper test-bench.

• Software tasks are written in system-c code. The execution performance of those tasks are measured for both MB and ARM. The execution cost of sample tasks is shown in Table 6 • At design time, each hardware task is stored in its executable format (as .bit) in external memory. In ZYNQ, such .bit files are stored in SD card.

• Software tasks are stored in executable (.elf ) format in the external SD card.

• This external memory is present in PS region and linked with the allocator.

Implementation and Outcomes

Both the strategies (Branch and Bound based and TAMF) are coded in systemc, compiled and stored (as respective executable format) in the SD card. At the system instantiation, ZYNQ starts booting from SD card and core-1 of ARM (allocator ), initiates the execution of the respective strategy. After completion, the tasks allocation information are stored in a log file, in the external memory. Now core-1, will start allocation by transferring the respective .bit file to the PL (if a task is assigned to PL region) and .elf to MB, core-0 of ARM respectively. In the similar way, the allocator further reads the task assignment information from the stored log file and allocates tasks (in their respective executable format) from external memory to appropriate PEs.

Table 7 shows the performance of BnB based allocation strategy and TAMF over different number of processing resources, on the ZYNQ platform. From the table, it can be concluded that the trends of results in the actual platform concur with the outcomes obtained through simulation studies.

Conclusion

In this paper, we presented methodologies for allocating task sets on FPGA based heterogeneous SOC such that makespan is minimized. An optimal strategy and heuristic based technique is discussed. We designed, implemented and evaluated the algorithms using simulation based experiments and the simulation results were further validated through real implementation on ZYNQ platform.

Fig. 1 .

 1 Fig. 1. System Model

Algorithm 1 : 6 Find 12 Remove T β from the τ ; 13 else 14 Choose the next min-LB; 15 Go to step 10 ; 16 Find

 16121314151016 Branch and Bound Based Allocation StrategyInput: Task set τ , M types of PEs (including k j units) Output: Allocation of tasks which provide minimum mk. 1 For each PE, calculate the minimum task execution costs; 2 Sum up those minimum execution costs and assign to Start Value; 3 while τ is not empty do 4 for each task Ti ∈ τ do 5 Find the LB for each type of PEs; task T β which provides min-LB (minimum LB) for say, j th PE; 7 {In case of multiple existence of min-LB, choose any arbitary T β }; 8 Calculate U B of T β for that j th PE; 9 Allocated Value = Summation of the costs of already allocated task/tasks ; 10 if (min-LB + Allocated Value) ≥ Start Value AND min-LB < U B then 11 Assign T β to j th PE; mk using equation 1.

Fig. 2 .

 2 Fig. 2. Performance of BnB Based strategy and TAMF

Table 1 .

 1 Tasks Parameters

	P PEs P P HC P	P P Tasks T1 T2 T3 T4 T5 T6 P 4 5 1 14 5 5
	SC	3 7 3 11 4 3
	RR	7 9 5 9 9 5

Table 2 .

 2 Tasks LBs

	P PEs P	P P HC	P Tasks T1 T2 T3 T4 T5 T6 P P 15 16 12 25 16 14
		SC	12 16 15 20 13 12
		RR	14 16 15 16 16 12

Table 3 .

 3 Tasks allotment and mk: BnB Based

	PEs	Allocated	Consumed mk
		Task(s)	Cost
	HC	T2, T3	5+1=6
	SC Core1 <= T1, T5 3+4=7	9
		Core2 <= T6	3
	RR	T4	9

Table 4 .

 4 Tasks allotment by TAMF

	P PEs P	P P HC	P Time 1 2 3 4 5 6 7 8 9 P P T2 T3
	SC (core1)	T1	T6
	SC (core2)	T5
		RR		T4

Table 5 .

 5 Performance of Branch and Bound (BnB) based strategy and TAMF BF Prun; AF Prun: Numbers of expected and actual nodes traveled respectively, COBnB: Computational overheads in terms of Clock ticks for Branch and Bound based strategy, COT AM F : Computational Overheads for TAMF

	PEs 6	N	BF Prun	AF prun	COBnB	COT AM F
	HC -2	10	> 100 2	330	1080551	243112
		15	> 100 2	720	2775883	384098
	SC -2	20	> 100 2	1260	5490998	535518
		25	> 100 2	1950	9675934	679567
	RR -2	30	> 100 2	2790	15481722	832551
	HC -3	10	> 100 2	440	1755676	252107
		15	> 100 2	960	4621855	391578
	SC -3	20	> 100 2	1680	10279888	552077
		25	> 100 2	2600	17389423	724583
	RR -2	30	> 100 2	3720	28938997	877661
	N : Number of tasks,

Table 6 .

 6 Benchmark tasks execution overhead ( clock ticks unit) on ZYNQ

	PEs Dec	Add	I2F	Lg2
	HC 460158 455920 464819 451817
	RR 750 35112 70089 465335
	SC 41312 42736 87733 581298

Table 7 .

 7 Performance on ZYNQ

	PEs N BF	AF COBnB COT AM F
		Prun Prun
	HC -1 10 > 100 2 330 1268233 483468
	SC -2 -	-	-	-	-
	RR -2 20 > 100 2 1260 1988597 791436

It is the total length of the schedule i.e. when all the tasks have finished their execution.

A tree constructed in the solution space.

The values corresponding to tasks are depicting the execution cost in terms of timeunits.

The PE finished its earlier execution and currently not executing any task.

routine tasks within an embedded system typically lies within this range[20]

Acknowledgments

This work was supported in part by the TCS Research Fellowship Award, granted to Sangeet Saha and TEQIP Phase-II project of University of Calcutta, India.

be observed that T 1 satisfies the condition, stated in step 4 of the algorithm 2. Hence, T 1 is allocated on SC (arbitrarily, core 1 ) and removed from τ .

By following the same way, T 2 gets allocated in HC but T 3 could get allocated in HC when T 2 finishes. Similarly, other tasks will be allocated by the following algorithm 2. The respective allocation and execution sequence of each task is shown in Table 4. It is very much evident that all the tasks complete their execution requirements within 9 time units and thus, mk = 9.

Experiments and Results

The performance of the Branch and Bound based strategy and TAMF have been evaluated by conducting simulation based experiments using randomly generated task sets whose execution cost corresponding to a PE have been taken from normal distribution. The performance metrics used for evaluation are makespan time as defined in equation 1 and the Computational Overheads, CO (measured in terms of consumed clock cycles / CPU ticks). Data sets for various values of N (10 to 30) 5 , have been generated on systems containing total 2 to 8 cores of three types of PEs. Each result is generated by executing 50 different instances of each data set type and then taking the average over these 50 runs.

Table 5 shows the performance variation of Branch and Bound (BnB) based strategy and TAMF over different number of processing resources. It may be observed from the third and fourth column of the table, that BnB based technique can effectively eliminate the possible numbers of solution (by traversing less number of nodes) through an intelligent pruning technique. Moreover, as N increases, the computation overhead related to the LB estimation also increases (lines 4-5, Algorithm 1) and thus, the CO BnB of overall strategy increases. Another notable observation reveals that when the number of processing resources