18885MarianaCarvalho_30035ThalissonSchumaber_30036RubenMachado.pdf

Trabalho Prático: Job-Shop COMPUTAÇÃO DE ALTO DESEMPENHO Nuno Lopes 18885 Mariana Carvalho 30035 Thalisson Schumaher 30036 Rúben Machado MESTRADO EM INTELIGÊNCIA ARTIFICIAL APLICADA 2023/2024 TRABALHO PRÁTICO:...

Trabalho Prático: Job-Shop COMPUTAÇÃO DE ALTO DESEMPENHO Nuno Lopes 18885 Mariana Carvalho 30035 Thalisson Schumaher 30036 Rúben Machado MESTRADO EM INTELIGÊNCIA ARTIFICIAL APLICADA 2023/2024 TRABALHO PRÁTICO: JOB-SHOP 2 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO Índice Introdução......................................................................................................................... 4 1. Descrição do problema......................................................................................... 4 2. Objetivo................................................................................................................ 5 3. Abordagem para Atribuição dos Tempos de Início.............................................. 5 4. Restrições na implementação de uma Solução..................................................... 6 Implementação Sequencial............................................................................................... 6 1. Branch-and-Bound............................................................................................... 6 2. Implementação...................................................................................................... 7 Função Principal....................................................................................................... 7 Definição das Estruturas de Dados:.......................................................................... 8 Leitura do Ficheiro de Entrada................................................................................. 9 Funções Auxiliares................................................................................................... 9 Implementação Paralela com Partilha de Memória.......................................................... 9 1. Proposta de particionamento.............................................................................. 10 2. Implementação.................................................................................................... 10 3. Características do programa paralelo:................................................................ 11 Variáveis globais partilhadas.................................................................................. 11 Variáveis locais de cada thread.............................................................................. 11 Secções críticas....................................................................................................... 12 Técnicas de exclusão mútua................................................................................... 12 Análise do Desempenho................................................................................................. 12 1. Mecanismo de medição do tempo de execução.................................................. 12 2. Tabela de comparação........................................................................................ 13 COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 3 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 4 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO Introdução Este trabalho prático tem como principal objetivo a utilização das capacidades de programação paralela através do modelo de partilha de memória, para a resolução de um problema de cálculo computacional. 1. Descrição do problema Considere o problema de Job-Shop, que é a alocação de recursos para a concretização de um trabalho. No problema de Job-Shop existem várias máquinas que conseguem realizar operações. Para se produzir um trabalho (job) é necessário realizar um conjunto de operações, por sequência, em várias máquinas. Como as máquinas não conseguem realizar todas as operações, cada trabalho é uma sequência de operações, em que cada operação tem de ser feita numa máquina específica. Adicionalmente, porque cada trabalho é distinto dos restantes, a sequência de máquinas de cada trabalho pode não ser a mesma dos restantes trabalhos, i.e., cada trabalho tem a sua própria sequência de máquinas. Contudo, a ordem das máquinas para cada trabalho tem de ser respeitada, i.e., uma operação de um trabalho que deve ser executada numa máquina específica só pode começar quando a operação anterior desse mesmo trabalho já terminou; assim como a operação seguinte do trabalho só pode começar depois da operação atual terminar. Finalmente, realizar uma operação numa máquina demora tempo. Cada operação de cada trabalho demora um tempo específico, que pode ser distinto para cada operação. Uma máquina só consegue fazer uma operação de cada vez, assim, quando começa uma operação, só fica livre para novas operações após esta terminar. Identificam-se assim as duas restrições deste problema: 1. As operações de cada trabalho têm de ser realizadas por ordem. A segunda operação de um trabalho só pode começar depois da primeira operação do mesmo trabalho estar concluída, e assim sucessivamente para todas as operações seguintes do mesmo trabalho; 2. Uma máquina só consegue executar uma operação de cada vez, pelo que havendo duas operações para a mesma máquina, uma só pode começar depois da outra ter terminado. Uma característica do problema, que simplifica as restrições, é que um trabalho não depende dos restantes trabalhos, i.e., os trabalhos são independentes entre si. Assim COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 5 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO sendo, as operações de um trabalho não interferem com as operações dos restantes trabalhos, desde que a máquina para onde estão atribuídas esteja livre. 2. Objetivo O objetivo do problema é apresentar um escalonamento válido, isto é, definir um tempo de início para cada uma das operações (de todos os trabalhos), de modo a cumprir as restrições, i.e., uma operação só começa após a anterior ter terminado, e uma máquina só está ocupada com uma operação de cada vez. Após encontrar uma solução válida, o segundo objetivo é otimizar (reduzir) o tempo de execução total do escalonamento. O tempo de execução total do escalonamento é definido como o tempo necessário para concluir todas as operações do plano de escalonamento. Um problema pode ter várias soluções distintas que são todas válidas e que podem ter uma duração total do tempo de produção distinta. O pior caso possível pode ser definido como o tempo necessário para executar todas as operações, uma de cada vez, até estarem todas concluídas. O melhor tempo possível pode não ser fácil de encontrar; contudo sabe- se que não poderá nunca ser inferior ao tempo que demora a executar qualquer um dos trabalhos individualmente (porque uma operação não pode nunca começar antes da anterior). A solução algorítmica deve apresentar um resultado melhor do que a “pior solução possível”, mas que não tem de ser o melhor possível. 3. Abordagem para Atribuição dos Tempos de Início Existem várias possíveis abordagens para esta atribuição. O método de atribuição de tempos de início mais simples de usar é fazer uma travessia sequencial para todas as operações de todos os trabalhos, e atribuir um tempo de início a todas as operações, respeitando a sua duração, independentemente da máquina ou trabalho a que pertençam. Esta abordagem corresponde ao caso sequencial, que também é o mais longo possível, sem intervalos, em que se executa uma operação e apenas uma operação em cada instante de tempo. Existem outras possíveis abordagens para a atribuição de tempos, válidas, desde que tenham em atenção o cumprimento das restrições do problema, como por exemplo Branch & Bound ou Shifting Bottleneck. Uma abordagem que consegue encontrar a melhor solução ótima para o problema, isto é, a combinação que demora menos tempo de todas as possíveis, denomina-se Branch COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 6 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO & Bound. Esta abordagem constrói uma árvore de pesquisa, onde regista as várias soluções encontradas e o seu resultado. No final do algoritmo, é escolhido o nodo da árvore com a melhor solução, i.e., a que tem o tempo de conclusão da última operação mais baixo. Cada nodo da árvore representa uma potencial fonte de paralelismo, dado que os seus cálculos podem ser feitos de modo independente em relação aos cálculos dos restantes nodos da árvore. Finalmente, foram publicados alguns trabalhos sobre implementações paralelas do método de Branch & Bound, algumas abordando o problema de job-shop. Estes trabalhos podem ser considerados, mas não é obrigatório a sua implementação; devem ser considerados como referências. 4. Restrições na implementação de uma Solução A escolha do algoritmo que o grupo queira usar é livre. A única restrição que se requer para a implementação é a não utilização de estruturas dinâmicas com apontadores. A implementação de grafos ou listas deve ser baseada em arrays (estáticos sem apontadores) e não listas ligadas ou equivalentes (com apontadores). Podendo ser utilizado um único apontador inicial para um array, mas não é permitida a utilização de apontadores internos na estrutura. Podem ser usados vários arrays. Implementação Sequencial 5. Branch-and-Bound O algoritmo utilizado para fazer a atribuição dos tempos de início das operações foi um algoritmo de branch-and-bound. Sendo este um método utilizado para resolver problemas de otimização combinatória, onde o objetivo é encontrar a melhor solução possível. Funcionando da seguinte forma: ▪ Verifica se existem operações pendentes para cada trabalho: ▪ Identifica a próxima operação a executar para o trabalho em questão (‘i’): ▪ Calcula o tempo de início da operação considerando o tempo em que a máquina ficará livre e o tempo de fim da operação anterior do mesmo trabalho, se aplicável: COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 7 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO ▪ Calcula o tempo de fim da operação tendo em conta o tempo de início, e somando o tempo de processamento da operação: ▪ Cria um novo nó copiando o estado atual e atualizando as informações relevantes, tais como: tempo de início e finalização das operações e progresso do trabalho: ▪ Verifica se o tempo final da nova operação é menor que o melhor tempo encontrado até agora. ▪ Executa a verificação de finalização quando todas as operações de todos os jobs estiverem concluídas. Calcula o tempo total necessário e, se for o melhor encontrado, atualiza o melhor tempo e nó. 6. Implementação Função Principal O algoritmo recebe como parâmetro de entrada um ficheiro com os dados de entrada, na função main onde são também chamadas as funções para ler os dados, executar o COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 8 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO algoritmo de Branch and Bound, e escrever os resultados no ficheiro de saída. É também a função principal que mede e imprime o tempo de execução do algoritmo. Definição das Estruturas de Dados: A estrutura Operation representa uma operação específica que deve ser executada como parte de um trabalho. Cada operação tem um identificador de trabalho, um identificador de máquina e um tempo de processamento. A estrutura job representa um trabalho que consiste em várias operações. Cada trabalho tem um conjunto de operações e um número máximo de operações que precisa de ser realizado. A estrutura Schedule armazena o horário de início e fim de uma operação específica numa máquina. É utilizada para manter o controlo do cronograma de execução de cada operação. A estrutura Node representa o estado atual do processo, incluindo o tempo atual, cronograma, progresso dos trabalhos, tempo de ocupação das máquinas e tempos de COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 9 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO finalização dos trabalhos. Leitura do Ficheiro de Entrada O ficheiro de entrada contém as informações sobre as operações que devem ser realizadas em cada máquina para cada trabalho. Cada linha do ficheiro contem dois números: o primeiro representa o identificador da máquina e o segundo o tempo de processamento da operação nessa mesma máquina. Assim, é necessária a sua leitura e processamento. Com a informação nele contida é preenchida a estrutura de dado job. Funções Auxiliares A função compare_shedules() é uma função auxiliar para ordenar operações pelo tempo de início, utilizada na escrita do ficheiro de saída. Existe ainda uma função para a escrita dos resultados, a qual escreve para um ficheiro o melhor tempo encontrado. Itera sobre cada máquina, escrevendo no ficheiro a máquina atual. Através da estrutura Schedule é criado um array temporário para os cronogramas das operações, ordenado pelo tempo de início. Por fim, para cada cronograma, os tempos de início e fim da operação são escrito também no ficheiro de saída. Implementação Paralela com Partilha de Memória COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 10 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO 7. Proposta de particionamento De maneira semelhante á implementação sequencial o algoritmo escolhido é o Branch and Bound. Sendo que neste caso as threads paralelas executam diferentes ramos da árvore de decisão. Cada thread trabalha de forma independente para explorar diferentes combinações de escalonamento de jobs. Isto é possível utilizando do OpenMP que marca um bloco de código como uma tarefa que pode ser executada de forma assíncrona por uma das threads disponíveis. Através da utilização do lock do OpenMP é necessário garantir que na verificação de melhor tempo a thread exclusão mútua durante a leitura e escrita das variáveis compartilhadas. 8. Implementação A implementação recebe como parâmetro de entrada o número de threads através do terceiro argumento da linha de comando, sendo este número de threads a utilizar para a realização do algoritmo paralelo. A implementação paralela conta com a mesma estrutura de dados utilizada na implementação sequencial. Sendo os dados e estado do escalonamento representado pelas estruturas job, operation, Schedule e node. As threads são inicializadas através da diretiva #pragma omp parallel, onde uma única thread inicia a execução do Branch and Bound: Cada thread executa a função Branch and Bound de forma independente, cuja base é semelhante á previamente explicada na implementação sequencial sendo que para a implementação paralela cada chamada recursiva de função é encapsulada dentro de uma tarefa paralela. Como múltiplas threads podem atualizar as variáveis best_time e best_node COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 11 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO simulraneamente utiliza-se o lock OpenMP para proteger a seção crítica onde estas são atualizadas. Apenas uma thread pode obter e libertar o lock, garantindo que as atualizações sejam feitas de forma exclusiva. 9. Características do programa paralelo: Variáveis globais partilhadas + Jobs: array de estruturas Job, contem as operações sendo este partilhado para leitura. + Best time: Variável que armazena o melhor tempo encontrado até o momento. É partilhada para leitura e escrita, protegida por um lock para garantir operações seguras em ambientes paralelos. + Best node: Estrutura Node que contém a melhor solução encontrada até o momento. É partilhada para leitura e escrita, também protegida pelo lock. + lock: Variável do tipo omp_lock_t utilizada para sincronização e exclusão mútua ao atualizar best_time e best_node. + NUM_MACHINES e NUM_JOBS: Variáveis globais que armazenam o número de máquinas e o número de jobs, respetivamente. São definidas globalmente e partilhadas para leitura. Variáveis locais de cada thread − new_node: Variável local dentro da função branch_and_bound, onde cada thread cria uma cópia local da estrutura. Node para explorar uma ramificação de procura. Cada thread trabalha de forma independente na sua cópia local do new_node. − node: Parâmetro da função branch_and_bound, passado por valor para cada chamada recursiva. Cada thread manipula sua própria cópia de node, garantindo isolamento e independência nas operações. − op_index, op, start_time, end_time: Variáveis locais dentro da função branch_and_bound utilizadas para controlar o progresso das operações e calcular COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 12 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO os tempos de início e término das mesmas. Cada thread possui as suas próprias cópias destas variáveis durante a execução. Secções críticas Tal como previamente mencionado as secções críticas da solução conta com a manipulação das variáveis globais best_time e best_node. Técnicas de exclusão mútua Os locks OpenMP são usados para garantir que apenas uma thread por vez tenha acesso a seções críticas do código, onde variáveis globais compartilhadas são modificadas. Além dos locks explícitos, a diretiva #pragma omp critical foi utilizada para criar regiões críticas que garantem a exclusão mútua. Garantimos asssim que a ordem de execução do programa seja determinística, ou seja, o resultado final seja independente da ordem de execução das threads. Análise do Desempenho 10. Mecanismo de medição do tempo de execução Sequencial & Paralelo O algoritmo Branch and Bound é executado repetidamente para cada combinação de matriz de entrada e número de threads, controlado por um ciclo while, sendo o tempo total de execução registado na variável execution_time. No final de cada ciclo registamos o tempo de execução e atualizamos o tempo COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 13 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO total de execução. No final mostra-se o tempo total de execução e o tempo médio de cada iteração. Exemplo de execução: Matriz 4x4 com 12 threads 11. Tabela de comparação Abordagem Tempo médio de Tempo médio de Threads execução 4x4 execução 5x4 Sequencial 1.382s 166.809s Sequencial Paralelo 1.560s 192.379s 1 Paralelo 0.907s 92.128s 2 Paralelo 0.434s 50.757s 4 Paralelo 0.271s 30.696s 8 Paralelo 0.250s 30.000s 12 Paralelo 0.255s 27.478s 16 Paralelo 0.250s 29.758s 32 Paralelo 0.330s 33.976s 64 Conseguimos observar para os dois casos que a partir de 2 threads o algoritmo verifica uma melhoria considerável em tempos de execução, continuando a ver melhorias até fazer o uso de 16 threads, apesar de 12 ser o número de núcleos presentes no CPU. No entanto, eventualmente conseguimos ver uma performance pior com 32 e 64 threads em termos de tempo. COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 14 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO A comparação do desempenho da execução paralela com a execução sequencial foi realizada através da fórmula de Speedup que calcula o racio entre tempo de execução sequencial T1, e o tempo de execução paralela Tp para p threads. Para o input 4x4: COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 15 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO O speed up inicial é baixo com 1 thread, pois o overhead da paralelização é maior do que o ganho. A partir de 2 threads, o speed up melhora significativamente, alcançando um pico com 12 threads. Após 12 threads, o speed up começa a diminuir, provavelmente devido ao overhead da gestão de muitas threads superando os ganhos de paralelização. Para o input 5x4: Observa-se uma tendência similar à matriz 4×4, com um baixo speed up com 1 thread. O speed up aumenta significativamente com mais threads, alcançando o pico com 16 threads. Após 16 threads, o speed up começa a diminuir, novamente sugerindo que o overhead da gestão de muitas threads torna-se maior que o benefício da paralelização. COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA TRABALHO PRÁTICO: JOB-SHOP 16 18885 MARIANA CARVALHO | 30035 THALISSON SCHUMAHER | 30036 RUBEN MACHADO COMPUTAÇÃO DE ALTO DESEMPENHO IPCA | MIAA