Task Scheduling Optimization on Enterprise Application Integration Platforms Based on the Meta-heuristic Particle Swarm Optimization

Task Scheduling Optimization on Enterprise Application Integration Platforms Based on the Meta-heuristic Particle Swarm Optimization Daniela F. Sellaro Unijuí University Ijuí, RS [email protected] Rafael Z. Frantz Unijuí University Ijuí, RS [email protected] Inma Hernández University of Seville Espanha [email protected] Fabricia Roos-Frantz Unijuí University Ijuí, RS [email protected] Sandro Sawicki Unijuí University Ijuí, RS [email protected] ABSTRACT Companies seek technological alternatives that provide competitiveness for their business processes. Among these alternatives, there are integration platforms that allow you to connect applications to your software ecosystems. These ecosystems are often composed of local applications and cloud computing services, such as SaaS and PaaS, and still, interact with social media. Integration platforms are specialized software that allows you to design, execute and monitor integration solutions, which connect functionality and data from different applications. Integration platforms typically provide a specific domain language, development toolkit, runtime engine, and monitoring tool. The efficiency of the engine in scheduling and performing integration tasks has a direct impact on the performance of a solution and this is one of the challenges faced by integration platforms. Our literature review has identified that integration engines adopt task scheduling algorithms based on the textit First-In-First-Out discipline, which may be inefficient. Therefore, it is appropriate to seek a task scheduling algorithm that optimizes engine performance, providing a positive impact on the performance of the integration solution in different scenarios. This article proposes an algorithm for task scheduling based on the meta-heuristic optimization technique, which assigns the tasks to the computational resources, considering the waiting time in the queue of ready tasks and the computational complexity of Each task in order to optimize the performance of the integration solution. CCS CONCEPTS •Software and its engineering → Software performance ; Cloud computing; Real-time schedulability;␣ KEYWORDS Integrating Enterprise Applications, Optimization, Cloud computing, Runtime System, Task Scheduling Algorithm. 1 INTRODUÇÃO As empresas possuem um ecossistema de software composto por diversas aplicações que geralmente são desenvolvidas internamente ou adquiridas de terceiros. O avanço das tecnologias de desenvolvimento de aplicações e a incorporação de serviços de software disponíveis na internet têm deixado os ecossistemas de software ainda mais heterogêneos. Os processos de negócio de uma empresa precisam ser suportados por um conjunto de aplicações e serviços de software que integram seu ecossistema, porém, frequentemente, tais aplicações e serviços não estão preparados para trabalhar de forma conjunta. A Integração de Aplicações Empresariais (EAI) é o campo de estudo que oferece metodologias, técnicas e ferramentas para que os processos de negócio funcionem de forma sincronizada, promovendo repostas rápidas e confiáveis. As plataformas de integração são softwares especializados que permitem projetar, executar e monitorar soluções de integração, as quais conectam funcionalidades e dados de diferentes aplicações. Uma solução de integração implementa um fluxo de integração composto por distintas tarefas atômicas que são executadas ao longo desse fluxo. Gregor Hophe e Bobby Woolf [ 16 ] documentaram um conjunto de padrões de integração que tem inspirado o desenvolvimento de plataformas de integração de código aberto e que por sua vez organizam o fluxo de integração seguindo uma arquitetura Pipes&Filters [ 3 ]. Usualmente, essas plataformas fornecem uma linguagem de domínio específico, um kit de ferramentas de desenvolvimento, um motor de execução e uma ferramenta de monitoramento. A linguagem de domínio específico possibilita a descrição de modelos conceituais para soluções de integração. O kit de desenvolvimento é um conjunto de ferramentas de software que permite a implementação de soluções, ou seja, transforma uma solução conceitual em código executável. O motor proporciona todo o suporte necessário à execução das soluções de integração. A ferramenta de monitoramento é utilizada para detectar erros que possam ocorrer durante a execução de soluções de integração. O motor é o responsável pela execução das soluções de integração [14]. As tarefas da solução de integração são executadas por meio de recursos computacionais presentes no motor de execução, dentre os quais estão as threads de execução. Neste contexto, as threads são usadas para proporcionar que as tarefas sejam executadas de forma simultânea, por meio da programação multithreads [ 8 , 27 ]. Nesse tipo de programação, a criação de threads pode impactar o desempenho da execução de uma solução de integração. Um algoritmo de agendamento de tarefas inadequado aumenta o tempo de execução, impactando o desempenho da solução de integração. A abordagem mais comum é a contratação de mais recursos computacionais, porém essa alternativa é financeiramente onerosa e nem sempre viável. Nossa revisão da literatura identificou que os motores de integração adotam como política de agendamento de tarefas as políticas de prioridade e a First-In-First-Out (FIFO). Há propostas de algoritmos de agendamento de tarefas para máquina virtuais em sistemas distribuídos [ 2 , 23 ], porém não foram identificadas propostas que foquem na otimização de desempenho de motores de execução de plataformas de integração de sistemas. O agendamento de fluxo de trabalho tem sido amplamente estudado ao longo dos anos, nos quais os algoritmos se concentram na geração de soluções aproximadas ou quase ótimas, por se tratar de um problema não polinomial difícil [ 26 ]. Pandey et al. [ 22 ] propõem um algoritmo baseado em PSO para minimizar o custo de execução de um único fluxo de trabalho enquanto equilibra a carga da tarefa nos recursos disponíveis. Wu et al. [ 29 ] usam PSO para produzir um agendamento quase ideal, se preocupando em minimizar custo e tempo, mas assume que um conjunto limitado de recursos, sem levar em conta a elasticidade proporcionada com a computação em das nuvens. O algoritmo de Byun et al. [ 6 ] estima o número ótimo de recursos que precisam ser alocados para que o custo de execução de um fluxo de trabalho seja minimizado. Sua abordagem aproveita a elasticidade dos recursos da nuvem, mas não considera a natureza heterogênea dos recursos computacionais. A contribuição deste trabalho é a aplicação da meta-heurística Particle Swarm Optimization (PSO) para o contexto dos motores de execução, nos quais as políticas de agendamento adotadas, não consideram o tempo de espera na fila de tarefas prontas, nem a complexidade computacional das tarefas. PSO é fácil de implementar e existirem poucos parâmetros para serem ajustado, adequando-se ao problema de encontrar melhor agendamento das tarefas. Classificase como uma pesquisa exploratória, a medida que busca um método mais eficiente do que os existentes, na resolução do problema. Um resumo com ideias iniciais para esse trabalho foi apresentado em um seminário de pesquisa [ 25 ], e o presente artigo as discute de forma mais ampla e completa a proposta de um algoritmo que busca o mapeamento ótimo das tarefas para os pools de threads. O resto deste artigo está organizado como segue. A Seção 2 apresenta a formulação do problema. A Seção 3 descreve sucintamente a técnica PSO. A Seção 4 expõe a abordagem proposta. E a Seção 5 apresenta nossas conclusões e perspectivas de trabalhos futuros. 2 FORMULAÇÃO DO PROBLEMA Numa solução de integração, baseada no estilo arquitetural Pipes&Filters [ 3 ], os pipes são representados por canais de mensagens e os filters por tarefas atômicas que implementam um padrão de integração concreto e processam dados encapsulados em mensagens. A Figura 1 mostra o modelo conceitual de uma solução de integração para o problema Café, introduzido por Gregor Hohpe [ 17 ] modelado com Guaraná [ 14 ]. O modelo conceitual pode ser representado Figura 1: Solução de integração Café como fluxos de trabalho modelados como Grafos Direcionados Acíclicos, definidos por W(T,E), onde T={t1,t2, ..tn} é o conjunto de tarefas e E é o conjunto de arestas direcionadas. Uma aresta eij da forma (ti,tj) existe, se houver uma dependência de dados entre ti e tj , onde ti é tarefa pai de tj e tj é tarefa filha de ti . Logo, uma tarefa filha não pode ser executada até que todas as suas tarefas pai estejam concluídas. Considera-se que o motor de execução oferece uma variedade de recursos computacionais para execução das tarefas da solução de integração. Essa variedade de recursos é definida por pool de threads, com diferentes números de threads, onde uma thread é a unidade básica de processamento. Assim, assume-se que um motor de execução pode ter mais de um pool de threads e que o número de threads em cada um pode ser diferente, ou seja, um pool com uma quantidade x threads e outro com uma quantidade y. Considera-se ainda, que um motor de execução tem uma quantidade limitada de recursos computacionais δr , sendo um recurso computacional Pool , um pool de threads que tem um tipo Pooli , uma capacidade de processamento PPoolj . O tipo diferencia os pools, a capacidade de processamento é a quantidade de threads do pool. A capacidade de memória não é tratada; assume-se que é suficiente para executar as tarefas do fluxo de trabalho. Assume-se que para cada tipo de recurso, a capacidade de processamento é definida em termos de instruções por ciclo (IPC), que pode ser estimada [ 1 ]. Esta informação é usada no algoritmo, para calcular o tempo de execução de uma tarefa em um determinado pool de threads Pool . A variação do desempenho pode ser modelada pelo ajuste da capacidade do Pool e introduzindo uma degradação de desempenho deдPoolj [ 23 ]. O tempo de execução TEPoolj ti da tarefa ti em um Pool de tipo Poolj é estimado pelo tamanho Tamti da tarefa em instruções por ciclo (IPC), calculado pela Equação 1. TEPoolj ti =Tamti/(PPoolj∗ (1−degPoolj)) (1) O tempo médio de espera na fila de tarefas TFieij é definido como o tempo para transferir dados entre uma tarefa pai ti e sua tarefa filha tje assume-se que ele pode ser monitorado e medido. Finalmente, o tempo total de processamento TPPoolj ti de uma tarefa em um Pool é calculado na Equação 2, onde k é o número de arestas, ti é uma tarefa pai e sk representa o tempo gasto pelo motor na troca de pool de threads, de maneira que sk = 0, quando tietjsão processadas no mesmo pool esk= 1, caso contrário. TPPoolj ti =TEPoolj ti +( k Õ 1 TFij +sk)(2) O objetivo é encontrar um agendamento de tarefas que possibilite executar as tarefas da solução de integração em pools de threads do motor de execução, minimizando o tempo total de execução e sem aumentar a quantidade de recursos computacionais. O agendamento de tarefas é definido por A=(R,M,TR,TTE) , sendo R um conjunto de recursos; M o mapeamento de tarefas em recursos, TR , TR = |R|=n , o total de recursos, TTE o tempo total de execução. Um exemplo é mostrado na Figura 2, representando o agendamento para o fluxo de trabalho, em que cada uma das quatro tarefas é mapeada para ser executada por um dos três recursos disponíveis, e onde as tarefas pais são executadas antes das sua tarefas filhas, mantendo assim a dependência dos dados. R={r1,r2, ..., rn} é o conjunto de Figura 2: Agendamento para o workflow do Café. recursos (pools de threads) do motor de execução, onde cada recurso ri tem associado a ele um Pool do tipo Pooli , um tempo de início estimado para alocação do recurso estimado TIniri . e um tempo de finalização estimado TFimri . M representa um mapeamento para cada uma das tarefas do fluxo de trabalho e é constituído por tuplas mrj ti =(ti,rj,T Initi,T Finti) , significando que a tarefa ti será executada pelo recurso rj , com o início da execução agendado para TIniti e previsão de término em TFinti . A Equação 3 mostra como o tempo total de execução TTE é calculado: TTE =max{T Fimti:ti∈T}(3) Assim, o problema pode ser formulado como: encontrar um agendamento A com o menor tempo total de execução TTE da solução de integração, sem exceder um valor pré-definido para o total de recursos TR. Essa formulação é representada pela Equação 4: MinimizeTTE (4) sujeito a TR ≤δr 3 PARTICLE SWARM OPTIMIZATION Particle Swarm Optimization (PSO) foi introduzido por Kennedy e Eberhart em 1995 [ 10 ], e foi inspirado no comportamento social de organismos biológicos, mais especificamente na habilidade de algumas espécies de animais de trabalhar em conjunto para localizar boas regiões com fontes de alimento, assim como ocorre em cardumes e em bandos de pássaros [ 5 ]. Em outras palavras, é baseado em um enxame de partículas (Particle Swarm) que se movem pelo espaço e se comunicam para determinar uma direção de busca ideal. O PSO tem melhor desempenho computacional para este tipo de problema de otimização de funções não-lineares de alta dimensionalidade com variáveis contínuas, do que outros algoritmos [ 4 , 5 , 10 ] e tem menos parâmetros para ajustar, facilitando sua implementação. O PSO vem sendo utilizado com sucesso na solução de problemas da ciência e da engenharia devido à sua simplicidade, eficácia e robustez [ 2 , 4 , 11 , 15 , 21 , 23 , 26 , 28 ]. Apresenta como desvantagens, a necessidade de informação do tomador de decisão, parâmetros difíceis de ajustar, e ainda incapacidade de alcançar a Frente de Pareto, principalmente em problemas com multimodalidade, aqueles com múltiplas soluções ótimas, onde algumas podem ser melhores soluções globais e outras melhores soluções locais [ 12 ], porém adapta-se ao problema abordado. Cada partícula i do enxame S é representada por sua posição e sua velocidade. A posição é um vetor de n dimensões, cujos componentes representam os parâmetros da função objetivo. As partículas controlam a sua melhor posição pbest e a melhor posição global дbest, a melhor solução conhecida dentro de sua vizinhança. Inicialmente, as partículas do enxame possuem posições aleatórias no espaço de busca, obedecendo uma distribuição de probabilidade uniforme. Posteriormente, a posição xi(t) de cada partícula i na iteração t é modificada por uma velocidade estocástica vi(t) que depende da distância que a partícula está da sua melhor solução conhecida e da distância para a melhor solução conhecida dentro de sua vizinhança. Cada partícula i∈S se movimenta em cada dimensão j∈{1,2, ..n} do espaço de busca em um instante discreto de tempo t, segundo as Equações 5 e 6: −→ xi(t+1)=−→ xi(t)+−→ vi(t)(5) −→ vi(t+1)=w−→ vi(t)+c1r1−→ x∗ i(t)−−→ xi(t)+c2r2−→ x∗(t)−−→ xi(t) (6) onde: w= inércia ci= coeficiente de aceleração, i=(1,2) ri = número aleatório pertencente a uma distribuição de probabilidade uniforme , i=(1,2)eri∈[0,1] −→ x∗ i(t)= melhor posição da partícula i −→ x∗(t)= posição da melhor partícula da população −→ xi(t)= posição atual da partícula i Quando a vizinhança das partículas consiste no enxame inteiro, a posição −→ xi(t) é denominada de дbest . O vetor velocidade é quem orienta o processo de otimização, usando tanto o conhecimento adquirido particularmente pela partícula quanto o conhecimento adquirido pela partícula baseada na interação com sua vizinhança. O termo c1r1−→ x∗ i(t)−−→ xi(t) da equação de atualização da velocidade é a componente cognitiva e representa a experiência da partícula. Essa componente é a responsável pela tendência que a partícula tem de voltar para a melhor solução encontrada por ela no passado. O termo c2r2−→ x∗(t)−−→ xi(t) , por sua vez, é conhecido como componente social da equação da velocidade, e representa o conhecimento coletivo do enxame, sendo responsável por atrair cada partícula para a melhor solução encontrada por alguma partícula de sua vizinhança. O vetor velocidade −→ vi é a soma vetorial das componentes cognitiva e social com a inércia da partícula. A inércia w atua como uma memória da direção da velocidade anterior da partícula e impede que haja alterações bruscas na direção da velocidade partícula [ 11 ]. Assim, caso a partícula esteja se dirigindo a uma boa região, a descoberta de um novo líder social não alterará completamente essa direção. O papel da componente cognitiva é aproximar a partícula na direção da melhor posição encontrada por ela desde o início da busca. Dessa forma, a partícula deverá encontrar uma boa posição que provavelmente está próxima do seu líder cognitivo atual. Através da componente social, as partículas comunicam a informação sobre as melhores posições encontradas por elas desde o início do processo de busca, sendo considerada como a mais importante componente na equação da velocidade das partículas. O pseudo-código do PSO é apresentado no Algoritmo 1. A cada passo, o algoritmo irá mudar a velocidade de cada partícula em direção às posições pbest e дbest , onde a posição e a velocidade da partícula são atualizadas conforme as Equações 5 e 6, respectivamente. Um termo aleatório r pondera o quanto a partícula se movimenta em direção a esses valores, onde diferentes números aleatórios são gerados em direção à aceleração para pbest e дbest locais [ 20 ]. O algoritmo continuará a iterar até que um critério de parada seja alcançado. Geralmente, esse critério de parada é um número máximo de iterações especificado ou um valor aptidão prédefinido considerado bom o suficiente. A equação de velocidade contém vários parâmetros que afetam o desempenho do algoritmo e alguns afetam significativamente na convergência do algoritmo. A inércia w , por exemplo, é fundamental para a convergência do algoritmo. Ela determina o quanto as velocidades anteriores afetarão a velocidade atual e definirá um equilíbrio entre o componente cognitivo local e o global social das partículas. Se o valor da inércia for alto, a velocidade aumentará, favorecendo a busca global. Mas, se o valor for baixo, as partículas sofrerão uma desaceleração, favorecendo a busca local. Dessa forma, um valor w que equilibra a pesquisa global e local implica menos iterações para que o algoritmo possa convergir. Apesar de c1 e c2 não influenciarem diretamente Algorithm 1 Particle Swarm Optimization 1: d←n◃Inicializa a dimensão das partículas para d 2: x[i] ← xaleatorio ◃Inicializa a população de partículas com posições e velocidades aleatórias v[i] ← valeatorio 3: while criterioparada =f also do ◃ Repete enquanto o critério de parada não tiver sido alcançado 4: for ido1n ◃Para cada partícula calcula o seu valor aptidão, compara o valor aptidão da partícula com o valor pbest e com o valor de дbest 5: if xatual ↔pbest then ◃Se o valor atual da partícula é melhor do que pbest 6: x[i] ← xatual pbest ←xatual 7: end if 8: if xatual ↔дbest then ◃Se o valor atual da partícula é melhor do que дbest 9: x[i] ← xatual дbest ←xatual 10: end if 11: x[i] ← xcalculada ◃ Atualiza a posição e velocidade da partícula Equações 5 e 6 v[i] ← vcalcculada 12: end for 13: end while na convergência do PSO, o ajuste desses parâmetros agiliza e evita que o algoritmo seja pego em mínimos locais. O parâmetro c1 é referido como parâmetro cognitivo e o valor c1r1 , na Equação 6, define a relevância da melhor posição anterior. c2 é referido como o parâmetro social e c2r2 e determina o comportamento da partícula em relação a outros vizinhos. O número, a dimensão das partículas, o alcance e a velocidade máxima das partículas são parâmetros utilizados como entrada para o algoritmo, embora não componham a definição de velocidade. Quanto ao número de partículas, um valor alto costuma aumentar a probabilidade de encontrar o ótimo global. O valor deste número depende da complexidade do problema de otimização, mas um intervalo típico é entre 20 e 40 partículas [ 23 ]. Os valores para a dimensão das partículas e o alcance, no qual sua movimentação é permitida, são determinados unicamente pela natureza do problema que está sendo resolvido e de como ele é modelado para se adequar ao PSO. A velocidade máxima define a mudança máxima que uma partícula pode ter em uma iteração e normalmente seu valor é aproximadamente a metade do alcance de posição da partícula [ 23 ]. 4 ALGORITMO A modelagem de um problema PSO é dividida em duas fases: definição do problema e definição da função aptidão. A primeira consiste em definir como o problema será codificado, ou seja, definir como a solução será representada. A segunda, em definir o quão boa uma partícula será medida, ou seja, definir a função de aptidão. Já para transformar o problema PSO em um algoritmo, é preciso definir a partícula e sua dimensão. Na abordagem adotada neste artigo, uma partícula representa um fluxo de trabalho e suas tarefas, e dimensão da partícula representa o número de tarefas no fluxo de trabalho. A dimensão de uma partícula serve para localizar sua posição no espaço, definindo o sistema de coordenadas. No exemplo do workflow do Café, a dimensão da partícula é quatro, sendo sua posição especificada por um sistema com quatro coordenadas. Uma partícula movimenta-se num espaço limitado, denomina-se alcance. Na abordagem adotada neste artigo, o alcance é determinado pelo número de pools de threads disponíveis para executar a tarefa. Assim, o valor de uma coordenada no sistema de coordenadas, que define o espaço de movimentação da partícula, tem um alcance de 0 até o número máximo de pools de threads disponíveis. A parte inteira do valor de uma coordenada na posição de uma partícula corresponde ao número de pools de threads e representa o recurso computacional atribuído a uma tarefa definida por essa coordenada específica. Assim, a posição da partícula corresponde a um mapeamento da tarefa em recursos. Para o workflow do Café, valores para as quatro coordenadas(tarefas) do nosso sistema de coordenadas, no qual existem três recursos computacionais (pools de threads disponíveis), de forma que o valor de cada coordenada poderá variar entre 0 e 3. Há 4 tarefas para serem mapeadas, o que corresponde a dimensão 4 da partícula, portanto a posição da partícula terá 4 coordenadas. O índice da coordenada (de 1 a 4) corresponde a uma tarefa (de t1 a t4 ). O valor da coordenada é um número real de 0 a 3 , correspondendo ao número de recursos disponíveis para cada tarefa, com o máximo de 3 no nosso exemplo. Quando esse número inteiro é arredondado, é determinado o número de recursos disponíveis para cada tarefa. A função de aptidão deve refletir os objetivos do problema de agendamento, pois ela é usada para determinar o quão boa uma determinada solução é. Nessa abordagem, ela é minimizada e seu valor será o tempo total de execução TTE contido no agendamento A derivado da posição da partícula. Considerando que o motor de execução é capaz de aumentar elástica e dinamicamente a quantidade de recursos, o modelo de aquisição oferecido pela computação em nuvem parece ilimitado, ou seja, não há um conjunto de recursos disponíveis que pode ser usado no algoritmo. A estratégia é definir um conjunto inicial de recursos que o algoritmo pode usar para explorar diferentes soluções e alcançar o agendamento. O tamanho desse conjunto será nossa restrição TR ≤δr , conforme a Equação 4. Tal estratégia tem de refletir a heterogeneidade dos pools de threads (diferentes números de threads) e oferecer opções suficientes de PSO, a fim de que seja produzida uma partícula adequada, ou seja, a solução. O conjunto de recursos inicial e limitado conterá os recursos que podem ser usados. Se esse conjunto é muito grande, o número de agendamento possíveis aumentará, assim como, o espaço de pesquisa explorado pelo PSO, tornando difícil para o algoritmo convergir e encontrar uma solução adequada [23]. Para reduzir o tamanho do espaço de pesquisa, o qual será usado pelo PSO para encontrar um agendamento próximo do ótimo, considera-se um conjunto de recursos inicial Rinicial , composto por um Pool de cada tipo, para cada tarefa em P; onde P é o conjunto que contém o número máximo de tarefas que podem ser executadas em paralelo para um dado fluxo de trabalho. O algoritmo selecionará o número e o tipo apropriados de Pools para o motor de execução, dentro das opções contidas em Rinicial . Assim, reflete-se a heterogeneidade dos recursos computacionais e reduz-se o tamanho do espaço de busca, além de permitir mapear todas as tarefas que podem ser executadas em paralelo. O tamanho de Rinicial seria igual a |P|∗n , onde n é o número de tipos de Pools disponíveis, sendo ainda possível, que o PSO selecione mais de um recurso |P| , se necessário (a menos que n=1). O problema abordado possui a restrição TR ≤δr , utiliza-se uma versão do PSO que incorpora uma estratégia para tratar restrições [ 7 ]. Nela, sempre que duas soluções estão sendo comparadas e (i) ambas as soluções forem viáveis, então a solução com melhor aptidão é selecionada; (ii) se uma solução é viável e a outra não é, então a viável é selecionada; e finalmente, (iii) se ambas as soluções são inviáveis, aquela que violar menos a restrição é selecionada. No último caso, implica que uma medida de quanto uma solução viola a restrição precisa ser encontrada. O problema define o valor de violação de restrição de uma solução δk , a restrição pode ser atribuída a limitação de recursos que se deseja contratar na computação em nuvem ou simplesmente e a quantidade de threads físicas das máquinas que irão ser utilizadas na execução da solução de integração. Uma solução do PSO que utilize recursos próximos de δkserá preterida em relação a uma solução menos recursos. O Algoritmo 2 apresenta o pseudo-código para mapear a posição de uma partícula em um agendamento. O conjunto de recursos R para serem alocados e o conjunto de mapeamentos M de tarefas para recursos são inicializados sem elementos, ou seja, vazios, e tempo total de execução TTE é inicializado com o valor zero. Na sequência, o algoritmo estima o tempo de execução de cada tarefa do fluxo de trabalho para todo o recurso ri∈Rinicial . A representação é uma matriz em que as linhas representam as tarefas, as colunas representam os recursos e a entrada TempoExec[i,j] corresponde ao tempo gasto para executar a tarefa ti no recurso rj , calculado conforme a Equação 1. O próximo passo é o cálculo ou atribuição da matriz de tempo de transferência de dados, ou tempo de espera na fila de tarefas, o qual assume-se que está sendo obtido por um procedimento, não tratado nesse trabalho, tal como por uma ferramenta de monitoramento. Essa matriz é representada como uma matriz de adjacência ponderada do workflow DAG, onde a entrada TempoTrans f er[i,j] contém o tempo que leva para transferir os dados de saída da tarefa ti para a tarefa tj e esse valor é zero sempre que i=j ou não há aresta direcionada conectando ti (tarefa pai) e tj (tarefa filha). De posse dessas informações, o algoritmo inicia determinando a posição da partícula e construindo o agendamento. Para isso, itera para toda i do array de posição pos e atualiza R e M . Primeiro, determina a tarefa e o recurso que está associado à coordenada atual e seu valor. A estratégia usada para isso é a descrita anteriormente, a qual indica que a coordenada i corresponde à tarefa ti e seu valor pos[i] corresponde ao recurso rpos[i]∈Rinicial . Encontrados os componentes, ti e rj , de uma tupla de mapeamento mrj ti , o algoritmo calcula os demais, o tempo de inicio TInitie tempo de finalização T Fintida tarefa. O valor de tempo de início TIniti diferencia-se em duas situações. Na primeira, a tarefa não tem tarefa pai e, portanto, pode começar a ser executada, assim que o recurso alocado para ela rpos[i] estiver disponível, o que ocorrerá quando o referido recurso terminar a execução que estiver em andamento. Na segunda situação, a tarefa tem um ou mais pais e, nesse caso, além de esperar que o recurso para ela alocado esteja disponível, também terá que aguardar pelo término da execução das suas tarefas pai, além do tempo de transferência dos dados. O valor de TFinti é calculado baseado no tempo total de processamento e no tempo de início da tarefa. Para determinar o tempo de processamento TPrpos[j] ti , é necessário calcular o tempo de execução e o tempo de transferência. O primeiro é TempoExec[i,pos[i]] , enquanto o último é calculado pela soma dos valores do tempo de transferência TempoTrans f [i,f ilha(i)] para toda tarefa filha tf ilha(i) de ti , que está mapeada para rodar em um recurso diferente de rpos[i] . Esses dois valores são então somados para obter TPrpos[j] ti , como definido na Equação 2. Por fim, o valor de TFinti é obtido pela subtração de TIniti de TPrpos[j] ti . Calculados os elementos de m , adiciona-se recurso para R , se necessário. Quando o algoritmo termina de processar, cada coordenada do vetor posição, R conterá todos os recursos necessários e os tempos de início e finalização. Além disso, o mapeamento completo das tarefas para os recursos estará em M e cada tarefa terá um recurso atribuído a ela e o tempo estimado de início e o de término. Com essas informações o algoritmo pode calcular o TTE associado a solução atual, conforme Equação 2. Nesse ponto, o algoritmo calculou R , M e TTE e poderá construir e apresentar o agendamento associado para essa posição da partícula. Finalmente, os Algoritmos 1 e 2 são combinados para o agendamento próximo de ótimo. Na linha 4 do Algoritmo 1, em vez de calcular o valor de aptidão da partícula, gera-se o agendamento, conforme Algoritmo 2. Em seguida, usa-se Algorithm 2 Geração de agendamento Entrada: Conjunto de fluxo de trabalho de tarefas T Conjunto Inicial de recursos Rinicial Um array pos[|T|]representando a posição da partícula Saída: Um agendamento A 1: R=∅,M=∅,TTE =0◃Inicializa componentes 2: Calcula TempoExec[|T|×|Rinicial |] 3: Calcula TempoTrans f [|T|×|T|] 4: for ido0|T|−1 5: ti=T[i],rpos[i]=Rinicial [pos[i]] 6: if tinão tem pai then 7: TIniti=T Finrpos[i] 8: else 9: TIniti=(max {T Fintpai :tpai [∈ pais(ti)},T Finrpos[i]) 10: end if 11: exe =tempoExec [i] [pos [i]] 12: for cada filha tf ilha de tido 13: if tf ilha é mapeada para um recurso diferente de rpos[i] then 14: tras f er+ = TempoTrans f [i][c] 15: end if 16: end for 17: TPrpos[j] ti =exe +trans f 18: TFinti=TPrpos[j] ti−TIniti 19: mrpos[j] ti =(ti,rpos[i],TIniti,TFinti) 20: M=M∪ {mrpos[i] ti} 21: if rpos[i]<Rthen 22: R=R∪rpos[i] 23: end if 24: end for 25: Calcula TTE conforme Equação 3 26: A=(R,M,TR,TTE) oTTE como valor de aptidão nas etapas seguintes e é introduzido o mecanismo de manipulação de restrição, tal que TR ≤δr. 5 ACKNOWLEDGEMENTS This work was partially supported by the Brazilian Coordination for the Improvement of Higher Education Personnel (Capes), under postdoctoral research grant 88881.119518/2016-01 6 CONCLUSÃO A eficiência dos motores de execução das plataformas de integração está diretamente relacionado com o algoritmo de agendamento das tarefas e a alocação de threads para executá-las. Um algoritmo ineficiente leva a um aumento do tempo de execução, degradando assim o desempenho das soluções de integração. Este artigo propõe um algoritmo baseado na meta-heurística Particle Swarm Optimization para a alocação de threads em motores de execução baseados em filas FIFO. O algoritmo proposto atribui threads para as tarefas considerando a complexidade computacional da tarefa e a heterogeneidade na capacidade computacional das threads. Apesar do PSO localizar de forma rápida a região das boas soluções, é lento no ajuste fino da solução, como acontece em outras técnicas, como no caso dos algoritmos genéticos. Como trabalho futuro, pretende-se implementar esse algoritmo em um motor de execução da plataforma Guaraná para avaliar o ganho de desempenho com distintos casos de uso. REFERÊNCIAS [1] A. A. Abraham, G. M. King, D. V. Rosa, and D. W. Schmidt. Runtime capacity planning in a simultaneous multithreading (smt) environment, Aug. 16 2016. US Patent 9,417,927. [2] A. Al-maamari and F. A. Omara. Task scheduling using pso algorithm in cloud computing environments. International Journal of Grid and Distributed Computing, 8(5):245–256, 2015. [3] C. Alexander, S. Ishikawa, and M. Silvertein. A pattern language: towns, buildings, construction. Oxford University Press, 1977. [4] M. R. AlRashidi and M. E. El-Hawary. A survey of particle swarm optimization applications in electric power systems. IEEE Transactions on Evolutionary Computation, 13(4):913–918, 2009. [5] D. Bratton and J. Kennedy. Defining a standard for particle swarm optimization. In Swarm Intelligence Symposium, 2007. SIS 2007. IEEE, pages 120–127. IEEE, 2007. [6] E.-K. Byun, Y.-S. Kee, J.-S. Kim, and S. Maeng. Cost optimized provisioning of elastic resources for application workflows. Future Generation Computer Systems, 27(8):1011–1026, 2011. [7] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2): 182–197, 2002. [8] P. Dietel. Java how to program. PHI, 2009. [9] D. Dossot, J. D’Emic, and V. Romero. Mule in action. Manning, 2014. [10] R. Eberhart and J. Kennedy. Particle swarm optimization. In neural networks, 1995., Proceedings of the IEEE international joint conference on, pages 1942–1948. IEEE, 1995. [11] A. P. Engelbrecht. Computational intelligence: an introduction. John Wiley & Sons, 2007. [12] E. M. d. N. FIGUEIREDO. Algoritmo baseado em enxame de partículas para otimização de problemas com muitos objetivos. 2013. [13] M. Fisher, J. Partner, M. Bogoevice, and I. Fuld. Spring integration in action. Manning Publications Co., 2012. [14] R. Z. Frantz, R. Corchuelo, and F. Roos-Frantz. On the design of a maintainable software development kit to implement integration solutions. Journal of Systems and Software, 111:89–104, 2016. [15] Y. Fukuyama and Y. Nakanishi. A particle swarm optimization for reactive power and voltage control considering voltage stability. In Proc. 11th IEEE Int. Conf. Intell. Syst. Appl. Power Syst, pages 117–121, 1999. [16] B. Hohpe, Gregor; Woolf. Enterprise integration patterns: Designing, building, and deploying messaging solutions. Addison-Wesley Professional, 2004. [17] G. Hohpe. Your coffee shop doesn’t use two-phase commit [asynchronous messaging architecture]. IEEE software, 22(2):64–66, 2005. [18] J. Ibsen, Claus & Anstey. Camel in action. Manning Publications Co., 2010. [19] K. Indrasiri. Introduction to WSO2 ESB. Springer, 2016. [20] A. Lazinica. Particle swarm optimization. InTech Kirchengasse, 2009. [21] C. O. Ourique, E. C. Biscaia, and J. C. Pinto. The use of particle swarm optimization for dynamical analysis in chemical processes. Computers & Chemical Engineering, 26(12):1783–1793, 2002. [22] S. Pandey, L. Wu, S. M. Guru, and R. Buyya. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. In Advanced information networking and applications (AINA), 2010 24th IEEE international conference on, pages 400–407. IEEE, 2010. [23] M. A. Rodriguez and R. Buyya. Deadline based resource provisioningand scheduling algorithm for scientific workflows on clouds. IEEE Transactions on Cloud Computing, 2(2):222–235, 2014. [24] J. Russell and R. Cohn. Fuse Esb. Book on Demand, 2012. ISBN 9785510817041. [25] D. F. Sellaro. Particle swarm optimization para agendamento de tarefas na integração de aplicações empresariais. V SFCT, 14, 2017. [26] T. Sousa, A. Silva, and A. Neves. Particle swarm based data mining algorithms for classification tasks. Parallel Computing, 30(5):767–783, 2004. [27] A. Tanenbaum. Modern operating systems. Pearson Education, Inc., 2009. [28] F. Van Den Bergh and A. P. Engelbrecht. A study of particle swarm optimization particle trajectories. Information sciences, 176(8):937–971, 2006. [29] Z. Wu, Z. Ni, L. Gu, and X. Liu. A revised discrete particle swarm optimization for cloud workflow scheduling. In Computational Intelligence and Security (CIS), 2010 International Conference on, pages 184–188. IEEE, 2010.