#All Imports import xml.etree.ElementTree as et import numpy as np import pandas as pd !pip install seaborn import seaborn as sns import scipy !pip install pandas_read_xml import pandas_read_xml as pdx import random import matplotlib.pyplot as plt from scipy.optimize import fsolve

#Create two Pandas Dataframes for the applications and for the platforms in the XML DFapp = pd.DataFrame(columns=['Deadline', 'Id', 'Period', "WCET"]) DFplat= pd.DataFrame(columns=["MCPId","CoreId","WCETFactor"]) #Another Dataframe to structure the Solution Sol = pd.DataFrame(columns=["Task", "MCP", "Core", "WCRT"])

#Iterate through the XML file to get all the needed data in order to be able to append them to the dataframes tree = et.parse("large.xml") root = tree.getroot() for primary in root.iter('Model'): for types in primary.iter("Application"): for tasks in types.iter("Task"): DFapp = DFapp.append({'Deadline':int(tasks.get("Deadline")), 'Id':int(tasks.get("Id")), 'Period':int(tasks.get("Period")), 'WCET':int(tasks.get("WCET")) }, ignore_index=True) for types in primary.iter("Platform"): for mcps in types.iter("MCP"): for cores in mcps.iter("Core"): DFplat = DFplat.append({"MCPId":int(mcps.get("Id")), "CoreId":int(cores.get("Id")), "WCETFactor":float(cores.get("WCETFactor"))}, ignore_index=True)

DFapp.head()

DFplat['ID'] = DFplat.index DFplat.head()

# Mean laxity def mean_laxity(DFapp): return (np.mean(np.array(DFapp['Laxity'])))

# Laxity def Laxity2(DFapp): DFapp['Laxity'] = DFapp['Deadline'] - DFapp['WCRT'] return(DFapp)

# Priority function def priority(DFapp): DFapp["Deadline"] = DFapp["Deadline"] DFapp.sort_values(by="Deadline",inplace=True) DFapp.reset_index(drop=True, inplace=True) DFapp["Priority"] = DFapp.index.astype(int) return(DFapp) DFapp_prio = priority(DFapp) DFapp_prio.head()

# Allocation function def allocation(DFapp,DFplat): cores = [] WCETFactors = [] for task in DFapp['Id']: sample = DFplat.sample(1) cores.append(int(sample['ID'])) WCETFactors.append(float(sample['WCETFactor'])) DFapp['CoreIndex'] = cores DFapp['WCETFactor'] = WCETFactors return(DFapp) DFapp_allo = allocation(DFapp,DFplat)

def neighbor1(app,DFplat,N): tasks = random.sample(list(app['Id']),N) core_ids = [] for taskId in tasks: coreId = random.choice(list(DFplat['ID'])) core_ids.append(coreId) core_ids.append(int(app[DFapp['Id'] == taskId]['CoreIndex'])) app.loc[(app['Id'] == taskId),['CoreIndex']] = coreId app.loc[app['Id'] == taskId,'WCETFactor'] = float(DFplat[DFplat['ID'] == coreId]['WCETFactor']) return(app,np.unique(core_ids))

# Check schedulability(if task is schdulable or not) def check_schedulability(DFapp): return all(DFapp['Laxity'] > 0)

### CORRECT FUNCTION FOR WCRT def compute_WCRT(DFapp,core_ids): core_ids = np.unique(core_ids) ## new WCRT is calculated only for the cores in which something has changed, since it's useless to calculate it each time for every core also if it's the same as before for core in core_ids: subset = DFapp[DFapp['CoreIndex'] == core] ## create a subset of the tasks allocated to the same core counter = 0 for taskId in subset['Id']: if counter == 0: ## if the element has the highest priority in the subset, the WCRT of task J is only the computation time R = subset.loc[subset['Id'] == taskId, 'WCET'] * subset.loc[subset['Id'] == taskId, 'WCETFactor'] else: ## if the element has not the highes priority in the subset, the WCRT of task J is calculated accounting for higher priority tasks P = int(subset.loc[subset['Id'] == taskId, 'Priority']) ## priority of core J D = int(subset.loc[subset['Id'] == taskId, 'Deadline']) ## deadline of core J Ct = float(subset.loc[subset['Id'] == taskId, 'WCET']) * float(subset.loc[subset['Id'] == taskId, 'WCETFactor']) ## computation time of task J (without interference) R = Ct ## the response time of core J is set initially equal to the computation time without interferences T = np.array(subset[subset['Priority'] < P]['Period']) ## array with periods of tasks with higher priority than J C = np.array(subset[subset['Priority'] < P]['WCET']) * np.array(subset[subset['Priority'] < P]['WCETFactor']) ## array with computation times of tasks with higher priority than J I = np.sum(np.ceil(R/T)*C) ## interference time control = True ## initialize value for while cycle while control == True: R = I + Ct ## update WCRT I = np.sum((np.ceil(R/T))*C) ## calculate interference with new WCRT if (I + Ct) > D: ## check if it's NOT schedulable R = 2*D ## if it's NOT schedulable, give a very high value of WCRT (so laxity is negative for the check) control = False if abs((I+Ct) - R) < 1: ## if it IS schedulable and the error on the WCRT is less than 1, R = WCRT and interrupt while loop control = False DFapp.loc[(DFapp['Id'] == taskId),['WCRT']] = np.ceil(R) ## update value of WCRT counter = counter + 1 return(DFapp)

## Simulated annealing # inizialization N = 1 DFplat['ID'] = DFplat.index T = 10000 r = 0.003 DFapp = priority(DFapp) ## assign priorities to tasks DFapp = allocation(DFapp,DFplat) ## initial allocation DFapp, core_ids = neighbor1(DFapp,DFplat,N) ## generate neighbor DFapp['WCRT'] = np.nan DFapp = compute_WCRT(DFapp,np.unique(DFplat['ID'])) ## initial computation of WCRT DFapp = Laxity2(DFapp) ## initial calculation of laxity schedulability = check_schedulability(DFapp) ## initial check of schedulability if schedulability == True: laxity = mean_laxity(DFapp) elif schedulability == False: laxity = mean_laxity(DFapp)/100000 ## penalize laxity if taskset is not schedulable all_costs = [] all_costs.append(laxity) # loop while (T>1): DFapp_new = DFapp.copy() # IMPORTANT!!! OTHERWISE ALSO DFAPP IS UPDATED DFapp_new, core_ids = neighbor1(DFapp_new,DFplat,1) ## generate neighbor DFapp_new = compute_WCRT(DFapp_new,core_ids) ## update WCRT DFapp_new = Laxity2(DFapp_new) ## update laxity schedulability_new = check_schedulability(DFapp_new) ## check schedulability if(schedulability_new == False): laxity_new = mean_laxity(DFapp_new)/100000 ## penalize the laxity if the task set is not schedulable else: laxity_new = mean_laxity(DFapp_new) if (laxity_new > laxity): all_costs.append(laxity_new) laxity = laxity_new DFapp = DFapp_new else: prob = np.exp((laxity_new - laxity)/T) ## probability to accept the new laxity if worse than the previous rand = np.random.rand(1) ## random number between 0 and 1 if(prob > rand): ## condition to accept a worse solution all_costs.append(laxity_new) laxity = laxity_new DFapp = DFapp_new else: ## condition to refuse a worse solution all_costs.append(laxity) T = T*(1-r) ## reduce the temperature print(T) # plot the results plt.plot(all_costs[1:])

DFapp[DFapp['CoreIndex'] == 1]

DFapp["CoreIndex"].value_counts().plot.bar()

def xml_add(data,cores): xml = ['<solution>'] for index in range(len(data)): xml.append(' <Task Id="{0}" MCP="{1}" Core="{2}" WCRT="{3}" />'.format(data.loc[index]["Id"], int(cores.loc[data.loc[index]["CoreIndex"]]["MCPId"]), int(cores.loc[data.loc[index]["CoreIndex"]]["CoreId"]), data.loc[index]["WCRT"])) xml.append('</solution>') xml.append('<!-- Total Laxity: {0} -->'.format(all_costs[-1] * len(data))) return xml

xml = xml_add(DFapp,DFplat) with open("Solution.xml", "w") as txt_file: #txt.write(u'\uFEFF'.encode('UTF-8')) for line in xml: txt_file.write("".join(str(line)) + "\n")